Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Конструирование компиляторов
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по алгоритмам и алгоритмическим языкам, архитектуре ЭВМ и общей алгебре в объеме, соответствующем программе первого года обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решении задач в области профессиональной деятельности 
•	ОПК-3.Б Способность решать задачи в области прикладной математики и информатики с использованием современных информационных технологий, учитывая основные требования информационной безопасности
•	ПК-4.Б Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий
Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	структуру современного оптимизирующего компилятора;
2.	структуру и состав современных компиляторных сред: GCC, LLVM и др.;
3.	промежуточные представления программы, удобные для статической оптимизации;
4.	методы машинно-независимой оптимизации;
5.	методы статической машинно-ориентированной оптимизации;
6.	методы динамического анализа и динамической оптимизации;
7.	методы динамического анализа программ и принципы построения динамических (JIT) компиляторов.

Уметь:
1.	применять компиляторные методы и технологии для решения задач обратной инженерии, защиты программного кода, обнаружения дефектов в программах и др.;
2.	строить квази-оптимальную SSA-форму процедуры;
3.	«укрупнять» узлы графа потока управления, выделяя в нем суперблоки и другие области и пересчитывая передаточные функции;
4.	осознанно выбирать режим работы компилятора, оптимальный для компилируемой программы

Владеть:
1.	методами статического анализа и оптимизации программ на основе исследования потока данных;
2.	методами и средствами статической машинно-ориентированной оптимизации (распределение регистров, планирование кода, использование параллелизма уровня машинных инструкций).

4. Формат обучения: лекции и семинарские занятия проводятся в традиционной форме, для консультирования, приёма заданий и информирования студентов используется электронная почта, блог и система автоматической проверки решений на веб-странице курса.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 54 академических часов, отведенных на контактную работу обучающихся с преподавателем, 54 академических часов на самостоятельную работу обучающихся. 

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Введение. Описание процесса компиляции. Структура оптимизи-рующего компилятора. Основные вопросы, изучаемые в курсе.	3	2	1	3	0	
2.	Построение промежуточного представления программы. Базовые блоки и граф потока управления. Биткод среды LLVM – пример промежуточного представления.	8	4	2	6	2	
3.	Текущий контроль успеваемости: первый этап практического задания	2	0	0	0	2	
4.	Локальная оптимизация. Метод нумерации значений. Представление базового блока в виде направленного ациклического графа	4	2	1	3	1	
5.	Анализ потока данных – основной метод глобальной оптимизации. Примеры анализа потока данных – анализ достигающих определений и анализ живых переменных.	8	4	2	6	2	
6.	Граф потока управления: остовное дерево, обход,  нумерация вершин, классификация дуг, отношение доминирования и построение дерева доминаторов.	4	2	1	3	1	
7.	SSA-форма промежуточного представления и ее построение. Граница доминирования. Анализ потока данных в SSA-форме. Доступные выражения.	8	4	2	6	2	
8.	Обоснование анализа потока данных: полурешетки, передаточные функции, общий  итерационный алгоритм.	4	2	1	3	1	
9.	Методы ускорения анализа потока данных. Суперблоки и другие области графа потока управления. Вычисление передаточных функций областей по передаточным функциям составляющих их базовых блоков.	8	4	2	6	2	
10.	Глобальный метод нумерации значений	4	2	1	3	1	
11.	Глобальный анализ указателей. Псевдонимы (алиасы). Недостаточность глобального анализа. Межпроцедурный анализ. Граф вызовов. Методы учета контекста.	8	4	2	6	2	
12.	Задачи, решаемые на этапе машинно-ориентированной оптимизации. Планирование кода. Распределение регистров.	4	2	1	3	1	
13.	Другие методы оптимизации: оптимизация потока управления, возвраты из рекурсивных функций. Раскрутка циклов. Открытая вставка функций. 	4	2	1	3	1	
14.	Генерация объектного кода методом переписывания дерева	4	2	1	3	1	
15.	Текущий контроль успеваемости: второй этап практического задания	5	0	0	0	5	
Промежуточная аттестация: устный экзамен	30	0	0	0	30	
Итого	108	36	18	54	54	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.
Комплексное индивидуальное практическое задание
В качестве практического задания студентам предлагается попробовать самостоятельно реализовать одно из оптимизирующих преобразований, используя инфраструктуру компилятора LLVM и его промежуточное представление – биткод. 
Примеры оптимизирующих преобразований:
•	Нахождение доступных выражений (для исключения избыточных вычислений)
•	Планирование кода в суперблоке
•	Распространение копий
•	Вынос инвариантных вычислений в предзаголовок цикла.
•	Распространение констант (с вычислением или без)
На первом этапе выполнения задания (первая - вторая недели) студент должен изучить среду LLVM, ее промежуточное представление (биткод), и, воспользовавшись компилятором Clang, получить биткод своего задания. 
На втором этапе, пользуясь возможностями LLVM, он должен составить фазу (программу), выполняющую требуемое преобразование, и включить ее в состав учебного компилятора на базе LLVM.
Для проверки задания используется автоматическая система на удаленном сервере. 
Срок выполнения задания – 12 недель. В конце семестра выставляются итоговые технические баллы.

