Loops in flow

5th chapter

1. Loops in Flow Graphs BP150511 R. RAMYA

2. LOOPS IN FLOW GRAPHS We shall use the notion of a node “Dominating” another to define “Natural Loop” and the important special class of “ Reducible” of flow graphs. An algorithm for finding dominators and checking reducibility of flow graphs.

3. Dominators Natural loops Inner loops Pre-Headers Reducible flow graphs

4. Dominators d dom n – Node d of a CFG dominates node n if every path from the initial node of the CFG to n goes through d– The loop entry dominates all nodes in the loop The immediate dominator m of a node n is the last dominator on the path from the initial node to n – If d ≠ n and d dom n then d dom m

5. Build a dominator tree as follows: – Root is CFG entry node n0 – m is child of node n iff n= Idom ( m)

6. Natural Loops A back edge is is an edge a → b whose head b dominates its tail a Given a back edge n → d 1. The natural loop consists of d plus the nodes that can reach n without going through d 2. The loop header is node d • Unless two loops have the same header, they are disjoint or one is nested within the other – A nested loop is an inner loop if it contains no other loops

7. Natural Inner Loops Example

8. Natural Outer Loops Example

9. Pre-Headers To facilitate loop transformations, a compiler often adds a pre-header to a loop • Code motion, strength reduction, and other loop transformations populate the pre-header

10. Reducible Flow Graphs Reducible graph = disjoint partition in forward and back edges such that the forward edges form an acyclic (sub)graph.

11. VIDEO video1

12. THANK YOU