Transfer functions

Each transfer function should specify the effect of that kind of node on the flow value. Recall that transfer functions should be monotonic in order to ensure convergence (using gen and kill sets satisfies this property). Note that in this implementation, there are no ``in'' and ``out'' values--rather, the transfer function should transform the in value into the out value.

Like the walker, if no transfer function is specified, then control passes to the transfer function of the super-class. Thus, all nodes can be handled uniformly by defining only the flow_node method. A transfer function should modify the FlowVal input appropriately. For example, this transfer function simply sets the bit corresponding to the input binary node:

void my_analysis::flow_binary(FlowVal * v, binaryNode * the_binary, Point p)
{
  my_flowval * my_v = (my_flowval *) v;
  if (p == Exit)
    my_v->bits().set(_defs_map[the_binary]);
}

Each transfer function is called twice, once for the entry point and once for the exit point. The Point argument indicates which call is being made. It may be useful to store the mapping from objects to bits in the FlowProblem class.

Many dataflow analysis problems can be expressed with a single transfer function that uses ``gen'' and ``kill'' sets. Each node can store two FlowVals called gen and kill, which we can then reference in the transfer function. Before running the analysis framework, we pass over the AST and populate the gen and kill sets. For example, we could use the following walker to set-up the sets for reaching definitions:

class rd_genkill_walker : public Walker
{
private:
  rd_genkill_walker()
    : Walker(Preorder, Subtree)
   {}
public:
  virtual void at_binary(binaryNode * the_binary, Order ord) {
    if (the_binary->op()->is_assignment()) {
      exprNode * lhs = the_binary->left();
      if (lhs->typ() == Id) {
        my_flowval * g = set_up_gen((idNode *)lhs, the_binary);
        my_flowval * k = set_up_kill((idNode *)lhs, the_binary);
        the_binary->gen(g);
        the_binary->kill(k);
      }
    }
  }
  // And a similar function for unary assignments...
};

Make sure to clean up the gen and kill sets at the end of analysis and reset the gen and kill members to null. The corresponding transfer function is the same for all nodes, so we only override the flow_node method of FlowProblem:

void reaching_defs::flow_node(FlowVal * v, Node * the_node, Point p)
{
  my_flowval * rv = (my_flowval *)v;
  if (p == Exit)
    if (the_node->gen() && the_node->kill()) {

      my_flowval * g = (my_flowval *) the_node->gen();
      my_flowval * k = (my_flowval *) the_node->kill();

      rv->bits() &= ~ k->bits();
      rv->bits() |= g->bits();
    }
}

This method operates at the exit point of the dataflow function. If the given node has gen and kills sets defined, then it casts them to the proper type and performs the bitset operations that correspond to the equation out = gen U ( in - kill).