Пример учебно-методического обеспечения для практического задания
Постановка задачи
Целью работы является создание оптимизирующего преобразования, позволяющего повысить качество кода, генерируемого учебным компилятором на базе LLVM. Задача оптимизации кода состоит в повышении его быстродействия и/или сокращения его размера.
Предлагается разработать преобразование, которое на вход получает программу в промежуточном представлении LLVM, а на выходе генерирует ее версию, оптимизированную по размеру и скорости выполнения путем удаления недостижимого и бесполезного кода. Например:

Первоначальная программа:

int main (void) {
printf(“First message \n”);
int a = 34+48;
if (0)
 printf(“Unreachable code\n”);
a = a * 2;
printf(“Second message\n”);
return 0;
}

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

int main (void) {
printf(“First message \n”);
printf(“Second message\n”);
return 0;
}

Решение задачи
Теоретические аспекты
Предполагается реализация алгоритмов удаления мертвого и недостижимого кода. Недостижимым кодом называют часть кода программы, которая ни при каких условиях не может быть исполнена, поскольку является недостижимой в графе потока управления.
Мертвый (неиспользуемый, бесполезный) код - команды, вычисляющие никогда не использующиеся значения.
Практические аспекты 
Решения должны быть написаны на языке С++ с использованием контейнеров и алгоритмов стандартной библиотеки, а также средств, предоставляемых LLVM. Оптимизирующие преобразования должны быть выполнены в учебном компиляторе, который представляет собой модифицированную версию LLVM, не содержащую оптимизирующих преобразований.

Пример сборки LLVM в ОС Linux:
В каталоге с исходными кодами следует создать каталог с названием build и перейти в него:
$ cd llvm/
$ mkdir build
$ cd build

Затем следует осуществить сборку LLVM с указанием каталога сборки и желаемого типа сборки (Debug/Release). Сборка осуществляется с помощью утилит configure и make. Ключи configure:
--prefix=<путь к каталогу инсталляции>
--disable-assertions/--enable-assertion – включить/выключить проверку утверждений
--enable-optimized/--disable-optimized – выбрать тип сборки: оптимизированная (Release) или без оптимизаций (Debug)

Для ускорения компиляции рекомендуется использовать ключ “-jN” утилиты make, где N -- число желаемых потоков сборки (как правило, равное количеству ядер процессора или количеству ядер процессора + 1).

Пример сборки Debug с выключенной проверкой утверждений и установкой в каталог </home/user/llvm> и сборкой в 8 потоков:

$   ../configure –prefix=/home/user/llvm –disable-optimized –  disable-assertions
$ make –j8
$ make install

После завершения установки и компиляции требуется добавить путь до каталога с LLVM в переменную окружения PATH:
$ export PATH=/home/user/llvm/bin:$PATH

