11Class 3• Review; questions• Basic Analyses (3)• Assign (see Schedule for links)• Representation and Analysis of Software (Sections 1-5)• Additional readings: • Data-flow analysis• Control/program-dependence analysis• Problem Set 2: due 9/1/0922Review, Questions?• Data-flow analysis33Data-flow Analysis44Introduction (overview)Data-flow analysis provides information for these and other tasks by computing the flow of different types of data to points in the programy For structured programs, data-flow analysis can be performed on an AST; in general, intraprocedural(global) data-flow analysis performed on the CFGy Exact solutions to most problems are undecidable—e.g.,y May depend on inputy May depend on outcome of a conditional statementy May depend on termination of loopThus, we compute approximations to the exact solution55Introduction (overview)y Approximate analysis can overestimate the solution:y Solution contains actual information plus some spurious information but does not omit any actual informationy This type of information is safe or conservativey Approximate analysis can underestimate the solution:y Solution may not contains all information in the actual solutiony This type of information in unsafey For optimization, need safe, conservative analysisy For software engineering tasks, may be able to use unsafe analysis informationy Biggest challenge for data-flow analysis: provide safe but precise (i.e., minimize the spurious information) information in an efficient way66Introduction (overview)y Approximate analysis can overestimate the solution:y Solution contains actual information plus some spurious information but does not omit any actual informationy This type of information is safe or conservativey Approximate analysis can underestimate the solution:y Solution may not contains all information in the actual solutiony This type of information in unsafey For optimization, need safe, conservative analysisy For software engineering tasks, may be able to use unsafe analysis informationy Biggest challenge for data-flow analysis: provide safe but precise (i.e., minimize the spurious information) information in an efficient way77Compute the flow of data to points in the program—e.g.,y Where does the assignment to I in statement 1 reach?y Where does the expression computed in statement 2 reach?y Which uses of variable J are reachable from the end of B1?y Is the value of variable I live after statement 3?Interesting points before and after basic blocks or statements1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B4Introduction (overview)88Data-flow Problems (reaching definitions)A definition of a variable or memory location is a point or statement where that variable gets a value—e.g., input statement, assignment statement.A definition of A reaches a point p if there exists a control-flow path in the CFG from the definition to p with no other definitions of A on the path (called a definition-clear path)Such a path may exist in the graph but may not be executable (i.e., there may be no input to the program that will cause it to be executed); such a path is infeasible. 1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B499Data-flow Problems (reaching definitions)y Where are the definitions in the program?y Of variable I: y Of variable J: y Which basic blocks (before block) do these definitions reach?y Def 1 reaches y Def 2 reaches y Def 3 reaches y Def 4 reaches y Def 5 reaches 1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B41010Graph for examples1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B41111Data-flow Problems (reaching definitions)y Where are the definitions in the program?y Of variable I: 1, 3y Of variable J: 2, 4, 5y Which basic blocks (before block) do these definitions reach?y Def 1 reaches B2 y Def 2 reaches B1, B2, B3y Def 3 reaches B1, B3, B4y Def 4 reaches B4y Def 5 reaches exit1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B41212Iterative Data-flow Analysis (reaching definitions)Method:1. Compute two kinds of local information (i.e., within a basic block) y GEN[B] is the set of definitions that are created (generated) within By KILL[B] is the set of definitions that, if they reach the point before B (i.e., the beginning of B) won’t reach the end of B orPRSV[B] is the set of definitions that are preserved (not killed) by B2. Compute two other sets by propagationy IN[B] is the set of definitions that reach the beginning of B; also RCHin[B]y OUT[B] is the set of definitions that reach the end of B; also RCHout[B]1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B41313Method (cont’d):3. Propagation method:y Initialize the IN[B], OUT[B] sets for all By Iterate over all B until there are no changes to the IN[B], OUT[B] setsy On each iteration, visit all B, and compute IN[B], OUT[B] asy IN[B] = U OUT[P], P is a predecessor of By OUT[B] = GEN[B] U (IN[B] ∩ PRSV[B]) ory OUT[B] = GEN[B] U (IN[B] – Kill[B]) 1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B4Iterative Data-flow Analysis (reaching definitions)14141. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B4Iterative Data-flow Analysis (reaching definitions)1515Iterative Data-flow Analysis (reaching definitions)InitGENInitKILLInitINInitOUTIter1INIter1OUTIter2INIter2OUT12341616Data-flow for example (set approach)All entries are sets; sets in red indicate changes from last iteration thus, requiring another iteration of the algorithmInitGENInitKILLInitINInitOUTIter1INIter1OUTIter2INIter2OUT1 1,2 3,4,5 -- 1,2 3 1,2 2,3 1,223 1 -- 3 1,2 2,3 1,2 2,33 4 2,5 -- 4 2,3 3,4 2,3 3,44 5 2,4 -- 5 3,4 3,5 3,4 3,51. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B4Iterative Data-flow Analysis (reaching definitions)17Data-flow for example (bit-vector approach)4321Iter1OUTIter1INInitOUTInitINInitKILLInitGEN1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B4Iterative Data-flow Analysis (reaching definitions)18Data-flow for example (bit-vector approach)0010100110000010000001010000014001100110000010000000100100010301100110000010000000100000010021100000100110000000000111110001Iter1OUTIter1INInitOUTInitINInitKILLInitGEN1. I := 22. J := I + 13. I := 14. J := J + 15. J := J - 4B1B2B3B4Iterative Data-flow Analysis (reaching definitions)19algorithm ReachingDefinitionsInput: CFG w/GEN[B], KILL[B] for