№

п/п

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

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

Содержание

1

Цели и задачи курса

Лекция 1.
Цели и задачи курса.

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

Компиляторная среда LLVM и ее промежуточное представление (биткод).

Ограничения современных компиляторов.

Какая подготовка предполагается у слушателей курса (список вопросов).

2

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

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

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

Выбор оптимального порядка циклов в гнезде.

Раскрутка циклов.

Лекция 3.
Анализ графа потока управления.

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

Лекция 4.
Структура потока данных

Полурешетки и их свойства. Функции на полу-решетках (передаточные или потоковые функции) и их свойства. Итерационные алгоритмы нисходя-щего и восходящего анализа свойств потока данных, выражаемых функциями потока.

Лекция 5.
Исследование алго-ритма распростра-нения констант.

Отсутствие свойства дистрибутивности у пере-даточной функции алгоритма и вытекающие из этого следствия.

Лекция 6.
Выявление частич-но-избыточных вычислений.

Понятие ожидаемого выражения. Четырехфазный алгоритм выявления частичных избыточностей.

Лекция 7.
Анализ потока дан-ных на областях.

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

Лекция 8.
Глобальный анализ алиасов.

Понятие алиаса. Итерационный алгоритм. Ограниченность итерационного алгоритма.

3

Межпроцедур-ная оптимиза-ция

Лекция 9.
Организация меж-процедурной оптимизации.

Граф вызовов и его построение. Виды меж-процедурной оптимизации: учет зависимостей от потока, от пути (трассы), от контекста вызова. Основные подходы к межпроцедурной оптимизации.

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

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

4

Методы и алгоритмы машинно-ори-ентированной оптимизации.

Лекция 11.
Планирование кода.

Локальное планирование кода списком. Обобщения алгоритма. Выявление «гамаков» в графе потока управления для глобального планирования.

Лекция 12.
Распределение регистров.

Алгоритм распределения регистров с использованием раскраски узлов графа конфликтов.

Быстрые алгоритмы распределения регистров с использованием различных эвристик.

Лекция 13
Заключительные замечания.

Покадровая оптимизация и др.

5

Динамическая и адаптивная оптимизация.

Лекция 14
Профилирование.

Типы профилирования. Различные алгоритмы инструментирования для сбора профилей.

Лекция 15.
Реализация динамических оптимизаторов

Сравнительный анализ динамических оптимизаторов в среде Java и динамического оптимизатора среды LLVM.

6

Выбор последо-вательности оптимизаций в компиляторе (обзор)

Лекция 16
Выбор последо-вательности оптимизаций.

Постановка проблемы. Обзор различных подходов к решению проблемы, включая машинное обучение (Machine Learning) и генетические алгоритмы.

№

п/п

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

Семинарские (практические) занятия

Содержание

2

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

Занятие 1.

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

Занятие 2.

Решение задач по теме «Анализ графа потока управления»
Пример задачи: Построить дерево доминаторов для конкретного ГПУ

Занятие 3.

Решение задач по теме «Структура потока данных»
Пример задачи: Написать передаточную функцию анализа живых переменных для конкретного базового блока.

Занятие 4.

Решение задач по теме «Анализ потока данных на областях.»
Пример задачи: Выделить суперблоки в конкретном ГПУ

Занятие 5.

Сдача лабораторной работы № 1

Занятие 6.

Сдача лабораторной работы № 1

4

Методы и алгоритмы машинно-ори-ентированной оптимизации.

Занятие 7.

Решение задач по теме «Планирование кода»
Пример задачи: Выделить все «гамаки» в заданном ГПУ.

Занятие 8.

Решение задач по теме «Планирование кода»
Пример задачи: Выделить все «гамаки» в заданном ГПУ.

Занятие 9.

Решение задач по теме «Распределение регистров»
Пример задачи: Построить граф конфликтов для конкретной функции

Занятие 10.

Решение задач по теме «Распределение регистров»
Пример задачи: Распределить регистры (для компьютера с 4 регистрами) по заданному графу конфликтов.

Занятие 11.

Сдача лабораторной работы № 2

Занятие 12.

Сдача лабораторной работы № 2

3

Межпроцедур-ная оптимиза-ция

Занятие 13.

Решение задач по теме «Организация межпроцедурной оптимизации»
Пример задачи: Построить граф вызовов для заданной программы.

Занятие 14.

Решение задач по теме «Межпроцедурный анализ указателей.»
Пример задачи:

Занятие 15.

Заключительная контрольная работа

Занятие 16.

Обсуждение результатов контрольной работы и выставление оценок.

№

п/п

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

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

Содержание

2

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

Работа 1.

Разработка и отладка (в среде LLVM) программы глобальной машинно-независимой оптимизации.
Пример программы:

4

Методы и алгоритмы машинно-ори-ентированной оптимизации.

Работа 2.

Разработка и отладка (в среде LLVM) программы планирования кода или распределения регистров.
Пример программы: