| soot.toolkits.graph |
Toolkit to produce and manipulate various types of control flow
graphs. While the CFG classes do not impose restrictions on the types
of graph nodes, the nodes are typically instances of {@link Unit}
or {@link Block}. The latter corresponds to basic blocks of
Units. Some of the CFG classes include the control
flow corresponding to thrown exceptions, while others
abstract away exception-related edges.
|
| Java Source File Name | Type | Comment |
| ArrayRefBlockGraph.java | Class | A CFG where the nodes are
Block instances, and where
Unit s which include array references start new blocks. |
| Block.java | Class | Represents BasicBlocks that partition
a method body. |
| BlockGraph.java | Class |
Represents the control flow graph of a
Body at the basic
block level. |
| BlockGraphConverter.java | Class | This utility class can convert any BlockGraph to a single-headed
and single-tailed graph by inserting appropriate Start or Stop
nodes. |
| BriefBlockGraph.java | Class | Represents a CFG for a
Body where the nodes are
Block s and edges are derived from control flow. |
| BriefUnitGraph.java | Class | Represents a CFG where the nodes are Unit instances, and
where no edges are included to account for control flow
associated with exceptions. |
| ClassicCompleteBlockGraph.java | Class | Represents a CFG where the nodes are
Block s and the
edges are derived from control flow. |
| ClassicCompleteUnitGraph.java | Class | Represents a CFG for a Body instance where the nodes are
Unit instances, and where edges are a conservative
indication of unexceptional and exceptional control
flow.
ClassicCompleteUnitGraph attempts to duplicate the
results that would have been produced by Soot's
CompleteUnitGraph in releases up to Soot 2.1.0 (the
one known discrepancy is that the 2.1.0
CompleteUnitGraph would include two edges joining one
node to another
Unit s if the first node both branched to and fell through to
the second). |
| CompleteBlockGraph.java | Class | Represents a CFG for a
Body instance where the nodes
are
Block instances, and where control flow associated with
exceptions is taken into account. |
| CompleteUnitGraph.java | Class | Represents a CFG for a
Body instance where the nodes
are
soot.Unit instances, and where control flow
associated with exceptions is taken into account. |
| CytronDominanceFrontier.java | Class | Class to compute the DominanceFrontier using Cytron's celebrated efficient
algorithm. |
| DirectedGraph.java | Interface | Defines the notion of a directed graph. |
| DominanceFrontier.java | Interface | Interface to compute and/or store the dominance frontiers of nodes
in a dominator tree. |
| DominatorAnalysis.java | Class | |
| DominatorNode.java | Class | Represents a dominator node in DominatorTree. |
| DominatorsFinder.java | Interface | General interface for a dominators analysis. |
| DominatorTree.java | Class | Constructs a dominator tree structure from the given
DominatorsFinder. |
| DominatorTreeAdapter.java | Class | This adapter provides a DirectedGraph interface to DominatorTree.
This might be useful if e.g. |
| ExceptionalBlockGraph.java | Class | Represents a CFG where the nodes are
Block s and the
edges are derived from control flow. |
| ExceptionalGraph.java | Interface | |
| ExceptionalUnitGraph.java | Class | Represents a control flow graph for a
Body instance
where the nodes are
Unit instances, and where control flow
associated with exceptions is taken into account.
To describe precisely the circumstances under which exceptional
edges are added to the graph, we need to distinguish the
exceptions thrown explicitly by a throw instruction
from the exceptions which are thrown implicitly by the VM to
signal an error it encounters in the course of executing
an instruction, which need not be a throw.
For every
ThrowInst or
ThrowStmt Unit which may explicitly throw an exception that
would be caught by a
Trap in the Body, there
will be an edge from the throw Unit to
the Trap handler's first Unit.
For every Unit which may implicitly throw an
exception that could be caught by a Trap in the
Body, there will be an edge from each of the
excepting Unit's predecessors to the
Trap handler's first Unit (since any of
those predecessors may have been the last Unit to
complete execution before the handler starts execution). |
| GraphComparer.java | Class | |
| HashMutableDirectedGraph.java | Class | HashMap based implementation of a MutableBlockGraph. |
| HashMutableEdgeLabelledDirectedGraph.java | Class | HashMap based implementation of a MutableEdgeLabelledDirectedGraph. |
| HashReversibleGraph.java | Class | |
| InverseGraph.java | Class | An inverted graph of a directed graph. |
| LoopNestTree.java | Class | A loop nesting tree, implemented as a tree-map. |
| MemoryEfficientGraph.java | Class | A memory efficient version of HashMutableDirectedGraph, in the sense
that throw-away objects passed as arguments will not be kept in the
process of adding edges. |
| MHGDominatorsFinder.java | Class | Calculate dominators for basic blocks.
Uses the algorithm contained in Dragon book, pg. |
| MHGPostDominatorsFinder.java | Class | Post-dominators finder for multi-headed graph.
The dominators returned by this finder are postdominators,
so e.g. |
| MutableDirectedGraph.java | Interface | Defines a DirectedGraph which is modifiable. |
| MutableEdgeLabelledDirectedGraph.java | Interface | Defines a DirectedGraph which is modifiable and associates
a label object with every edge. |
| Orderer.java | Interface | An orderer builds an order on a directed, not necessarily acyclic, graph. |
| PostDominatorAnalysis.java | Class | |
| PseudoTopologicalOrderer.java | Class | Orders in pseudo-topological order, the nodes of a DirectedGraph instance. |
| ReversePseudoTopologicalOrderer.java | Class | Convenience class which returns a PseudoTopologicalOrderer with the mReversed
flag set by default. |
| ReversibleGraph.java | Interface | DirectedGraph which can be reversed and re-reversed. |
| SimpleDominatorsFinder.java | Class | Wrapper class for a simple dominators analysis based on a simple
flow analysis algorithm. |
| SlowPseudoTopologicalOrderer.java | Class | Provide the pseudo topological order of a graph's nodes. |
| StronglyConnectedComponents.java | Class | Identifies and provides an interface to query the strongly-connected
components of DirectedGraph instances. |
| TrapUnitGraph.java | Class |
Represents a CFG for a
Body instance where the nodes are
Unit instances, and where, in additional to unexceptional
control flow edges, edges are added from every trapped
Unit to the
Trap 's handler Unit, regardless
of whether the trapped Units may actually throw the
exception caught by the Trap.
There are three distinctions between the exceptional edges added
in TrapUnitGraph and the exceptional edges added in
ExceptionalUnitGraph :
-
In
ExceptionalUnitGraph, the edges to
Traps are associated with Units which
may actually throw an exception which the Trap
catches (according to the
soot.toolkits.exceptions.ThrowAnalysis ThrowAnalysis used in the
construction of the graph). |
| UnitGraph.java | Class | |
| ZonedBlockGraph.java | Class | A CFG where the nodes are
Block instances, and where
exception boundaries are taken into account when finding the
Blocks for the provided Body. |