Генерация и оптимизация кода

АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ТК

Тема: Генерация и оптимизация кода

кода – это перевод компилятором внутреннего представления исходной программы в

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

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

Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода:

распределено адресное пространство под функции и переменные;

проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы и т. д.

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

компилятор должен выполнить синтаксический анализ всей входной программы, затем провести

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

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

Формальные методы анализа семантики применимы только к очень незначительной части возможных входных программ.

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

компилятор выполняет генерацию результирующего кода поэтапно на основе законченных синтаксических

конструкций входной программы.

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

Затем он переходит к следующей синтаксической конструкции.

Так продолжается до тех пор, пока не будет разобрана вся входная программа.

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

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

часто используется метод, называемый синтаксически управляемым переводом

СУ-перевод – это основной метод порождения кода результирующей программы на основании результатов синтаксического анализа.

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

СУ-перевода заключается в следующем: с каждой вершиной дерева синтаксического разбора

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

N - вершина

С(N) - код для вершины N

N

R

P

U

T

С(U)

С(T)

С(P)С(U)С(T)

С(R)

С(N)С(R)С(P)С(U)С(T)

случае схемы СУ-перевода могут предусматривать выполнение следующих действий:
помещение в

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

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

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

компилятора, в которой синтаксический анализ входной программы и генерация кода

результирующей программы объединены в одну фазу.

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

Для описания компиляторов такого типа часто используется термин «СУ-компиляция» – синтаксически управляемая компиляция.

Схему СУ-компиляции можно реализовать не для всякого входного языка программирования.

Принцип СУ-перевода применим ко всем входным КС-языкам.

формы внутреннего представления синтаксических конструкций исходной программы в компиляторе.

На

этапе синтаксического анализа часто используется форма, именуемая деревом вывода.

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

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

представления программы обычно содержат в себе две принципиально различные вещи

– операторы и операнды.

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

Также операторы и операнды должны отличаться друг от друга, если они встречаются в любом порядке.

За различение операндов и операторов отвечает
разработчик компилятора, который руководствуется
семантикой входного языка.

формы внутреннего представления программ:
связочные списочные структуры, представляющие синтаксические деревья;

многоадресный код с явно именуемым результатом (тетрады);

многоадресный код с неявно именуемым результатом (триады);

ассемблерный код или машинные команды;

обратная (постфиксная) польская запись операций.

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

Существуют три формы записи выражений:
префиксная – операция записывается перед операндами
+ab;
инфиксная – операция записывается между операндами
a+b;
постфиксная – операция записывается после операндов
ab+ .

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

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

Синтаксические деревья –
это машинно-независимая форма
внутреннего представления программы.

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

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

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

результатом
Тетрады представляют собой запись операций в форме из четырех составляющих:

операция, два операнда и результат операции.

<операция>(<операнд1>,<операнд2>,<результат>)

Тетрады представляют собой линейную последовательность команд.

При вычислении выражения, записанного в форме тетрад, они вычисляются одна за другой последовательно.

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

Если какой-то из операндов (или оба операнда) в тетраде отсутствует (например, если тетрад представляет собой унарную операцию), то он может быть опущен или заменен пустым операндом (в зависимости от принятой формы записи и ее реализации).

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

результатом
Порядок вычисления тетрад может быть изменен, но только если допустить

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

Достоинства:

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

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

Тетрады – это машинно-независимая форма
внутреннего представления программы.

Недостатки:

требуют больше памяти для своего представления, чем триады;

не отражают явно взаимосвязь операций между собой.

есть сложности с преобразованием тетрад в машинный код.

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

результатом
Пример:
выражение C:=A*12+K*(2-3*В), записанное в

виде тетрад, будет иметь вид:

1. * (A,12, D1)

2. * (3, B, D2)

3. - (2, D2, D3)

4. * ( K, D3, D4)

5. + (D1, D4, D5)

6. := ( D5, 0, C )

результатом
Триады представляют собой запись операций в форме из трех составляющих:

операция и два операнда.

<операция>(<операнд1>,<операнд2>)

Триады представляют собой линейную последовательность команд.

При вычислении выражения, записанного в форме триад, они вычисляются одна за другой последовательно.

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

Если какой-то из операндов в триаде отсутствует (например, если триада представляет собой унарную операцию), то он может быть опущен или заменен пустым операндом (в зависимости от принятой формы записи и ее реализации).

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

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

результатом
Порядок вычисления триад может быть изменен, но только если допустить

наличие триад, целенаправленно изменяющих этот порядок (например, триады, вызывающие переход на несколько шагов вперед или на­зад при каком-то условии).

Достоинства:

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

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

Триады – это машинно-независимая форма
внутреннего представления программы.

Недостатки:

требуют меньше памяти для своего представления, чем тетрады;

явно отражают взаимосвязь операций между собой.

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

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

результатом
Триады ближе к двухадресным машинным командам, чем тетрады, а именно

эти команды более всего распространены в наборах команд большинства современных компьютеров.

Пример:
выражение C:=A*12+K*(2-3*В), записанное в виде триад, будет иметь вид:

1. * (A,12)

2. * (3, B)

3. - (2, 2♦)

4. * ( K, 3♦)

5. + (1♦, 4♦)

6. := (C ,5♦)

команды удобны тем, что при их использовании внутреннее представление программы

полностью соответствует объектному коду и сложные преобразования не требуются.

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

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

Ассемблерный код и машинные команды –
это машинно-зависимая форма
внутреннего представления программы.

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

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

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

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

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

Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.

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

в обратной польской записи идет элементарно просто с помощью стека.

Для этого выражение просматривается в порядке слева направо, и встречающиеся в нем элементы обрабатываются по следующим правилам:

если встречается операнд, то он помещается в стек (попадает на верхушку стека);

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

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

Вычисление выражения заканчивается, когда достигается конец записи выражения.

Результат вычисления при этом всегда находится на верхушке стека.

еще один этап компиляции – оптимизацию результирующей программы, чтобы повысить

эффективность насколько это возможно.

Важно зафиксировать два момента:

выделение оптимизации в отдельный этап генерации кода – это вынужденный шаг.

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

Оптимизация нужна, поскольку результирующая программа строится не вся сразу, а поэтапно;

оптимизация – это необязательный этап компиляции.

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

Однако практически все компиляторы, так или иначе, выполняют оптимизацию, поскольку их разработчики стремятся завоевать хорошие позиции на рынке средств разработки ПО.

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

обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе

с целью получения более эффективной результирующей объектной программы.

Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.

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

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

скорость выполнения (быстродействие) программы.

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

любой стадии генерации кода, начиная от завершения синтаксического анализа и

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

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

Оптимизация в компиляторе может
выполняться несколько раз
на этапе генерации кода.

Принципиально различаются два основных вида оптимизирующих преобразований:

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

преобразования результирующей объектной программы.

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

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

от типов синтаксических конструкций исходного языка.
Теоретически разработаны методы оптимизации

для многих типовых конструкций языков программирования.

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

линейных участков программы;

Во всех случаях могут использоваться как машинно-зависимые, так и машинно-независимые методы оптимизации.

логических выражений;

циклов;

вызовов процедур и функций;

других конструкций входного языка.

записать в виде тетрад и триад.
Второе выражение вычислить в обратной

польской записи с использованием стека.