scale.score.dependence
Class DDGraph

java.lang.Object
  scale.score.dependence.DDGraph

public class DDGraph
extends java.lang.Object

This class represents the data dependence graph.

$Id: DDGraph.java,v 1.75 2007-10-04 19:58:24 burrill Exp $

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

The entire dependence information for one function is contained in a single DDGraph instance. This class contains a table of dependence edges that maps from array (by name) to the edges. The edges have a source and a sink which are SubscriptExpr instances. This table is discarded when the Scribble.reduceMemory() method is called after all optimizations or when the Scribble.recomputeDataDependence() method is called because the CFG was changed. Note - the data dependence information is only computed on demand. Currently, only ScalarReplacement demands it.

This graph shows the data dependence graph for a simple program:

     int A[10];
     for (I = 0; I < 10; I++) {
       X = &A[I];
       Y = &A[I];
       S = S + *X * *X + *Y * *Y
     }
 

In this example there is one DDEdge instance which connects the two SubscriptExpr instances. The SubscriptExpr instances are the ends of the edge.

Even though there is only one DDEdge instance in the above example, there are implied edges between all of the uses of the address specified by one SubscriptExpr instance. For these implied edges the distance is always known and is zero because they all refer to the same array element. If there are n uses (e.q., LoadDeclValueExpr instances) of one SubscriptExpr instance then there are n × (n - 1) / 2 implied data dependence edges.

When it is proved that there is a data dependence edge between two SubscriptExpr instances as shown above in the graph, then it is asserted that there is an edge between each of the uses of the two SubscriptExpr instances. These edges all have the same distance and direction. If there are n uses of one SubscriptExpr instance and m uses of the other, then there are n × m asserted data dependence edges. But, they are all represented by a single DDEdge instance. (The graph shows only one of the four asserted edges.)

Whether an edge is implied or asserted, the Scale system creates a DDEdge instance to represent it. (The graph only shows the DDEdge instance for the asserted edges.)

The DDEdge instances do not provide all the information about the edges. Whether an edge is a flow, anti, input, or output edge can only be determined by looking at the actual uses. The DDEdge classes provide several methods for obtaining all of the implied and asserted edges and the information about them. The getEnds and iterator methods provide access to the SubscriptExpr instances. The getEdgeType method provides the edge type (e.g., flow, anti, input, or output). From a SubscriptExpr instance you can obtain the uses of the array element address by using the addUses method.

See Also:

DDEdge, DDNormalEdge, DDTransEdge, DataDependence

Field Summary

boolean	allComputed True if all dependencies were computed.
static boolean	classTrace True if trace information should be displayed.
static boolean	useBanerjee Enable use of the Banerjee dependendence test
static boolean	useBasic Enable use of the simple dependendence test
static boolean	useOmega Enable use of the Omega dependendence test
static boolean	useTransClosure Enable use of transitive closure

Constructor Summary

DDGraph(Scribble scribble, boolean createSpatialDependencies)

Method Summary

static int	banerjeeFails() Return the count of all the ddTests that failed using the Banerjee test.
static int	banerjeeTests() Return the count of all the ddTests performed using the Banerjee test.
void	computeArrayDependences(LoopHeaderChord loop) Perform array dependence testing for subscript expressions in the specified loop nest.
void	dumpEdgeList() Dump out all data dependence edges.
static int	edgeExisted() Return the count of all the edges that already existed.
java.util.Enumeration<DDEdge>	getEdges() Return an enumeration of all the edges.
Vector<DDEdge>	getEdges(LoopHeaderChord loop) Return a vector of all edges for the specified Loop.
DDEdge[]	getEdges(SubscriptExpr src) Return an array of all edges that contain the specified expression.
Table<Declaration,SubscriptExpr>	getSubscriptsUsed() Return the table of subscripts used to compute the dependencies.
void	graphDependence(DisplayGraph da, boolean addChord) Create a graphic display of the dependence graph.
boolean	hasLoopCarriedTemporalReuse(SubscriptExpr srcR, int depth, int checkDepth) Return true if this expression has loop carried temporal reuse across iterations of loop.
boolean	hasSpatialReuse(SubscriptExpr srcR, int depth, boolean group, int checkDepth) Return true if this expression has spatial reuse across iterations of the loop.
boolean	hasTemporalReuse(SubscriptExpr srcR, int depth, int checkDepth) Check if this expression has temporal reuse across iterations of loop.
static int	omegaFails() Return the count of all the ddTests that failed using the Omega Library.
static int	omegaTests() Return the count of all the ddTests performed using the Omega Library.
void	removeEdges(SubscriptExpr exp) Remove all edges from or to this expression.
static int	simpleTest() Return the count of all the ddTests performed using the simple test.
java.lang.String	toString()
static int	totalTests() Return the count of all the ddTests performed using the Omega Library.

