avrora.core
Class ControlFlowGraph

java.lang.Object
  avrora.core.ControlFlowGraph

public class ControlFlowGraph

extends java.lang.Object

The ControlFlowGraph represents a control flow graph for an entire program, including all basic blocks and all procedures.

See Also:

Program, ProcedureMap

Nested Class Summary

class	ControlFlowGraph.Block The Block class represents a basic block of code within the program.
class	ControlFlowGraph.Edge The Edge represents an edge leaving a basic block and (optionally) arriving at another, known basic block.

Field Summary

protected java.util.HashMap	blocks The blocks field contains a reference to a map from Integer to Block this map is used to lookup the basic block that starts at a particular address.
static java.util.Comparator	COMPARATOR The COMPARATOR field stores a comparator that is used in sorting basic blocks by program order.
protected java.util.List	edges The edges field contains a reference to the list of edges (instances of class Edge) within this control flow graph.
protected Program	program The program field stores a reference to the program to which this control flow graph corresponds.

Method Summary

void	addEdge(ControlFlowGraph.Block s, ControlFlowGraph.Block t) The addEdge() method adds an edge between two blocks.
void	addEdge(ControlFlowGraph.Block s, ControlFlowGraph.Block t, java.lang.String type) The addEdge() method adds an edge between two blocks with a given type.
ControlFlowGraph.Block	getBlockContaining(int address) The getBlockContaining() method looks up the basic block that contains the address specified.
java.util.Iterator	getBlockIterator() The getBlockIterator() method constructs an interator over all of the blocks in the control flow graph, regardless of connectivity.
ControlFlowGraph.Block	getBlockStartingAt(int address) The getBlockStartingAt() method looks up a basic block based on its starting address.
java.util.Iterator	getEdgeIterator() The getEdgeIterator() method returns an interator over all edges between all blocks within this control flow graph.
ProcedureMap	getProcedureMap() The getProcedureMap() method returns a reference to a ProcedureMap instance that maps basic blocks to the procedures in which they are contained
java.util.Iterator	getSortedBlockIterator() The getBlockIterator() method constructs an interator over all of the blocks in the control flow graph, regardless of connectivity.
ControlFlowGraph.Block	newBlock(int address) The newBlock() method creates a new block within the control flow graph, starting at the specified address.

Methods inherited from class java.lang.Object

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

Field Detail

blocks

protected final java.util.HashMap blocks

The blocks field contains a reference to a map from Integer to Block this map is used to lookup the basic block that starts at a particular address.

edges

protected final java.util.List edges

The edges field contains a reference to the list of edges (instances of class Edge) within this control flow graph.

program

protected final Program program

The program field stores a reference to the program to which this control flow graph corresponds.

COMPARATOR

public static final java.util.Comparator COMPARATOR

The COMPARATOR field stores a comparator that is used in sorting basic blocks by program order.

Method Detail

newBlock

public ControlFlowGraph.Block newBlock(int address)

The newBlock() method creates a new block within the control flow graph, starting at the specified address. No checking is done by this method as to whether the address overlaps with another block. This is primarily intended for use within the CFGBuilder class.

Parameters:

address - the byte address at which this block begins

Returns:

an instance of Block representing the new block

addEdge

public void addEdge(ControlFlowGraph.Block s,
                    ControlFlowGraph.Block t,
                    java.lang.String type)

The addEdge() method adds an edge between two blocks with a given type. If the destination block is null, then the edge has an unknown target.

Parameters:

s - the source block of the edge

t - the target block of the edge

type - the string name of the type of the edge, e.g. CALL or RETURN

addEdge

public void addEdge(ControlFlowGraph.Block s,
                    ControlFlowGraph.Block t)

The addEdge() method adds an edge between two blocks. If the destination block is null, then the edge has an unknown target.

Parameters:

s - the source block of the edge

t - the target block of the edge

getBlockStartingAt

public ControlFlowGraph.Block getBlockStartingAt(int address)

The getBlockStartingAt() method looks up a basic block based on its starting address. If a basic block contains the address, but does not begin at that address, that basic block is ignored.

Parameters:

address - the byte address at which the block begins

Returns:

a reference to the Block instance that starts at the address specified, if such a block exists; null otherwise

getBlockContaining

public ControlFlowGraph.Block getBlockContaining(int address)

The getBlockContaining() method looks up the basic block that contains the address specified. The basic blocks are assumed to not overlap.

Returns:

a reference to the Block instance that contains the address specified, if such a block exists; null otherwise

getBlockIterator

public java.util.Iterator getBlockIterator()

The getBlockIterator() method constructs an interator over all of the blocks in the control flow graph, regardless of connectivity. No order is guaranteed.

Returns:

an instance of Iterator that can be used to iterate over all blocks in the control flow graph

getSortedBlockIterator

public java.util.Iterator getSortedBlockIterator()

The getBlockIterator() method constructs an interator over all of the blocks in the control flow graph, regardless of connectivity. The order is guaranteed to be in ascending order.

Returns:

an instance of Iterator that can be used to iterate over all blocks in the control flow graph in ascending order

getEdgeIterator

public java.util.Iterator getEdgeIterator()

The getEdgeIterator() method returns an interator over all edges between all blocks within this control flow graph.

Returns:

an instance of Iterator that iterates over the edges of this control flow graph.

getProcedureMap

public ProcedureMap getProcedureMap()

The getProcedureMap() method returns a reference to a ProcedureMap instance that maps basic blocks to the procedures in which they are contained

Returns:

a reference to a ProcedureMap instance for this control flow graph