Введение в теорию построения оптимизирующих компиляторов, 04 лекция (от 24 октября)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1457 участника 155.207.113.95 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | <P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 24.10.06</P> |
- | + | <P STYLE="margin-bottom: 0cm"><BR> | |
- | + | </P> | |
- | + | <P STYLE="margin-bottom: 0cm">Сегодня продолжим изучение устройства | |
+ | компилятора.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Дерево внутреннего представления | ||
+ | получается из дерева разбора программы путём упрощения. Такое дерево | ||
+ | называется представлением высокоуровневым (high-level intermediate | ||
+ | representation) – parse tree. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Для чего оно нужно:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Дерево разбора удобно для | ||
+ | проведения семантического анализа. Семант анализ будет заключаться в | ||
+ | расставлении дополн ссылок. | ||
+ | </P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Кроме того, оно может подвергаться | ||
+ | некоторым перестроениям, например добавление неявных операций. Под | ||
+ | неявными операциями понимаются привидение типов, вызовы | ||
+ | конструкторов по умолчанию и т. д.</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Некоторые оптимизации начального | ||
+ | уровня, например свёртка констант.</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Function inlining</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Шаблонные подстановки, | ||
+ | Специализации шаблонов (для извращённых языков типа С++)</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Теперь это дерево хотелось бы | ||
+ | трансформировать к другому представлнию, более удобному для глубокого | ||
+ | анализа – представление среднего уровня.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Что мы хотим от представление среднего | ||
+ | уровня:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Простота представления, чтобы в | ||
+ | нём не было сложных синтаксических и семантических конструкций, | ||
+ | программы была бы разложена на элементарные операции, чтобы | ||
+ | программа представлялась на четвёрки следующего вида: результат, | ||
+ | аргумент1, операция, аргумент2. Естественно, что при переходе от | ||
+ | сложных выражений потребуется введение так называемых временных | ||
+ | переменных. Например, если есть r = a+b*c, то оно будет выглядеть | ||
+ | как t1 <- b*c; r <- a+t1. Тут потребовалось введение одной | ||
+ | временной переменной t1. Такие временные переменны мы будем называть | ||
+ | soft-register, pseudo-register, в противоположносьт hard-register.</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Сделать более явным поток | ||
+ | управления: оставить только два вида переходов – условные и | ||
+ | безусловные. В языке видов переходов достаточно много: for, While, | ||
+ | do while, goto, break, continue, return, if, switch, &&, ||, | ||
+ | long_jump, в плюсах ещё обработка исключений.</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Хотелось бы организовать области | ||
+ | видимости.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{ f(); int a; g(); } } - область после | ||
+ | объявления нужно выделять в отдельную область видимости</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Пример:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">int fib(int m)</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> int f0 = 0, f1 = 1, f2, i;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> if (m<=1) return m;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> for (i = 2; i<=m; i++)</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> {</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f2 = f0+f1;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f0=f1;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f1=f2;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> }</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> return f2;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">как это будет выглядеть во внутреннем | ||
+ | представлении:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L0: display {</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Lm: int m;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">L1: display {</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Lf0: int f0;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Lf1: int f1;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Lf2: int f2;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Li: int i;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">fib: func(L0, L1, int, @1) {</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f0 <- 0</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f1 <- 1</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> jg Lm, 1, L</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> @1 <- Lm</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> jmp __</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L2: Li <- 2</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L3: jg Li, Lm, __</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Lf2 <- Lf0 + Lf1</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Lf0 <- Lf1</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Lf1 <- Lf2</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> incr(Li, Li)</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> jmp L3</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L4: @1 <- Lf2</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L5:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Почему имена заменили на метки – | ||
+ | имена могут перекрываться, а метки уникальны.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Изменения:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Заменили имена на метки</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Разнесены объявление и | ||
+ | инициализация. Ибо место под переменные выделяется в стеке</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Заменили переходы</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Чем отличается от низкоур | ||
+ | представления:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Оперируем с именами, а не | ||
+ | регистрами</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Регистры пока абстрактнгые</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Это предст уже не зависит от языка. И | ||
+ | от платформы тоже не сильно зависит.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Что мы хотим сделать с этим | ||
+ | представлением:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Разбить на базовые блоки и | ||
+ | построить граф потока управления</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Базовый блок – последовательность | ||
+ | операций максимальной длины, которая выполняется от начала до конца, | ||
+ | внутри блока управление переходит от предыдущего оператора к | ||
+ | следующему.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">В данной программе есть точка входа в | ||
+ | функцию, которую мы обозн через entry.</P> | ||
+ | <TABLE WIDTH=100% BORDER=1 BORDERCOLOR="#000000" CELLPADDING=4 CELLSPACING=0> | ||
+ | <COL WIDTH=128*> | ||
+ | <COL WIDTH=128*> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD WIDTH=50%> | ||
+ | <P>fib: func(L0, L1, int, @1) {</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD ROWSPAN=3 WIDTH=50%> | ||
+ | <P STYLE="margin-bottom: 0cm"> f0 <- 0 | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f1 <- 1 | ||
+ | </P> | ||
+ | <P> jg Lm, 1, L</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD ROWSPAN=2 WIDTH=50%> | ||
+ | <P STYLE="margin-bottom: 0cm"> @1 <- Lm | ||
+ | </P> | ||
+ | <P> jmp __</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD WIDTH=50%> | ||
+ | <P>L2: Li <- 2</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD WIDTH=50%> | ||
+ | <P>L3: jg Li, Lm, __</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD ROWSPAN=5 WIDTH=50%> | ||
+ | <P STYLE="margin-bottom: 0cm"> Lf2 <- Lf0 + Lf1 | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Lf0 <- Lf1 | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Lf1 <- Lf2 | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"> incr(Li, Li) | ||
+ | </P> | ||
+ | <P> jmp L3</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD WIDTH=50%> | ||
+ | <P>L4: @1 <- Lf2</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR VALIGN=TOP> | ||
+ | <TD ROWSPAN=2 WIDTH=50%> | ||
+ | <P>L5: }</P> | ||
+ | </TD> | ||
+ | <TD WIDTH=50%> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | <TR> | ||
+ | <TD WIDTH=50% VALIGN=TOP> | ||
+ | <P><BR> | ||
+ | </P> | ||
+ | </TD> | ||
+ | </TR> | ||
+ | </TABLE> | ||
+ | <P STYLE="margin-bottom: 0cm">Особенность появляется, если в язые | ||
+ | поддерживаются исключения.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Try {</P> | ||
+ | <P STYLE="margin-bottom: 0cm">f();</P> | ||
+ | <P STYLE="margin-bottom: 0cm">g();</P> | ||
+ | <P STYLE="margin-bottom: 0cm">} catch() { }</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Каждую функцию надо поместить в базовый | ||
+ | блок, и разместить в нём дополнительную информацию. Переходы в | ||
+ | программе с исключениями бывают очень сложными.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Мы выделили базовые блоки, теперь можем | ||
+ | построить граф потока управления. Вершинами графа являются базовые | ||
+ | блоки.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Для чего нужен граф потока управления и | ||
+ | почему мы его строим по базовым блокам: многие методы анализа | ||
+ | программы работают , делают несколько итераций, пока какие-то | ||
+ | уравнения не сойдутся. На каждой итерации нужно просматривтаь базовый | ||
+ | блок, причём сложность метода может нелинейно расти при увеличении | ||
+ | размера базовых структур. Но базовый блок можно рассматривать как | ||
+ | одну инструкцию, и для него можно заранее просчитать некоторые | ||
+ | характеристики.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Succ(a) – множество всех базовых | ||
+ | блоков, которые следуют непосредственно за a:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">succ(a) = {x: exist a-> x}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">pred(b) = {x: exist x-> b}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Отношение доминирования:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">d dom i если любой путь из entry в i | ||
+ | проходит через d</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Какие вершины доминируют над B5:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">B1, B3, B4</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Для exit: B1</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Свойства доминирования:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Рефлексивность</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Трансфлективность</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Антисимметричность</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Это отношение частичного порядка.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Что можно делать с отношением | ||
+ | частичного порядка:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Строить дерево отношений.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">A sdom b:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">a dom b</P> | ||
+ | <P STYLE="margin-bottom: 0cm">a != b</P> | ||
+ | <P STYLE="margin-bottom: 0cm">a idom b:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">a sdom b</P> | ||
+ | <P STYLE="margin-bottom: 0cm">not exist c: c != a, c!= b</P> | ||
+ | <P STYLE="margin-bottom: 0cm">(a dom c)&(c dom b)</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Дерево доминирования:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Предком некоторой вершины будет | ||
+ | являться вершина, непосредственно доминирующая её.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Постдоминирование:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Есди в качестве начальной будем | ||
+ | рассматривать exit, и дуги развернём в обратную сторону.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">A pdom b</P> | ||
+ | <P STYLE="margin-bottom: 0cm">any путь из b в exit проходит через a</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Аналогично опред строгое и непоср | ||
+ | доминирование.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">С помощью этих переменных можно | ||
+ | выделять циклы, живые переменны, переменные которые можно двигать.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Алгоритм вычисления отношения | ||
+ | доминирования:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">N = множество вершин</P> | ||
+ | <P STYLE="margin-bottom: 0cm">pred() - отношение предшествования</P> | ||
+ | <P STYLE="margin-bottom: 0cm">pred: N -> set(N)</P> | ||
+ | <P STYLE="margin-bottom: 0cm">r – корневая вершина</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Можно вычислять с помощью итеративных | ||
+ | методов</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">for(n:N\{r})</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Dom<- N</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Dom(r)<-{r}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">f<-true</P> | ||
+ | <P STYLE="margin-bottom: 0cm">while (f)</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f<-true</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> for(n:N\{r})</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> T<-N</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> for (p:pred(n))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> T crossing= Dom(p)</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> T <- {n} concat T</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> if (T != Dom(n))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> f<-true</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> Dom(n) <- T</P> | ||
+ | <P STYLE="margin-bottom: 0cm">return Dom</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Обратное доминирование:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">N, Dom: N->set(N), r</P> | ||
+ | <P STYLE="margin-bottom: 0cm">for (n:N)</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> tmp(n) <- Dom(n)\{n}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">for (n:N\{r})</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> for(s:tmp(n))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> for(t:tmp(n))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> if(t in tmp(s))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> tmp(n) -= {t}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">dom<-tmp</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Эти алгоритмы имеют не очень хорошую | ||
+ | временную сложность, существуют более эффективные алгоритмы:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Len\uganer-Tarjan – первый мужик, | ||
+ | второй мужик</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Работает за время, пропорционально | ||
+ | количеству графов в ершине: o(e*alpha(e,n))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Теперь мы можем классифицировать дуги.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Классификация дуг:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Прямая дуга. a->b прямая, если | ||
+ | a dom b</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Обратная дуга: b dom a</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Косая дуга – где первые два | ||
+ | условия не выполняются</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Для каждой дуги мы можем ввести понятие | ||
+ | естественного цикла</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Естественный цикл: пусть есть обратная | ||
+ | дуга a->b, тогда ест цикл будет состоять из b (заголовок цикла) и | ||
+ | всех вершин, из которых достигается a, не проходя через b</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Определим понятие сильно связной | ||
+ | компоненты:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Такой подграф G<SUB>s</SUB>=<N<SUB>s</SUB>, | ||
+ | E<SUB>s</SUB>>, что любая вершина достижима из любой вершины.</P> | ||
+ | |||
+ | |||
+ | {{Введение в теорию построения оптимизирующих компиляторов}} | ||
+ | {{Lection-stub}} |
Текущая версия
Оптимизация компиляторов 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 |