scale.score.dependence
Class DDEdge

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

Direct Known Subclasses:

DDNormalEdge, DDTransEdge

public abstract class DDEdge
extends java.lang.Object

This class is the base class for data dependence edges.

$Id: DDEdge.java,v 1.35 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 edge in the data dependence graph goes from a source node to a sink node where a node is some SubscriptExpr instance expression in the CFG. The edge type may be for flow dependence, antidependence, input dependence, output dependence, or spatial dependence.

Note that while edges connect SubscriptExpr instances, the actual edges are between the uses of the address specified by the SubscriptExpr instance. It is necessary to have the use at each end in order to determine the type of data dependence edge.

There are two types of edges recorded. A normal edge connects between two nodes. A transitive edge is used to reduce the amount of memory used by the compiler to represent the data dependence edges. A transitive edge can represent many actual edges. For example, if there is an edge from a to b and an edge from b to c, then there is also an edge from a to c if all the edges have zero distance.

See Also:

DDTransEdge, DDNormalEdge, DataDependence, DDGraph, DDInfo

Field Summary

static int	cAnti An anti dependence.
static int	cFlow A flow, or true, dependence.
static int	cInput An input dependence.
static int	cNone No dependence.
static DColor[]	colors The colors used to graph the different edge types.
static int	cOutput An output dependence.
static java.lang.String[]	dependenceName Map from dependence to string.
static DEdge[]	lineType The line types used to graph the different edge types.

Constructor Summary

DDEdge(java.lang.String aname, boolean spatial)
Create an edge for the data dependence graph.

Method Summary

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

Methods inherited from class java.lang.Object

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

Field Detail

colors

public static final DColor[] colors

The colors used to graph the different edge types.

lineType

public static final DEdge[] lineType

The line types used to graph the different edge types.

cFlow

public static final int cFlow

A flow, or true, dependence. A value defined in S1 is used in S2.

See Also:

Constant Field Values

cAnti

public static final int cAnti

An anti dependence. A value used in S1 is defined in S2.

See Also:

Constant Field Values

cOutput

public static final int cOutput

An output dependence. A value defined in S1 is defined in S2

See Also:

Constant Field Values

cInput

public static final int cInput

An input dependence. A value used both in S1 and in S2

See Also:

Constant Field Values

cNone

public static final int cNone

No dependence. There is a dependence from S2 to S1 but not S1 to S2.

See Also:

Constant Field Values

dependenceName

public static final java.lang.String[] dependenceName

Map from dependence to string.

Constructor Detail

DDEdge

public DDEdge(java.lang.String aname,
              boolean spatial)

Create an edge for the data dependence graph.

Parameters:

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, DDNormalEdge, DDTransEdge

Method Detail

getNodeID

public final int getNodeID()

Return a unique integer specifying this edge instance.

iterator

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

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

contains

public abstract boolean contains(SubscriptExpr exp)

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

representsAllInput

public abstract boolean representsAllInput()

Return true if every edge represented is an input edge.

getEnds

public abstract void getEnds(Vector<Note> v)

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

numberEdges

public abstract int numberEdges()

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

getArrayName

public final java.lang.String getArrayName()

Return the name of array (or scalar) involved in the dependence.

getDDInfo

public abstract long[] getDDInfo()

Return the computed data dependence information.

isLoopIndependentDependency

public abstract boolean isLoopIndependentDependency()

Return true if the edge is loop-independent dependency.

getDistance

public abstract int getDistance(int level)

Return the distance for the specified level.

isDistanceKnown

public abstract boolean isDistanceKnown(int level)

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

isAnyDistanceKnown

public abstract boolean isAnyDistanceKnown()

Return true if the distance is known at any level.

isAnyDistanceNotKnown

public abstract boolean isAnyDistanceNotKnown()

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

isAnyDistanceNonZero

public abstract boolean isAnyDistanceNonZero()

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

getEdgeType

public abstract int getEdgeType(Note source,
                                Note sink)

Return the data dependence type - flow, anti, input, or output. This logic assumes that the source precedes the sink. The source and sink must the uses of the addresses represented by the SubscriptExpr instances that are the ends of the data dependence edge.

See Also:

DDGraph, DataDependence

isSpatial

public final boolean isSpatial()

Return true if this is a spatial edge.

isTransitive

public abstract boolean isTransitive()

Return true if this is a transitive edge set.

printDDInfo

public abstract void printDDInfo(Note source,
                                 Note sink)

Print to stdout the information about the data dependence.

format

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

Return a string representation of a data dependence edge.

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 abstract void graphDependence(DisplayGraph da,
                                     boolean addChord,
                                     HashSet<Note> nodes,
                                     DDGraph graph)

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

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 abstract boolean forLoop(LoopHeaderChord loop)

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