In the last post, we discussed a method to find common subexpression on the entire control-flow graph using partitioning.  Today, we're going to talk about another classic way of accomplishing this goal using data-flow analysis.  Then I think I'm going to discuss topics other than compilers... at least for a while.

The first thing we need to do is to define what it means for an expression to be redundant.  So far we've done this two ways.  Initially we gave an algorithm (value numbering) to find redundant expressions, and implicitly defined an expression to be redundant if value numbering declared it so.  Later we gave a definition of congruence of operations, and gave an algorithm for finding congruent operations.  Congruence was related to redundant expressions, but two operations being congruent did not necessarily mean that one was redundant. 

For today's discussion, we're no longer going to insist that all names are unique.  This means that we have to deal with blocks that redefine variables used in expressions.  Say we have some expression of the form x + y.  If some basic block redefines either x or y, we say the block has killed the expression x + y.  With this terminology out of the way, we can now give a definition for redundant expressions.

Definition:  An expression e is said to be Available at a block b if e is defined on every control-flow path that reaches b and e is not killed on any of these control-flow paths.  The set of all expression available at a block b is referred to as Avail(b).

This is a very intuitive definition of e, often referred to as the meet over all paths solution.  Unfortunately, the definition gives us no ideas how we can compute these available-expression sets.  enumerating all control-flow paths that reach a block b sounds hard, and how should we deal with loops?  This is where data-flow analysis comes in.

In order to calculate available expressions for a block b, let's start by assuming that we've already successfully computed these sets for every block in the procedure except for b.  We can then easily figure out available expressions for b.  If an expression is available at all predecessors of b and it isn't killed in any of those predecessors, it's clearly available at b.  Further, any expression that is defined in all predecessors of b and isn't killed in any predecessor is also available at b.  For every block in the control-flow graph, we can calculate two sets

DefsOut(b) = {every expression defined in b and not killed  b}

Killed(b) = {all expressions that are killed as a result of an assignment in b}

Both of these sets can easily be computed by examining the block.  We can then define the set of expressions available in b as follows:

(*)    Avail(b) = Intersect(over all predecessors p of b)  [DefsOut(p) U (Avail(p) - Killed(p))]     

Where the minus sign means set substraction.

Now this works if we already have Avail sets calculated for every block other than b, but let's make a leap.  Let's start everyone off with empty Avail sets, and run through the graph applying formula (*).  Once we're done, run through the graph again applying the formula.  Keep doing this until the sets we calculate stop changing.  Once the sets stop changing, we hope that we've calculated the meet-over-all-paths solution above.  Here's an algorithm that accomplishes this (with a few improvements);

Worklist = {all blocks}

while Worklist isn't empty
    pull a node b off the worklist
(**)Avail(b) = Avail(b) U Intersect(over all predecessors p of b)  [DefsOut(p) U (Avail(p) - Killed(p))]     
    if the calculation caused Avail(b) to change
        add all successors of b onto Worklist

Now there are three basic questions to ask about this algorithm:  does it terminate, does it calculate the correct answer, and how fast is it.  It should be obvious that this algorithm terminates.  Every iteration either leaves the Avail sets alone or increases them monotonically, so at some point it must finish.  If the control-flow graph is acyclic, this algorithm intuitively works.  If you imagine the set of available expressions as starting from the source node and being pushed out to successor nodes (though successor nodes can also act as sources of expressions), each iteration pushes the information a little further down the graph;  since there are no cycles, eventually all possible execution paths are followed, and we're done.  This intuition is very similar to the rational behind the Bellman-Ford algorithm for shortest paths in graphs.

In general flow graphs, whether the above algorithm correctly calculates the meet-over-all-paths solution depends on the definition of the expression (**).  If this expression satisfies certain properties (which causes terminology geeks to call it admissible), the algorithm will correctly calculate the meet-over-all-paths solution.  It turns out that our definition for Avail has these properties, so the above algorithm works.  The proof that this algorithm works is far from obvious, and is based off of a branch of mathematics called Lattice Theory.

The last question is... how fast?  This also depends on characteristic of the expression (**).  Further, the order in which we look at nodes has a huge impact on how many iterations are needed to reach a fixed point.  For expressions like (**) that cause data to flow downwards, a good bet might be to order the worklist by the block's index in a reverse postorder walk.

Now that we have or Avail sets, what should we do with them?  Well first of all, we need to make sure to generate global names for all the expressions we care about.  Now we can run the local value numbering algorithm from several posts back on each block, but instead of starting out with an empty hash table we can start off the hash table with the list of available expressions for the block.  Generating global names will generate a lot of extra copies and useless variables, but later compiler passes will find these and eliminate them.

Next time I think I might get back to some math-related topics.