|
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГО
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
ЛАБОРАТОРИЯ «ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ»
ПРОЕКТ «ИССЛЕДОВАТЕЛЬСКИЙ КОМПИЛЯТОР»
Практикум
«Оптимизирующие компиляторы»
(на примере GCC)
Содержание
Содержание 3
Предисловие 11
Предисловие 11
Общая структура компилятора 13
Общая структура компилятора 13
GNU Compiler Collection 21
GNU Compiler Collection 21
Проходы GCC 23
Проходы GCC 23
Парсер (лексический и синтаксический анализатор) 23
Парсер (лексический и синтаксический анализатор) 23
Оптимизация дерева 24
Оптимизация дерева 24
Генерация RTL 24
Генерация RTL 24
Оптимизация вызовов 25
Оптимизация вызовов 25
Оптимизация переходов 25
Оптимизация переходов 25
Сканирование регистров (определение времени жизни переменных) 26
Сканирование регистров (определение времени жизни переменных) 26
Зацепление переходов 26
Зацепление переходов 26
SSA 26
SSA 26
Продвижение констант в условных операторах 27
Удаление «мертвого» кода 27
Удаление общих подвыражений (CSE) 27
Удаление общих подвыражений (CSE) 27
Глобальное удаление общих подвыражений GCSE 28
Глобальное удаление общих подвыражений GCSE 28
Оптимизация циклов 28
Оптимизация циклов 28
Оптимизация цепочек переходов 29
Оптимизация цепочек переходов 29
Вторичное удаление общих подвыражений 29
Вторичное удаление общих подвыражений 29
Анализ потока данных 29
Анализ потока данных 29
Комбинирование инструкций 29
Комбинирование инструкций 29
Преобразование условных операторов (if-конверсия) 30
Преобразование условных операторов (if-конверсия) 30
Перемещение регистров 30
Перемещение регистров 30
Планирование инструкций 31
Планирование инструкций 31
Распределение регистров 31
Распределение регистров 31
Предпочтение класса регистра 31
Локальное распределение регистров 31
Глобальное распределение регистров 32
Распределение регистров с помощью раскраски графа 32
Перезагрузка регистров 32
Планирование инструкций-2 32
Планирование инструкций-2 32
Переупорядочивание базовых блоков 33
Переупорядочивание базовых блоков 33
Управление отложенными переходами 33
Управление отложенными переходами 33
Укорачивание ветвей 33
Укорачивание ветвей 33
Преобразование регистров в регистровый стек 34
Преобразование регистров в регистровый стек 34
Вывод ассемблерного кода 34
Вывод ассемблерного кода 34
Вывод информации для отладки 34
Вывод информации для отладки 34
Резюме по проходам 34
Резюме по проходам 34
Дополнительные ключи: 35
Дополнительные ключи: 35
Представление программ в компиляторе 37
Представление программ в компиляторе 37
RTL 40
RTL 40
RTL формат 41
RTL формат 41
Пример RTL 41
Пример RTL 41
Представление констант в RTL 42
Представление констант в RTL 42
Представление регистров и памяти в RTL 42
Представление регистров и памяти в RTL 42
Представление арифметических выражений в RTL 43
Представление арифметических выражений в RTL 43
Прочие инструкции 43
Прочие инструкции 43
SSA форма в GCC 44
SSA форма в GCC 44
Минусы представления RTL и дерева, используемого front end, как промежуточных представлений при работе оптимизатора 44
Минусы представления RTL и дерева, используемого front end, как промежуточных представлений при работе оптимизатора 44
Представление Tree SSA 45
Представление Tree SSA 45
SSA 45
SSA 45
Управляющий граф 47
Управляющий граф 47
Преобразование в SSA 48
Преобразование в SSA 48
Массивы 49
Массивы 49
Применение SSA 50
Применение SSA 50
Анализ исходной программы 51
Анализ исходной программы 51
Языки 51
Языки 51
Лексический и синтаксический анализы 53
Лексический и синтаксический анализы 53
Front end 54
Front end 54
Создание собственного Front end 57
Создание собственного Front end 57
Язык. 58
Язык. 58
Исходные материалы. 58
Исходные материалы. 58
Генерация кода 60
Генерация кода 60
Выбор инструкций 61
Выбор инструкций 61
Распределение регистров. 63
Распределение регистров. 63
Генерация кода 69
Генерация кода 69
Программная конвейеризация. 71
Программная конвейеризация. 71
Кодогенератор (backend compiler) 77
Кодогенератор (backend compiler) 77
Описание архитектуры микропроцессора 78
Описание архитектуры микропроцессора 78
Описание конвейера в GCC 78
Описание конвейера в GCC 78
Распознаватель конфликтов 79
Модель распознавателя конфликтов и описание конвейера 80
Модель описания конвейера в GCC 83
Пример описания 84
Пример описания 84
Описание целевой машины в GCC на примере микроконтроллера семейства AVR. 87
Описание целевой машины в GCC на примере микроконтроллера семейства AVR. 87
Файл tm.h 89
Файл tm.с 94
Файл tm.md 95
Оптимизации в компиляторе 100
Оптимизации в компиляторе 100
Определение оптимизирующего преобразования 100
Определение оптимизирующего преобразования 100
Участки экономии. 103
Участки экономии. 103
Примеры оптимизации 108
Примеры оптимизации 108
Продвижение констант 108
Продвижение констант 108
Свертка констант 108
Свертка констант 108
Распространение копий 108
Распространение копий 108
Подстановка операторов 109
Подстановка операторов 109
Прямое преобразование 109
Прямое преобразование 109
Удаление неиспользуемого кода 109
Удаление неиспользуемого кода 109
Упрощение булевых выражений в серию переходов 110
Упрощение булевых выражений в серию переходов 110
Снижение мощности выражений с индексной переменной 110
Снижение мощности выражений с индексной переменной 110
Удаление индексной переменной 112
Удаление индексной переменной 112
Раскрутка циклов 113
Раскрутка циклов 113
Программная конвейеризация 113
Программная конвейеризация 113
Вынесение условных выражений за пределы цикла 115
Вынесение условных выражений за пределы цикла 115
Вынесение первых и последних итераций 116
Вынесение первых и последних итераций 116
Оптимизация хвостовых вызовов 118
Оптимизация хвостовых вызовов 118
Встраивание функций (Inline) 119
Встраивание функций (Inline) 119
Приложение А. Установка GCC 120
Приложение А. Установка GCC 120
Получение дистрибутива. 120
Получение дистрибутива. 120
Конфигурирование GCC 120
Конфигурирование GCC 120
Компиляция 121
Компиляция 121
Тестирование 121
Тестирование 121
Установка 121
Установка 121
Приложение Б. Использование GCC 122
Приложение Б. Использование GCC 122
Общие опции 122
Общие опции 122
Опции оптимизации и генерации отладочной информации 124
Опции оптимизации и генерации отладочной информации 124
Опции поиска каталогов и подключения библиотек 125
Опции поиска каталогов и подключения библиотек 125
Пример компиляции 126
Пример компиляции 126
Приложение В. Каталоги GCC 127
Приложение В. Каталоги GCC 127
Корневой каталог 127
Корневой каталог 127
contrib 128
contrib 128
Подкаталог gcc 130
Подкаталог gcc 130
'language' 131
config 131
Приложение Г. LEX (FLEX) 132
Приложение Г. LEX (FLEX) 132
Приложение Д. YACC (BISON) 137
Приложение Д. YACC (BISON) 137
Приложение Е. Lex.l 145
Приложение Е. Lex.l 145
Приложение Ж. parce.y 147
Приложение Ж. parce.y 147
Лабораторный практикум 150
Лабораторный практикум 150
Рекомендуемая литература 151
Рекомендуемая литература 151
Предисловие
Пособие предназначено студентам, желающим самостоятельно изучить основополагающие технологии современных оптимизирующих компиляторов. В центре внимания находится промышленный компилятор GNU Compiler Collection (GCC). Пособие основано на материалах семинаров «Проблемы генерации кода в компиляторе», проводимых в учебно-исследовательской лаборатории "Информационные технологии" факультета ВМК (проект «Исследовательский компилятор»). Целью цикла семинаров и данного документа является создание у студента связного представления об архитектуре современного промышленного компилятора (на примере GNU GCC). Цикл семинаров расширен серией компьютерных лабораторных работ, посвященных практическому изучению компилятора GCC (добавление собственного языка, перенацеливание на новую архитектуру, добавление прохода оптимизации). Авторы предполагают, что читатель знаком с теорией формальных языков (на ВМК эта теория излагается в курсах «Теория автоматов и мат. логика» Д.И. Когана и «Сетевые грамматики и языковые процессоры» С.Г. Кузина), а также с классическими принципами построения компиляторов, см., например, [1]. Для выполнения лабораторных работ требуется, чтобы у слушателя был опыт программирования на языке Си и некоторая практика пользовательской работы в среде операционной системы Linux.
Разработка методического пособия выполнена в рамках проекта «Исследовательский компилятор».
В заключение предисловия авторы выражают благодарность В.П. Гергелю, Н.Ю. Золотых, Л.В. Нестеренко за неоценимую помощь в разработке данного пособия.
Общая структура компилятора
Наиболее общее определение для понятия компилятор таково:
Компилятор – это программа, которая получает на входе программу, написанную на одном языке – исходном, и транслирует (переводит) её в эквивалентную программу на другом языке – целевом.
Для нас интерес представляет более узкое определение этого термина:
Компилятор – это программная система, которая переводит программы, написанные на языках высокого уровня в объектный или машинный код для выполнения на вычислительной машине.
Опишем общую структуру компилятора (рисунок Error: Reference source not found):
Лексический анализатор. Преобразует поток символов, который представляет исходный текст программы в поток токенов. Т. е. программа разбивается на «слова» исходного языка, называемые лексемами.
Синтаксический анализатор. Получает на вход последовательность токенов и, обычно основываясь на контекстно-свободных грамматиках, генерирует некоторое промежуточное представление, например в виде дерева. В процессе этого преобразования формируется таблица символов.
Семантический анализатор. Проверяет семантику программы, т.е. определяет правильность написания программы, основываясь на правилах исходного языка, которые не могут быть выражены контекстно-свободными грамматиками. Важным аспектом этого этапа является проверка типов.
Кодогенератор. Преобразует программу на промежуточном языке в перемещаемый машинный код или ассемблерный код. Для каждой переменной программы определяется её положение в памяти. Каждая промежуточная инструкция транслируется в одну или несколько машинных инструкций. Ключевой аспект этой фазы заключается в назначении переменных регистрам.
В настоящее время представляют интерес только, так называемые, оптимизирующие компиляторы. Оптимизирующим компилятором называется такой компилятор, который применяет улучшающие в некотором смысле преобразования программы, именуемые оптимизациями. Цели оптимизации могут быть различными, например, уменьшение времени исполнения программы и/или уменьшение размера кода.
На рисунке Error: Reference source not found приведены две основные схемы оптимизирующих компиляторов. В первом случае (рисунок Error: Reference source not found.а) все оптимизирующие преобразования выполняются над промежуточным представлением низкого уровня. Во втором (рисунок Error: Reference source not found.б) – исходная программа транслируется в среднеуровневое представление, над которым происходит большинство архитектурно независимых оптимизаций, а затем, переводится в низкоуровневое представление, над которым проводят машинно-зависимые оптимизации.
Как видно, работа компилятора разделяется на несколько фаз. Но, при реализации часто происходит объединение действий, выполняемых в различных фазах. Так, например, фазы объединяются в начальную стадию, или frond end, и заключительную стадию, или back end. Начальная стадия состоит из тех этапов компиляции, которые зависят от исходного языка и почти не зависят от целевой платформы (лексический и синтаксический анализ, создание таблицы символов, семантический анализ и генерация промежуточного кода). Сюда так же может относиться некоторая часть оптимизатора.
Заключительная стадия, состоит из тех этапов, которые зависят от целевой архитектуры, для которой выполняется компиляция. В эту стадию входит часть оптимизации кода и генерация выходного кода, сопровождаемые необходимой обработкой ошибок и работой с таблицей символов.
Теперь рассмотрим подробнее структуру оптимизатора. Представим оптимизации в виде групп, и покажем, в каком порядке следует применять эти группы (Рисунок Error: Reference source not found). Раскроем состав и назначение каждой из групп.
A. Эти оптимизации обычно производятся над каким-либо промежуточным представлением высокого уровня. Это делается для того, что бы сохранить исходную структуру циклов, последовательность операций в них и доступ к элементам массивов в виде близком к исходному. В эту группу входят следующие оптимизации:
замена скалярными переменными ссылок на элементы массива;
оптимизации кэша данных.
B, С. Оптимизации данной группы производятся над промежуточным представлением среднего или низкого уровня (в зависимости от выбранной модели оптимизаций: низко-уровневой или смешанной – см. рисунок Error: Reference source not found). Разветвление от группы C1 к группам C2 и C3 представляет выбор метода оптимизаций, которые состоят в том, что бы уменьшить частоту выполнения некоторых частей кода без изменения семантики программы. Это разветвление так же представляет выбор анализа потока управления для применения оптимизаций. Перечислим оптимизации, входящие в рассматриваемые блоки:
-
B
встраивание функций;
оптимизации хвостовых вызовов, включая удаление хвостовой рекурсии;
замена агрегатов на константу;
продвижение констант в условных операторах;
межпроцедурное продвижение констант;
специализация и клонирование процедур;
-
C1
глобальное номерование значений;
глобальное и локальное распространение копий;
продвижение констант в условных операторах;
удаление «мёртвого кода»;
-
C2
локальное и глобальное удаление общих подвыражений;
вынесение инвариантного кода из тела цикла;
-
C3
частичное удаление ненужных вычислений;
-
C4
удалёние «мёртвого кода»;
подстановка операторов;
снижение мощности выражений с индексной переменной;
замена линейных индексов на адресные выражения;
удаление индексной переменной;
устранение лишних проверок включения в диапазон значений;
оптимизации потока управления;
|
