Институт системного программирования Роcсийской академии наук


Статический анализ и машинно-независимая оптимизация программ.

Гайсарян Сергей Суренович, к.ф.-м.н., доцент. Полугодовой курс.

Курс опирается на спецкурс А.В. Чернова «Введение в оптимизацию программ», читаемый в пятом семестре, и на обязательный курс В.А. Серебрякова «Конструирование компиляторов», читаемый в шестом семестре.

При разработке компиляторов применяемые методы анализа программ и генерации промежуточного представления (анализ с помощью контекстно-независимых грамматик с учетом контекстных условий с помощью вычисления атрибутов) приводят к тому, что промежуточное представление программы содержит избыточные вычисления, а также мертвый и недостижимый код. Кроме того, в поток управления добавляются многочисленные «лишние» передачи управления (например, возврат из рекурсивной функции при рекурсии глубины состоит из n переходов вместо одного).

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

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

Курс предназначен для студентов 3-5 курсов.

Курс группы

Компиляторные технологии

Перейти к учебным курсам ИСП РАН