Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины для направления/ специальности подготовки бакалавра/ магистра/ специалиста
Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет компьютерных наук
Департамент программной инженерии
Программа дисциплины
"Компиляторные технологии и верификация программ"
для направления 09.03.04 «Программная инженерия»
подготовки бакалавра
Авторы программы:
Белеванцев А.А, к.ф.-м.н., abel@ispras.ru
Одобрена на заседании кафедры системного программирования «___»____________ 20 г
Зав. кафедрой Иванников В.П.
Рекомендована секцией УМС «___»____________ 20 г
Председатель
Утверждена УС факультета «___»_____________20 г.
Ученый секретарь ________________________
Москва, 2015
Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 09.03.04 «Программная инженерия», обучающихся по бакалаврской программе изучающих дисциплину " Компиляторные технологии и верификация программ".
Программа разработана в соответствии с образовательным стандартом Национального исследовательского университета «Высшая школа экономики» по направлению 09.03.04 «Программная инженерия».
1Цели освоения дисциплины
Цель курса – Целью курса является изучение основ построения оптимизирующих статических и динамических компиляторов современных языков программирования, учитывающих особенности архитектур современных компьютеров.
Задачами данного курса являются:
освоение студентами базовых знаний в области оптимизирующей компиляции программ;
приобретение теоретических знаний в области теории графов, теории решеток, методов сбора статистики, используемых при разработке методов анализа и трансформации программ;
оказание консультаций и помощи студентам в проведении собственных исследований и разработок в областях, использующих компиляторные технологии;
приобретение навыков работы на современных неоднородных распределенных компьютерных системах.
2Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
фундаментальные понятия, теории современного системного программирования;
структуру и состав современных оптимизирующих компиляторных сред (примеры – GCC, LLVM и др.);
цели, задачи и методы машинно-независимой, машинно-ориентированной статической и динамической оптимизации программ в процессе их компиляции;
принципы применения компиляторных сред для решения других задач программной инженерии: выявление дефектов и аудит программ, запутывание программ и др. ;
разрабатывать, обосновывать и реализовывать новые методы и алгоритмы машинно-независимой оптимизации программ;
разрабатывать и реализовывать новые языки и их оптимизирующие компиляторы для новых архитектур процессоров, в том числе специализированных;
применять компиляторные методы и компиляторные среды для решения задач обратной инженерии, защиты программного кода, обнаружения дефектов в программах и др.;
Иметь навыки (приобрести опыт):
освоения большого объема информации;
самостоятельной работы в Интернете;
культурой разработки и реализации системного программного обеспечения современных компьютеров;
грамотной разработки новых языков программирования и их программного обеспечения.
В результате освоения дисциплины студент осваивает следующие компетенции:
Компетенция
|
Код по ФГОС/ НИУ
|
Дескрипторы – основные признаки освоения (показатели достижения результата)
|
|
ОК-1
|
владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановки цели и выбору путей ее достижения
|
|
ОК-2
|
умение логически верно, аргументировано и ясно строить устную и письменную речь
|
|
ОК-6
|
стремление к саморазвитию, повышению своей квалификации и мастерства
|
|
ОК-7
|
умение критически оценивать свои достоинства и недостатки, наметить пути и выбрать средства развития достоинств и устранения недостатков
|
|
ОК-10
|
готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования
|
|
ОК-11
|
владение иностранным языком на уровне, достаточном для разговорного общения, а также для поиска и анализа иностранных источников информации
|
|
ПК-1
|
понимание основных концепций, принципов, теорий и фактов, связанных с информатикой
|
|
ПК-2
|
способность к формализации в своей предметной области с учетом ограничений используемых методов исследования
|
|
ПК-3
|
готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности
|
|
ПК-10
|
умение применять основы информатики и программирования к проектированию, конструированию и тестированию программных продуктов
|
|
ПК-11
|
навыки чтения, понимания и выделения главной идеи прочитанного исходного кода, документации
|
|
ПК-13
|
способность оценивать временную и емкостную сложность программного обеспечения
|
|
ПК-14
|
способность создавать программные интерфейсы
|
|
ПК-16
|
навыки использования различных технологий разработки программного обеспечения
|
|
ПК-17
|
умение применять основные методы и инструменты разработки программного обеспечения
|
3Место дисциплины в структуре образовательной программы
Изучение данной дисциплины базируется на знаниях, полученных студентами при освоении учебных дисциплин:
«Дискретная математика»,
«Программирование»,
«Информатика, математическая логика и теория алгоритмов»,
«Построение и анализ алгоритмов»,
«Архитектура вычислительных систем»,
«Операционные системы».
4Тематический план учебной дисциплины
№
|
Название раздела
|
Всего часов
|
Аудиторные часы
|
Самостоятельная работа
|
Лекции
|
Семинары
|
Практические занятия
|
1
|
Постановка задачи анализа программ в компиляторах.
|
6
|
2
|
|
2
|
2
|
2
|
Глобальная оптимизация: анализ потока данных.
|
21
|
5
|
|
8
|
8
|
3
|
Методы ускорения анализа потока данных. Выделение областей графа потока управления
|
16
|
8
|
|
4
|
4
|
4
|
Методы ускорения анализа потока данных.
|
14
|
2
|
|
6
|
6
|
5
|
Межпроцедурный анализ указателей
|
27
|
5
|
|
11
|
11
|
6
|
Другие оптимизирующие преобразования.
Применение статического анализа потоков данных в задачах инженерии программ.
|
30
|
8
|
|
11
|
11
|
|
|
114
|
30
|
|
42
|
42
|
5Формы контроля знаний студентов
Тип контроля
|
Форма контроля
|
3 год
|
Кафедра
|
Параметры **
|
1
|
2
|
3
|
4
|
Текущий
(неделя)
|
Контрольная работа
|
8
|
|
|
|
|
Например: письменная работа 60 минут
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Промежуточный
|
Домашнее задание
|
|
4
|
|
|
|
|
|
|
|
|
|
|
|
Итоговый
|
Зачет/ Экзамен
|
|
8
|
|
|
|
|
5.1Критерии оценки знаний, навыков
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.
5.2Порядок формирования оценок по дисциплине
Преподаватель оценивает работу студентов на семинарских и практических занятиях: Оценки за работу на семинарских и практических занятиях преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за работу на семинарских и практических занятиях определяется перед промежуточным или итоговым контролем - Оауд.
Преподаватель оценивает самостоятельную работу студентов. Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за самостоятельную работу определяется перед промежуточным или итоговым контролем – Осам. работа.
Накопленная оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом:
Онакопленная= 0,5* Оауд + 0,5*Осам.работа
На пересдаче студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль.
На экзамене студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.
В диплом выставляет результирующая оценка по учебной дисциплине, которая формируется по следующей формуле:
Орезульт = 0,5*Онакопл + 0,5*Оэкз
ВНИМАНИЕ: оценка за итоговый контроль блокирующая, при неудовлетворительной итоговой оценке она равна результирующей.
6Содержание дисциплины
№
п/п
|
Разделы и темы лекционных занятий
|
Содержание
|
1
|
Постановка задачи анализа программ в компилято-рах.
|
Задача компиляции. Неоптимизирующий компилятор. Основные фазы компиляции. Выявление ошибок в процессе компиляции и сообщения о них. Промежуточное представление программы – трехадресный код (четверки). Граф потока управления и алгоритм его построения. Локальная и глобальная оптимизации. Метод нумерации значений (локальный) как основа локальной оптимизации. Недостаточность локальной оптимизации.
|
2
|
Глобальная оптимиза-ция. Анализ потока данных.
|
Состояние программы. Путь выполнения (трасса). Прямой и обратный обход программы. Передаточная функция инструкции. Композиция передаточных функций. Передаточная функция базового блока. Определение переменной. Постановка задачи о достигающих определениях. Понятие консервативности анализа. Передаточные функции задачи о достигающих определениях (передаточные функции класса gen-kill). Замкнутость класса передаточных функций gen-kill относительно композиции. Система уравнений для задачи о достигающих определениях и ее решение методом итераций. Итеративный алгоритм для вычисления достигающих определений.
Применение достигающих определений: нахождение выражений, инвариантных относительно циклов. Алгоритм обнаружения кода, инвариантного относительно цикла. Анализ живых переменных: передаточные функции, система уравнений и итерационный алгоритм. Анализ доступных выражений: передаточные функции, система уравнений и итерационный алгоритм.
Анализ потока данных. Обоснование итерационных алгоритмов. Понятие полурешетки. Связь между операцией сбора и полурешеточным отношением порядка. Понятие верхнего (наибольшего) элемента полурешетки. Реализация полурешеток с помощью конечных множеств. Операции объединения и пересечения множеств как реализации операции сбора. Диаграммы полурешеток. Декартовы произведения полурешеток. Понятие структуры потока данных. Понятие замкнутости семейства передаточных функций. Замкнутость семейств передаточных функций для достигающих определений, живых переменных и доступных выражений.
Монотонные и дистрибутивные структуры потока данных. Дистрибутивность структур потока данных для достигающих определений, живых переменных и доступных выражений. Обобщенный итеративный алгоритм и его свойства. Понятие максимальной фиксированной точки. Сходимость обобщенного итеративного алгоритма к максимальной фиксированной точке. Идеальное решение уравнений потока данных. Решение сбором по всем путям для дистрибутивных и монотонных структур потока данных. Консервативность максимальной фиксированной точки.
Пример недистрибутивной, но монотонной структуры потока данных – распространение констант. Полурешетка для проблемы распространение констант. Семейство передаточных функций, его монотонность и недистрибутивность. Итерационный алгоритм распространения констант.
Исключение частично избыточных выражений методом анализа ожидаемых выражений. Четырехэтапный алгоритм отложенного перемещения кода. Достоинства и недостатки подхода. Предварительный этап – ликвидация критических ребер. Первый этап – анализ ожидаемых выражений. Второй этап – анализ доступных выражений. Третий этап – анализ откладываемых выражений. Четвертый этап – анализ используемых выражений (исключение мертвого кода).
|
3
|
Методы ускорения анализа потока данных. Выделение областей графа потока управления
|
Структурный анализ графа потока управления. Глубинное остовное дерево и его обход. Нумерация узлов графа потока управления. Классификация ребер графа потока управления. Алгоритм построения глубинного остовного дерева и упорядочения графа потока управления в глубину. Нумерация узлов графа потока управления (в глубину). Доминаторы. Свойства отношения доминирования. Итеративный алгоритм вычисления доминаторов. Дерево доминаторов и алгоритм его построения. Классификация ребер графа потока управления.
Понятие естественного цикла. Алгоритм построения естественного цикла для заданного обратного ребра. Вложенность естественных циклов. Гнезда циклов. Сильно связанные компоненты. Алгоритм построения всех максимальных сильно связанных компонентов заданного графа потока управления. Приводимые графы потока управления. Неприводимые области (собственные и несобственные) графа потока управления. Примеры неприводимых областей. Глубина графа потока управления.
Понятие области. Виды областей Алгоритм построения иерархии областей для приводимых графов потока управления. Дерево управления. Алгоритм построения восходящего порядка областей графа потока управления. Другие способы структурирования графов потока управления: интервальный анализ, «структурный анализ» с помощью шаблонов и др.
Анализ потоков данных на основе областей. Построение передаточных функций областей с помощью операций композиции, сбора и замыкания. Замкнутость структуры потока данных относительно операций композиции, сбора и замыкания. Трехэтапный алгоритм анализа потока данных на основе областей (на примере достигающих определений). Метод расщепления узлов для обработки неприводимых графов потока управления.
|
4
|
Методы ускорения анализа потока данных.
|
Форма статического единственного присваивания (SSA-форма). Определение SSA-формы. Понятие -функции. Свойства -функции. Базовый алгоритм преобразования промежуточного представления программы в SSA-форму. Недостатки базового алгоритма. Пример применения алгоритма.
Форма статического единственного присваивания (SSA-форма). Квазиоптимальная SSA-форма. Граница доминирования. Алгоритм построения границ доминирования. Построение множества глобальных имен и других вспомогательных множеств. Размещение f-функций. Переименование переменных. Восстановление кода из SSA-формы. Проблема потери копий
Глобальная нумерация значений. Два подхода к реализации глобальной нумерации значений: нумерация значений, основанная на хэшировании и нумерация значений, основанная на классификации значений. Нумерация значений, основанная на хэшировании. Нумерация значений в расширенном базовом блоке. Повторное использование результатов для блоков, входящих в несколько путей. Механизм контекстно-ориентированных хэш-таблиц. Алгоритм нумерации значений на основе доминаторов.
Нумерация значений, основанная на классификации значений. Понятие конгруэнтности ориентированных графов.
Объединение нумерации значений с построением SSA-формы.
|
5
|
Межпро-цедурный анализ указателей
|
Внутрипроцедурный (глобальный). Проблемы, связанные с обработкой членов структур, элементов массивов и данных, доступных по указателям, в том числе – динамических данных. Понятие алиаса. Алиасы в языке Си. Алиасы в языке Java. Глобальный (внутрипроцедурный) анализ алиасов: первая фаза – обнаружение алиасов, вторая фаза – распространение алиасов (задача анализа потока данных). Недостаточность глобального анализа алиасов.
Межпроцедурный анализ алиасов. Способы задания графа вызовов. Чувствительность к потоку и контексту вызова. Контекстно-нечувствительный межпроцедурный анализ. Контекстно-чувствительный анализ на основе аннотаций. Контекстно-чувствительный анализ на основе классификации и клонирования. Контекстно-чувствительный анализ ссылок
|
6
|
Другие оптимизирующие преобразования.
Применение статического анализа потоков данных в задачах инженерии программ.
|
Оптимизация циклов: классификация и обработка индуктивных переменных, развертка циклов, исключение ненужных (избыточных) проверок условий окончания цикла. Оптимизация потока управления. Оптимизация возвратов из рекурсивных процедур. Открытое вставление процедур. Порядок применения оптимизирующих преобразований. Режимы компиляции.
Распознавание программ: восстановление документации разработчика по исходному коду программы. Запутывание (обфускация) программ на языках высокого уровня. Нахождение критических ошибок и уязвимостей.
|
|
|
|
7Оценочные средства для текущего контроля и аттестации студента
7.1Тематика заданий текущего контроля
Перечень контрольных вопросов для экзамена
1. Промежуточное представление программы. Граф потока управления и алгоритм его построения. Локальная оптимизация. Представление базового блока в виде ориентированного ациклического графа. Локальный метод нумерации значений. Виды локальной оптимизации.
2. Понятие потока данных. Состояние программы. Передаточная функция инструкции. Передаточная функция базового блока. Пути выполнения.
3. Определение и использование переменной в программе. Понятие дости-гающего определения. Передаточные функции достигающих определений. Итеративный алгоритм вычисления достигающих определений.
4. Применение достигающих определений. Обнаружение кода, инвариант-ного относительно цикла и вынесение его за пределы цикла.
5. Понятие живой (активной) переменной. Итеративный алгоритм анализа живых переменных. Понятие доступного выражения. Итеративный алго-ритм вычисления доступных выражений.
6. Полурешетки. Основные свойства полурешеток. Примеры полурешеток. Наибольшая нижняя граница и ее связь с операцией сбора. Диаграммы полурешеток.
7. Структура потока данных. Замкнутость семейства передаточных функций для достигающих определений, живых переменных и доступных выраже-ний. Монотонные и дистрибутивные структуры. Дистрибутивность структур достигающих определений, живых переменных и доступных выражений.
8. Обобщенный итеративный алгоритм. Сходимость итеративного алгоритма к решению уравнений потоков данных. Максимальная фиксированная точка. Сравнение максимальной фиксированной точки с идеальным решением уравнений потока данных и решением сбором по всем путям.
9. Распространение констант как задача потока данных. Передаточные функции структуры распространения констант, ее монотонность и недист-рибутивность. Итеративный алгоритм распространения констант.
10. Обход графа потока управления. Глубинное остовное дерево. Алгоритм упорядочения графа потока в глубину. Классификация ребер графа потока управления. Доминаторы. Свойства отношения доминирования. Алгоритм вычисления доминаторов. Дерево доминаторов.
11. Обратные ребра и естественные циклы. Построение естественного цикла обратного ребра.
12. Структурный анализ графа потока управления. Понятие области. Выделение областей в графе потока. Виды областей. Построение иерархии областей для приводимых графов потока. Дерево управления. Алгоритм построения восходящего порядка областей графа потока.
13. Алгоритм анализа на основе областей: построение иерархии областей (снизу вверх) и обработка иерархии областей (сверху вниз). Пересчет передаточных функций. Пример применения алгоритм анализа достига-ющих на основе областей. Обработка неприводимых графов потоков.
14. Форма статического единственного присваивания (SSA-форма). Функции объединения значений (f-функции). Определение f-функции. Свойства f-функций. Базовый алгоритм построения SSA-формы.
15. Алгоритм построения квазиоптимальной SSA-формы. Алгоритм постро-ения границы доминирования. Алгоритм переименования переменных.
16. Алгоритм восстановления программы по ее квазиоптимальной SSA-форме.
17. Глобальная нумерация значений (постановка задачи). Два подхода к реализации глобальной нумерации значений. Первый подход: использо-вание хэш-функций.
18. Глобальная нумерация значений: конгруэнтные подграфы.
19. Анализ алиасов: определение алиасов, виды алиасов. Глобальный (внутрипроцедурный) анализ алиасов.
20. Недостаточность глобального анализа алиасов. Межпроцедурный анализ алиасов. Контекстно-нечувствительный межпроцедурный анализ и его недостатки. Построение графа вызовов.
21. Межпроцедурный анализ алиасов. Чувствительность к контексту. Строки вызовов. k-ограниченный контекстно-чувствительный анализ.
22. Контекстно-чувствительный анализ на основе клонирования и на основе аннотаций.
23. Симметричные мультипроцессоры с общей памятью (SMP). Многоядерные процессоры. Закон Амдаля. Понятие локальности данных: пространственная и временная локальность. Формальная постановка задачи распараллеливания циклов.
24. Распараллеливание циклов. Пространство итераций. Построение пространств итераций для гнезд циклов. Управление порядком выполнения циклов гнезда. Алгоритм исключения Фурье-Моцкина. Алгоритм вычисления границ циклов для заданного порядка выполнения.
8Учебно-методическое и информационное обеспечение дисциплины
8.1Базовый учебник
A.В. Axo, М.С. Лам, P. Сети, Дж.Д. Ульман. Компиляторы: принципы, технологии и инструментарий. Издание второе. / М.: ООО «И.Д. Вильямс», 2008, ISBN: 978-5-8459-1349-4
8.2Основная литература
K.D. Cooper and L. Torczon. Engineering a Compiler. / Morgan Kaufman Publishers, 2004,
ISBN: 1-55860-698-X
8.3Дополнительная литература
Y. N. Srikant, P. Shankar. The Compiler Design Handbook. 2nd edition. CRC press – 2008 ISBN: 978-1-4200-4382-2
The LLVM Compiler Infrastructure. // http://llvm.org/
A GNU Manual. // http://gcc.gnu.org/
The SUIF 2 Compiler System. // http://suif.stanford.edu/suif/suif2/
Free Compiler Construction Tools. // http://www.thefreecountry.com/programming/compilerconstruction.shtml
|
