org.jikesrvm.compilers.opt.ir
Class ControlFlowGraph
java.lang.Object
org.jikesrvm.compilers.opt.util.SpaceEffGraph
org.jikesrvm.compilers.opt.ir.ControlFlowGraph
- All Implemented Interfaces:
- Graph, TopSortInterface
public final class ControlFlowGraph
- extends SpaceEffGraph
The Factored Control Flow Graph (FCFG).
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.
- See Also:
BasicBlock,
IR
| Methods inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraph |
addGraphEdge, addGraphEdge, addGraphNode, addRootNode, addTopSortNode, allocateNodeNumber, buildTopSort, clearDFS, enumerateNodes, firstNode, initTopSort, isTopSorted, lastNode, numberOfNodes, printDepthFirst, removeGraphNode, resetTopSorted, rootNodes, setFirstNode, setLastNode, setNumberOfNodes, setTopSorted, topSort, topSortOrder, toString |
_exitNode
private final BasicBlock _exitNode
- The distinguished exit node of the FCFG
ControlFlowGraph
public ControlFlowGraph(int number)
- Parameters:
number - starting value for assigning node numbers
entry
public BasicBlock entry()
- Return the entry node of the FCFG. All reachable nodes
can be found by doing a forward traversal from this node.
- Returns:
- the entry node of the FCFG
exit
public BasicBlock exit()
- Return the "exit" node of the FCFG. In a perfect world,
we'd have the invariant that all nodes that are reachable in a
forward traversal from cfgEntry() are exactly the same set of nodes
as those that are reachable from cfgExit() via a reverse traversal,
but that's currently not the case. Not all forward reachable nodes can
be found by going backwards from exit. The issue is infinite loops
(loops without normal exits).
- Returns:
- the exit node of the FCFG
firstInCodeOrder
public BasicBlock firstInCodeOrder()
- Return the first basic block with respect to
the current code linearization order.
- Returns:
- the first basic block in the code order
lastInCodeOrder
public BasicBlock lastInCodeOrder()
- Return the last basic block with respect to
the current code linearization order.
- Returns:
- the last basic block in the code order
startNode
public SortedGraphNode startNode(boolean forward)
- Return the node to start with for a topological traversal
of the FCFG.
Override
SpaceEffGraph.startNode(boolean)
to use entry and exit; we want topological traversals to be with
respect to FCFG edges not the code linearization order
- Specified by:
startNode in interface TopSortInterface- Overrides:
startNode in class SpaceEffGraph
- Parameters:
forward - true for forward traversal, false for reverse
- Returns:
- the node to use as the start of a topological traversal
compactNodeNumbering
public void compactNodeNumbering()
- Densely number (0...n) all nodes in the FCFG.
Override
SpaceEffGraph.compactNodeNumbering() to also
number the exit node.
- Specified by:
compactNodeNumbering in interface Graph- Overrides:
compactNodeNumbering in class SpaceEffGraph
buildRevTopSort
public SortedGraphNode buildRevTopSort()
- Builds the reverse topological order, i.e., the topsort order on the
reverse graph. (This is not the same as reversing the topsort order
of the forward graph.)
- Overrides:
buildRevTopSort in class SpaceEffGraph
- Returns:
- the first node in the reverse topological ordering
linkToExit
public void linkToExit(BasicBlock bb)
- Add an FCFG edge from the given basic block to the exit node.
- Parameters:
bb - basic block to link to the exit
removeFromCFGAndCodeOrder
public void removeFromCFGAndCodeOrder(BasicBlock bb)
- Remove a basic block from both the CFG and code ordering
- Parameters:
bb - the block to remove
removeFromCFG
public void removeFromCFG(BasicBlock bb)
- Remove a basic block from the FCFG, leaving the code ordering unchanged.
- Parameters:
bb - the block to remove
removeFromCodeOrder
public void removeFromCodeOrder(BasicBlock bb)
- Remove a basic block from the code ordering,
leaving the FCFG unchanged.
- Parameters:
bb - the block to remove
insertAfterInCodeOrder
public 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.
If necessary, _lastNode is updated.
No impact on FCFG edges.
- Parameters:
old - a block currently in the code orderingtoAdd - a block to add after old in the code ordering
insertBeforeInCodeOrder
public 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.
If necessary, _firstNode is updated.
No impact on FCFG edges.
- Parameters:
old - a block currently in the code orderingtoAdd - a block to add before old in the code ordering
addLastInCodeOrder
public void addLastInCodeOrder(BasicBlock bb)
- Add a block not currently in the code ordering to the end of the
code ordering.
No impact on FCFG edges.
- Parameters:
bb - the block to add to the end of the code ordering
linkInCodeOrder
public void linkInCodeOrder(BasicBlock bb1,
BasicBlock bb2)
- Make BB2 follow BB1 in the code ordering.
If _lastNode == BB1, then update _lastNode appropriately
No impact on FCFG edges.
- Parameters:
bb1 - a basic blockbb2 - the basic block to follow bb1 in the code ordering
breakCodeOrder
public 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).
No impact on FCFG edges.
- Parameters:
bb1 - the first blockbb2 - the second block
clearCodeOrder
public void clearCodeOrder()
- Clear the code ordering information for the CFG.
NOTE: This method should only be called as part of a
whole scale recomputation of the code order, for example
by ReorderingPhase
basicBlocks
public Enumeration<BasicBlock> basicBlocks()