compiler-textbook (Лекции)
Описание файла
Файл "compiler-textbook" внутри архива находится в папке "Лекции". PDF-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Московский Государственный Университет им. М.В. Ломоносовафакультет Вычислительной математики и кибернетикикафедра системного программированияКонструированиекомпиляторовИсключение бесполезного кодаМосква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Рис.