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

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

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

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

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

Описание изменений:

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

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

Получено с http://esyr.us/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_08_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_21_%D0%BD%D0%BE%D1%8F%D0%B1%D1%80%D1%8F%29

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-<P STYLE="margin-bottom: 0cm">Чернов, 21.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">Расстановка поколений переменных.</P>
+Dig yourself a grave - you will need it.
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">Определние границ доминир</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">Когда мы обрабатываем очередной базовый
-блок, мы просматриваем каждую исходящую дугу, и проставляем поколение
-в соотв со стеком. Нам нужен счётчик поколений и стек поколений.</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">Init</P>
-<P STYLE="margin-bottom: 0cm">  foreach a принадлежит Vans</P>
-<P STYLE="margin-bottom: 0cm">    count[a] &lt;- 0</P>
-<P STYLE="margin-bottom: 0cm">    stack[a] &lt;- empty</P>
-<P STYLE="margin-bottom: 0cm">    stack[a].push(0)</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">Rename(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">Rename(n)</P>
-<P STYLE="margin-bottom: 0cm">  foreach s принадлежит stmt(n)</P>
-<P STYLE="margin-bottom: 0cm">    if s != фи-финкция</P>
-<P STYLE="margin-bottom: 0cm">      foreach x принадлежит use(s)</P>
-<P STYLE="margin-bottom: 0cm">        i &lt;- stack[x].top()</P>
-<P STYLE="margin-bottom: 0cm">        заменить x на x<SUB>i</SUB></P>
-<P STYLE="margin-bottom: 0cm">    foreach a принадлежит defs(s)</P>
-<P STYLE="margin-bottom: 0cm">      count[a]++</P>
-<P STYLE="margin-bottom: 0cm">      i &lt;- count[a]</P>
-<P STYLE="margin-bottom: 0cm">      stack[a].push(i)</P>
-<P STYLE="margin-bottom: 0cm">      заменить a на a<SUB>i</SUB></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">foreach y принадлежит succ(n)</P>
-<P STYLE="margin-bottom: 0cm">  пусть n &ndash; j-й предш. для y</P>
-<P STYLE="margin-bottom: 0cm">  foreach фи принадлежит фи-функция(y)</P>
-<P STYLE="margin-bottom: 0cm">    пусть a- j-й операнд</P>
-<P STYLE="margin-bottom: 0cm">    i &lt;- stack[a].top()</P>
-<P STYLE="margin-bottom: 0cm">    заменить а на a<SUB>i</SUB></P>
-<P STYLE="margin-bottom: 0cm">for x принадлежит child(n)</P>
-<P STYLE="margin-bottom: 0cm">  Rename(x)</P>
-<P STYLE="margin-bottom: 0cm">//ну и последнее, совсем последнее &ndash;
-почистить стек</P>
-<P STYLE="margin-bottom: 0cm">foreach s прниадлежит stmt(n)</P>
-<P STYLE="margin-bottom: 0cm">  foreach a принадлежит def(j)</P>
-<P STYLE="margin-bottom: 0cm">    stack[a].pop();</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">проблемы:</P>
-<OL>
-	<LI><P STYLE="margin-bottom: 0cm">когда возникают перекрывающиеся
-	интервалы жизни переменных (требуется edge splitting)</P>
-	<LI><P STYLE="margin-bottom: 0cm">Параллельна янатура всех
-	фи-присваиваний &ndash; все фи-присв одновременны</P>
-	<LI><P STYLE="margin-bottom: 0cm">Нарушение границ доминирования<BR><BR>
-	</P>
-</OL>
-<P STYLE="margin-bottom: 0cm">Распределение регистров</P>
-<OL>
-	<LI><P STYLE="margin-bottom: 0cm">register allocation</P>
-	<LI><P STYLE="margin-bottom: 0cm">register assignment</P>
-</OL>
-<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">Какие переменные не могут одновременно
-помещены на регистр &ndash; которые одновременно живы.Каждую
-переменную, которая исп. в программе, представляем вершиной графа.
-Регистры также предст. вершинами. Если две переменные одновременно не
-являются живыми, то мы их соединяем. Такой граф называется графом
-наложений.</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">Теперь поставим в соотв регистру цвет.
-Соответственно, две перем не могут иметь одного цвета. Эта задача
-широко известна &ndash; задача о раскраске графа. Нас интересует
-раскраска с мин. количеством цветов. Это NP-полная задача. Тем не
-менее, можно применять эфристики.</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">Поэтому распред регистров лучше вести
-для сетей (web)</P>
-<P STYLE="margin-bottom: 0cm">Что такое сеть &ndash; предположим, что
-есть построенные du-цепочки (можно обобщитьна SSA). Пусть есть опред
-x, от него есть ссылки на места использования. У этого использования
-есть, возможно на него ссылкаются другие определения. Соответственно,
-максимальная компонента и будет являться сетью.</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">(я прослушал, как он звучит :( Похоже,
-что надо смотреть только на точки определения)</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">В соответствии с ним гв графе будут
-только два ребра, соед а1  а2 и b1 b2.</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">Для преобр. графа можно склеивать
-регистры (<SPAN LANG="en-US">register</SPAN> <SPAN LANG="en-US">coalescing</SPAN>)</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">ai &lt;- aj</P>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<OL>
-	<LI><P STYLE="margin-bottom: 0cm">Либо ai и aj не накладываются друг
-	на друга, либо они не исп. от текущей точки до конца функции. В этом
-	случае их можно склеить</P>
-	<P STYLE="margin-bottom: 0cm">=&gt; def ai -&gt; def aj удаляем ai
-	&lt;- aj</P>
-</OL>
-<P STYLE="margin-bottom: 0cm"><BR>
-</P>
-<P STYLE="margin-bottom: 0cm">Склецйка регистров:</P>
-<OL>
-	<LI><P STYLE="margin-bottom: 0cm">Выполняем edge splitting</P>
-	<LI><P STYLE="margin-bottom: 0cm"><IMG SRC="CO_06_11_21_html_528d24d7.gif" ALIGN=LEFT>a3=a1
-	    a3=a2</P>
-	<LI><P STYLE="margin-bottom: 0cm"><IMG SRC="CO_06_11_21_html_70a6898f.gif" ALIGN=LEFT><IMG SRC="CO_06_11_21_html_m3a7159c4.gif" ALIGN=LEFT>
-	                          В резульатте появляется множество лишних
-	копирований, что может поставить под вопрос саму целесообразность
-	преобразования.</P>
-</OL>
-<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">Пусть у нас есть R регистров</P>
-<OL>
-	<LI><P STYLE="margin-bottom: 0cm">Вершины степени меньше R &ndash;
-	всегда могут быть раскрашены, выкидываем их, так можно удалять, пока
-	не останутя только вершины степени больше равно R</P>
-	<P STYLE="margin-bottom: 0cm">2. Найдём произв узел со степенью
-	больше равно R, найдём ту, для которой отношение стоимости сброса к
-	её степени минимальна. Стоимость сброса &ndash; то, насколько плохо
-	запихивать переменную в память.Такую вершину мы, как и все со
-	степенью меньше R помещаем в стек. Это мы делаем, пока граф не
-	опустошится. 3. Теперь их будем выимать и назначать цвета. Если
-	назначили, то всё хорошо, если же нет, то в опред момент появляется
-	переменная, которая становится кандидатом на сброс.</P>
-	<P STYLE="margin-bottom: 0cm">В чё мзаключается сброс (spill).
-	</P>
-	<P STYLE="margin-bottom: 0cm"></P>
-</OL>
-{{Введение в теорию построения оптимизирующих компиляторов}}
-{{Lection-stub}}