Структура рабочей программы Гайсарян (Программа курса), страница 2

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. Распараллеливание циклов. Пространство итераций. Построение пространств итераций для гнезд циклов. Управление порядком выполнения циклов гнезда. Алгоритм исключения Фурье-Моцкина. Алгоритм вычисления границ циклов для заданного порядка выполнения.

25. Повторное использование данных. Собственные и групповые повторные использования. Анализ зависимостей по данным. Обнаружение параллельности, не требующей синхронизации. Ограничения разбиений пространства и их решение.

Перечень контрольных вопросов для экзамена в конце 7 семестра

1. Генерация кода для базового блока

2. Распределение и назначение регистров

3. Глобальное распределение и назначение регистров. Построение интервалов жизни

4. Глобальное распределение и назначение регистров. Конфликтные ситуации и граф конфликтов. Построение графа конфликтов

5. Глобальное распределение и назначение регистров. Раскраска графа конфликтов сверху вниз. Раскраска графа конфликтов снизу вверх.

6. Глобальное распределение и назначение регистров. Структура распределителя регистров. Алгоритм в целом (на примере)

7. Выбор команд путем переписывания дерева.

8. Генерация оптимального кода для выражений. Числа Ершова.

9. Рекурсивный алгоритм генерации кода для размеченного дерева выражения

10. Генерация кода с использованием динамического программирования

11. Покадровая оптимизация

12. Планирование кода. Анализ зависимостей.

13. Планирование списков базовых блоков

14. Спекулятивное планирование. Опережающее выполнение.

15. Глобальное планирование кода. Алгоритм глобального планирования на основе областей

16. Глобальное планирование кода. Агрессивные алгоритмы перемещения кода

17. Программная конвейеризация циклов.

18. JIT-компиляторы. Профилирование. Сэмплирование. Выбор «горячих» участков

19. JIT-компиляторы. Архитектура JIT-компилятора

20. Параллельное выполнение циклов. Закон Амдаля. Понятие локальности данных

21. Формальная постановка задачи распараллеливания циклов.

22. Распараллеливание циклов. Блокирование: Разбиение на блоки

23. Изменение порядка циклов.

24. Обнаружение параллельности, не требующей синхронизации (на примере)

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

   1. Необходимое оборудование для лекций и практических занятий: компьютер и мультимедийное оборудование (проектор, звуковая система)

   2. Необходимое программное обеспечение:

   3. Обеспечение самостоятельной работы: Текстовые файлы, доступные на сайтах http://www.thefreecountry.com/programming/compilerconstruction.shtml, http://llvm.org/, http://gcc.gnu.org/, http://suif.stanford.edu/suif/suif2/,

1. Наименование возможных тем курсовых работ – учебным планом не предусмотрены

2. ТЕМАТИКА И ФОРМЫ ИНДИВИДУАЛЬНОЙ РАБОТЫ – учебным планом не предусмотрены

3. ТЕМАТИКА ИТОГОВЫХ РАБОТ – учебным планом не предусмотрены

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

   1. Основная литература.

1. A.В. Axo, М.С. Лам, P. Сети, Дж.Д. Ульман. Компиляторы: принципы, технологии и инструментарий. Издание второе. / М.: ООО «И.Д. Вильямс», 2008, ISBN: 978-5-8459-1349-4

2. K.D. Cooper and L. Torczon. Engineering a Compiler. / Morgan Kaufman Publishers, 2004,
   ISBN: 1-55860-698-X

1. Дополнительная литература.

1. Y. N. Srikant, P. Shankar. The Compiler Design Handbook. 2nd edition. CRC press – 2008 ISBN: 978-1-4200-4382-2

2. The LLVM Compiler Infrastructure. // http://llvm.org/

3. A GNU Manual. // http://gcc.gnu.org/

4. The SUIF 2 Compiler System. // http://suif.stanford.edu/suif/suif2/

5. Free Compiler Construction Tools. // http://www.thefreecountry.com/programming/compilerconstruction.shtml

1. Пособия и методические указания.

1. Слайды лекций (Интернет)

Пособие по лекциям разрабатывается.

Программу составил

С. С. Гайсарян, доцент, к.ф.–м.н.

«_____»_________2012 г.