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

• Автор: Идрисов, Ренат Искандерович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 143 с. : ил.

Введение.

1. Обзор методов межпроцедурного анализа и внутренних представлений целевого языка.

1.1 Анализ совмещений.

1.2 Анализ значений

1.3 Анализ использования переменных

1.3.1 Неточные алгоритмы описания областей массивов

1.3.1.1 Регулярные секции i.

1.3.1.2 Дескрипторы доступа к данным i

1.3.1.3 Регионы i

1.3.2 Точные алгоритмы описания областей массивов

1.3.2.1 Образы I.

1.3.2.2 Линеаризация iii.
1.3.2.3 Омегатест.
1.3.3 Комбинированные методы
1.4 Анализ контекста использования процедуры.
1.5 Язык I.
1.5.1 Система
1.5.2 Внутреннее представление I1.
1.5.3 Внутреннее представление I2.
1.5.4 Внутреннее представление I3.
Выводы по первой главе.
2. Практическая реализация анализа и оптимизаций
2.1 Свойства внутренних представлений
2.2 Хранение контекстных условий.
2.3 Алгоритмы анализа
2.3.1 Протягивание одиночных значений
2.3.2 Протягивание мультизначений
2.3.3 Протягивание диапазонов
2.3.4 Протягивание мультидиапазонов
2.3.5 Протягивание другой информации о значениях.
2.3.6 Анализ массивов
2.3.7 Реализация алгоритмов анализа значений.
2.4 Алгоритмы оптимизации
2.4.1 Удаление избыточного кода
2.4.3 Вынос инвариантных вычислений
2.4.4 Оптимизация циклических конструкций
2.4.5 Оптимизация копирования
2.5 Межпроцедурный анализ
2.5.1 Граф исполнений вызовов
2.5.3 Алгоритмы анализа
2.6. Алгоритмы распараллеливания.
2.6.1 Построение развртки
2.6.2 Влияние оптимизирующих алгоритмов.
2.6.3 Макропараллелизм циклов I.
Выводы по второй главе
3. Тестирование анализа и оптимизаций.
3.1 Структура разработанного транслятора
3.2 Ввод и вывод данных.
3.3 Вычислительные задачи.
Выводы по третьей главе.
Заключение
Список литературы


Статическое совмещение (explicit aliasing) - возникает, когда две переменные с помощью конструкций языка обозначаются как указывающие на одну область памяти (например union в языке С или equivalence в языке Fortran). Анализ таких совмещений не вызывает сложностей. Совмещение через параметры (parameter aliasing) - возникает, когда переменная передаётся в функцию в качестве нескольких из формальных параметров или выступает в качестве параметра, но также доступна из глобального окружения. Динамическое совмещение или совмещение указателей (pointer aliasing) -возникает вследствие неизвестных значений переменных типа “указатель”, которые могут отвечать также за одну ячейку памяти. Алгоритмы анализа совмещений по параметрам и алгоритмы анализа динамических совмещений имеют много общего. В первом случае совмещение порождается вызовом функции, а во втором - изменением указателя. В общем случае проблема точного определения совмещений является неразрешимой, она сводится к проблеме функциональной эквивалентности. Ачгоритмы дают лишь приближённую информацию, но если в результате анализа выявлено, что переменные не могут быть совмещены в процессе исполнения программы - они не должны совмещаться никогда на практике, а если они могут быть совмещены - не означает, что переменные будут обязательно при любом исполнении программы обозначать одну и ту же ячейку памяти. Для этой рекурсивной процедуры нельзя точно сказать, как будут совмещены параметры в процессе исполнения программы, если заранее не известно значение переменной е. Контекстная чувствительность - чувствительность алгоритма к контексту вызова процедуры. В случае вызова процедуры по различным путям в графе вызовов программы реальная информация о совмещениях может быть различной. Это может быть учтено на стадии статического анализа, но не для любого случая. В соответствии с наличием такой возможности выделяют контекстно-чувствительные (context-sensitive) [] и контекстнонечувствительные (context-insensitive) [] алгоритмы анализа. Узловая чувствительность — чувствительность алгоритма к точке определения совмещений внутри процедуры. Некоторые функции подпрограммы могут изменять множество совмещений и это так же можно учесть на стадии статического анализа. Свойством узловой чувствительности могут обладать только алгоритмы анализа динамических совмещений, поскольку новые совмещения по параметрам могут возникнуть только на входе в процедуру и, соответственно, не могут измениться в процессе её исполнения. Тесты на реальном классе задач могут показать, что уточнение информации не происходит []. В большинстве случаев пользуются нечувствительными алгоритмами (flow-insensitive) и уточняют информацию различными способами []. В классическом потоковом анализе [] структурные компоненты не рассматриваются отдельно, в этом случае при совмещении одной из компонент структуры или массива вся структура или массив считается потенциально совместимой (возможной к совмещению в процессе исполнения программы). В этом случае говорят об обобщённой переменной массива или записи. Отдельный анализ структурных переменных можно найти в работе []. Существует также промежуточный вариант, когда для записи информации о структурных компонентах используются неточные алгоритмы []. Наличие первичных и вторичных множеств возможных совместителей означает, что алгоритм разделяет переменные, с которыми другая переменная связана посредством присваивания или совмещения через параметр непосредственно и переменных, с которыми она может быть совмещена, поскольку совмещённая с ней переменная имеет также своих совместителей. В работе [] рассматривается такой подход. Отличительной особенностью этой работы является то, что анализируются не совмещения, а синонимы, что можно было бы отнести к различиям в терминологии, но авторы указали явно, что синонимы, рассматриваемые ими, отличаются от совмещений. Подход, используемый в указанной работе, является грамматическим []. Это означает, что синонимы исследуются при помощи построения грамматик, в отличие от большинства других подходов, где используется дерево граф программы во внутреннем представлении компилятора.