Почему компиляторы строят граф при распределении регистров?

Я исследовал распределение регистров и задавался вопросом, почему все они строят графики из списка живых регистров, когда может быть лучший способ сделать это. Я думаю, что они могли бы это сделать, когда количество живых регистров пересекает количество доступных регистров, тогда регистры могут быть сброшены. Вот пример (псевдосборка):

## ldi: load immediate
## addr: add registers and store in arg 2
## store: store memory at offset from stack pointer
.text
    main:
        # live registers: {}
        ldi    %t0, 12             # t0 = 12
        # live registers: {t0}
        ldi    %t1, 8              # t1 = 8
        # live registers: {t0, t1}
        addr   %t0, %t1            # t1 = t0 + t1
        # live registers: {t1}
        store  -4(%sp), %t1        # -4(%sp) = t1
        # live registers: {}
        exit

Я выложил живые регистры в ассемблерном коде. Теперь все учебные пособия и тексты строят отсюда графики интерференции и т. Д. Но вместо этого (как я упоминал выше) они могли смотреть на живые регистры. Например, если это была машина с одним 1 регистром, тогда, когда действующие регистры равны {t0, t1}, нам нужно будет выбрать регистр для сброса. Я считаю, что это намного проще, чем построить график и делать все остальное, чтобы проверить, не должны ли мы пролить регистры. Я знаю, что незнание не глобально (кто-то, должно быть, подумал об этом и посчитал это неподходящим), так что же я здесь не вижу?


assembly compiler-construction graph-algorithm cpu-registers register-allocation
person xilpex    schedule 22.06.2020    source источник
comment
Как вы выбираете, какой реестр проливать? t0 или t1? предположим, что наш текущий набор регистров равен {t0}, затем {t0, t1}, затем {t1}, затем {t1, t2} и затем {t2}   -  person user253751    schedule 24.03.2021

Ответы (2)


arrow_upward
8
arrow_downward

Построение графика не обязательно, например, алгоритм Linear Scan позволяет избежать построения графика. Очевидно, он используется JIT-компиляторами, такими как V8 и HotSpot, потому что он быстрый, а компромисс заключается в менее оптимальном принятии решений.

Линейное сканирование является более сложным, чем просто однократное сканирование и выдача данных, когда у вас заканчиваются регистры. Вместо этого вы находите живые диапазоны и проверяете, когда они перекрываются. Это может неплохо работать даже с некоторыми ветвлениями и циклами.

Я предполагаю, что ваш упрощенный алгоритм может довольно сильно выродиться в разветвленный код, если вы не умеете использовать одни и те же временные регистры на обеих сторонах ветви и такой анализ, который выполняет линейное сканирование. Как говорит @supercat, не весь код является прямолинейным. Даже в этом случае решение LRU о том, что разлить, не было бы оптимальным. Вы - компилятор, вы можете заглянуть вперед, чтобы увидеть, что регистры делают для дальнейшего использования.

Также вам нужно заглянуть вперед, чтобы увидеть, используется ли вообще результат, если вы не планируете вообще не оптимизировать. например x++; x++; должен компилироваться так же, как x+=2, в инструкцию добавления, а не в две отдельные операции добавления-1. Таким образом, вам нужна какая-то структура данных для представления логики программы, а не просто для превращения ее в asm на лету за один проход. (Если вы не пишете действительно однопроходный компилятор, такой как tcc.)

Обратите внимание, что многие компиляторы нацелены на хороший код, а не только на правильный код, а это означает минимизацию утечки / повторной загрузки, особенно в цепочках зависимостей с переносом цикла. Также хорошо обрабатывает распределение даже в ветвящемся коде. Именно здесь полезен граф статического одиночного назначения (SSA), а также он помогает понять, когда вывести вычисление или доступ к памяти из цикла.

Связанный: Распределение и разлив регистров, простой способ? содержит более подробную информацию об алгоритмах распределения регистров, а также Compilers: Register Allocation Against Complex Branch / Jumps содержит ссылки на статьи.

person Peter Cordes    schedule 22.06.2020

arrow_upward
7
arrow_downward

Простое мышление в терминах утечки регистров может быть приемлемым для прямолинейного кода, но многие программы содержат циклы. Хотя эффективность регистров в циклах часто более важна, чем в прямолинейном коде, модель утечки регистров затрудняет обработку ситуаций, когда значение должно быть активным для части цикла ближе к концу и оставаться активным, пока выполнение не достигнет некоторого пятно рядом с началом, но не должно оставаться живым посередине. Согласно модели утечки регистров, можно получить значение, хранящееся в регистре около начала цикла и в другом регистре ближе к концу. Раскраска графика гарантирует, что обоим будет назначен один и тот же цвет [т. Е. помещены в тот же реестр].

person supercat    schedule 22.06.2020