Тема 05(2016)Машинно-независимая оптимизация (Лекции), страница 2

Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно циклаАлгоритм:1. Перед заголовком цикла вставить пустой базовый блок(будущий предзаголовок).Для всех инструкций в теле цикла:2. Отметить как инвариантные все операнды-константы3. Отметить как инвариантные все операнды, у которых всеопределения, достигающие инструкции, находятся вне цикла4.

Отметить как инвариантные все инструкции, все операндыкоторых отмечены5. Повторять шаги 2 – 4, пока инвариантные инструкции неперестанут выделяться6. Переместить все выделенные инструкции в предзаголовок.295.2. Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно циклаB1 b2i1B2 if(i>100) B3B4 da+d B5 dced+1fd+1B6ab+1c2if(i%2=0)EntryB1ii+1if(a<2)B2Исходный циклB3B4B5B6Exit305.2. Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно циклаB1 b2i1B2 if(i>100) B2EntryB3 ab+1c2if(i%2=0)B4 da+d B5 dced+1fd+1B1B6B2ii+1if(a<2)B2После добавления предзаголовка (B2)B3B4B5B6Exit315.2. Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно циклаB1 b2i1B2 if(i>100) B2EntryB3 ab+1c2if(i%2=0)B4 da+d B5 dced+1fd+1B1B6B2ii+1if(a<2)B2Выделение инвариантных инструкций:операнды-константы отмечены зеленымцветомоперанды, определенные вне цикла –коричневым цветоминвариантные инструкции подчеркнутыB3B4B5B6Exit325.2.

Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно циклаB1b2i1B2B3Entryif(i>100) B2 ab+1c2t1a<2if(i%2=0)B4 da+d B5 dced+1fd+1B6B1ii+1if(t1)B2После вынесения инвариантного кода впредзаголовокB2B3B4B5B6Exit335.3. Исключение бесполезного кода5.3.1 Постановка задачиПрограмма может содержать бесполезный код – инструкции,не влияющие на результат вычислений. Как правило, бесполезныйкод появляется в программе в результате работы некоторыхалгоритмов анализа и оптимизации, реализованных вкомпиляторе.Существует несколько разновидностей бесполезного кода:Мертвый код – инструкции, результат которыхне используется в дальнейших вычислениях.Недостижимый код – инструкции, которыене содержатся ни в одном реальном пути выполнения.Избыточный код – инструкции, повторно вычисляющиеуже вычисленные значения (например, доступныевыражения или инвариантные вычисления в циклах).Требуется обнаружить и удалить бесполезный код345.3.

Исключение бесполезного кода5.3.2 Алгоритм Mark & Sweep.Алгоритм Mark & Sweep (двухпроходный), применяющийся дляосвобождения динамической памяти в сборщиках мусора, можетиспользоваться и для исключения бесполезного кода.Инструкция называется полезной, если она:вычисляет возвращаемое значение процедурыявляется обращением к функции ввода-выводавычисляет значение глобальной переменной, доступнойиз других процедурее результат используется в других полезных инструкциях.Алгоритм состоит из двух проходов:на первом проходе (Mark) выявляются и помечаютсяполезные инструкции.на втором проходе (Sweep) непомеченные инструкцииудаляются.355.3.

Исключение бесполезного кода5.3.3 Поток управления: переходы и ветвления.При удалении бесполезных инструкций необходимо учитыватьпоток управления.Поток управления определяется с помощью инструкций перехода.В промежуточном представлении определено два видаинструкций перехода:переходы (jump) – инструкция goto (безусловныйпереход).ветвления (branch) – инструкции условного переходаifTrue x goto L и ifFalse x goto L,используемые для отображения в промежуточноепредставление операторов if-then,if-then-else, switch исходного языка.Для описания потока управления понадобится понятиезависимости по управлению.365.3.

Исключение бесполезного кода5.3.4 ПостдоминаторыОбратным графом ориентированного графа G = N, Eназывается ориентированный граф GR = N, ER, у которогонаправления всех ребер противоположны.В ГПУ вершина p является постдоминатором вершины n(p = Postdom (n) ) , если каждый путь из вершины n в вершинуexit проходит через вершину p.Постдоминаторы ГПУ – это доминаторы его обратного графа.Обратная граница доминирования (RDF(n)) вершины n  Gэто обычная граница доминирования в обратном графе GR.375.3. Исключение бесполезного кода5.3.5 Зависимость по управлению.По определению, вершина m ГПУ зависит по управлению отвершины n тогда, и только тогда, когда:существует непустой путь T от n до m, такой чтоk  T – {n}: m = Postdom(k), т.е. если выполнениепрограммы пошло по пути T, то, чтобы достичь exit,оно обязательно пройдет через m.m не обязательно является строгим постдоминатором n:у n может быть несколько выходов, так что помимо Tвозможны и другие пути, проходящие через n, но потомведущие не в m, а в другие вершины.Обратная граница доминирования позволяет определять границызависимостей по управлению.385.3.

Исключение бесполезного кода5.3.6. Проход Mark.На первом проходе (Mark) в каждом базовом блоке n:выбирается очередная инструкция из Worklistдля этой инструкцииудаляется ее пометка, так как Worklist содержиттолько помеченные инструкциис помощью специальной процедуры выясняетсяполезность инструкцииесли инструкция полезна, ее пометкавосстанавливаетсяпомечаются ветви, по которым «приходят»операнды инструкции (операнды полезны, так какиспользуются в полезной инструкции)посещаются все блоки b  RDF(n) и помечаетсякаждая ветвь, ведущая к этим блокам.Каждая помеченная ветвь помещается в Worklist.Проход завершается, когда Worklist становится пустым.395.3. Исключение бесполезного кода5.3.6.

