brotikovskaya_420_task4 (домашние задания)
Описание файла
Файл "brotikovskaya_420_task4" внутри архива находится в следующих папках: домашние задания, Домашние задания (danuta). PDF-файл из архива "домашние задания", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA Entry End B1 01 i < 1 02 j < 0 03 goto L5 B9 L5: 39 ifTrue i < M 40 goto L4 41 else 42 goto L6 B2 L4: 05 goto L2 B3 L7: 15 t2 < *, 4, j 16 t3 < p[t2] 17 t4 < *, 4, i 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 B10 L6: Бротиковская Данута, 420 группа Исходный граф потока управления End Entry B10 B1 B9 B2 B5 L2: 10 ifTrue j > 0 11 goto L7 12 else 13 goto L3 B4 L1: 07 t1 < -‐, j, 1 08 j < d[t1] B5 B6 L3: 24 t6 < *, 4, j 25 t7 < p[t6] 26 t8 < *, 4, i 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: 35 t10 < *, 4, i 36 d[t10] < j 37 i < +, i, 1 B3 B4 B6 B7 B7 L8: 33 j < +, j, 1 B8 End Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Построение дерева доминаторов Entry Бротиковская Данута, 420 группа B1 B10 B1 B9 B9 B2 B10 B5 B2 B3 B8 B7 B4 B5 B4 B6 Дерево доминаторов B3 B6 B7 № БЛОКА 1 2 3 4 5 6 7 8 9 10 PRED {} {9} {5} {3} {2, 4} {3, 5} {6} {6, 7} {1,8} {9} DOM {} {1, 2, 9} {1, 2, 9, 5, 3} {1, 9, 2, 3, 4} {1, 2, 9, 5} {1, 2, 9, 5, 6} {1, 2, 9, 5, 6, 7} {1, 2, 9, 5, 6, 8} {1, 9} {1, 9, 10} IDOM -‐ 9 5 3 2 5 6 6 1 9 B8 Граф потока управления End B10 Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Построение границ доминирования Entry Бротиковская Данута, 420 группа Точки сбора – B5, B6, B8, B9 B1 B1 B9 B9 B2 B2 B10 B5 B3 B5 B4 B6 B8 B7 B4 B3 Дерево доминаторов B6 B7 B8 Граф потока управления № БЛОКА 1 2 3 4 5 6 7 8 9 10 PRED {} {9} {5} {3} {2, 4} {3, 5} {6} {6, 7} {1,8} {9} IDOM -‐ 9 5 3 2 5 6 6 1 9 End B10 Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA. Построение границ доминирования Entry Бротиковская Данута, 420 группа Точки сбора – B5, B6, B8, B9 Текущая точка сбора – B5 Pred(B5) = {2, 4} Idom(B5) = 2 B1 B9 B2 B1 B9 B2 B10 B5 B3 B5 B4 B6 B8 B7 B4 B3 Дерево доминаторов B6 B7 B8 Граф потока управления № БЛОКА 1 2 3 4 5 6 7 8 9 10 PRED {} {9} {5} {3} {2, 4} {3, 5} {6} {6, 7} {1,8} {9} IDOM -‐ 9 5 3 2 5 6 6 1 9 DF {} {} {5} {5} {5} {} {} {} {} {} End B10 Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Построение границ доминирования Entry Бротиковская Данута, 420 группа Точки сбора – B5, B6, B8, B9 Текущая точка сбора – B6 Pred(B6) = {3, 5} Idom(B6) = 5 B1 B9 B2 B1 B9 B2 B10 B5 B3 B5 B4 B6 B8 B7 B4 B3 Дерево доминаторов B6 B7 B8 Граф потока управления № БЛОКА 1 2 3 4 5 6 7 8 9 10 PRED {} {9} {5} {3} {2, 4} {3, 5} {6} {6, 7} {1,8} {9} IDOM -‐ 9 5 3 2 5 6 6 1 9 DF {} {} {5, 6} {5} {5} {} {} {} {} {} End B10 Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA. Построение границ доминирования Entry Бротиковская Данута, 420 группа Точки сбора – B5, B6, B8, B9 Текущая точка сбора – B6 Pred(B8) = {6, 7} Idom(B8) = 6 B1 B9 B2 B1 B9 B2 B10 B5 B3 B5 B4 B6 B8 B7 B4 B3 Дерево доминаторов B6 B7 B8 Граф потока управления № БЛОКА 1 2 3 4 5 6 7 8 9 10 PRED {} {9} {5} {3} {2, 4} {3, 5} {6} {6, 7} {1,8} {9} IDOM -‐ 9 5 3 2 5 6 6 1 9 DF {} {} {5, 6} {5} {5} {} {8} {} {} {} End B10 Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Построение границ доминирования Entry Бротиковская Данута, 420 группа Точки сбора – B5, B6, B8, B9 Текущая точка сбора – B9 Pred(B9) = {1, 8} Idom(B9) = 1 B1 B9 B2 B1 B9 B2 B10 B5 B3 B5 B4 B6 B8 B7 B4 B3 Дерево доминаторов B6 B7 B8 Граф потока управления № БЛОКА 1 2 3 4 5 6 7 8 9 10 PRED {} {9} {5} {3} {2, 4} {3, 5} {6} {6, 7} {1,8} {9} IDOM -‐ 9 5 3 2 5 6 6 1 9 DF {} {9} {5, 6} {5} {5, 9} {9} {8} {9} {9} {} Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA. Построение Globals и Blocks Entry End B1 01 i < 1 02 j < 0 03 goto L5 B9 L5: 39 ifTrue i < M 40 goto L4 41 else 42 goto L6 B2 L4: 05 goto L2 B3 L7: 15 t2 < *, 4, j 16 t3 < p[t2] 17 t4 < *, 4, i 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 Бротиковская Данута, 420 группа № БЛОКА 1 2 3 4 5 6 7 8 9 10 DF {} {9} {5, 6} {5} {5, 9} {9} {8} {9} {9} {} B10 L6: B5 L2: 10 ifTrue j > 0 11 goto L7 12 else 13 goto L3 B4 L1: 07 t1 < -‐, j, 1 08 j < d[t1] B6 L3: 24 t6 < *, 4, j 25 t7 < p[t6] 26 t8 < *, 4, i 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: 35 t10 < *, 4, i 36 d[t10] < j 37 i < +, i, 1 B7 L8: 33 j < +, j, 1 Globals i j p d Blocks {1, 8} {1, 4, 7} {} {8} Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Вставка фи-‐функций Entry End B1 01 i < 1 02 j < 0 03 goto L5 B9 L5: i = Ф(i, i) 39 ifTrue i < M 40 goto L4 41 else 42 goto L6 B10 L6: B2 L4: 05 goto L2 B5 L2: 10 ifTrue j > 0 11 goto L7 12 else 13 goto L3 B3 L7: 15 t2 < *, 4, j 16 t3 < p[t2] 17 t4 < *, 4, i 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 B4 L1: 07 t1 < -‐, j, 1 08 j < d[t1] Бротиковская Данута, 420 группа № БЛОКА 1 2 3 4 5 6 7 8 9 10 DF {} {9} {5, 6} {5} {5, 9} {9} {8} {9} {9} {} B6 L3: 24 t6 < *, 4, j 25 t7 < p[t6] 26 t8 < *, 4, i 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: 35 t10 < *, 4, i 36 d[t10] < j 37 i < +, i, 1 B7 L8: 33 j < +, j, 1 Globals i j p d Blocks {1, 8} {1, 4, 7} {} {8} Размещаем фи-‐функцию для i в блоке 9 Entry Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Вставка фи-‐функций B1 01 i < 1 02 j < 0 03 goto L5 B9 L5: i = Ф(i, i) d = Ф(d, d) 39 ifTrue i < M 40 goto L4 41 else 42 goto L6 B2 L4: 05 goto L2 B3 L7: 15 t2 < *, 4, j 16 t3 < p[t2] 17 t4 < *, 4, i 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 End Бротиковская Данута, 420 группа № БЛОКА 1 2 3 4 5 6 7 8 9 10 DF {} {9} {5, 6} {5} {5, 9} {9} {8} {9} {9} {} B10 L6: B5 L2: j = Ф(j, j) 10 ifTrue j > 0 11 goto L7 12 else 13 goto L3 B4 L1: 07 t1 < -‐, j, 1 08 j < d[t1] B6 L3: 24 t6 < *, 4, j 25 t7 < p[t6] 26 t8 < *, 4, i 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: j = Ф(j, j) 35 t10 < *, 4, i 36 d[t10] < j 37 i < +, i, 1 B7 L8: 33 j < +, j, 1 Globals i j p d Blocks {1, 8} {1, 4, 7} {} {8} Размещаем фи-‐функции для j в блоках 5 и 8 Entry Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Вставка фи-‐функций B1 01 i < 1 02 j < 0 03 goto L5 B9 L5: i = Ф(i, i) d = Ф(d, d) 39 ifTrue i < M 40 goto L4 41 else 42 goto L6 B2 L4: 05 goto L2 B3 L7: 15 t2 < *, 4, j 16 t3 < p[t2] 17 t4 < *, 4, i 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 End B10 L6: B5 L2: j = Ф(j, j) 10 ifTrue j > 0 11 goto L7 12 else 13 goto L3 B4 L1: 07 t1 < -‐, j, 1 08 j < d[t1] Бротиковская Данута, 420 группа Создаем пустой стек и нулевой счетчик для каждой переменной Globals i j p d Counter 0 0 0 0 Globals i j p d Stack {} {} {} {} B1 B9 B6 L3: 24 t6 < *, 4, j 25 t7 < p[t6] 26 t8 < *, 4, i 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: j = Ф(j, j) 35 t10 < *, 4, i 36 d[t10] < j 37 i < +, i, 1 B7 L8: 33 j < +, j, 1 B10 B2 B5 B3 B4 B6 B7 B8 Дерево доминаторов Entry Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Переименование переменных B1 01 i0 < 1 02 j0 < 0 03 goto L5 B9 L5: i1 = Ф(i0, i2) d0 = Ф(d1) 39 ifTrue i1 < M 40 goto L4 41 else 42 goto L6 B2 L4: 05 goto L2 B3 L7: 15 t2 < *, 4, j1 16 t3 < p[t2] 17 t4 < *, 4, i1 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 End B10 L6: B5 L2: j1 = Ф(j0, j2, j4) 10 ifTrue j1 > 0 11 goto L7 12 else 13 goto L3 B4 L1: 07 t1 < -‐, j1, 1 08 j2 < d[t1] Бротиковская Данута, 420 группа Создаем пустой стек и нулевой счетчик для каждой переменной Globals i j p d Counter 3 5 0 2 Globals i j p d Stack {} {} {} {} B1 B9 B6 L3: 24 t6 < *, 4, j1 25 t7 < p[t6] 26 t8 < *, 4, i1 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: j4 = Ф(j1, j3) 35 t10 < *, 4, i1 36 d1[t10] < j3 37 i2 < +, i1, 1 B7 L8: 33 j3 < +, j1, 1 B10 B2 B5 B3 B4 B6 B7 B8 Дерево доминаторов Entry Домашнее задание №4 по курсу “Конструирование компиляторов” Построение SSA.
Переименование переменных B1 01 i0 < 1 02 j0 < 0 03 goto L5 B9 L5: i1 = Ф(i0, i2) d0 = Ф(d1) 39 ifTrue i1 < M 40 goto L4 41 else 42 goto L6 B2 L4: 05 goto L2 B3 L7: 15 t2 < *, 4, j1 16 t3 < p[t2] 17 t4 < *, 4, i1 18 t5 < p[t4] 19 ifTrue t3 != t5 20 goto L1 21 else 22 goto L3 End Бротиковская Данута, 420 группа Результат B10 L6: B5 L2: j1 = Ф(j0, j2, j4) 10 ifTrue j1 > 0 11 goto L7 12 else 13 goto L3 B4 L1: 07 t1 < -‐, j1, 1 08 j2 < d[t1] B6 L3: 24 t6 < *, 4, j1 25 t7 < p[t6] 26 t8 < *, 4, i1 27 t9 < p[t8] 28 ifTrue t7 = t9 29 goto L8 30 else 31 goto L9 B8 L9: j4 = Ф(j1, j3) 35 t10 < *, 4, i1 36 d1[t10] < j3 37 i2 < +, i1, 1 B7 L8: 33 j3 < +, j1, 1 .
