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

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГОФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИЛАБОРАТОРИЯ «ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ»ПРОЕКТ «ИССЛЕДОВАТЕЛЬСКИЙ КОМПИЛЯТОР»Практикум«Оптимизирующие компиляторы»(на примере GCC)Практикум «оптимизирующие компиляторы»СодержаниеПредисловие...............................................................................

6Общая структура компилятора ................................................. 7GNU Compiler Collection ........................................................... 14Проходы GCC..........................................................................................................................16Парсер (лексический и синтаксический анализатор) .....................................................16Оптимизация дерева ..........................................................................................................17Генерация RTL ...................................................................................................................17Оптимизация вызовов ........................................................................................................18Оптимизация переходов ....................................................................................................18Сканирование регистров (определение времени жизни переменных) .........................19Зацепление переходов .......................................................................................................19SSA ......................................................................................................................................20Продвижение констант в условных операторах ....................................................20Удаление «мертвого» кода ......................................................................................20Удаление общих подвыражений (CSE) ...........................................................................20Глобальное удаление общих подвыражений GCSE .......................................................21Оптимизация циклов..........................................................................................................21Оптимизация цепочек переходов .....................................................................................22Вторичное удаление общих подвыражений ....................................................................22Анализ потока данных .......................................................................................................22Комбинирование инструкций ...........................................................................................23Преобразование условных операторов (if-конверсия) ...................................................23Перемещение регистров ....................................................................................................23Планирование инструкций ................................................................................................24Распределение регистров ..................................................................................................24Предпочтение класса регистра ................................................................................24Локальное распределение регистров ......................................................................25Глобальное распределение регистров ....................................................................25Распределение регистров с помощью раскраски графа ........................................25Перезагрузка регистров............................................................................................25Планирование инструкций-2.............................................................................................26Переупорядочивание базовых блоков..............................................................................26Управление отложенными переходами ...........................................................................26Укорачивание ветвей .........................................................................................................27Преобразование регистров в регистровый стек ..............................................................27Вывод ассемблерного кода ...............................................................................................27Вывод информации для отладки ......................................................................................27Резюме по проходам ..........................................................................................................28Дополнительные ключи: ...................................................................................................29Практикум «оптимизирующие компиляторы»Представление программ в компиляторе ..............................

30RTL ...........................................................................................................................................33RTL формат ........................................................................................................................34Пример RTL ........................................................................................................................34Представление констант в RTL ........................................................................................35Представление регистров и памяти в RTL ......................................................................35Представление арифметических выражений в RTL .......................................................36Прочие инструкции ............................................................................................................36SSA форма в GCC ...................................................................................................................37Минусы представления RTL и дерава, используемого front end, как промежуточныхпредставлений при работе оптимизатора ........................................................................37Представление Tree SSA ...................................................................................................38SSA ......................................................................................................................................38Управляющий граф ............................................................................................................39Преобразование в SSA .......................................................................................................40Массивы ..............................................................................................................................41Применение SSA ................................................................................................................42Анализ исходной программы ................................................................................................43Языки ...................................................................................................................................43Лексический и синтаксический анализы .........................................................................45Front end ..............................................................................................................................46Создание собственного Front end ..........................................................................................49Язык.

....................................................................................................................................50Исходные материалы. ........................................................................................................50Генерация кода ........................................................................ 52Выбор инструкций .............................................................................................................53Распределение регистров. .................................................................................................55Генерация кода ...................................................................................................................61Программная конвейеризация. .........................................................................................63Кодогенератор (backend compiler) .........................................................................................69Описание архитектуры микропроцессора .......................................................................70Описание конвейера в GCC ..............................................................................................71Распознаватель конфликтов ....................................................................................71Модель распознавателя конфликтов и описание конвейера ................................72Модель описания конвейера в GCC........................................................................75Пример описания ...............................................................................................................77Описание целевой машины в GCC на примере микроконтроллера семейства AVR.

.79Файл tm.h ...................................................................................................................81Файл tm.с ...................................................................................................................86Файл tm.md ................................................................................................................87Оптимизации в компиляторе ................................................... 92Определение оптимизирующего преобразования ..........................................................92Участки экономии.