scale.score.dependence
Class DDTransEdge

java.lang.Object
  scale.score.dependence.DDEdge
      scale.score.dependence.DDTransEdge

public final class DDTransEdge
extends DDEdge

This class represents the set of edges, in the data dependence graph, that have a distance of 0 and the same direction for some array in some loop. It forms a transitive closure.

$Id: DDTransEdge.java,v 1.22 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.

An instance of this class represents a set of data dependence edges for an array where the edge distance is zero. For example if there is an edge from A to B of zero distance, and there is an edge from A to C of zero distance, then there is also an edge from B to C of zero distance.

See Also:

DDEdge, DDNormalEdge, DataDependence, DDGraph

Field Summary

Fields inherited from class scale.score.dependence.DDEdge

cAnti, cFlow, cInput, cNone, colors, cOutput, dependenceName, lineType

Constructor Summary

DDTransEdge(SubscriptExpr end1, SubscriptExpr end2, java.lang.String aname, boolean spatial)
Create an edge for the data dependence graph.

Method Summary

boolean	addEdge(SubscriptExpr exp, boolean spatial) Specify another data dependence edge end point.
boolean	chkEnds(Note source, Note sink)
boolean	contains(SubscriptExpr exp) Return true if the expression is an end of an edge represented by this instance.
static int	created() Return the number of instances of this class that were created.
boolean	forLoop(LoopHeaderChord loop) Return true if this edge has a source or sink in the specified loop.
java.lang.String	format(Note s1, Note s2, java.lang.String aname, int ddtype) Return a string representation of a data dependence edge.
long[]	getDDInfo() Return the computed data dependence information.
int	getDistance(int level) Return the distance for the specified level.
int	getEdgeType(Note source, Note sink) Return the data dependence type - flow, anti, input, or output.
void	getEnds(Vector<Note> v) Add the SubscriptExpr instances, that are the edge ends, to the Vector.
void	graphDependence(DisplayGraph da, boolean addChord, HashSet<Note> nodes, DDGraph graph) Create a graphic display of the edges represented by this instancce.
boolean	isAnyDistanceKnown() Return true if the distance is known at any level.
boolean	isAnyDistanceNonZero() Return true if any distance is unknown or not zero at any level.
boolean	isAnyDistanceNotKnown() Return true if the distance is not known at any level.
boolean	isDistanceKnown(int level) Return true if the distance is known at the specified level.
boolean	isLoopIndependentDependency() Return true if the edge is loop-independent dependency.
boolean	isTransitive() Return true if this is a transitive edge set.
java.util.Iterator<SubscriptExpr>	iterator() Return an iterator over the SubscriptExpr instances that are the edge ends.
int	numberEdges() Return a metric for the number of data dependence edges represented.
static int	numberEnds() Return the number of data dependence edges represented.
void	printDDInfo(Note source, Note sink) Print to stdout the information about the data dependence.
int	removeEdge(SubscriptExpr exp) Remove to / from this expression.
boolean	representsAllInput() Return true if every edge represented is an input edge.
java.lang.String	toString()

Methods inherited from class scale.score.dependence.DDEdge

getArrayName, getNodeID, isSpatial

Methods inherited from class java.lang.Object

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

Constructor Detail

DDTransEdge

public DDTransEdge(SubscriptExpr end1,
                   SubscriptExpr end2,
                   java.lang.String aname,
                   boolean spatial)

Create an edge for the data dependence graph.

Parameters:

end1 - is the one end of the edge

end2 - is the other end of the edge

aname - is the name of array (or scalar) involved in the dependence

spatial - is true if the edge records a spatial dependence

See Also:

DataDependence, DDGraph

Method Detail

numberEnds

public static int numberEnds()

Return the number of data dependence edges represented.

created

public static int created()

Return the number of instances of this class that were created.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

iterator

public java.util.Iterator<SubscriptExpr> iterator()

Return an iterator over the SubscriptExpr instances that are the edge ends.

