Лекция 04. Форма статического единственного присваивания (SSA-форма) (1157462), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Базовый алгоритм построения SSA-формы Вход:программа в промежуточном представлении Выход:промежуточное представление программы в SSA-форме Метод:Выполнить следующие действия:(3)Отсортировать определения,достигающие каждой -функции и для каждой -функции обеспечить соответствие имен ееаргументов путям, по которым определенияэтих аргументов достигают блока, содержащегоуказанную  -функцию.354.3 Построение SSA-формы4.3.3. Базовый алгоритм построения SSA-формы.

Примерx  -,a,bx  -,a,cx  +,a,bx  *,a,cu  *,x,bv  +,a,x364.3 Построение SSA-формы4.3.3. Базовый алгоритм построения SSA-формы. Примерx  -,a,bx  -,a,bx  -,a,cx  -,a,cx  +,a,bx  *,a,cu  *,x,bv  +,a,xx  +,a,bx  *,a,cu  *,x,bv  +,a,x374.3 Построение SSA-формы4.3.3. Базовый алгоритм построения SSA-формы. ПримерАлгоритм вставил -функциюпосле каждой точки сбора ГПУ.x0  -,a,bx1  -,a,cПосле преобразованияпроцедуры в SSA-форму(1) внутри процедуры каждоеопределение создаетуникальное имя;(2) каждое использованиеобращается к единственномуопределению.x2  +,a,bx3 (x2,x0)x4  *,a,cx5 (x4,x3)u  *,x5,bx6 (x1,x5)v  +,a,x6384.3 Построение SSA-формы4.3.3.

Базовый алгоритм построения SSA-формы. Примерx0  -,a,bx1  -,a,cПостроенная SSA-форма корректна: Каждая переменнаяопределяется только один раз Каждое обращение используетимя отдельного определения.Построенная SSA-форманазывается максимальной SSA-формой, так как она обычносодержит намного больше -функций, чем необходимо.x2  +,a,bx3 (x0,x2)x4  *,a,cx5 (x4,x3)u  *,x5,bx6 (x1,x5)v  +,a,x6394.4 Построение частично усеченной SSA-формы4.4.1. Постановка задачиПо определению частично усеченная SSA-форма содержитменьше  -функций, чем максимальная (но, к сожалению, какследует и из ее названия она содержит не минимально возможноеколичество  -функций).404.4 Построение частично усеченной SSA-формы4.4.1.

Постановка задачиПо определению частично усеченная SSA-форма содержитменьше  -функций, чем максимальная (но, к сожалению, какследует и из ее названия она содержит не минимально возможноеколичество  -функций).Чтобы не всегда вставлять  -функции необходимодля каждой точки сбора уметь выяснять, какие переменныенуждаются в  -функциях.414.4 Построение частично усеченной SSA-формы4.4.1. Постановка задачиПо определению частично усеченная SSA-форма содержитменьше  -функций, чем максимальная (но, к сожалению, какследует и из ее названия она содержит не минимально возможноеколичество  -функций).Чтобы не всегда вставлять  -функции необходимодля каждой точки сбора уметь выяснять, какие переменныенуждаются в  -функциях.Илидля каждого определения переменной уметь находить множествовсех точек сбора, которые нуждаются в  -функциях для значения,порожденного этим определением.424.4 Построение частично усеченной SSA-формы4.4.1. Постановка задачиx  -,a,bВ розовом блоке  -функциядля x не нужна, так как ислева, и справа приходит однои то же значение x434.4 Построение частично усеченной SSA-формы4.4.1.

Постановка задачиx  -,a,bx  -,a,bx  +,a,bВ розовом блоке  -функциядля x не нужна, так как ислева, и справа приходит однои то же значение xВ розовом блоке нужна -функция для x так как справапоявился блок, в которомвычисляется еще одно значение x444.4 Построение частично усеченной SSA-формы4.4.1. Постановка задачиПусть Dom(m) – множество доминаторов узла m.n:x=…Если n  Dom(m), определение x0в вершине n не требует  -функции вp:узле m, так как каждый путь, которыйx=…достигает m проходит через n.Если n  Dom(m), единственнымm:вариантом, при котором определение x0…=xне достигнет узла m, являетсявклинивание определения x в некоторомузле p  Dom(m), расположенном междуn и m.При этом -функцию будет требоватьне определение x в узле n, а егопереопределение в узле p.454.4 Построение частично усеченной SSA-формы4.4.2.

