cetus.analysis

Class RangeTest

java.lang.Object

cetus.analysis.RangeTest

All Implemented Interfaces:

DDTest

public class RangeTest
extends java.lang.Object
implements DDTest

Symbolic Range Test for disproving loop-carried dependences between two subscript expressions. Unlike the Banerjee-Wolfe test, the Range test does not solve the problem under the all possible direction vectors; it disproves dependences between a subscript pairs. Because of the DDT driver calling a DDT solver with a specific direction vector, the Range test should also return a correct answer when given such a direction vector. To address this issue, the Range test records a list of direction vectors that do not incur any dependences once it disproves a dependence and returns an appropriate answer based on the "independent direction vectors". The Range test utilizes the power of the symbolic range analysis as much as possible when performing the test. For example, when computing minimum and maximum symbolic values of a subscript expression at any given iteration, it just expands the index variables of the enclosing loops using the utility methods given by RangeDomain.

Constructor Summary

Constructors

Constructor and Description
RangeTest(SubscriptPair pair) Constructs a range test problem from the given subscript pair.

Method Summary

Methods

Modifier and Type	Method and Description
static void	compressDV(java.util.List<DependenceVector> dvs) Compresses direction vectors as much as possible.
java.util.LinkedList<Loop>	getCommonEnclosingLoops() Returns the list of loops that commonly enclose the subscript pair.
static RangeTest	getInstance(SubscriptPair pair) Returns an instance of a range test problem with the specified subscript pair.
boolean	isTestEligible() Checks if this test can proceed.
boolean	testDependence(DependenceVector dvec) Test dependence on the specified direction vector.
java.lang.String	toString() Returns a string that shows a snapshot of the current range test problem.

Methods inherited from class java.lang.Object

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

Constructor Detail

RangeTest

public RangeTest(SubscriptPair pair)

Constructs a range test problem from the given subscript pair.

Parameters:

pair - the subscript pair to be tested for dependency.

Method Detail

getInstance

public static RangeTest getInstance(SubscriptPair pair)

Returns an instance of a range test problem with the specified subscript pair. This method either constructs a new instance or returns an existing instance if pair matches one in the history cache.

testDependence

public boolean testDependence(DependenceVector dvec)

Test dependence on the specified direction vector.

Specified by:

testDependence in interface DDTest

Parameters:

dvec - direction vector to be tested on.

Returns:

whether dependence exists.

isTestEligible

public boolean isTestEligible()

Checks if this test can proceed.

Specified by:

isTestEligible in interface DDTest

Returns:

true if it is, false otherwise.

getCommonEnclosingLoops

public java.util.LinkedList<Loop> getCommonEnclosingLoops()

Returns the list of loops that commonly enclose the subscript pair.

Specified by:

getCommonEnclosingLoops in interface DDTest

Returns:

the list of common loops.

compressDV

public static void compressDV(java.util.List<DependenceVector> dvs)

Compresses direction vectors as much as possible.

toString

public java.lang.String toString()

Returns a string that shows a snapshot of the current range test problem.

Overrides:

toString in class java.lang.Object

Returns:

test information in string.