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

Вариативная часть, в т.ч. :

__4___ зач. ед.

Лекции

__34___ часа

Практические занятия

__ нет ___ часов

Лабораторные работы

__16___ часов

Индивидуальные занятия с преподавателем

__нет___ часов

Самостоятельные занятия

__18__ часов

Итоговая аттестация

Экзамен 8 семестр

ВСЕГО

50 часов

№ темы и название

Количество часов

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

1

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

1

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

14 + 8

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

10 + 8

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

4

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

2

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

2

ВСЕГО часов

50 (34 л. + 16 лаб.)

№ темы и название

Количество часов

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

1

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

1

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

14

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

10

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

4

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

2

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

2

ВСЕГО часов

34

№ темы и название

Количество часов

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

8

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

8

ВСЕГО часов

16

№ п.п.

Темы

Трудоёмкость (количество часов)

1

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

14 час.

2

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

4 час.

3

Подготовка к выполнению лабораторных работ.

4

Подготовка к экзамену

ВСЕГО (зач. ед.(часов))

№

п/п

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

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

Содержание

1

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

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

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

2

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

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

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

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

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

3

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

Локальная оптимизация.

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

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

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

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

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

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

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

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

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

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