Практикум «Оптимизирующие компиляторы» (на примере GCC), страница 2

.............................................................................................................95Примеры оптимизации .........................................................................................................100Продвижение констант ....................................................................................................100Свертка констант..............................................................................................................100Распространение копий ...................................................................................................100Практикум «оптимизирующие компиляторы»Подстановка операторов .................................................................................................101Прямое преобразование...................................................................................................101Удаление неиспользуемого кода ....................................................................................101Упрощение булевых выражений в серию переходов ...................................................102Снижение мощности выражений с индексной переменной ........................................103Удаление индексной переменной ...................................................................................104Раскрутка циклов .............................................................................................................105Программная конвейеризация ........................................................................................105Вынесение условных выражений за пределы цикла ....................................................107Вынесение первых и последних итераций ....................................................................109Оптимизация хвостовых вызовов ...................................................................................110Встраивание функций (Inline) .........................................................................................111Приложение А.

Установка GCC ............................................ 113Получение дистрибутива.................................................................................................113Конфигурирование GCC .................................................................................................113Компиляция ......................................................................................................................114Тестирование ....................................................................................................................114Установка ..........................................................................................................................114Приложение Б.

Использование GCC .................................... 115Общие опции ....................................................................................................................115Опции оптимизации и генерации отладочной информации ........................................117Опции поиска каталогов и подключения библиотек ....................................................117Пример компиляции ........................................................................................................119Приложение В. Каталоги GCC ..............................................

120Корневой каталог ..................................................................................................................120contrib .....................................................................................................................................121Подкаталог gcc ......................................................................................................................123'language' ............................................................................................................................124config .................................................................................................................................124Приложение Г.

LEX (FLEX) .................................................... 125Приложение Д. YACC (BISON) .............................................. 130Приложение Е. Lex.l ............................................................... 138Приложение Ж. parce.y .......................................................... 140Лабораторный практикум ...................................................... 143Рекомендуемая литература ..................................................

144Практикум «оптимизирующие компиляторы»ПредисловиеПособие предназначено студентам, желающим самостоятельно изучитьосновополагающиетехнологиисовременныхоптимизирующихкомпиляторов. В центре внимания находится промышленный компиляторGNU Compiler Collection (GCC). Пособие основано на материалахсеминаров «Проблемы генерации кода в компиляторе», проводимых вучебно-исследовательской лаборатории "Информационные технологии"факультета ВМК (проект «Исследовательский компилятор»). Целью цикласеминаров и данного документа является создание у студента связногопредставления об архитектуре современного промышленного компилятора(на примере GNU GCC).

Цикл семинаров расширен серией компьютерныхлабораторных работ, посвященных практическому изучению компилятораGCC (добавление собственного языка, перенацеливание на новуюархитектуру, добавление прохода оптимизации). Авторы предполагают,что читатель знаком с теорией формальных языков (на ВМК эта теорияизлагается в курсах «Теория автоматов и мат. логика» Д.И. Когана и«Сетевые грамматики и языковые процессоры» С.Г. Кузина), а также склассическими принципами построения компиляторов, см., например, [1].Для выполнения лабораторных работ требуется, чтобы у слушателя былопытпрограммированиянаязыкеСиинекотораяпрактикапользовательской работы в среде операционной системы Linux.Разработкаметодическогопособиявыполненаврамкахпроекта«Исследовательский компилятор».В заключение предисловия авторы выражают благодарность В.П.

