Текущая версия |
Ваш текст |
Строка 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">Если граф удаётся свернуть, тто он
| + | |
- | считается сводимым. Если нет – несводимым.</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">Два блока подряд – можно
| + | |
- | заменить на один</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 – сложное условие</P>
| + | |
- | <LI><P STYLE="margin-bottom: 0cm">Паскалевый case – рис 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">Ещё один – выделение циклов, что
| + | |
- | будет использоваться длоя дальнейшей оптимизации.</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">Дерево разбора – внутренне
| + | |
- | представление – граф потока управления – структурные
| + | |
- | конструкции. Это позволяет находить больше структурнрых конструкций.</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 – вычисление некоторых фактов
| + | |
- | о взаимосвязи переменных и значений в программе. Потом эти факты
| + | |
- | используются при оптимизации. Пример:</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] –
| + | |
- | внутренний цикл. Тут будет вычисление i-й строки.</P>
| + | |
- | <P STYLE="margin-bottom: 0cm">Или:</P>
| + | |
- | <P STYLE="margin-bottom: 0cm">a[i][j][k]=b[i][j][k] – считать
| + | |
- | смещение можно только один раз.</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"><BR>
| + | |
- | </P>
| + | |
- | <P STYLE="margin-bottom: 0cm">Задача о достигающих определениях
| + | |
- | (reaching definition)</P>
| + | |
- | <P STYLE="margin-bottom: 0cm">Достижение (определение) –
| + | |
- | присваивание некоторого значения.</P>
| + | |
- | <P STYLE="margin-bottom: 0cm">I1: a<- 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, если
| + | |
- | существует путь, в котором переменная не переприсваивается. Таким
| + | |
- | образом для каждой точки программы можно найти множество достигающих
| + | |
- | определений. [<a, i2>, <a, i3>, <b, i4>, ...} -
| + | |
- | таким образом, можно рештиь задачу о достигающих определениях.</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>. Инструкции у нас следующего вида –
| + | |
- | есть переменные, которым присваиваются и некоторое выражение. Как
| + | |
- | будет модифицироваться множество w при прохождении через данную
| + | |
- | инструкцию? Первое – выуинуть те переменные, которым
| + | |
- | присваиваются значения (множество 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)) –
| + | |
- | функция потока</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">Появление точек слияния –
| + | |
- | когда нескоьлко блоков передают управление в один. Такую точку
| + | |
- | обозначим как 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">Скорость – зависит от структуры
| + | |
- | программы.</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">У нас есть, когда мы рассч достигающее
| + | |
- | определение, у нас есть пра перменная-точка в программе. У нас есть
| + | |
- | для всей функции полное множество этих точек. Мы поступим следующим
| + | |
- | образом – каждой точке программы поставим в соотв один бит:</P>
| + | |
- | <P STYLE="margin-bottom: 0cm"><a, 1> <b, 2> <a, 3>
| + | |
- | <a, 5> - для хранения информации достаточно 5 бит. Теперь, если
| + | |
- | мы рассмотрим функцию потока, то она сведётся к набору битовых
| + | |
- | операции. В частности, нам нужно сначала выбросить убиваемые, то есть
| + | |
- | логическое и, а потом объединяем с множеством новых опред –
| + | |
- | логическое или. Таким образом, задача о нахажд множество дост опред
| + | |
- | свелась к операциями над битами в числе.</P>
| + | |
- | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
- | </P>
| + | |
- | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
- | </P>
| + | |
- | | + | |
- | | + | |
- | {{Введение в теорию построения оптимизирующих компиляторов}}
| + | |
- | {{Lection-stub}}
| + | |