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

aBlocks(a) = {B1, B3}, так что алгоритм должен вставить -функцию для a в каждый блок из границ доминированияDF(B1) =  и DF(B3) = {B7}.Вставив -функцию для a в B7, получим новое определение a– -функцию, вставленную в B7. Следовательно, необходимовключить B7 в WorkList и вставить -функцию для a в каждыйблок из DF(B7) = {B1}. Но B1 уже имеется в WorkList, так что,DF(B7) не добавляется к WorkList.xaBlocks(x) {B7, B1}b{B7, B1}cdi{B7, B1, B6} {B7, B1, B6} {B1}634.4 Построение частично усеченной SSA-формы4.4.7. Размещение -функцийПример.B0i  1B5c B1abcdiabbcddB7abcdyziadB2B4(a,a)(b,b)(c,c)(d,d)(i,i)B3(a,a)(b,b)(c,c)(d,d)+, a, b+, c, d+, i, 1B6 c  (c,c)d  (d,d)b 644.4 Построение частично усеченной SSA-формы4.4.8. Переименование переменныхАлгоритм Вход:программа с размещенными -функциями Выход:программа, в которой переменным сопоставлены ихSSA-имена Метод:Сначала (в основном алгоритме) инициализируются стекии счетчики, после чего из корня дерева доминаторов n0вызывается рекурсивная функция Rename.Rename обрабатывает блок, рекурсивно вызывая егопоследователей по дереву доминаторов.Закончив обрабатывать очередной блок, Renameвыталкивает из стеков все имена, помещенные в них вовремя обработки блока.Функция NewName, манипулируя со счетчиками истеками, в случае необходимости создает новые имена.654.4 Построение частично усеченной SSA-формы4.4.7.

Переименование переменныхАлгоритм Основной алгоритм: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}664.4 Построение частично усеченной SSA-формы4.4.7. Переименование переменных.Функция 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]);674.4 Построение частично усеченной SSA-формы4.4.8.

Переименование переменныхПрименим алгоритм переименования крассматриваемой программе в предположении, чтона входе в блок B0 определены имена a0, b0, c0, d0.B0i  1B5c B1abcdiabB7abcdyziB2b c d B3a d B4d B6(a,a)(b,b)(c,c)(d,d)(i,i)(a,a)(b,b)(c,c)(d,d)+, a, b+, c, d+, i, 1c  (c,c)d  (d,d)b 684.4 Построение частично усеченной SSA-формы4.4.8. Переименование переменныхБлок B0Состояние счетчиков и стековв момент вызова Rename(B0)Глобальныеa bcпеременныеdi0Счетчики1111Стекиa0b0c0d0Rename(B0)1) заменяет i на i0, увеличивает значение счетчика i изаталкивает i0 в соответствующий стек.2) заменяет первый параметр каждой -функции насоответствующие имена из текущего состоянияa0, b0, c0, d0, i0.3) вызывает по рекурсии сына B0 по деревудоминаторов – узел B1694.4 Построение частично усеченной SSA-формы4.4.8. Переименование переменныхБлок B0Когда в конце обхода дерева доминаторовуправление снова попадает в B0 Renameвыталкивает значение из стека для i и происходитвыход их нее.Состояние счетчиков и стеков в момент, когдаRename(B0) уже кончила обрабатывать блок B0,но еще не удалила имена, связанные с B0 изсоответствующих стековГлобальныеaBcdiпеременныеСчетчики11111Стекиa0b0c0d0i0704.4 Построение частично усеченной SSA-формы4.4.8.

Переименование переменныхБлок B1Rename(B1) по рекурсии во время обработки блока B0.На входе в блок B1 Rename1) заменяет имена, определяемые -функциями нановые имена a1, b1, c1, d1, i1.2) заменяет имена в определениях переменных a и cна a2 и c2.3) вызывает по рекурсии сыновей B1 по деревудоминаторов – узлы B2, B3 и B7.Когда управление снова попадает в B1Rename освобождает стеки и идет на выход.На выходе из B1ГлобальныепеременныеabcdiСчетчики32322Стекиa0b0c0d0i0a1b1c1d1i1a2c2714.4 Построение частично усеченной SSA-формы4.4.8. Переименование переменныхБлок B7 (последний)Rename(B7) по рекурсии из блока B1.1) заменяет имена, определяемые -функциями, создавая новыеимена a4, b4, c6 и d6.2) заменяет использования глобальных имен в двух присваиваниях, неменяя определяемых ими имен, так как ни y, ни z не являютсяглобальными.3) последнем присваивании заменяет используемое имя на i1, а затемсоздает новое имя i2 для определения переменной i.4) заменяет второй параметр каждой -функции в B1 (единственныйпоследователь по ГПУ) на соответствующее текущее имя(a4, b4, c6, d6 и i2).Потом Rename освобождает стеки, возвращается в B1, в B0и прекращает работу.724.4 Построение частично усеченной SSA-формы4.4.8.

