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

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

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

Сегодня продолжим изучение устройства компилятора.

Дерево внутреннего представления получается из дерева разбора программы путём упрощения. Такое дерево называется представлением высокоуровневым (high-level intermediate representation) – parse tree.

Для чего оно нужно:

1. Дерево разбора удобно для проведения семантического анализа. Семант анализ будет заключаться в расставлении дополн ссылок.

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

3. Некоторые оптимизации начального уровня, например свёртка констант.

4. Function inlining

5. Шаблонные подстановки, Специализации шаблонов (для извращённых языков типа С++)

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

Что мы хотим от представление среднего уровня:

1. Простота представления, чтобы в нём не было сложных синтаксических и семантических конструкций, программы была бы разложена на элементарные операции, чтобы программа представлялась на четвёрки следующего вида: результат, аргумент1, операция, аргумент2. Естественно, что при переходе от сложных выражений потребуется введение так называемых временных переменных. Например, если есть r = a+b*c, то оно будет выглядеть как t1 <- b*c; r <- a+t1. Тут потребовалось введение одной временной переменной t1. Такие временные переменны мы будем называть soft-register, pseudo-register, в противоположносьт hard-register.

2. Сделать более явным поток управления: оставить только два вида переходов – условные и безусловные. В языке видов переходов достаточно много: for, While, do while, goto, break, continue, return, if, switch, &&, ||, long_jump, в плюсах ещё обработка исключений.

3. Хотелось бы организовать области видимости.

   { f(); int a; g(); } } - область после объявления нужно выделять в отдельную область видимости

Пример:

int fib(int m)

{

int f0 = 0, f1 = 1, f2, i;

if (m<=1) return m;

for (i = 2; i<=m; i++)

{

f2 = f0+f1;

f0=f1;

f1=f2;

}

return f2;

}

как это будет выглядеть во внутреннем представлении:

L0: display {

Lm: int m;

}

L1: display {

Lf0: int f0;

Lf1: int f1;

Lf2: int f2;

Li: int i;

}

fib: func(L0, L1, int, @1) {

f0 <- 0

f1 <- 1

jg Lm, 1, L

@1 <- Lm

jmp __

L2: Li <- 2

L3: jg Li, Lm, __

Lf2 <- Lf0 + Lf1

Lf0 <- Lf1

Lf1 <- Lf2

incr(Li, Li)

jmp L3

L4: @1 <- Lf2

L5:

}

Почему имена заменили на метки – имена могут перекрываться, а метки уникальны.

Изменения:

1. Заменили имена на метки

2. Разнесены объявление и инициализация. Ибо место под переменные выделяется в стеке

3. Заменили переходы

Чем отличается от низкоур представления:

1. Оперируем с именами, а не регистрами

2. Регистры пока абстрактнгые

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

Что мы хотим сделать с этим представлением:

1. Разбить на базовые блоки и построить граф потока управления

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

В данной программе есть точка входа в функцию, которую мы обозн через entry.

<COL WIDTH=128*> <COL WIDTH=128*>

fib: func(L0, L1, int, @1) {
f0 <- 0 f1 <- 1 jg Lm, 1, L
@1 <- Lm jmp __
L2: Li <- 2
L3: jg Li, Lm, __
Lf2 <- Lf0 + Lf1 Lf0 <- Lf1 Lf1 <- Lf2 incr(Li, Li) jmp L3
L4: @1 <- Lf2
L5: }

Особенность появляется, если в язые поддерживаются исключения.

Try {

f();

g();

} catch() { }

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

Мы выделили базовые блоки, теперь можем построить граф потока управления. Вершинами графа являются базовые блоки.

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

Succ(a) – множество всех базовых блоков, которые следуют непосредственно за a:

succ(a) = {x: exist a-> x}

pred(b) = {x: exist x-> b}

Отношение доминирования:

d dom i если любой путь из entry в i проходит через d

Какие вершины доминируют над B5:

B1, B3, B4

Для exit: B1

Свойства доминирования:

1. Рефлексивность

2. Трансфлективность

3. Антисимметричность

Это отношение частичного порядка.

Что можно делать с отношением частичного порядка:

Строить дерево отношений.

A sdom b:

a dom b

a != b

a idom b:

a sdom b

not exist c: c != a, c!= b

(a dom c)&(c dom b)

Дерево доминирования:

Предком некоторой вершины будет являться вершина, непосредственно доминирующая её.

Постдоминирование:

Есди в качестве начальной будем рассматривать exit, и дуги развернём в обратную сторону.

A pdom b

any путь из b в exit проходит через a

Аналогично опред строгое и непоср доминирование.

С помощью этих переменных можно выделять циклы, живые переменны, переменные которые можно двигать.

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

N = множество вершин

pred() - отношение предшествования

pred: N -> set(N)

r – корневая вершина

Можно вычислять с помощью итеративных методов

for(n:N\{r})

Dom<- N

Dom(r)<-{r}

f<-true

while (f)

{

f<-true

for(n:N\{r})

T<-N

for (p:pred(n))

T crossing= Dom(p)

T <- {n} concat T

if (T != Dom(n))

f<-true

Dom(n) <- T

return Dom

Обратное доминирование:

N, Dom: N->set(N), r

for (n:N)

tmp(n) <- Dom(n)\{n}

for (n:N\{r})

for(s:tmp(n))

for(t:tmp(n))

if(t in tmp(s))

tmp(n) -= {t}

dom<-tmp

Эти алгоритмы имеют не очень хорошую временную сложность, существуют более эффективные алгоритмы:

Len\uganer-Tarjan – первый мужик, второй мужик

Работает за время, пропорционально количеству графов в ершине: o(e*alpha(e,n))

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

Классификация дуг:

1. Прямая дуга. a->b прямая, если a dom b

2. Обратная дуга: b dom a

3. Косая дуга – где первые два условия не выполняются

Для каждой дуги мы можем ввести понятие естественного цикла

Естественный цикл: пусть есть обратная дуга a->b, тогда ест цикл будет состоять из b (заголовок цикла) и всех вершин, из которых достигается a, не проходя через b

Определим понятие сильно связной компоненты:

Такой подграф G_s=<N_s, E_s>, что любая вершина достижима из любой вершины.