public abstract class BlockGraph extends java.lang.Object implements DirectedGraph<Block>
Represents the control flow graph of a Body at the basic block level.
Each node of the graph is a Block while the edges represent the flow
of control from one basic block to the next.
This is an abstract base class for different variants of BlockGraph,
where the variants differ in how they analyze the control flow between
individual units (represented by passing different variants of
UnitGraph to the BlockGraph constructor) and in how they
identify block leaders (represented by overriding BlockGraph's
definition of computeLeaders().
| Modifier and Type | Field and Description |
|---|---|
protected java.util.List<Block> |
mBlocks |
protected Body |
mBody |
protected java.util.List<Block> |
mHeads |
protected java.util.List<Block> |
mTails |
protected Chain<Unit> |
mUnits |
| Modifier | Constructor and Description |
|---|---|
protected |
BlockGraph(UnitGraph unitGraph)
Create a
BlockGraph representing at the basic block level
the control flow specified, at the Unit level, by a given
UnitGraph. |
| Modifier and Type | Method and Description |
|---|---|
protected java.util.Map<Unit,Block> |
buildBlocks(java.util.Set<Unit> leaders,
UnitGraph unitGraph)
A utility method that does most of the work of constructing basic blocks,
once the set of block leaders has been determined, and which designates
the heads and tails of the graph.
|
protected java.util.Set<Unit> |
computeLeaders(UnitGraph unitGraph)
|
java.util.List<Block> |
getBlocks()
Returns a list of the Blocks composing this graph.
|
Body |
getBody()
Returns the
Body this BlockGraph is derived from. |
java.util.List<Block> |
getHeads()
Returns a list of entry points for this graph.
|
java.util.List<Block> |
getPredsOf(Block b)
Returns a list of predecessors for the given node in the graph.
|
java.util.List<Block> |
getSuccsOf(Block b)
Returns a list of successors for the given node in the graph.
|
java.util.List<Block> |
getTails()
Returns a list of exit points for this graph.
|
java.util.Iterator<Block> |
iterator()
Returns an iterator for the nodes in this graph.
|
int |
size()
Returns the node count for this graph.
|
java.lang.String |
toString() |
protected Body mBody
protected java.util.List<Block> mBlocks
protected java.util.List<Block> mHeads
protected java.util.List<Block> mTails
protected java.util.Set<Unit> computeLeaders(UnitGraph unitGraph)
Utility method for computing the basic block leaders for a Body,
given its UnitGraph (i.e., the instructions which begin new basic
blocks).
This implementation designates as basic block leaders :
Unit which has zero predecessors (e.g. the
Unit following a return or unconditional branch) or more
than one predecessor (e.g. a merge point).Units which are the target of any branch (even if they
have no other predecessors and the branch has no other successors, which
is possible for the targets of unconditional branches or degenerate
conditional branches which both branch and fall through to the same
Unit).Unit which has more than one
successor (this includes the successors of Units which may
throw an exception that gets caught within the Body, as well
the successors of conditional branches).Unit in any Trap handler.
(Strictly speaking, if unitGraph were a
ExceptionalUnitGraph that included only a single
unexceptional predecessor for some handler—because no trapped unit
could possibly throw the exception that the handler catches, while the
code preceding the handler fell through to the handler's code—then
you could merge the handler into the predecessor's basic block; but such
situations occur only in carefully contrived bytecode.)
unitGraph - is the Unit-level CFG which is to be split into
basic blocks.Set of Units in unitGraph which
are block leaders.protected java.util.Map<Unit,Block> buildBlocks(java.util.Set<Unit> leaders, UnitGraph unitGraph)
A utility method that does most of the work of constructing basic blocks, once the set of block leaders has been determined, and which designates the heads and tails of the graph.
BlockGraph provides an implementation of
buildBlocks() which splits the Units in
unitGraph so that each Unit in the passed set
of block leaders is the first unit in a block. It defines as heads the
blocks which begin with Units which are heads in
unitGraph, and defines as tails the blocks which end with
Units which are tails in unitGraph. Subclasses
might override this behavior.
leaders - Contains Units which are to be block leaders.unitGraph - Provides information about the predecessors and successors of
each Unit in the Body, for
determining the predecessors and successors of each created
Block.Map from Units which begin or end a block to
the block which contains them.public Body getBody()
Body this BlockGraph is derived from.Body this BlockGraph is derived from.public java.util.List<Block> getBlocks()
Blockpublic java.lang.String toString()
toString in class java.lang.Objectpublic java.util.List<Block> getHeads()
DirectedGraphgetHeads in interface DirectedGraph<Block>public java.util.List<Block> getTails()
DirectedGraphgetTails in interface DirectedGraph<Block>public java.util.List<Block> getPredsOf(Block b)
DirectedGraphgetPredsOf in interface DirectedGraph<Block>public java.util.List<Block> getSuccsOf(Block b)
DirectedGraphgetSuccsOf in interface DirectedGraph<Block>public int size()
DirectedGraphsize in interface DirectedGraph<Block>public java.util.Iterator<Block> iterator()
DirectedGraphiterator in interface java.lang.Iterable<Block>iterator in interface DirectedGraph<Block>