scale.score.dependence
Class DataDependence

java.lang.Object
  scale.score.dependence.DataDependence

Direct Known Subclasses:

BanerjeeTest, OmegaTest

public abstract class DataDependence
extends java.lang.Object

The base class for computing array data dependences.

$Id: DataDependence.java,v 1.42 2007-10-04 19:58:25 burrill Exp $

Copyright 2007 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

After a data dependence object is created, dependence testing is performed by calling ddTest. After testing is complete, the dependence object contains information in both directions. That is, from the first node to the second and the second node to the first. To add dependence edges or print dependence information, the getForwardDependence and getBackwardDependence methods must be called to filter the dependence testing results.

Field Summary

protected int	bnest The common nesting level of the two references.
static int	cEqDependent Indicates that the data dependence test found that the two array accesses access the same array element for every value of the loop induction variable.
static int	cFailed Indicates that the data dependence test failed.
static int	cIndependent Indicates that the data dependence test found that the two array accesses never access the same array element.
static int	cLCDependent Indicates that the data dependence test found that the two array accesses may access the same array element for different values of the loop induction variable.
protected LoopHeaderChord	cloop Loop containing both.
static int	cUnkDependent Indicates that the data dependence test found that the two array accesses may access the same array element.
protected long[]	ddinfo The data dependence information of the two references.
protected LoopHeaderChord	iloop Loop containing inode.
protected SubscriptExpr	inode An array reference.
protected LoopHeaderChord[]	loopInfo The loop information for the current references.
protected LoopHeaderChord	oloop Loop containing onode.
protected SubscriptExpr	onode An array reference.
protected int	precedes It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".
static java.lang.String[]	result Map the data dependence result from an integer to a string representation.
protected Scribble	scribble The CFG from which the data dependence isfound.

Constructor Summary

DataDependence(Scribble scribble)
Create an object for dependence testing.

Method Summary

abstract int	ddTest(SubscriptExpr onode, SubscriptExpr inode, LoopHeaderChord oloop, LoopHeaderChord iloop, int precedes) Determine if there is a dependence between two references.
long[]	getBackwardDependences() Return backwards dependence information.
long[]	getDDInfo() Return the data dependence information for these two references.
abstract Vector<long[]>	getDependenceInfo(boolean forward) Compute data dependences in one direction.
long[]	getForwardDependences() Return forward dependence information.
void	initialize(SubscriptExpr onode, SubscriptExpr inode, LoopHeaderChord oloop, LoopHeaderChord iloop, int precedes)
abstract void	spatialTest(SubscriptExpr onode, SubscriptExpr inode, LoopHeaderChord oloop, LoopHeaderChord iloop, int precedes)

Methods inherited from class java.lang.Object

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

Field Detail

cIndependent

public static final int cIndependent

Indicates that the data dependence test found that the two array accesses never access the same array element. For example, a[2] and a[3] never access the same array element.

See Also:

Constant Field Values

cUnkDependent

public static final int cUnkDependent

Indicates that the data dependence test found that the two array accesses may access the same array element. For example, a[2] and a[i] will access the same element when i ≡ 2.

See Also:

Constant Field Values

cLCDependent

public static final int cLCDependent

Indicates that the data dependence test found that the two array accesses may access the same array element for different values of the loop induction variable. The distance and direction may be known. For example, a[i] and a[i-1] are dependent with a distance of 1 and a direction of < while a[i] and a[i] are dependent with a distance of 0 and a direction of =.

See Also:

Constant Field Values

cEqDependent

public static final int cEqDependent

Indicates that the data dependence test found that the two array accesses access the same array element for every value of the loop induction variable. The distance and direction may be known. For example, a[i] and a[i] are dependent with a distance of 0 and a direction of =.

See Also:

Constant Field Values

cFailed

public static final int cFailed

Indicates that the data dependence test failed.

See Also:

Constant Field Values

result

public static final java.lang.String[] result

Map the data dependence result from an integer to a string representation.

onode

protected SubscriptExpr onode

An array reference.

inode

protected SubscriptExpr inode

An array reference.

precedes

protected int precedes

It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".

oloop

protected LoopHeaderChord oloop

Loop containing onode.

iloop

protected LoopHeaderChord iloop

Loop containing inode.

cloop

protected LoopHeaderChord cloop

Loop containing both.

bnest

protected int bnest

The common nesting level of the two references.

ddinfo

protected long[] ddinfo

The data dependence information of the two references. The array is indexed by loop nest level (and loops start at level 1). The 0th level represents dependences that start outside of loops. Currently, we don't use the 0th entry.

loopInfo

protected LoopHeaderChord[] loopInfo

The loop information for the current references. We access the array by nest level (so the 0th entry is unused because the outermost nest level is 1).

scribble

protected Scribble scribble

The CFG from which the data dependence isfound.

Constructor Detail

DataDependence

public DataDependence(Scribble scribble)

Create an object for dependence testing.

Method Detail

initialize

public void initialize(SubscriptExpr onode,
                       SubscriptExpr inode,
                       LoopHeaderChord oloop,
                       LoopHeaderChord iloop,
                       int precedes)

Parameters:

onode - a node access

inode - a node access

oloop - is the loop containing onode

iloop - is the loop containing inode

precedes - specifies the execution order. It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".

getDDInfo

public long[] getDDInfo()

Return the data dependence information for these two references.

getDependenceInfo

public abstract Vector<long[]> getDependenceInfo(boolean forward)

Compute data dependences in one direction.

Parameters:

forward - is true if we want forward dependence information.

Returns:

the dependence information (in one direction).

ddTest

public abstract int ddTest(SubscriptExpr onode,
                           SubscriptExpr inode,
                           LoopHeaderChord oloop,
                           LoopHeaderChord iloop,
                           int precedes)

Determine if there is a dependence between two references. This method determines depedences between onode and inode. The methods getForwardDependences and getBackwardDependences filter the dependence information to account for lexical ordering and direction.

If cLCDependent is returned, then getDDInfo will return valid dependence information.

Parameters:

onode - a node access

inode - a node access

oloop - is the loop containing onode

iloop - is the loop containing inode

precedes - specifies the execution order. It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".

Returns:

the data dependence test result.

See Also:

cIndependent, cUnkDependent, cLCDependent, cEqDependent, cFailed

spatialTest

public abstract void spatialTest(SubscriptExpr onode,
                                 SubscriptExpr inode,
                                 LoopHeaderChord oloop,
                                 LoopHeaderChord iloop,
                                 int precedes)
                          throws java.lang.Exception

Parameters:

onode - a node access

inode - a node access

oloop - is the loop containing onode

iloop - is the loop containing inode

precedes - specifies the execution order. It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".

Throws:

java.lang.Exception

getForwardDependences

public long[] getForwardDependences()

Return forward dependence information. That is, the information from onode to inode Recall that the dependence tester computes dependences in both directions. This routine just checks if there is a forward dependence. There is a forward dependence if there is a loop-independent dependence and onode occurs before inode in lexical execution order or if it is a loop-carried dependence. We also strip any nonsensical '<' directions. That is a '>' direction that occurs at the same nesting level as the first '<' direction.

Returns:

the data dependence information for foward dependences.

getBackwardDependences

public long[] getBackwardDependences()

Return backwards dependence information. That is, the information from inode to onode. Recall that the dependence tester computes dependences in both directions. This routine just checks if there is a backward dependence. There is a backward dependence if there is a loop-independent dependence and inode occurs before onode in lexical execution order or if it is a loop carried dependence. We also strip any nonsensical '<' directions.

Returns:

the data dependence info for backward dependences.