compiler-textbook (1161795)
Текст из файла
Московский Государственный Университет им. М.В. Ломоносовафакультет Вычислительной математики и кибернетикикафедра системного программированияКонструированиекомпиляторовИсключение бесполезного кодаМосква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Рис.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
