Calculating range expressions

Here is some sample code that will determine the range of values that a single reduction array subscript may take.

// Initialization code.  Execute only once in your pass.

#include "/groups/polaris/cvdl/AIRangeDict.h"
// #include "/groups/polaris/cvdl/ControlRangeDict.h"
#include "/groups/polaris/cvdl/RangeAccessor.h"
#include "/groups/polaris/cvdl/range.h"

// Determine the set of ranges holding for each statement in the the
// program unit.

RangeDict *ranges = new AIRangeDict(pgm);

// A faster but less accurate way to compute ranges for a program.
// (Twice as fast, but only collects ranges from IF conditionals and
// loop bounds.)

// RangeDict *ranges = new ControlRangeDict(pgm);

 ...

// Code executed for each reduction statement.  This example only
// looks at the first array subscript of the reduction.  It can
// easily be extended to handle multiple array subscripts.

// Create an object to compare expressions, using the ranges
// that hold for a given statement.  Reduction_stmt is the current
// reduction statement.

RangeAccessor accessor(ranges, reduction_stmt);

// Compute the range taken by the first array subscript of the
// reduction statement.  Loop_variant_vars is a set of variables
// (i.e. RefSet<Symbol>) that are loop variant for the loop in which
// the reduction is being parallelized.  Range_expr is the 
// resulting range.

Expression *range_expr
    = accessor.eliminate_vars(reduction_stmt.lhs().subscript().arg_list()[0],
                              loop_variant_vars);

// The returned expression may be a RangeExpr object, indicating the
// range that the reduction's array subscript may take, or it
// may be some other expression, indicating a range that spans a
// single element.  So, we would need to test whether range_expr
// is type RANGE_OP or not.

Expression *lower_bound, *upper_bound;

if (range_expr->op() == RANGE_OP) {
    RangeExpr range = * (RangeExpr *) range_expr;
    lower_bound = range.grab_lb();
    upper_bound = range.grab_ub();
}
else {
    lower_bound = range_expr->clone();
    upper_bound = range_expr->clone();
}	

delete range_expr;

Now, if you wish to merge two ranges together, you can just call the routine union_ranges(), found in /groups/polaris/cvdl/range/range_util.h.

To learn more about the interfaces to the range propagation pass, read the comments in range.h, AIRangeDict.h, ControlRangeDict.h, RangeAccessor.h, RangeComparator.h, range_utils.h, and Relation.h. (Reading just range.h, RangeAccessor.h, and part of RangeComparator.h should be sufficient.)