Гергелю,Н.Ю. Золотых, Л.В. Нестеренко за неоценимую помощь в разработкеданного пособия.Практикум «оптимизирующие компиляторы»Общая структура компилятораНаиболее общее определение для понятия компилятор таково:Компилятор – это программа, которая получает на входе программу,написанную на одном языке – исходном, и транслирует (переводит) её вэквивалентную программу на другом языке – целевом.Поток символовЛексическийанализаторПотоктокеновСинтаксическийанализаторТаблица символов ипроцедуры доступаПромежуточныйкодИнтерфейс соперационнойсистемойСемантическийанализаторПромежуточныйкодКодогенераторПеремещаемый объектный модуль илиисполняемый машинный кодРисунок 1. Общая структура простого (не оптимизирующего) компилятораДля нас интерес представляет более узкое определение этого термина:Компилятор – это программная система, которая переводит программы,написанные на языках высокого уровня в объектный или машинный коддля выполнения на вычислительной машине.Опишем общую структуру компилятора (рисунок 1):Практикум «оптимизирующие компиляторы»• Лексический анализатор.

Преобразует поток символов, которыйпредставляет исходный текст программы в поток токенов. Т. е.программа разбивается на «слова» исходного языка, называемыелексемами.• Синтаксический анализатор. Получает на вход последовательностьтокенови,обычноосновываясьнаконтекстно-свободныхграмматиках, генерирует некоторое промежуточное представление,например в виде дерева. В процессе этого преобразованияформируется таблица символов.• Семантический анализатор. Проверяет семантику программы, т.е.определяет правильность написания программы, основываясь направилах исходного языка, которые не могут быть выраженыконтекстно-свободными грамматиками.

Важным аспектом этогоэтапа является проверка типов.• Кодогенератор. Преобразует программу на промежуточном языке вперемещаемый машинный код или ассемблерный код. Для каждойпеременной программы определяется её положение в памяти.Каждая промежуточная инструкция транслируется в одну илинесколько машинных инструкций. Ключевой аспект этой фазызаключается в назначении переменных регистрам.В настоящее время представляют интерес только, так называемые,оптимизирующиекомпиляторы.Оптимизирующимкомпиляторомназывается такой компилятор, который применяет улучшающие внекоторомсмыслепреобразованияпрограммы,именуемыеоптимизациями. Цели оптимизации могут быть различными, например,уменьшение времени исполнения программы и/или уменьшение размеракода.Практикум «оптимизирующие компиляторы»Поток символовЛексическийанализаторПоток символовПотоктокеновЛексическийанализаторСинтаксическийанализаторПотоктокеновДерево разбораСинтаксическийанализаторСемантическийанализаторДерево разбораДерево разбораСемантическийанализаторГенераторпромежуточногопредставленияДерево разбораТрансляторНизкоуровневоепромежуточное представлениеСреднеуровневоепромежуточноеОптимизаторОптимизаторНизкоуровневоепромежуточное представлениеСреднеуровневоепромежуточное представлениеКодогенераторОкончательнаясборкаНизкоуровневоепромежуточное представлениеПеремещаемый объектныймодуль или исполняемыймашинный кодPostpassоптимизаторПеремещаемый объектныймодуль или исполняемыймашинный код(а)(б)Рисунок 2.

Две структуры оптимизирующего компилятора:а) низкоуровневая модель,б) смешанная модельНа рисунке 2 приведены две основные схемы оптимизирующихкомпиляторов. В первом случае (рисунок 2.а) все оптимизирующиепреобразованиявыполняютсянадпромежуточнымпредставлениемнизкого уровня. Во втором (рисунок 2.б) – исходная программатранслируется в среднеуровневое представление, над которым происходитбольшинствоархитектурнонезависимыхоптимизаций,азатем,Практикум «оптимизирующие компиляторы»переводится в низкоуровневое представление, над которым проводятмашинно-зависимые оптимизации.Как видно, работа компилятора разделяется на несколько фаз.

Но, приреализации часто происходит объединение действий, выполняемых вразличных фазах. Так, например, фазы объединяются в начальную стадию,или frond end, и заключительную стадию, или back end. Начальная стадиясостоит из тех этапов компиляции, которые зависят от исходного языка ипочти не зависят от целевой платформы (лексический и синтаксическийанализ, создание таблицы символов, семантический анализ и генерацияC2ABC4C1DEC3FРисунок 3.