Содержание
- 2. Системное программное обеспечение Тема № 16 Генерация и оптимизация кода
- 3. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода Генерация объектного кода – это
- 4. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода В идеале компилятор должен выполнить
- 5. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода Как правило, компилятор выполняет генерацию
- 6. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода Чтобы компилятор мог построить код
- 7. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода Суть принципа СУ-перевода заключается в
- 8. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода В общем случае схемы СУ-перевода
- 9. Системное программное обеспечение Генерация и оптимизация кода Общие принципы генерации кода Возможна модель компилятора, в которой
- 10. Системное программное обеспечение Генерация и оптимизация кода Способы внутреннего представления программ Возможны различные формы внутреннего представления
- 11. Системное программное обеспечение Генерация и оптимизация кода Способы внутреннего представления программ Все внутренние представления программы обычно
- 12. Системное программное обеспечение Генерация и оптимизация кода Способы внутреннего представления программ Известны следующие формы внутреннего представления
- 13. Системное программное обеспечение Генерация и оптимизация кода Синтаксические деревья Синтаксические деревья – это структура, представляющая собой
- 14. Системное программное обеспечение Генерация и оптимизация кода Многоадресный код с явно именуемым результатом Тетрады представляют собой
- 15. Системное программное обеспечение Генерация и оптимизация кода Многоадресный код с явно именуемым результатом Порядок вычисления тетрад
- 16. Системное программное обеспечение Генерация и оптимизация кода Многоадресный код с явно именуемым результатом Пример: выражение C:=A*12+K*(2-3*В),
- 17. Системное программное обеспечение Генерация и оптимизация кода Многоадресный код с неявно именуемым результатом Триады представляют собой
- 18. Системное программное обеспечение Генерация и оптимизация кода Многоадресный код с неявно именуемым результатом Порядок вычисления триад
- 19. Системное программное обеспечение Генерация и оптимизация кода Многоадресный код с неявно именуемым результатом Триады ближе к
- 20. Системное программное обеспечение Генерация и оптимизация кода Ассемблерный код или машинные команды Машинные команды удобны тем,
- 21. Системное программное обеспечение Генерация и оптимизация кода Обратная польская запись операций Это постфиксная запись операций, которая
- 22. Системное программное обеспечение Генерация и оптимизация кода Обратная польская запись операций Вычисление выражений в обратной польской
- 23. Системное программное обеспечение Генерация и оптимизация кода Обратная польская запись операций Выражение 5*9-6*(3+4)
- 24. Системное программное обеспечение Генерация и оптимизация кода Обратная польская запись операций Выражение 5*(9-6)*3+4
- 25. Системное программное обеспечение Генерация и оптимизация кода Обратная польская запись операций Выражение 5*(9-6)*(3+4)
- 26. Системное программное обеспечение Генерация и оптимизация кода Оптимизация кода Большинство современных компиляторов выполняют еще один этап
- 27. Системное программное обеспечение Генерация и оптимизация кода Оптимизация кода Оптимизация программы – это обработка, связанная с
- 28. Системное программное обеспечение Генерация и оптимизация кода Оптимизация кода Оптимизацию можно выполнять на любой стадии генерации
- 29. Системное программное обеспечение Генерация и оптимизация кода Оптимизация кода Методы преобразования программы зависят от типов синтаксических
- 31. Скачать презентацию
Системное программное обеспечение
Тема № 16
Генерация и оптимизация кода
Системное программное обеспечение
Тема № 16
Генерация и оптимизация кода
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Генерация объектного кода
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Генерация объектного кода
Внутреннее представление программы
может иметь любую структуру
в зависимости от реализации компилятора,
в то время как результирующая
программа всегда представляет
собой линейную последовательность команд.
Поэтому генерация объектного кода
(объектной программы) в любом случае
должна выполнять действия, связанные
с преобразованием сложных
синтаксических структур в линейные цепочки.
Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода:
распределено адресное пространство под функции и переменные;
проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы и т. д.
Характер отображения входной программы в последовательность команд, выполняемого генерацией, зависит от входного языка, архитектуры вычислительной системы, на которую ориентирована результирующая программа, а также от качества желаемого объектного кода.
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
В идеале компилятор
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
В идеале компилятор
Дело в том, что в общем случае ни один семантический анализатор и ни один компилятор не способны проанализировать и оценить смысл всей входной программы в целом.
Формальные методы анализа семантики применимы только к очень незначительной части возможных входных программ.
Поэтому у компилятора нет практической возможности порождать эквивалентную выходную программу на основе всей входной программы.
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Как правило, компилятор
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Как правило, компилятор
Компилятор выделяет законченную синтаксическую конструкцию из текста входной программы, порождает для нее фрагмент результирующего кода и помещает его в текст выходной программы.
Затем он переходит к следующей синтаксической конструкции.
Так продолжается до тех пор, пока не будет разобрана вся входная программа.
В качестве анализируемых законченных синтаксических конструкций выступают операторы, блоки операторов, описания процедур и функций. Их конкретный состав зависит от входного языка и реализации компилятора.
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Чтобы компилятор мог
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Чтобы компилятор мог
СУ-перевод – это основной метод порождения кода результирующей программы на основании результатов синтаксического анализа.
Для удобства понимания сути метода можно считать, что результат синтаксического анализа представлен в виде дерева синтаксического разбора (либо же дерева операций), хотя в реальных компиляторах это не всегда так.
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Суть принципа СУ-перевода
Системное программное обеспечение
Генерация и оптимизация кода
Общие принципы генерации кода
Суть принципа СУ-перевода
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♦)
Системное программное обеспечение
Генерация и оптимизация кода
Ассемблерный код или машинные команды
Машинные команды
Системное программное обеспечение
Генерация и оптимизация кода
Ассемблерный код или машинные команды
Машинные команды
Команды ассемблера представляют собой лишь форму записи машинных команд, а потому в качестве формы внутреннего представления программы практически ничем не отличаются от них.
Использование команд ассемблера или машинных команд для внутреннего представления программы требует дополнительных структур для отображения взаимосвязи операций.
Ассемблерный код и машинные команды –
это машинно-зависимая форма
внутреннего представления программы.
Машинные команды – это язык, на котором должна быть записана результирующая программа. Поэтому компилятор, так или иначе, должен работать с ними. Кроме того, только обрабатывая машинные команды (или их представление в форме команд ассемблера), можно добиться наиболее эффективной результирующей программы. Следовательно любой компилятор работает с представлением результирующей программы в форме машинных команд, однако, их обработка происходит, как правило, на завершающих этапах фазы генерации кода.
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Это постфиксная запись
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Это постфиксная запись
По сравнению с обычной (инфиксной) записью операций в польской записи операнды следуют в том же порядке, а знаки операций – строго в порядке их выполнения.
Тот факт, что в этой форме записи все операции выполняются в том порядке, в котором они записаны, делает ее чрезвычайно удобной для вычисления выражений на компьютере.
Польская запись не требует учитывать приоритет операций, в ней не употребляются скобки, и в этом ее основное преимущество.
Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Главный недостаток обратной польской записи также проистекает из метода вычисления выражений в ней: поскольку используется стек, то для работы с ним всегда доступна только верхушка стека, а это делает крайне затруднительной оптимизацию выражений в форме обратной польской записи (практически выражения в форме обратной польской записи почти не поддаются оптимизации).
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Вычисление выражений в
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Вычисление выражений в
если встречается операнд, то он помещается в стек (попадает на верхушку стека);
если встречается знак унарной операции (операции, требующей одного операнда), то операнд выбирается с верхушки стека, операция выполняется и результат помещается в стек (попадает на верхушку стека);
если встречается знак бинарной операции (операции, требующей двух операндов), то два операнда выбираются с верхушки стека, операция выполняется и результат помещается в стек (попадает на верхушку стека).
Вычисление выражения заканчивается, когда достигается конец записи выражения.
Результат вычисления при этом всегда находится на верхушке стека.
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Выражение 5*9-6*(3+4)
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Выражение 5*9-6*(3+4)
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Выражение 5*(9-6)*3+4
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Выражение 5*(9-6)*3+4
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Выражение 5*(9-6)*(3+4)
Системное программное обеспечение
Генерация и оптимизация кода
Обратная польская запись операций
Выражение 5*(9-6)*(3+4)
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Большинство современных компиляторов выполняют еще
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Большинство современных компиляторов выполняют еще
Важно зафиксировать два момента:
выделение оптимизации в отдельный этап генерации кода – это вынужденный шаг.
Компилятор вынужден производить оптимизацию построенного кода, поскольку он не может выполнить семантический анализ всей входной программы в целом, оценить ее смысл и, исходя из него, построить результирующую программу.
Оптимизация нужна, поскольку результирующая программа строится не вся сразу, а поэтапно;
оптимизация – это необязательный этап компиляции.
Компилятор может вообще не выполнять оптимизацию, и при этом результирующая программа будет правильной, а сам компилятор будет полностью выполнять свои функции.
Однако практически все компиляторы, так или иначе, выполняют оптимизацию, поскольку их разработчики стремятся завоевать хорошие позиции на рынке средств разработки ПО.
Оптимизация, которая существенно влияет на эффективность результирующей программы, является здесь немаловажным фактором.
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Оптимизация программы – это обработка,
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Оптимизация программы – это обработка,
Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.
В качестве показателей эффективности результирующей программы можно использовать два критерия:
объем памяти, необходимый для выполнения результирующей программы (для хранения всех ее данных и кода);
скорость выполнения (быстродействие) программы.
Далеко не всегда удается выполнить оптимизацию так,
чтобы удовлетворить обоим этим критериям.
Зачастую сокращение необходимого программе
объема данных ведет к уменьшению ее быстродействия,
и наоборот. Поэтому для оптимизации обычно
выбирается либо один из упомянутых критериев,
либо некий комплексный критерий, основанный на них.
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Оптимизацию можно выполнять на любой
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Оптимизацию можно выполнять на любой
Если компилятор использует несколько различных форм внутреннего представления программы, то каждая из них может быть подвергнута оптимизации, причем различные формы внутреннего представления ориентированы на различные методы оптимизации.
Оптимизация в компиляторе может
выполняться несколько раз
на этапе генерации кода.
Принципиально различаются два основных вида оптимизирующих преобразований:
преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка;
преобразования результирующей объектной программы.
Данные преобразования не зависят
от архитектуры целевой вычислительной
системы, на которой будет
выполняться результирующая программа.
Обычно основаны на выполнении
хорошо известных и обоснованных
математических и логических преобразований,
производимых над внутренним
представлением программы.
Данные преобразования могут
зависеть не только от свойств
объектного языка, но и от архитектуры
вычислительной системы, на которой
будет выполняться результирующая
программа. При оптимизации может
учитываться объем кэш-памяти и
методы организации конвейерных
операций центрального процессора.
В большинстве случаев эти преобразования
сильно зависят от реализации компилятора
и являются «ноу-хау» производителей компилятора.
Именно эти оптимизирующие преобразования
позволяют существенно повысить
эффективность результирующего кода.
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Методы преобразования программы зависят от
Системное программное обеспечение
Генерация и оптимизация кода
Оптимизация кода
Методы преобразования программы зависят от
Теоретически разработаны методы оптимизации для многих типовых конструкций языков программирования.
Оптимизация может выполняться для следующих типовых синтаксических конструкций:
линейных участков программы;
Во всех случаях могут использоваться как машинно-зависимые, так и машинно-независимые методы оптимизации.
логических выражений;
циклов;
вызовов процедур и функций;
других конструкций входного языка.