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.

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 DominatorTreeNode[] dominatorInfoMap

A structure used to quickly index into the DominatorVertex tree

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?

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! We assume the scratch object of each basic block contains the LTDominatorInfo object holding this information.

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