Найти бесполезный код (домашние задания)

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