Unformatted text preview:

Dataflow AnalysisReaching DefinitionsReaching DefinitionsReaching Definitions and Constant PropagationComputing Reaching DefinitionsFormalizing AnalysisDataflow EquationsSolving EquationsReaching Definitions AlgorithmQuestionsAvailable ExpressionsComputing Available ExpressionsQuestionsGeneral CorrectnessDuality In Two AlgorithmsLiveness AnalysisWhat Use is Liveness Information?Conceptual Idea of AnalysisLiveness ExampleAlgorithmSimilar to Other Dataflow AlgorithmsAnalysis Information Inside Basic BlocksSummaryMIT 6.035Introduction to Dataflow AnalysisMartin RinardLaboratory for Computer ScienceMassachusetts Institute of TechnologyDataflow Analysis• Used to determine properties of program that involve multiple basic blocks• Typically used to enable transformations– common sub-expression elimination – constant and copy propagation– dead code elimination• Analysis and transformation often come in pairsReaching Definitions• Concept of definition and use–a = x+y– is a definition of a– is a use of x and y• A definition reaches a use if – value written by definition– may be read by useReaching Definitionss = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i = i + 1; return sReaching Definitions and Constant Propagation• Is a use of a variable a constant?– Check all reaching definitions– If all assign variable to same constant– Then use is in fact a constant• Can replace variable with constantIs a Constant in s = s+a*b?s = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i = i + 1; return sYes!On all reaching definitionsa = 4Constant Propagation Transforms = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < ns = s + 4*b;i = i + 1; return sYes!On all reaching definitionsa = 4Is b Constant in s = s+a*b?s = 0; a = 4; i = 0;k == 0 b = 1; b = 2;i < ns = s + a*b;i = i + 1; return sNo!One reaching definition withb = 1One reaching definition withb = 2SplittingPreserves Information Lost At Mergess = 0; a = 4; 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 = i + 1; return si < ns = s + a*b;i = i + 1; return sSplittingPreserves Information Lost At Mergess = 0; a = 4; 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*1;i = i + 1; return si < ns = s + a*2;i = i + 1; return sComputing Reaching Definitions• Compute with sets of definitions– represent sets using bit vectors– each definition has a position in bit vector• At each basic block, compute– definitions that reach start of block– definitions that reach end of block• Do computation by simulating execution of program until reach fixed point00000001: s = 0; 2: a = 4; 3: i = 0;k == 0 4: b = 1; 5: b = 2;i < n6: s = s + a*b;7: i = i + 1; return s1110000 1110000111110011111001111100111111111111111111111Formalizing Analysis• 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[s = s + a*b; i = i + 1;] = 0000011• KILL[s = s + a*b; i = i + 1;] = 1010000• Compiler scans each basic block to derive GEN and KILL setsDataflow Equations• 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 equationsSolving Equations• Use fixed point algorithm• Initialize with solution of OUT[b] = 0000000• Repeatedly apply equations– IN[b] = OUT[b1] U ... U OUT[bn]– OUT[b] = (IN[b] - KILL[b]) U GEN[b]• Until reach fixed point • Until equation application has no further effect• Use a worklist to track which equation applications may have a further effectReaching Definitions Algorithmfor all nodes n in N OUT[n] = emptyset; // OUT[n] = GEN[n];Changed = N; // N = all nodes in graphwhile (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];OUT[n] = GEN[n] U (IN[n] - KILL[n]);if (OUT[n] changed)for all nodes s in successors(n) Changed = Changed U { s };Questions• Does the algorithm halt?– yes, because transfer function is monotonic– if increase IN, increase OUT– in limit, all bits are 1• If bit is 1, is there always an execution in which corresponding definition reaches basic block?• If bit is 0, does the corresponding definition ever reach basic block?• Concept of conservative analysisAvailable Expressions• An expression x+y is available at a point p if – every path from the initial node to p evaluates x+y before reaching p, – and there are no assignments to x or y after the evaluation but before p.• Available Expression information can be used to do global (across basic blocks) CSE• If expression is available at use, no need to reevaluate itComputing Available Expressions• Represent sets of expressions using bit vectors• Each expression corresponds to a bit• Run dataflow algorithm similar to reaching definitions• Big difference– definition reaches a basic block if it comes from ANY predecessor in CFG– expression is available at a basic block only if it is available from ALL predecessors in CFG0000a = x+y;x == 0 x = z;b = x+y;i < nc = x+y;i = i+c;d = x+yi = x+y; Expressions1: x+y2: i<n3: i+c4: x==010011000100011001100a = x+y;t = a;x == 0 x = z;b = x+y;t = b;i < nc = t;i = i+c;d = t;i = t; Global CSE Transform0000Expressions1: x+y2: i<n3: i+c4: x==0100110001100must use same tempfor CSE in all blocks10001100Formalizing Analysis• Each basic block has– IN - set of expressions available at start of block– OUT - set of expressions available at end of block– GEN - set of expressions computed in block– KILL - set of expressions killed in in block• GEN[x = z; b = x+y] = 1000• KILL[x = z; b = x+y] = 1001• Compiler scans each basic block to derive GEN and KILL setsDataflow Equations• IN[b] = OUT[b1] intersect ... intersect OUT[bn]– where b1, ..., bn are predecessors of b in CFG• OUT[b] = (IN[b] - KILL[b]) U GEN[b]• IN[entry] = 0000• Result: system of equationsSolving Equations• Use fixed point algorithm• IN[entry] = 0000• Initialize OUT[b] = 1111• Repeatedly apply equations– IN[b] = OUT[b1] intersect ... intersect OUT[bn]– OUT[b] = (IN[b] - KILL[b]) U GEN[b]• Use a worklist algorithm to reach fixed pointAvailable Expressions


View Full Document

MIT 6 035 - Introduction to Dataflow Analysis

Download Introduction to Dataflow Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Dataflow Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Dataflow Analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?