Введение
ГЛАВА І. Анализ основных методов оптимизации программ 18
1.1. Оптимизация циклов 18
1.1.1. Циклы - ключевые места при оптимизации программы IS
1.1.2. Основные виды , оптимизации циклов 19
1.1.2.1. Вынос инвариантов из тела цикла 19
1.1.2.2. Оптимизация индуктивных вычислений 19
1.1.2.3. Уменьшение числа параметров в цикле 20
1.1.2.4. Расширение возможностей итеративного цикла в Паскале 20
1.1.2.5. Буферизация циклов 21
1.1.2.6. Использование команды "Конец цикла" 21
1.2. Сравнительная характеристика локальной и
глобальной оптимизаций .21
1.2.1. Основные методы экономии памяти программы 1.2.2. Характеристика линейной оптимизации 22
1.2.3. Характеристика методов глобальной оптимизации 22
1.2.3.1. Анализ потока управления и анализ потока данных 22
1.2.3.2. Нахождение доступных выражений 23
1.2.3.3. Оценка времени сходшлости алгоритмов АПД 25
1.2.3.4. Оценка влияния глобальной оптимизации 25"
1.3. Оптимизация в рамках регулярного графа 26
1.3.1. Абстрактные циклы 26
1.3.2. Переход от абстрактного УТЛ к синтаксическому УТЛ гг
1.3.3. Последовательный вынос инвариантных вычислений из вложенных циклов <2 7
1.4. Виды оптимизирующих компиляторов 28
1.4.1. Оптимизирующий компилятор с промежуточным 9 кодом 28
1.4.2. Оптимизация на исходном языке 28
1.4.3. Синтаксический оптимизатор 29
1.4.4. Покадровая оптимизация 30
1.5. Выбор схемы для построения оптимизирующего
Паскаль-компилятора 30
1.5.1. Классическая методика реализации Паскаль-компилятора 30
1.5.2. Компилятор с универсальным промежуточным
кодом 31
1.5.3. Схема реализации Паскаль-компилятора для ЦП 32
ГЛАВА 2. Методо машинно-независимой оптимизации программ .
2.1. Представление линейного блока в виде ориентированного ациклического графа 3
2.2. Основные виды линейной оптимизации 36
2.2.1. Экономия эквивалентных вычислений 36
2.2.2. Свертка вычислений, состоящих из одних констант 37
2.2.3. Устранение избыточных операторов присваивания . 3?
2.2.4. Оптимизации, опирающиеся на конкретные значения операндов 36
2.2.5. Выделение постоянной составляющей в индексном выражении 38
2.2.6. Экономия эквивалентных вычислений с учетом использования операций отношения
2.2.7. Оптимизация эквивалентных вычислений функций 33
2.2.8. Влияние побочных эффектов при обращениях к процедурам/функциям 40
2.3. Обзор методов линейной оптимизации 40
2.3.1. Метод нумерации значений 40
2.3.2. Линейная оптимизация в компиляторе ФОРЕКС
2.3.3. Использование коммутативно-ассоциативных законов для упорядочивания выражения 45
2.4. Внутренее представление линейного блока 44
2.4.1. Структура триады 45
2.4.2. Описание эквивалентных вычислений с помощью триад 46
2.4.3. Преобразование триад в переменные и константы 4?
2.4.4. Инвариантные триады 7
2.4.5. Индуктивные триады 4?
2.4.6. Вынесенные триады 4?
2.4.7. Особенности оптимизации операций отношения. 4?
2.4.8. Структура адресных триад 43
2.4.9. Представление переменных в рамках промежуточного кода 51
2.4.10. Представление констант в промежуточном коде 52
2.5. Оптимизация регулярных циклов 54
2.5.1. Структура синтаксического УТЛ 5
2.5.2. Вынос инвариантных триад из тела регулярного цикла 55
2.5.3. Оптимизация индуктивных вычислений
2.5.3.1. Описатель итеративного цикла в промежуточном коде 58
2.5.3.2. Преобразование индуктивных вычислений 53
ГЛАВА 3. Комплексная линейнм оптимизация 6І
3.1. Описание оптимизирующих преобразований выражений Паскаля 6І
3.1.1. Представление выражения в виде ассоциативного дерева 6І
3.1.2. Перестановка констант 62.
3.1.3. Перестановка вещественных и целых операндов б 5
3.1.4. Перестановка SET - операндов о о
3.1.5. Упорядочивание операндов в ассоциативной кисти 63
3.2. Описание алгоритма линейной оптимизации 6
3.2.1. Основные и вспомогательные структуры линейного оптимизатора 64
3.2.2. Структура стека вычислений и его использование для поиска эквивалентных триад 66
3.2.3. Назначение и структура TABVAR .64
3.2.4. Особенности поиска эквивалентных адресных триад 6%
3.2.5. Особенности поиска эквивалентных обращений к стандартным функциям 63
3.2.6. Обработка операторов присваивания простым.. 41 переменным ?i
3.2.7. Обработка триад присваивания структурным переменным ?2
3.2.8. Обработка операторов присваивания вариантным полям записей 7с2
3.2.9. Обработка триад присваивания массовым и динамическим переменным ?к
3.2.10. Устранение избыточных триад присваивания ?б
3.2.11. Особенности использования констант 7?
3.2.12. Грубая оценка влияния побочного эффекта 7&
3.2.13. Описание первого прохода оптимизации SO
3.2.14. Описание второго прохода оптимизации 6І
ГЛАВА 4. Методы машинно
4.1. Обзор методов машинно-зависимой оптимизации S2
4.1.1. Метод распределения регистров с помощью счетчиков использований &2
4.1.2. Распределение индекс-регистров в линейном блоке и простых циклах 2
4.1.3. Алгоритм глобального распределения регистров 845
4.1.4. Генерация команд для линейных блоков в компиляторе ФОРЖС 84
4.2. Связь между машинно-независимой и машинно-зависимой оптимизацией 85
4.3. Краткие сведения о ЦП
4.3.1. Структура регистров в ЦП S6
4.3.2. Скрытый стек и программный магазин 88
4.4. Представление простых паскалевских типов через машинные типы ЦП ЬЗ
4.5. Оптимизации, связанные с распределением памяти для размещения переменных 91
4.6. Оптимизации, связанные с распределением регистров в линейном блоке 94
4.6.1. Задачи подготовки операндов и распределение регистров 3 -
.6.2. Описатель состояний операндов 9S
4.6.3. Структура полного описателя операнда триады 98
4.6.4. Структура таблицы регистров 9&
4.6.5. Генерация команд из триад линейного блока 400
4.6.6. Алгоритм распределения регистров (процедура GETRE6 ) ^02
4.7 Глобальное распределение регистров для FOR -циклов iOS
4.8. Эффективная реализация CASE, -оператора.. 105
4.9. Покадровые оптимизации
4.10. Характеристика ЦП как Паскаль-машины 106
ГЛАВА 5. Анализ работы оптишзирующего
5.1. Оценка качества откомпилированных программ 108
5.2. Исследование влияния оптимизации на ускорение программ 109
5.2.1. Измерение временных характеристик Паскаль-тестов 109
5.2.2. Буферизация циклов ІІ2
5.2.3. Особенности оптимизации условных циклов 112
5.2.4. Дополнительные особенности оптимизации циклов 1 13
5.3. Измерение качества межпроцедурных взаимодействий 11*3
5.4. Оценка эффективности реализации CASE - операторов И^
5.5. Анализ эффективности обработки упакованных данных ІІ 5"
5.6. Оценка эффективности алгоритмов распределения регистров 116
5.7. Оценка эффективности алгоритмов экономии памяти
5.7.1. Экономия программного кода
5.7.2. Экономия памяти, занимаемой переменными
5.8. Введение в компилятор средств анализа
статического и динамического профилей программ
ГЛАВА 6. Эффективная реажзащя расширений паскаля
6.1. Параметризация типов 12.0
6.2. Использование новых возможностей итеративного цикла 22
Заключение
