public final class ControlFlowGraph extends SpaceEffGraph
Like a standard control flow graph (CFG), the FCFG is composed
of basic blocks which in turn contain
instructions. The critical difference between
a FCFG and a CFG is in the definition of basic blocks. In the FCFG,
a Potentially Excepting Instruction (PEI) does not necessarily end its
basic block. Therefore, although instructions within a FCFG basic block
have the expected dominance relationships, they do not have the
same post-dominance relationships as they would under the traditional
basic block formulation used in a CFG.
We chose to use an FCFG because doing so significantly reduces the
number of basic blocks and control flow graph edges, thus reducing
the time and space costs of representing the FCFG and also
increasing the effectiveness of local (within a single basic block)
analysis. However, using an FCFG does complicate flow-sensitive
global analaysis. Many analyses can be easily extended to
work on the FCFG. For those analyses that cannot, we provide utilities
(IR.unfactor(), BasicBlock.unfactor(IR))
to effectively convert the FCFG into a CFG.
For a more detailed description of the FCFG and its implications for
program analysis see the PASTE'99 paper by Choi et al.
Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs
The nodes in the FCFG are components in two distinct
orderings, the "main" one is the control flow relationship
in which edges represent flow of control.
The secondary ordering is a linearization of the blocks
which represents the ordering of instructions in the generated code.
Both of these relationships are represented using the fields inherited
from SpaceEffGraphNode.
The control flow edges are the primary relationship and are encoded by
In and Out relations of
SpaceEffGraphNode and the entry() and exit()
functions of ControlFlowGraph.
The linear order is secondary and is represented by the order of the
nodes in the doubly linked list (SpaceEffGraphNode.next and
SpaceEffGraphNode.prev) and the functions
(firstInCodeOrder(), lastInCodeOrder())
of ControlFlowGraph.
Utility functions are provided here and in SpaceEffGraphNode
to manipulate these orderings.
Note: Clients that add or remove nodes must call compactNodeNumbering()
after they are done with the modifications to ensure that subsequent compiler phases
can use the node numbering to index lookaside data structures for basic blocks.
BasicBlock,
IR| Modifier and Type | Class and Description |
|---|---|
private static class |
ControlFlowGraph.NodeEnumeration<T> |
| Modifier and Type | Field and Description |
|---|---|
private BasicBlock |
_exitNode
The distinguished exit node of the FCFG
|
_firstNode, _lastNode, backwardTopSorted, forwardTopSorted, numberOfNodes| Constructor and Description |
|---|
ControlFlowGraph(int number) |
| Modifier and Type | Method and Description |
|---|---|
void |
addLastInCodeOrder(BasicBlock bb)
Add a block not currently in the code ordering to the end of the
code ordering.
|
Enumeration<BasicBlock> |
basicBlocks() |
void |
breakCodeOrder(BasicBlock bb1,
BasicBlock bb2)
Create a break in the code order between bb1 and bb2
(bb1 and bb2 must be currently adjacent in the code order).
|
SortedGraphNode |
buildRevTopSort()
Builds the reverse topological order, i.e., the topsort order on the
reverse graph.
|
void |
clearCodeOrder()
Clear the code ordering information for the CFG.
|
void |
compactNodeNumbering()
Densely numbers (0...n) all nodes in the FCFG.
|
BasicBlock |
entry()
Return the entry node of the FCFG.
|
BasicBlock |
exit()
Return the "exit" node of the FCFG.
|
BasicBlock |
firstInCodeOrder()
Return the first basic block with respect to
the current code linearization order.
|
void |
insertAfterInCodeOrder(BasicBlock old,
BasicBlock toAdd)
Insert a block 'toAdd' not currently in the code ordering after
a block 'old' that is currently in the code ordering.
|
void |
insertBeforeInCodeOrder(BasicBlock old,
BasicBlock toAdd)
Insert a block 'toAdd' not currently in the code ordering before
a block 'old' that is currently in the code ordering.
|
BasicBlock |
lastInCodeOrder()
Return the last basic block with respect to
the current code linearization order.
|
void |
linkInCodeOrder(BasicBlock bb1,
BasicBlock bb2)
Make BB2 follow BB1 in the code ordering.
|
void |
linkToExit(BasicBlock bb)
Add an FCFG edge from the given basic block to the exit node.
|
void |
removeFromCFG(BasicBlock bb)
Remove a basic block from the FCFG, leaving the code ordering unchanged.
|
void |
removeFromCFGAndCodeOrder(BasicBlock bb)
Remove a basic block from both the CFG and code ordering
|
void |
removeFromCodeOrder(BasicBlock bb)
Remove a basic block from the code ordering,
leaving the FCFG unchanged.
|
SortedGraphNode |
startNode(boolean forward)
Return the node to start with for a topological traversal
of the FCFG.
|
addGraphEdge, addGraphEdge, addGraphNode, addRootNode, addTopSortNode, allocateNodeNumber, buildTopSort, clearDFS, enumerateNodes, firstNode, initTopSort, isTopSorted, lastNode, numberOfNodes, printDepthFirst, removeGraphNode, resetTopSorted, rootNodes, setFirstNode, setLastNode, setNumberOfNodes, setTopSorted, topSort, topSortOrder, toStringprivate final BasicBlock _exitNode
public ControlFlowGraph(int number)
number - starting value for assigning node numberspublic BasicBlock entry()
public BasicBlock exit()
public BasicBlock firstInCodeOrder()
public BasicBlock lastInCodeOrder()
public SortedGraphNode startNode(boolean forward)
SpaceEffGraph.startNode(boolean)
to use entry and exit; we want topological traversals to be with
respect to FCFG edges not the code linearization orderstartNode in interface TopSortInterfacestartNode in class SpaceEffGraphforward - true for forward traversal, false for reversepublic void compactNodeNumbering()
Note: clients must call this method after they are done with adding or removing nodes. This allows subsequent phases to save additional information about BasicBlocks in arrays by using the node number as index.
This method overrides SpaceEffGraph.compactNodeNumbering() to also
number the exit node.
compactNodeNumbering in interface GraphcompactNodeNumbering in class SpaceEffGraphpublic SortedGraphNode buildRevTopSort()
buildRevTopSort in class SpaceEffGraphpublic void linkToExit(BasicBlock bb)
bb - basic block to link to the exitpublic void removeFromCFGAndCodeOrder(BasicBlock bb)
bb - the block to removepublic void removeFromCFG(BasicBlock bb)
bb - the block to removepublic void removeFromCodeOrder(BasicBlock bb)
bb - the block to removepublic void insertAfterInCodeOrder(BasicBlock old, BasicBlock toAdd)
old - a block currently in the code orderingtoAdd - a block to add after old in the code orderingpublic void insertBeforeInCodeOrder(BasicBlock old, BasicBlock toAdd)
old - a block currently in the code orderingtoAdd - a block to add before old in the code orderingpublic void addLastInCodeOrder(BasicBlock bb)
bb - the block to add to the end of the code orderingpublic void linkInCodeOrder(BasicBlock bb1, BasicBlock bb2)
bb1 - a basic blockbb2 - the basic block to follow bb1 in the code orderingpublic void breakCodeOrder(BasicBlock bb1, BasicBlock bb2)
bb1 - the first blockbb2 - the second blockpublic void clearCodeOrder()
NOTE: This method should only be called as part of a whole scale recomputation of the code order, for example by ReorderingPhase
public Enumeration<BasicBlock> basicBlocks()