Carnegie Mellon Lecture 4 More on Data Flow: Constant Propagation, Speed, Loops I. Constant Propagation II. Efficiency of Data Flow Analysis III. Algorithm to find loops Reading: Chapter 9.4, 9.6 M. Lam CS243: Constants, Speed, Loops 1Carnegie Mellon I. Constant Propagation/Folding • At every basic block boundary, for each variable v • determine if v is a constant • if so, what is the value? M. Lam CS243: Constants, Speed, Loops 2 x = 2 m = x + e e = 3 p = e + 4 e = 1Carnegie Mellon Semi-lattice Diagram – Finite domain? – Finite height? M. Lam CS243: Constants, Speed, Loops 3Carnegie Mellon Equivalent Definition • Meet Operation: – Note: undef ∧ c2 = c2! M. Lam CS243: Constants, Speed, Loops 4 v1 v2 v1 ∧ v2 undef undef undef c2 c2 NAC NAC c1 undef c1 c2 c1, if c1 =c2 NAC otherwise NAC NAC NAC undef NAC c2 NAC NAC NACCarnegie Mellon Example M. Lam CS243: Constants, Speed, Loops 5 x = 2 p = xCarnegie Mellon Transfer Function • Assume a basic block has only 1 instruction • Let IN[b,x], OUT[b,x] • be the information for variable x at entry and exit of basic block b • OUT[entry, x] = undef, for all x. • Non-assignment instructions: OUT[b,x] = IN[b,x] • Assignment instructions: (next page) M. Lam CS243: Constants, Speed, Loops 6Carnegie Mellon Constant Propagation (Cont.) • Let an assignment be of the form x3 = x1 + x2 • “+” represents a generic operator • OUT[b,x] = IN [b,x], if x ≠ x3 • Use: x ≤ y implies f(x) ≤ f(y) to check if framework is monotone • [v1 v2 ... ] ≤ [v1’ v2’ ... ], f([v1 v2 ... ]) ≤ f ([v1’ v2’ ... ]) M. Lam CS243: Constants, Speed, Loops 7 IN[b,x1] IN[b,x2] OUT[b,x3] undef undef undef c2 c2 NAC NAC c1 undef undef c2 c1 + c2 NAC NAC NAC undef NAC c2 NAC NAC NACCarnegie Mellon Distributive? • Iterative solutions is not precise! – it is also not wrong – it is conservative M. Lam CS243: Constants, Speed, Loops 8 x = 2 y = 3 x = 3 y = 2 z = x + yCarnegie Mellon Summary of Constant Propagation • A useful optimization • Illustrates: – abstract execution – an infinite semi-lattice – a non-distributive problem M. Lam CS243: Constants, Speed, Loops 9Carnegie Mellon II. Efficiency of Iterative Data Flow • Assume forward data flow for this discussion • Speed of convergence depends on the ordering of nodes • How about: M. Lam CS243: Constants, Speed, Loops 10 I. A B C D II. A D B E C exitCarnegie Mellon Depth-first Ordering: Reverse Postorder • Preorder traversal: visit the parent before its children • Postorder traversal: visit the children then the parent • Preferred ordering: reverse postorder • Intuitively – depth first postorder visits the farthest node as early as possible – reverse postorder delays visiting farthest node M. Lam CS243: Constants, Speed, Loops 11Carnegie Mellon “Reverse Post-Order” Iterative Algorithm input: control flow graph CFG = (N, E, Entry, Exit) // Boundary condition OUT[Entry] = ∅ // Initialization for iterative algorithm For each basic block B other than Entry OUT[B] = ∅ // iterate While (changes to any OUT occur) { For each basic block B other than Entry in reverse post order { IN[B] = ∪ (OUT[p]), for all predecessors p of B OUT[B] = fB(IN[B]) // OUT[B]=gen[B]∪(IN[B]-kill[B]) } M. Lam CS243: Constants, Speed, Loops 12Carnegie Mellon Consideration of Speed of Convergence • Does it matter if we go around the same cycle multiple times? • Cycles do not make a difference: – reaching definitions, liveness • Cycles make a difference: constant propagation M. Lam CS243: Constants, Speed, Loops 13 a = b b = c c = 1Carnegie Mellon Speed of Convergence • If cycles do not add info: – Labeling nodes in a path by their reverse postorder rank: 1 -> 4 -> 5 -> 7 -> 2 -> 4 ... – info flows down nodes of increasing reverse postorder rank in 1 pass • Loop depth = max. # of “retreating edges” in any acyclic path • Maximum # iterations in data flow algorithm = Loop depth+2 (2 is necessary even if there are no cycles) • Knuth’s experiments show: average loop depth in real programs = 2.75 M. Lam CS243: Constants, Speed, Loops 14Carnegie Mellon III. What is a Loop? • Goals: – Define a loop in graph-theoretic terms (control flow graph) – Not sensitive to input syntax – A uniform treatment for all loops: DO, while, goto’s • Informally: A “natural” loop has – edges that form at least a cycle – a single entry point M. Lam CS243: Constants, Speed, Loops 15Carnegie Mellon Dominators • Node d dominates node n in a graph (d dom n): – if every path from the start node to n goes through d • a node dominates itself • Immediate dominance: d idom n : d dom n, d ≠ n, ¬∃m s.t. d dom m and m dom n • Immediate dominance relationships form a tree M. Lam CS243: Constants, Speed, Loops 16Carnegie Mellon Finding Dominators • Definition • Node d dominates node n in a graph (d dom n) if every path from the start node to n goes through d • Formulated as MOP problem: • node d lies on all possible paths reaching node n ⇒ d dom n – Direction: – Values: – Meet operator: – Top: – Bottom: – Boundary condition: start/exit node = – Finite descending chain? – Transfer function: • Speed: • With reverse postorder, solution to most flow graphs (reducible flow graphs) found in 1 pass M. Lam CS243: Constants, Speed, Loops 17Carnegie Mellon Definition of Natural Loops • Single entry-point: header (d ) – a header dominates all nodes in the loop • A back edge (n  d ) in a flow graph is – an edge whose destination dominates its source (d dom n) • The natural loop of a back edge (n  d ) is d + {nodes that can reach n without going through d } M. Lam CS243: Constants, Speed, Loops 18Carnegie Mellon Constructing Natural Loops • The natural loop of a back edge (n  d ) is d + {nodes that can reach n without going through d } • Remove d from the flow graph, find all predecessors of n • Example: M. Lam CS243: Constants, Speed, Loops 19Carnegie Mellon Inner Loops • If two loops do not have the same header: – they are either disjoint, or – one is