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

Пратт в книге «Языки программирования» приводит перечень свойствхорошего языка:• Ясность, простота и единообразие понятий языка• Ортогональность• Естественность для приложений• Поддержка абстракций• Удобство верификации программы• Среда программирования• Переносимость программ• Стоимость использованияПрактикум «оптимизирующие компиляторы»ƒ Стоимость выполнения программыƒ Стоимость трансляции программыƒ Стоимостьсоздания,тестированияииспользованияпрограммыƒ Стоимость сопровождения программыРазнообразие предметных областей и желание приблизить язык по уровнюабстракций и естественности представления алгоритма к каждой областипорождает новые и новые языки. Существенным компонентом оценкикаждого решения является стоимость, которая складывается из если невзаимоисключающих, то, по меньшей мере, несовместимых компонент.Конкретный выбор в пользу того или иного критерия делается взависимости от сферы применения компилятора. Так для компиляциибольшинства студенческих программ важно скорость компиляции инесущественна скорость исполнения.

Скорость компиляции важна и в JITкомпиляторах.Принятая модель классификации языков выделяет четыре основныевычислительные модели:• Императивные (процедурные) языки. Состояние машины – память.Программа – последовательность операторов. Исполнение операторавлечет изменения состояния памяти. Примеры: C, C++, FORTRAN,ALGOL, PL/1, Pascal, Ada, Smalltalk, COBOL.• Аппликативные (функциональные) языки. Начальное состояниемашины – память. Программа – композиция функций. Примеры: ML,Lisp.• Языки,основанныенасистемеправил(логическогопрограммирования). Программа – совокупность пар (разрешающееусловие, действие).

Примеры: Prolog, НБФ в YACC, Lex.Практикум «оптимизирующие компиляторы»• Объектно-ориентированное программирование. В этой моделистроятся сложные объекты данных и определяются операции надэтими объектами.На язык оказывает влияние и среда программирования. Преимущественнона возможности языка, упрощающие раздельную компиляцию и сборкупрограммы (модульность), и на возможности тестирования и отладкипрограммы.Архитектура также оказывает влияние на языки.

В основном причиноймодификации языка для архитектуры служит желание значительноповысить производительность конечной программы. Пример: OpenMPрасширение.Ключевым вопросом в реализации языка программирования является то,какое представление имеет программа во время её выполнения нареальном компьютере. В зависимости от реализации языка их делят на:• Компилируемые.

Языки C, C++, FORTRAN, Pascal, Ada принятосчитатькомпилируемыми.Трансляторкомпилируемогоязыкаобычно является довольно большой и сложной программой, имаксимальное значение имеет создание максимально эффективных сточки зрения исполнения программ.• Интерпретируемые. Языки LISP, ML, Perl, Postscript, Prolog иSmalltalkобычнореализуютсяспомощьюинтерпретаторов.Трансляторы таких языков обычно – сравнительно простыепрограммы.Основнаясложностьзаключаетсявреализацииинтерпретатора.Лексический и синтаксический анализыЗадача лексического анализатора состоит в чтении потока символов ивыдачи потока токенов.

Синтаксический анализатор получает строкуПрактикум «оптимизирующие компиляторы»токенов от лексического анализатора и проверяет, может ли эта строкапорождаться грамматикой исходного языка.ИсходнаяпрограммаТокенЛексическийанализаторСинтаксическийанализаторЗапрос наполучениеТаблицасимволовДля построения лексических анализаторов на основе спецификаций,использующих регулярные выражения, был создан ряд специальныхпрограммных инструментов. В приложении описан инструмент подназванием Lex.Для построения синтаксических анализаторов на основе спецификаций вприложении рассматривается генератор LALR-анализаторов Yacc.Front endВ GCC от языка зависит только Front end (часть компилятора,анализирующая программу на языке высокого уровня и преобразующая еёво внутреннее представление программы в компиляторе).Исходный кодна языкевысокогоуровняFront endЗависит от языка программированияРисунок 11Back endОбъектныйфайлПрактикум «оптимизирующие компиляторы»Front end.CC ParserC++C++ ParserJavaJava ParserFortran 95Objective-CBack end.RTLRTLOptimizerCodeGeneratorFortran 95Objective CРисунок 12Front end должен обеспечивать: лексический анализ, синтаксическийанализ, генерацию кода во внутреннем представлении.

