Построение частично-усечённой SSA формы (1157374)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Граф Потока Управления (ГПУ)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:.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов курсовой работы