Исключение бесполезного кода (методичка) (2015)

Московский Государственный Университет им. М.В. Ломоносовафакультет Вычислительной математики и кибернетикикафедра системного программированияКонструированиекомпиляторовИсключение бесполезного кодаМосква20151Постановка задачиБесполезный код - множество инструкций программы, не влияющих навнешнее поведение и результат. К бесполезному коду относятся:• Мертвый код - выполнение не влияет на внешнее поведение и результат.• Недостижимый код - не может быть выполнен в ходе работы программы.Требуется обнаружить и удалить мертвый и недостижимый код из программы.2Описание алгоритма Mark&SweepКлассический алгоритм удаления мертвого кода работает по аналогии с mark-sweep алгоритмами сборщиков мусора, где в качестве данных выступает промежуточное представление.Как и mark-sweep сборщики мусора, алгоритм удаления мертвого кода выполняется в два прохода.2.1Проход MarkВ начале первого прохода необходимо очистить все пометки и пометить критические(critical) инструкции как полезные.Для приведенного в заданиях промежуточного представления критическимиявляются:• инструкции, возвращающие управление из процедуры,• инструкции ввода-вывода,• инструкции, влияющие на значения в доступных извне процедуры областяхпамяти.Все такие инструкции в начале прохода Mark помещаются в Worklist.2Algorithm 1 Процедура Markprocedure MarkWorkList ← ∅for all operation i doclear i’s markif i is critical thenmark iWorkList ← WorkList ∪ {i}end ifend forwhile WorkList 6= ∅ doremove i from WorkList(assume i is x ← y op z)if def(y) is not marked thenmark def(y)WorkList ← WorkList ∪ {def(y)}end ifif def(z) is not marked thenmark def(z)WorkList ← WorkList ∪ {def(z)}end iffor all block b ∈ RDF(block(i)) dolet j be the branch that ends bif j is unmarked thenmark jWorkList ← WorkList ∪ {j}end ifend forend whileend procedureЗатем пока Worklist не пуст выполняется следующее:• очередная иструкция I извлекается из Worklist,3• для каждого операнда x инструкции I:– для каждого определения x, если соответствующая инструкцияx ← y op zещё не помечена, то она помечается и помещается в Worklist,• для каждого базового блока B из RDF (block(I)): Пусть j - последняя инструкция B.

Это ветвление. Та ветка, которая ведет в block(I), если она ещёне помечена, помечается и добавляется в Worklist.2.2Проход SweepДалее проход Sweep для каждой непомеченной инструкции делает следующее:• если это одна из ветвей оператора ветвления, то она заменяется на инструкцию goto на ближайший помеченный постдоминатор,• иначе, если это не безусловный переход, то инструкция удаляется.Algorithm 2 Процедура Sweepprocedure Sweepfor all operation i doif i is unmasked thenif i is branch thenrewrite i with a jumpto i’s nearest markedpostdominatorend ifif i is not a jump thendelete iend ifend ifend forend procedure43ПримерEntryB1scanf x (1)scanf y (2)i ← 0 (3)r ← i (4)if (> x, y)goto B3 (5)elsegoto B4 (6)B4a ←x ←y ←h ←gotoB3p ← y (9)goto B5 (10)B2i ← + i, 1 (7)goto B4 (8)x (11)y (12)a (13)3 (14)B5 (15)B5i ← + i, 1 (16)p ← + y, 1 (17)it ← % i, 10 (18)if (= it, 0)goto B6 (19)elsegoto B7 (20)B6print «|» (21)goto B7 (22)B7r ← % y, x (23)y ← x (24)x ← r (25)if (> r, 0)goto B5 (26)elsegoto B8 (27)B8return y (28)ExitРис.

1: Граф потока управления53.13.1.1Удаление мертвого кодаПостроение обратной границы доминированияТаблица 1: Обратная граница доминированияBlock n3.1.2RDF(n)B1∅B2∅B3{B1}B4{B1}B5{B7}B6{B5}B7∅B8∅Проход Mark1. В начале первого прохода помечаются и добавляются в Worklist критическиеинструкции.Worklist: (1), (2), (21), (28)Marked: (1), (2), (21), (28)2. Из Worklist вынимается инструкция (1). RDF (B1) = ∅Worklist: (2), (21), (28)Marked: (1), (2), (21), (28)3.

Из Worklist вынимается инструкция (2). RDF (B1) = ∅Worklist: (21), (28)Marked: (1), (2), (21), (28)4. Из Worklist вынимается инструкция (21). Помечается и добавляется вWorklist ветка блока B5 ∈ RDF (B6), по которой поток управления идетв B6 – (19).6Worklist: (28), (19)Marked: (1), (2), (19), (21), (28)5. Из Worklist вынимается инструкция (28). Помечаются и добавляются вWorklist инструкции, вычисляющие её операнды: (13), (24). RDF (B8) = ∅Worklist: (19), (13), (24)Marked: (1), (2), (13), (19), (21), (24), (28)6.

Из Worklist вынимается инструкция (19). Помечаются и добавляются вWorklist инструкции, вычисляющие её операнды: (18).Помечается и добавляется в Worklist ветка блока B7 ∈ RDF (B5), по которой поток управленияидет в B5 – (26).Worklist: (13), (24), (18), (26)Marked: (1), (2), (13), (18), (19), (21), (24), (26), (28)7. Из Worklist вынимается инструкция (13). Помечаются и добавляются вWorklist инструкции, вычисляющие её операнды: (11).

