Range Analysis

The goal of Range Analysis is to collect, at each program statement, a map from integer-typed scalar variables to their symbolic value ranges, represented by a symbolic lower bound and an upper bound. In other words, a symbolic value range expresses the relationship between the variables that appear in the range. We use a similar approach as in Symbolic Range Propagation in the Polaris parallelizing compiler, with necessary adjustment for the C language, to compute the set of value ranges before each statement. The set of value ranges at each statement can be used in several ways. Pass writers can directly query the symbolic bound of a variable or can compare two symbolic expressions using the constraints given by the set of value ranges.

The high-level algorithm performs fix-point iteration in two phases when propagating the value ranges throughout the program. The first phase applies widening operations at nodes that have incoming back edges to guarantee the termination of the algorithm. The second phase compensates the loss of information due to the widening operations by applying narrowing operation to the node at which widening has occurred. During the fix-point iteration, the value ranges are merged at nodes that have multiple predecessors, and outgoing value ranges are computed by symbolically executing the statement. Two typical types of program semantics that cause such changes of value ranges are constraints from conditional expressions and assignments to variables.

Range analysis returns a map from each statement to its corresponding that contains the set of valid value ranges before each statement. The result of this analysis was verified with the C benchmarks in the SPEC CPU2006 suite. Range analysis does not handle integer overflow as it does not model the overflow but such cases are rare in normal correct programs. Following example shows how to invoke a range analyzer in a compiler pass:

 import cetus.analysis.*;
 ...
 Map<Statement, RangeDomain> range_map = RangeAnalysis.getRanges(procedure);
 RangeDomain range_domain = range_map.get(statement);
 // range_domain now contains the set of value ranges for the statement.
 range_domain.compare(expr1, expr2);

Following example shows a function and its range map created after the range analysis.

          int foo(int k)
                  []                    
          {                             
                  []                    
            int i, j;                   
                  []                    
            double a;                   
                  []                    
            for ( i=0; i<10; ++i )      
                  []                    
            {                           
                  [0<=i<=9]             
              a=(0.5*i);                
            }                           
                  [i=10]                
            j=(i+k);                    
                  [i=10, j=(i+k)]       
            return j;                   
          }                             

Since version 1.2, interprocedural range analysis is provided as an option to increase the accuracy of value ranges, which is still in experimental state. The following example shows the effect of this extension on the loop-parallelization pass. For this example, the Range test was used instead of the default Banerjee-Wolfe test.

int main()                                int main()
{                                         { ...
  double a[100];                          }
  foo(a, 0, 10);                          
  return 0;                               void foo(double *a, int lb, int ub)
}                                         {
                                     -->    int i;
void foo(double *a, int lb, int ub)         #pragma cetus private(i)
{                                           #pragma cetus parallel
  int i;                                    #pragma omp parallel for private(i)
  for (i=lb; i<ub; i++) {                   for (i=lb; i<ub; i++) {
    a[i] = a[i+10];                           a[i] = a[i+10];
  }                                         }
}                                         }