org.apache.flex.abc.graph.algorithms

Class DominatorTree

java.lang.Object

org.apache.flex.abc.graph.algorithms.DominatorTree

public class DominatorTree
extends Object

An implementation of the O(n log n) Lengauer-Tarjan algorithm for building the dominator tree of a flowgraph.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DominatorTree.Multimap<T> Multimap maps a key to a set of values.

Constructor Summary

Constructors

Constructor and Description
DominatorTree(Collection<? extends IBasicBlock> roots) Construct a DominatorTree from a collection of "roots."
DominatorTree(IBasicBlock root) Construct a DominatorTree from a root.

Method Summary

Methods

Modifier and Type	Method and Description
DominatorTree.Multimap<IBasicBlock>	getDominanceFrontiers() Compute and/or fetch the dominance frontiers as a Multimap.
DominatorTree.Multimap<IBasicBlock>	getDominatorTree() Compute and/or fetch the dominator tree as a Multimap.
Map<IBasicBlock,IBasicBlock>	getIdoms() Create and/or fetch the map of immediate dominators.
Iterable<IBasicBlock>	reverseTopologicalTraversal() Create and/or fetch a reverse topological traversal of the dominator tree, such that for every node, node appears before idom(node).
List<IBasicBlock>	topologicalTraversal() Create and/or fetch a topological traversal of the dominator tree, such that for every node, idom(node) appears before node.

Methods inherited from class java.lang.Object

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

Constructor Detail

DominatorTree

public DominatorTree(IBasicBlock root)

Construct a DominatorTree from a root.

Parameters:

root - the root of the graph.

DominatorTree

public DominatorTree(Collection<? extends IBasicBlock> roots)

Construct a DominatorTree from a collection of "roots."

Parameters:

roots - the collection of roots; one of these is the true root of the flowgraph, the others are exception handlers that would otherwise be unreachable.

Method Detail

getIdoms

public Map<IBasicBlock,IBasicBlock> getIdoms()

Create and/or fetch the map of immediate dominators.

Returns:

the map from each block to its immediate dominator (if it has one).

getDominatorTree

public DominatorTree.Multimap<IBasicBlock> getDominatorTree()

Compute and/or fetch the dominator tree as a Multimap.

Returns:

the dominator tree.

getDominanceFrontiers

public DominatorTree.Multimap<IBasicBlock> getDominanceFrontiers()

Compute and/or fetch the dominance frontiers as a Multimap.

Returns:

a Multimap where the set of nodes mapped to each key node is the set of nodes in the key node's dominance frontier.

topologicalTraversal

public List<IBasicBlock> topologicalTraversal()

Create and/or fetch a topological traversal of the dominator tree, such that for every node, idom(node) appears before node.

Returns:

the topological traversal of the dominator tree, as an immutable List.

reverseTopologicalTraversal

public Iterable<IBasicBlock> reverseTopologicalTraversal()

Create and/or fetch a reverse topological traversal of the dominator tree, such that for every node, node appears before idom(node).

Returns:

a reverse topological traversal of the dominator tree, as an immutable List.