• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

Компиляторные технологии

Статус: Курс по выбору (Программная инженерия)
Направление: 09.03.04. Программная инженерия
Когда читается: 3-й курс, 3, 4 модуль
Формат изучения: без онлайн-курса
Язык: русский
Кредиты: 5

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

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

Планируемые результаты обучения

  • Знать структуру и состав современных оптимизирующих компиляторных сред
  • Знать цели, задачи и методы машинно-независимой, машинно-ориентированной статической и динамической оптимизации программ в процессе их компиляции
  • Знать принципы применения компиляторных сред для решения других задач программной инженерии: выявление дефектов и аудит программ, запутывание программ
  • Уметь проводить анализ потока данных
  • Владеть методами ускорения анализа потока данных иметь применять их на практике.
  • Знать методы ускорения анализа потока данных и уметь применять их на практике.
  • Владеть методами межпроцедурного анализа указателей
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Постановка задачи анализа программ в компиляторах
    Задача компиляции. Неоптимизирующий компилятор. Основные фа-зы компиляции. Выявление ошибок в процессе компиляции и сооб-щения о них. Промежуточное представление программы – трехад-ресный код (четверки). Граф потока управления и алгоритм его по-строения. Локальная и глобальная оптимизации. Метод нумерации значений (локальный) как основа локальной оптимизации. Недоста-точность локальной оптимизации.
  • Глобальная оптимизация: анализ потока данных
    Состояние программы. Путь выполнения (трасса). Прямой и обрат-ный обход программы. Передаточная функция инструкции. Компо-зиция передаточных функций. Передаточная функция базового бло-ка. Определение переменной. Постановка задачи о достигающих определениях. Понятие консервативности анализа. Передаточные функции задачи о достигающих определениях (передаточные функ-ции класса gen-kill). Замкнутость класса передаточных функций gen-kill относительно композиции. Система уравнений для задачи о до-стигающих определениях и ее решение методом итераций. Итера-тивный алгоритм для вычисления достигающих определений. Применение достигающих определений: нахождение выражений, инвариантных относительно циклов. Алгоритм обнаружения кода, инвариантного относительно цикла. Анализ живых переменных: пе-редаточные функции, система уравнений и итерационный алгоритм. Анализ доступных выражений: передаточные функции, система уравнений и итерационный алгоритм. Анализ потока данных. Обоснование итерационных алгоритмов. Понятие полурешетки. Связь между операцией сбора и полуреше-точным отношением порядка. Понятие верхнего (наибольшего) эле-мента полурешетки. Реализация полурешеток с помощью конечных множеств. Операции объединения и пересечения множеств как реа-лизации операции сбора. Диаграммы полурешеток. Декартовы про-изведения полурешеток. Понятие структуры потока данных. Понятие замкнутости семейства передаточных функций. Замкнутость се-мейств передаточных функций для достигающих определений, жи-вых переменных и доступных выражений. Монотонные и дистрибутивные структуры потока данных. Дистри-бутивность структур потока данных для достигающих определений, живых переменных и доступных выражений. Обобщенный итера-тивный алгоритм и его свойства. Понятие максимальной фиксиро-ванной точки. Сходимость обобщенного итеративного алгоритма к максимальной фиксированной точке. Идеальное решение уравнений потока данных. Решение сбором по всем путям для дистрибутивных и монотонных структур потока данных. Консервативность макси-мальной фиксированной точки. Пример недистрибутивной, но монотонной структуры потока дан-ных – распространение констант. Полурешетка для проблемы рас-пространение констант. Семейство передаточных функций, его мо-нотонность и недистрибутивность. Итерационный алгоритм распро-странения констант. Исключение частично избыточных выражений методом анализа ожидаемых выражений. Четырехэтапный алгоритм отложенного пе-ремещения кода. Достоинства и недостатки подхода. Предваритель-ный этап – ликвидация критических ребер. Первый этап – анализ ожидаемых выражений. Второй этап – анализ доступных выраже-ний. Третий этап – анализ откладываемых выражений. Четвертый этап –анализ используемых выражений (исключение мертвого кода).
  • Методы ускорения анализа потока данных. Выделение областей графа потока управления
    Структурный анализ графа потока управления. Глубинное остовное дерево и его обход. Нумерация узлов графа потока управления. Клас-сификация ребер графа потока управления. Алгоритм построения глубинного остовного дерева и упорядочения графа потока управле-ния в глубину. Нумерация узлов графа потока управления (в глуби-ну). Доминаторы. Свойства отношения доминирования. Итератив-ный алгоритм вычисления доминаторов. Дерево доминаторов и ал-горитм его построения. Классификация ребер графа потока управле-ния. Понятие естественного цикла. Алгоритм построения естественного цикла для заданного обратного ребра. Вложенность естественных циклов. Гнезда циклов. Сильно связанные компоненты. Алгоритм построения всех максимальных сильно связанных компонентов за-данного графа потока управления. Приводимые графы потока управ-ления. Неприводимые области (собственные и несобственные) графа потока управления. Примеры неприводимых областей. Глубина гра-фа потока управления. Понятие области. Виды областей Алгоритм построения иерархии об-ластей для приводимых графов потока управления. Дерево управле-ния. Алгоритм построения восходящего порядка областей графа по-тока управления. Другие способы структурирования графов потока управления: интервальный анализ, «структурный анализ» с помощью шаблонов и др. Анализ потоков данных на основе областей. Построение передаточ-ных функций областей с помощью операций композиции, сбора и замыкания. Замкнутость структуры потока данных относительно операций композиции, сбора и замыкания. Трехэтапный алгоритм анализа потока данных на основе областей (на примере достигающих определений). Метод расщепления узлов для обработки неприводи-мых графов потока управления.
  • Методы ускорения анализа потока данных
    Форма статического единственного присваивания (SSA-форма). Определение SSA-формы. Понятие -функции. Свойства -функции. Базовый алгоритм преобразования промежуточного представления программы в SSA-форму. Недостатки базового алгоритма. Пример применения алгоритма. Форма статического единственного присваивания (SSA-форма). Квазиоптимальная SSA-форма. Граница доминирования. Алгоритм построения границ доминирования. Построение множества глобальных имен и других вспомогательных множеств. Размещение -функций. Переименование переменных. Восстановление кода из SSA-формы. Проблема потери копий Глобальная нумерация значений. Два подхода к реализации глобальной нумерации значений: нумерация значений, основанная на хэшировании и нумерация значений, основанная на классификации значений. Нумерация значений, основанная на хэшировании. Нумерация значений в расширенном базовом блоке. Повторное использование результатов для блоков, входящих в несколько путей. Механизм контекстно-ориентированных хэш-таблиц. Алгоритм нумерации значений на основе доминаторов. Нумерация значений, основанная на классификации значений. Понятие конгруэнтности ориентированных графов. Объединение нумерации значений с построением SSA-формы.
  • Межпроцедурный анализ указателей
    Внутрипроцедурный (глобальный). Проблемы, связанные с обработкой членов структур, элементов массивов и данных, доступных по указателям, в том числе – динамических данных. Понятие алиаса. Алиасы в языке Си. Алиасы в языке Java. Глобальный (внутрипроцедурный) анализ алиасов: первая фаза – обнаружение алиасов, вторая фаза – распространение алиасов (задача анализа потока данных). Недостаточность глобального анализа алиасов. Межпроцедурный анализ алиасов. Способы задания графа вызовов. Чувствительность к потоку и контексту вызова. Контекстно-нечувствительный межпроцедурный анализ. Контекстно-чувствительный анализ на основе аннотаций. Контекстно-чувствительный анализ на основе классификации и клонирования. Контекстно-чувствительный анализ ссылок.
  • Другие оптимизирующие преобразования. Применение статического анализа потоков данных в задачах инженерии программ
    Оптимизация циклов: классификация и обработка индуктивных переменных, развертка циклов, исключение ненужных (избыточных) проверок условий окончания цикла. Оптимизация потока управления. Оптимизация возвратов из рекурсивных процедур. Открытое вставление процедур. Порядок применения оптимизирующих преобразований. Режимы компиляции. Распознавание программ: восстановление документации разработчика по исходному коду программы. Запутывание (обфускация) программ на языках высокого уровня. Нахождение критических ошибок и уязвимостей.
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание
  • неблокирующий Экзамен
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    0.5 * Домашнее задание + 0.5 * Экзамен
Список литературы

Список литературы

Рекомендуемая основная литература

  • Cooper, K., & Torczon, L. (2012). Engineering a Compiler. San Francisco: Elsevier Ltd. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=354941
  • Компиляторы: принципы, технологии и инструменты, Ахо, А. В., Лам, М. С., 2011

Рекомендуемая дополнительная литература

  • Shankar, P., & Srikant, Y. N. (2008). The Compiler Design Handbook : Optimizations and Machine Code Generation, Second Edition (Vol. 2nd ed). Boca Raton: CRC Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=209423