Дизайн компилятора - Генерация кода

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

Он должен нести точное значение исходного кода.
Он должен быть эффективным с точки зрения использования ЦП и управления памятью.

Теперь мы увидим, как промежуточный код преобразуется в код целевого объекта (в данном случае ассемблерный код).

Направленный ациклический граф

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

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

Example:

t₀ = a + b
t₁ = t₀ + c
d = t₀ + t₁

[t ₀ = a + b]	[t ₁ = t ₀ + c]	[d = t ₀ + t ₁ ]

Оптимизация глазка

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

Устранение избыточных инструкций

На уровне исходного кода пользователь может делать следующее:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

int add_ten(int x)
   {
   return x + 10;
   }

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

MOV x, R0
MOV R0, R1

Мы можем удалить первую инструкцию и переписать предложение как:

MOV x, R1

Недостижимый код

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

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

В этом сегменте кода printf оператор никогда не будет выполнен, поскольку управление программой возвращается до того, как он сможет выполнить, поэтому printf можно удалить.

Оптимизация потока управления

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

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

В этом коде метка L1 может быть удалена, поскольку она передает управление L2. Таким образом, вместо перехода к L1, а затем к L2, элемент управления может напрямую достигать L2, как показано ниже:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Упрощение алгебраических выражений

Бывают случаи, когда алгебраические выражения можно сделать простыми. Например, выражениеa = a + 0 можно заменить на a само себя и выражение a = a + 1 можно просто заменить на INC a.

Снижение силы

Есть операции, которые требуют больше времени и места. Их «сила» можно уменьшить, заменив их другими операциями, которые требуют меньше времени и места, но дают тот же результат.

Например, x * 2 можно заменить на x << 1, который включает только один сдвиг влево. Хотя результат a * a и a ² одинаковый, ² гораздо эффективнее реализовать.

Доступ к машинным инструкциям

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

Генератор кода

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

Target language: Генератор кода должен знать природу целевого языка, для которого нужно преобразовать код. Этот язык может облегчить выполнение некоторых машинно-ориентированных инструкций, чтобы помочь компилятору сгенерировать код более удобным способом. Целевая машина может иметь архитектуру процессора CISC или RISC.
IR Type: Промежуточное представление имеет разные формы. Это может быть структура абстрактного синтаксического дерева (AST), обратная польская нотация или трехадресный код.
Selection of instruction: Генератор кода принимает на входе промежуточное представление и преобразует (отображает) его в набор команд целевой машины. Одно представление может иметь много способов (инструкций) для его преобразования, поэтому ответственность за правильный выбор соответствующих инструкций ложится на генератор кода.
Register allocation: Программа имеет ряд значений, которые необходимо поддерживать во время выполнения. Архитектура целевой машины может не позволять хранить все значения в памяти или регистрах ЦП. Генератор кода решает, какие значения хранить в регистрах. Кроме того, он решает, какие регистры будут использоваться для хранения этих значений.
Ordering of instructions: Наконец, генератор кода определяет порядок, в котором инструкция будет выполняться. Он создает расписания для инструкций по их выполнению.

Дескрипторы

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

Register descriptor: Дескриптор регистра используется для информирования генератора кода о доступности регистров. Дескриптор регистра отслеживает значения, хранящиеся в каждом регистре. Когда во время генерации кода требуется новый регистр, этот дескриптор запрашивает доступность регистра.
Address descriptor: Значения имен (идентификаторов), используемых в программе, могут храниться в разных местах во время выполнения. Дескрипторы адресов используются для отслеживания ячеек памяти, где хранятся значения идентификаторов. Эти места могут включать регистры ЦП, кучи, стеки, память или комбинацию упомянутых мест.

Генератор кода обновляет оба дескриптора в режиме реального времени. Для оператора загрузки LD R1, x генератор кода:

обновляет дескриптор регистра R1, который имеет значение x и
обновляет дескриптор адреса (x), чтобы показать, что один экземпляр x находится в R1.

Генерация кода

Базовые блоки состоят из последовательности трехадресных инструкций. Генератор кода принимает эту последовательность инструкций в качестве входных данных.

Note: Если значение имени находится более чем в одном месте (регистр, кеш или память), значение регистра будет предпочтительнее кеша и основной памяти. Точно так же значение кеша будет предпочтительнее основной памяти. Основной памяти практически не отдается предпочтение.

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

Если переменная Y уже находится в регистре R, она использует этот регистр.
В противном случае, если доступен какой-либо регистр R, он использует этот регистр.
В противном случае, если оба вышеуказанных параметра невозможны, он выбирает регистр, который требует минимального количества инструкций загрузки и сохранения.

Для инструкции x = y OP z генератор кода может выполнять следующие действия. Предположим, что L - это место (предпочтительно регистр), в котором должен быть сохранен вывод y OP z:

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

MOV y ', L

где y’ представляет собой скопированное значение y.
Определите текущее местонахождение z используя тот же метод, что и на шаге 2 для y и сгенерируйте следующую инструкцию:

OP z ', L

где z’ представляет собой скопированное значение z.
Теперь L содержит значение y OP z, которое предназначено для присвоения x. Итак, если L - регистр, обновите его дескриптор, чтобы указать, что он содержит значениеx. Обновите дескрипторx чтобы указать, что он хранится в месте L.
Если y и z больше не используются, их можно вернуть системе.

Другие конструкции кода, такие как циклы и условные операторы, преобразуются в язык ассемблера общим способом ассемблера.