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 }