Граница доминирования (Dominance Frontier)Определение. Множество узлов m, удовлетворяющих условиям:n является доминатором предшественника mp  Pred(m) & n  Dom(p)(2)n не является строгим доминатором mn  (Dom (m) – {m}).называется границей доминирования n и обозначается DF(n).(1)Неформально: DF(n) содержит все первые узлы, которыедостижимы из n, на любом пути графа потока, проходящемчерез n, но над которыми n не доминирует.464.4 Построение частично усеченной SSA-формы4.4.2.

Граница доминированияПример. На рисунке справаB3  Dom(B4), B3  Dom(B5),B3  Dom(B6),B3  (Dom(B7) – {B7}),т.е. B3 является доминатором B4, B5 и B6,но не является доминатором B7.Более того, на любом пути, выходящем из B3,B7 – первая вершина, для которойB3 не является доминаторомСледовательно, B7  DF(B3)а так как узел B3 не является доминаторомузлов B0, B1 и B2, то DF(B3) = {B7}474.4 Построение частично усеченной SSA-формы4.4.3.

Построение границы доминированияСвойства узлов, входящих в границу доминирования(1)узел, принадлежащий границе доминирования долженбыть точкой сбора графа потока.(2)если j – точка сбора: n  Pred(j) & n  Dom(j),то j  DF(n)т.е. точка сбора j входит в границу доминированиялюбого своего предшественника n, не являющегосядоминатором j.(3)если j – точка сбора:m  Pred(j) & n  Dom(m) & n  Dom(j), то j  DF(n)т.е. доминаторы предшественников точки сбора j должныиметь j в своих множествах границ доминирования,если только они не доминируют над j.484.4 Построение частично усеченной SSA-формы4.4.3.

Построение границы доминированияСвойства узлов границы доминирования позволяют составитьпростой алгоритм ее построенияШаг 1.Найти все точки сбора j графа потока, т.е. все узлы j, укоторых |Pred(j)| > 1.Шаг 2.Исследовать каждый узел p  Pred(j) и продвинутьсяпо дереву доминаторов, начиная с p и вплоть донепосредственного доминатора j: при этом j входит всостав границы доминирования каждого из пройденныхузлов, за исключением непосредственного доминатора j.494.4 Построение частично усеченной SSA-формы4.4.4.

Алгоритм построения границ доминирования Вход: граф потока Выход: множество границ доминирования для узлов графа потока Метод: выполнить следующую программу:for all n  N do DF(n) = ;for all n  N do{if |Pred(n)| > 1 thenfor each p  Pred(n) do{r = p;while r  IDom(n) do{DF(r) = DF(r)  {n};r = Idom(r);}};}504.4 Построение частично усеченной SSA-формы4.4.5. Пример применения алгоритма построения границдоминированияГраф потокауправленияДереводоминаторовn01234567Pred(n){0,7}{1}{1}{3}{3}{4, 5}{2, 6}Dom(n){0}{0,1}{0,1,2}{0,1,3}{0,1,3,4} {0,1,3,5} {0,1,3,6} {0,1,7}Idom(n){0}{1}{1}{3}{3}{3}{1}514.4 Построение частично усеченной SSA-формы4.4.5.

Пример применения алгоритма построения границдоминированияУ графа три точки сбора – входы в узлы B1, B6 и B7.Узел B6: Pred(B6) = {B4, B5}, Idom(B6) = {B3},проходим от B5 до B3, добавляем B6 к DF(B5),проходим от B4 до B3, добавляем B6 к DF(B4).Узел B7: Pred(B7)= {B2, B6}, Idom(B7) = {B1},проходим от B2 до B1, добавляем B7 к DF(B2),проходим от B6 до B3, добавляем B7 к DF(B6)проходим от B3 до B1, добавляем B7 к DF(B3)Таблица текущих результатов:n0123456DF(Bn){B7}{B7}{B6}{B6}{B7}74.4 Построение частично усеченной SSA-формы4.4.5.

