com.ibm.wala.ssa.analysis
Class ExpandedControlFlowGraph

java.lang.Object
  com.ibm.wala.ssa.analysis.ExpandedControlFlowGraph

All Implemented Interfaces:

ControlFlowGraph, EdgeManager<IBasicBlock>, Graph<IBasicBlock>, NodeManager<IBasicBlock>, NumberedEdgeManager<IBasicBlock>, NumberedGraph<IBasicBlock>, NumberedNodeManager<IBasicBlock>, java.lang.Iterable<IBasicBlock>

public class ExpandedControlFlowGraph
extends java.lang.Object
implements ControlFlowGraph

The ExpandedControlFlowGraph provides a convenient way of performing dataflow analyses over the SSA IR. The SSA IR is efficient, but complicates analyses by exposing null instructions, and by working at the (more efficient) basic-blocks level. The ExpandedControlFlowGraph has the following features: 1. it has a single instruction per basic block (acutally, it uses SingleInstructionBasicBlocks) 2. all instructions, including phi instructions, are present in the graph 3. there are no null instructions in the graph, these are skipped over 4. there are designated single entry and single exit nodes that do not contain any instructions At least at this stage, I prefer the less efficient, but more clear ExpandedControlFlowGraph representation. TODO: this needs MAJOR refactoring !!! [EY]

Nested Class Summary

class	ExpandedControlFlowGraph.SingleInstructionBasicBlock SingleInstructionBasicBlock A basic-block containing a single instructions.
class	ExpandedControlFlowGraph.SingleInstructionExceptionHandlerBlock SingleInstructionExceptionHandlerBlock BB for exception handler.

Constructor Summary

ExpandedControlFlowGraph(IR ir)
create an ExpandedControlFlowGraph

Method Summary

void	addEdge(IBasicBlock src, IBasicBlock dst) unsupported operation
void	addNode(IBasicBlock n) unsupported operation
boolean	containsNode(IBasicBlock n) unsupported operation
void	dumpDotFile() dump dot files of the current CFG and the underlying original CFG.
IBasicBlock	entry() Return the entry basic block in the CFG
IBasicBlock	exit()
java.util.Collection	getAllInstructions() get all instructions in the method
IBasicBlock	getBlockForInstruction(int index)
IBasicBlock	getBlockForInstruction(SSAInstruction s)
BitVector	getCatchBlocks()
java.util.Collection<IBasicBlock>	getExceptionalPredecessors(IBasicBlock b) The order of blocks returned should be arbitrary but deterministic.
java.util.Collection<IBasicBlock>	getExceptionalSuccessors(IBasicBlock b) The order of blocks returned should be arbitrary but deterministic.
IBasicBlock	getFallThroughTarget(IBasicBlock src) get the fall-through target of a given source block
ExpandedControlFlowGraph.SingleInstructionBasicBlock	getInstructionBlock(SSAInstruction inst) return the Instruction-Block for the given instruction.
IInstruction[]	getInstructions()
int	getMaxNumber() unsupported operation
IMethod	getMethod()
IBasicBlock	getNode(int i)
java.util.Collection<IBasicBlock>	getNormalPredecessors(IBasicBlock b) The order of blocks returned should be arbitrary but deterministic.
java.util.Collection<IBasicBlock>	getNormalSuccessors(IBasicBlock b) The order of blocks returned should be arbitrary but deterministic.
int	getNumber(IBasicBlock n) unsupported operation
int	getNumberOfNodes()
java.util.List	getPredecessors(SSACFG.BasicBlock dest) get predecessors of a basic block
int	getPredNodeCount(IBasicBlock node) Return the number of immediate predecessor nodes of this Node in the Graph.
IntSet	getPredNodeNumbers(IBasicBlock node)
java.util.Iterator<IBasicBlock>	getPredNodes(IBasicBlock node) Return an Iterator over the immediate predecessor nodes of this Node in the Graph.
int	getProgramCounter(int index)
java.util.List	getSuccessors(SSACFG.BasicBlock src) get successors of a basic block
int	getSuccNodeCount(IBasicBlock node) Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(IBasicBlock node)
java.util.Iterator<IBasicBlock>	getSuccNodes(IBasicBlock node) Return an Iterator over the immediate successor nodes of this Node in the Graph
java.util.Set	getTrueCasePiInstructions() get a set of true-case pi instructions
boolean	hasEdge(IBasicBlock src, IBasicBlock dst)
boolean	isFallThroughTarget(IBasicBlock src, IBasicBlock dest)
java.util.Iterator<IBasicBlock>	iterateNodes(IntSet set) unsupported operation
java.util.Iterator<IBasicBlock>	iterator()
void	removeAllIncidentEdges(IBasicBlock node) unsupported operation
void	removeEdge(IBasicBlock src, IBasicBlock dst) unsupported operation
void	removeIncomingEdges(IBasicBlock node) unsupported operation
void	removeNode(IBasicBlock obj) unsupported operation
void	removeNodeAndEdges(IBasicBlock n) unsupported operation
void	removeOutgoingEdges(IBasicBlock node) unsupported operation

