joeq.Compiler.Quad
Class ControlFlowGraph

java.lang.Object
  joeq.Compiler.Quad.ControlFlowGraph

All Implemented Interfaces:

jwutil.graphs.Graph

public class ControlFlowGraph
extends Object
implements jwutil.graphs.Graph

Control flow graph for the Quad format. The control flow graph is a fundamental part of the quad intermediate representation. The control flow graph organizes the basic blocks for a method. Control flow graphs always include an entry basic block and an exit basic block. These basic blocks are always empty and have id numbers 0 and 1, respectively. A control flow graph includes references to the entry and exit nodes, and the set of exception handlers for the method.

Version:

$Id: ControlFlowGraph.java 2465 2006-06-07 23:03:17Z joewhaley $

Author:

John Whaley

Field Summary

static Map

correspondenceMap Merges the given control flow graph into this control flow graph.

Constructor Summary

ControlFlowGraph(jq_Method method, int numOfExits, int numOfExceptionHandlers, RegisterFactory rf)
Creates a new ControlFlowGraph.

Method Summary

void	addJSRInfo(JSRInfo info)
void	appendExceptionHandlers(ExceptionHandlerList ehl)
BasicBlock	createBasicBlock(int numOfPredecessors, int numOfSuccessors, int numOfInstructions, ExceptionHandlerList ehs) Create a new basic block in this control flow graph.
BasicBlock	entry() Returns the entry node.
BasicBlock	exit() Returns the exit node.
String	fullDump() Returns a verbose string of every basic block in this control flow graph.
List.ExceptionHandler	getExceptionHandlers() Return the list of exception handlers in this control flow graph.
Iterator	getExceptionHandlersMatchingEntry(BasicBlock b) Return an iterator of the exception handlers with the given entry point.
JSRInfo	getJSRInfo(BasicBlock bb)
int	getMaxQuadID() Returns the maximum id number for a quad.
jq_Method	getMethod() Returns the method this control flow graph represents.
jwutil.graphs.Navigator	getNavigator()
int	getNewQuadID() Returns a new id number for a quad.
int	getNumberOfBasicBlocks() Returns a maximum on the number of basic blocks in this control flow graph.
int	getNumberOfQuads()
RegisterFactory	getRegisterFactory() Returns the register factory used by this control flow graph.
Collection	getRoots()
ControlFlowGraph	merge(ControlFlowGraph from)
List.BasicBlock	postOrderOnReverseGraph(BasicBlock start_bb) Returns a list of basic blocks of the reversed graph in post order, starting at the given basic block.
ListIterator.BasicBlock	postOrderOnReverseGraphIterator() Returns an iteration of the basic blocks in the reversed graph in post order.
boolean	removeUnreachableBasicBlocks()
List.BasicBlock	reversePostOrder(BasicBlock start_bb) Returns a list of basic blocks in reverse post order, starting at the given basic block.
ListIterator.BasicBlock	reversePostOrderIterator() Returns an iteration of the basic blocks in this graph in reverse post order.
ListIterator.BasicBlock	reversePostOrderIterator(BasicBlock start_bb) Returns an iteration of the basic blocks in this graph reachable from the given basic block in reverse post order, starting from the given basic block.
List.BasicBlock	reversePostOrderOnReverseGraph(BasicBlock start_bb) Returns a list of basic blocks of the reversed graph in reverse post order, starting at the given basic block.
ListIterator.BasicBlock	reversePostOrderOnReverseGraphIterator() Returns an iteration of the basic blocks in the reversed graph in reverse post order.
void	visitBasicBlocks(BasicBlockVisitor bbv) Visits all of the basic blocks in this graph with the given visitor.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

correspondenceMap

public static Map correspondenceMap

Merges the given control flow graph into this control flow graph. Doesn't modify the given control flow graph. A copy of the given control flow graph (with appropriate renumberings) is returned.

Constructor Detail

ControlFlowGraph

public ControlFlowGraph(jq_Method method,
                        int numOfExits,
                        int numOfExceptionHandlers,
                        RegisterFactory rf)

Creates a new ControlFlowGraph.

Parameters:

numOfExits - the expected number of branches to the exit node.

numOfExceptionHandlers - the expected number of exception handlers.

Method Detail

entry

public BasicBlock entry()

Returns the entry node.

Returns:

the entry node.

exit

public BasicBlock exit()

Returns the exit node.

Returns:

the exit node.

getMethod

public jq_Method getMethod()

Returns the method this control flow graph represents. May be null for synthetic methods.

Returns:

method this control flow graph represents, or null for synthetic.

getRegisterFactory

public RegisterFactory getRegisterFactory()

Returns the register factory used by this control flow graph.

Returns:

