Редактирование: Введение в теорию построения оптимизирующих компиляторов, 06 лекция (от 07 ноября)

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 1: Строка 1:
-
<P STYLE="margin-bottom: 0cm">Чернов 07.11.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">Reaching definitions</P>
+
Dig yourself a grave - you will need it.
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">worklist &ndash; список необработанных
+
-
вершин</P>
+
-
<P STYLE="margin-bottom: 0cm">На 0й итерации в worklist записываем
+
-
все вершины.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">WL &lt;- V</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">while (WL!=0)</P>
+
-
<P STYLE="margin-bottom: 0cm"> v &lt;- get(WL)</P>
+
-
<P STYLE="margin-bottom: 0cm"> out'<SUB>v</SUB> = FLOW<SUB>v</SUB>(объединение
+
-
по всем w принадлежащим pred(v) out<SUB>w</SUB>)</P>
+
-
<P STYLE="margin-bottom: 0cm"> if (out'<SUB>v</SUB>!=out<SUB>v</SUB>)
+
-
WL &lt;-WL объединить с succ(v)</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">Таким образом для каждой точки
+
-
программы насчитываем множество достигающих определений.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<TABLE WIDTH=100% BORDER=1 BORDERCOLOR="#000000" CELLPADDING=4 CELLSPACING=0>
+
-
<COL WIDTH=64*>
+
-
<COL WIDTH=64*>
+
-
<COL WIDTH=128*>
+
-
<THEAD>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>0</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>Func fib(m)</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
</THEAD>
+
-
<TBODY>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>1</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>f0 &lt;- 0</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>2</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>f1 &lt;- 1</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>3</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>if m &gt; 1 goto L3</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>4</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>@1 &lt;- m</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>5</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>goto L2</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>6</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>L1: if i&lt;=m goto L3</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>7</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>@1 &lt;= f2</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>8</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>goto L2</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>9</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>L3: f2 &lt;- f0+1</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>10</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>f0 &lt;- f1</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>11</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>f1 &lt;- f2</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>12</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>i &lt;- i+1</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>13</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>goto L1</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=25%>
+
-
<P>14</P>
+
-
</TD>
+
-
<TD WIDTH=25%>
+
-
<P>L2: return @1</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
</TBODY>
+
-
</TABLE>
+
-
<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">Du-chains</P>
+
-
<P STYLE="margin-bottom: 0cm">ud-chains</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">use-def chain</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">В ud-цепочке будут храниться
+
-
достигающие определения. Для f1 в 12 это будет 10 и 2.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">du-цепочка &ndash; обратная цепочка &ndash;
+
-
def-use цепочка. Мы делаем наоборот. Для каждого, например, берём
+
-
какое-нибудь определение, например, определение переменной f0, и для
+
-
каждого определения строим, и она будет состоять из использования её
+
-
в 9 инстр. Для m это 3, 4, 6. То есть если ud-цепочка это отображения
+
-
точек исп в точки определния, то ду &ndash; обратная.
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Du-ud-chains &ndash; один из исп
+
-
методов хранения инф.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Анализ достигающих опред относится к
+
-
прямым итеративным методам. Теперь рассмотр пример обратного метода &ndash;
+
-
обратный анализ потоков данных.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Live variables</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Пусть есть переменная в программе, и
+
-
точка в программе. &lt;v, i&gt;</P>
+
-
<P STYLE="margin-bottom: 0cm">Задача о живых перем сост след образом.
+
-
Для данной пары определить, есть ли оспользование данной переменной
+
-
на пути следования в данную точку.
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Предп, эта переменная занимает регистр
+
-
процессора, хранится на некотором регистре процессора. Если анализ
+
-
живых перем показал, что она далее нигде не исп, то это означает, что
+
-
регистр мы можем использовтаь для других целей, и освободить его под
+
-
другие переменные. Решение задачи необх для качественного распред
+
-
регистров, мы распред регитры на то время, когда она используется.
+
-
Такая задача часто возн для счётчиков перем циклов. Например, етсь
+
-
цикл по i:</P>
+
-
<P STYLE="margin-bottom: 0cm">for (i=...) {...}</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">for (j=...) {...}</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">В рамках цикла логично поместить i на
+
-
регистр, но потом она пересстаёт быть живой и на тот же самый регистр
+
-
можно поместить j. В результате уменьш давление на регистр, уменьш
+
-
требование к регистрам, что вообще хорошо.
+
-
</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"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Вершина exit &ndash; 14 инструкция, где
+
-
возвращ регистр @1. На exit информация о живых переменных не
+
-
определена. На входе в return живой будет переменная @1. То есть,
+
-
вообще говоря, в точке, предшевствующей оператор return, то эта
+
-
переменная живая. В вершиеу exit есть несколько переходовЖ из инстр 4
+
-
и из инстр 7. На выходе множество живых переменных состоит из @1&#8203;
+
-
Рассм каждую инстр. Рассм каждую инстр. Что будет на входе. Очевидно,
+
-
что @1 не будет жив выше 7, и выше 4. Но вместо него мы должны потр,
+
-
чтобы переменная f2 и m были живыми, соотв. То есть определна
+
-
переменная потока, которая из out получает in. Чему она равна. Нам
+
-
нужно ихз множ живых перем выкинуть перем, которые переприсв в данной
+
-
точке и добавить к множ живых перем множ используемых:
+
-
FLOWi(OUTi)=OUTi\GENi объединить с USEi. Мы можем свести упр всей
+
-
программы к графу потока упрЮ на каждом графе можно посчитать FLOW, и
+
-
у нас в резте появится некоторое уравнение потоков данных для решения
+
-
задачи о живых переменных.</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">OUTi=Inj объединение с Ink</P>
+
-
<P STYLE="margin-bottom: 0cm">OUTi = объединение по всем послед
+
-
вершинам i j=succ(i) Inj</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">После того, как мы решили задачу, будет
+
-
насчитанно множество всех переменных, которыне являются живыми. И
+
-
если некрая переменная не является живой, то мы можем регистр от неё
+
-
освободить.</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">Теория решёток (lattice)</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Решётка &ndash; неекая алгебр
+
-
структура, опред множеством элементов произв природы и две операции.
+
-
Первую опреацию обозначю таким образом П, такую - таким образом |_|.
+
-
Первая называется meet, вторую &ndash; join. Эти опреации определны
+
-
на всём множестве элементов решётки.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Любое x, y принадлежит L: существует
+
-
единств u? Z: u = x П y, z = x |_| y</P>
+
-
<P STYLE="margin-bottom: 0cm">Требования:</P>
+
-
<P STYLE="margin-bottom: 0cm">1. Коммутативеость</P>
+
-
<P STYLE="margin-bottom: 0cm">x П y = y П x</P>
+
-
<P STYLE="margin-bottom: 0cm">x |_| y = y |_| x</P>
+
-
<OL START=2>
+
-
<LI><P STYLE="margin-bottom: 0cm">Ассоциативность</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">(x П y) П z = x П (y П z)</P>
+
-
<P STYLE="margin-bottom: 0cm">(x |_| y) |_| z = x |_| (y |_| z)</P>
+
-
<OL START=3>
+
-
<LI><P STYLE="margin-bottom: 0cm">Наличие двух выделенных элементов
+
-
&ndash; inf и sup</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">_|_ - bottom</P>
+
-
<P STYLE="margin-bottom: 0cm">T &ndash; top</P>
+
-
<P STYLE="margin-bottom: 0cm">x П _|_ = _|_</P>
+
-
<P STYLE="margin-bottom: 0cm">x |_| T = T</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Поскольку дополн даны дистриб свойства,
+
-
то говорят о дистриб решётках.</P>
+
-
<P STYLE="margin-bottom: 0cm">Если выполн</P>
+
-
<P STYLE="margin-bottom: 0cm">(x П y) |_| z = (x |_| y) П (y |_| z)</P>
+
-
<P STYLE="margin-bottom: 0cm">(x |_| y) П z = (x П y) |_| (y П z)</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">BV3 &ndash; битовые вектора длины 3</P>
+
-
<P STYLE="margin-bottom: 0cm">meet П - &amp;</P>
+
-
<P STYLE="margin-bottom: 0cm">join |_| - |</P>
+
-
<P STYLE="margin-bottom: 0cm">_|_ = &lt;000&gt;</P>
+
-
<P STYLE="margin-bottom: 0cm">T = &lt;111&gt;</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">Операции meet и join индуцируют
+
-
частичный порядок. А именно, мы можем ввести отношение частичного
+
-
порядка т и тт, когда их joiun будет давать один из эл-тов:</P>
+
-
<P STYLE="margin-bottom: 0cm">x квадратик без правой стороны с
+
-
двойной нижней y &lt;=&gt; x П y = x</P>
+
-
<P STYLE="margin-bottom: 0cm">x квадратик без левой стороны с двойной
+
-
нижней y &lt;=&gt; x |_| y = x</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Поскольку есть отн частичного порядка,
+
-
мы можем ввести понятие высоты решётки, а именно:</P>
+
-
<P STYLE="margin-bottom: 0cm">v<SUB>0</SUB> = _|_ -&gt; v<SUB>1</SUB>
+
-
-&gt; v<SUB>2</SUB> -&gt; ... -&gt; v<SUB>n-1</SUB> -&gt; T = v<SUB>n</SUB></P>
+
-
<P STYLE="margin-bottom: 0cm">причем v<SUB>i</SUB> квадратик без
+
-
правой стороны с двойной нижней v<SUB>i+1</SUB></P>
+
-
<P STYLE="margin-bottom: 0cm">n &ndash; высота решётки</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Если есть некая ф-ция в них самих, то
+
-
мы можем ставить задачу о неподвиж точке на решётке, то есть x0
+
-
такое, что x0 = f(x0). Потребуем, чтобы f была монотонной, то есть
+
-
для любого x: f(x) квадратик без левой стороны с двойной нижней x, Мы
+
-
можем ввести понятие эффективной высоты решётки относительно f. Что
+
-
это такое. Ну, как. Через n-кратное применение f мы обозначим</P>
+
-
<P STYLE="margin-bottom: 0cm">f<SUP>(0)</SUP>(x)=x</P>
+
-
<P STYLE="margin-bottom: 0cm">f<SUP>(i)</SUP>(x)=f(f<SUP>(i-1)</SUP>(x))</P>
+
-
<P STYLE="margin-bottom: 0cm">x0 квадратик без правой стороны с
+
-
двойной нижней f(x0) квадратик без правой стороны с двойной нижней
+
-
f<SUP>(2)</SUP>(x0) квадратик без правой стороны с двойной нижней
+
-
... квадратик без правой стороны с двойной нижней f<SUP>(k)</SUP>(x0)
+
-
= f<SUP>(k+1)</SUP>(x0)</P>
+
-
<P STYLE="margin-bottom: 0cm">max по x0 (min по k) &ndash;
+
-
эффективнаЯ высота решётки.</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">В чём смысл f. Если мы рассм задачу
+
-
анализа потоков данных, то мы увидим, что имели дело с решётками, По
+
-
сути, мы имели дело с решётками битовых векторов некрого размера BVn,
+
-
мы использовали join и meet и f &ndash; некоторая функция потока. И
+
-
для задачи достиг опред, и для живых перем функция монотонна.
+
-
Следовательно, время работы будет оцениваться эффект высотой решётке.
+
-
А в следствие того, что эфф высота оценивается просто высотой, а
+
-
высота равна n. Мы получаем, что для реш задач нам нужно проделать не
+
-
бдолее n итераций. Таким образом, мы можем достаточно грубо оценить
+
-
сверху время работы алгоритма.</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">Пусть у нас есть неуий нграф потока
+
-
управления. (рисует баянистый граф)</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Нам нужно найте все вектора
+
-
meet-over-all-path solution. Фикс базовый блок. В этот блок ведёт
+
-
некоторое количество путей. Соотв, на каждом из этих путей мы можем
+
-
насчитать некоторое множество In<SUB>p1</SUB> на нашем пути. Рассм
+
-
другое множество, насчитаем In<SUB>p2</SUB> ... In<SUB>pk</SUB>. Как
+
-
нам теперь получить решение задачи потоков данных? Нам нужно будет
+
-
взять минимум этих решений.
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">In = П по p:entry -&gt; B<SUB>5</SUB>
+
-
Inp</P>
+
-
<P STYLE="margin-bottom: 0cm">То эсть это практически невозможно.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">То, что мы делали в прошлый раз &ndash;
+
-
находили макс решение неподвиж точки &ndash; maximum-fixed point
+
-
solution.
+
-
</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">f &ndash; дистрибутивная</P>
+
-
<P STYLE="margin-bottom: 0cm">L &ndash; монотонная</P>
+
-
<P STYLE="margin-bottom: 0cm">тогда MFP-solution = MOP-solution
+
-
(минимума по всем путям)</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">Можем в качестве пример рассм решётку о
+
-
продвижении констант &ndash; constant propagation</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">Решётка будет выглядить след образом.
+
-
Предп, что рассм булевские и целые значения. Явные элементы top <SUB>
+
-
</SUB>и bottom:</P>
+
-
<P STYLE="margin-bottom: 0cm">T &ndash; переопределённость &ndash;
+
-
значение переменной константа, но какая, мы не знаем.</P>
+
-
<P STYLE="margin-bottom: 0cm">/ | \</P>
+
-
<P STYLE="margin-bottom: 0cm">... -2 -1 false 0 true 1 2 ...</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">Для этой решётки свойство дистриб не
+
-
выполняется.
+
-
</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"><BR>
+
-
</P>
+
-
 
+
-
 
+
-
{{Введение в теорию построения оптимизирующих компиляторов}}
+
-
{{Lection-stub}}
+

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_06_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_07_%D0%BD%D0%BE%D1%8F%D0%B1%D1%80%D1%8F%29
Личные инструменты
Разделы