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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:56, 18 июня 2016.

Генератор кода - процесс компиляции, конвертирующая синтаксически корректную программу в последовательность инструкций, которые могут выполняться на машине.При этом могут применяться различные, в первую очередь машинно-зависимые оптимизации. Часто кодогенератор является общей частью для множества компиляторов. Каждый из них генерирует промежуточный код, который подаётся на вход кодогенератору. Обычно, на вход генератора кода подаётся дерево разбора или абстрактное синтаксическое дерево. Дерево преобразуется в линейную последовательность инструкций промежуточного языка (например, в трехадресный код). Сложные компиляторы, как правило, делают несколько проходов через различные промежуточные формы кода. Этот многоступенчатый процесс используется потому, что многие алгоритмы оптимизации кода проще реализовать каждый отдельно, или же потому, что какой-то шаг оптимизации зависит от результата отработки другого шага. Кроме того, при такой организации, легко создать один компилятор, который будет создавать код для нескольких платформ, так как достаточно заменить последний шаг генерации кода (бэкэнд, англ. backend). Дальнейшие этапы компиляции могут и не относиться к «генерации кода», в зависимости от того, насколько значительными будут изменения, вносимые ими. Так, локальная оптимизация вряд ли может называться «генерацией кода», однако сам генератор кода может включать в себя этап локальной оптимизации.

Задачи генератора кода

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

  • Выбор инструкций: какие инструкции использовать
  • Планирование инструкций: в каком порядке размещать эти инструкции. Планирование — это оптимизация, которая может значительно влиять на скорость выполнения программы на конвейерных процессорах
  • Размещение в регистрах: размещение переменных программы в регистрах процессора.

Выбор инструкций обычно выполняется рекурсивным обходом абстрактного синтаксического дерева, в этом случае сравниваются части конфигураций дерева с шаблонами; например, дерево W:=ADD(X,MUL(Y,Z)) может быть преобразовано в линейную последовательность инструкций рекурсивной генерации последовательностей t1:=X и t2:=MUL(Y,Z), а затем инструкцией ADD W,t1,t2.

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

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

Генерация кода во время выполнения

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

Организация информации в генераторе кода

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

  • всю эту информацию можно хранить в таблицах генератора кода;
  • информация хранится в вершинах дерева с соответствующими указателями.

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

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

Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе. На этапе синтаксического дерева (часто используется форма, именуемая деревом вывода). Но формы представления, используемые на этапах i-тактического анализа, оказываются неудобными в работе при генерации и оптимизации объектного кода. Поэтому перед оптимизацией и непосредственно перед генерацией объектного кода внутреннее представление программы может преобразовываться в одну из соответствующих форм записи.
Все внутренние представления программы обычно содержат в себе две различные вещи — операторы и операнды. Различия между формами внутреннего представления заключаются лишь в том, как операторы и операнды соединяются между собой. Также операторы и операнды должны отличаться друг от друга, если они встречаются в любом порядке. За различение оператора и операнда, как уже было сказано выше, отвечает разработчик компилятора, который руководствуется семантикой входного языка. Известны следующие формы внутреннего представления программ:

  • связочные списочные структуры, представляющие синтаксические деревья;
  • многоадресный код с явно именуемым результатом (тетрады);
  • многоадресный код с неявно именуемым результатом (триады);
  • обратная (постфиксная) польская запись операций;
  • ассемблерный код или машинные команды;

В каждом конкретном компиляторе может использоваться одна из этих пользованием только одной формы для внутреннего представления программы. На различных фазах компиляции могут использоваться различные формы, которые по мере выполнения проходов компилятора преобразуются одна в другую. Не все из перечисленных форм широко используются в современных компиля­торах.
Некоторые компиляторы, незначительно оптимизирующие результирующий код, генерируют объектный код по мере разбора исходной программы. В этом случае применяется схема СУ-компиляции, когда фазы синтаксического разбора, семан­тического анализа, подготовки и генерации объектного кода совмещены в одном проходе компилятора. Тогда внутреннее представление программы существует только условно в виде последовательности шагов алгоритма разбора. В любом случае компилятор всегда будет работать с представлением программы в форме машинных команд — иначе он не сможет построить результирующую программу.

Источники

  1. Кодогенерация [Электронный ресурс] : Материал из Википедии — свободной энциклопедии : Версия 60584773, сохранённая в 10:34 UTC 8 января 2014 / Авторы Википедии // Википедия, свободная энциклопедия. — Электрон. дан. — Сан-Франциско: Фонд Викимедиа, 2014. — Режим доступа: http://ru.wikipedia.org/?oldid=60584773
  2. https://habrahabr.ru/post/23858/
  3. http://www.uran.donetsk.ua/~masters/2006/fvti/svyezhentsev/library/article2.htm
  4. http://citforum.ru/programming/theory/serebryakov/9.shtml
  5. http://uz.denemetr.com/docs/294/index-20812-1.html?page=23