com.ibm.wala.dataflow.IFDS
Interface ISupergraph<T,P>

All Superinterfaces:

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

All Known Implementing Classes:

BackwardsSupergraph, ICFGSupergraph

public interface ISupergraph<T,P>
extends NumberedGraph<T>

A supergraph as defined by Reps, Horwitz, and Sagiv POPL95

In our implementation we don't require explicit entry and exit nodes. So, the first basic block in a method is implicitly the entry node, but might also be a call node too. Similarly for exit nodes. The solver is coded to deal with this appropriately.

Additionally, due to exceptional control flow, each method might have multiple exits or multiple entries. T type of node in the supergraph P type of a procedure (like a box in an RSM)

Field Summary

static byte	CALL_EDGE
static byte	CALL_TO_RETURN_EDGE
static byte	OTHER
static byte	RETURN_EDGE

Method Summary

byte	classifyEdge(T src, T dest)
java.util.Iterator<? extends T>	getCalledNodes(T call)
java.util.Iterator<? extends T>	getCallSites(T ret, P callee)
T[]	getEntriesForProcedure(P procedure)
T[]	getExitsForProcedure(P procedure)
T	getLocalBlock(P procedure, int i)
int	getLocalBlockNumber(T n)
java.util.Iterator<T>	getNormalSuccessors(T call)
int	getNumberOfBlocks(P procedure)
Graph<? extends P>	getProcedureGraph()
P	getProcOf(T n)
java.util.Iterator<? extends T>	getReturnSites(T call, P callee)
boolean	isCall(T n)
boolean	isEntry(T n)
boolean	isExit(T n)
boolean	isReturn(T n)

Methods inherited from interface com.ibm.wala.util.graph.Graph

removeNodeAndEdges

Methods inherited from interface com.ibm.wala.util.graph.NodeManager

addNode, containsNode, getNumberOfNodes, iterator, removeNode

Methods inherited from interface com.ibm.wala.util.graph.EdgeManager

addEdge, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeOutgoingEdges

Methods inherited from interface com.ibm.wala.util.graph.NumberedNodeManager

getMaxNumber, getNode, getNumber, iterateNodes

Methods inherited from interface com.ibm.wala.util.graph.NodeManager

addNode, containsNode, getNumberOfNodes, iterator, removeNode

Methods inherited from interface com.ibm.wala.util.graph.NumberedEdgeManager

getPredNodeNumbers, getSuccNodeNumbers

Methods inherited from interface com.ibm.wala.util.graph.EdgeManager

addEdge, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeOutgoingEdges

Field Detail

CALL_EDGE

static final byte CALL_EDGE

See Also:

Constant Field Values

RETURN_EDGE

static final byte RETURN_EDGE

See Also:

Constant Field Values

CALL_TO_RETURN_EDGE

static final byte CALL_TO_RETURN_EDGE

See Also:

Constant Field Values

OTHER

static final byte OTHER

See Also:

Constant Field Values

Method Detail

getProcedureGraph

Graph<? extends P> getProcedureGraph()

Returns:

the graph of procedures (e.g. a call graph) over which this supergraph is induced.

isCall

boolean isCall(T n)

Parameters:

n - a node in this supergraph

Returns:

true iff this node includes a call.

getCalledNodes

java.util.Iterator<? extends T> getCalledNodes(T call)

Parameters:

call - a "call" node in the supergraph

Returns:

an Iterator of nodes that are targets of this call.

getNormalSuccessors

java.util.Iterator<T> getNormalSuccessors(T call)

Parameters:

call - a "call" node in the supergraph

Returns:

an Iterator of nodes that are normal (non-call) successors of this call. This should only apply to backwards problems, where we might have, say, a call and a goto flow into a return site.

getReturnSites

java.util.Iterator<? extends T> getReturnSites(T call,
                                               P callee)

Parameters:

call - a "call" node in the supergraph

callee - a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.

Returns:

the corresponding return nodes. There may be many, because of exceptional control flow.

getCallSites

java.util.Iterator<? extends T> getCallSites(T ret,
                                             P callee)

Parameters:

r - a "return" node in the supergraph

callee - a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.

Returns:

the corresponding call nodes. There may be many.

isExit

boolean isExit(T n)

Parameters:

n - a node in the supergraph

Returns:

true iff this node is an exit node

getProcOf

P getProcOf(T n)

Parameters:

n - a node in the supergraph

Returns:

an object which represents the procedure which contains n

getEntriesForProcedure

T[] getEntriesForProcedure(P procedure)

Returns:

the blocks in the supergraph that represents entry nodes for procedure p

getExitsForProcedure

T[] getExitsForProcedure(P procedure)

Returns:

the blocks in the supergraph that represents exit nodes for procedure p

getNumberOfBlocks

int getNumberOfBlocks(P procedure)

Parameters:

procedure - an object that represents a procedure

Returns:

the number of blocks from this procedure in this supergraph

getLocalBlockNumber

int getLocalBlockNumber(T n)

Parameters:

n - a node in the supergraph

Returns:

the "logical" basic block number of n in its procedure

getLocalBlock

T getLocalBlock(P procedure,
                int i)

Parameters:

procedure - an object that represents a procedure

i - the "logical" basic block number of a node in the procedure

Returns:

the corresponding node in the supergraph

isReturn

boolean isReturn(T n)

Parameters:

n - a node in this supergraph

Returns:

true iff this node is a return site.

isEntry

boolean isEntry(T n)

Returns:

true iff this node is an entry node s_p for a procedure

classifyEdge

byte classifyEdge(T src,
                  T dest)

Parameters:

src - node in the supergraph

dest - a successor of src in the supergraph

Returns:

one of CALL_EDGE, RETURN_EDGE, CALL_TO_RETURN_EDGE, or OTHER