EDU.purdue.cs.bloat.ssa

Class SSAGraph

java.lang.Object

EDU.purdue.cs.bloat.ssa.SSAGraph

public class SSAGraph
extends java.lang.Object

The SSA graph (also called the value graph) represents the nesting of expression in a control flow graph. Each node in the SSA graph represents an expression. If the expression is a definition, the it is labeled with the variable it defines. Each node has directed edges to the nodes representing its operands.

SSAGraph is a representation of the definitions found in a CFG in the following form: Each node in the graph is an expression that defines a variable (a VarExpr, PhiStmt, or a StackManipStmt). Edges in the graph point to the nodes whose expressions define the operands of the expression in the source node.

This class is used primarily get the strongly connected components of the SSA graph in support of value numbering and induction variable analysis.

Nate warns: Do not modify the CFG while using the SSA graph! The effects of such modification are undefined and will probably lead to nasty things occuring.

See Also:

ValueNumbering

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	DEBUG

Constructor Summary

Constructors

Constructor and Description
SSAGraph(FlowGraph cfg) Constructor.
SSAGraph(FlowGraph cfg, boolean useless) Grumble.

Method Summary

Methods

Modifier and Type	Method and Description
FlowGraph	cfg() Returns the FlowGraph that this SSAGraph is built around.
java.util.List	children(Node node) Returns the children (that is, the operands) of a given Node in the SSA Graph.
java.util.Collection	equivalences() Returns the Sets of Nodes whose values are equivalent.
java.util.Set	equivalent(Node node) Returns a set of nodes whose value is equivalent to a given node.
void	printSCCs(java.io.PrintWriter pw) Prints a textual representation of the strongly connected components of the SSAGraph to a PrintWriter.
void	visitComponent(Node startNode, ComponentVisitor visitor) Visits the strongly connected component that contains a given Node.
void	visitComponents(ComponentVisitor visitor) Calculates the strongly connected components (SCC) of the SSA graph.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

public static boolean DEBUG

Constructor Detail

SSAGraph

public SSAGraph(FlowGraph cfg,
        boolean useless)

Grumble.

SSAGraph

public SSAGraph(FlowGraph cfg)

Constructor. Traverse the control flow graph and determines which Nodes are of an equivalent Type.

Parameters:

cfg - The control flow graph to examine

Method Detail

cfg

public FlowGraph cfg()

Returns the FlowGraph that this SSAGraph is built around.

equivalent

public java.util.Set equivalent(Node node)

Returns a set of nodes whose value is equivalent to a given node. For example, the LHS and RHS of an assignment are equivalent. As are all local variables with the same definition.

children

public java.util.List children(Node node)

Returns the children (that is, the operands) of a given Node in the SSA Graph.

equivalences

public java.util.Collection equivalences()

Returns the Sets of Nodes whose values are equivalent.

visitComponents

public void visitComponents(ComponentVisitor visitor)

Calculates the strongly connected components (SCC) of the SSA graph. SSCs are represented by a List of Nodes. The SCCs are then visited by the ComponentVistor.

visitComponent

public void visitComponent(Node startNode,
                  ComponentVisitor visitor)

Visits the strongly connected component that contains a given Node.

printSCCs

public void printSCCs(java.io.PrintWriter pw)

Prints a textual representation of the strongly connected components of the SSAGraph to a PrintWriter.