Введение
1. Обзор методов межпроцедурного анализа и внутренних представлений целевого языка 8
1.1 Анализ совмещений 9
1.2 Анализ значений 15
1.3 Анализ использования переменных 18
1.3.1 Неточные алгоритмы описания областей массивов 20
1.3.1.1 Регулярные секции (Regular Sections) 21
1.3.1.2 Дескрипторы доступа к данным (Data Access Descriptors) 22
1.3.1.3 Регионы (Regions) 23
1.3.2 Точные алгоритмы описания областей массивов 24
1.3.2.1 Образы (Atom Images) 24
1.3.2.2 Линеаризация (Linearization) 25
1.3.2.3 Омега-тест 26
1.3.3 Комбинированные методы . 27
1.4 Анализ контекста использования процедуры 28
1.5 Язык SISAL 30
1.5.1 Система SFP 32
1.5.2 Внутреннее представление IR1 33
1.5.3 Внутреннее представление IR2 34
1.5.4 Внутреннее представление IR3 37
Выводы по первой главе 38
2. Практическая реализация анализа и оптимизаций 39
2.1 Свойства внутренних представлений 40
2.2 Хранение контекстных условий 49
2.3 Алгоритмы анализа 51
2.3.1 Протягивание одиночных значений 52
2.3.2 Протягивание мультизначений 57
2.3.3 Протягивание диапазонов 59
2.3.4 Протягивание мультидиапазонов 61
2.3.5 Протягивание другой информации о значениях 63
2.3.6 Анализ массивов 67
2.3.7 Реализация алгоритмов анализа значений 73
2.4 Алгоритмы оптимизации 74
2.4.1 Удаление избыточного кода 75
2.4.3 Вынос инвариантных вычислений 80
2.4.4 Оптимизация циклических конструкций 82
2.4.5 Оптимизация копирования 84
2.5 Межпроцедурный анализ 86
2.5.1 Граф исполнений вызовов 87
2.5.3 Алгоритмы анализа 89
2.6. Алгоритмы распараллеливания 98
2.6.1 Построение развёртки 100
2.6.2 Влияние оптимизирующих алгоритмов 107
2.6.3 Макропараллелизм циклов SISAL 109
Выводы по второй главе 111
3. Тестирование анализа и оптимизаций 112
3.1 Структура разработанного транслятора 113
3.2 Ввод и вывод данных 116
3.3 Вычислительные задачи 120
Выводы по третьей главе 126
Заключение 127
Список литературы 128
Приложение
