Конструирование оптимизирующих компиляторов (8 сем ВМК) только прогр (Программа курса)

№

п/п

Название модулей

Разделы и темы лекционных занятий

Содержание

1

Архитектура оптимизирую-щего компилятора. Цели и задачи курса.

Архитектура оптимизирующе-го компилятора. (2 часа лекций)

Задача компиляции. Основные фазы компиляции. Промежуточные представления программы. Цели и задачи курса.

Современные компиляторные среды GCC, LLVM.

2

Построение промежуточно-го представле-ния среднего уровня (обзор).

Построение промежуточного представления среднего уровня (1 час лекций)

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

Построение промежуточного представления среднего уровня – трехадресный код (четверки).

Граф потока управления и алгоритм его построения.

3

Машинно-независимая оптимизация компилируе-мого кода.

Локальная оптимизация. (1 час лекций)

Задачи локальной оптимизации. Построение ациклического направленного графа базового блока методом нумерации значений. Особенности реализации локального метода нумерации значений.

Глобальная оптимизация. Анализ и оптимизация потока управления. (2 часа лекций)

Оптимизация переходов и возвратов из функций. Открытая вставка функций. Развертка циклов.

Глобальная оптимизация. Анализ потока данных. (2 часа лекций + 8 часов лабораторных занятий)

Анализ потока данных – основной метод глобальной и межпроцедурной оптимизации. Итерационный алгоритм анализа потока данных на полурешетках. Сходимость итерационного алгоритма для различных классов передаточных функций. Монотонные и дистрибутивные структуры потока данных.

Глобальная оптимизация. Анализ зависимостей. (2 часа лекций)

DU-цепочки. Зависимости по данным и по управлению. Граф зависимостей. Построение срезов (слайсов).

Глобальная оптимизация. Методы ускорения анализа потока данных. (2 часа лекций)

Построение глубинного остовного дерева графа потока управления. Нумерация узлов графа потока управления (в глубину). Дерево доминаторов и алгоритм его построения. Понятие области. Виды областей Алгоритм построения иерархии областей для приводимых графов потока управления. Дерево управления процедуры.

Анализ потоков данных на основе областей. Построение передаточных функций областей с помощью операций композиции, сбора и замыкания. Замкнутость структуры потока данных относительно операций композиции, сбора и замыкания.

Трехэтапный алгоритм анализа потока данных на основе областей (на примере достигающих определений). Метод расщепления узлов для обработки неприводимых графов потока управления.

Глобальная оптимизация гнезд циклов. (2 часа лекций)

Выделение гнезд циклов на графе потока управления. Вынесение инвариантных вычислений за пределы цикла. Сокращение количества индуктивных переменных. Выбор оптимального порядка циклов в гнезде для улучшения локальности данных. Развертка циклов.

Глобальная нумерация значений (2 часа лекций)

SSA-форма и оптимальный метод ее построения.

Нумерация значений в расширенном базовом блоке. Повторное использование результатов для блоков, входящих в несколько путей. Механизм контекстно-ориентированных хэш-таблиц. Алгоритм нумерации значений на основе доминаторов.

Объединение глобальной нумерации значений с построением SSA-формы.

Глобальный анализ псевдонимов
(в частности, указателей и объектных ссылок). (2 часа лекций)

Проблемы, связанные с обработкой членов структур, элементов массивов и данных, доступных по указателям, в том числе – динамических данных. Понятие псевдонима (алиаса). Псевдонимы в языке Си (указатели). Псевдонимы в языке Java (объектные ссылки). Глобальный анализ псевдонимов: первая фаза – обнаружение псевдонимов, вторая фаза – распространение псевдонимов (задача анализа потока данных). Недостаточность глобального анализа псевдонимов.

Межпро-цедурный анализ указателей (2 часа лекций)

Межпроцедурный анализ указателей. Граф вызовов и способы его задания. Чувствительность анализа к потоку управления и контексту вызова. Контекстно-нечувствительный межпроцедурный анализ, его достоинства и недостатки.

4

Машинно-ориентиро-ванная оптимизация.

Особенности архитектуры современных компьютеров и задача генерации оптимального кода. (2 часа лекций)

RISC и CISC. Конвейер потока команд: блокировки конвейера, система сброса конвейера, конфликты по данным. Вырезки из массивов. Конвейер данных. Выдача команд. Блок предсказания переходов. Конвейерное выполнение. Out-of-Order-процессоры. VLIW и EPIC. Многоядерные процессоры.

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

Операции низкого уровня. Модель целевой машины (целевой язык). Псевдорегистры. Режимы адресации: прямая, косвенная, индексированная адресации.

Задачи машинно-ориентированной оптимизации: распределение памяти, распределение и назначение регистров, планирование кода.

Распределение и назначение регистров. (2 часа лекций + 8 часов лабораторных занятий)

Распределение и назначение регистров в пределах базового блока (Функция getReg()).

Глобальное распределение регистров. Интервалы жизни значений переменных и их построение. Оценка стоимости сброса. Конфликтные ситуации, граф конфликтов и его построение. Распределение и назначение регистров с помощью алгоритма раскраски графа конфликтов снизу вверх.

Планирование кода. (2 часа лекций)

Постановка задачи планирования кода: цель планирования кода – эффективное использование параллелизма на уровне команд. Ограничения планирования кода – зависимости по данным и по управлению. Упорядочение фаз распределения регистров и планирования кода. Способы оценки эффективности расписания.

Локальное планирование кода: алгоритм планирования списка.

Конвейеризация одиночных циклов.

5

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

Динамическая и адаптивная оптимизация в компиляторах времени выполнения (2 часа лекций)

Структура JIT-компилятора. Примеры JIT-компиляторов. Уровни оптимизации. Архитектура JIT-компилятора (на примере экспериментального JIT-компилятора Jikes RVM): подсистема измерений, подсистема перекомпиляции, подсистема управления процессом динамической компиляции (контроллер). Фазы JIT-компиляции. Профилирование в JIT-компиляторах. Профилирование с помощью «семплов». Хранение данных о профилях.

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

6

Применение статического и динамиче-ского анализа для решения различных задач инженерии программ.

Применение статического и динамического анализа для решения задач инженерии программ (обзорная лекция). (2 часа лекций)

Рассматриваются проблемы поиска дефектов, контроля за использованием выбранного подмножества исходного языка, понимания программ (обратная инженерия) и др.