Найти бесполезный код (1157366)
Текст из файла
Граф Потока Управления (ГПУ)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Алгоритм начинается на слайде 30, 6-й лекции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Построение обратной границы доминированияГПУДереводоминаторовL0L0L1L2L1L2L3L4L3L5L4L5L6L6L7L7L8Для построения рассмотрим обратный граф.По нему построим множество Pred и Dom, и множество IDOM(непосредственных доминаторов), по ним построим дереводоминаторов, а по нему построим DF(n) – границудоминирования.Которая будет являться обратной границей доминирования дляисходного графа.(Границу доминирования здесь я находил не в соответствии сопределением на странице 46, а в соответствии с примером наслайде 52, 4-й лекции):У графа 3 точки сбора: L6, L3, L1.
Разберём узлы по очерединачиная с L6. Pred (6) = 1,7 idom(6)=7. Значит теперь в дереведоминаторов пройдём от 1 и 7 до 7 и поставим 6 всоответствующих местых таблицы. (аналогично для остальных 3,1)n012345678Pred(n)12,334,5561,78ØDom(n)0,1,3,5,6,7,81,3,5,6,7,82,3,5,6,7,83,5,6,7,84,5,6,7,85,6,7,86,7,87,88IDom(n)13355678ØDF(n)Ø717377ØØL8Проход MarkКритерий полезности инструкции:ГПУ•вычисляет возвращаемое значение процедуры (return)•является обращением к функции ввода-вывода (в данном фрагменте невстречается)•вычисляет значение глобальной переменной, доступной из других процедур(множество Globals будет подробно вычислено в домашнем задании номер 4,на слайде номер 6)•ее результат используется в других полезных инструкциях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, 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 t4exitGlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5n01 2 3 4 5 67 8RDF(n)Ø 7 1 7 3 7 7Ø ØПроанализируем алгоритм Прохода MarkWorkList <- (пустое множество)for each инструкции i (x <- op, y, z ::: пометка) -- т.е.
для каждой инструкции мы вычисляем полезна ли она, после чего идём в цикл нижеубрать пометку у iif (i полезная) пометить iWorkList <- WorkList и {i}while (WorkList не пусто) -- в цикле мы просто добавляем все def от операторов исходного исследуемого выражения в forremove i from WorkListif (def(y) не помечена)пометить def(y)WorkList <- WorkList и {def(y)}if (def(z) не помечена)пометить def(z)WorkList <- WorkList и {def(z)}for each block b в множестве RDF(block(i)) -- и для каждого блока из множества обратной границы доминирования мы помечаем ветвь ведущую к этому блокупусть j ветвь, оканчивающаяся в bif (j не помечена)пометить jWorkList <- WorkList и {j}Проход MarkГПУНа данном шаге мы рассмотрели первую операцию(под номером 02), и пометили её, так же мыпометили блок, к которому она принадлежит, и теоперации, которые отвечают def её операторов, т.е.def(l) и def(r).Критерий полезности инструкции:•вычисляет возвращаемое значение процедуры (return)Обратная граница доминирования блока 1 – блок 7,поэтому его мы тоже пометим, а так же добавим всевозможные ветви в список помеченных ветвей•является обращением к функции ввода-вывода (в данном фрагменте невстречается)•вычисляет значение глобальной переменной, доступной из других процедур(множество Globals будет подробно вычислено в домашнем задании номер 4,на слайде номер 6)•ее результат используется в других полезных инструкциях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, 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 L7Так же помним ещё 2 вещи:•Базовый блок, содержащий хотя бы одну помечен функцию – помечается.•Ветвь содержащая хотя бы один помеченный блок - помечаетсяПомеченные ветви: 1,2,3,4,5,6,7 или 1,3,4,5,6,7 или 1,2,3,5,6,7 или 1,3,5,6,7L7:31 t4 < -132 return t4exitНомерблока1def2(t1),3(m),4(t2),5(t3)2311(t4)14(t5),15(t6),16(t7)456722(r)24(l)31(t4)GlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5n01 2 3 4 5 67 8RDF(n)Ø 7 1 7 3 7 7Ø ØПроход MarkГПУПродолжая аналогичным образом рассуждать мы так жеобрабатываем операции от 3 до 5.Критерий полезности инструкции:Так как мы не рассматриваем оптимизацию приэлементарных вычислениях, то не сильно задумываясьмы так же помечаем операции 6-9Потом успешно помечаем операцию 11, а следовательнопомечаем и весь блок 2, граница доминатора у него блок1 – но он уже помечен, однако мы добавляем ветви.•вычисляет возвращаемое значение процедуры (return)•является обращением к функции ввода-вывода (в данном фрагменте невстречается)•вычисляет значение глобальной переменной, доступной из других процедур(множество Globals будет подробно вычислено в домашнем задании номер 4,на слайде номер 6)•ее результат используется в других полезных инструкциях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, 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 L7Так же помним ещё 2 вещи:•Базовый блок, содержащий хотя бы одну помечен функцию – помечается.•Ветвь содержащая хотя бы один помеченный блок - помечаетсяПомеченные ветви: 1,2,3,4,5,6,7 или 1,3,4,5,6,7 или 1,2,3,5,6,7 или 1,3,5,6,7 или2,3,4,5,6,1 или 2,3,5,6,1L7:31 t4 < -132 return t4exitНомерблока1def2(t1),3(m),4(t2),5(t3)2311(t4)14(t5),15(t6),16(t7)456722(r)24(l)31(t4)GlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5n01 2 3 4 5 67 8RDF(n)Ø 7 1 7 3 7 7Ø ØПроход MarkГПУОперация 12 помечается как операция ,вычисляющая возвращаемое значениепроцедуры.Критерий полезности инструкции:Дальнейшие рассуждения не будут уникальны –всё повторяется, поэтому я просо на следующемслайде окрашу всё, что необходимо пометить (вмоём случае – это абсолютно всё)•вычисляет возвращаемое значение процедуры (return)•является обращением к функции ввода-вывода (в данном фрагменте невстречается)•вычисляет значение глобальной переменной, доступной из других процедур(множество Globals будет подробно вычислено в домашнем задании номер 4,на слайде номер 6)•ее результат используется в других полезных инструкциях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, 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 L7Так же помним ещё 2 вещи:•Базовый блок, содержащий хотя бы одну помечен функцию – помечается.•Ветвь содержащая хотя бы один помеченный блок - помечаетсяПомеченные ветви: 1,2,3,4,5,6,7 или 1,3,4,5,6,7 или 1,2,3,5,6,7 или 1,3,5,6,7 или2,3,4,5,6,1 или 2,3,5,6,1L7:31 t4 < -132 return t4exitНомерблока1def2(t1),3(m),4(t2),5(t3)2311(t4)14(t5),15(t6),16(t7)456722(r)24(l)31(t4)GlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5n01 2 3 4 5 67 8RDF(n)Ø 7 1 7 3 7 7Ø ØПроход MarkГПУНа этом поход mark завершён.Заметим, что для каждой из помеченных ветвейкаждый её блок должен быть так же помечен,однако все наши блоки уже помечены.Критерий полезности инструкции:•вычисляет возвращаемое значение процедуры (return)•является обращением к функции ввода-вывода (в данном фрагменте невстречается)•вычисляет значение глобальной переменной, доступной из других процедур(множество Globals будет подробно вычислено в домашнем задании номер 4,на слайде номер 6)•ее результат используется в других полезных инструкциях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, 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 L7Так же помним ещё 2 вещи:•Базовый блок, содержащий хотя бы одну помечен функцию – помечается.•Ветвь содержащая хотя бы один помеченный блок - помечаетсяПомеченные ветви: 1,2,3,4,5,6,7 или 1,3,4,5,6,7 или 1,2,3,5,6,7 или 1,3,5,6,7 или 2,3,4,5,6,1или 2,3,5,6,1 или 3,4,5,6,7 или 3,5,6,7 или 4,5,6,1,2,3 или 4,5,6,1,3 или 5,6,7 или 6,7L7:31 t4 < -132 return t4exitНомерблока1def2(t1),3(m),4(t2),5(t3)2311(t4)14(t5),15(t6),16(t7)456722(r)24(l)31(t4)GlobalslravmBlocks(x)1,4,61,61,31,32,3,4,5n01 2 3 4 5 67 8RDF(n)Ø 7 1 7 3 7 7Ø ØПроход SweepГПУВ моём случае отсутствуют непомеченные ветви,а потому дополнительных безусловныхпереходов нету.В данном проходе берётся каждый блок, с которого начинается не помеченнаяветвь (т.е.
фактически не помеченный блок из которого есть путь ещё в другойнепомеченный блок, но только по непомеченным блокам), и ставится безусловныйпереход на один из его помеченных постдоминаторов.На этом проход sweep закончен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, 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 L7Помеченные ветви: 1,2,3,4,5,6,7 или 1,3,4,5,6,7 или 1,2,3,5,6,7 или 1,3,5,6,7 или 2,3,4,5,6,1или 2,3,5,6,1 или 3,4,5,6,7 или 3,5,6,7 или 4,5,6,1,2,3 или 4,5,6,1,3 или 5,6,7 или 6,7n012345678RDF(n)Ø717377ØØDom(n)0,1,3,5,6,7,81,3,5,6,7,82,3,5,6,7,83,5,6,7,84,5,6,7,85,6,7,86,7,87,88L7:31 t4 < -132 return t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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, 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 t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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, 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 t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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, 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 t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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, 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 t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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, 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 t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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, 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 t4exitИсключение недостижимого кодаДля проверки наличия недостижимого кода – необходимо начать обход с entry ипри помощи обхода графа в глубину (или в ширину) выяснить, какие вершиныдостижимы.ГПУСделаем пару начальных шагов.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Таким образом – в данном Графе потока управления – все блоки достижимы, иничего не выбрасывается.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Итог после удаления бесполезного кода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, 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 t4exit.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
