Package EDU.purdue.cs.bloat.cfg

Class 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:
    MethodEditor, Block

    • Field Detail

      • PEEL_LOOPS_LEVEL

        public static int PEEL_LOOPS_LEVEL

      • DEBUG

        public static boolean DEBUG

      • DB_GRAPHS

        public static boolean DB_GRAPHS

      • PRINT_GRAPH

        public static boolean PRINT_GRAPH

    • Constructor Detail

      • FlowGraph

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

    • Method Detail

      • 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 java.util.Collection subroutines()
        Returns all of the Subroutines in the method modeled by this FlowGraph.

      • print

        public void print​(java.io.PrintStream out)

      • print

        public void print​(java.io.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​(java.io.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​(java.io.PrintWriter out)

      • printGraph

        public void printGraph​(java.io.PrintWriter out,
                       java.lang.String name)

      • visitChildren

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

      • method

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

      • trace

        public java.util.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 java.util.Collection iteratedDomFrontier​(java.util.Collection blocks)
        Returns the iterated dominance frontiers for several basic blocks.
        See Also:
        Block.domFrontier

      • iteratedPdomFrontier

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

      • roots

        public java.util.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 java.util.Collection reverseRoots()
        Overrides:
        reverseRoots in class Graph
        Returns:
        A Collection containing only the sink block.
        See Also:
        roots()

      • removeNode

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

      • handlersMap

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

      • handlers

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

      • catchBlocks

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

      • domChildren

        public java.util.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(EDU.purdue.cs.bloat.cfg.Block)

      • 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 java.util.List preOrder()
        Returns the blocks in the flow graph sorted in pre-order.
        Overrides:
        preOrder in class Graph

      • postOrder

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

      • pdomChildren

        public java.util.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 java.util.Collection domFrontier​(Block block)
        Returns the dominance frontier of a given block.
        See Also:
        Block.domFrontier

      • pdomFrontier

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

      • toString

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