org.jikesrvm.compilers.opt.controlflow

Class DominatorTreeNode

java.lang.Object

org.jikesrvm.compilers.opt.util.TreeNode

org.jikesrvm.compilers.opt.controlflow.DominatorTreeNode

public class DominatorTreeNode
extends TreeNode

This class implements a node in the dominator tree.

TODO: we do not support IRs with exception handlers!!

Field Summary

Fields

Modifier and Type	Field and Description
private BasicBlock	block the basic block this node represents
private int	depth distance from the root of the dominator tree, lazily initialized (-1 => not initialized)
private BitVector	dominanceFrontier representation of the dominance frontier for this node
(package private) BitVector	dominators the cache to hold the set of nodes that dominate this one.
private int	high upper bound of dominated nodes range
private int	low lower bound of dominated nodes range

Constructor Summary

Constructors

Constructor and Description
DominatorTreeNode(BasicBlock block) Construct a dominator tree node for a given basic block.

Method Summary

Modifier and Type	Method and Description
(package private) boolean	_isDominatedBy(DominatorTreeNode master) This method returns true if the passed node dominates this node
(package private) Enumeration<BasicBlock>	domFrontierEnumerator(IR ir) Enumerate the basic blocks in the dominance frontier for this node.
(package private) String	dominanceFrontierString() Return a string representation of the dominance frontier for this node.
(package private) BitVector	dominators(IR ir) This method returns the set of blocks that dominates the passed block, i.e., it answers the question "Who dominates me?"
BasicBlock	getBlock() Get the basic block for this dominator tree node
(package private) int	getDepth() Return the distance of this node from the root of the dominator tree.
(package private) BitVector	getDominanceFrontier() Return a bit set representing the dominance frontier for this node
private void	initializeRanges()
private int	initializeRanges(int i)
(package private) boolean	isDominatedBy(DominatorTreeNode master) This method returns true if the passed node dominates this node
(package private) void	setDominanceFrontier(BitVector set) Set a bit set representing the dominance frontier for this node
String	toString() String-i-fies the node

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

addChild, clear, getChildren, getLeftChild, getParent, getRightSibling

Methods inherited from class java.lang.Object

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

Field Detail

block

private final BasicBlock block

the basic block this node represents

depth

private int depth

distance from the root of the dominator tree, lazily initialized (-1 => not initialized)

dominanceFrontier

private BitVector dominanceFrontier

representation of the dominance frontier for this node

dominators

BitVector dominators

the cache to hold the set of nodes that dominate this one. This is computed on demand by walking up the tree.

low

private int low

lower bound of dominated nodes range

high

private int high

upper bound of dominated nodes range

Constructor Detail

DominatorTreeNode

DominatorTreeNode(BasicBlock block)

Construct a dominator tree node for a given basic block.

Parameters:

block - the basic block

Method Detail

getBlock

public BasicBlock getBlock()

Get the basic block for this dominator tree node

Returns:

the basic block

getDepth

int getDepth()

Return the distance of this node from the root of the dominator tree.

Returns:

the distance of this node from the root of the dominator tree.

getDominanceFrontier

BitVector getDominanceFrontier()

Return a bit set representing the dominance frontier for this node

Returns:

a bit set representing the dominance frontier for this node

setDominanceFrontier

void setDominanceFrontier(BitVector set)

Set a bit set representing the dominance frontier for this node

Parameters:

set - the bit set

dominanceFrontierString

String dominanceFrontierString()

Return a string representation of the dominance frontier for this node.

Returns:

a string representation of the dominance frontier for this node

dominators

BitVector dominators(IR ir)

This method returns the set of blocks that dominates the passed block, i.e., it answers the question "Who dominates me?"

Parameters:

ir - the governing IR

Returns:

a BitVector containing those blocks that dominate me

_isDominatedBy

boolean _isDominatedBy(DominatorTreeNode master)

This method returns true if the passed node dominates this node

Parameters:

master - the proposed dominating node

Returns:

whether the passed node dominates me

isDominatedBy

boolean isDominatedBy(DominatorTreeNode master)

This method returns true if the passed node dominates this node

Parameters:

master - the proposed dominating node

Returns:

whether the passed node dominates me

initializeRanges

private void initializeRanges()

initializeRanges

private int initializeRanges(int i)

domFrontierEnumerator

Enumeration<BasicBlock> domFrontierEnumerator(IR ir)

Enumerate the basic blocks in the dominance frontier for this node.

Parameters:

ir - the governing IR

Returns:

an enumeration of the basic blocks in the dominance frontier for this node.

toString

public final String toString()

String-i-fies the node

Overrides:

toString in class Object

Returns:

the node as a string