Также front endможет включать предварительную оптимизацию: например, вычислениеконстантных выражений, упрощение арифметических выражений.Создание компилятора для нового языка в GCC означает создание новогоfront end-а.Обычно front end работает по схеме показанной на рисунке 13.Обрабатывая очередную лексему средствами функций предоставленныхGCC, формируется дерево, хранящее информацию о распознанном участкепрограммы.Центральной структурой данных в Front end является дерево (по формеочень похоже на дерево синтаксического разбора).

Узлы дерева способныхранить целые или вещественные числа, строки, операторы и пр. В общемслучае дерево не является универсальным для всех front end-ов.Практикум «оптимизирующие компиляторы»генерациявнутреннегопредставленияформированиедереваТекстовый файлИсходный кодпрограммы на языкевысокого уровняTreeДеревоRTLЯзыкпромежуточногопредставленияРисунок 13Как только завершается анализ осмысленного участка кода, генерируетсяфрагмент RTL кода на основании сформированного дерева.Практикум «оптимизирующие компиляторы»Создание собственного Front endВ данной главе описывается процесс создания игрушечного front end-аVMK.Создание собственного Front end достаточно хорошо описано в документеGCC Front end HOWTO от Sreejith K Menon.

Если Вы собираетесь начатьписать собственный Front end, то, несомненно, следует начать с прочтенияэтого документа.Имя каталога содержащего файлы с реализацией front end совпадает сименем языка и располагается в папке gcc.Как правило, никто не создает front end с нуля. Для этого с GCC идетстандартный пример treelang. Нужно скопировать его в свой каталог иначать модифицировать.Файлы, которые получились в результате первого этапа (копированиястандартного front end-а и смены имен) представлены в Таблице 4.Таблица 4ФайлНазначениеChangeLogИстория вашего font end’а.

Файл необязателен, но этикеттребует его присутствия.Make-lang.inВключается в главный makefile в каталоге gcc. Его главнаяроль – вызвать makefile в каталоге языка. Обязательныйфайл.Makefile.inИспользуется для создания makefile в директории языка.Обязательный файл.config-lang.inОбрабатывается скриптом configure.lang-specs.hСодержит информацию для программы gcc о новомкомпиляторе (расширения файлов, возможные параметры).Файлы настройки на этом закончились. Теперь осталась реализация самогоfront end.

Для построения минимального варианта понадобится реализацияследующих модулей, описанных в Таблице 5.Практикум «оптимизирующие компиляторы»Таблица 5ФайлНазначениеLex.lОписания токенов для лексического анализатора на входномязыке LEX.Parce.yОписание синтаксиса для YACC. Генерация деревавнутреннего представления и генерация RTL.Vmk.c, vmk.hСобственно реализация компилятора. Инициализации...

Атакже заглушки для функций, которые от нас требует gcc.Vmk1.cСюда по примеру treelang вынесены callback функцииинициализации компилятора, парсера, открытия/закрытияфайлов, декодирования параметров командной строки. Визвестном примере TOY было всё в одном файле, но мырешили его не загромождать.Язык.Разработанный front end воспринимает язык, который позволяет втекстовой формулировке записывать унарные, бинарные и тернарныематематические функции.Ограничения языка:• оперирует целыми числами;• четыре математических операции (плюс, минус, умножить, делить).Пример:binary function a isfirstly first argument plus second then mul ten;Что эквивалентно следующей программе на языке Си:a( int first, int second ){ return ( first + second ) * 10 ; }Исходные материалы.Наиболее подробно процесс создание Front end описан в документе GCCFront end HOWTO от Sreejith K MenonПрактикум «оптимизирующие компиляторы»Для очень старых версий GCC существовал Front end TOY, которыйфактически реализовывал нужную нам функциональностьВ коллекции GCC существует демонстрационный язык treelang – примертого, как нужно создавать front end-ы.

Но он гораздо крупнее TOY и необладает нужной прозрачностью для лабораторной работы.Реализация front end-a для языка, функциональность которого непревышает Си, сводится к вызовам нужных API функции работы с деревоми RTL. В том же случае, если Вы реализуете font end для более сложногоязыка, то Вам предстоит свести все дополнительные возможности кимеющимся примитивам.В нашем случае всё очень просто. Приведённые в приложении два файлаlex.l и parce.y полностью описывают язык.Практикум «оптимизирующие компиляторы»Генерация кодаПроцесс генерации кода для базового блока (ББ) состоит из трёх основныхэтапов:1.