Генерация целевого кода. Распределение регистров.

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

Получаемый код должен быть семантически эквивалентен входному промежуточному коду. Кроме того, целевой код должен эффективно использовать ресурсы исполнительного устройства.

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

Перед генератором кода стоят три основные задачи:

• выбор команд
• распределение регистров
• упорядочение команд

Целевой код

Целевая архитектура оказывает значительное влияние на сложность разработки хорошего кодогенератора. Наиболее распространёнными являются архитектуры типа

• RISC (Restricted/Reduced Instruction Set Computer)
• CISC (Complex/Complete Instruction Set Computer)
• Стековая машина

RISC-архитектуры обычно имеют множество регистров общего назначения и относительно простой набор команд, и, как следствие, хорошо вписываются в концепцию кодогенератора, но крайне слабо подходят для “ручной” разработки.

CISC-архитектуры, напротив, имеют сравнительно мало регистров общего назначения, специализированные регистры, и множество различных команд, которые в некоторых случаях могут дублировать другие. Такие архитектуры лучше подходят для “ручной” разработки. На практике, ассемблеры x86 и x86_64 являются примерами CISC-архитектуры, но в реальности процессоры реализованы как RISC-ядро и транслятор CISC-инструкций в RISC-аналоги.

Наконец, стековые машины практически не встречаются на практике в “железном” исполнении, но встречаются в качестве исполнительной модели байт-кода, например, в виртуальной машине Java.

Выбор команд

Кодогенератор должен отобразить промежуточное представление на некий набор команд целевой машины. Эта задача, в общем случае, нетривиальна.

В частности, если используется высокоуровневое представление промежуточного кода (скажем, АСД), то каждый элемент промежуточного представления может быть транслирован во множество команд целевой архитектуры. Такой код может требовать дальнейшей оптимизации. С другой стороны, если промежуточное представление отражает какие-то особенности целевой архитектуры, то эти особенности могут быть учтены на стадии машинно-независимой оптимизации.

Скажем, команды трёхадресного кода вида x=y+z могут быть транслированы в несколько инструкций загрузки из памяти и сохранения в память. В общем случае несколько последовательных команд такого вида могут иметь несколько излишних операций сохранения-загрузки.

Другим фактором является различная скорость выполнения команд целевого кода. Так, скажем, инструкция a = a + 1 может быть (в некой абстрактно-фантазийной целевой машине) реализована как ADD a, 1 или как INC a. В общем случае эти команды могут иметь разную сложность и разное время выполнения.

Распределение регистров

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

Объём		Время доступа
>64 ГБ	Виртуальная память (файл подкачки)	3-15 мс
сотни МБ - 64 ГБ	Физическая оперативная память	100-150 нс
128 КБ - 4 МБ	Кэш второго уровня	40-60 нс
десятки КБ	Кэш первого уровня	5-10 нс
десятки машинных слов (сотни байт)	Регистры	1 нс

Математически, задача оптимального распределения регистров является NP-полной.

Как правило, ряд регистров резервируется под специализированные нужды, в частности, указатель на вершину стека. Другие же используются свободно.

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

Пусть имеется инструкция, эквивалентная трёхадресному коду x = y + z (где + принципиально любой оператор). Тогда, сначала выбираются регистры для y и z, затем регистр для x.

Регистры для y и z выбираются одинаково, поэтому рассмотрим алгоритм выбора регистра для y:

1. Если y в настоящий момент хранится в регистре, то используем этот же регистр
2. Если y не хранится в регистре, и имеется пустой регистр (не содержащий никакой “живой” переменной), используем его (и пометим его как “занятый”)
3. Если пустых регистров нет, то для каждого из занятых регистров R, хранящего значение v мы должны рассмотреть следующие варианты:
   1. Если значение v хранится где-то кроме регистра R (например, было загружено из памяти), используем регистр R
   2. Если v есть x, т.е. значение должно быть перезаписано результатом текущей команды, и при этом x не является одним из операндов (y или z), данное значение более не будет использовано, поэтому используем регистр R
   3. Если значение v более не используется в рамках данного базового блока (т.е. либо переменная вообще не используется после данного базового блока, либо значение v перезаписывается после текущей команды), используем регистр R
   4. Если ни одна из вышеописанных ситуаций не реализуется, регистр R нельзя использовать.
   5. Если нельзя использовать ни один регистр, мы должны выбрать какой-то из них и сохранить значение регистра в оперативной памяти (и позже, при необходимости, загрузить его)

Выбор регистра для x очень похож, но есть несколько ключевых отличий:

1. Регистр, который хранит переменную x, всегда подходит для переменной x, даже если y или z есть x (при условии, что целевая машина допускает совпадение регистров результата и операндов – обычно допускает)
2. Если значения y или z более не используется в рамках базового блока, соответствующие им регистры могут быть использованы для x.

Вне базовых блоков, как правило оказывается осмысленным назначение “глобальных” регистров для часто используемых переменных, таких как, например, счётчики циклов. Это правило, однако, не универсально, и компиляторы, как правило, производят анализ ожидаемого выигрыша производительности от такой оптимизации (выигрыш зависит в первую очередь от количества использований значения переменной между разными базовыми блоками) – в общем случае его может и не быть.