Главная страница « Спецкурсы «

Курс „Введение в анализ и оптимизацию программ“

Лектор: канд. физ.-мат. наук Чернов Александр Владимирович
для студентов 3-5 курса

Аннотация

Новости
Преподаватели и сотрудники
Студенты и аспиранты
Научно-исследовательский семинар
Спецсеминары
Просеминар
Спецкурсы
Проекты
Ссылки
Поиск

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

В спецкурсе рассматриваются следующие вопросы:

  1. Структура компилятора. Виды промежуточных представлений программы, используемые при оптимизации. Место оптимизационных фаз в структуре компилятора.

  2. Анализ потока управления. Структурный анализ. Выделение циклов.

  3. Итерационные методы анализа потока данных. Уравнение потока. Сходимость. Задача о достигающих определениях.

  4. Локальное и глобальное устранение общих подвыражений.

  5. Вынос инвариантов из цикла. Уменьшение сложности (strength reduction) индуктивных выражений.

  6. Представление программы со статически однократным присваиванием (SSA). Перевод из регулярного представления в SSA и обратно.

  7. Продвижение констант и копий в SSA-представлении. Устранение мёртвого кода в SSA-представлении.

  8. Анализ указателей (alias analysis).

  9. Анализ интервалов жизни переменных. Устранение мёртвого кода. Глобальное распределение регистров методом раскраски графа.

  10. Понятие локальности. Оптимизации, повышающие локальность.

  11. Планирование инструкций (instruction scheduling).

  12. Полустатический (profile-based) анализ и оптимизация программ. Перегруппировка базовых блоков.

  13. Динамическая оптимизация программ. Just-in-time компиляторы.

Литература:

  1. А. Ахо, М. Лам, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2008.

  2. R. Allen, K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, 2002.

  3. A. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998.

  4. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 11.6.2008