Понятие компилятора. Генерация кода. Основные подходы к генерации кода. Понятие целевой машины.
Последней стадией в модели компиляции является генератор кода, который получает на вход промежуточное представление исходной программы и выводит эквивалентную целевую программу.
Традиционно к генератору кода предъявляются жесткие требования. Получаемый код должен быть корректным и высококачественным, что означает эффективное использование ресурсов целевой машины. Кроме того, эффективно должен работать и сам генератор кода.
Математически проблема генерации оптимального кода является неразрешимой. На практике мы вынуждены довольствоваться эвристическими технологиями, дающими хороший, но не обязательно оптимальный код. Выбор эвристики очень важен, так как тщательно разработанный алгоритм генерации кода может давать код, работающий в несколько раз быстрее кода, полученного с помощью недостаточно продуманного алгоритма.
Хотя мелкие детали генератора кода зависят от целевой машины и операционной системы, такие вопросы, как управление памятью, выбор инструкций, распределение регистров и порядок вычислений, свойственны практически всем задачам, связанным с генерацией кода.
Вход генератора кода
Входной поток генератора кода представляет собой промежуточное представление исходной программы, полученное на начальной стадии компиляции, вместе с таблицей символов, которая используется для определения адресов времени исполнения объектов данных, обозначаемых в промежуточном представлении именами.
Целевые программы
Выходом генератора кода является целевая программа. Подобно промежуточному коду, выход генератора кода может принимать различные виды: абсолютный машинный язык, перемещаемый машинный язык, или язык ассемблера.
Управление памятью
Отображение имен исходной программы в адреса объектов данных в памяти во время работы программы выполняется совместно начальной стадией компилятора и генератором кода.
Выбор инструкций
Набор инструкций целевой машины определяет сложность их выбора. Важными факторами этого выбора являются единообразие и полнота множества инструкций. Если целевая машина не поддерживает все типы данных единообразно, то каждое исключение из общего правила потребует специальной обработки.
Другими важными факторами являются скорость выполнения инструкций и идиомы языка целевой машины.
Распределение регистров
Инструкции, использующие в качестве операндов регистры, обычно короче и быстрее выполняются, чем инструкции, работающие с операндами, расположенными в памяти. Следовательно, эффективное использование регистров — еще одна важная составляющая генерации хорошего целевого кода. Использование регистров часто разделяется на две подзадачи.
В процессе распределения регистров мы выбираем множество переменных, которые будут находиться в регистрах в некоторой точке программы.
В последующей фазе назначения регистров мы выбираем конкретные регистры для размещения в них переменных.
Выбор порядка вычислений
Порядок, в котором выполняются вычисления, также может существенно влиять на эффективность целевого кода. Как мы увидим, изменение порядка вычислений может привести к уменьшению количества необходимых для работы регистров.
Подходы к генерации кода
Несомненно, самым важным критерием работы генератора кода является корректность производимого кода. Корректность приобретает особую значимость из-за огромного количества частных случаев и исключений из правил, с которыми приходится сталкиваться генератору кода. С учетом приоритета корректности, важной целью разработки генератора кода является создание легко реализуемого, тестируемого и поддерживаемого генератора целевого кода.
Простой алгоритм генерации кода использует информацию о последующем использовании операндов для генерации кода регистровой машины. Он рассматривает каждую инструкцию по очереди, сохраняя операнды в регистрах, насколько это оказывается возможным. Выход такого генератора может быть улучшен путем применения технологий локальной оптимизации.
Существуют технологии, оптимизирующие использование регистров путем рассмотрения потока управления в промежуточном коде. Особый упор делается на распределении регистров для интенсивно используемых операндов во внутренних циклах.
Существуют некоторые технологии выбора кода с использованием деревьев, упрощающие создание перенастраиваемых генераторов кода. Версии РСС — переносимого компилятора С — с такими генераторами кода распространились на самые разнообразные платформы, чему немало способствовала доступность операционной системы UNIX. Генерация кода может рассматриваться в качестве процесса построения дерева.
Целевая машина
Архитектура (набор программно-аппаратных средств), для которой производится компиляция, называется целевой машиной.
Одним из непременных требований к построению хорошего генератора кода является близкое знакомство с целевой машиной и ее набором инструкций. К сожалению, при обсуждении общих вопросов генераций кода невозможно описать нюансы той или иной целевой машины достаточно подробно, чтобы иметь возможность генерировать для нее хороший код. Рассмотрим регистровую машину, являющуюся типичным представителем ряда мини-компьютеров. Однако рассматриваемые здесь принципы и технологии применимы и к множеству других классов машин.
Наш целевой компьютер представляет собой машину с адресацией байтов, словом из четырех байтов и п регистрами общего назначения RO, Rl. ..., R/i-1. Он имеет двухадресные инструкции вида
op source, destination
где op— код операции, a source (источник) и destination (получатель)— поля данных. Среди прочих имеются следующие коды операций.
MOV (переместить source в destination)
ADD (прибавить source к destination)
SUB (вычесть source из destination)
Поля источника и получателя недостаточно длинны для хранения адресов памяти, поэтому определенные наборы битов в этих полях определяют, что следующее за инструкцией слово содержит операнды и/или адреса. Источник и получатель инструкции определяются комбинированием регистров и ячеек памяти с режимами адресации. В следующем далее описании contents(a) означает содержимое регистра или ячейки памяти, представленных а.
Далее приведены режимы адресации вместе с их ассемблерным представлением и стоимостью.