Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Лекция 04. Форма статического единственного присваивания (SSA-форма)

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

PDF-файл Лекция 04. Форма статического единственного присваивания (SSA-форма) (Лекции (2015)) Конструирование компиляторов (52917): Лекции - 7 семестрЛекция 04. Форма статического единственного присваивания (SSA-форма) (Лекции (2015)) - PDF (52917) - СтудИзба2019-09-18СтудИзба

Описание файла

Файл "Лекция 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]PPred ( 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.

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
456
Средний доход
с одного платного файла
Обучение Подробнее