Введение в теорию построения оптимизирующих компиляторов, 04 лекция (от 24 октября)
Материал из eSyr's wiki.
(Сырой текст) |
м (1 версий) |
Версия 14:42, 13 ноября 2007
Оптимизация компиляторов 24.10.06
Сегодня продолжим изучение устройства компилятора.
Дерево внутреннего представления получается из дерева разбора программы путём упрощения. Такое дерево называется представлением высокоуровневым (high-level intermediate representation) – parse tree.
Для чего оно нужно:
Дерево разбора удобно для проведения семантического анализа. Семант анализ будет заключаться в расставлении дополн ссылок.
Кроме того, оно может подвергаться некоторым перестроениям, например добавление неявных операций. Под неявными операциями понимаются привидение типов, вызовы конструкторов по умолчанию и т. д.
Некоторые оптимизации начального уровня, например свёртка констант.
Function inlining
Шаблонные подстановки, Специализации шаблонов (для извращённых языков типа С++)
Теперь это дерево хотелось бы трансформировать к другому представлнию, более удобному для глубокого анализа – представление среднего уровня.
Что мы хотим от представление среднего уровня:
Простота представления, чтобы в нём не было сложных синтаксических и семантических конструкций, программы была бы разложена на элементарные операции, чтобы программа представлялась на четвёрки следующего вида: результат, аргумент1, операция, аргумент2. Естественно, что при переходе от сложных выражений потребуется введение так называемых временных переменных. Например, если есть r = a+b*c, то оно будет выглядеть как t1 <- b*c; r <- a+t1. Тут потребовалось введение одной временной переменной t1. Такие временные переменны мы будем называть soft-register, pseudo-register, в противоположносьт hard-register.
Сделать более явным поток управления: оставить только два вида переходов – условные и безусловные. В языке видов переходов достаточно много: for, While, do while, goto, break, continue, return, if, switch, &&, ||, long_jump, в плюсах ещё обработка исключений.
Хотелось бы организовать области видимости.
{ 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:
}
Почему имена заменили на метки – имена могут перекрываться, а метки уникальны.
Изменения:
Заменили имена на метки
Разнесены объявление и инициализация. Ибо место под переменные выделяется в стеке
Заменили переходы
Чем отличается от низкоур представления:
Оперируем с именами, а не регистрами
Регистры пока абстрактнгые
Это предст уже не зависит от языка. И от платформы тоже не сильно зависит.
Что мы хотим сделать с этим представлением:
Разбить на базовые блоки и построить граф потока управления
Базовый блок – последовательность операций максимальной длины, которая выполняется от начала до конца, внутри блока управление переходит от предыдущего оператора к следующему.
В данной программе есть точка входа в функцию, которую мы обозн через entry.
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
Свойства доминирования:
Рефлексивность
Трансфлективность
Антисимметричность
Это отношение частичного порядка.
Что можно делать с отношением частичного порядка:
Строить дерево отношений.
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))
Теперь мы можем классифицировать дуги.
Классификация дуг:
Прямая дуга. a->b прямая, если a dom b
Обратная дуга: b dom a
Косая дуга – где первые два условия не выполняются
Для каждой дуги мы можем ввести понятие естественного цикла
Естественный цикл: пусть есть обратная дуга a->b, тогда ест цикл будет состоять из b (заголовок цикла) и всех вершин, из которых достигается a, не проходя через b
Определим понятие сильно связной компоненты:
Такой подграф Gs=<Ns, Es>, что любая вершина достижима из любой вершины.
Введение в теорию построения оптимизирующих компиляторов
Календарь
вт | вт | вт | вт | вт | |
Сентябрь
| 19 | 26 | |||
Октябрь
| 10 | 24 | 31 | ||
Ноябрь
| 07 | 14 | 21 | ||
Декабрь
| 05 | 12 |