EDU.purdue.cs.bloat.cfg
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:

MethodEditor, Block

Field Summary

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

FlowGraph(MethodEditor method)
Constructor.

Method Summary

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 theBlocks 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 Subroutines 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

PEEL_ALL_LOOPS

public static final int PEEL_ALL_LOOPS

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