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

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

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

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

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

Текущая версия Ваш текст
Строка 1: Строка 1:
-
<P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 31.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"><B>Структурный анализ</B></P>
+
-
<P STYLE="margin-bottom: 0cm">У нас есть граф потка управления. И в
+
-
результате преобразований мы сворачиваем его в граф из одной вершины.
+
-
Это делается путём изучения графа потока управления и сворачивания
+
-
отдельных частей в соотв с шаблонами. Например, есть шшаблон цикла.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">В результате (см рис 2) получим
+
-
структурный граф. Он в некоотрой степени отражает структурную
+
-
вложенность программы.</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">Пример несводимой конструкции (improper
+
-
regions): см рис 3</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Все шаблоны будут отвечать соотв
+
-
конструкциям языка. Какие могут быть шаблоны:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Два блока подряд &ndash; можно
+
-
заменить на один</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Конструкция типа if then else</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Конструкция if then</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Self loop</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">While</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Этими шаблонами моржно было бы
+
-
исчерпать паскаль.</P>
+
-
<OL START=6>
+
-
<LI><P STYLE="margin-bottom: 0cm">См. Рис 4 &ndash; сложное условие</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Паскалевый case &ndash; рис 5</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">break, Label, continue, return
+
-
порождают дополнительные ребра (см рис 6)</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Можно делать такие преобразования,
+
-
которые делают из несводимых областей сводимые (рис 7)</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">Ещё один &ndash; выделение циклов, что
+
-
будет использоваться длоя дальнейшей оптимизации.</P>
+
-
<P STYLE="margin-bottom: 0cm">Третье, для чего нужен структ анализ &ndash;
+
-
одна из задач анализа &ndash; выявление потока данных, современные
+
-
алгоритмы работают на графе потока управления, и работают итертивыно.
+
-
Если мы строим дерево упр конструкций, то мы можем использовать не
+
-
итеративные алгоритмы, а те, которые учитывают структуру графа, и
+
-
сложность у них меньше.</P>
+
-
<P STYLE="margin-bottom: 0cm">Четвёртое &ndash; для поддержки
+
-
инкрементальных изменений.</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">Дерево разбора &ndash; внутренне
+
-
представление &ndash; граф потока управления &ndash; структурные
+
-
конструкции. Это позволяет находить больше структурнрых конструкций.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Control flow analysis</P>
+
-
<P STYLE="margin-bottom: 0cm">Следующий этап:</P>
+
-
<P STYLE="margin-bottom: 0cm">Data flow analysis</P>
+
-
<P STYLE="margin-bottom: 0cm">Вычисляются некторые зависимости между
+
-
элементами программы. Задача DFA &ndash; вычисление некоторых фактов
+
-
о взаимосвязи переменных и значений в программе. Потом эти факты
+
-
используются при оптимизации. Пример:</P>
+
-
<P STYLE="margin-bottom: 0cm">По всей программе рассматриваем
+
-
конструкции вида a op b. Например, если далее по тексту есть a op b,
+
-
и ни a, ни b не меняется, то она даст тот же результат. Это позволяет
+
-
ввести времпенную переменную и использовать её потом. Такое
+
-
преобразование называется common subexpretion elimination (CSE).
+
-
Понятно, что такие преобразования могут идти каскадом. Таким образом
+
-
мы можем сворачивать не только минимальные операции, но и большие
+
-
операции. Например, перемножение матриц:</P>
+
-
<P STYLE="margin-bottom: 0cm">a[i][j]+=b[i][k]*c[k][j] &ndash;
+
-
внутренний цикл. Тут будет вычисление i-й строки.</P>
+
-
<P STYLE="margin-bottom: 0cm">Или:</P>
+
-
<P STYLE="margin-bottom: 0cm">a[i][j][k]=b[i][j][k] &ndash; считать
+
-
смещение можно только один раз.</P>
+
-
<P STYLE="margin-bottom: 0cm">Три группы методом преобразования:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Локальные &ndash; работают в
+
-
пределах базового блока. Можно сделать за один проход.</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Глобальные &ndash; применяются ко
+
-
всему телу процедуры или функции</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Межпроцедурный &ndash; применяется
+
-
ко всей программе в совокупности</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Первые два класса методов хорошо
+
-
изучены и применяются в каждом уважающем себя компиляторе.
+
-
Межпроцедурных преобразований ни у кого нет. При переходе от глоб к
+
-
межпроц идёт такой скачок сложности и требований к памяти, что делает
+
-
их бесполезными.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Задача о достигающих определениях
+
-
(reaching definition)</P>
+
-
<P STYLE="margin-bottom: 0cm">Достижение (определение) &ndash;
+
-
присваивание некоторого значения.</P>
+
-
<P STYLE="margin-bottom: 0cm">I1: a&lt;- expr</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">i2:</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">орпределние i1 достигает i2, если
+
-
существует путь, в котором переменная не переприсваивается. Таким
+
-
образом для каждой точки программы можно найти множество достигающих
+
-
определений. [&lt;a, i2&gt;, &lt;a, i3&gt;, &lt;b, i4&gt;, ...} -
+
-
таким образом, можно рештиь задачу о достигающих определениях.</P>
+
-
<P STYLE="margin-bottom: 0cm">Рассмотрим эту задачу для одного
+
-
базового блока. (local reaching definition)</P>
+
-
<P STYLE="margin-bottom: 0cm">В рамках одного блока путь
+
-
единственный. Что может быть:</P>
+
-
<P STYLE="margin-bottom: 0cm">Заведём рабочее множество достигающих
+
-
определений. W={}</P>
+
-
<P STYLE="margin-bottom: 0cm">Предположим, что мы пришли к некоторой
+
-
инструкции, и на входе множество W<SUB>in</SUB>. Теперь мы хотим
+
-
псчитать W<SUB>out</SUB>. Инструкции у нас следующего вида &ndash;
+
-
есть переменные, которым присваиваются и некоторое выражение. Как
+
-
будет модифицироваться множество w при прохождении через данную
+
-
инструкцию? Первое &ndash; выуинуть те переменные, которым
+
-
присваиваются значения (множество KILL): Wout = (Win \ KILL<SUB>i</SUB>).
+
-
После этого мы должны добавить множество определений, которые
+
-
порождаются в этой инструкции (GEN): Wout = (Win \ KILLi) объединить
+
-
с GENi. Поскольку путь один, перемещаемся от инструкции к инструкции.
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">W<SUB>in</SUB><SUP>(i+1)</SUP> =
+
-
W<SUB>out</SUB><SUP>(i)</SUP></P>
+
-
<P STYLE="margin-bottom: 0cm">Wout(i) = FLOW<SUB>i</SUB>(Win(i)) &ndash;
+
-
функция потока</P>
+
-
<P STYLE="margin-bottom: 0cm">Система уравнений называется уравнением
+
-
потока. Поскольку у нас базовы блок, то решать это уравнением мы
+
-
можем за один поток. Более того, мы можем вычислить функцию для всего
+
-
блока: Wout = FLOW<SUB>B</SUB>(W<SUB>in</SUB>). Можно рассм базовый
+
-
блок как одну сложную инструкцию. Таким образом, мы можем решать
+
-
задачу о достигающих определений для одного блока.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm"><B>Global reaching defs</B></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">Появление точек слияния &ndash;
+
-
когда нескоьлко блоков передают управление в один. Такую точку
+
-
обозначим как JOIN. Для функцци достигающих определений в точке
+
-
слияния м множества объединяем.</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Теперь мы можем выписать по аналогии
+
-
выписать уравнение потока данных.</P>
+
-
<P STYLE="margin-bottom: 0cm">(расписывается уравнение для B4)</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Метод простой итерации</P>
+
-
<OL START=0>
+
-
<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"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">f=true;</P>
+
-
<P STYLE="margin-bottom: 0cm">while(f) {</P>
+
-
<P STYLE="margin-bottom: 0cm">f = false;</P>
+
-
<P STYLE="margin-bottom: 0cm">(считаем Wk(i))</P>
+
-
<P STYLE="margin-bottom: 0cm">if (Wk(i) !=Wk(i-1)) f=true;</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">Скорость &ndash; зависит от структуры
+
-
программы.</P>
+
-
<P STYLE="margin-bottom: 0cm">Свойства такого анализа:</P>
+
-
<P STYLE="margin-bottom: 0cm">Алгоритм решения итеративный:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Прямой (forward)</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Обратный (backward)</P>
+
-
</OL>
+
-
<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">У нас есть, когда мы рассч достигающее
+
-
определение, у нас есть пра перменная-точка в программе. У нас есть
+
-
для всей функции полное множество этих точек. Мы поступим следующим
+
-
образом &ndash; каждой точке программы поставим в соотв один бит:</P>
+
-
<P STYLE="margin-bottom: 0cm">&lt;a, 1&gt; &lt;b, 2&gt; &lt;a, 3&gt;
+
-
&lt;a, 5&gt; - для хранения информации достаточно 5 бит. Теперь, если
+
-
мы рассмотрим функцию потока, то она сведётся к набору битовых
+
-
операции. В частности, нам нужно сначала выбросить убиваемые, то есть
+
-
логическое и, а потом объединяем с множеством новых опред &ndash;
+
-
логическое или. Таким образом, задача о нахажд множество дост опред
+
-
свелась к операциями над битами в числе.</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_05_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_31_%D0%BE%D0%BA%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29
Личные инструменты
Разделы