Проход Mark.Базовый блок, содержащий хотя бы одну помеченную инструкцию,помечается для ускорения анализа.Ветвь состоит из одного или более блоков. Она считаетсяпомеченной, если помечен хотя бы один из ее блоков.Каждая помеченная ветвь помещается в Worklist.Проход завершается, когда Worklist становится пустым.405.3. Исключение бесполезного кода5.3.6.

Проход Mark (псевдокод)Mark( )WorkList  ;for each инструкции i (x  op, y, z ::: пометка)убрать пометку у iif (i полезная) пометить iWorkList  WorkList  {i}while (WorkList  )remove i from WorkListif (def(y) не помечена)пометить def(y)WorkList  WorkList  {def(y)}if (def(z) не помечена)пометить def(z)WorkList  WorkList  {def(z)}for each block b  RDF(block(i))пусть j ветвь, оканчивающаяся в bif (j не помечена)пометить jWorkList  WorkList  {j}415.3.

Исключение бесполезного кода5.3.6 Проход SweepSweep( )for each instruction iif (i is unmarked)if (i is a branch)rewrite i with a jumpto i’s nearest markedpostdominatorif (i is not a jump)delete iНа втором проходе (Sweep) в каждый блок, с которого начинаетсянепомеченная ветвь, помещается безусловный переход на егопомеченный постдоминатор.Это правильно, так как если ветвь не помечена, потомки блокавплоть до его непосредственного постдоминатора, не могутсодержать полезных инструкций, так как иначе они были быпомечены.425.3.

Исключение бесполезного кода5.3.6 Проход SweepSweep( )for each instruction iif (i is unmarked)if (i is a branch)rewrite i with a jumpto i’s nearest markedpostdominatorif (i is not a jump)delete iСказанное справедливо и для непосредственного непомеченногопостдоминатора.Чтобы найти ближайший помеченный постдоминатор, можнодвигаться вверх по дереву постдоминаторов, пока не найдетсяпомеченный блок. Поиск обязательно закончится, так как поопределению блок exit помечен.435.4.

Исключение недостижимого кода5.4.1 Постановка задачиИногда ГПУ содержит недостижимый код. Компилятор долженнайти недостижимые базовые блоки и исключить их.Две причины недостижимости блока:в ГПУ отсутствует путь, ведущий к базовому блоку;путь, достигающий блока, может быть невыполнимым(например, if(i*(i+1)%2==0){…})В этом курсе рассматривается только первый случай, в которомдля анализа можно использовать алгоритм типа Mark & Sweep.Этот анализ прост и недорог. Он может быть выполнен попутново время обхода ГПУ для других целей или даже во времяпостроения ГПУ.445.4.

Исключение недостижимого кода5.4.2 Анализ достижимостиПроход Mark сначала помечает каждый блок b как«недостижимый», потом он начинает обход ГПУ с entry ипомечает как «достижимый» каждый блок, которого он можетдостичь.Если все ветвления и переходы определяются однозначно, товсе непомеченные блоки действительно недостижимы и могутбыть удалены на проходе Sweep.В случае неоднозначных условий ветвления, компилятор долженсохранить любой блок, достижимый ветвлением или переходом.455.5. Оптимизация потока управления5.5.1. Постановка задачиНекоторые оптимизации могут иметь побочный эффект,изменяющий форму ГПУ, добавляя в него бесполезные блоки идуги.Если компилятор содержит такие оптимизации, он должентакже содержать проход, упрощающий ГПУ, исключаябесполезный поток управления.Функция Clean обрабатывает непосредственно ГПУоптимизируемой процедуры, упрощая его.465.5.

Оптимизация потока управления5.5.2. Основные преобразования. Преобразование 1.Функция Clean применяет следующие четыре основныхпреобразования (в указанном порядке): 1. Свернуть избыточную ветвь: Если последниеинструкции блока Bi реализуют ветвление, и обе ветвивыполняют условный переход на один и тот же блок Bj,то ветвление заменяется безусловным переходом наблок Bj.Bi BiBjBjТакая ситуация может возникнуть в результатедругих оптимизаций(Например, у Bi могло быть два последователя, каждыйиз которых заканчивался переходом на Bj. Если другиеоптимизации убрали из этих блоков все инструкции,то второе из основных преобразований могло породитьлевый граф, показанный на рисунке).475.5. Оптимизация потока управления5.5.2.

Основные преобразования. Преобразование 2. 2.Удалить пустой блок: Если блок Bi содержиттолько инструкцию перехода, то он поглощаетсясвоим последователем – блоком Bj.BiBjBjТакая ситуация возникает, когдапредшествующие оптимизации удаляют всеинструкции из блока Bi.Так как у Bi всего один последователь, Bj,преобразование перенаправляет дуги, входящиев Bi, к Bj и исключает Bi из Pred(Bj), что упрощаетГПУ и ускоряет выполнение.485.5. Оптимизация потока управления5.5.2. Основные преобразования. Преобразование 3. 3.Объединение блоков: Если имеется блок Bi, которыйоканчивается переходом на Bj, у которого всего одинпредшественник, Bi, он может объединить эти блоки какпоказано на рисунке внизу, что позволяет исключитьпереход из Bi в Bj.BiBj495.5. Оптимизация потока управления5.5.2.

Основные преобразования. Преобразование 4. 4.Подъём ветвлений. В ситуации, когда блок Bi, которыйоканчивается переходом в пустой блок Bj, а блок Bjоканчивается ветвлением, переход в конце блоказаменяется на копию ветвления из блока Bj. Такоепреобразование поднимает ветвление из Bj в Bi.Ситуация может возникнуть, если другие оптимизацииудалят все операции из Bj, оставив только ветвление.К ГПУ добавится ребро.