brotikovskaya_420_task2 (домашние задания)
Описание файла
Файл "brotikovskaya_420_task2" внутри архива находится в следующих папках: домашние задания, Домашние задания (danuta). PDF-файл из архива "домашние задания", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Домашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кодаEntryB101 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:15 t2 < *, 4, j16 t3 < p[t2]17 t4 < *, 4, i18 t5 < p[t4]19 ifTrue t3 != t520 goto L121 else22 goto L3B10L6:Бротиковская Данута, 420 группаИсходный граф потокауправленияEndEntryB10B1B9B2B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]B5B6L3:24 t6 < *, 4, j25 t7 < p[t6]26 t8 < *, 4, i27 t9 < p[t8]28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B3B4B6B7B7L8:33 j < +, j, 1B8Домашнее задание №2 по курсу “Конструирование компиляторов”Найти бесполезный код.
Построение обратной границы доминированияEndB10EntryТочки сбора – B3, B5, B6, B9B10B9Pred(B3) = {4, 6}IDOM(B3) = {6}B1Pred(B5) = {3, 6}IDOM(B5) = {6}B9B7B6B3Pred(B6) = {7, 8}IDOM(B6) = {8}B2B1B8B5B4B2Pred(B9) = {2, 10}IDOM(B9) = {10}Обратное дерево доминаторовB5B4№БЛОКА12345678910PRED{9}{4, 5}{4, 6}{5}{3, 6}{7, 8}{8}{9}{2, 10}{}DOM{1,9, 10}{2, 5, 6,8, 9, 10}{3, 6, 8,9, 10}{4, 5, 6,8, 9,10}{5, 6, 8,9, 10}{6, 8, 9,10}{7, 8, 9,10}{8, 9,10}{9, 10}{}B8IDOM9565688910-Обратный ГПУRDF{}{9}{5}{3}{3, 9}{9}{6}{9}{9}{}B3B6B7Домашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кода. Проход MarkEntryB101 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:15 t2 < *, 4, j16 t3 < p[t2]17 t4 < *, 4, i18 t5 < p[t4]19 ifTrue t3 != t520 goto L121 else22 goto L3B10L6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]Бротиковская Данута, 420 группа№ БЛОКА12345678910RDF{}{9}{5}{3}{3, 9}{9}{6}{9}{9}{}Def{1, 2}{}{15-18}{7}{}{24-27}{33}{35-37}{}{}Помечаем полезные инструкции и ветви в соответствии скритериямиПомещаем эти инструкции в WorkList, отмечаемсоответствующие блокиWorkList – 1, 2, 8, 36, 37, 33B6L3:24 t6 < *, 4, j25 t7 < p[t6]26 t8 < *, 4, i27 t9 < p[t8]28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7 L8:33 j < +, j, 1GlobalsijpdBlocks{1, 8}{1, 4, 7}{}{8}Критерии полезности кода•вычисляет возвращаемое значениепроцедуры (return)•является обращением к функции вводавывода•вычисляет значение глобальнойпеременной (Globals)Домашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кода.
Проход MarkEntryB101 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:15 t2 < *, 4, j16 t3 < p[t2]17 t4 < *, 4, i18 t5 < p[t4]19 ifTrue t3 != t520 goto L121 else22 goto L3B10L6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]Бротиковская Данута, 420 группа№ БЛОКА12345678910RDF{}{9}{5}{3}{3, 9}{9}{6}{9}{9}{}Def{1, 2}{}{15-18}{7}{}{24-27}{33}{35-37}{}{}WorkList – 1, 2, 8, 36, 37, 33Берем каждую инструкцию из WorkList• Для всех операндов инструкции помечаются и добавляются вworklist их определения, те, что ещё не были помечены.Таким образом, еще помечаются инструкции 7 и 35•B6L3:24 t6 < *, 4, j25 t7 < p[t6]26 t8 < *, 4, i27 t9 < p[t8]28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7 L8:33 j < +, j, 1Помечаем инструкции ветвления вблоках и вносим их в WorkList,входящих в обратную границудоминирования выбраннойинструкцииДомашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кода.
Проход MarkEntryB101 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:15 t2 < *, 4, j16 t3 < p[t2]17 t4 < *, 4, i18 t5 < p[t4]19 ifTrue t3 != t520 goto L121 else22 goto L3B10L6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]Бротиковская Данута, 420 группа№ БЛОКА12345678910RDF{}{9}{5}{3}{3, 9}{9}{6}{9}{9}{}Def{1, 2}{}{15-18}{7}{}{24-27}{33}{35-37}{}{}Берем каждую инструкцию из WorkList• Для всех операндов инструкции помечаются и добавляются вworklist их определения, те, что ещё не были помечены.Таким образом, еще помечаются инструкции 7 и 35•B6L3:24 t6 < *, 4, j25 t7 < p[t6]26 t8 < *, 4, i27 t9 < p[t8]28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7 L8:33 j < +, j, 1Помечаем инструкции ветвления вблоках и вносим их в WorkList,входящих в обратную границудоминирования выбраннойинструкцииРезультат прохода Markпродемонстрирован на слайдеДомашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кода.
Проход SweepEntryB1Бротиковская Данута, 420 группа01 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:19 ifTrue t3 != t520 goto L121 else22 goto L3B10L6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]B6L3:28 ifTrue t7 = t929 goto L830 else31 goto L9№ БЛОКА12345678910IDOM9565688910-RDF{}{9}{5}{3}{3, 9}{9}{6}{9}{9}{}B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7 L8:33 j < +, j, 1Рассматриваем непомеченныеинструкцииДля инструкций ветвлениязаменяем переходы на переходына ближайшие постдоминаторыНепомеченные инструкцииприсваивания удаляемРезультат продемострирован наслайде – удалены инструкции15-18 и 24-27Домашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кодаEntryB1L4:05 goto L2B3L7:19 ifTrue t3 != t520 goto L121 else22 goto L3Бротиковская Данута, 420 группаРезультат удаления бесполезного кода01 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndB10L6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]B6L3:28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7 L8:33 j < +, j, 1Домашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кода.
Удаление недостижимого кодаEntryB1Бротиковская Данута, 420 группа01 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:19 ifTrue t3 != t520 goto L121 else22 goto L3B10•Для определения недостижимогокодаобходимграфпотокауправления в глубину•НепомеченныенедостижимыL6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]B6L3:28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7L8:33 j < +, j, 1блоки-Домашнее задание №4 по курсу “Конструирование компиляторов”Удаление бесполезного кода.
Удаление недостижимого кодаEntryB1Бротиковская Данута, 420 группа•01 i < 102 j < 003 goto L5B9L5:39 ifTrue i < M40 goto L441 else42 goto L6B2EndL4:05 goto L2B3L7:19 ifTrue t3 != t520 goto L121 else22 goto L3B10Результат – все блоки достижимыL6:B5L2:10 ifTrue j > 011 goto L712 else13 goto L3B4L1:07 t1 < -, j, 108 j < d[t1]B6L3:28 ifTrue t7 = t929 goto L830 else31 goto L9B8L9:35 t10 < *, 4, i36 d[t10] < j37 i < +, i, 1B7 L8:33 j < +, j, 1.
