Учебный курс «Проектирование компиляторов» - 2021

Предисловие

Данный учебный курс посвящён введению в проектирование оптимизирущих компиляторов. Он включает в себя лекции по общему устройству компиляторов и по возможностям оптимизирующих компиляторов. Курс рассчитан на студентов 3-4 курса, предполагает 38 академических часов лекций (16 тем), лабораторные и курсовые работы. При необходимости курс можно как сократить, так и увеличить до двух-семестрового. На этой странице приведены материалы, по которым курс читался в МФТИ и МАИ в 2021 году.

Материалы курса

Лекция 1. Введение в компиляторы. (слайды)

Введение
Схема работы компилятора
История появления компиляторов
Мотивация

Лекция 2. Лексический анализ. (слайды)

Лексический анализ
Регулярные выражения
Конечные автоматы

Лекция 3. Синтаксический анализ. (слайды)

Контекстно-свободные грамматики
Деревья разбора
Синтаксические анализаторы

Лекция 4. Семантический анализ. (слайды)

Таблица символов
Система типов
Ошибки проектирования языков программирования

Лекция 5. Время исполнения программы.

Исполняемый файл
Архитектура компьютера
Исполнение программы

Лекция 6. Внутреннее представление программы в компиляторе. (слайды)

Промежуточное представление
Граф потока управления
Профиль

Лекция 7. Создание целевого кода. (слайды)

Выбор инструкций
Планирование
Распределение регистров

Лекция 8. Введение в оптимизации. (слайды)

Определения
Типы оптимизаций
Линейки оптимизаций
Схема работы оптимизатора

Лекция 9. Локальные оптимизации и оптимизации потока данных. (слайды)

Свёртка констант
Алгебраические упрощения
Понижение силы операций
Распространение констант
Оконные оптимизации
Алгебраическое переупорядочивание
Балансировка выражений
Удаление общих подвыражений
Распространение копий
Удаление мёртвого кода

Лекция 10. Оптимизации потока управления. (слайды)

Введение
Удаление недостижимого кода
Упрощение переходов
Оптимизация условий
Сортировка линейных участков
Предикатное исполнение кода
Спекулятивное исполнение кода
Слияние ветвлений

Лекция 11. Оптимизации памяти.

Иерархия памяти
Виды локальности в памяти
Расположение объектов в памяти
Перенос со стека на регистры
Перенос из кучи на стек
Выстраивание массивов
Предподкачка данных

Лекция 12. Оптимизации циклов. Часть 1.

Введение
Вынос первых итераций
Вынос всех итераций
Слияние циклов
Расщипление циклов
Раскрутка циклов
Раскрутка и слияние циклов

Лекция 13. Оптимизации циклов. Часть 2.

Программная конвейеризация

Лекция 14. Оптимизации циклов. Часть 3.

Оптимизация индуктивной переменной
Вынос инвариантов
Раскоммутация цикла
Расщипление цикла по индексу
Расщипление цикла по условию

Лекция 15. Межпроцедурные и межмодульные оптимизации.

Подстановка функций
Распространение констант
Специализация функций
Режим сборки «вся программа»
Подстановка неявных вызовов
Девиртуализация