Specified by:

iterator in class DDEdge

contains

public boolean contains(SubscriptExpr exp)

Return true if the expression is an end of an edge represented by this instance.

Specified by:

contains in class DDEdge

representsAllInput

public boolean representsAllInput()

Return true if every edge represented is an input edge.

Specified by:

representsAllInput in class DDEdge

addEdge

public boolean addEdge(SubscriptExpr exp,
                       boolean spatial)

Specify another data dependence edge end point. If the loop containing the end point is a sub-loop or parent loop of the edge's characteristic loop and the data dependence information matches, the end point is added to this transitive edge. Only edges with zero distance should be added.

Parameters:

spatial - is true if the edge records a spatial dependence

Returns:

true if the end point was added

removeEdge

public int removeEdge(SubscriptExpr exp)

Remove to / from this expression. Return the number of edge ends.

getEnds

public void getEnds(Vector<Note> v)

Add the SubscriptExpr instances, that are the edge ends, to the Vector.

Specified by:

getEnds in class DDEdge

numberEdges

public int numberEdges()

Return a metric for the number of data dependence edges represented. This is the number of edge end points - 1.

Specified by:

numberEdges in class DDEdge

getDDInfo

public long[] getDDInfo()

Return the computed data dependence information.

Specified by:

getDDInfo in class DDEdge

isLoopIndependentDependency

public boolean isLoopIndependentDependency()

Return true if the edge is loop-independent dependency.

Specified by:

isLoopIndependentDependency in class DDEdge

getDistance

public int getDistance(int level)

Return the distance for the specified level.

Specified by:

getDistance in class DDEdge

isDistanceKnown

public boolean isDistanceKnown(int level)

Return true if the distance is known at the specified level.

Specified by:

isDistanceKnown in class DDEdge

isAnyDistanceKnown

public boolean isAnyDistanceKnown()

Return true if the distance is known at any level.

Specified by:

isAnyDistanceKnown in class DDEdge

isAnyDistanceNotKnown

public boolean isAnyDistanceNotKnown()

Return true if the distance is not known at any level.

Specified by:

isAnyDistanceNotKnown in class DDEdge

isAnyDistanceNonZero

public boolean isAnyDistanceNonZero()

Return true if any distance is unknown or not zero at any level.

Specified by:

isAnyDistanceNonZero in class DDEdge

isTransitive

public boolean isTransitive()

Return true if this is a transitive edge set.

Specified by:

isTransitive in class DDEdge

getEdgeType

public int getEdgeType(Note source,
                       Note sink)

Return the data dependence type - flow, anti, input, or output. This logic depends on the CFG nodes being labeled. The source and sink must the uses of the address represented by the SubscriptExpr instances that are the ends of the data dependence edge.

Specified by:

getEdgeType in class DDEdge

See Also:

DDGraph, DataDependence

chkEnds

public boolean chkEnds(Note source,
                       Note sink)

printDDInfo

public void printDDInfo(Note source,
                        Note sink)

Print to stdout the information about the data dependence.

Specified by:

printDDInfo in class DDEdge

format

public java.lang.String format(Note s1,
                               Note s2,
                               java.lang.String aname,
                               int ddtype)

Description copied from class: DDEdge

Return a string representation of a data dependence edge.

Specified by:

format in class DDEdge

Parameters:

s1 - is one end of the edge

s2 - is another end of the edge

aname - is the array name

ddtype - is the edge type

graphDependence

public void graphDependence(DisplayGraph da,
                            boolean addChord,
                            HashSet<Note> nodes,
                            DDGraph graph)

Create a graphic display of the edges represented by this instancce.

Specified by:

graphDependence in class DDEdge

Parameters:

da - is the graph display

addChord - is true if the ends of each edge should be added to the nodes set

nodes - is the set of

forLoop

public boolean forLoop(LoopHeaderChord loop)

Return true if this edge has a source or sink in the specified loop.

Specified by:

forLoop in class DDEdge