Machine-Independent Optimizations IV CS308 Compiler Theory 1
Machine-Independent Optimizations Ⅳ CS308 Compiler Theory 1
Loops in Flow Graphs Loops are important because programs spend most of their time executing them Optimizations that improve the performance of loops can have a significant impact. CS308 Compiler Theory 2
Loops in Flow Graphs • Loops are important because programs spend most of their time execut ing t hem • Optimizations that improve the performance of loops can have a si ifi t i t ignifican t impac t. CS308 Compiler Theory 2
Dominators ●g Say node d of a flow graph dominates node n,written d dom n,if every path from the entry node of the flow graph to n goes through d. Every node dominates itself. Which nodes are dominated by each node? CS308 Compiler Theory 3
Dominators • Say node d of a flow graph dominates node n, written d dom n, if every path from th d f h fl h he entry node of the flow graph to n goes th h roug d. • Every node dominates itself. Which nodes are dominated by each node? CS308 Compiler Theory 3
Dominator Tree The entry node is the root Each node d dominates only its descendants in the tree. 2 3 6 8 10 CS308 Compiler Theory 4
Dominator Tree • The entry node is the root • Each node d dominates only its descendants in the tree. CS308 Compiler Theory 4
Finding Dominators D(n。)={no} For n∈N-{n。} D(n)=N; Change TRUE WHILE Change Change FALSE For n E N -no) { NewD ={n}U∩D(p) p∈P(n) f D(n)≠NewD Then { Change TRUE D (n )NewD } CS308 Compiler Theory 5
Finding Dominators ( ) { } 0 0 D n = n ; { } ( ) ; ( ) { } 0 0 0 WHIL E Chan g e Change TRUE For n N n D n N = ∈ − = { } ; { 0 Fo r n N n Change FALSE g ∈ − = { } ( ) { { } ( ) 0 NewD n D p N p P n = ∪ ∈ I ; { ( ) Change TRUE If D n NewD Then = ≠ } } D ( n ) = NewD ; CS308 Compiler Theory 5 }
Depth-First Ordering The route of the search in a depth-first search forms a depth-first spanning tree(DFST) 8 9 CS308 Compiler Theory 6
Depth-First Ordering • The route of the search in a depth-first search forms a depth-first spanni ( ng tree (DFST ). CS308 Compiler Theory 6
Depth-First Ordering void search(n){ mark n“visited”; for (each successor s of n) if(sis“unvisited'”){ add edge n→stoT; search(s); } dfnin c; 6 c=c-1; main() 8 T=①；/*set of edges*/ 10 for (each node n of G) mark n“unvisited”; c number of nodes of G; search(no); } CS308 Compiler Theory 7
Depth-First Ordering CS308 Compiler Theory 7
Edges in a Depth-First Spanning Tree Advancing edges:going from a node m to a proper descendant of m in the tree Retreating edges:going from a node m to an ancestor of m in the tree (possibly to m itself). Cross edges:edges m>n such that neither m nor n is an ancestor of the other in the DFST CS308 Compiler Theory 8
Edges in a Depth-First Spanning Tree • Advancing edges: going from a node m to a proper descendant of m in t he tree • Retreating edges: going from a node m to an ancestor of m in the tree ( ibl t it lf) (possibly to m itself) . • C d ross e dges: e dges m Æ n such th t ith i t f h th a t neither m nor n is an ances tor o f the other in the DFST CS308 Compiler Theory 8
Back Edges and Reducibility A back edge is an edge a >b whose head b dominates its tail a. For any flow graph,every back edge is retreating,but not every retreating edge is a back edge. A flow graph is said to be reducible if all its retreating edges in any depth-first spanning tree are also back edges. A flow graph is said to be reducible if all its retreating edges in any depth-first spanning tree are also back edges. CS308 Compiler Theory
Back Edges and Reducibility • A back edge is an edge a Æb whose head b dominates its tail a. • For any flow graph, every back edge is retreating, but not every retreating edge is a back edge. • A flow graph is said to be reducible if all its retreatin g edges in any depth-first spanning tree are also back edges. • A flow graph is said to be reducible if all its retreating edges in any depth -first spanning tree are also back edges first spanning tree are also back edges. CS308 Compiler Theory 9
Depth of a Flow Graph Given a depth-first spanning tree for the graph,the depth is the largest number of retreating edges on any cycle-free path. 10→7→4→3 Depth=3 0 9 CS308 Compiler Theory 10
Depth of a Flow Graph • Given a depth-first spanning tree for the graph, the depth is the largest numb f er o f retreatid l ng e dges on any cyc lefree pat h. 10 Æ 7 Æ4 Æ 3 Depth=3 CS308 Compiler Theory 10