Notes for week 15

Day 1

Flow Graphs

1. Show the flow graph for the basic block code overlay.

   Note that the only block following an unconditional goto is the target of the goto. Blocks ending in a conditional goto are followed by both the target of a conditional goto and the block following. Branches do not distinguish between conditional and unconditional branches.

2. Terminology
   1. Block B is a predecessor of block C if there is an edge that flows from B to C. B pred C
   2. If B is the predecessor of C then C is a successor of B. C succ B
   3. In the diagram, we can reach B4 from B2 but B2 is not a predecessor of B4 since there is no edge between the two.
   4. Node B dominates node C if we must pass through B to get to C when starting at the beginning of the graph. B is an immediate dominator of node C if it is the last dominator we pass through before reaching C. Go through flow diagram to get the dominance.
   5. Finding loops by finding back edges - an edge of the flow diagram whose head dominates its tail. B10 -> B2 and B7 -> B4 are back edges.
3. Data-Flow Equations
   1. To optimize globally must keep track of the movement of information between basic blocks.
   2. Example of the problem j := j+1 in Block B7 where did the j come from? Initialized in B3 not changed before B7 .
   3. Things considered in data-flow analysis
      1. What happens to variables and expression values within a block(used? or updated?)
      2. How variables or values reach the beginning of a block.
      3. Where they go from the end of a block.
   4. Four forms of flow analysis
      1. Forward
      2. Backward
      3. Any path to or from a block
      4. All paths to and from a block

Day 2

1. Forward-Flow Analysis
   1. An expression is available at a point p, it its value has been computed some place before p.
      1. What's available coming into a block? ina(Bi) = intersection of outa(Bj) where Bj pred Bi
      2. Within a block an expression is killed if any of its operands are changed.
      3. An expression is generated in a block if its value is computed and not killed in the block. outa(Bi) = gen[Bi] »(ina(Bi) - kill(Bi) ina(B1) = { }
   2. Use-definition (ud-) chaining. The ud-chain for any use of a variable is the list of all definitions in a program that reach that use. (union of the outs from predecessor blocks.
2. Backward-Flow Analysis (use intersection and union of successor.
3. Solving the Data-Flow Equations.
   1. Compute the kill and gen for each block.

      Block	Gen	Kill	In	Out
      1	{1}	{}	{}	{1}
      2	{}	{}	{}	{}
      3	{3,4}	{13,14}	{}	{3,4}
      4	{}	{}	{}	{}
      5	{}	{}	{}	{}
      6	{1,3}	{3}	{}	{1,3}
      7	{1,4}	{4}	{}	{1,4}
      8	{}	{}	{}	{}
      9	{20}	{}	{}	{20}
      10	{30}	{1}	{}	{30}
      11	{}	{}	{}	{}

   2. Do a first interation using the Flow-graph