Package com.ibm.wala.ssa

Class SSACFG

java.lang.Object

com.ibm.wala.ssa.SSACFG

All Implemented Interfaces:

ControlFlowGraph<SSAInstruction,ISSABasicBlock>, MinimalCFG<ISSABasicBlock>, EdgeManager<ISSABasicBlock>, Graph<ISSABasicBlock>, NodeManager<ISSABasicBlock>, NumberedEdgeManager<ISSABasicBlock>, NumberedGraph<ISSABasicBlock>, NumberedNodeManager<ISSABasicBlock>, Iterable<ISSABasicBlock>

public class SSACFG
extends Object
implements ControlFlowGraph<SSAInstruction,ISSABasicBlock>, MinimalCFG<ISSABasicBlock>

A control-flow graph for ssa form.

This implementation is uglified in the name of performance. This implementation does not directly track the graph structure, but instead delegates to a prebuilt ControlFlowGraph which stores the structure. This decision from 2004 may have been premature optimization, left over from a world where IRs and related structures were long-lived. In today's system, they are cached and reconstituted by SSACache. Perhaps we should just extend AbstractCFG and not worry so much about space.

As the current implementation stands, the delegate graph stores the graph structure, and this class additionally stores SSACFG.BasicBlocks and the SSAInstruction array.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	SSACFG.BasicBlock	A Basic Block in an SSA IR
class	SSACFG.ExceptionHandlerBasicBlock

Field Summary

Fields

Modifier and Type	Field	Description
protected final AbstractCFG<IInstruction,IBasicBlock<IInstruction>>	delegate	A delegate CFG, pre-built, which stores the graph structure of this CFG.
protected final SSAInstruction[]	instructions	The "normal" instructions which constitute the SSA form.
protected final IMethod	method	The IMethod this ControlFlowGraph represents

Constructor Summary

Constructors

Constructor	Description
SSACFG(IMethod method, AbstractCFG cfg, SSAInstruction[] instructions)

Method Summary

Modifier and Type	Method	Description
void	addEdge(ISSABasicBlock src, ISSABasicBlock dst)
void	addNode(ISSABasicBlock n)	add a node to this graph
boolean	containsNode(ISSABasicBlock N)
SSACFG.BasicBlock	entry()	Return the entry basic block in the CFG
boolean	equals(Object o)
SSACFG.BasicBlock	exit()
SSACFG.BasicBlock	getBasicBlock(int bb)
SSACFG.BasicBlock	getBlockForInstruction(int instructionIndex)	Get the basic block an instruction belongs to.
BitVector	getCatchBlocks()
Collection<ISSABasicBlock>	getExceptionalPredecessors(ISSABasicBlock b)	The order of blocks returned should be arbitrary but deterministic.
List<ISSABasicBlock>	getExceptionalSuccessors(ISSABasicBlock b)	The order of blocks returned must indicate the exception-handling scope.
SSAInstruction[]	getInstructions()	NB: Use iterators such as IR.iterateAllInstructions() instead of this method.
int	getMaxNumber()
IMethod	getMethod()
SSACFG.BasicBlock	getNode(int number)
Collection<ISSABasicBlock>	getNormalPredecessors(ISSABasicBlock b)	The order of blocks returned should be arbitrary but deterministic.
Collection<ISSABasicBlock>	getNormalSuccessors(ISSABasicBlock b)	The order of blocks returned should be arbitrary but deterministic.
int	getNumber(ISSABasicBlock b)
int	getNumberOfNodes()
int	getPredNodeCount(ISSABasicBlock b)	Return the number of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(ISSABasicBlock node)
Iterator<ISSABasicBlock>	getPredNodes(ISSABasicBlock b)	Return an Iterator over the immediate predecessor nodes of n
int	getProgramCounter(int index)	TODO: move this into IR?
int	getSuccNodeCount(ISSABasicBlock b)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(ISSABasicBlock b)
Iterator<ISSABasicBlock>	getSuccNodes(ISSABasicBlock b)	Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(ISSABasicBlock src, ISSABasicBlock dst)
boolean	hasExceptionalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest)	has exceptional edge src -> dest
int	hashCode()
boolean	hasNormalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest)	has normal edge src -> dest
boolean	isCatchBlock(int i)	is the given i a catch block?
Iterator<ISSABasicBlock>	iterateNodes(IntSet s)
Iterator<ISSABasicBlock>	iterator()
void	removeAllIncidentEdges(ISSABasicBlock node)
void	removeEdge(ISSABasicBlock src, ISSABasicBlock dst)
void	removeIncomingEdges(ISSABasicBlock node)
void	removeNode(ISSABasicBlock n)	remove a node from this graph
void	removeNodeAndEdges(ISSABasicBlock N)	remove a node and all its incident edges
void	removeOutgoingEdges(ISSABasicBlock node)
Stream<ISSABasicBlock>	stream()
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

instructions

protected final SSAInstruction[] instructions

The "normal" instructions which constitute the SSA form. This does not include SSAPhiInstructions, which dwell in SSACFG.BasicBlocks instead.

