Тема 08(2016)SSA-форма (1161803), страница 2
Текст из файла (страница 2)
При вычислении Globalsиспользуются результаты анализа живых переменных.Алгоритм вычисления множества Globals попутно вычисляетдля каждого базового блока B множество defB и для каждойпеременной x Globals – множество Blocks(x) базовыхблоков B, в которых x defB.308.3 Построение частично усеченной SSA-формы8.3.2. Размещение -функцийАлгоритм построения множеств Globals и Blocks(x) Вход:ГПУ Выход:множество Globals,множества Blocks(x) для каждой переменной xмножества defB для каждого базового блока B. Метод:Выполнить следующие действия:318.3 Построение частично усеченной SSA-формы8.3.2. Размещение -функцийАлгоритм построения множеств 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}}32}8.3 Построение частично усеченной SSA-формы8.3.2.
Размещение -функцийАлгоритм размещения -функций Вход: исходный ГПУ Выход: преобразованный ГПУ Метод: Выполнить следующие действия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};}}338.3 Построение частично усеченной SSA-формы8.3.2. Размещение -функцийЗамечание 1. Для каждого блока B WorkList алгоритм вставляет -функцию в начало каждого блока D DF(B).Порядок -функций роли не играет.После вставления -функции для x в блок D алгоритм добавляет Dв WorkList, чтобы в дальнейшем учесть новое определение x вблоке D.348.3 Построение частично усеченной SSA-формы8.3.2. Размещение -функцийЗамечание 2.
Для улучшения эффективности алгоритманеобходимо избегать следующих двух видов дублирования:(1) помещение какого-либо блока в WorkList более одного разадля каждого глобального имени; для этого можно вести списокуже обработанных блоков (например, не удалять B изWorkList, а помечать его как уже обработанный).(2) рассматриваемый блок может входить в состав границдоминирования нескольких блоков, входящих в WorkList;чтобы избежать вставления дублирующих -функций дляпеременной x, можно использовать список блоков, которые ужесодержат -функции для x, что быстрее, чем проверять каждыйраз какие -функции включены.358.3 Построение частично усеченной SSA-формы8.3.3.
Размещение -функций. Пример.B0i 1B5c B1a b B3a d B2bcdbB7yzidB6B4 +, a, b +, c, d +, i, 1368.3 Построение частично усеченной SSA-формы8.3.3. Размещение -функций. Пример.Сначала вычисляются множества Globals и Blocks(x):Globals = {a, b, c, d, i}.Множества Blocks(x) представлены в таблице:abcdi{B1, B3}{B3, B6}{B1, B2, B5}{B2, B3, B4}{B0, B7}Алгоритму размещения -функций потребуются также ужевычисленные границы доминированияn01234567DF(Bn){B7}{B7}{B6}{B6}{B7}{B1}378.3 Построение частично усеченной SSA-формы8.3.3. Размещение -функций. Пример.Применяем алгоритм размещения -функций.Берем первую переменную из Globals = {a, b, c, d, i}, т.е . 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}388.3 Построение частично усеченной SSA-формы8.3.3. Размещение -функций. Пример.B0i 1B5c B1abcdiabbcddB7abcdyziadB2B4(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 398.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхАлгоритм Вход:программа с размещенными -функциями Выход:программа, в которой каждой переменной сопоставленоее SSA-имя. Метод:Сначала (в основном алгоритме) инициализируются стекии счетчики, после чего из корня дерева доминаторов n0вызывается рекурсивная функция Rename.Rename обрабатывает блок, рекурсивно вызывая егопоследователей по дереву доминаторов.Закончив обрабатывать очередной блок, Renameвыталкивает из стеков все имена, помещенные в них вовремя обработки блока.Функция NewName, манипулируя со счетчиками истеками, в случае необходимости создает новые имена.408.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхАлгоритмОсновной алгоритм: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}418.3 Построение частично усеченной SSA-формы8.3.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]);428.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхПрименим алгоритм переименования крассматриваемому примеру в предположении, чтона входе в блок B0 определены имена a0, b0, c0, d0.B0i 1B5c B1abcdiabB7abcdyziB2b 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 438.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхКорнем обрабатываемой части дерева доминаторов являетсяблок B0. Поэтому «Основной алгоритм», обнулив счетчики иопустошив стеки для переменных из множестваGlobals = {a, b, c, d, i}, сделает вызов Rename(B0).Порядок обработки базовых блоковопределяется деревом доминаторовпервым обрабатывается блок B0.во время обработки B0 будет вызванRename(B1),во время обработки B1 будут вызваныRename(B2), Rename(B3) и Rename(B5),во время обработки B3 будет вызванRename(B4)во время обработки B5 будут вызваныRename(B6), Rename(B7) и Rename(B8)448.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхКорнем обрабатываемой части дерева доминаторов являетсяблок B0. Поэтому «Основной алгоритм», обнулив счетчики иопустошив стеки для переменных из множестваGlobals = {a, b, c, d, i}, сделает вызов Rename(B0).Вход в B0abcdiСчетчики11110Стеки ()a0b0c0d0B0:i 1;Rename(B0): Вызов NewName (i) возвращает имя i0Замена i 1; на i0 1;Занесение i0 в стек для iУвеличение счетчика для i на 1Заполнение параметров -функций в B1Вызов Rename(B1)B0:i0 1;458.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхВход в B1 a bc d iСчетчики11111Стеки ()a0b0c0d0i0Работа Rename(B1): Вызов NewName (a) a1 Вызов NewName (b) b1 Вызов NewName (c) c1 Вызов NewName (d) d1 Вызов NewName (i) i1 Вызов NewName (a) a2 Вызов NewName (c) c2 Заполнение параметров функций в B2 отсутствует,так как в B2 нет -функций Вызов Rename(B2)B1:a b c d i a c (a <(a0,(b0,(c0,(d0,(i0,a);b);c);d);i);...;...;c);Rename(B1)B1:a1 b1 c1 d1 i1 a2 c2 (a2 <(a0,(b0,(c0,(d0,(i0,...;...;c2);a);b);c);d);i);468.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхВход в B2abcdiСчетчики32322Стеки ()a0 b0 c0 d0 i0a1B2:c2B2 до чисткиabcdiСчетчики33432b0c0d0i0b1c1d1i1b2c2d2c3b ...;c ...;d ...;Rename(B2)b1 c1 d1 i1a2Стеки ()B2:b2 ...;c3 ...;d2 ...;Работа Rename(B2): Вызов NewName (b) b2 Вызов NewName (c) c3 Вызов NewName (d) d2 Заполнение параметров -функций в B3 Чистка стеков Возврат в Rename(B1)478.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхB2 до чистки a b c d iСчетчики33432Стеки ()a0b0c0d0i0a1b1c1d1i1a2b2c2d2c3ПослечисткиabcdiСчетчики33432Стеки ()a0 b0 c0 d0 i0a1a2Работа Rename(B2): Вызов NewName (b) b2 Вызов NewName (c) c3 Вызов NewName (d) d2 Заполнение параметров -функций в B3 Чистка стеков Возврат в Rename(B1)b1 c1 d1 i1c2488.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхПосле B2abcdiСчетчики33432Стеки ()a0 b0 c0 d0 i0a1a2b1 c1 d1 i1c2Работа Rename(B1): Заполнение параметров функций в B3 проведено в B2 Вызов Rename(B3)498.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхВход в B3abcdiСчетчики33432Стеки ()a0b0c0d0i0a1b1c1d1i1a2B3:c2Работа Rename(B3): Вызов NewName (a) a3; Вызов NewName (b) b3; Вызов NewName (c) c4; Вызов NewName (d) d3; Вызов NewName (x) x1; Переименование операндов; Вызов NewName (z) z1; Переименование операндов; Вызов NewName (i) i2; Переименование операндов;a b c d x z i (i (a2,(b2,(c3,(d2,a);b);c);d);a + b;c + d;i + 1;100)…;Rename(B3)B3:a3 b3 c4 d3 x1 z1 i2 (i2 (a2,(b2,(c3,(d2,a);b);c);d);a3 + b3;c4 + d3;i1 + 1;100)…;508.3 Построение частично усеченной SSA-формы8.3.4.
Переименование переменныхB3 до чистки a b c d iСчетчики44543Стеки ()a0b0c0d0i0a1b1c1d1i1a2b3c2d3i2a3B3:a3 b3 c4 d3 x z i2 (i2 (a2,(b2,(c3,(d2,B1:a1 b1 c1 d1 i1 a2 c2 (a2 <(a0,(b0,(c0,(d0,(i0,c4Работа Rename(B3): Вызов Rename(B4); Заполнение параметров-функций в B1 Вызов Rename(B1); Чистка стековa);b);c);d);a3 + b3;c4 + d3;i1 + 1;100)…;a3);b3);c4);d3);i2);...;...;c2);518.3 Построение частично усеченной SSA-формы8.3.4. Переименование переменныхB3 послеa b c d iчисткиСчетчики44543Стеки ()a0b0c0d0i0a1b1c1d1i1a2B3:a3 b3 c4 d3 x z i2 (i2 (a2,(b2,(c3,(d2,B1:a1 b1 c1 d1 i1 a2 c2 (a2 <(a0,(b0,(c0,(d0,(i0,c2Работа Rename(B3): Возврат в Rename(B1);Работа Rename(B1): Заполнение параметров -функций в B5 непроизводится, так как в B5нет -функций Вызов Rename(B5);a);b);c);d);a3 + b3;c4 + d3;i1 + 1;100)…;a3);b3);c4);d3);i2);...;...;c2);528.3 Построение частично усеченной SSA-формы8.3.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
