Package EDU.purdue.cs.bloat.ssa

Class 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 Description
      static boolean DEBUG  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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.