method

protected final IMethod method

The IMethod this ControlFlowGraph represents

delegate

protected final AbstractCFG<IInstruction,IBasicBlock<IInstruction>> delegate

A delegate CFG, pre-built, which stores the graph structure of this CFG.

Constructor Details

SSACFG

public SSACFG(IMethod method,
 AbstractCFG cfg,
 SSAInstruction[] instructions)

Throws:

IllegalArgumentException - if method is null

Method Details

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object o)

Overrides:

equals in class Object

getBlockForInstruction

public SSACFG.BasicBlock getBlockForInstruction(int instructionIndex)

Get the basic block an instruction belongs to. Note: the instruction2Block array is filled in lazily. During initialization, the mapping is set up only for the first instruction of each basic block.

Specified by:

getBlockForInstruction in interface ControlFlowGraph<SSAInstruction,ISSABasicBlock>

Parameters:

instructionIndex - an instruction index

Returns:

the basic block which contains this instruction.

getInstructions

public SSAInstruction[] getInstructions()

NB: Use iterators such as IR.iterateAllInstructions() instead of this method. This will probably be deprecated someday.

Return the instructions. Note that the CFG is created from the Shrike CFG prior to creating the SSA instructions.

Specified by:

getInstructions in interface ControlFlowGraph<SSAInstruction,ISSABasicBlock>

Returns:

an array containing the SSA instructions.

toString

public String toString()

Overrides:

toString in class Object

getCatchBlocks

public BitVector getCatchBlocks()

Specified by:

getCatchBlocks in interface ControlFlowGraph<SSAInstruction,ISSABasicBlock>

Returns:

the indices of the catch blocks, as a bit vector

isCatchBlock

public boolean isCatchBlock(int i)

is the given i a catch block?

Returns:

true if catch block, false otherwise

entry

public SSACFG.BasicBlock entry()

Description copied from interface: MinimalCFG

Return the entry basic block in the CFG

Specified by:

entry in interface MinimalCFG<ISSABasicBlock>

exit

public SSACFG.BasicBlock exit()

Specified by:

exit in interface MinimalCFG<ISSABasicBlock>

Returns:

the synthetic exit block for the cfg

getNumber

public int getNumber(ISSABasicBlock b)
              throws IllegalArgumentException

Specified by:

getNumber in interface NumberedNodeManager<ISSABasicBlock>

Throws:

IllegalArgumentException

getNode

public SSACFG.BasicBlock getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<ISSABasicBlock>

See Also:

• NumberedNodeManager.getNode(int)

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<ISSABasicBlock>

See Also:

• NumberedNodeManager.getMaxNumber()

iterator

public Iterator<ISSABasicBlock> iterator()

Specified by:

iterator in interface Iterable<ISSABasicBlock>

Specified by:

iterator in interface NodeManager<ISSABasicBlock>

Returns:

an Iterator of the nodes in this graph

See Also:

• NodeManager.iterator()

stream

public Stream<ISSABasicBlock> stream()

Specified by:

stream in interface NodeManager<ISSABasicBlock>

Returns:

a Stream of the nodes in this graph

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<ISSABasicBlock>

Returns:

the number of nodes in this graph

See Also:

• NodeManager.getNumberOfNodes()

getPredNodes

public Iterator<ISSABasicBlock> getPredNodes(ISSABasicBlock b)
                                      throws IllegalArgumentException

Description copied from interface: EdgeManager

Return an Iterator over the immediate predecessor nodes of n

This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<ISSABasicBlock>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

Throws:

IllegalArgumentException

See Also:

• EdgeManager.getPredNodes(Object)

getPredNodeCount

public int getPredNodeCount(ISSABasicBlock b)
                     throws IllegalArgumentException

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<ISSABasicBlock>

Returns:

the number of immediate predecessors of n.

Throws:

IllegalArgumentException

See Also:

• EdgeManager.getPredNodeCount(Object)

getSuccNodes

public Iterator<ISSABasicBlock> getSuccNodes(ISSABasicBlock b)
                                      throws IllegalArgumentException

Description copied from interface: EdgeManager

Return an Iterator over the immediate successor nodes of n

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<ISSABasicBlock>

Returns:

an Iterator over the immediate successor nodes of n

Throws:

IllegalArgumentException

See Also:

• EdgeManager.getSuccNodes(Object)

getSuccNodeCount

public int getSuccNodeCount(ISSABasicBlock b)
                     throws IllegalArgumentException

Description copied from interface: EdgeManager

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

Specified by:

getSuccNodeCount in interface EdgeManager<ISSABasicBlock>

Returns:

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

Throws:

IllegalArgumentException

See Also:

• EdgeManager.getSuccNodeCount(Object)

addNode

public void addNode(ISSABasicBlock n)
             throws UnsupportedOperationException

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• NodeManager.addNode(Object)

addEdge

public void addEdge(ISSABasicBlock src,
 ISSABasicBlock dst)
             throws UnsupportedOperationException

