sofya.graphs.cfg
Class CFG

java.lang.Object
  sofya.graphs.Graph
      sofya.graphs.cfg.CFG

All Implemented Interfaces:

SConstants

public class CFG
extends Graph
implements SConstants

Class which represents the basic block control flow graph for a given method.

Version:

02/11/2005

Author:

Alex Kinneer

Nested Class Summary

Nested classes/interfaces inherited from interface sofya.base.SConstants

SConstants.BlockLabel, SConstants.BlockObjectType, SConstants.BlockSubType, SConstants.BlockType, SConstants.BranchObjectType, SConstants.BranchType, SConstants.EDObjectType, SConstants.TraceObjectType

Field Summary

protected gnu.trove.TIntObjectHashMap	blockOffsetMap Lookup table which maps bytecode offsets to blocks, used to optimize retrieval of successor blocks when constructing edges.
protected java.lang.String	displayString Human-friendly string for the method for which this CFG was built.
protected MethodSignature	methodSignature Signature of the method for which the control flow graph is built.

Fields inherited from class sofya.graphs.Graph

edges, MATCH_INCOMING, MATCH_OUTGOING, nodes

Fields inherited from interface sofya.base.SConstants

DEFAULT_PORT, INST_COMPATIBLE, INST_OLD_UNSUPPORTED, INST_OPT_NORMAL, INST_OPT_SEQUENCE, SIG_CHKALIVE, SIG_ECHO

Constructor Summary

protected	CFG(MethodSignature signature, java.lang.String displayString) Creates a control flow graph.
protected	CFG(java.lang.String displayString) Creates a control flow graph.

Method Summary

protected void	addBlock(Block b) Adds a block to the CFG.
protected void	addEdge(Edge e) Adds an edge to the list of edges.
protected Block	addExceptionalExit(Block realExit) Creates and adds to the CFG an exceptional exit block associated with a given 'real' block.
protected void	addNode(Node n) Adds a node to the CFG, creating an entry in the offset map so the block can be retrieved by its start offset later.
Block[]	getBasicBlocks() Gets the basic blocks in this control flow graph.
Block[]	getBasicBlocks(int typeMask) Gets the basic blocks in this control flow graph corresponding to selected types.
Block	getBlock(int id) Gets a block from the node list.
int	getHighestNodeId() Returns the highest node ID in the control flow graph.
java.lang.String	getMethodName() Returns the name of the method with which this control flow graph is associated.
int	getNumberOfBranches() Returns the number of branches in the control flow graph.
int	getNumberOfEdges() Returns the number of edges in the control flow graph.
int	getNumberOfNodes() Returns the number of nodes in the control flow graph.
int	getRootNodeID() Returns the ID of the root node of the control flow graph.
MethodSignature	getSignature() Gets the signature of the method that this CFG models.
int	getSummaryBranchID() Returns the ID of summary branch, which captures all exceptional exits from the method that cannot be precisely identified.
protected void	setNumberOfBranches(int count) Sets the number of branches in the control flow graph, for use by CFHandler.
protected void	setSignature(MethodSignature ms) Sets the signature of the method that this CFG models.
protected void	setSummaryBranchID(int id) Sets the ID of summary branch.
java.lang.String	toString() Returns string representation of the control flow graph, which is a list of the edges that constitute the CFG.

Methods inherited from class sofya.graphs.Graph

clear, getEdge, getEdgeCount, getEdges, getEdges, getEdges, getNode, getNodeCount, getRootNode, removeEdge, removeNode

Methods inherited from class java.lang.Object

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

Field Detail

methodSignature

protected MethodSignature methodSignature

Signature of the method for which the control flow graph is built.

displayString

protected java.lang.String displayString

Human-friendly string for the method for which this CFG was built.

blockOffsetMap

protected gnu.trove.TIntObjectHashMap blockOffsetMap

Lookup table which maps bytecode offsets to blocks, used to optimize retrieval of successor blocks when constructing edges.

Constructor Detail

CFG

protected CFG(MethodSignature signature,
              java.lang.String displayString)

Creates a control flow graph.

Parameters:

signature - Signature of the method for which the control flow graph will be built.

displayString - Human-friendly string to represent the method for which the control flow graph will be built.

CFG

protected CFG(java.lang.String displayString)

Creates a control flow graph.

