Notes on Graph Algorithms Used in Optimizing Compilers

Notes on Graph Algorithms Used in Optimizing Compilers Carl D. Offner University of Massachusetts Boston April 26, 2011 Contents 1 Depth-First Walks 1 1.1 Depth-First Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 A Characterization of DAGS . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 A Characterization of Descendants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 The Path Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 An Application: Strongly Connected Components . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Tarjan’s Original Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Flow Graphs 19 2.1 Flow Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Dominators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Depth-First Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Reducible Flow Graphs 24 3.1 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Algorithms for Constructing Intervals . . . ....

Website: www.cs.umb.edu | Filesize: -
No of Page(s): 100
Download Notes on Graph Algorithms Used in Optimizing Compilers.pdf