the register factory used by this control flow graph.

createBasicBlock

public BasicBlock createBasicBlock(int numOfPredecessors,
                                   int numOfSuccessors,
                                   int numOfInstructions,
                                   ExceptionHandlerList ehs)

Create a new basic block in this control flow graph. The new basic block is given a new, unique id number.

Parameters:

numOfPredecessors - number of predecessor basic blocks that this basic block is expected to have.

numOfSuccessors - number of successor basic blocks that this basic block is expected to have.

numOfInstructions - number of instructions that this basic block is expected to have.

ehs - set of exception handlers for this basic block.

Returns:

the newly created basic block.

getNumberOfBasicBlocks

public int getNumberOfBasicBlocks()

Returns a maximum on the number of basic blocks in this control flow graph.

Returns:

a maximum on the number of basic blocks in this control flow graph.

getNumberOfQuads

public int getNumberOfQuads()

getNewQuadID

public int getNewQuadID()

Returns a new id number for a quad.

getMaxQuadID

public int getMaxQuadID()

Returns the maximum id number for a quad.

addJSRInfo

public void addJSRInfo(JSRInfo info)

getJSRInfo

public JSRInfo getJSRInfo(BasicBlock bb)

reversePostOrderIterator

public ListIterator.BasicBlock reversePostOrderIterator()

Returns an iteration of the basic blocks in this graph in reverse post order.

Returns:

an iteration of the basic blocks in this graph in reverse post order.

reversePostOrderOnReverseGraphIterator

public ListIterator.BasicBlock reversePostOrderOnReverseGraphIterator()

Returns an iteration of the basic blocks in the reversed graph in reverse post order. The reversed graph is the graph where all edges are reversed.

Returns:

an iteration of the basic blocks in the reversed graph in reverse post order.

postOrderOnReverseGraphIterator

public ListIterator.BasicBlock postOrderOnReverseGraphIterator()

Returns an iteration of the basic blocks in the reversed graph in post order. The reversed graph is the graph where all edges are reversed.

Returns:

an iteration of the basic blocks in the reversed graph in post order.

reversePostOrderIterator

public ListIterator.BasicBlock reversePostOrderIterator(BasicBlock start_bb)

Returns an iteration of the basic blocks in this graph reachable from the given basic block in reverse post order, starting from the given basic block.

Parameters:

start_bb - basic block to start reverse post order from.

Returns:

an iteration of the basic blocks in this graph reachable from the given basic block in reverse post order.

visitBasicBlocks

public void visitBasicBlocks(BasicBlockVisitor bbv)

Visits all of the basic blocks in this graph with the given visitor.

Parameters:

bbv - visitor to visit each basic block with.

reversePostOrder

public List.BasicBlock reversePostOrder(BasicBlock start_bb)

Returns a list of basic blocks in reverse post order, starting at the given basic block.

Parameters:

start_bb - basic block to start from.

Returns:

a list of basic blocks in reverse post order, starting at the given basic block.

reversePostOrderOnReverseGraph

public List.BasicBlock reversePostOrderOnReverseGraph(BasicBlock start_bb)

Returns a list of basic blocks of the reversed graph in reverse post order, starting at the given basic block.

Parameters:

start_bb - basic block to start from.

Returns:

a list of basic blocks of the reversed graph in reverse post order, starting at the given basic block.

postOrderOnReverseGraph

public List.BasicBlock postOrderOnReverseGraph(BasicBlock start_bb)

Returns a list of basic blocks of the reversed graph in post order, starting at the given basic block.

Parameters:

start_bb - basic block to start from.

Returns:

a list of basic blocks of the reversed graph in post order, starting at the given basic block.

getExceptionHandlers

public List.ExceptionHandler getExceptionHandlers()

Return the list of exception handlers in this control flow graph.

getExceptionHandlersMatchingEntry

public Iterator getExceptionHandlersMatchingEntry(BasicBlock b)

Return an iterator of the exception handlers with the given entry point.

Parameters:

b - basic block to check exception handlers against.

Returns:

an iterator of the exception handlers with the given entry point.

fullDump

public String fullDump()

Returns a verbose string of every basic block in this control flow graph.

Returns:

a verbose string of every basic block in this control flow graph.

merge

public ControlFlowGraph merge(ControlFlowGraph from)

appendExceptionHandlers

public void appendExceptionHandlers(ExceptionHandlerList ehl)

getRoots

public Collection getRoots()

Specified by:

getRoots in interface jwutil.graphs.Graph

getNavigator

public jwutil.graphs.Navigator getNavigator()

Specified by:

getNavigator in interface jwutil.graphs.Graph

removeUnreachableBasicBlocks

public boolean removeUnreachableBasicBlocks()