Used by the MapHandler primarily to provide legacy support.

Parameters:

displayString - Human-friendly string to represent the method for which the control flow graph is/was built.

Method Detail

getSignature

public MethodSignature getSignature()

Gets the signature of the method that this CFG models.

Returns:

The signature of the method for which this CFG was constructed.

setSignature

protected void setSignature(MethodSignature ms)

Sets the signature of the method that this CFG models.

Parameters:

ms - The signature of the method for which this CFG has been constructed.

getBasicBlocks

public Block[] getBasicBlocks()

Gets the basic blocks in this control flow graph.

Returns:

An array containing the basic blocks identified in the method.

getBasicBlocks

public Block[] getBasicBlocks(int typeMask)

Gets the basic blocks in this control flow graph corresponding to selected types.

Parameters:

typeMask - Bitmask indicating the types of basic blocks to be retrieved.

Returns:

An array containing the basic blocks of the given type(s) identified in the method.

getBlock

public Block getBlock(int id)

Gets a block from the node list.

Parameters:

id - ID of the block to be retrieved.

Returns:

The block in the node list with the specified ID, if any.

addEdge

protected void addEdge(Edge e)

Adds an edge to the list of edges.

Overrides:

addEdge in class Graph

Parameters:

e - Edge to be added to the CFG.

See Also:

Edge

addNode

protected void addNode(Node n)

Adds a node to the CFG, creating an entry in the offset map so the block can be retrieved by its start offset later.

If the given node is not a Block, this method behaves identically to the implementation in Graph. 'Virtual' blocks (entry, exit, and return) are not added to the offset map. This is because the offset map is an optimization to speed up the creation of the most common types of edges representing flow of control through actual code. Creation of edges pointing to virtual nodes is handled explicitly as necessary.

Overrides:

addNode in class Graph

Parameters:

n - Node to be added to the graph, typically expected to be a Block.

addBlock

protected void addBlock(Block b)

Adds a block to the CFG.

Parameters:

b - Block to be added to the CFG.

See Also:

Block

addExceptionalExit

protected Block addExceptionalExit(Block realExit)

Creates and adds to the CFG an exceptional exit block associated with a given 'real' block.

Note: The new block created by this method will not be connected to any other blocks through any predecessor or successor references. An edge connecting the blocks must also be added to establish those relationships. However, the (virtual) exit block's start and end offsets will be equivalent to those of the 'real' node with which it is associated.

Parameters:

realExit - Block which represents the actual code at which the exit occurs.

Returns:

The block that was created and added to the graph.

See Also:

Block

getNumberOfNodes

public int getNumberOfNodes()

Returns the number of nodes in the control flow graph.

Returns:

The number of nodes in the control flow graph.

getNumberOfEdges

public int getNumberOfEdges()

Returns the number of edges in the control flow graph.

Returns:

The number of edges in the control flow graph.

getNumberOfBranches

public int getNumberOfBranches()

Returns the number of branches in the control flow graph.

Returns:

The number of branches (branch IDs) in the control flow graph.

setNumberOfBranches

protected void setNumberOfBranches(int count)

Sets the number of branches in the control flow graph, for use by CFHandler.

Parameters:

count - The number of branches (branch IDs) in the control flow graph.

getHighestNodeId

public int getHighestNodeId()

Returns the highest node ID in the control flow graph.

Returns:

The highest ID of any node currently in the control flow graph.

getMethodName

public java.lang.String getMethodName()

Returns the name of the method with which this control flow graph is associated.

Returns:

The name of the method for which this control flow graph was built.

getRootNodeID

public int getRootNodeID()

Returns the ID of the root node of the control flow graph.

Returns:

The ID of the node that is the root of the control flow graph.

getSummaryBranchID

public int getSummaryBranchID()

Returns the ID of summary branch, which captures all exceptional exits from the method that cannot be precisely identified.

Returns:

The ID of summary branch.

setSummaryBranchID

protected void setSummaryBranchID(int id)

Sets the ID of summary branch.

Parameters:

id - The ID of summary branch.

toString

public java.lang.String toString()

Returns string representation of the control flow graph, which is a list of the edges that constitute the CFG.

Overrides:

toString in class Graph

Returns:

List of edges that constitute this control flow graph.

See Also:

Block.toString(), Edge.toString()