Пример применения алгоритма построения границдоминированияУзел B1: Pred(B1) = {B0, B7}, Idom(B1) = {B0},У B0 нет непосредственного доминатора:Idom(B0) = ,значит B1  DF(B0).проходим от B7 до B1 (по обратному ребру),добавляем B1 к DF(B7).Окончательная таблица результатов0nDF(Bn) 1234567{B7} {B7} {B6} {B6} {B7} 4.4 Построение частично усеченной SSA-формы4.4.6. Размещение -функцийБазовый алгоритм помещал по -функции для каждойпеременной в начало каждой вершины сбора.Границы доминирования позволяют более точно определить,какие именно  -функции необходимы в данной вершине.Правило: Определение переменной x в базовом блоке B требуетсоответствующей -функции в каждой вершине из DF(B).При этом вставленная -функция становится новымопределением x, так что могут потребоваться новые -функции.544.4 Построение частично усеченной SSA-формы4.4.6.

Размещение -функцийПеременная, которая используется только в одном блоке, неможет иметь живой -функции. Поэтому  -функции нужновставлять только для глобальных имен.Для этого вычисляется множество глобальных имен Globals.При этом используются результаты анализа живых переменных.Алгоритм вычисления множества Globals попутно вычисляетдля каждого базового блока B множество defB и для каждойx Globals – множество Blocks(x) базовых блоков B,в которых x defB.554.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийАлгоритм построения множеств Globals и Blocks(x) Вход:граф потока Выход:множество Globals,множества Blocks(x) для каждой переменной xмножества defB для каждого базового блока B. Метод:Выполнить следующие действия:564.4 Построение частично усеченной SSA-формы4.4.7.

Размещение -функцийАлгоритм построения множеств Globals и Blocks(x)Globals = ;for each variable x doBlocks(x) = ;for each block B do {defB = ;for each instruction i  B do {|| пусть команда i имеет вид: x  op, y, zif y  defB then Globals = Globals  {y};if z  defB then Globals = Globals  {z};defB = defB  {x};Blocks(x) = Blocks(x)  {B}}57}4.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийАлгоритм размещения-функций Вход: исходный граф потока Выход: преобразованный граф потока Метод: Выполнить следующие действияfor each name x  Globals do {WorkList = Blocks(x);for each block B  WorkList do {for each block D  DF(B) do {вставить -функцию для x в D;WorkList = WorkList  {D};};WorkList = WorkList – {B};}}584.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийЗамечание 1.

Для каждого блока B  WorkList алгоритм вставляет-функцию в начало каждого блока D  DF(B). Порядок -функцийроли не играет.После вставления -функции для x в блок D алгоритм добавляет Dв WorkList, чтобы отразить новое определение x в блоке D.594.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийЗамечание 2. Для улучшения эффективности алгоритманеобходимо избегать следующих двух видов дублирования:(1) помещение какого-либо блока в WorkList более одного разадля каждого глобального имени; для этого можно вести списокуже обработанных блоков (например, не удалять B изWorkList, а помечать его как уже обработанный).(2) рассматриваемый блок может входить в состав границдоминирования нескольких блоков, входящих в WorkList;чтобы избежать вставления дублирующих -функций дляпеременной x, можно использовать список блоков, которые ужесодержат -функции для x, что быстрее, чем проверять каждыйраз какие -функции включены.604.4 Построение частично усеченной SSA-формы4.4.7.

Размещение -функцийПример.B0i  1B5c B1a b B3a d B2bcdbB7yzidB6B4 +, a, b +, c, d +, i, 1614.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийПример.Сначала вычисляются множества Globals и Blocks(x):Globals = {a, b, c, d, i}.Множества Blocks(x) представлены в таблице:abcdi{B1, B3}{B3, B6}{B1, B2, B5}{B2, B3, B4}{B0, B7}Алгоритму размещения  -функций потребуются также ужевычисленные границы доминированияn01234567DF(Bn){B7}{B7}{B6}{B6}{B7}{B1}624.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийПример.Применяем алгоритм размещения  -функций.Берем первую переменную из Globals = {a, b, c, d, i}, т.е .

Характеристики

Список файлов лекций