cetus.analysis

Class DDGraph

java.lang.Object

cetus.analysis.DDGraph

public class DDGraph
extends java.lang.Object

Data-dependence Graph to store the result of dependence testing

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DDGraph.Arc

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	not_summarize
static boolean	summarize

Constructor Summary

Constructors

Constructor and Description
DDGraph()
DDGraph(java.util.ArrayList<DDGraph.Arc> dependence_arcs)

Method Summary

Methods

Modifier and Type	Method and Description
void	addAllArcs(java.util.ArrayList<DDGraph.Arc> arcs)
void	addArc(DDGraph.Arc arc_to_add)
boolean	checkAntiDependence(Expression e1, Expression e2) Check if there is anti dependence from e1 to e2
boolean	checkEqualDependences(Loop loop) Check if the dependence direction for the input loop is equal in all dependences in the graph
boolean	checkFlowDependence(Expression e1, Expression e2) Check if there is flow dependence from e1 to e2
boolean	checkLoopCarriedDependence(Loop l) Check if the dependence direction for the input loop is loop-carried for any of the dependences in the graph
boolean	checkLoopCarriedDependenceForGraph() Returns true if there exists a loop carried dependence for ANY loop in the nest represented by this dependence graph
boolean	checkOutputDependence(Expression e1, Expression e2) Check if there is an output dependence from e1 to e2
void	deleteArc(DDGraph.Arc arc)
void	filterUnwantedArcs() Removes arcs with directions: (.) --> containing '.' = invalid merged direction
java.util.ArrayList<DDGraph.Arc>	getAllArcs()
java.util.ArrayList<DDGraph.Arc>	getDependenceArcsFromTo(ArrayAccess expr1, ArrayAccess expr2) Obtain all possible dependence information from expr1 to expr2 in a given loop
java.util.ArrayList<DDGraph.Arc>	getDependences(Expression expr1, Expression expr2) Obtain all possible dependence information between a pair of array accesses in a given loop
java.util.ArrayList<DDGraph.Arc>	getDependences(Statement stmt1, Statement stmt2) Obtain all possible dependence information between a pair of statements in a given loop
java.util.ArrayList<DependenceVector>	getDirectionMatrix(java.util.LinkedList<Loop> nest) Obtain a matrix representation of direction vectors for the dependences contained within this dependence graph
java.util.ArrayList<DDGraph.Arc>	getLoopCarriedDependencesForGraph() Returns a list of all dependences (arcs) that are loop carried with respect to ANY of the loops in the nest represented by this dependence graph
DDGraph	getSubGraph(Loop loop) From the current dependence graph, extract a subgraph containing dependences only for the specified loop and its inner nest
void	removeDuplicateArcs() Filter out duplicate and unwanted arcs from the graph
void	summarizeGraph() Summarize the direction vectors between nodes of this graph
java.lang.String	toString() Print function to print entire dependence graph information

Methods inherited from class java.lang.Object

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

Field Detail

summarize

public static final boolean summarize

See Also:

Constant Field Values

not_summarize

public static final boolean not_summarize

See Also:

Constant Field Values

Constructor Detail

DDGraph

public DDGraph()

DDGraph

public DDGraph(java.util.ArrayList<DDGraph.Arc> dependence_arcs)

Method Detail

addArc

public void addArc(DDGraph.Arc arc_to_add)

deleteArc

public void deleteArc(DDGraph.Arc arc)

getAllArcs

public java.util.ArrayList<DDGraph.Arc> getAllArcs()

addAllArcs

public void addAllArcs(java.util.ArrayList<DDGraph.Arc> arcs)

filterUnwantedArcs

public void filterUnwantedArcs()

Removes arcs with directions: (.) --> containing '.' = invalid merged direction

removeDuplicateArcs

public void removeDuplicateArcs()

Filter out duplicate and unwanted arcs from the graph

summarizeGraph

public void summarizeGraph()

Summarize the direction vectors between nodes of this graph

checkLoopCarriedDependenceForGraph

public boolean checkLoopCarriedDependenceForGraph()

Returns true if there exists a loop carried dependence for ANY loop in the nest represented by this dependence graph

Returns:

true if it does, false otherwise

getLoopCarriedDependencesForGraph

public java.util.ArrayList<DDGraph.Arc> getLoopCarriedDependencesForGraph()

Returns a list of all dependences (arcs) that are loop carried with respect to ANY of the loops in the nest represented by this dependence graph

Returns:

the list of dependence arcs.

checkEqualDependences

public boolean checkEqualDependences(Loop loop)

Check if the dependence direction for the input loop is equal in all dependences in the graph

Parameters:

loop - the loop for which equal dependence direction must be checked

Returns:

true if it is, false otherwise

checkLoopCarriedDependence

public boolean checkLoopCarriedDependence(Loop l)

Check if the dependence direction for the input loop is loop-carried for any of the dependences in the graph

Parameters:

l - the loop for which loop-carried dependence existence must be checked

Returns:

true if it is, false otherwise

getDependenceArcsFromTo

public java.util.ArrayList<DDGraph.Arc> getDependenceArcsFromTo(ArrayAccess expr1,
                                                       ArrayAccess expr2)

Obtain all possible dependence information from expr1 to expr2 in a given loop

Parameters:

expr1 - - ArrayAccess

expr2 - - ArrayAccess

Returns:

arcSet - List of all existing dependence arcs from expr1 to expr2

getDependences

public java.util.ArrayList<DDGraph.Arc> getDependences(Expression expr1,
                                              Expression expr2)

Obtain all possible dependence information between a pair of array accesses in a given loop

Parameters:

expr1 - - ArrayAccess

expr2 - - ArrayAccess

Returns:

arcSet - List of all existing dependence arcs between the two accesses

checkFlowDependence

public boolean checkFlowDependence(Expression e1,
                          Expression e2)

Check if there is flow dependence from e1 to e2

Parameters:

e1 - source of dependence

e2 - sink of dependence

Returns:

true if it is, false otherwise

checkAntiDependence

public boolean checkAntiDependence(Expression e1,
                          Expression e2)

Check if there is anti dependence from e1 to e2

Parameters:

e1 - source of dependence

e2 - sink of dependence

Returns:

true if it is, false otherwise

checkOutputDependence

public boolean checkOutputDependence(Expression e1,
                            Expression e2)

Check if there is an output dependence from e1 to e2

Parameters:

e1 - source of dependence

e2 - sink of dependence

Returns:

true if it is, false otherwise

getDependences

public java.util.ArrayList<DDGraph.Arc> getDependences(Statement stmt1,
                                              Statement stmt2)

Obtain all possible dependence information between a pair of statements in a given loop

Parameters:

stmt1 - - Statement

stmt2 - - Statement

Returns:

arcSet - List of all existing dependence arcs between the two statements

getSubGraph

public DDGraph getSubGraph(Loop loop)

From the current dependence graph, extract a subgraph containing dependences only for the specified loop and its inner nest

Parameters:

loop - the loop and its inner nest for which dependences are to be extracted into a separate graph

Returns:

the sub-DDGraph that belongs to loop

toString

public java.lang.String toString()

Print function to print entire dependence graph information

Overrides:

toString in class java.lang.Object

getDirectionMatrix

public java.util.ArrayList<DependenceVector> getDirectionMatrix(java.util.LinkedList<Loop> nest)

Obtain a matrix representation of direction vectors for the dependences contained within this dependence graph

Parameters:

nest - the loop nest for which the matrix needs to be obtained

Returns:

the list that encodes the matrix in terms of list of DependenceVector