Class FlowGraph

java.lang.Object
EDU.purdue.cs.bloat.util.Graph
EDU.purdue.cs.bloat.cfg.FlowGraph
public class FlowGraph extends Graph
FlowGraph constructs and represents a Control Flow Graph (CFG) used for analyzing a method. It consists of the basic blocks of a method.

See Also:

  • Field Details

    • PEEL_NO_LOOPS

      public static final int PEEL_NO_LOOPS
      See Also:

    • PEEL_ALL_LOOPS

      public static final int PEEL_ALL_LOOPS
      See Also:

    • PEEL_LOOPS_LEVEL

      public static int PEEL_LOOPS_LEVEL

    • DEBUG

      public static boolean DEBUG

    • DB_GRAPHS

      public static boolean DB_GRAPHS

  • Constructor Details

    • FlowGraph

      public FlowGraph(MethodEditor method)
      Constructor.
      Parameters:
      method - The method to create the CFG for.

  • Method Details

    • maxLoopDepth

      public int maxLoopDepth()
      Returns the maximum loop depth (also the maximum loop height) in the control flow graph.

    • initialize

      public void initialize()
      Sets up the control flow graph. Computes the dominators and the dominance frontier, cleans up the tree, works with the loops, inserts stores to aid copy and constant propagation as well as code generation.

    • loopTree

      public Graph loopTree()
      Returns the loop tree for the method modeled by this flow graph. The loop tree represents the nesting of the loops in a method. The procedure is at the root of the loop tree. Nested loops are represented by a parent and child relationship.

    • removeSub

      public void removeSub(Subroutine sub)
      Removes a subroutine from this method.
      Parameters:
      sub - The subroutine to remove.

    • addEdge

      public void addEdge(GraphNode src, GraphNode dst)
      Adds an edge between two nodes in this graph.
      Overrides:
      addEdge in class Graph
      Parameters:
      src - Node at which the edge originates.
      dst - Node at which the edge terminates.

    • removeEdge

      public void removeEdge(GraphNode v, GraphNode w)
      Removes an edge from the graph and performs the necessary cleanup.
      Overrides:
      removeEdge in class Graph
      Parameters:
      v - Node at which edge to be removed originates.
      w - Node at which edge to be removed terminates.

    • newBlock

      public Block newBlock()
      Returns a new Block with the next available Label.

    • labelSub

      public Subroutine labelSub(Label label)
      Returns the Subroutine whose entry block is labeled by a given Label.

    • subroutines

      public Collection subroutines()
      Returns all of the Subroutines in the method modeled by this FlowGraph.

    • print

      public void print(PrintStream out)

    • print

      public void print(PrintWriter out)
      Prints the graph.
      Parameters:
      out - The writer to which to print.

    • printGraph

      public void printGraph()

    • print

      public void print()

    • printGraph

      public void printGraph(PrintStream out)
      Creates a graphical description of the CFG in the dot language. The name of the generated file is the name of the method modeled by this CFG followed by a number and the ".dot" postfix. For more information about dot and tools that use it see:

      http://www.research.att.com/sw/tools/graphviz/

    • printGraph

      public void printGraph(PrintWriter out)

    • printGraph

      public void printGraph(PrintWriter out, String name)

    • visitChildren

      public void visitChildren(TreeVisitor visitor)
      Visit each node (block) in this CFG in pre-order.

    • visit

      public void visit(TreeVisitor visitor)

    • method

      public MethodEditor method()
      Returns the method editor for the method modeled by this graph.

    • trace

      public List trace()
      Returns the basic blocks contained in this CFG in trace order. Trace order implies that basic blocks that end with a conditional jump are followed by their false branch and, where possible, that blocks that end in an unconditional jump are followed by the block that is the target of the unconditional branch.

      The trace does not contain the source and the sink blocks.

      Returns:
      The basic Blocks in this CFG.

    • commit

      public void commit()
      Commit changes back to the method editor.

    • source

      public Block source()
      Returns the "Enter" block of this CFG. That is, the block through which all paths enter.

    • init

      public Block init()
      Returns the initialization block.

    • sink

      public Block sink()
      Returns the sink block. That is, the block through which all paths exit.

    • iteratedDomFrontier

      public Collection iteratedDomFrontier(Collection blocks)
      Returns the iterated dominance frontiers for several basic blocks.
      See Also:
      • Block.domFrontier

    • iteratedPdomFrontier

      public Collection iteratedPdomFrontier(Collection blocks)
      Returns the iterated postdominance frontier for several basic blocks.
      See Also:
      • Block.pdomFrontier

    • roots

      public Collection roots()
      Overrides:
      roots in class Graph
      Returns:
      A Collection containing the root(s) of this FlowGraph. In this case there is only one root, so the Collection only contains the source block.

    • reverseRoots

      public Collection reverseRoots()
      Overrides:
      reverseRoots in class Graph
      Returns:
      A Collection containing only the sink block.
      See Also:

    • removeNode

      public void removeNode(Object key)
      Removes a node (a Block) from the graph.
      Overrides:
      removeNode in class Graph
      Parameters:
      key - Block to remove

    • handlersMap

      public Map handlersMap()
      Returns A Map mapping the first block in an exception handler to its Handler object.
      See Also:

    • handlers

      public Collection handlers()
      Returns all of the Handler objects in this CFG.

    • catchBlocks

      public List catchBlocks()
      Returns theBlocks in this CFG that begin exception handlers.

    • domChildren

      public Collection domChildren(Block block)
      Returns the blocks that a given block dominates.

    • domParent

      public Block domParent(Block block)
      Returns the Block that dominates a given block.

    • blockType

      public int blockType(Block block)
      Returns the type of a given block. A block's type is one of Block.NON_HEADER, Block.IRREDUCIBLE, or Block.REDUCIBLE.

    • loopDepth

      public int loopDepth(Block block)
      Returns the depth of the loop in which a block is contained. The block must be contained in a loop. The procedure has depth 0. A loop (while, for, etc.) at the procedure level has depth 1. Depth increases as loops are nested.
      Parameters:
      block - A block whose depth we are interested in.
      See Also:

    • loopLevel

      public int loopLevel(Block block)
      Returns the level of the loop containing a given block. The innermost loops have level 0. The level increases as you go outward to higher loop nestings. For any given loop, the level is the maximum possible. 

       procedure()
 {
   // Depth 0, Level 2 (max possible)
   while()
   {
     // Depth 1, Level 1
     while()
     {
       // Depth 2, Level 0
     }
   }
   while()
   {
     // Depth 1, Level 0
   }
 }
      Parameters:
      block - A block whose loop level we want to know. This block must be contained in a loop.

    • loopHeader

      public Block loopHeader(Block block)
      Returns the loop header of the loop containing a given block. The loop header is the block that dominates all of the blocks in the loop.

    • preOrder

      public List preOrder()
      Returns the blocks in the flow graph sorted in pre-order.
      Overrides:
      preOrder in class Graph

    • postOrder

      public List postOrder()
      Returns the blocks in the flow graph sorted in post-order.
      Overrides:
      postOrder in class Graph

    • pdomChildren

      public Collection pdomChildren(Block block)
      Returns the postdominator children of a given block.
      See Also:
      • Block.pdomChildren

    • pdomParent

      public Block pdomParent(Block block)
      Returns the postdominator parent of a given block.
      See Also:
      • Block.pdomParent

    • domFrontier

      public Collection domFrontier(Block block)
      Returns the dominance frontier of a given block.
      See Also:
      • Block.domFrontier

    • pdomFrontier

      public Collection pdomFrontier(Block block)
      Returns the postdominance frontier of a given block.
      See Also:
      • Block.pdomFrontier

    • toString

      public String toString()
      Returns a brief textual description of this FlowGraph, namely the name of the method it represents.
      Overrides:
      toString in class Graph