Лекция 10. Заключение (Лекции (2015)), страница 2

является отношением частичного порядка.Для любой вершины n ГПУ каждый ациклический путьот Entry до n проходит через все доминаторы n,причем на всех таких путях доминаторы проходятсяв одном и том же порядке1910.1 Что было рассказано10.1.12. ДоминаторыВершина i ГПУ является непосредственным доминаторомвершины n (i idom n), если(1)i dom n(2)не существует вершины m, m  i, m n,такой что i dom m и m dom n.У каждой вершины n за исключением Entry существуетединственный непосредственный доминатор.Вершина s ГПУ является строгим доминатором вершины n(s sdom n), если s dom n и s n.Множество строгих доминаторов вершины n являетсяпересечением множеств доминаторов всех еепредшественников.2010.1 Что было рассказано10.1.12. ДоминаторыАлгоритм вычисления доминаторовОбласть определенияМножество подмножеств базовых блоковНаправление обходаForwardПередаточная функцияfB(x) = x {B}Граничное условиеOut [Entry] = EntryОперация сбора ()Система уравненийOut[ B]  f B ( In[ B])In[ B]  Out[ P]PPred ( B )Начальное приближениеOut [B] = N2110.1 Что было рассказано10.1.13.

SSA-формаФорма статического единственного присваивания (SSA)позволяет в каждой точке программы объединитьинформацию об имени переменнойс информацией о текущем значении этой переменной(или, что то же самое, с информацией о том, какое изопределений данной переменной определяет ее текущеезначение в данной точке). -функция определяет SSA-имя для значения своего аргумента,соответствующего ребру, по которому управление входит в блок.При входе в базовый блок все его  -функции выполняютсяодновременно и до любого другого оператора, определяяцелевые SSA-имена.2210.1 Что было рассказано10.1.13. SSA-форма Для преобразования процедуры в SSA-форму компилятор должен:вставить в точки сбора необходимые -функции для каждойпеременнойпереименовать переменные (в том числе и временные) такимобразом, чтобы выполнялись следующие два правила:(1)каждое определение имеет индивидуальное имя; и(2)каждое использование ссылается на единственноеопределение.2310.1 Что было рассказано10.1.13.

SSA-форма Частично усеченная SSA-форма содержит меньше  -функций,чем максимальная (но, к сожалению, как следует и из ее названияона содержит не минимально возможное количество  -функций).Чтобы не всегда вставлять  -функции необходимодля каждой точки сбора уметь выяснять, какие переменныенуждаются в  -функциях.Илидля каждого определения переменной уметь находить множествовсех точек сбора, которые нуждаются в  -функциях для значения,порожденного этим определением.2410.1 Что было рассказано10.1.14.

Граница доминированияМножество узлов m, удовлетворяющих условиям:n является доминатором предшественника mp  Pred(m) & n  Dom(p)(2)n не является строгим доминатором mn  (Dom (m) – {m}).называется границей доминирования n и обозначается DF(n).(1)Неформально: DF(n) содержит все первые узлы, которыедостижимы из n, на любом пути графа потока, проходящемчерез n, но над которыми n не доминирует.2510.1 Что было рассказано10.1.14. Граница доминирования Алгоритм построения границы доминированияШаг 1.Найти все точки сбора j графа потока, т.е. все узлы j, укоторых |Pred(j)| > 1.Шаг 2.Исследовать каждый узел p  Pred(j) и продвинутьсяпо дереву доминаторов, начиная с p и вплоть донепосредственного доминатора j: при этом j входит всостав границы доминирования каждого из пройденныхузлов, за исключением непосредственного доминатора j.2610.1 Что было рассказано10.1.15.

Размещение -функцийПеременная, которая используется только в одном блоке, неможет иметь живой -функции. Поэтому  -функции нужновставлять только для глобальных имен.Для этого вычисляется множество глобальных имен Globals.При этом используются результаты анализа живых переменных.Алгоритм вычисления множества Globals попутно вычисляетдля каждого базового блока B множество defB и для каждойx Globals – множество Blocks(x) базовых блоков B,в которых x defB.2710.1 Что было рассказано10.1.15. Размещение -функцийАлгоритм построения множеств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}}28}10.1 Что было рассказано10.1.15.

