Введение в теорию построения оптимизирующих компиляторов, 05 лекция (от 31 октября)

Материал из eSyr's wiki.

Оптимизация компиляторов 31.10.06

В прошлый раз рассказывали про доминирование, про граф ... . Сегодня примерно про то же самое.

Структурный анализ

У нас есть граф потка управления. И в результате преобразований мы сворачиваем его в граф из одной вершины. Это делается путём изучения графа потока управления и сворачивания отдельных частей в соотв с шаблонами. Например, есть шшаблон цикла.

В результате (см рис 2) получим структурный граф. Он в некоотрой степени отражает структурную вложенность программы.

Если граф удаётся свернуть, тто он считается сводимым. Если нет – несводимым.

Пример несводимой конструкции (improper regions): см рис 3

Все шаблоны будут отвечать соотв конструкциям языка. Какие могут быть шаблоны:

1. Два блока подряд – можно заменить на один

2. Конструкция типа if then else

3. Конструкция if then

4. Self loop

5. While

Этими шаблонами моржно было бы исчерпать паскаль.

6. См. Рис 4 – сложное условие

7. Паскалевый case – рис 5

break, Label, continue, return порождают дополнительные ребра (см рис 6)

Можно делать такие преобразования, которые делают из несводимых областей сводимые (рис 7)

Для чего может понадобиться подобное преобразование графа потока управления? Для каждого блока можно легко нарисовать раскладку его на плоскоти, дерево иерархическое, и ...

Из него следует один из алгоритмов рисования графов на плоскости.

Ещё один – выделение циклов, что будет использоваться длоя дальнейшей оптимизации.

Третье, для чего нужен структ анализ – одна из задач анализа – выявление потока данных, современные алгоритмы работают на графе потока управления, и работают итертивыно. Если мы строим дерево упр конструкций, то мы можем использовать не итеративные алгоритмы, а те, которые учитывают структуру графа, и сложность у них меньше.

Четвёртое – для поддержки инкрементальных изменений.

Следующий вопрос:

Почему бы не делать структурный анализ сразу по дереву разбора?

Дерево разбора – внутренне представление – граф потока управления – структурные конструкции. Это позволяет находить больше структурнрых конструкций.

Control flow analysis

Следующий этап:

Data flow analysis

Вычисляются некторые зависимости между элементами программы. Задача DFA – вычисление некоторых фактов о взаимосвязи переменных и значений в программе. Потом эти факты используются при оптимизации. Пример:

По всей программе рассматриваем конструкции вида a op b. Например, если далее по тексту есть a op b, и ни a, ни b не меняется, то она даст тот же результат. Это позволяет ввести времпенную переменную и использовать её потом. Такое преобразование называется common subexpretion elimination (CSE). Понятно, что такие преобразования могут идти каскадом. Таким образом мы можем сворачивать не только минимальные операции, но и большие операции. Например, перемножение матриц:

a[i][j]+=b[i][k]*c[k][j] – внутренний цикл. Тут будет вычисление i-й строки.

Или:

a[i][j][k]=b[i][j][k] – считать смещение можно только один раз.

Три группы методом преобразования:

1. Локальные – работают в пределах базового блока. Можно сделать за один проход.

2. Глобальные – применяются ко всему телу процедуры или функции

3. Межпроцедурный – применяется ко всей программе в совокупности

Первые два класса методов хорошо изучены и применяются в каждом уважающем себя компиляторе. Межпроцедурных преобразований ни у кого нет. При переходе от глоб к межпроц идёт такой скачок сложности и требований к памяти, что делает их бесполезными.

Задача о достигающих определениях (reaching definition)

Достижение (определение) – присваивание некоторого значения.

I1: a<- expr

i2:

орпределние i1 достигает i2, если существует путь, в котором переменная не переприсваивается. Таким образом для каждой точки программы можно найти множество достигающих определений. [<a, i2>, <a, i3>, <b, i4>, ...} - таким образом, можно рештиь задачу о достигающих определениях.

Рассмотрим эту задачу для одного базового блока. (local reaching definition)

В рамках одного блока путь единственный. Что может быть:

Заведём рабочее множество достигающих определений. W={}

Предположим, что мы пришли к некоторой инструкции, и на входе множество W_in. Теперь мы хотим псчитать W_out. Инструкции у нас следующего вида – есть переменные, которым присваиваются и некоторое выражение. Как будет модифицироваться множество w при прохождении через данную инструкцию? Первое – выуинуть те переменные, которым присваиваются значения (множество KILL): Wout = (Win \ KILL_i). После этого мы должны добавить множество определений, которые порождаются в этой инструкции (GEN): Wout = (Win \ KILLi) объединить с GENi. Поскольку путь один, перемещаемся от инструкции к инструкции.

W_in⁽ⁱ⁺¹⁾ = W_out⁽ⁱ⁾

Wout(i) = FLOW_i(Win(i)) – функция потока

Система уравнений называется уравнением потока. Поскольку у нас базовы блок, то решать это уравнением мы можем за один поток. Более того, мы можем вычислить функцию для всего блока: Wout = FLOW_B(W_in). Можно рассм базовый блок как одну сложную инструкцию. Таким образом, мы можем решать задачу о достигающих определений для одного блока.

Global reaching defs

Рассмотрим граф потока управления.

Отличия:

1. Не можем построить функию для всего графа

2. Появление точек слияния – когда нескоьлко блоков передают управление в один. Такую точку обозначим как JOIN. Для функцци достигающих определений в точке слияния м множества объединяем.

Теперь мы можем выписать по аналогии выписать уравнение потока данных.

(расписывается уравнение для B4)

Метод простой итерации

0. Положим все множества пустыми

1. По уравнению будем рассчитывать очередную итерацию, подставляя значения с предыдущего шага

2. Итерации заканчиваются, когда все множества перестают изменяться

f=true;

while(f) {

f = false;

(считаем Wk(i))

if (Wk(i) !=Wk(i-1)) f=true;

}

Результат и будет решением уравнения потока.

Какой вопрос возникает при рассмотрении итеративного алгоритма: сходится ли он? Да, потому что мы должны каждый раз увеличивать множество, которое конечно.

Скорость – зависит от структуры программы.

Свойства такого анализа:

Алгоритм решения итеративный:

1. Прямой (forward)

2. Обратный (backward)

Возвращаемся к структурному дереву.

Если у нас есть структурное дерево, то мы можем ... .

Мыможем построить обобщённую функцию потока для каждого шаблона. Теперь у нас есть структурное дерево, для каждого элемента есть информация, обоьщенная функция потока. Как только она будет построена, мы можем вычислять итерации в порядке обхода. Мы можем снизу вверх рассчитать обобщ функции, а потом за несколько итерации рассчитать их окончатеьлный вид. В итоге итеративные алгоритмы будут работать быстрее, всег оза несколько шагов.

У нас есть, когда мы рассч достигающее определение, у нас есть пра перменная-точка в программе. У нас есть для всей функции полное множество этих точек. Мы поступим следующим образом – каждой точке программы поставим в соотв один бит:

<a, 1> <b, 2> <a, 3> <a, 5> - для хранения информации достаточно 5 бит. Теперь, если мы рассмотрим функцию потока, то она сведётся к набору битовых операции. В частности, нам нужно сначала выбросить убиваемые, то есть логическое и, а потом объединяем с множеством новых опред – логическое или. Таким образом, задача о нахажд множество дост опред свелась к операциями над битами в числе.