Class SSAGraph

java.lang.Object
EDU.purdue.cs.bloat.ssa.SSAGraph
public class SSAGraph extends 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:

  • Field Details

    • DEBUG

      public static boolean DEBUG

  • Constructor Details

    • 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 Details

    • cfg

      public FlowGraph cfg()
      Returns the FlowGraph that this SSAGraph is built around.

    • equivalent

      public 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 List children(Node node)
      Returns the children (that is, the operands) of a given Node in the SSA Graph.

    • equivalences

      public 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(PrintWriter pw)
      Prints a textual representation of the strongly connected components of the SSAGraph to a PrintWriter.