план пособия (УМК ВМК)

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

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

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

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

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

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

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

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

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

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

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

(в) Глобальная оптимизация. Анализ потока данных.

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

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

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

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

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

(з) SSA-форма и метод ее построения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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