compiler-textbook (1161795), страница 2
Текст из файла (страница 2)
2: Граф потока управления после применения алгортма Mark&Sweep113.1.5Замечания1. Данный программа реализует алгоритм Евклида, при этом печатает на каждой десятой итерации символ «|». Значение счетчика итераций i не влияетна результат вычислений программы, но влияет на внешнее поведение, чтои было обнаружено в ходе алгоритма и этот код был оставлен как полезный.2. Тем не менее, внимательный читатель мог заметить, что инструкция (4) неявляется полезной, т.к. вычисляет мертвое значение переменной r, но она небыла удалена. Этой неточности можно было бы избежать, если перед запуском алгоритма Mark&Sweep программа была бы приведена к SSA-форме.3.
Данный алгоритм не только не удаляет недостижимый код (блок B2 былнедостижимым и остался в итоговом графе), но и порождает новый (блокB3 стал недостижимым). Поэтому необходимо дополнительно озаботитьсяудалением недостижимого кода.3.2Удаление недостижимого кодаДля удаления недостижимого кода необходимо обойти граф потока управления в глубину (или в ширину), начиная с блока Entry.
Все непосещенные в процессе обхода блоки являются недостижимыми и подлежат удалению.В рассмотренном выше примере необходимо удалить блоки B2 и B3 (см.Рис. 3)12EntryB1scanf x (1)scanf y (2)i ← 0 (3)r ← i (4)if (> x, y)goto B5 (5)elsegoto B4 (6)B4a ←x ←y ←gotox (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Рис. 3: Граф потока управления после удаления недостижимого кода13Список литературы[1] Keith D. Cooper and Linda Torczon. Engineering a Compiler, Second Edition.
RiceUniversity, Houston, Texas, 2011[2] Yming Zhang, Rebecca Smith, Linge Dai and Max Grossman, ImplementationoftheMarkSweepdeadcodeeliminationalgorithmhttps://yunmingzhang.files.wordpress.com/2013/12/dcereport-2.pdf14inLLVM..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
