Тема 08(2016)SSA-форма (1161803), страница 3
Текст из файла (страница 3)
Переименование переменныхВход в B5a b c d iСчетчики44543Стеки ()a0b0c0d0i0a1b1c1d1i1a2abcdiСчетчики44543Стеки ()a0b0c0d0i0a1b1c1d1i 1c2d4a4a ...;d ...;(a d)…;Rename(B5)c2Вход в B6a2B5:B5:a4 ...;d4 ...;(a4 d4)…;Работа Rename(B5): Вызов NewName (a) a4; Вызов NewName (d) d4; Переименование операндов; Вызов Rename(B6);538.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхВход в B6a b c d iСчетчики54553Стеки ()a0b0c0d0i0a1b1c1d1i1c2d4a2B6 до чисткиabcdiСчетчики54563Стеки ()a0b0c0d0i0a1b1c1d1i1c2d4a4d ...;Rename(B6)B6:a4a2B6:d5 ...;Работа Rename(B6): Вызов NewName (d) d5; Переименование операндов; Заполнение параметров -функций в B7 Чистка стеков Вызов Rename(B7);d5548.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхВход в B7a b c d iСчетчики54563Стеки ()a0b0c0d0i0a1b1c1d1i1c2d4a2B7 до чисткиabcdiСчетчики55673Стеки ()a0b0c0d0i0a1b1c1d1i1a2b4c2d4c5d6c (c, c);d (d, d);b ...;Rename(B7)B7:a4a4B7:c5 (c2, c);d6 (d5, d);b4 ...;Работа Rename(B7): Вызов NewName (с) с5; Вызов NewName (d) d6; Вызов NewName (b) b4; Переименование операндов; Заполнение параметров -функций в B3 Чистка стеков55 Возврат в Rename(B5);8.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхB7 до чистки a b c d iСчетчики55673Стеки ()a0b0c0d0i0a1b1c1d1i1a2b4c2d4c5d6a4B3:a3 b3 c4 d3 x z i2 (i2 (a2,(b2,(c3,(d2,a);b);c);d);a3 + b3;c4 + d3;i1 + 1;100)…;Rename(B7)Работа Rename(B7): Заполнение параметров -функций в B3 Чистка стеков Возврат в Rename(B5);B3:a3 b3 c4 d3 x z i2 (i2 (a2,(b2,(c3,(d2,a4);b4);c5);d6);a3 + b3;c4 + d3;i1 + 1;100)…;568.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхБлок 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и прекращает работу.578.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхВход в B8a b c d iСчетчики54673Стеки ()a0b0c0d0i0a1b1c1d1i1c2d4a2B8:c ...;Rename(B8)B8:с6 ...;a4B8 до чисткиabcdiСчетчики55673Стеки ()a0b0c0d0i0a1b1c1d1i1a2c2d4a4c6Работа Rename(B8): Вызов NewName (с) с6; Переименование операндов;588.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхB8 до чистки a b c d iСчетчики55673Стеки ()a0b0c0d0i0a1b1c1d1i1a2c2d4a4c6B7:c5 (c2, c);d6 (d5, d);b4 ...;Rename(B8)B7:c5 (c2, c6);d6 (d5, d4);b4 ...;Работа Rename(B8): Заполнение параметров -функций в B7 Чистка стеков Возврат в Rename(B5);598.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхБлок B0Когда в конце обхода дерева доминаторовуправление снова попадает в B0 Renameвыталкивает значение из стека для i и происходитвыход их нее.Состояние счетчиков и стеков в момент, когдаRename(B0) уже кончила обрабатывать блок B0,но еще не удалила имена, связанные с B0 изсоответствующих стековГлобальныеaBcdiпеременныеСчетчики11111Стекиa0b0c0d0i0608.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхПосле окончания работы алгоритма получим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 618.4 Восстановление кода из SSA-формы8.4.1.
Постановка задачиПоскольку современные процессоры не выполняют -функций,компилятор должен перевести программу в SSA-форме ввыполняемый код.Рассмотрение примеров наводит на мысль, чтокомпилятору достаточно попросту опустить индексы имен иудалить -функции.Такой подход был бы правильным, если бы при построении SSAформы использовался простейший алгоритм.Однако, если переименования выполняются рассмотреннымалгоритмом, простой процесс переименованияможет привести к некорректному коду.628.4 Восстановление кода из SSA-формы8.4.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, y0a017a0638.4 Восстановление кода из SSA-формы8.4.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 b3a4b4c6d6a2b2c3d2B2b2 c3 d2 B2b2c3d2a4b4c6d6a3b3c5d5648.4 Восстановление кода из SSA-формы8.4.2.
Замена -функций группами инструкций копирования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 b3a4b4c6d6B2b2 c3 d2 B2b2c3d2a4b4c6d6a2b2c3d2a3b3c5d5Удаление -функций из блока B6 породитинструкции копирования в блоках B4 и B8.Удаление -функций из блока B1 должнопородить инструкции копирования в блоках B0 и B7.Но этого делать нельзя!658.4 Восстановление кода из SSA-формы8.4.2. Замена -функций группами инструкций копированияУдаление -функций из блока B1 должнопородить инструкции копирования в блокахB0 и B7.Но этого делать нельзя! Почему?У блоков B0 и B7 по два последующихблока (вторые блоки не попали на схему, таккак они находятся вне анализируемогоцикла).Если вставить копирования в конце B0 и B7,они будут выполняться не только на ребрах,внутри рассматриваемого цикла, но и наребрах выводящих из цикла (помеченыусловием i > 100).668.4 Восстановление кода из SSA-формы8.4.2.
Замена -функций группами инструкций копированияПо определению ребро, выходящее извершины с несколькими потомками, ивходящее в вершину с несколькимипредками, называется критическим.Ребра (B0 B1) и (B7 B1) – критические.Критические ребра обычно исключают,разрывая их и вставляя в разрывдополнительные вершины.Разорвем критические ребра и добавим двановых блока B8 и B9, поместив в нихтребуемые инструкции копирования.678.4 Восстановление кода из SSA-формы8.4.2. Замена -функций группами инструкций копированияПо определению ребро, выходящее извершины с несколькими потомками, ивходящее в вершину с несколькимипредками, называется критическим.Ребра (B0 B1) и (B7 B1) – критические.Критические ребра обычно исключают,разрывая их а вставляя в разрывдополнительные вершины.Разорвем критические ребра и добавимдва новых блока B8 и B9, поместив в нихтребуемые инструкции копирования.688.4 Восстановление кода из SSA-формы8.4.2.
Замена -функций группами инструкций копированияB0B0B9B1B2B1B3B4B5B6B7B2B3B4B5 B8B6B769.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
