Построение частично-усечённой SSA формы (домашние задания)
Описание файла
Файл "Построение частично-усечённой SSA формы" внутри архива находится в следующих папках: домашние задания, Домашние задания (avasite), домашнее задание 4. PDF-файл из архива "домашние задания", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Граф Потока Управления (ГПУ)entryL2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1Алгоритм начинается на слайде 51, 4-й лекцииL1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4exitПостроение дерева доминаторовГПУДерево доминаторовL0:L0:L1:L2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1L1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L2:L3:L4:L5:L6:L7:L8:L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8n012345678Pred(n)Ø0,611,233,4567Dom(n)00,10,1,20,1,30,1,3,40,1,3,50,1,3,5,60,1,3,5,6,70,1,3,5,6,7,8Idom(n)Ø01133567Построение границы доминированияДерево доминаторов:L0:ГПУL1:L0:L2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1L1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8L2:У графа – 3 точки сбора – L1, L3, L5Разберём узлы по очереди – сейчас L3L3:L4:L5:L6:Границу доминирования здесь я находил не всоответствии с определением на странице 46,а в соответствии с примером на слайде 52L7:L8:Pred (3) = (1, 2), Idom(3) = 1, теперь на дереведоминаторов – пройдём от 1 и 2 до 1 ипоставим 3 в таблицу в соответствующихместахn012345678DF(Bn)ØØ3ØØØØØØПостроение границы доминированияДерево доминаторов:L0:ГПУL1:У графа – 3 точки сбора – L1, L3, L5Разберём узлы по очереди – сейчас L1L0:L2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1L7:31 t4 < -132 return t4L8L3:L4:L5:L6:L1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L2:L7:Pred (1) = (0, 6), Idom(1) = 0, теперь надереве доминаторов – пройдём от 0 и6 до 0 и поставим 1 таблицу всоответствующих местахL8:n012345678DF(Bn)Ø131Ø11ØØПостроение границы доминированияДерево доминаторов:L0:ГПУL1:L0:L2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1L1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8L2:У графа – 3 точки сбора – L1, L3, L5Разберём узлы по очереди – сейчас L5L3:L4:L5:L6:L7:Pred (5) = (3, 4), Idom(5) = 3, теперь надереве доминаторов – пройдём от 3 и4 до 3 и поставим 5 таблицу всоответствующих местахL8:n012345678DF(Bn)Ø131511ØØПостроение множества Globals и BlocksГПУL0:L2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1L1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8Для каждого блока перебираем все переменныевнутри неё, и если эта переменная не принадлежит defэтого блока, то она добавляется в globalsGlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5Размещение ф - функцийГПУL0:L2:11 t4 < m;12 return t4;L3:m = Ф (m,m)14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:l = Ф(l, l)m = Ф (m,m)24 l < +, m, 1L1:l = Ф (l, l)r = Ф (r,r)a = Ф (a,a)v = Ф (v,v)m = Ф (m,m)02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8Алгоритм на 58 слайде 4-й лекцииДля каждого имени, для каждого блока этой globalпеременной, для каждого блока из границыдоминирования для этого блока, вставляем функциюдля этой переменной.GlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5n012345678DF(Bn)Ø131511ØØПереименование переменныхL0:Дерево доминаторов:L1:ГПУL2:L0:L2:11 t4 < m2;12 return t4;L3:m3 = Ф (m2)14 t5 < *, 4, m315 t6 < +, a0, t516 t7 < a0[t6]17 ifTrue t7 > v018 goto L419 else20 goto L5L4:22 r < -, m3, l1L5:l = Ф(l1)m = Ф (m3)24 l < +, m, 1L1:l1 = Ф (l0, l)r1 = Ф (r0,r)a1 = Ф (a0,a)v1 = Ф (v0,v)m1 = Ф (m0,m)02 t1 < +, l1, r103 m2 < /, t1, 204 t2 < *, 4, m205 t3 < a1[t2]06 ifTrue t3 == v107 goto L208 else09 goto L3L6:26 ifTrue r >= l27 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8По алгоритму с 66 и 67 слайда.Обходим дерево доминаторов начиная с корня,рекурсивно в глубь и для каждого блока делаемпереименование на основе стека в таблицеL3:L4:L5:L6:L7:L8:На этом слайде сделано 5 шагов – для L0, L1, L2,L3 и L4GlobalslravmСчётчики11114Стекиl0r0a0v0m0m1m2m3Переименование переменныхL0:Дерево доминаторов:L1:ГПУL2:L0:L2:11 t4 < m2;12 return t4;L3:m3 = Ф (m2)14 t5 < *, 4, m315 t6 < +, a0, t516 t7 < a0[t6]17 ifTrue t7 > v018 goto L419 else20 goto L5L4:22 r1 < -, m3, l1L5:l2 = Ф(l1)m4 = Ф (m3)24 l2 < +, m4, 1L1:l1 = Ф (l0, l2)r1 = Ф (r0,r1)a1 = Ф (a0,a1)v1 = Ф (v0,v1)m1 = Ф (m0,m4)02 t1 < +, l1, r103 m2 < /, t1, 204 t2 < *, 4, m205 t3 < a1[t2]06 ifTrue t3 == v107 goto L208 else09 goto L3L6:26 ifTrue r1 >= l227 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8По алгоритму с 66 и 67 слайда.Обходим дерево доминаторов начиная с корня,рекурсивно в глубь и для каждого блока делаемпереименование на основе стека в таблицеL3:L4:L5:L6:L7:L8:L5, L6, L7, L8GlobalslravmСчётчики31114Стекиl0r0a0v0m0l1m1l2m2m3Частично-усечённая SSA-формаL0:Дерево доминаторов:L1:ГПУL2:L0:L2:11 t4 < m2;12 return t4;L3:m3 = Ф (m2)14 t5 < *, 4, m315 t6 < +, a0, t516 t7 < a0[t6]17 ifTrue t7 > v018 goto L419 else20 goto L5L4:22 r1 < -, m3, l1L5:l2 = Ф(l1)m4 = Ф (m3)24 l2 < +, m4, 1L1:l1 = Ф (l0, l2)r1 = Ф (r0,r1)a1 = Ф (a0,a1)v1 = Ф (v0,v1)m1 = Ф (m0,m4)02 t1 < +, l1, r103 m2 < /, t1, 204 t2 < *, 4, m205 t3 < a1[t2]06 ifTrue t3 == v107 goto L208 else09 goto L3L6:26 ifTrue r1 >= l227 goto L128 else29 goto L7L7:31 t4 < -132 return t4L8РезультатL3:L4:L5:L6:L7:L8:.
