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

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

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

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

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

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

Целевой код

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

• 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. В общем случае эти команды могут иметь разную сложность и разное время выполнения.

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

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

Математически, задача оптимального распределения регистров является 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.

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

Локальная оптимизация.

Большинство оптимизирующих компиляторов применяют т.н. “локальную” оптимизацию. При таком подходе, сначала генерируется достаточно простой (с точки зрения генерации) машинный код, затем по коду перемещается некое “окно” которое рассматривает лишь локальную окрестность текущей команды, и к коду внутри этого “окна” применяются локальные трансформации.

Примеры локальных оптимизаций:

• Устранение “лишних” инструкций
  • В частности, лишних загрузок и сохранений из/в оперативную память
  • Недостижимого кода (скажем, используемого для отладки)
• Оптимизация потока управления
  • Устранение цепочек переходов (т.е. устранение лишних безусловных переходов)
• Алгебраические упрощения
• Использование машинных идиом

Параллелизм уровня команд. Конвейеризация

Все современные процессоры способны выполнять за один такт несколько операций. Однако, если все операции в программе сильно зависят одна от другой, ясно, что никакие методы распараллеливания не изменят её производительности. С другой стороны, скажем, вычислительные и графические программы часто допускают крайне высокую степень параллельности.

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

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

1. Чтение команды из памяти
2. Декодирование команды
3. Исполнение команды
4. Обращение к памяти
5. Сохранение результата

Эти действия выполняются, как правило, различными исполнительными блоками внутри процессора, и поэтому могут, в целом, работать одновременно. Таким образом, в тот момент, когда для, скажем i-той команды всё ещё выполняется действие 5, для i+1-й может выполняться действие 4, для i+2-й действие 3 и т.д.

Определённую сложность представляют собой команды ветвления, поскольку заранее неизвестно, по какой ветви пойдёт дальнейшее выполнение кода. Это, соответственно приводит к “заиканию” конвейера, когда он опустошается, и затем вновь заполняется после ветвления. Многие современные процессоры использовали т.н. модель спекулятивного исполнения, когда процессор пытался “предугадать” по какой ветви пойдёт исполнение кода, и опустошал конвейер только если догадка оказалась неверной. Однако некоторая неаккуратность в реализации в итоге привела к недавно нашумевшим уязвимостям Meltdown и Spectre.

Следует заметить, что не все команды полностью конвейеризуемы, и если следующая команда зависит от результатов предыдущей, то она, очевидно, не может быть конвейеризована. Современные компиляторы (и даже процессоры!) нередко могут менять порядок выполнения команд для обхода этой проблемы (что, кстати сказать, может менять поведение программ, хотя по идее и не должно бы!)

Ещё один источник ускорения – использование векторных команд, т.е. команд, производящих операцию сразу над несколькими адресами. Эта оптимизация может быть реализована как в компиляторе (тогда используются специальные инструкции, называемые в общем VLIW – very long instruction word), так и непосредственно в железе, тогда такой процессор называется суперскалярным.

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

Оптимизация локальности

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

• Временная локальность означает использование некоторых данных несколько раз за короткий промежуток времени
• Пространственная локальность означает использование в течение короткого промежутка времени некоторых находящихся рядом друг с другом данных

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

Например:

for(i = 0; i < n; ++i) {
  Z[i] = X[i] - Y[i];
  Z[i] = Z[i] * Z[i];
}

тот же код можно написать иначе:

for(i = 0; i < n; ++i) {
  Z[i] = X[i] - Y[i];
}
for(i = 0; i < n; ++i) {
  Z[i] = Z[i] * Z[i];
}

Технически, оба варианта подразумевают одинаковое количество операций присваивания, однако первый вариант будет значительно быстрее за счёт лучшей локальности данных. К тому же, в первом варианте результаты вычисления X[i] - Y[i] могут вообще не быть записаны в физическую память (поскольку далее не используются), в то время как во втором варианте, если массив Z достаточно велик, чтобы не умещаться в кэш процессора, X[i] - Y[i] должны быть записаны в память.

Другой пример, обнуление “двумерного” массива:

for (j = 0; j < n; ++j)
  for (i = 0; i < m; ++i)
    Z[i+m*j] = 0;

против

for (i = 0; i < m; ++i)
  for (j = 0; j < n; ++j)
    Z[i+m*j] = 0;

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

Задача оптимизации локальности значительно усложняется, если в рамках рассмотрения к тому же оказывается и параллелизм. В частности, если предполагается параллельное исполнение кода на нескольких процессорах/ядрах, то разные данные могут быть “локальными” для разных процессоров.