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

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

Представимоптимизации в виде групп, и покажем, в каком порядке следует применятьэти группы (Рисунок 3). Раскроем состав и назначение каждой из групп.Практикум «оптимизирующие компиляторы»A.Этиоптимизацииобычнопроизводятсянадкаким-либопромежуточным представлением высокого уровня. Это делается для того,что бы сохранить исходную структуру циклов, последовательностьопераций в них и доступ к элементам массивов в виде близком кисходному. В эту группу входят следующие оптимизации:• замена скалярными переменными ссылок на элементы массива;• оптимизации кэша данных.B, С. Оптимизации данной группы производятся над промежуточнымпредставлением среднего или низкого уровня (в зависимости от выбранноймодели оптимизаций: низко-уровневой или смешанной – см.

рисунок 2).Разветвление от группы C1 к группам C2 и C3 представляет выбор методаоптимизаций, которые состоят в том, что бы уменьшить частотувыполнения некоторых частей кода без изменения семантики программы.Это разветвление так же представляет выбор анализа потока управлениядля применения оптимизаций. Перечислим оптимизации, входящие врассматриваемые блоки:• Bo встраивание функций;o оптимизации хвостовых вызовов, включая удаление хвостовойрекурсии;o замена агрегатов на константу;o продвижение констант в условных операторах;o межпроцедурное продвижение констант;o специализация и клонирование процедур;• C1o глобальное номерование значений;Практикум «оптимизирующие компиляторы»o глобальное и локальное распространение копий;o продвижение констант в условных операторах;o удаление «мёртвого кода»;• C2o локальное и глобальное удаление общих подвыражений;o вынесение инвариантного кода из тела цикла;• C3o частичное удаление ненужных вычислений;• C4o удалёние «мёртвого кода»;o подстановка операторов;o снижение мощности выражений с индексной переменной;o замена линейных индексов на адресные выражения;o удаление индексной переменной;o устранение лишних проверок включения в диапазон значений;o оптимизации потока управления;D.

Эти оптимизации всегда проводятся над низкоуровневой формойпромежуточного представления, так как они могут быть полностьюмашинно-зависимыми. В эту группу входят следующие оптимизации:• низкоуровневое встраивание функций;• оптимизация функций, не содержащих вызовов;• оптимизация кода пролога и эпилога функций, содержащих вызовыдругих функций;• специфические машинные оптимизации;Практикум «оптимизирующие компиляторы»• совмещение концов базовых блоков;• оптимизация ветвлений и перемещение условных выражений;• удаление «мёртвого кода»;• программнаяконвейеризациясраскруткойциклов,variableexpansion, переименование регистров, hierarchical reduction;• планирование инструкций – 1;• распределение регистров с помощью раскраски графа;• планирование инструкций – 2;• внутрепроцедурная оптимизация кэша инструкций;• упреждающая выборка инструкций;• упреждающая выборка данных;• предсказание переходов.E.

Оптимизации этой группы производятся на этапе линковки кода; ониоперируют перемещаемым объектным кодом:• межпроцедурное распределение регистров;• агрегация глобальных объектов;• межпроцедурная оптимизация кэша инструкций.F. Данный блок содержит следующие оптимизации:• свёртывание константных выражений;• алгебраические упрощения.Эта группа связана с другими блоками на рисунке 2 пунктирнымилиниями, что означает возможность применение этих оптимизаций налюбом другом этапе – там, где это понадобится.Практикум «оптимизирующие компиляторы»GNU Compiler CollectionДля проведения исследований в области компиляции или в целях обученияпринципам работы современного промышленного компилятора, имеетсмысл обратиться к GNU Compiler Collection.

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

Этоперенацеливаемый (как по входному языку, так и по целевой архитектуре)компилятор доступный по лицензии GPL.Оригинальная версия компилятора была написана Ричардом Сталлманом(RichardStallman).Сейчас,существуетогромноесообществоразработчиков, которые используют и совершенствуют GCC.Отметим некоторые характерные черты данного компилятора:• Поддерживает большое число языков и машинных архитектур:o Языки: С, С++, Ada95 (GNAT), Fortran 77, Fortran 95, Pascal,Modula-2, Modula-3, Java, Cobol, Chill (Cygnus).Практикум «оптимизирующие компиляторы»o Архитектуры: ARM, Alpha (DEC), Intel x86, Motorola 680x0,68C11, DSP56000, Hitachi SH и H8300, MIPS, IBM PowerPC,HP PA-RISC, SUN SPARC, IA64, AMD x86-64.• По качеству не уступает многим известным компиляторам (в томчисле и коммерческим).

Так, на Alpha результаты работы GCCсравнимы с компилятором от DEC.• GCC является постоянно развивающимся проектом. Отметимосновные направления работы по развитию компилятора:o реализация новых языков программирования;o реализация новых алгоритмов оптимизации;o введение поддержки новых платформ;o улучшение библиотек времени исполнения;o ускорение процесса отладки.Практикум «оптимизирующие компиляторы»Проходы GCCКомпиляция в GCC производится проходами, то есть последовательностьюпреобразований исходного кода программы во внутреннее представление,оптимизацией внутреннего представления, и преобразования внутреннегопредставления в машинный код.Всего проходов в GCC 3.4 – 26 штук, начиная от лексико-синтаксическогоразбора и заканчивая генерацией машинного кода и отладочнойинформации.Рассмотрим подробнее последовательность проходов.

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

Переменные представляются какузлы дерева-декларации. В результате прохода получается представлениепрограммы в виде древовидной структуры. Оптимизации на этом этапе непроисходит.Практикум «оптимизирующие компиляторы» Файлы,описывающиепроход:tree.c,fold-const.c,stor-layout.c(языконезависимый разбор); tree.h, tree.def (описание формата древовидногопредставления программы); c-* (синтаксический разбор С-программ).Оптимизация дереваОптимизация представления программы в виде дерева, перед егопереводом во внутреннее представление в виде RTL.

В настоящий моментосновная оптимизация, выполняющаяся на этом этапе – встраиваниевызываемых функций (inlining).Эта оптимизация позволяет увеличить скорость выполнения программы засчет уменьшения числа вызовов функций. Реализация функциональности находится в файле tree-inline.c.Так же выполняется свертывание констант (поддерево – выражение надконстантами – преобразуется в один узел-константу) и упрощениенекоторых арифметических выражений.Оптимизация позволяет увеличить скорость выполнения программы засчет отсутствия вычисления константных выражений и многократногоиспользования констант.

Реализация методов находится в файле fold-const.c.Генерация RTLПреобразование представления программы в виде дерева в RTL код. Приэтом проходе выполняется оптимизация if-условий для сравнений,булевых операций и условных выражений. Определяется хвостоваярекурсия. Принимается решение о лучшей организации циклов иоператоров выбора (switch).Возможные улучшения работы механизма предсказания переходов. Генерация RTL описана в файлах: stmt.c, calls.c, expr.c, explow.c, expmed.c,function.c, optabs.c, emit-rtl.c.Практикум «оптимизирующие компиляторы»В конце генерации RTL принимается решение о возможности встраиванияфункции.