Methods inherited from class java.lang.Object

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

Field Detail

useBasic

public static boolean useBasic

Enable use of the simple dependendence test

useBanerjee

public static boolean useBanerjee

Enable use of the Banerjee dependendence test

useOmega

public static boolean useOmega

Enable use of the Omega dependendence test

useTransClosure

public static boolean useTransClosure

Enable use of transitive closure

classTrace

public static boolean classTrace

True if trace information should be displayed.

allComputed

public boolean allComputed

True if all dependencies were computed. It is set false if any dependency relation was not able to be determined.

See Also:

computeArrayDependences(scale.score.chords.LoopHeaderChord)

Constructor Detail

DDGraph

public DDGraph(Scribble scribble,
               boolean createSpatialDependencies)

Parameters:

scribble - specifies the CFG containing the dependencies

createSpatialDependencies - is true if spatial edges should be created

Method Detail

totalTests

public static int totalTests()

Return the count of all the ddTests performed using the Omega Library.

omegaTests

public static int omegaTests()

Return the count of all the ddTests performed using the Omega Library.

banerjeeTests

public static int banerjeeTests()

Return the count of all the ddTests performed using the Banerjee test.

simpleTest

public static int simpleTest()

Return the count of all the ddTests performed using the simple test.

omegaFails

public static int omegaFails()

Return the count of all the ddTests that failed using the Omega Library.

banerjeeFails

public static int banerjeeFails()

Return the count of all the ddTests that failed using the Banerjee test.

edgeExisted

public static int edgeExisted()

Return the count of all the edges that already existed.

graphDependence

public void graphDependence(DisplayGraph da,
                            boolean addChord)

Create a graphic display of the dependence graph. You must call computeArrayDependences first.

Parameters:

da - is the graph display

addChord - is true if a link between the expression and its Chord should be shown

dumpEdgeList

public void dumpEdgeList()

Dump out all data dependence edges.

getEdges

public java.util.Enumeration<DDEdge> getEdges()

Return an enumeration of all the edges.

getEdges

public DDEdge[] getEdges(SubscriptExpr src)

Return an array of all edges that contain the specified expression.

getEdges

public Vector<DDEdge> getEdges(LoopHeaderChord loop)

Return a vector of all edges for the specified Loop. You must call computeArrayDependences first.

computeArrayDependences

public void computeArrayDependences(LoopHeaderChord loop)

Perform array dependence testing for subscript expressions in the specified loop nest.

Parameters:

loop - is the loop for which dependencies are to be checked

getSubscriptsUsed

public Table<Declaration,SubscriptExpr> getSubscriptsUsed()

Return the table of subscripts used to compute the dependencies.

removeEdges

public void removeEdges(SubscriptExpr exp)

Remove all edges from or to this expression.

hasTemporalReuse

public boolean hasTemporalReuse(SubscriptExpr srcR,
                                int depth,
                                int checkDepth)

Check if this expression has temporal reuse across iterations of loop.

Returns:

true if all distances are equal.

hasLoopCarriedTemporalReuse

public boolean hasLoopCarriedTemporalReuse(SubscriptExpr srcR,
                                           int depth,
                                           int checkDepth)

Return true if this expression has loop carried temporal reuse across iterations of loop.

hasSpatialReuse

public boolean hasSpatialReuse(SubscriptExpr srcR,
                               int depth,
                               boolean group,
                               int checkDepth)

Return true if this expression has spatial reuse across iterations of the loop.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object