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

Field Summary

Fields
Modifier and Type	Field and Description
`static boolean`	`DB_GRAPHS`
`static boolean`	`DEBUG`
`static int`	`PEEL_ALL_LOOPS`
`static int`	`PEEL_LOOPS_LEVEL`
`static int`	`PEEL_NO_LOOPS`
`static boolean`	`PRINT_GRAPH`

Fields inherited from class EDU.purdue.cs.bloat.util.Graph
edgeModCount, nodeModCount, removingEdge, removingNode, revRootEdgeModCount, rootEdgeModCount

Constructor Summary

Constructors
Constructor and Description

FlowGraph(MethodEditor method)
Constructor.

Constructors
Constructor and Description
`FlowGraph(MethodEditor method)` Constructor.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`addEdge(GraphNode src, GraphNode dst)` Adds an edge between two nodes in this graph.
`int`	`blockType(Block block)` Returns the type of a given block.
`java.util.List`	`catchBlocks()` Returns the`Block`s in this CFG that begin exception handlers.
`void`	`commit()` Commit changes back to the method editor.
`java.util.Collection`	`domChildren(Block block)` Returns the blocks that a given block dominates.
`java.util.Collection`	`domFrontier(Block block)` Returns the dominance frontier of a given block.
`Block`	`domParent(Block block)` Returns the `Block` that dominates a given block.
`java.util.Collection`	`handlers()` Returns all of the `Handler` objects in this CFG.
`java.util.Map`	`handlersMap()` Returns A Map mapping the first block in an exception handler to its `Handler` object.
`Block`	`init()` Returns the initialization block.
`void`	`initialize()` Sets up the control flow graph.
`java.util.Collection`	`iteratedDomFrontier(java.util.Collection blocks)` Returns the iterated dominance frontiers for several basic blocks.
`java.util.Collection`	`iteratedPdomFrontier(java.util.Collection blocks)` Returns the iterated postdominance frontier for several basic blocks.
`Subroutine`	`labelSub(Label label)` Returns the `Subroutine` whose entry block is labeled by a given `Label`.
`int`	`loopDepth(Block block)` Returns the depth of the loop in which a block is contained.
`Block`	`loopHeader(Block block)` Returns the loop header of the loop containing a given block.
`int`	`loopLevel(Block block)` Returns the level of the loop containing a given block.
`Graph`	`loopTree()` Returns the loop tree for the method modeled by this flow graph.
`int`	`maxLoopDepth()` Returns the maximum loop depth (also the maximum loop height) in the control flow graph.
`MethodEditor`	`method()` Returns the method editor for the method modeled by this graph.
`Block`	`newBlock()` Returns a new `Block` with the next available `Label`.
`java.util.Collection`	`pdomChildren(Block block)` Returns the postdominator children of a given block.
`java.util.Collection`	`pdomFrontier(Block block)` Returns the postdominance frontier of a given block.
`Block`	`pdomParent(Block block)` Returns the postdominator parent of a given block.
`java.util.List`	`postOrder()` Returns the blocks in the flow graph sorted in post-order.
`java.util.List`	`preOrder()` Returns the blocks in the flow graph sorted in pre-order.
`void`	`print()`
`void`	`print(java.io.PrintStream out)`
`void`	`print(java.io.PrintWriter out)` Prints the graph.
`void`	`printGraph()`
`void`	`printGraph(java.io.PrintStream out)` Creates a graphical description of the CFG in the dot language.
`void`	`printGraph(java.io.PrintWriter out)`
`void`	`printGraph(java.io.PrintWriter out, java.lang.String name)`
`void`	`removeEdge(GraphNode v, GraphNode w)` Removes an edge from the graph and performs the necessary cleanup.
`void`	`removeNode(java.lang.Object key)` Removes a node (a Block) from the graph.
`void`	`removeSub(Subroutine sub)` Removes a subroutine from this method.
`java.util.Collection`	`reverseRoots()`
`java.util.Collection`	`roots()`
`Block`	`sink()` Returns the sink block.
`Block`	`source()` Returns the "Enter" block of this CFG.
`java.util.Collection`	`subroutines()` Returns all of the `Subroutine`s in the method modeled by this `FlowGraph`.
`java.lang.String`	`toString()` Returns a brief textual description of this `FlowGraph`, namely the name of the method it represents.
`java.util.List`	`trace()` Returns the basic blocks contained in this CFG in trace order.
`void`	`visit(TreeVisitor visitor)`
`void`	`visitChildren(TreeVisitor visitor)` Visit each node (block) in this CFG in pre-order.

Methods inherited from class EDU.purdue.cs.bloat.util.Graph
addNode, getNode, hasEdge, hasNode, isAncestorToDescendent, keySet, nodes, postOrderIndex, preds, preOrderIndex, removeUnreachable, size, succs

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - PEEL_NO_LOOPS
```
public static final int PEEL_NO_LOOPS
```
    See Also:
    Constant Field Values
  - PEEL_ALL_LOOPS
```
public static final int PEEL_ALL_LOOPS
```
    See Also:
    Constant Field Values
  - 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.
  - visit
```
public void visit(TreeVisitor visitor)
```
  - 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

Class FlowGraph

Field Summary

Fields inherited from class EDU.purdue.cs.bloat.util.Graph

Constructor Summary

Method Summary

Methods inherited from class EDU.purdue.cs.bloat.util.Graph

Methods inherited from class java.lang.Object

Field Detail

PEEL_NO_LOOPS

PEEL_ALL_LOOPS

PEEL_LOOPS_LEVEL

DEBUG

DB_GRAPHS

PRINT_GRAPH

Constructor Detail

FlowGraph

Method Detail

maxLoopDepth

initialize

loopTree

removeSub

addEdge

removeEdge

newBlock

labelSub

subroutines

print

print

printGraph

print

printGraph

printGraph

printGraph

visitChildren

visit

method

trace

commit

source

init

sink

iteratedDomFrontier

iteratedPdomFrontier

roots

reverseRoots

removeNode

handlersMap

handlers

catchBlocks

domChildren

domParent

blockType

loopDepth

loopLevel

loopHeader

preOrder

postOrder

pdomChildren

pdomParent

domFrontier

pdomFrontier

toString