Лекция 04. Форма статического единственного присваивания (SSA-форма) (Лекции (2015))
Описание файла
Файл "Лекция 04. Форма статического единственного присваивания (SSA-форма)" внутри архива находится в папке "Лекции (2015)". PDF-файл из архива "Лекции (2015)", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
4. Форма статическогоединственного присваивания(SSA-форма)14.1 Доминаторы4.1.1 ОпределениеВ ГПУ вершина d является доминатором вершины n(этот факт записывается как d dom n или d = Dom(n)),если любой путь от вершины Entry до вершины n проходитчерез вершину d.Замечание. Из определения 4.2.1 следует, что каждая вершина nявляется доминатором самой себя, так как путь от Entry до nпроходит через n.24.1 ДоминаторыB14.1.2 Примеры доминаторовРассмотрим ГПУ с входной вершиной B1,показанный на рисунке.является доминаторомвсех узлов, включаяB4себя самого.B2является доминаторомB6только себя самого.B3является доминаторомвсех вершин, кроме B1 иB7B2.B4является доминаторомвсех вершин, кроме B1, B2и B3 .B5 и B6 являются доминаторамитолько себя.B3B2B1B5B8B10B934.1 ДоминаторыB14.1.2 Примеры доминаторовРассмотрим ГПУ с входной вершиной B1,показанный на рисунке.является доминаторомвершин B7, B8, B9 и B10.B8является доминаторомвершин B8, B9 и B10.B9 и B10являются доминаторамитолько себя.B3B2B7B4B6B5B7B8B10B944.1 Доминаторы4.1.3 Свойства отношения dom 1.Отношение dom рефлексивно, антисимметрично итранзитивно, т.е.
является отношением частичного порядка.(1)(2)(3) 2.Рефлексивность: a dom a.Антисимметрчность: если a dom b и b dom а,то a = b.Транзитивность: если a dom b и b dom с, то a dom c.Для любой вершины n ГПУ каждый ациклический путьот Entry до n проходит через все доминаторы n,причем на всех таких путях доминаторы проходятсяв одном и том же порядке54.1 Доминаторы4.1.3 Свойства отношения dom 3.Вершина i ГПУ является непосредственным доминаторомвершины n (i idom n), если(1)i dom n(2)не существует вершины m, m i, m n,такой что i dom m и m dom n. 4.У каждой вершины n за исключением Entry существуетединственный непосредственный доминатор. 5.Вершина s ГПУ является строгим доминатором вершины n(s sdom n), если s dom n и s n.64.1 Доминаторы4.1.3 Свойства отношения dom 6Пусть n – вершина ГПУ,Pred(n) = {p1, p2, … , pk} и d n.Тогда d dom n тогда и только тогда, когда i d dom pi. 7Множество строгих доминаторов вершины n являетсяпересечением множеств доминаторов всех еепредшественников.74.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовЗадача поиска всех доминаторов вершин ГПУ формулируетсякак задача анализа потока данных в прямом направлении.Значением потока данных на входе в блок B является множествовершин (базовых блоков), являющихся доминаторами B.Операцией сбора является операция пересечения множеств.Передаточная функция fB добавляет вершину B крассматриваемому множеству вершин.Граничное условие: единственным доминатором вершиныEntry является она сама.84.1 Доминаторы4.1.4 Алгоритм вычисления доминаторов АлгоритмВход:граф потока G = N, Е с входным узлом Entry.Выход:для каждой вершины n N множество D(n)ее доминаторов.Метод:найти решение следующей задачи потока данных(вершины n соответствуют базовым блокам):n ND(n) = Out[Pred(n)].94.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовОбласть определенияМножество подмножеств базовых блоковНаправление обходаForwardПередаточная функцияfB(x) = x {B}Граничное условиеOut [Entry] = EntryОперация сбора ()Система уравненийOut[ B] f B ( In[ B])In[ B] Out[ P]PPred ( B )Начальное приближениеOut [B] = N104.1 ДоминаторыB14.1.4 Алгоритм вычисления доминаторов Пример.
Применим алгоритм к ГПУна рисунке в предположении, что блокипосещаются в порядке их номеров, аEntry это блок B1.Pred(B2) = {B1}D(B2) = {B2} D(B1) ={B1, B2}B2B4Первая итерацияГраничное условие: D(B1) = {B1}B3B6B5B7B8B10B9114.1 ДоминаторыB14.1.4 Алгоритм вычисления доминаторов Пример. Применим алгоритм к ГПУна рисунке в предположении, что блокипосещаются в порядке их номеров, аEntry это блок B1.B2B4Первая итерацияГраничное условие: D(B1) = {B1}B3B6Pred(B2) = {B1}D(B2) = {B2} D(B1) ={B1, B2}Pred(B3) = {B1, B2, B4, B8}D(B3) = {B3} (D(B1) D(B2) D(B4) D(B8)) = {B3} ({B1} {B1, B2} N N ) ={B1, B3}N = {B1, B2, B3, B4, B5, B6, B7, B8, B9, B10}B5B7B8B10B9124.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4} (D(B3) D(B7)) = {B4} ({B1, B3} N ) == {B1, B3, B4}134.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4} (D(B3) D(B7)) = {B4} ({B1, B3} N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5} D(B4) = {B5} {B1, B3, B4} = {B1, B3, B4, B5}D(B6) = {B6} D(B4) = {B6} {B1, B3, B4} = {B1, B3, B4, B6}144.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4} (D(B3) D(B7)) = {B4} ({B1, B3} N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5} D(B4) = {B5} {B1, B3, B4} = {B1, B3, B4, B5}D(B6) = {B6} D(B4) = {B6} {B1, B3, B4} = {B1, B3, B4, B6}Pred(B7) = {B5, B6, B10}D(B7) = {B7} (D(B5) D(B6)) D(B10)) = {B7} ({B1, B3, B4, B5} = {B1, B3, B4, B6} N ) = {B1, B3, B4, B7}Pred(B8) = {B7}154.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4} (D(B3) D(B7)) = {B4} ({B1, B3} N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5} D(B4) = {B5} {B1, B3, B4} = {B1, B3, B4, B5}D(B6) = {B6} D(B4) = {B6} {B1, B3, B4} = {B1, B3, B4, B6}Pred(B7) = {B5, B6, B10}D(B7) = {B7} (D(B5) D(B6)) D(B10)) = {B7} ({B1, B3, B4, B5} = {B1, B3, B4, B6} N ) = {B1, B3, B4, B7}Pred(B8) = {B7}D(B8) = {B8} D(B7) = {B8} {B1, B3, B4, B7} = {B1, B3, B4, B7, B8}Pred(B9) = Pred(B10) = {B8}D(B9) = {B9} D(B8) = {B9} {B1, B3, B4, B7, B8} = {B1, B3,B4, B7,B8,B9}D(B10) = {B10} D(B8) = {B10} {B1, B3, B4, B7, B8} == {B1, B3, B4, B7, B8, B10}164.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4} (D(B3) D(B7)) = {B4} ({B1, B3} N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5} D(B4) = {B5} {B1, B3, B4} = {B1, B3, B4, B5}ПолученныезначенияD(B6) = {B6} D(B4) = {B6} {B1, B3, B4} = {B1, B3, B4, B6}Pred(B7) = {B5, B6D(B, B101}) – D(B10) на второйитерациине изменяютсяD(B7) = {B7} (D(BD(B10)) = {B7} ({B1, B3, B4, B5} 5) D(B6))= {B1, B3, B4, B6} N ) = {B1, B3, B4, B7}Pred(B8) = {B7}D(B8) = {B8} D(B7) = {B8} {B1, B3, B4, B7} = {B1, B3, B4, B7, B8}Pred(B9) = Pred(B10) = {B8}D(B9) = {B9} D(B8) = {B9} {B1, B3, B4, B7, B8} = {B1, B3,B4, B7,B8,B9}D(B10) = {B10} D(B8) = {B10} {B1, B3, B4, B7, B8} == {B1, B3, B4, B7, B8, B10}174.1 Доминаторы4.1.5 Непосредственные доминаторы и дерево доминаторовnB1B2B3B4B5B6B7B8B9B10D(n)B1B1, B2B1, B3B1, B3, B4B1, B3, B4, B5B1, B3, B4, B6B1, B3, B4, B7B1, B3, B4, B7, B8B1, B3, B4, B7, B8, B9B1, B3, B4, B7, B8, B10IDom(n)–B1B1B3B4B4B4B7B8B8В таблице приведенысписки доминаторовкаждой вершины ГПУиз рассмотренногопримера.Непосредственныйдоминатор в каждомсписке предпоследний.Соединив дугами длякаждого n NIDom(n) с n, получимдерево доминаторов.Оно изображено наследующем слайде184.1 Доминаторы4.1.5 Непосредственные доминаторы и дерево доминаторовB1B3B2B1B2B3B4B6B4B5B5B7B6B7B8B8ГПУB10B9B9ДереводоминаторовB10194.2 Форма статического единственного присваивания(SSA-форма)4.2.1.
Постановка задачиФорма статического единственного присваивания (SSA)позволяет в каждой точке программы объединитьинформацию об имени переменнойс информацией о текущем значении этой переменной(или, что то же самое, с информацией о том, какое изопределений данной переменной определяет ее текущеезначение в данной точке).204.2 Форма статического единственного присваивания(SSA-форма)4.2.1.
Постановка задачиФорма статического единственного присваивания (SSA)позволяет в каждой точке программы объединитьинформацию об имени переменнойс информацией о текущем значении этой переменной(или, что то же самое, с информацией о том, какое изопределений данной переменной определяет ее текущеезначение в данной точке).Хотелось бы, чтобы программа в SSA-форме удовлетворяла двумусловиям:(1)каждое определение переменной имеет индивидуальноеимя;(2)каждое использование переменной ссылается наединственное определение.214.2 SSA-форма4.2.1.
Постановка задачиx -,a,bx -,a,cИспользования в синемблоке достигают триопределения x,в зеленом – четыреопределения xЦель же состоит в том,чтобы каждогоиспользованиядостигало толькоодно определениеВведем «функцию»объединения значенийили -функциюx +,a,bx *,a,cu *,x,bv +,a,x224.2 SSA-форма4.2.1. Постановка задачиx0 -,a,bx1 -,a,cПо определениюx3 (x2, x0)является новымопределениемпеременной x:значение x3 равно x2,когда управлениепопадает в блок слева,значение x3 равно x0,когда управлениепопадает в блок справа.x2 +,a,bx3 (x2,x0)x4 *,a,cx5 (x4,x3)u *,x,bx6 (x1,x5)v +,a,x6234.2 SSA-форма4.2.2. Определение -функции -функция определяет SSA-имя для значения своего аргумента,соответствующего ребру, по которому управление входит в блок.При входе в базовый блок все его -функции выполняютсяодновременно и до любого другого оператора, определяяцелевые SSA-имена.244.2 SSA-форма4.2.2. Определение -функции. Примерx =y = …while (x < 100){x = x + 1y = y + x}254.2 SSA-форма4.2.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)264.2 SSA-форма4.2.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)274.2 SSA-форма4.2.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 ,y0y1y2y3284.2 SSA-форма4.2.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)ее второй29аргумент еще не определен.4.2 SSA-форма4.2.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)) читает только один из своихаргументов, а именно тот аргумент, который соответствуетсамому последнему пройденному ребру ГПУ.Поэтому -функция никогда не прочитает неопределенногозначения.304.2 SSA-форма4.2.3. Количество аргументов -функцииПо определению у -функции может быть любое числоаргументов.Например, на рисунке -функция, у которой 16 аргументовswitch on y0x1=…x2=…...x16=…x17 = (…)314.3 Построение SSA-формы4.3.1. Постановка задачи Для преобразования процедуры в SSA-форму компилятор должен:вставить в точки сбора необходимые -функции для каждойпеременнойпереименовать переменные (в том числе и временные) такимобразом, чтобы выполнялись следующие два правила:(1)каждое определение имеет индивидуальное имя; и(2)каждое использование ссылается на единственноеопределение.324.3 Построение SSA-формы4.3.2.
Базовый алгоритм построения SSA-формы Вход:программа в промежуточном представлении Выход:промежуточное представление программы в SSA-форме Метод:Выполнить следующие действия:(1)Вставить -функции:в начало каждого блока B, у которого|Pred(B)| > 1 вставить -функцию видаy = (y, y, ...) для каждого имени y, котороелибо определяется, либо используется в B.Вставленная -функция должна иметь по одномуаргументу для каждого B′ Pred(B):Порядок вставляемых -функций несуществен334.3 Построение SSA-формы4.3.2. Базовый алгоритм построения SSA-формы Вход:программа в промежуточном представлении Выход:промежуточное представление программы в SSA-форме Метод:Выполнить следующие действия:(2)Переименовать переменные:(a)вычислить достигающие определения;при этом только одно определение будетдостигать любого использования:это гарантируют вставленные -функции,которые тоже являются определениями;(b)переименовать каждое использование(как основных, так и временных)переменных таким образом, чтобы новоеимя соответствовало единственномуопределению, которое достигает его.344.3 Построение SSA-формы4.3.2.