Specified by:

addEdge in interface EdgeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

removeEdge

public void removeEdge(ISSABasicBlock src,
 ISSABasicBlock dst)
                throws UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

removeAllIncidentEdges

public void removeAllIncidentEdges(ISSABasicBlock node)
                            throws UnsupportedOperationException

Specified by:

removeAllIncidentEdges in interface EdgeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• EdgeManager.removeAllIncidentEdges(Object)

removeNodeAndEdges

public void removeNodeAndEdges(ISSABasicBlock N)
                        throws UnsupportedOperationException

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<ISSABasicBlock>

Throws:

UnsupportedOperationException - if the graph implementation does not allow removal

See Also:

• NodeManager.removeNode(Object)

removeNode

public void removeNode(ISSABasicBlock n)
                throws UnsupportedOperationException

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• NodeManager.removeNode(Object)

getProgramCounter

public int getProgramCounter(int index)

Description copied from interface: ControlFlowGraph

TODO: move this into IR?

Specified by:

getProgramCounter in interface ControlFlowGraph<SSAInstruction,ISSABasicBlock>

Parameters:

index - an instruction index

Returns:

the program counter (bytecode index) corresponding to that instruction

containsNode

public boolean containsNode(ISSABasicBlock N)

Specified by:

containsNode in interface NodeManager<ISSABasicBlock>

Returns:

true iff the graph contains the specified node

See Also:

• NodeManager.containsNode(Object)

getMethod

public IMethod getMethod()

Specified by:

getMethod in interface ControlFlowGraph<SSAInstruction,ISSABasicBlock>

Returns:

the Method this CFG represents

getExceptionalSuccessors

public List<ISSABasicBlock> getExceptionalSuccessors(ISSABasicBlock b)

Description copied from interface: MinimalCFG

The order of blocks returned must indicate the exception-handling scope. So the first block is the first candidate catch block, and so on. With this invariant one can compute the exceptional control flow for a given exception type.

Specified by:

getExceptionalSuccessors in interface MinimalCFG<ISSABasicBlock>

Returns:

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

getExceptionalPredecessors

public Collection<ISSABasicBlock> getExceptionalPredecessors(ISSABasicBlock b)

Description copied from interface: MinimalCFG

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getExceptionalPredecessors in interface MinimalCFG<ISSABasicBlock>

Returns:

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

See Also:

• MinimalCFG.getExceptionalSuccessors(Object)

hasExceptionalEdge

public boolean hasExceptionalEdge(SSACFG.BasicBlock src,
 SSACFG.BasicBlock dest)

has exceptional edge src -> dest

Throws:

IllegalArgumentException - if dest is null

hasNormalEdge

public boolean hasNormalEdge(SSACFG.BasicBlock src,
 SSACFG.BasicBlock dest)

has normal edge src -> dest

Throws:

IllegalArgumentException - if dest is null

getNormalSuccessors

public Collection<ISSABasicBlock> getNormalSuccessors(ISSABasicBlock b)

Description copied from interface: MinimalCFG

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalSuccessors in interface MinimalCFG<ISSABasicBlock>

Returns:

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

getNormalPredecessors

public Collection<ISSABasicBlock> getNormalPredecessors(ISSABasicBlock b)

Description copied from interface: MinimalCFG

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalPredecessors in interface MinimalCFG<ISSABasicBlock>

Returns:

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

See Also:

• MinimalCFG.getNormalSuccessors(Object)

iterateNodes

public Iterator<ISSABasicBlock> iterateNodes(IntSet s)

Specified by:

iterateNodes in interface NumberedNodeManager<ISSABasicBlock>

Returns:

iterator of nodes with the numbers in set s

See Also:

• NumberedNodeManager.iterateNodes(com.ibm.wala.util.intset.IntSet)

removeIncomingEdges

public void removeIncomingEdges(ISSABasicBlock node)
                         throws UnsupportedOperationException

Specified by:

removeIncomingEdges in interface EdgeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

removeOutgoingEdges

public void removeOutgoingEdges(ISSABasicBlock node)
                         throws UnsupportedOperationException

Specified by:

removeOutgoingEdges in interface EdgeManager<ISSABasicBlock>

Throws:

UnsupportedOperationException

hasEdge

public boolean hasEdge(ISSABasicBlock src,
 ISSABasicBlock dst)
                throws UnimplementedError

Specified by:

hasEdge in interface EdgeManager<ISSABasicBlock>

Throws:

UnimplementedError

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(ISSABasicBlock b)
                          throws IllegalArgumentException

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<ISSABasicBlock>

Returns:

the numbers identifying the immediate successors of node

Throws:

IllegalArgumentException

getPredNodeNumbers

public IntSet getPredNodeNumbers(ISSABasicBlock node)
                          throws UnimplementedError

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<ISSABasicBlock>

Returns:

the numbers identifying the immediate predecessors of node

Throws:

UnimplementedError

getBasicBlock

public SSACFG.BasicBlock getBasicBlock(int bb)

Returns:

the basic block with a particular number