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.

Field Summary

protected java.util.Stack<java.util.List>	break_link
protected java.util.Stack<java.util.List>	continue_link
protected java.util.Map<Label,java.util.List>	goto_link
protected Traversable	root_node
protected java.lang.Class	super_node
protected java.util.Stack<java.util.List>	switch_link

Fields inherited from class cetus.analysis.DFAGraph

nodes

Constructor Summary

CFGraph(Traversable t)
Constructs a CFGraph object with the given traversable object.

CFGraph(Traversable t, java.lang.Class supernode)
Constructs a CFGraph object with the given traversable object and the IR type whose sub graph is pruned.

Method Summary

protected DFAGraph	buildAnnotationStatement(AnnotationStatement stmt)
protected DFANode	buildBreak(Statement stmt)
protected DFANode	buildCase(Statement stmt)
protected DFAGraph	buildCompound(CompoundStatement stmt)
protected DFANode	buildContinue(Statement stmt)
protected DFAGraph	buildDeclarationStatement(DeclarationStatement stmt)
protected DFAGraph	buildDoLoop(DoLoop stmt)
protected DFAGraph	buildForLoop(ForLoop stmt)
protected DFANode	buildGoto(GotoStatement stmt)
protected DFAGraph	buildGraph(Traversable t) Builds a control flow graph for a traversable object.
protected DFAGraph	buildIf(IfStatement stmt)
protected DFANode	buildLabel(Label label)
protected DFAGraph	buildProcedure(Procedure proc)
protected DFAGraph	buildSwitch(SwitchStatement stmt)
protected DFAGraph	buildWhile(WhileLoop stmt)
protected static void	expandAssignment(CompoundStatement stmts, AssignmentExpression e)
protected static void	expandConditional(CompoundStatement stmts, ConditionalExpression e)
protected static void	expandExpression(CompoundStatement stmts, Traversable t)
protected static DFAGraph	expandExpression(DFANode node)
protected static void	expandUnary(CompoundStatement stmts, UnaryExpression e)
static java.lang.Object	getIR(DFANode node) Returns the corresponding IR object for the specified node.
protected static java.util.List	getSafeEvaluation(Traversable t)
protected static boolean	isJump(DFANode node)
protected static boolean	isUnsafeExpansion(Traversable t)
void	normalize() Normalizes the graph so that each node does not have an assignment expression as a sub expression of another expression.
protected void	reduce()
protected boolean	removable_node(DFANode node)
protected static void	removeRedundancy(CompoundStatement stmts)
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, toString

Methods inherited from class java.lang.Object

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

Field Detail

break_link

protected java.util.Stack<java.util.List> break_link

continue_link

protected java.util.Stack<java.util.List> continue_link

switch_link

protected java.util.Stack<java.util.List> switch_link

goto_link

protected java.util.Map<Label,java.util.List> goto_link

super_node

protected java.lang.Class super_node

root_node

protected Traversable root_node

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 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.

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.

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.

buildGraph

protected DFAGraph buildGraph(Traversable t)

Builds a control flow graph for a traversable object.

isJump

protected static boolean isJump(DFANode node)

buildProcedure

protected DFAGraph buildProcedure(Procedure proc)

buildAnnotationStatement

protected DFAGraph buildAnnotationStatement(AnnotationStatement stmt)

buildDeclarationStatement

protected DFAGraph buildDeclarationStatement(DeclarationStatement stmt)

buildBreak

protected DFANode buildBreak(Statement stmt)

buildCase

protected DFANode buildCase(Statement stmt)

buildContinue

protected DFANode buildContinue(Statement stmt)

buildGoto

protected DFANode buildGoto(GotoStatement stmt)

buildLabel

protected DFANode buildLabel(Label label)

buildCompound

protected DFAGraph buildCompound(CompoundStatement stmt)

buildDoLoop

protected DFAGraph buildDoLoop(DoLoop stmt)

buildForLoop

protected DFAGraph buildForLoop(ForLoop stmt)

buildIf

protected DFAGraph buildIf(IfStatement stmt)

buildSwitch

protected DFAGraph buildSwitch(SwitchStatement stmt)

buildWhile

protected DFAGraph buildWhile(WhileLoop stmt)

removable_node

protected boolean removable_node(DFANode node)

reduce

protected void reduce()

isUnsafeExpansion

protected static boolean isUnsafeExpansion(Traversable t)

getSafeEvaluation

protected static java.util.List getSafeEvaluation(Traversable t)

expandExpression

protected static DFAGraph expandExpression(DFANode node)

expandAssignment

protected static void expandAssignment(CompoundStatement stmts,
                                       AssignmentExpression e)

expandConditional

protected static void expandConditional(CompoundStatement stmts,
                                        ConditionalExpression e)

expandUnary

protected static void expandUnary(CompoundStatement stmts,
                                  UnaryExpression e)

removeRedundancy

protected static void removeRedundancy(CompoundStatement stmts)

expandExpression

protected static void expandExpression(CompoundStatement stmts,
                                       Traversable t)