Спецкурс «Конструирование компиляторов»

Лектор: профессор Гайсарян Сергей Суренович
общая трудоемкость – 3 зачетные единицы
форма отчетности – экзамен
аудитория курса: аспиранты

Оглавление

• Аннотация
• Программа курса
• Литература

Аннотация

Спецкурс «Конструирование компиляторов» обеспечивает слушателей необходимыми знаниями и навыками в области оптимизирующей компиляции, а также в таких смежных областях, как статический анализ для выявления дефектов, обратная инженерия, генерация тестовых покрытий и др.. Целью освоения курса является получение базовых знаний в области разработки и применения современных компиляторов и компиляторных сред для разработки программ и для решения некоторых задач по обеспечению безопасного функционирования программ, для решения которых применяются компиляторные технологии.

Программа курса

Введение. Описание процесса компиляции. Структура оптимизирующего компилятора. Основные вопросы, изучаемые в курсе. Построение промежуточного представления программы. Базовые блоки и граф потока управления. Биткод среды LLVM – пример промежуточного представления.

Локальная оптимизация. Метод нумерации значений: представление базового блока в виде направленного ациклического графа. Анализ потока данных – основной метод глобальной оптимизации. Примеры анализа потока данных – анализ достигающих определений и анализ живых переменных. Вынесение инвариантных вычислений за пределы цикла.

Граф потока управления: остовное дерево, обход, нумерация вершин, классификация дуг. Отношение доминирования и построение дерева доминаторов. Построение естественных циклов и гнезд циклов. SSA-форма промежуточного представления и ее построение. Граница доминирования. Анализ потока данных в SSA-форме. Выявление доступных выражений. Исключение избыточности.

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

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

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

Межпроцедурный анализ. Граф вызовов. Методы учета контекста.

Задачи, решаемые на этапе машинно-ориентированной оптимизации. Планирование кода.

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

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

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

Литература

1. Keith D. Cooper, Linda Torczon. Engineering a Compiler, Second Edition. 2012 Elsevier, Inc..

2. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. 2nd Edition Addison-Wesley.2006 (last modified 2008) Есть русский перевод 2010.

3. Steven S. Muchnick Advanced Compiler Design & Implementation. Morgan Kaufman Publishers, 1997

4. Y.N. Srikant, Priti Shankar. The Compiler Design Handbook, Second Edition, CRC Press, 2008.

Размещение на других ресурсах, а также коммерческое использование материалов, опубликованных в данном разделе, возможно только с разрешения авторов.

© Кафедра системного программирования ВМК МГУ.

Обновлено: 19.2.2017