Текущая версия |
Ваш текст |
Строка 1: |
Строка 1: |
- | <P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 24.10.06</P>
| + | == From Ebaums Inc to MurkLoar. == |
- | <P STYLE="margin-bottom: 0cm"><BR>
| + | We at EbaumsWorld consider you as disgrace of human race. |
- | </P>
| + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
- | <P STYLE="margin-bottom: 0cm">Сегодня продолжим изучение устройства
| + | Dig yourself a grave - you will need it. |
- | компилятора.</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}}
| + | |