Помечается и добавляется в Worklist ветка блока B1 ∈ RDF (B4), по которой поток управленияидет в B4 – (6).Worklist: (24), (18), (26), (6), (11)Marked: (1), (2), (6), (11), (13), (18), (19), (21), (24), (26), (28)8. Из Worklist вынимается инструкция (24). Помечаются и добавляются вWorklist инструкции, вычисляющие её операнды: (12), (25). RDF (B7) = ∅.Worklist: (18), (26), (6), (11), (12), (25)Marked: (1), (2), (6), (11), (12), (13), (18), (19), (21), (24), (25), (26), (28)9. Из Worklist вынимается инструкция (18). Помечаются и добавляются вWorklist инструкции, вычисляющие её операнды: (3), (7), (16).

Ветви, ведущие из RDF (B5) в B5, также уже помечены.Worklist: (26), (6), (11), (12), (25), (3), (7), (16)Marked: (1), (2), (3), (6), (7), (11), (12), (13), (16), (18), (19), (21), (24),(25), (26), (28)10. Из Worklist вынимается инструкция (26). Помечаются и добавляются вWorklist инструкции, вычисляющие её операнды: (4), (23). Ветви, ведущие7из RDF (B5) в B5, также уже помечены.Worklist: (6), (11), (12), (25), (3), (7), (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)11. Из Worklist вынимается инструкция (6). Инструкции, вычисляющие её операнды, уже помечены.

RDF (B1) = ∅.Worklist: (11), (12), (25), (3), (7), (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)12. Из Worklist вынимается инструкция (11). Инструкции, вычисляющие её операнды, уже помечены. Ветви, ведущие из RDF (B4) в B4, также уже помечены.Worklist: (12), (25), (3), (7), (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)13. Из Worklist вынимается инструкция (12). Инструкции, вычисляющие её операнды, уже помечены. Ветви, ведущие из RDF (B4) в B4, также уже помечены.Worklist: (25), (3), (7), (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)14. Из Worklist вынимается инструкция (25).

Инструкции, вычисляющие её операнды, уже помечены. RDF (B7) = ∅.Worklist: (3), (7), (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)15. Из Worklist вынимается инструкция (3). RDF (B1) = ∅.Worklist: (7), (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)816. Из Worklist вынимается инструкция (7). Инструкции, вычисляющие её операнды, уже помечены. RDF (B2) = ∅.Worklist: (16), (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)17. Из Worklist вынимается инструкция (16).

Инструкции, вычисляющие её операнды, уже помечены. Ветви, ведущие из RDF (B5) в B5, также уже помечены.Worklist: (4), (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)18. Из Worklist вынимается инструкция (4). Инструкции, вычисляющие её операнды, уже помечены. RDF (B1) = ∅.Worklist: (23)Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)19.

Из Worklist вынимается инструкция (23). Инструкции, вычисляющие её операнды, уже помечены. RDF (B7) = ∅.Worklist:Marked: (1), (2), (3), (4), (6), (7), (11), (12), (13), (16), (18), (19), (21),(23), (24), (25), (26), (28)20. W orklist = ∅. Первый проход Mark завершается.3.1.3Проход SweepРассматриваем все непомеченные инструкции:1. Инструкция (5): ветка. Заменяется переходом на первый полезный постдоминатор.goto B52. Инструкция (8): безусловный переход.

Остается без изменений.93. Инструкция (9): не ветка и не безусловный переход. Удаляется.4. Инструкция (10): безусловный переход. Остается без изменений.5. Инструкция (14): не ветка и не безусловный переход. Удаляется.6. Инструкция (15): безусловный переход. Остается без изменений.7. Инструкция (17): не ветка и не безусловный переход. Удаляется.8. Инструкция (20): ветка. Заменяется переходом на первый полезный постдоминатор.goto B79. Инструкция (22): безусловный переход. Остается без изменений.10. Инструкция (20): ветка.

Заменяется переходом на первый полезный постдоминатор.goto B8103.1.4Результат работы алгоритма Mark&SweepEntryB1scanf x (1)scanf y (2)i ← 0 (3)r ← i (4)if (> x, y)goto B5 (5)elsegoto B4 (6)B3goto B5 (10)B4a ←x ←y ←gotoB2i ← + i, 1 (7)goto B4 (8)x (11)y (12)a (13)B5 (15)B5i ← + i, 1 (16)it ← % i, 10 (18)if (= it, 0)goto B6 (19)elsegoto B7 (20)B6print «|» (21)goto B7 (22)B7r ← % y, x (23)y ← x (24)x ← r (25)if (> r, 0)goto B5 (26)elsegoto B8 (27)B8return y (28)ExitРис. 2: Граф потока управления после применения алгортма Mark&Sweep113.1.5Замечания1.

Данный программа реализует алгоритм Евклида, при этом печатает на каждой десятой итерации символ «|». Значение счетчика итераций i не влияетна результат вычислений программы, но влияет на внешнее поведение, чтои было обнаружено в ходе алгоритма и этот код был оставлен как полезный.2. Тем не менее, внимательный читатель мог заметить, что инструкция (4) неявляется полезной, т.к. вычисляет мертвое значение переменной r, но она небыла удалена. Этой неточности можно было бы избежать, если перед запуском алгоритма Mark&Sweep программа была бы приведена к SSA-форме.3. Данный алгоритм не только не удаляет недостижимый код (блок B2 былнедостижимым и остался в итоговом графе), но и порождает новый (блокB3 стал недостижимым).