1CS553 Lecture Control-Flow and Loop Detection 2Control-Flow Analysis and Loop Detection Last time– Speeding up data-flow analysis Today– Control-flow analysis– Loops– Identifying loops using dominators– Reducibility CS553 Lecture Control-Flow and Loop Detection 3Context Data-flow– Flow of data values from defs to uses– Could alternatively be represented as a data dependence Control-flow– Sequencing of operations– Could alternatively be represented as a control dependence– e.g., Evaluation of then-code and else-code depends on if-test,CS553 Lecture Control-Flow and Loop Detection 4Why study control flow analysis? Finding Loops– most computation time is spent in loops– to optimize them, we need to find them Loop Optimizations– Loop-invariant code hoisting– Induction variable elimination– Array bounds check removal– Loop unrolling– Parallelization– ... Identifying structured control flow– can be used to speed up data-flow analysisCS553 Lecture Control-Flow and Loop Detection 5Representing Control-Flow High-level representation– Control flow is implicit in an AST Low-level representation:– Use a Control-flow graph– Nodes represent statements– Edges represent explicit flow of control Other options– Control dependences in program dependence graph (PDG) [Ferrante87]– Dependences on explicit state in value dependence graph (VDG) [Weise 94]2CS553 Lecture Control-Flow and Loop Detection 6What Is Control-Flow Analysis? Control-flow analysis discovers the flow of control within a procedure(e.g., builds a CFG, identifies loops) Example 1 a := 0 2 b := a * b 3 L1: c := b/d 4 if c < x goto L2 5 e := b / c 6 f := e + 1 7 L2: g := f 8 h := t - g 9 if e > 0 goto L3 10 goto L1 11 L3: returnYesNo1a := 0b := a * b3c := b/dc < x?5e := b / cf := e + 17g := fh := t - ge > 0?10goto11returnCS553 Lecture Control-Flow and Loop Detection 7Loop Concepts Loop: Strongly connected component of CFG with a single entry point (header) Loop entry edge: Source not in loop & target in loop Loop exit edge: Source in loop & target not in loop Loop header node: Target of loop entry edge Natural loop: Nodes with path to backedge without going through header. Back edge: Target is loop header & source is in the loop Loop tail node: Source of back edge Loop preheader node: Single node that’s source of the loop entry edge Nested loop: Loop whose header is inside another loopCS553 Lecture Control-Flow and Loop Detection 8entry edgePicturing Loop Terminologypreheaderexit edgeloopback edgetailheadCS553 Lecture Control-Flow and Loop Detection 9htpre-headerpThe Value of Preheader Nodes Not all loops have preheaders– Sometimes it is useful to create them Without preheader node– There can be multiple entry edges With single preheader node– There is only one entry edge Useful when moving code outside the loop– Don’t have to replicate code for multiple entryedgesht3CS553 Lecture Control-Flow and Loop Detection 10Identifying Loops Why?– Most execution time spent in loops, so optimizing loops will often givemost benefit Many approaches– Interval analysis– Exploit the natural hierarchical structure of programs– Decompose the program into nested regions called intervals– Structural analysis: a generalization of interval analysis– Identify dominators to discover loops We’ll look at the dominator-based approachCS553 Lecture Control-Flow and Loop Detection 11Dominatorsd dom i if all paths from entry to node i include dStrict dominators d sdom i if d dom i and d ≠ iImmediate dominators a idom b if a sdom b and there does not exist a node csuch that c ≠ a, c ≠ b, a dom c, and c dom bPost dominators p pdom i if every possible path from i to exit includesp (p dom i in the flow graph whose arcs are reversedand entry and exit are interchanged)dientryd dom ipiexitp pdom iDominator Terminologyabentrya idom bnot ∃ c, a sdom c and c sdom bCS553 Lecture Control-Flow and Loop Detection 12Back edgesA back edge of a natural loop is one whose targetdominates its sourceNatural loopThe natural loop of a back edge (m→n), where ndominates m, is the set of nodes x such that ndominates x and there is a path from x to m notcontaining ntsback edgenmnatural loopbcadebacdeThe target, c, of theedge (d→c) does notdominate its source, d,so (d→c) does notdefine a natural loopExampleThis loop has twoentry points,c and dIdentifying Natural Loops with DominatorsCS553 Lecture Control-Flow and Loop Detection 13Computing DominatorsInput: Set of nodes N (in CFG) and an entry node sOutput: Dom[i] = set of all nodes that dominate node iDom[s] = {s}for each n ∈ N – {s}Dom[n] = Nrepeatchange = falsefor each n ∈ N – {s}D = {n} ∪ (∩p∈pred(n) Dom[p])if D ≠ Dom[n]change = trueDom[n] = Duntil !changeKey IdeaIf a node dominates allpredecessors of node n, then italso dominates node nnpred[n]p1p2p3 x ∈ Dom(p1) ^ x ∈ Dom(p2) ^ x ∈ Dom(p3) ⇒ x ∈ Dom(n)4CS553 Lecture Control-Flow and Loop Detection 14{n, p, q, r, s}{n, p, q, r, s}{n, p, q, r, s}Computing Dominators (example)Input: Set of nodes N and an entry node sOutput: Dom[i] = set of all nodes that dominate node iDom[s] = {s}for each n ∈ N – {s}Dom[n] = Nrepeatchange = falsefor each n ∈ N – {s}D = {n} ∪ (∩p∈pred(n) Dom[p])if D ≠ Dom[n]change = trueDom[n] = Duntil !changenprInitiallyDom[s] = {s}Dom[q] = {n, p, q, r, s}. . .Finally Dom[q] =Dom[r] =Dom[p] =Dom[n] = s{n, p, q, r, s} {n, p, q, r, s} {s} {q, s} {r, s} {p, s} {n, p, s}{n, p, q, r, s}q{n, p, q, r, s} {n, p, q, r, s}CS553 Lecture Control-Flow and Loop Detection 15Reducibility Definition– A CFG is reducible (well-structured) if we can partition its edges intotwo disjoint sets, the forward edges and the back edges, such that– The forward edges form an acyclic graph in which every node can bereached from the entry node– The back edges consist only of edges whose targets dominate theirsources– A CFG is reducible if it can be converted into a single node using T1 andT2 transformations. Structured control-flow constructs give rise to reducible CFGs Value of reducibility– Dominance useful in identifying loops– Simplifies code transformations (every loop has a single header)– Permits interval analysis and it is easy to calculate the CFG depthCS553 Lecture Control-Flow and Loop Detection 16T1 and T2 transformations T1 transformation– remove self-cycles T2 transformation– if node n has a