Переименование переменныхБлок B7 (последний)Вход в B7ГлобальныепеременныеabcdiСчетчики44662Стекиa0b0c0d0i0a1b1c1d1i1a2Выход из B7Глобальныепеременныеc2abcdIСчетчики55773Стекиa0b0c0d0I0a1b1c1d1I1a2b4c2D6I2a4c6734.4 Построение частично усеченной SSA-формы4.4.8. Переименование переменныхПосле окончания работы алгоритма получимB0i0  1B5c4 B1a1b1c1d1i1a2b2B7a4b4c6d6yzi2B2b2 c3 d2 B3a3 d3 B4d4 B6(a0,(b0,(c0,(d0,(i0,a4)b4)c6)d6)i2)(a2, a3)(b2, b3)(c3, c5)(d2, d5)+, a4, b4+, c6, d6+, i1, 1c5  (c2, c4)d5  (d4, d3)b3 744.5 Восстановление кода из SSA-формы4.5.1. Постановка задачиПоскольку современные процессоры не выполняют -функций,компилятор должен перевести программу в SSA-форме ввыполняемый код.Рассмотрение примеров наводит на мысль, чтокомпилятору достаточно попросту опустить индексы имен иудалить -функции.Такой подход был бы правильным, если бы при построении SSAформы использовался простейший алгоритм.Однако, если переименования выполняются рассмотреннымалгоритмом, простой процесс переименованияможет привести к некорректному коду.754.5 Восстановление кода из SSA-формы4.5.1.

Постановка задачи Пример. Внизу слева показан базовый блок из четырех команд и егооптимизация с помощью ЛНЗ над исходными именами.Справа показан тот же самый пример с использованием SSA-имен.Вследствие того, что исходное имя a имеет разные SSA-именаa0 и a1, удалось оптимизировать последнее присваивание.Заметим однако, что если у имен опустить индексы, получитсянекорректный код: c будет присвоено значение 17.Исходные именаabac+, x, y+, x, y17+, x, yabac+, x, ya17+, x, ySSA-именаa0b0a0c0+, x0, y0+, x0, y017+, x0, y0a0b0a1c0+, x0, y0a017a0764.5 Восстановление кода из SSA-формы4.5.2. Замена -функций группами команд копированияМожно оставить SSA-имена неизменными, заменив каждую-функцию группой команд копирования (по одной для каждоговходного ребра), предоставив разбираться с именамиоптимизирующему преобразованию «Распространение копий».В рассматриваемом примере при удалении -функций будет:B7B7a4b4c6d6yzi2(a2, a3)(b2, b3)(c3, c5)(d2, d5)+, a4, b4+, c6, d6+, i1, 1y  +, a4, b4z  +, c6, d6i2  +, i1, 1B6 c5  (c2, c4)d5  (d4, d3)b3 B6 b3a4b4c6d6a2b2c3d2B2b2 c3 d2 B2b2c3d2a4b4c6d6a3b3c5d5774.5 Восстановление кода из SSA-формы4.5.2.

Замена -функций группами инструкций копированияB7B7a4b4c6d6yzi2(a2, a3)(b2, b3)(c3, c5)(d2, d5)+, a4, b4+, c6, d6+, i1, 1y  +, a4, b4z  +, c6, d6i2  +, i1, 1B6 c5  (c2, c4)d5  (d4, d3)b3 B6 b3a4b4c6d6B2b2 c3 d2 B2b2c3d2a4b4c6d6a2b2c3d2a3b3c5d5Удаление -функций из блока B6 породитинструкции копирования в блоках B4 и B5.Удаление -функций из блока B1 должнопородить инструкции копирования в блоках B0 и B7.Но этого делать нельзя!784.5 Восстановление кода из SSA-формы4.5.2. Замена -функций группами инструкций копированияУдаление -функций из блока B1 должнопородить инструкции копирования в блокахB0 и B7.

Но этого делать нельзя! Почему?У блоков B0 и B7 по два последующихблока (вторые блоки не попали на схему, таккак они находятся вне анализируемогоцикла).Если вставить копирования в конце B0 и B7,они будут выполняться не только на ребрах,внутри рассматриваемого цикла, но и наребрах выводящих из цикла (помеченыусловием i > 100).794.5 Восстановление кода из SSA-формы4.5.2. Замена -функций группами инструкций копированияПо определению ребро, выходящее извершины с несколькими потомками, ивходящее в вершину с несколькимипредками, называется критическим.Ребра (B0 B1) и (B7 B1) – критические.Критические ребра обычно исключают,разрывая их а вставляя в разрывдополнительные вершины.Разорвем критические ребра и добавим двановых блока B8 и B9, поместив в нихтребуемые инструкции копирования.804.5 Восстановление кода из SSA-формы4.5.2. Замена -функций группами инструкций копированияПо определению ребро, выходящее извершины с несколькими потомками, ивходящее в вершину с несколькимипредками, называется критическим.Ребра (B0 B1) и (B7 B1) – критические.Критические ребра обычно исключают,разрывая их а вставляя в разрывдополнительные вершины.Разорвем критические ребра и добавимдва новых блока B8 и B9, поместив в нихтребуемые инструкции копирования.814.5 Восстановление кода из SSA-формы4.5.2.

Замена -функций группами инструкций копированияB0B0B9B1B2B1B3B4B5B6B7B2B3B4B5 B8B6B782.