Конструирование компиляторов (8-й семестр, 2л+1с)

Оптимизация в компиляторах (9-й семестр, 2л+1с)

Введение в компиляторные технологии (8-й семестр, 2л+1с)

Применение компиляторных технологий (9-й семестр, 2л+1с)

9 семестр

Специальная дисциплина магистерской программы I (3 = 2 + 1) экз. 4,0

Оптимизация в компиляторах

Введение в компиляторные технологии

1. Структура оптимизирующего компилятора

2. Промежуточное представление «среднего уровня» (gimple, LLVM) – языково-независимое и машинно-независимое представление программы: программа = последовательность инструкций, таблица символов. Построение промежуточного представления (напоминаются методы лексического, синтаксического и семантического (контекстного) анализа и алгоритм построения таблицы символов со ссылкой на соответствующие курсы). Понятие базового блока. Построение графа потока управления процедуры.

3. Простейшие оптимизации: сворачивание констант, распространение констант и копий, «открытая вставка» функций, развертка циклов, оптимизация переходов.

4. Постановка задачи машинно-независимой оптимизации процедуры – исключение мертвого, недостижимого и избыточного кода. Решение задачи машинно-независимой оптимизации процедуры для базового блока (локальная оптимизация): локальный метод нумерации значений и его реализация.

5. Анализ потока данных – основной метод глобальной оптимизации (в пределах процедуры). Пример анализа потока данных – анализ достигающих определений. Другие примеры анализа потока данных – анализ живых переменных, анализ доступных выражений. Общая теория анализа потока данных: полурешетки, передаточные функции, итерационный алгоритм.

6. Введение в оптимизацию циклов (более подробно – в курсе «Применение компиляторных технологий»). Выделение циклов и гнезд циклов. Выявление переменных, инвариантных относительно цикла.

7. Методы ускорения анализа потока данных. Понятие о структурном анализе графа потока управления (на примере анализа достигающих определений). SSA-форма промежуточного представления программы.

8. Понятие о межпроцедурном анализе. Представление программы для межпроцедурного анализа. Способы учета контекста в точках вызова процедур (контекстно-зависимый анализ).

9. Построение промежуточного представления нижнего уровня.

10. Проблема учета особенностей архитектуры целевого компьютера. Распределение регистров. Анализ зависимостей по данным. Планирование кода. Конвейеризация циклов.

11. Динамическая оптимизация в компиляторах времени выполнения.

Применение компиляторных технологий

1. Машинно-независимая оптимизация: исключение частично-избыточного кода. «Регист-ровое давление».

2. Метод глобальной нумерации значений (два варианта) и особенности его реализации.

3. Оптимизация гнезд циклов. Анализ индуктивных переменных. Параллельное выполне-ние циклов.

4. Межпроцедурный анализ указателей. Межпроцедурная оптимизация программных модулей.

5. Методы учета особенностей архитектуры современных компьютеров при генерации оптимального кода. Современные алгоритмы планирования кода.

6. Генерация объектного кода и покадровая оптимизация.

7. Профилирование и оптимизация кода в динамических компиляторах.

8. Применение компиляторных технологий в обратной инженерии.

9. Эмуляция бинарного кода и бинарная трансляция.

10. Поиск дефектов