cetus.analysis

Class RangeAnalysis

java.lang.Object

cetus.analysis.AnalysisPass

cetus.analysis.RangeAnalysis

public class RangeAnalysis
extends AnalysisPass

RangeAnalysis performs symbolic range propagation for the programs by symbolically executing the program and abstracting the values of integer variables with a symbolic bounds. The implementation is based on Symbolic Range Propagation by Blume and Eigenmann, which was implemented for the Fortran77 language.

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 RangeDomain 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:

 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.
 

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;                   
          }                             
 

Field Summary

Fields

Modifier and Type	Field and Description
static int	RANGE_EMPTY Option for disabling range computation
static int	RANGE_INTER Option for enforcing inter-procedural analysis
static int	RANGE_INTRA Option for enforcing intra-procedural analysis
static int	RANGE_PRAGMA Option for enforcing use of range pragma and constraint

Constructor Summary

Constructors

Constructor and Description
RangeAnalysis(Program program) Constructs a range analyzer for the program.

Method Summary

Methods

Modifier and Type	Method and Description
static RangeDomain	extractRanges(Expression e)
java.lang.String	getPassName() Returns the pass name.
static RangeDomain	getRangeDomain(Statement stmt) Returns a range domain for the given statement.
java.util.Map<Statement,RangeDomain>	getRangeMap(Procedure proc) Performs range analysis for the procedure and returns the result.
static java.util.Map<Statement,RangeDomain>	getRanges(SymbolTable symtab) Returns a range map created for the symbol table object.
static java.util.Map<Statement,RangeDomain>	getRanges(SymbolTable symtab, int temporal_option) Enforces use of the specified option for computing the ranges
static void	invalidate() Invalidates range domains stored in the static spaces.
static RangeDomain	query(Statement stmt) Returns a range domain associated with the specified statement.
static void	registerSafeFunction(java.lang.String name, java.lang.String... names) Register the specified function names in the safe list of function calls.
void	start() Starts range analysis for the whole program.
static java.lang.String	toPrettyRanges(Traversable t, java.util.Map<Statement,RangeDomain> ranges, java.lang.Integer indent) Returns the range map in a pretty format.

Methods inherited from class cetus.analysis.AnalysisPass

run

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

RANGE_EMPTY

public static final int RANGE_EMPTY

Option for disabling range computation

See Also:

Constant Field Values

RANGE_INTRA

public static final int RANGE_INTRA

Option for enforcing intra-procedural analysis

See Also:

Constant Field Values

RANGE_INTER

public static final int RANGE_INTER

Option for enforcing inter-procedural analysis

See Also:

Constant Field Values

RANGE_PRAGMA

public static final int RANGE_PRAGMA

Option for enforcing use of range pragma and constraint

See Also:

Constant Field Values

Constructor Detail

RangeAnalysis

public RangeAnalysis(Program program)

Constructs a range analyzer for the program. The instantiated constructor is used only internally.

Parameters:

program - the input program.

Method Detail

getPassName

public java.lang.String getPassName()

Returns the pass name.

Specified by:

getPassName in class AnalysisPass

Returns:

the pass name in string.

start

public void start()

Starts range analysis for the whole program. this is useful only for testing the range analysis.

Specified by:

start in class AnalysisPass

getRangeMap

public java.util.Map<Statement,RangeDomain> getRangeMap(Procedure proc)

Performs range analysis for the procedure and returns the result.

Parameters:

proc - the input procedure.

Returns:

the range map for the procedure.

toPrettyRanges

public static java.lang.String toPrettyRanges(Traversable t,
                              java.util.Map<Statement,RangeDomain> ranges,
                              java.lang.Integer indent)

Returns the range map in a pretty format.

Parameters:

t - the traversable object.

ranges - the range map.

indent - the indent for pretty printing.

Returns:

the string in a pretty format.

getRanges

public static java.util.Map<Statement,RangeDomain> getRanges(SymbolTable symtab,
                                             int temporal_option)

Enforces use of the specified option for computing the ranges

getRanges

public static java.util.Map<Statement,RangeDomain> getRanges(SymbolTable symtab)

Returns a range map created for the symbol table object. It is more general to support range map for a traversable object but supporting this functionality on an object that contains collection of statement object, i.e. symbol table, is more natural.

Parameters:

symtab - the symbol table object whose range map is collected.

Returns:

the range map for the traversable object.

getRangeDomain

public static RangeDomain getRangeDomain(Statement stmt)

Returns a range domain for the given statement.

Parameters:

stmt - the input statement.

Returns:

the out range domain for the statement.

extractRanges

public static RangeDomain extractRanges(Expression e)

query

public static RangeDomain query(Statement stmt)

Returns a range domain associated with the specified statement. It will return an already existing range domain if one is found. Otherwise, the range domains for the procedure containing stmt are recomputed , and then the associated range domain is returned.

Parameters:

stmt - the statement of interest.

Returns:

the associated range domain.

invalidate

public static void invalidate()

Invalidates range domains stored in the static spaces. Every IR-changing passes need to call this method.

registerSafeFunction

public static void registerSafeFunction(java.lang.String name,
                        java.lang.String... names)

Register the specified function names in the safe list of function calls. During range analysis these functions are considered to have no side effects at all.