Definition-Use Chains COMP 512 Rice University Houston, Texas Spring 2009 Copyright 2009, Keith D. Cooper & Linda Torczon, all rights reserved. Students enrolled in Comp 512 at Rice University have explicit permission to make copies of these materials for their personal use. 1!COMP 512, Spring 2009!Last Class •! Worklist iterative algorithm for data-flow analysis •! Series of data-flow problems >! LIVE, AVAIL, VERYBUSY, CONSTANTS >! Example of non-distributive framework – CONSTANTS >! Example of non-rapid framework – Interprocedural MOD If we continue along this direction, the compiler solves one data-flow problem per transformation. Instead, we would like to solve one data-flow problem and use it for multiple transformations. Instead, the community invented information chains COMP 512, Spring 2009! 2!COMP 512, Spring 2009! 3!Information Chains A tuple that connects 2 data-flow events is a chain •! Chains express data-flow relationships directly •! Chains provide a graphical representation •! Chains jump across unrelated code, simplifying search We can build chains efficiently Four interesting types of chain DependenceSource Sink Typedef use true, flowuse def antidef def outputuse use inputDef-Use chains are the most common event ! definition or use COMP 512, Spring 2009! 4!d is dead It has no use Information Chains Example a ! 5!b ! 3!c ! b + 2!d ! a - 2!e ! a + b!e ! e + c!e ! 13!f ! 2 + e!Write f!def-use chains *COMP 512, Spring 2009! 5!Notation Assume that, " operation i and each variable v, •!DEFS(v,i) is the set of operations that may have defined v most recently before i, along some path in the CFG •!USES(v,i) is the set of operations that may use the value of v computed at i, along some path in the CFG x # DEFS(A,y) $ y # USES(A,x) To construct DEF-USE chains, we solve reaching definitions (YADFP ) •! A definition d of some variable v reaches an operation i if and only if i reads v and there is a v-clear path from d to i >!v-clear % no definition of v on the path •! Prior definition of v in same block % |DEFS(v,i )| = 1 •! No prior definition % |DEFS(v,i )| ! 1 The chains are non-local in this case COMP 512, Spring 2009! 6!Reaching Definitions The equations REACHES(n) = Ø, " n # N REACHES(n) = &p!preds(n) DEDEF(p) & (REACHES(p) ' DEFKILL(p)) •!REACHES(n) is the set of definitions that reach block n •!DEDEF(N) is the set of definitions in n that reach the end of n •!DEFKILL(n) is the set of defs obscured by a new def in n Computing REACHES(n) •! Use any data-flow method (rapid framework) •! Zadeck shows a simple linear-time scheme F.K. Zadeck, “Incremental data-flow analysis in a structured program editor,” Proceedings of the SIGPLAN 84 Conf. on Compiler Construction, June, 1984, pages 132-143. Domain is |definitions|, same as number of operations * Form of f is same as in LIVECOMP 512, Spring 2009! 7!Building DEFS sets The Plan 1. Find basic blocks & build the CFG 2. " block b, compute REACHES(b) (to the fixed point) 3. " block b, " operation i, " referenced name v, Set DEFS(v,i) according to the earlier rule A.) If there is a prior definition, d, of v in b DEFS(v,i) ! d B.) Otherwise DEFS(v,i) ! {d | d defines v & d # REACHES(b ) } To build USES •! Invert DEFS, or •! Solve reachable uses, and use the analogous construction COMP 512, Spring 2009! 8!Building DEF-USE Chains Miscellany •! Domain of REACHES is the set of definitions (( |operations|) •! Domain of DEFS & USES is also definitions •! Need a compact representation of DEFS & USES Detecting Anomalies •!DEFS(v,i) = Ø implies use of a never initialized variable •! Add a definition for each v to n0 to detect larger set of anomalies >! If initial def # DEFS(v,i) then ) a path to i with no initialization * And, how do we use these information chains?COMP 512, Spring 2009! 9!Constant Propagation over DEF-USE Chains Worklist ! Ø For i ! 1 to number of operations if in1 of operation i is a constant ci then Value(in1,i ) ! ci else Value(in1,i ) ! T if in2 of operation i is a constant cj then Value(in2,i ) ! cj else Value(in2,i ) ! T if (Value(in1,i ) is a constant & Value(in2,i ) is a constant) then Value(out,i ) ! evaluate op i Worklist ! Worklist & {i } else Value(out,i ) ! T Initialization Step while ( Worklist " Ø) remove a definition i from WorkList for each j # USES(out,i ) set x so that out of i is inx of j Value(inx,j ) ! Value(inx,j ) * Value(out,,i ) if (Value(in1,j ) is a constant & Value(in2,j ) is a constant) then Value(out,j ) ! evaluate op j Worklist ! Worklist & {j } else if (Value(in1,j ) is + or Value(in2,j ) is +) then Value(out,j ) ! + Propagation Step Any T left after fixed point derives from unitinitalized value: what should we do? COMP 512, Spring 2009! 10!Constant Propagation over DEF-USE Chains Optimism i " 12 while ( … ) … x " i * 17 j " i i " … … i " j Clear that i is always 12 at def of x + + + + 12 Pessimistic initializations Leads to i !12 *+ = + In general •! Optimism helps inside loops •! Largely a matter of initial value M.N. Wegman & F.K. Zadeck, Constant propagation with conditional branches, ACM TOPLAS, 13(2), April 1991, pages 181–210. * Optimism •! This version of the algorithm is an optimistic formulation •! Initializes values to •! Prior version used + (implicit ) + Optimistic initializations + Leads to i !12 * = 12 + + + + 12COMP 512, Spring 2009! 11!Constant Propagation over DEF-USE Chains Complexity •! Initial step takes O(1) time per operation •! Propagation takes >! |USES(v,i )| for each i pulled from Worklist >! Summing over all ops, becomes |edges in DEF-USE graph| >! A definition can be on the worklist twice (lattice height) >! O(|operations| + |edges in DU graph|) This approach (on a sparse graph) is faster than the straightforward iterative approach in the Kildall style COMP 512, Spring 2009! 12!Constant Propagation (Classic formulation) Transformation: Global Constant Folding •! Along every path to p, v has same known value •! Specialize computation at p based on v’s value Data-flow problem: Constant Propagation Domain is the set of pairs <vi,ci> where vi is a variable and ci # C CONSTANTS(b) = *p ! preds(b) fp(CONSTANTS(p)) •! * performs a pairwise meet on two sets of