Тема 08(2016)SSA-форма (1161803)
Текст из файла
8. Форма статическогоединственного присваивания(SSA-форма)18.1 Форма статического единственного присваивания(SSA-форма)8.1.1. Постановка задачиФорма статического единственного присваивания (SSA)позволяет в каждой точке программы объединитьинформацию об имени переменнойс информацией о текущем значении этой переменной(или, что то же самое, с информацией о том, какое изопределений данной переменной определяет еетекущее значение в данной точке).28.1 Форма статического единственного присваивания(SSA-форма)8.1.1. Постановка задачиФорма статического единственного присваивания (SSA)позволяет в каждой точке программы объединитьинформацию об имени переменнойс информацией о текущем значении этой переменной(или, что то же самое, с информацией о том, какое изопределений данной переменной определяет еетекущее значение в данной точке).Хотелось бы, чтобы программа в SSA-форме удовлетворяла двумусловиям:(1)каждое определение переменной имеет индивидуальноеимя;(2)каждое использование переменной ссылается наединственное определение.38.1 SSA-форма8.1.1.
Постановка задачиx -,a,bx -,a,cИспользования в синемблоке достигают триопределения x,в зеленом – четыреопределения xЦель же состоит в том,чтобы каждогоиспользованиядостигало толькоодно определениеВведем «функцию»объединения значенийили -функциюx +,a,bx *,a,cu *,x,bv +,a,x48.1 SSA-формаx0 -,a,b8.1.1. Постановка задачиx1 -,a,cПо определениюx2 +,a,bx3 (x2, x0)является новымопределениемпеременной x:значение x3 равно x2,когда управлениепопадает в блок слева,значение x3 равно x0,когда управлениепопадает в блок справа.x3 (x2,x0)x4 *,a,cx5 (x4,x3)u *,x,bx6 (x1,x5)v +,a,x658.1 SSA-форма8.1.2. Определение -функции -функция определяет SSA-имя для значения своего аргумента,соответствующего ребру, по которому управление входит в блок.При входе в базовый блок все его -функции выполняютсяодновременно и до любого другого оператора, определяяцелевые SSA-имена.68.1 SSA-форма8.1.2.
Определение -функции. Примерx =y = …while (x < 100){x = x + 1y = y + x}78.1 SSA-форма8.1.2. Определение -функции. Примерx =y = …while (x < 100){x = x + 1y = y + x}x0y0ifloop: x1y1x2y2ifnext: x3y3= …= …(x0 100) goto next= (x0, x2)= (y0, y2)= x1 + 1= y1 + x2(x2 < 100) goto loop= (x0, x2)= (y0, y2)88.1 SSA-форма8.1.2. Определение -функции.
Примерx =y = …while (x < 100){x = x + 1y = y + x}Каждая из -функцийобъединяет значения своихаргументов в новое значение,определением которого онаявляется.x0y0ifloop: x1y1x2y2ifnext: x3y3= …= …(x0 100) goto next= (x0, x2)= (y0, y2)= x1 + 1= y1 + x2(x2 < 100) goto loop= (x0, x2)= (y0, y2)98.1 SSA-форма8.1.2. Определение -функции. Примерx =y = …while (x < 100){x = x + 1y = y + x}Каждая из -функцийобъединяет значения своихаргументов в новое значение,определением которого онаявляется.x0y0ifloop: x1y1x2y2ifnext: x3y3= …= …(x0 100) goto next= (x0, x2)= (y0, y2)= x1 + 1= y1 + x2(x2 < 100) goto loop= (x0, x2)= (y0, y2)До цикла –На входе в цикл –Внутри цикла –После цикла –x0 ,x1 ,x2 ,x3 ,y0y1y2y3108.1 SSA-форма8.1.2. Определение -функции.
Примерx =y = …while (x < 100){x = x + 1y = y + x}x0y0ifloop: x1y1x2y2ifnext: x3y3= …= …(x0 100) goto next= (x0, x2)= (y0, y2)= x1 + 1= y1 + x2(x2 < 100) goto loop= (x0, x2)= (y0, y2)Затруднение. Первый аргумент (x0, x2)определяетсяв блоке, который предшествует циклу, второй аргументопределяется позже в блоке, содержащем (x0, x2).Следовательно, при первом выполнении (x0, x2)ее второй11аргумент еще не определен.8.1 SSA-форма8.1.2. Определение -функции. Примерx =y = …while (x < 100){x = x + 1y = y + x}x0y0ifloop: x1y1x2y2ifnext: x3y3= …= …(x0 100) goto next= (x0, x2)= (y0, y2)= x1 + 1= y1 + x2(x2 < 100) goto loop= (x0, x2)= (y0, y2)Выход из затруднения: по определению любая -функция(а значит и (x0, x2)) читает только один из своихаргументов, а именно тот аргумент, который соответствуетсамому последнему пройденному ребру ГПУ.Поэтому -функция не прочитает неопределенногозначения.128.1 SSA-форма8.1.3.
Количество аргументов -функцииПо определению у -функции может быть любое числоаргументов.Например, на рисунке -функция, у которой 16 аргументовswitch on y0x1=…x2=…...x16=…x17 = (…)138.2 Построение SSA-формы8.2.1. Постановка задачи Для преобразования процедуры в SSA-форму компилятор должен:вставить в точки сбора необходимые -функции для каждойпеременнойпереименовать переменные (в том числе и временные) такимобразом, чтобы выполнялись следующие два правила:(1)каждое определение имеет индивидуальное имя; и(2)каждое использование ссылается на единственноеопределение.148.2 Построение SSA-формы8.2.2. Базовый алгоритм построения SSA-формы Вход:программа в промежуточном представлении Выход:промежуточное представление программы в SSA-форме Метод:Выполнить следующие действия:(1)Вставить -функции:в начало каждого блока B, у которого|Pred(B)| > 1 вставить -функцию видаy = (y, y, ...) для каждого имени y, котороелибо определяется, либо используется в B.Вставленная -функция должна иметь по одномуаргументу для каждого B′ Pred(B):Порядок вставляемых -функций несуществен158.2 Построение SSA-формы8.2.2.
Базовый алгоритм построения SSA-формы Вход:программа в промежуточном представлении Выход:промежуточное представление программы в SSA-форме Метод:Выполнить следующие действия:(2)Переименовать переменные:(a)вычислить достигающие определения;при этом только одно определение будетдостигать любого использования:это гарантируют вставленные -функции,которые тоже являются определениями;(b)переименовать каждое использование(как основных, так и временных)переменных таким образом, чтобы новоеимя соответствовало единственномуопределению, которое достигает его.168.2 Построение SSA-формы8.2.2. Базовый алгоритм построения SSA-формы Вход:программа в промежуточном представлении Выход:промежуточное представление программы в SSA-форме Метод:Выполнить следующие действия:(3)Отсортировать определения,достигающие каждой -функции и для каждой -функции обеспечить соответствие имен ееаргументов путям, по которым определенияэтих аргументов достигают блока, содержащегоуказанную -функцию.178.2 Построение SSA-формы8.2.3.
Базовый алгоритм построения SSA-формы. Примерx -,a,bx -,a,cx +,a,bx *,a,cu *,x,bv +,a,x188.2 Построение SSA-формы8.2.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,x198.2 Построение SSA-формы8.2.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,x6208.2 Построение SSA-формы8.2.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,x6218.3 Построение частично усеченной SSA-формы8.3.1. Постановка задачиПо определению частично усеченная SSA-форма содержитменьше -функций, чем максимальная (но, к сожалению, какследует и из ее названия она содержит не минимально возможноеколичество -функций).228.3 Построение частично усеченной SSA-формы8.3.1.
Постановка задачиПо определению частично усеченная SSA-форма содержитменьше -функций, чем максимальная (но, к сожалению, какследует и из ее названия она содержит не минимально возможноеколичество -функций).Чтобы не всегда вставлять -функции необходимодля каждой точки сбора уметь выяснять, какие переменныенуждаются в -функциях.238.3 Построение частично усеченной SSA-формы8.3.1. Постановка задачиПо определению частично усеченная SSA-форма содержитменьше -функций, чем максимальная (но, к сожалению, какследует и из ее названия она содержит не минимально возможноеколичество -функций).Чтобы не всегда вставлять -функции необходимодля каждой точки сбора уметь выяснять, какие переменныенуждаются в -функциях.Илидля каждого определения переменной уметь находить множествовсех точек сбора, которые нуждаются в -функциях для значения,порожденного этим определением.248.3 Построение частично усеченной SSA-формы8.3.1.
Постановка задачиx -,a,bВ розовом блоке -функциядля x не нужна, так как ислева, и справа приходит однои то же значение x258.3 Построение частично усеченной SSA-формы8.3.1. Постановка задачиx -,a,bx -,a,bx +,a,bВ розовом блоке -функциядля x не нужна, так как ислева, и справа приходит однои то же значение xВ розовом блоке нужна -функция для x так как справапоявился блок, в которомвычисляется еще одно значение x268.3 Построение частично усеченной SSA-формы8.3.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.278.3 Построение частично усеченной SSA-формы8.3.1.
Постановка задачиПусть Dom(m) – множество доминаторов узлаm.n:x=…Если n Dom(m), определение x0в вершине n не требует -функции вp:узле m, так как каждый путь, которыйx=…достигает m проходит через n.Если n Dom(m), единственнымm:вариантом, при котором определение x0Нетрудно заметить,…=xне достигнет узла m, являетсячто блок с меткой m – границавклиниваниеопределенияв некоторомдоминированияблока с xметкойp.узле p Dom(m), расположенноммежду n и m.При этом -функцию будет требоватьне определение x в узле n, а егопереопределение в узле p.288.3 Построение частично усеченной SSA-формы8.3.2.
Размещение -функцийБазовый алгоритм помещал по -функции для каждойпеременной в начало каждой вершины сбора.Границы доминирования позволяют более точно определить,какие именно -функции необходимы в данной вершине.Правило: Определение переменной x в базовом блоке B требуетсоответствующей -функции в каждой вершине из DF(B).При этом вставленная -функция становится новымопределением x, так что могут потребоваться новые -функции.298.3 Построение частично усеченной SSA-формы8.3.2. Размещение -функцийПеременная, которая используется только в одном блоке, неможет иметь живой -функции. Поэтому -функции нужновставлять только для глобальных имен.Поэтому перед размещением -функций вычисляется множествоглобальных имен Globals.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
