Примеры оптимизирующих преобразований:

• Нахождение доступных выражений (для исключения избыточных вычислений)

• Планирование кода в суперблоке

• Распространение копий

• Вынос инварианьных вычислений в предзаголовок цикла.

• Распространение констант (с вычислением или без)

На первом этапе выполнения задания (первая - вторая недели) студент должен изучить среду LLVM, ее промежуточное представление (биткод), и, воспользовавшись компилятором Clang, получить биткод своего задания. Далее, пользуясь возможностями LLVM, он должен составить фазу (программу), выполняющую требуемое преобразование и включить ее в состав учебного компилятора на базе LLVM. Для проверки задания используется автоматическая система на удаленном сервере.

Срок выполнения задания – 12 недель. В конце семестра выставляются итоговые технические баллы.

1. 4.4 Содержание лекций

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

Лекция 2. Локальная оптимизация. Метод нумерации значений: представление базового блока в виде направленного ациклического графа.

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

Лекция 4. Граф потока управления: остовное дерево, обход, нумерация вершин, классификация дуг. Отношение доминирования и построение дерева доминаторов.Построение естественных циклов и гнезд циклов.

Лекция 5. SSA-форма промежуточного представления и ее построение. Граница доминирования.

Лекция 6. Анализ потока данных в SSA-форме. Выявление доступных выражений. Исключение избыточности.

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

Лекция 8. Методы ускорения анализа потока данных. Суперблоки и другие области графа потока управления.

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

Лекция 10. Глобальный метод нумерации значений с использованием дерева доминаторов.

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

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

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

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

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

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

1. 5. Образовательные технологии

Используются традиционные технологии проведения лекций. Учебные и методические материалы опубликованы на веб-странице http://algcourse.cs.msu.su/?page_id=409.

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

1. 6. Учебно-методическое и информационное обеспечение дисциплины

а) основная литература

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. Веб-страница дисциплины: ://algcourse.cs.msu.su/?page_id=409./

2. Веб-сайт LLVM http://llvm.org

1. 7. Материально-техническое обеспечение дисциплины

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

1. 8. Учебно-методическое обеспечение самостоятельной работы студентов

8.1 Пример учебно-методического обеспечения для практического задания

Постановка задачи

Целью работы является создание оптимизирующего преобразования, позволяющего повысить качество кода, генерируемого учебным компилятором на базе 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 в читаемом виде.

TH

Написание оптимизирующего прохода 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.

1. 9. Контрольно-оценочные материалы

   1. 9.1 Программа экзамена по курсу

1. Структура оптимизирующего компилятора.. Построение промежуточного представления программы.

2. Базовые блоки и граф потока управления. Биткод среды LLVM – пример промежуточного представления.

3. Локальная оптимизация. Метод нумерации значений: представление базового блока в виде направленного ациклического графа.

4. Анализ потока данных – основной метод глобальной оптимизации. Примеры анализа потока данных – анализ достигающих определений

5. Анализ живых переменных. Исключение мерьвого кода.