Новый подход к межпроцедурному анализу программ

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

Содержание
Введение
Общая характеристика работы
Содержание работы
1 Существующие методы описания и исследования структуры программ
1 Подходы к исследованию структуры программ
2 Граф алгоритма и его использование при анализе программ
3 Обзор существующих методов межпроцедурного анализа программ
3.1 Основные положения
3.2 Неточные методы получения READ и WRITE областей
3.3 Точные методы получения READ и WRITE областей
3.4 Сравнение методов получения READ и WRITE областей
3.5 Получение IN и OUT областей из READ и WRITE областей
2 Каноническая форма параметрического описания графа алгоритма
1 Описание задачи
2 Описание алгоритма канонизации
2.1 Нормализация
2.2 Исключение переменных из равенств
2.3 Эвристические методы
2.4 Исключения Фурье-Моцкина
2.5 Исключения Омег а-теста
2.6 Перебор гиперплоскостей
2.7 Получение неизбыточного описания
2.8 Гарантия сохранности формы многогранников
3 Операции над областями
4 Геометрические свойства областей
5 Свойства дуг графа алгоритма на канонических областях
6 Определение свойств программ на основе канонической формы параметрического описания графа алгоритма
3 Межпроцедурный анализ программ на основе канонической формы параметрического описания графа алгоритма
1 Получение IN и OUT областей с помощью графа алгоритма
2 Описание входных и выходных данных процедуры в терминах фактических параметров (обратная подстановка)
3 Анализ данных, использующих общую память
4 Исследование возможности проведения межпроцедурного анализа
5 Методика проведения анализа больших программных комплексов

6 Пример применения техники межпроцедурного анализа
4 Практическое применение описанных методов
1 Немного о компьютерах СЛАУ У-МР С90 и СЛАУ
2 Оптимизация программы ЫШТС для одного векторно-конвейерного
процессора СЛАУ У-МР С90
2.1 Общая характеристика и структура программы
2.2 Анализ и оптимизация программы
2.3 Результаты оптимизации
3 Оптимизация программы ОСМА для компьютеров СЛАУ У-МР С90
3.1 Общая характеристика и структура программы
3.2 Анализ и оптимизация программы
3.3 Оставшиеся узкие места программы
3.4 Результаты оптимизации
4 Анализ и получение параллельной версии П
4.1 Общая характеристика и структура ЛЪ052
4.2 Потенциал параллелизма программы
4.3 Какое распределение данных использовать?
4.4 Как распределять итерации циклов?
4.5 Согласование распределений данных и итераций
4.6 Оптимизация работы программы на каждом процессоре
4.7 Результаты оптимизации РЬ052
Заключение
Литература

Список рисунков
1 Дерево методов межпроцедурного анализа
2 Фрагмент программы и вычисляемая область массива
3 Область, полученная методом ограниченных регулярных секций
4 Область, полученная методом описания с помощью триплетов
5 Область, полученная методом простых секций
6 Область, заданная минимальной выпуклой оболочкой
7 Проектирование методами Фурье-Моцкина и Омега-теста
8 Определение избыточности ограничения
9 Пересечение, разность и объединение двух областей
10 Разность двух областей (ограничение-равенство)
11 Разность двух областей (ограничение-неравенство)
12 Свойства областей
13 Порядок проекций вершин
14 Пример последовательно выполняемого фрагмента программы
15 Области в пространстве итераций
16 Вспомогательный фрагмент программы
17 Обратная подстановка
18 Анализ директивы EQUIVALENCE
19 Анализ данных в COMMON-блоках
20 Исследование условий линейности функции Трд
21 Методика проведения анализа программ
22 Пример применения техники межпроцедурного анализа
23 Фрагмент графа вызовов программы LIU-FTC
24 Фрагмент подпрограммы F33C
25 Фрагмент подпрограммы NNL
26 Структура фрагмента подпрограммы TAULW
27 Фрагмент подпрограммы RADFLW
28 Фрагмент подпрограммы GAUSPH
29 Схлопывание циклов
30 Граф вызовов программы FL052
31 Циклический профиль подпрограммы EFLUX
32 Тривиальное распределение итераций
33 Координатное распределение итераций
34 Структура подпрограммы PSMOO
35 Возможные схемы распределения итераций
36 Схемы параллельного взаимодействия
37 Полученное ускорение

можных пар линейных участков. Если одна из областей состоит из тпг линейных участков, а другая — из 777.2, то для построения пересечения необходимо 0(m,mi) раз произвести операцию элементарного пересечения. При построении совокупного образа этого удаётся избежать, так как все ссылки на массив объединены в одном описателе.
3.5 Получение IN и OUT областей из READ и WRITE областей
Метод получения IN и OUT областей из READ и WRITE областей подробно описан в [30, 31]. Под IN областью массива, используемого в анализируемой подпрограмме, понимается множество элементов данного массива, необходимых для выполнения подпрограммы и не вычисляемых ранее в её теле, то есть полученных извне данной подпрограммы. Под OUT областью массива понимается множество элементов, вычисляемых в теле подпрограммы и используемых где-либо после выхода из неё. IN и OUT области точно описывают влияние подпрограммы на контекст её вызова, то есть решают одну из задач межпроцедурного анализа.
Процесс вычисления IN областей идёт “снизу вверх” — от вызываемых подпрограмм к вызывающим. Внутри одной подпрограммы вычисление IN области производится в порядке, обратном направлению дуг графа управления. Сначала в качестве IN области принимается READ область, соответствующая последнему оператору, вычисляющему элементы анализируемого массива. Затем при движении по операторам к началу подпрограммы из текущей области вычитаются WRITE области, соответствующие данному массиву, и добавляются соответствующие READ области. Подобный алгоритм существует и для получения IN области DO-цикла, суммирующей IN области со всех его итераций.
Для получения OUT области подпрограммы недостаточно анализа её тела, необходимо знание использования элементов данной области в последующем тексте. Поэтому процесс вычисления OUT областей идёт “сверху вниз” — от вызывающих подпрограмм к вызываемым. Сначала для анализируемого массива получаются IN области для операторов вызывающей подпрограммы и других вызовов после вызова данной подпрограммы. Объединение полученных областей пересчитывается в терминах формальных параметров анализируемой подпрограммы, после чего и начинается собственно процесс построения OUT области для данной подпрограммы. Для всех операторов подпрограммы, перебираемых в порядке, задаваемом дугами графа управления, берётся пересечение их WRITE областей, соответствующих анализируемому массиву, с переданной в подпрограмму областью, после чего берётся объединение таких пересечений.