Methods inherited from class java.lang.Object

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

Constructor Detail

ExpandedControlFlowGraph

public ExpandedControlFlowGraph(IR ir)

create an ExpandedControlFlowGraph

Parameters:

ir - - method's IR (just to avoid re-getting it)

Throws:

java.lang.IllegalArgumentException - if ir is null

Method Detail

getInstructionBlock

public ExpandedControlFlowGraph.SingleInstructionBasicBlock getInstructionBlock(SSAInstruction inst)

return the Instruction-Block for the given instruction.

Parameters:

inst - - instruction

Returns:

SingleInstructionBasicBlock containing the given instruction

getAllInstructions

public java.util.Collection getAllInstructions()

get all instructions in the method

Returns:

a collection of SSAInstructions

getTrueCasePiInstructions

public java.util.Set getTrueCasePiInstructions()

get a set of true-case pi instructions

Returns:

a set of SSAPiInstructions

getSuccessors

public java.util.List getSuccessors(SSACFG.BasicBlock src)

get successors of a basic block

Parameters:

src - - source basic block

Returns:

a List of successor basic-blocks

getPredecessors

public java.util.List getPredecessors(SSACFG.BasicBlock dest)

get predecessors of a basic block

Parameters:

dest - - destination basic block (starting point)

Returns:

a List of predecessor basic-blocks

entry

public IBasicBlock entry()

Return the entry basic block in the CFG

Specified by:

entry in interface ControlFlowGraph

exit

public IBasicBlock exit()

Specified by:

exit in interface ControlFlowGraph

Returns:

the synthetic exit block for the cfg

getCatchBlocks

public BitVector getCatchBlocks()

Specified by:

getCatchBlocks in interface ControlFlowGraph

Returns:

the indices of the catch blocks, as a bit vector

getBlockForInstruction

public IBasicBlock getBlockForInstruction(int index)

Specified by:

getBlockForInstruction in interface ControlFlowGraph

Parameters:

index - an instruction index

Returns:

the basic block which contains this instruction.

getBlockForInstruction

public IBasicBlock getBlockForInstruction(SSAInstruction s)

Returns:

the basic block which contains this instruction.

getInstructions

public IInstruction[] getInstructions()

Specified by:

getInstructions in interface ControlFlowGraph

Returns:

the instructions of this CFG, as an array.

getProgramCounter

public int getProgramCounter(int index)

Specified by:

getProgramCounter in interface ControlFlowGraph

Parameters:

index - an instruction index

Returns:

the program counter (bytecode index) corresponding to that instruction

getMethod

public IMethod getMethod()

Specified by:

getMethod in interface ControlFlowGraph

Returns:

the Method this CFG represents

getExceptionalSuccessors

