org.jikesrvm.compilers.opt.controlflow

Class DominatorTree

java.lang.Object

org.jikesrvm.compilers.opt.util.Tree

org.jikesrvm.compilers.opt.controlflow.DominatorTree

public class DominatorTree
extends Tree

This class provides the abstraction of a dominator tree

TODO: we do not support IRs with exception handlers.

Field Summary

Fields

Modifier and Type	Field and Description
private DominatorTreeNode[]	dominatorInfoMap A structure used to quickly index into the DominatorVertex tree
private boolean	forward true if we are computing regular dominators, false for post-dominators
private IR	ir The governing IR

Constructor Summary

Constructors

Constructor and Description
DominatorTree(IR ir, boolean forward) Build a dominator tree from an IR.

Method Summary

Modifier and Type	Method and Description
private void	addNode(BasicBlock b) Creates dominator tree nodes for the passed block and adds them to the map.
BasicBlock	deepestCommonAncestor(BasicBlock a, BasicBlock b) Return the deepest common dominance ancestor of blocks a and b
int	depth(BasicBlock b) Return the distance from the root of the dominator tree to a given basic block
boolean	dominates(BasicBlock master, BasicBlock slave) Does basic block number "master" dominate basic block number "slave"?
boolean	dominates(int b, BitVector bits) Does basic block number b dominate all basic blocks in a set?
boolean	dominates(int master, int slave) Does basic block number "master" dominate basic block number "slave"?
Enumeration<TreeNode>	getChildren(BasicBlock bb) Enumerate the children of the vertex corresponding to a basic block
BitVector	getDominanceFrontier(BasicBlock bb) Return the (already calculated) dominance frontier for a basic block
BitVector	getDominanceFrontier(int number) Return the (already calculated) dominance frontier for a basic block
private BasicBlock	getFirstNode() Get the first node, either entry or exit depending on which way we are viewing the graph
BasicBlock	getParent(BasicBlock bb) Return the parent of the vertex corresponding to a basic block
static void	perform(IR ir, boolean forward) Build a dominator tree from an IR.

Methods inherited from class org.jikesrvm.compilers.opt.util.Tree

elements, getBottomUpEnumerator, getRoot, getTopDownEnumerator, isEmpty, numberOfNodes, setRoot, toString

Methods inherited from class java.lang.Object

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

Field Detail

forward

private final boolean forward

true if we are computing regular dominators, false for post-dominators

ir

private final IR ir

The governing IR

dominatorInfoMap

private final DominatorTreeNode[] dominatorInfoMap

A structure used to quickly index into the DominatorVertex tree

Constructor Detail

DominatorTree

public DominatorTree(IR ir,
                     boolean forward)

Build a dominator tree from an IR. NOTE: the dominator information MUST be computed BEFORE calling this constructor!

Parameters:

ir - the governing IR

forward - are we building regular dominators or post-dominators?

Method Detail

perform

public static void perform(IR ir,
                           boolean forward)

Build a dominator tree from an IR. NOTE: the dominator information MUST be computed BEFORE calling this method!

Parameters:

ir - the governing IR

forward - are we building regular dominators or post-dominators?

getFirstNode

private BasicBlock getFirstNode()

Get the first node, either entry or exit depending on which way we are viewing the graph

Returns:

the entry node or exit node

getChildren

public Enumeration<TreeNode> getChildren(BasicBlock bb)

Enumerate the children of the vertex corresponding to a basic block

Parameters:

bb - the basic block

Returns:

an Enumeration of bb's children

getParent

public BasicBlock getParent(BasicBlock bb)

Return the parent of the vertex corresponding to a basic block

Parameters:

bb - the basic block

Returns:

bb's parent

getDominanceFrontier

public BitVector getDominanceFrontier(BasicBlock bb)

Return the (already calculated) dominance frontier for a basic block

Parameters:

bb - the basic block

Returns:

a BitVector representing the dominance frontier

getDominanceFrontier

public BitVector getDominanceFrontier(int number)

Return the (already calculated) dominance frontier for a basic block

Parameters:

number - the number of the basic block

Returns:

a BitVector representing the dominance frontier

dominates

public boolean dominates(int b,
                         BitVector bits)

Does basic block number b dominate all basic blocks in a set?

Parameters:

b - the number of the basic block to test

bits - BitVector representation of the set of basic blocks to test

Returns:

true or false

dominates

public boolean dominates(int master,
                         int slave)

Does basic block number "master" dominate basic block number "slave"?

Parameters:

master - the number of the proposed "master" basic block

slave - the number of the proposed "slave block

Returns:

"master dominates slave"

dominates

public boolean dominates(BasicBlock master,
                         BasicBlock slave)

Does basic block number "master" dominate basic block number "slave"?

Parameters:

master - the number of the proposed "master" basic block

slave - the number of the proposed "slave block

Returns:

"master dominates slave"

addNode

private void addNode(BasicBlock b)

Creates dominator tree nodes for the passed block and adds them to the map.

Parameters:

b - the basic block

depth

public int depth(BasicBlock b)

Return the distance from the root of the dominator tree to a given basic block

Parameters:

b - the basic block in question

Returns:

b's depth

deepestCommonAncestor

public BasicBlock deepestCommonAncestor(BasicBlock a,
                                        BasicBlock b)

Return the deepest common dominance ancestor of blocks a and b

Parameters:

a - The first basic block

b - The second basic block

Returns:

the deepest common dominance ancestor of blocks a and b