Методы высокоуровневой оптимизации циклов

• Автор: Серебряный, Константин Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 91 с. : ил.

Содержание
Содержание
Введение

1 Трансформации индуктивных переменных

1.1 Трансформации циклов.

1.1.1 Автоматическая параллелизация.

1.1.2 Распознавание цикловидиом

1.1.3 Перестановка циклов.

1.1.4 Снижение стоимости индуктивных выражений

1.1.5 Развертка циклов

1.2 Индуктивные переменные и выражения

1.2.1 Преобразование типов индуктивных переменных.
1.2.2 Деление индуктивного выражения на константу
1.3 Символьное представление индуктивных выражений.
1.3.1 Сфункция.
1.3.2 Каноническая форма Сфункции
1.3.3 Линейные Сфункции
1.4 Подстановка индуктивных переменных.
1.4.1 Подстановка точек модификации.
1.4.2 Вычисление количества итераций цикла
1.4.3 Подстановка индуктивных переменных
1.5 Снижение стоимости
1.6 Другие реализации алгоритмов .
1.6.1 Идентификация индуктивных переменных
1.6.2 Снижение стоимости индуктивных выражений
1.6.3 Подстановка индуктивных переменных
1.7 Результаты.
1.8 ВыводыГ.
2 Нормализация структуры управляющей переменной цикла
2.1 Использование беззнакового типа.
2.2 Использование оператора в условии цикла
2.3 Использование оператора постинкремента
2.4 Использование глобальной переменной в качестве верхней границы .
2.5 Порядок нормализации циклов .
.2.6 Ограничения применения специализации кода
2.7 Результаты.
2.8 Выводы.
3 Профилирование значений выражений для специализации кода
3.1 Специализация кода по конкретным значениям инвариантов
3.2 Профилирование значений выражений.
3.2.1 Инструментирование программы.
3.2.2 Использование результатов инструментирования.
3.3 Результаты.
3.4 Выводы.
Заключение
Приложение. Внутренняя структура компилятора фирмы
Список литературы


Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([, §. Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках данной диссертационной работы, интересен как минимум по двум причинам. Во-первых, этот алгоритм разработан не только как теоретическое построение, но и внедрен в работающий компилятор с его заданной структурой представления программы, при этом за то же время выполняет существенно большее число трансформаций, чем предыдущий алгоритм, реализованный в компиляторе Sun. Во-вторых, в основу данного алгоритма снижения стоимости положен такой механизм символьного анализа индуктивных переменных и индуктивных выражений, который применим для очень широкого класса оптимизаций и точного аналога которому автор не нашел в известной ему литературе. После успешного внедрения в компилятор механизма символьного анализа индуктивных выражений было решено применить данный механизм для реализации еще одной оптимизирующей трансформации — подстановки индуктивных переменных. Данная оптимизация, необходимая в первую очередь дія параллелизации циклов, достаточно изучена, однако ее прежняя реализация не позволяла охватить ряд важных случаев. Применение символьного анализа к индуктивным переменным позволило существенно расширить множество обрабатываемых случаев, сохранив прежнее время компиляции. В процессе работы над алгоритмами трансформации индуктивных переменных и в ходе исследования результатов их работы было обнаружено большое количество таких циклов, которые нельзя было трансформировать из-за неправильной структуры управляющей переменной цикла. Зачастую неправильная структура управляющей переменной цикла являлась следствием применения некоторых конструкций языка Си (и Си++), например, использования глобальной переменной в качестве верхней границы цикла или оператора неравенства для проверки условия выхода из цикла. Sun. В диссертационной работе предлагается метод нормализации структуры цикла с использованием специализации кода, то есть при помощи дублирования цикла и вставки в код динамической проверки определенных условий. Реализация данного метода широко использует механизм символьного анализа индуктивных переменных, упомянутый выше. Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использования различной профильной информации (самыми распространенными типами такой информации следует назвать профиль переходов и профиль вызовов виртуальных функций). Однако профили значений выражений не нашли пока применения в большинстве компиляторов в силу крайне низкой скорости сбора статистики о значениях выражений. В большинстве работ по профилированию выражений упоминается замедление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод профилирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный “быстрый” метод позволяет собирать статистику несколько иного рода, чем ранее известные “медленные” методы. Это дает возможность не только собрать ббльшую часть информации о значениях выражений, доступной при использовании других методов, но также получить информацию о взаимозависимости значений различных выражений. Актуальность диссертационой работы обусловлена тем, что все исследованные методы оптимизации позволяют существенно повысить скорость выполнения программ.