1CS553 Lecture Control-Flow Analysis 2Control-Flow Analysis Last time– Introduction to data-flow analysis (liveness) Today– Control-flow analysis– Building basic blocks– Building control-flow graphs (CFGs)– Loops CS553 Lecture Control-Flow Analysis 3Context Data-flow– Flow of data values from defs to uses Control-flow– Sequencing of operations– e.g., Evaluation of then-code and else-code depends on if-test2CS553 Lecture Control-Flow Analysis 4Representing 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]CS553 Lecture Control-Flow Analysis 5What 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?10goto11return3CS553 Lecture Control-Flow Analysis 6Basic Blocks Definition– A basic block is a sequence of straight line code that can be entered onlyat the beginning and exited only at the end Building basic blocks– Identify leaders– The first instruction in a procedure, or– The target of any branch, or– An instruction immediately following a branch (implicit target)– Gobble all subsequent instructions until the next leaderYesNog := fh := t - ge > 0?CS553 Lecture Control-Flow Analysis 7Algorithm for Building Basic BlocksInput: List of n instructions (instr[i] = ith instruction)Output: Set of leaders & list of basic blocks(block[x] is block with leader x)leaders = {1} // First instruction is a leaderfor i = 1 to n // Find all leadersif instr[i] is a branchleaders = leaders ∪ set of potential targets of instr[i]foreach x ∈ leadersblock[x] = { x }i = x+1 // Fill out x’s basic blockwhile i ≤ n and i ∉ leadersblock[x] = block[x] ∪ { i }i = i + 14CS553 Lecture Control-Flow Analysis 8Building Basic Blocks Example 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: return Leaders? Blocks?– {1, 3, 5, 7, 10, 11}– {1, 2}– {3, 4}– {5, 6}– {7, 8, 9}– {10}– {11}CS553 Lecture Control-Flow Analysis 9Extended Basic Blocks Extended basic blocks– A maximal sequence of instructionsthat has no merge points in it (exceptperhaps in the leader)– Single entry, multiple exits How are these useful?– Increases the scope of any localanalysis or transformation that “flowsforwards” (e.g., copy propagation,register renaming, instructionscheduling) Reverse extended basic blocks– Useful for “backward flow” problems5CS553 Lecture Control-Flow Analysis 10 Construction– Each CFG node represents a basic block– There is an edge from node i to j if– Last statement of block i branches to the first statement of j, or– Block i does not end with an unconditional branch and isimmediately followed in program order by block j (fall through)Input: A list of m basic blocks (block)Output: A CFG where each node is a basic blockfor i = 1 to mx = last instruction of block[i]if instr x is a branchfor each target (to block j) of instr xcreate an edge from block i to block jif instr x is not an unconditional branchcreate an edge from block i to block i+1Building a CFG from Basic Blocksgoto L1:L1:5121CS553 Lecture Control-Flow Analysis 11 Multiple edges between two nodes... if (a<b) goto L2L2: ...– Combine these edges into one edge Unreachable code ... goto L1L0: a = 10L1: ... Unreachable code vs. dead code?Details– Perform DFS from entry node– Mark each basic block as it is visited– Unmarked blocks are unreachable6CS553 Lecture Control-Flow Analysis 12Challenges When is CFG construction more complex? Languages with branch delay slots– e.g., Sparcba loopsub %l1, %l2, %l3 Languages where branch targets may be unknown– e.g., Executable codeld $8, 104($7)jmp $8CS553 Lecture Control-Flow Analysis 13Loop Concepts Loop: Strongly connected component of CFG 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: Loop with only a single loop 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 loop Reducible flow graph: CFG whose loops are all natural loops7CS553 Lecture Control-Flow Analysis 14entry edgePicturing Loop Terminologypreheaderexit edgeloopback edge(natural)tailheadCS553 Lecture Control-Flow Analysis 15htpre-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 entryedgesht8CS553 Lecture Control-Flow Analysis 16Identifying 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 Analysis 17Dominatorsd 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 b9CS553 Lecture Control-Flow Analysis 18Back edgesA back edge of a natural loop is one whosetarget dominates its sourceNatural loopThe natural loop of