Получить промежуточное представление LLVM для программы можно, выполнив команду:

$ clang –c –O0 –emit-llvm test.c –o test.bc

Перевод бинарного представления в ассемблер LLVM
$ llvm-dis test.bc –o test.ll

Ассемблирование в бинарное представление
$ llvm-as test.ll –o newTest.bc

Запуск преобразования pass_name из динамической библиотеки pass_name.so
$ opt -load <путь/до/динамической/библиотеки/>pass_name.so -<pass_name> test.bc –o transformedTest.bc
test.bc - файл, содержащий бинарную версию промежуточного представления LLVM.
test.ll – файл, содержащий ассемблер LLVM в читаемом виде.

Написание оптимизирующего прохода LLVM

Для выполнения работы могут потребоваться проходы следующих типов: FunctionPass (по функциям), ModulePass (по модулям), BasicBlockPass (по базовым блокам).
В качестве примера приведен проход по функциям и именем Hello, вызываемым из командной строки с помощью ключа “–hello”:

#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

namespace {
 struct Hello : public FunctionPass {
 static char ID;
 Hello() : FunctionPass(ID) {}

 virtual bool runOnFunction(Function &F) {
 errs() << "Hello: ";
 errs().write_escaped(F.getName()) << '\n';
 return false;
 }
 };
}

char Hello::ID = 0;
static RegisterPass<Hello> X("hello", "Hello World Pass", false, false);
Листинг 1. Пример компиляторного прохода
Данный код выводит на экран сообщения вида “Hello: <function_name>”.

Более детально изучить построение оптимизирующих проходов можно посмотреть в документации на компилятор (страница WritingAnLLVMPass.html в каталоге docs в поставке учебного компилятора).

Тестирование
На личной странице расположена форма загрузки файла, а также информация о результатах тестирования и минимальный набор синтетических тестов. 
Загрузка решения. Загружаемый файл должен представлять собой текст программы на языке С++, содержащий компиляторный проход, запускаемый по ключу “-dce”. После загрузки решение будет скомпилировано и запущенно с помощью утилиты “opt” на тестовом наборе данных.

Оценивается последнее присланное решение.

Для тестирования на локальной машине во время разработки предлагается осуществлять компиляцию программы с уровнем оптимизации “O0”. Локальное тестирование предлагается осуществлять с помощью программ с открытыми исходными кодами и минимального набора синтетических тестов.
Оценка

Обязательное условие:
Присланное решение должно проходить проверку на корректность на программах SQlite и Lzma.

Оценка эффективности будет производиться на расширенном синтетическом наборе тестов.
«Удовлетворительно» – реализовано удаление бесполезного кода на уровне функций.
 «Хорошо» - реализовано удаление бесполезного и недостижимого кода на уровне функций. Удаление избыточных вызовов “pure” функций (не имеющих побочных эффектов и зависящих только от аргумента), например в выражении double y=sin(x), если y нигде более не используется вызов sin(x) можно удалить.

