cetus.analysis

Class CFGraph

java.lang.Object

cetus.analysis.DFAGraph

cetus.analysis.CFGraph

public class CFGraph
extends DFAGraph

CFGraph supports creation of statmenet-level control flow graphs. The DFANode class is used to represent each node in the graph. The nodes in a CFGraph object contain information gathered from their corresponding Cetus IR and these data can be accessed with the DFANode.getData(String) method. Following key:data pairs are added to each node by default after calling the constructor of CFGraph.

• ir: the IR associated with the node (either Expression or Statement).
• stmt: the Statement IR whose entry node is this node.
• stmt-exit: the Statement IR whose exit node is this node.
• symbol-entry: symbol table object whose entry node is this node.
• symbol-exit: list of symbol table object whose exit node is this node.
• true: the successor node for the "taken" branch.
• false: the successor node for the "not-taken" branch.
• tag: additional information about each node.

Notice that not every content above is available at a node since some nodes merely represents loop controls or entry/exit point of certain Cetus IRs.

Nested Class Summary

Nested classes/interfaces inherited from class cetus.analysis.DFAGraph

DFAGraph.TopIterator

Constructor Summary

Constructors

Constructor and Description
CFGraph(NestedDeclarator t, boolean arrayDecl) Constructs a CFGraph object for NestedDeclarator, which is used by def-use/use-def chain computation.
CFGraph(Traversable t) Constructs a CFGraph object with the given traversable object.
CFGraph(Traversable t, java.lang.Class<? extends Traversable> supernode) Constructs a CFGraph object with the given traversable object and the IR type whose sub graph is pruned.
CFGraph(Traversable t, java.lang.Class<? extends Traversable> supernode, boolean includeDeclarator, java.util.List<VariableDeclaration> paramList) Constructs a CFGraph object which is used by def-use/use-def chain computation.
CFGraph(VariableDeclarator t, boolean arrayDecl) Constructs a CFGraph object for VariableDeclarator, which is used by def-use/use-def chain computation.

Method Summary

Methods

Modifier and Type	Method and Description
DFANode	getCallNode(FunctionCall fc) Returns the DFANode object that contains the given function call.
DFANode	getEntry()
static java.lang.Object	getIR(DFANode node) Returns the corresponding IR object for the specified node.
void	normalize() Normalizes the graph so that each node does not have an assignment expression as a sub expression of another expression.
java.lang.String	toDot() Converts the graph to a string in dot format to be used with GraphViz.

Methods inherited from class cetus.analysis.DFAGraph

absorb, addEdge, addNode, getEntryNodes, getExitNodes, getFirst, getLast, getNode, getNode, getNodeWith, getSCC, isEmpty, isReachable, iterator, removeEdge, removeNode, removeNodes, size, toDot, topologicalSort, topologicalSortOptimized, toString

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

CFGraph

public CFGraph(Traversable t)

Constructs a CFGraph object with the given traversable object. The entry node contains a string "ENTRY" for the key "stmt".

Parameters:

t - the traversable object.

CFGraph

public CFGraph(Traversable t,
       java.lang.Class<? extends Traversable> supernode)

Constructs a CFGraph object with the given traversable object and the IR type whose sub graph is pruned. The resulting control flow graph does contain the sub graphs for the specified IR type but those sub graphs are not connected to/from the whole graph. Depending on the applications of CFGraph, those isolated sub graphs can be removed from or reconnected to the whole graph.

Parameters:

t - the traversable object.

supernode - IR type that is pruned.

CFGraph

public CFGraph(VariableDeclarator t,
       boolean arrayDecl)

Constructs a CFGraph object for VariableDeclarator, which is used by def-use/use-def chain computation.

Parameters:

t - a variable declarator

arrayDecl - a boolean for declarator with arrays

CFGraph

public CFGraph(NestedDeclarator t,
       boolean arrayDecl)

Constructs a CFGraph object for NestedDeclarator, which is used by def-use/use-def chain computation.

Parameters:

t - a nested declarator

arrayDecl - a boolean for declarator with arrays

CFGraph

public CFGraph(Traversable t,
       java.lang.Class<? extends Traversable> supernode,
       boolean includeDeclarator,
       java.util.List<VariableDeclaration> paramList)

Constructs a CFGraph object which is used by def-use/use-def chain computation.

Parameters:

t - a traversable

supernode -

includeDeclarator -

paramList -

Method Detail

toDot

public java.lang.String toDot()

Converts the graph to a string in dot format to be used with GraphViz. By default, it prints out the corresponing IR objects or tags. See DFAGraph.toDot(String,int) for more flexible formatting.

Returns:

the string in dot format.

See Also:

DFAGraph.toDot(String,int)

getIR

public static java.lang.Object getIR(DFANode node)

Returns the corresponding IR object for the specified node.

Parameters:

node - the node in the graph.

Returns:

the corresponding IR, null if no such mapping exists.

getEntry

public DFANode getEntry()

normalize

public void normalize()

Normalizes the graph so that each node does not have an assignment expression as a sub expression of another expression. Expressions that contain conditionally evaluated sub expressions -- e.g., short-circuit evaluation -- are not normalized to avoid possibly unsafe expression evaluation.

getCallNode

public DFANode getCallNode(FunctionCall fc)

Returns the DFANode object that contains the given function call.