Размещение -функцийАлгоритм размещения-функций Вход: исходный граф потока Выход: преобразованный граф потока Метод: Выполнить следующие действия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};}}2910.1 Что было рассказано10.1.16. Алгоритм переименования переменных Вход:программа с размещенными -функциями Выход:программа, в которой переменным сопоставлены ихSSA-имена Метод:Сначала (в основном алгоритме) инициализируются стекии счетчики, после чего из корня дерева доминаторов n0вызывается рекурсивная функция Rename.Rename обрабатывает блок, рекурсивно вызывая егопоследователей по дереву доминаторов.Закончив обрабатывать очередной блок, Renameвыталкивает из стеков все имена, помещенные в них вовремя обработки блока.Функция NewName, манипулируя со счетчиками истеками, в случае необходимости создает новые имена.3010.1 Что было рассказано10.1.16.

Алгоритм переименования переменныхОсновной алгоритм:for each i  Globals do{counter[i] = 0;stack[i] = ;};Rename(n0);Функция NewName:NewName(n) {i = counter[n];counter[n] += 1;Push ni onto stack[n];return ni}3110.1 Что было рассказано10.1.16. Алгоритм переименования переменныхФункция Rename(B) :for each -function  B: x = (…) dorename x as NewName(x);for each instruction  B: x  op, y, z do{rewrite y as top(stack[y]);rewrite z as top(stack[z]);rewrite x as NewName(x);for each successor of B in the flowgraph dofill in -function parameters;for each successor S of B in thedominator tree do Rename(S)for each -function  B: x = (…)doPop(stack[x]);for each instruction  B: x  op, y, z doPop(stack[x]);3210.1 Что было рассказано10.1.17.

Восстановление кода из SSA-формыМожно оставить SSA-имена неизменными, заменив каждую-функцию группой команд копирования (по одной для каждоговходного ребра), предоставив разбираться с именамиоптимизирующему преобразованию «Распространение копий».В рассматриваемом примере при удалении -функций будет:3310.1 Что было рассказано10.1.18. Нумерация значений в суперблоках Расширенный базовый блок или суперблок E – это множествобазовых блоков B1, B2, …, Bn, где у блока B1 может быть несколькопредшественников (они не входят в состав суперблока), а каждый изблоков Bi, 2  i  n имеет в суперблоке единственногопредшественника.Блоки Bi  E формируют дерево с корнем B1.У суперблока E может быть несколько выходов на блоки (илисуперблоки), не входящие в состав E. Алгоритм нумерации значений в суперблоках будем называтьрасширенным алгоритмом локальной нумерации значений. Используется стек (обход дерева блоков)3410.1 Что было рассказано10.1.19.

Рекурсивный алгоритм глобальной нумерации значений(1) граф потока управления N, E, дерево доминаторов DTВход:(2) множество Val значений переменных, констант ивыраженийВыход: отображение VN: Val  N  {0} (N – множество натуральныхчисел), ставящее в соответствие каждому значению его номер:натуральное число или 0.Метод:procedure DBGVN(Block B)||Обработка -функцийОтметить начало новой области именfor each p  B, где p – -функция вида “n  (…)”if p бессмысленна или избыточнапоместить номер значения p в VN[n]удалить pelse VN[n]  n;добавить p в ТЗ3510.1 Что было рассказано10.1.19. Рекурсивный алгоритм глобальной нумерации значений(2) Обработка остальных инструкцийfor each aB где a – присваивание вида “x  op, y, z”заменить y на VN[y] и z на VN[z]expr  op, y, z|| expr – вход в ТЗif expr может быть упрощено до exprЗаменить a на “x  expr ”expr  exprif expr имеется в ТЗ с номером vVN[x]  vУдалить aelse Добавить expr в ТЗ с номером x VN[x]  x3610.1 Что было рассказано10.1.19.

Рекурсивный алгоритм глобальной нумерации значений(2) Обработка остальных инструкцийfor each aB где a – присваивание вида “x  op, y, z”заменить y на VN[y] и z на VN[z]expr  op, y, z|| expr – вход в ТЗif expr может быть упрощено до exprЗаменить a на “x  expr ”expr  exprif expr имеется в ТЗ с номером vVN[x]  vУдалить aelse Добавить expr в ТЗ с номером x VN[x]  x3710.1 Что было рассказано10.1.19.

Рекурсивный алгоритм глобальной нумерации значений(3) Окончание обработки блока B и переход к обработке его дочернихблоков (по дереву доминаторов)for each s  Succ(B)скорректировать входы -функций в sfor each дочернего блока c узла B по дереву доминаторовDBGVN (c)|| рекурсивный вызовОчистить ТЗ при выходе из области (стэк)3810.1 Что было рассказано10.1.20 Распространение копий Пусть в оптимизируемой процедуре есть инструкция копированияx  yРаспространение копий означает замену всех последующихвхождений переменной x на переменную y.Рассмотрим множество всех команд копирования анализируемойпроцедуры.