«Отлично» - реализовано удаление бесполезного и недостижимого кода на уровне функций. Реализован алгоритм удаления частично избыточного кода, алгоритм описан в публикации: Jens Knoop, Oliver Rüthing, and Bernhard Steffen. 1994. Partial dead code elimination.SIGPLAN Not. 29, 6 (June 1994), 147-158. DOI=10.1145/773473.178256 http://doi.acm.org/10.1145/773473.17825.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Вопросы к экзамену.
1.	Структура оптимизирующего компилятора.. Построение промежуточного представления программы. 
2.	Базовые блоки и граф потока управления. Биткод среды LLVM – пример промежуточного представления. 
3.	Локальная оптимизация. Метод нумерации значений: представление базового блока в виде направленного ациклического графа. 
4.	Анализ потока данных – основной метод глобальной оптимизации. Примеры анализа потока данных – анализ достигающих определений 
5.	Анализ живых переменных. Исключение мерьвого кода.
6.	Вынесение инвариантных вычислений за пределы цикла. 
7.	Граф потока управления: остовное дерево, обход, нумерация вершин, классификация дуг. 
8.	Отношение доминирования и построение дерева доминаторов 
9.	Построение естественных циклов и гнезд циклов.
10.	SSA-форма промежуточного представления и ее построение. Граница доминирования. 
11.	Анализ потока данных в SSA-форме. Выявление доступных выражений. Исключение избыточности.
12.	Обоснование анализа потока данных: полурешетки, передаточные функции, общий  итерационный алгоритм.  
13.	Методы ускорения анализа потока данных. Суперблоки и другие области графа потока управления.
14.	Вычисление передаточных функций областей по передаточным функциям составляющих их базовых блоков. Пример – анализ достигающих определений.
15.	Вычисление передаточных функций областей по передаточным функциям составляющих их базовых блоков на примере анализа достигающих определений. 
16.	Глобальный метод нумерации значений – использование дерева доминаторов. 
17.	Глобальный анализ указателей. Псевдонимы (алиасы). Недостаточность глобального анализа. 
18.	Межпроцедурный анализ. Использование графа вызовов. 
19.	Межпроцедурный анализ. Методы учета контекста вызова.
20.	Задачи, решаемые на этапе машинно-ориентированной оптимизации. 
21.	Планирование кода. 
22.	Распределение регистров. 
23.	Оптимизация потока управления, возвраты из рекурсивных функций. 
24.	Раскрутка циклов. 
25.	Открытая вставка функций.
26.	Генерация объектного кода методом переписывания дерева

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Практическое задание, Экзамен 	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципи-ального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	методы машинно-независимой оптимизации;
2.	методы статической машинно-ориентированной оптимизации;
3.	методы динамического анализа и динамической оптимизации;
4.	методы динамического анализа программ и принципы построения динамических (JIT) компиляторов.

Владеть:
1.	методами статического анализа и оптимизации программ на основе исследования потока данных;
2.	методами и средствами статической машинно-ориентированной оптимизации (распределение регистров, планирование кода, использование параллелизма уровня машинных инструкций).	

ОПК-1.Б	
Знать:
1.	промежуточные представления программы, удобные для статической оптимизации;

Уметь:
1.	строить квази-оптимальную SSA-форму процедуры;
2.	«укрупнять» узлы графа потока управления, выделяя в нем суперблоки и другие области и пересчитывая передаточные функции;

ОПК-2.Б	
Знать:
1.	структуру современного оптимизирующего компилятора;
2.	структуру и состав современных компиляторных сред: GCC, LLVM и др.;

Уметь:
1.	применять компиляторные методы и технологии для решения задач обратной инженерии, защиты программного кода, обнаружения дефектов в программах и др.;

ОПК-3.Б	
Уметь:
1.	применять компиляторные методы и технологии для решения задач обратной инженерии, защиты программного кода, обнаружения дефектов в программах и др.;
2.	осознанно выбирать режим работы компилятора, оптимальный для компилируемой программы

ПК-4.Б	

8. Ресурсное обеспечение:

Основная литература:  
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.

Дополнительная литература:
1.	Steven S. Muchnick Advanced Compiler Design & Implementation. Morgan Kaufman Publishers, 1997
2.	Y.N. Srikant, Priti Shankar. The Compiler Design Handbook, Second Edition, CRC Press, 2008.
Информационные справочные системы:

1.	Веб-страница дисциплины:  http://algcourse.cs.msu.su/?page_id=409
2.	Веб-сайт LLVM http://llvm.org

Материально-техническое обеспечение:  Используются  компьютер и мультимедийный проектор для демонстрации слайдов в ходе лекций. Для самостоятельной работы студенты используют компьютеры в машинных залах и/или личные компьютеры.

9. Язык преподавания - русский.

10. Преподаватели:  профессор факультета ВМК МГУ С.С. Гайсарян.

11. Авторы программы:  профессор факультета ВМК МГУ С.С. Гайсарян.