Алгоритм Чейтина для распределения регистров: сколько цветов используется с R регистрами?

Question

В моей лекции о распределении регистров / алгоритме Чейтина кажется, что мы строим граф помех и затем пытаемся найти k-раскраску этого графа, где k = R, если мы можем использовать R регистров в целевой архитектуре , Однако, если мы передадим значение, не будет ли это означать, что нам нужен дополнительный регистр для загрузки значений из памяти перед их использованием в инструкциях, и, таким образом, мы можем использовать только значения k = R-1 для алгоритма Чейтина?

Answer 1

Вы все еще можете использовать k = R. Когда вы проливаете значение, вы добавляете код сброса, который сохраняет и извлекает это значение (обычно в стеке, но существуют другие альтернативы). Это заменит исходный виртуальный регистр с высокой степенью помех рядом новых виртуальных регистров, которые существуют только в течение короткого времени и (мы надеемся) имеют меньшую степень. Теперь вы можете сделать еще одну попытку окраски, и если она все еще не удалась, вы повторяете процесс разлива, пока не добьетесь успеха.