e oSpring 2010Spring 2010 Lect 10 Int od ction t Lecture 10: Introduction to Dataflow AnalysisValue Numbering Summaryg y • Forward symbolic execution of basic block •MMaps – Var2Val – symbolic value for each variable – Exp2Val – value of each evaluated expression – Exp2Tmp – tmp that holds value of each evaluated expression • Algorithm – For each statement For each statement • If variables in RHS not in the Var2Val add it with a new value • If RHS expression in Exp2Tmp use that Temp • IfIf nott add RHS dd RHS expressiion to EExp2Vall withith new valluet 2V • Copy the value into a new tmp and add to EXp2Tmp Saman Amarasinghe 2 6.035 ©MIT Fall 1998Copy Propagation Summarypy p g y • Forward Propagation within basic block •Maps – tmp2var: tells which variable to use instead of a given temporary variable • – var2set: inverse of tmp to var. tells which temps are mapped to a given variable by tmp to var • AlgorithmAlgorithm – For each statement • If any tmp variable in the RHS is in tmp2var replace it with var • If LHS var in var2set remove the variables in the set in tmp2var Saman Amarasinghe 3 6.035 ©MIT Fall 1998•Dead Code Elimination Summaryy • Backward Propagation within basic block •Map – A set of variables that are needed later in computation • AlgorithmAlgorithm – Every statement encountered • If LHS is not in the set, remove the statement •El ll h i bl i h RHS i Else put all the variables in the RHS into thhe set Saman Amarasinghe 4 6.035 ©MIT Fall 1998Summary So far… what’s nexty• Till now: How to analyze and transform ywithin a basic block • Next: How to do it for the entire procedure Saman Amarasinghe 5 6.035 ©MIT Fall 1998Outline • Reaching DefinitionsReaching Definitions • Available Expressions • LivenessReaching Definitionsg•Concept of definition and usep–a = x+y–is adefinition of aad o o a– is a use of x and y• A definition reaches a use if• A definition reaches a use if– value written by definitionmay be read by use– may be read by useSaman Amarasinghe 7 6.035 ©MIT Fall 1998Reaching Definitionsgs = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i = i + 1; return sSaman Amarasinghe 8 6.035 ©MIT Fall 2006aa aab oa o a•Reaching Definitions and Constant PropagationConstant Propagation • Is a use of a variable a constant? Can replace variable with constant– Then use is in fact a constant g– Check all reaching definitions –If all assign variable to same constant • Can replace variable with constantSaman Amarasinghe 9 6.035 ©MIT Fall 1998Is a Constant in s = s+a*b?s = 0; Yes!a = 4; i = 0;k == 0On all reaching definitionsk0b = 1; b = 2;a = 4; ;i < ns = s + a*b;i = i + 1;return sSaman Amarasinghe 10 6.035 ©MIT Fall 2006;Constant Propagation TransformTransforms = 0; Yes!a = 4; i = 0;k == 0On all reaching definitionsk0b = 1; b = 2;a = 4; ;i < ns = s + 4*b;i = i + 1;return sSaman Amarasinghe 11 6.035 ©MIT Fall 2006;Is b Constant in s = s+a*b?s = 0; No!a = 4; i = 0;k == 0One reaching definition withk0b = 1; b = 2;b = 1One reaching; ;i < ngdefinition withb = 2s = s + a*b;i = i + 1;return sSaman Amarasinghe 12 6.035 ©MIT Fall 2006;Splittings = 0; a = 4;pgPreserves Information Lost At Mergesa4;i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i = i + 1; return ss = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i < ns = s + a*b;Saman Amarasinghe 13 6.035 ©MIT Fall 2006ssab;i = i + 1; return sssab;i = i + 1; return sSplittings = 0; a = 4;pgPreserves Information Lost At Mergesa4;i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i = i + 1; return ss = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < n+*1i < n+*2Saman Amarasinghe 14 6.035 ©MIT Fall 2006s = s + a*1;i = i + 1; return ss = s + a*2;i = i + 1; return sa d o a a o o b o–eComputing Reaching DefinitionsDefinitions •Compute with sets of definitions p– represent sets using bit vectors –each definition has a position in bit vectorp • At each basic block, compute – definitions that reach start of blockdefinitions that reach start of block – definitions that reach end of block Do computation by simulating xecution of • Do computation by simulating execution of program until reach fixed point Saman Amarasinghe 15 6.035 ©MIT Fall 19981: s = 0;00000001 2 3 4 5 6 7;2: a = 4; 3: i = 0;k==0k==0111000011100001 2 3 4 5 6 7 1 2 3 4 5 6 711100004: b = 1; 5: b = 2;111000011100001111000 11101001111100111111112345671 2 3 4 5 6 711111001111111i < n111110011111001111111111111112345671 2 3 4 5 6 71111100111110011111111111111return s6: s = s + a*b;7 ii+1Saman Amarasinghe 16 6.035 ©MIT Fall 20060101111111110011111117: i = i+1;s atFormalizing Analysisg y • Each basic block has – IN - set of definitions that reach beginning of block – OUT - set of definitions that reach end of block – GEN - set of definitions generated in block – KILL - set of definitions killed in block GEN[sGEN[s = s ++ a*b; ii = i + 1 ] i + 1;] = 00000110000011 • *b • KILL[s = s + a*b; i = i + 1;] = 1010000 •C il hb ibl k di GEN Compiler scans each basic block to derive GEN and KILL sets Saman Amarasinghe 17 6.035 ©MIT Fall 1998Dataflow Equationsq• IN[b] = OUT[b1] U ... U OUT[bn] – where b1, ..., bn are predecessors of b in CFG • OUT[b] = (IN[b] - KILL[b]) U GEN[b] • IN[entry] = 0000000 • Result: system of equations Saman Amarasinghe 18 6.035 ©MIT Fall 1998•==•Solving Equationsgq• Use fixed point algorithm • Initialize with solution of OUT[b] = 0000000Initialize with solution of OUT[b] 0000000 • Repeatedly apply equations – IN[b] = OUT[b1] U U OUT[bn] IN[b] OUT[b1] U ... U OUT[bn] – OUT[b] = (IN[b] - KILL[b]) U GEN[b] • Until reach fixed pointUntil reach fixed point • Until equation application has no further effect • Use a worklist to track which equationUse a worklist to track which equation applications may have a further effect Saman Amarasinghe 19 6.035 ©MIT Fall 1998Reaching Definitions Algorithmg g for all nodes n in N OUT[n] = emptyset; // OUT[n] = GEN[n]; IN[Entry] = emptyset; OUT[Entry] = GEN[Entry]; Changed = N - { Entry }; // N = all nodes in graph while (Changed != emptyset) choose a node n in Changed; Changed = Changed - { n }; IN[n] = emptyset; for all nodes p in predecessors(n) IN[n] = IN[n] U OUT[p];[] [] [p]; OUT[n] = GEN[n] U (IN[n] - KILL[n]); if (OUT[n] changed) Saman Amarasinghe …