public java.util.Collection<IBasicBlock> getExceptionalSuccessors(IBasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getExceptionalSuccessors in interface ControlFlowGraph

Parameters:

b -

Returns:

the basic blocks which may be reached from b via exceptional control flow

getNormalSuccessors

public java.util.Collection<IBasicBlock> getNormalSuccessors(IBasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalSuccessors in interface ControlFlowGraph

Parameters:

b -

Returns:

the basic blocks which may be reached from b via normal control flow

getPredNodeCount

public int getPredNodeCount(IBasicBlock node)

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of this Node in the Graph.

Specified by:

getPredNodeCount in interface EdgeManager<IBasicBlock>

Parameters:

node - - source node

Returns:

the number of immediate predecessor Nodes of this Node in the Graph.

getSuccNodes

public java.util.Iterator<IBasicBlock> getSuccNodes(IBasicBlock node)

Description copied from interface: EdgeManager

Return an Iterator over the immediate successor nodes of this Node in the Graph

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<IBasicBlock>

Parameters:

node - - source node

Returns:

iterator over successor nodes

getSuccNodeCount

public int getSuccNodeCount(IBasicBlock node)

Description copied from interface: EdgeManager

Return the number of immediate successor nodes of this Node in the Graph

Specified by:

getSuccNodeCount in interface EdgeManager<IBasicBlock>

Parameters:

node - - source node

Returns:

number of successor nodes

addEdge

public void addEdge(IBasicBlock src,
                    IBasicBlock dst)
             throws java.lang.UnsupportedOperationException

unsupported operation

Specified by:

addEdge in interface EdgeManager<IBasicBlock>

Throws:

java.lang.UnsupportedOperationException - unconditionally

removeEdge

public void removeEdge(IBasicBlock src,
                       IBasicBlock dst)

unsupported operation

Specified by:

removeEdge in interface EdgeManager<IBasicBlock>

removeAllIncidentEdges

public void removeAllIncidentEdges(IBasicBlock node)

unsupported operation

Specified by:

removeAllIncidentEdges in interface EdgeManager<IBasicBlock>

removeIncomingEdges

public void removeIncomingEdges(IBasicBlock node)

unsupported operation

Specified by:

removeIncomingEdges in interface EdgeManager<IBasicBlock>

removeOutgoingEdges

public void removeOutgoingEdges(IBasicBlock node)

unsupported operation

Specified by:

removeOutgoingEdges in interface EdgeManager<IBasicBlock>

iterateNodes

public java.util.Iterator<IBasicBlock> iterateNodes(IntSet set)

unsupported operation

Specified by:

iterateNodes in interface NumberedNodeManager<IBasicBlock>

Returns:

iterator of nodes with the numbers in set s

containsNode

public boolean containsNode(IBasicBlock n)

unsupported operation

Specified by:

containsNode in interface NodeManager<IBasicBlock>

Returns:

true iff the graph contains the specified node

getMaxNumber

public int getMaxNumber()

unsupported operation

Specified by:

getMaxNumber in interface NumberedNodeManager<IBasicBlock>

iterator

public java.util.Iterator<IBasicBlock> iterator()

Specified by:

iterator in interface NodeManager<IBasicBlock>

Specified by:

iterator in interface java.lang.Iterable<IBasicBlock>

Returns:

an Iterator of the nodes in this graph

removeNode

public void removeNode(IBasicBlock obj)

unsupported operation

Specified by:

removeNode in interface NodeManager<IBasicBlock>

Parameters:

obj - - object to be removed

getPredNodes

public java.util.Iterator<IBasicBlock> getPredNodes(IBasicBlock node)

Description copied from interface: EdgeManager

Return an Iterator over the immediate predecessor nodes of this Node in the Graph. This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<IBasicBlock>

Parameters:

node - - source node

Returns:

iterator over predecssors of given node

addNode

public void addNode(IBasicBlock n)
             throws java.lang.UnsupportedOperationException

unsupported operation

Specified by:

addNode in interface NodeManager<IBasicBlock>

Parameters:

n -

Throws:

java.lang.UnsupportedOperationException - unconditionally

removeNodeAndEdges

public void removeNodeAndEdges(IBasicBlock n)

unsupported operation

Specified by:

removeNodeAndEdges in interface Graph<IBasicBlock>

Parameters:

n -

getNumber

public int getNumber(IBasicBlock n)

unsupported operation

Specified by:

getNumber in interface NumberedNodeManager<IBasicBlock>

Parameters:

n -

getNode

public IBasicBlock getNode(int i)

Specified by:

getNode in interface NumberedNodeManager<IBasicBlock>

Parameters:

i - - number of node to be returned

Returns:

the i-th node

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<IBasicBlock>

Returns:

number of nodes in the graph

isFallThroughTarget

public boolean isFallThroughTarget(IBasicBlock src,
                                   IBasicBlock dest)

getFallThroughTarget

public IBasicBlock getFallThroughTarget(IBasicBlock src)

get the fall-through target of a given source block

Parameters:

src - - source block

Returns:

the fall-through target of the given src block

dumpDotFile

public void dumpDotFile()

dump dot files of the current CFG and the underlying original CFG. note: only used for debugging.

getExceptionalPredecessors

public java.util.Collection<IBasicBlock> getExceptionalPredecessors(IBasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getExceptionalPredecessors in interface ControlFlowGraph

Returns:

the basic blocks from which b may be reached via exceptional control flow

getNormalPredecessors

public java.util.Collection<IBasicBlock> getNormalPredecessors(IBasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalPredecessors in interface ControlFlowGraph

Returns:

the basic blocks from which b may be reached via normal control flow

hasEdge

public boolean hasEdge(IBasicBlock src,
                       IBasicBlock dst)

Specified by:

hasEdge in interface EdgeManager<IBasicBlock>

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(IBasicBlock node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<IBasicBlock>

Returns:

the numbers identifying the immediate successors of node

getPredNodeNumbers

public IntSet getPredNodeNumbers(IBasicBlock node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<IBasicBlock>

Returns:

the numbers identifying the immediate predecessors of node