Methods

The analysis framework needs four methods on the flow value: meet, to_top, clone, and diff. The meet method implements the confluence operator, denoted by V. It must satisfy the following algebraic properties:

Associative

: x V (y V z) = (x V y) V z

Commutative

: x V y = y V x

idempotent

: x V x = x

These properties hold for the set operations, union and intersection, which are the most common meet operators. In the FlowVal class, notice that the meet method only takes one argument. The implementation should modify the this object so that it holds the result value. Here is an example meet method -- it implements set union using bitsets (the bits() method returns a reference to the _def_bits member variable).

void my_flowval::meet(const FlowVal * other)
{
  my_flowval * o = (my_flowval *) other;
  bits() |= o->bits();
}

The to_top method is used to set the flow value to the lattice top T. Recall that the top value must satisfy the following algebraic property: x V T = x. If the meet operator is set union, then the to_top method should set the flow value to empty-set:

void my_flowval::to_top()
{
  for (int i = 0; i < bits().size(); ++i)
    bits().reset(i);
}

The clone method is used when the flow of control splits (e.g., an if statement). It should return an identical copy of the flow value (make sure any sets are copied). The diff method should compare the flow value to the input flow value and return true if they are different. This method is used to test for convergence.