org.jikesrvm.compilers.opt.controlflow
Class LTDominators

java.lang.Object
  org.jikesrvm.compilers.opt.util.Stack<BasicBlock>
      org.jikesrvm.compilers.opt.controlflow.LTDominators

All Implemented Interfaces:

Iterable<BasicBlock>

public class LTDominators
extends Stack<BasicBlock>

Calculate dominators using Langauer and Tarjan's fastest algorithm. TOPLAS 1(1), July 1979. This implementation uses path compression and results in a O(e * alpha(e,n)) complexity, where e is the number of edges in the CFG and n is the number of nodes.

Sources: TOPLAS article, Muchnick book

The current implementation (4/25/00) does not include the EXIT node in any solution despite the fact that it is part of the CFG (it has incoming edges). This is to be compatible with the old code.

DEBUG

static final boolean DEBUG

See Also:

Constant Field Values

forward

private final boolean forward

Indicates whether we perform the algorithm over the CFG or the reverse CFG, i.e., whether we are computing dominators or post-dominators.

DFSCounter

protected int DFSCounter

a counter for assigning DFS numbers

vertex

private BasicBlock[] vertex

a mapping from DFS number to their basic blocks

cfg

private final ControlFlowGraph cfg

a convenient place to locate the cfg to avoid passing it internally

LTDominators

LTDominators(IR ir,
             boolean forward)

The constructor, called by the perform method

Parameters:

ir -

forward - Should we compute regular dominators, or post-dominators?

perform

public static void perform(IR ir,
                           boolean forward,
                           boolean unfactor)

The entry point for this phase

Parameters:

ir - the IR

forward - Should we compute regular dominators, or post-dominators?

unfactor - Should we unfactor the CFG?

approximate

public static void approximate(IR ir,
                               boolean forward)

Compute approximate dominator/post dominator without unfactoring exception handlers. Can only be used if what the client wants is approximate domination (ie, if it doesn't actually have to be correct...)

Parameters:

ir - the IR

forward - Should we compute regular dominators, or post-dominators?

analyze

protected void analyze(IR ir)

analyze dominators

checkReachability

private void checkReachability(IR ir)

Check to make sure all nodes were reached

step1

private void step1()

The goal of this step is to perform a DFS numbering on the CFG, starting at the root. The exit node is not included.

DFS

private void DFS()

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

printNextNodes

private void printNextNodes(BasicBlock block)

Print the "next" nodes (either out or in) for the passed block depending on which way we are viewing the graph

Parameters:

block - the basic block of interest

getNextNodes

private Enumeration<BasicBlock> getNextNodes(BasicBlock block)

Returns an enumeration of the "next" nodes (either out or in) for the passed block depending on which way we are viewing the graph

Parameters:

block - the basic block of interest

getPrevNodes

private Enumeration<BasicBlock> getPrevNodes(BasicBlock block)

Returns an enumeration of the "prev" nodes (either in or out) for the passed block depending on which way we are viewing the graph

Parameters:

block - the basic block of interest

DFS

protected void DFS(BasicBlock block)

The non-recursive depth-first numbering code called from Step 1. The recursive version was too costly on the toba benchmark on Linux/IA32.

Parameters:

block - the basic block to process

step2

private void step2()

This is the heart of the algorithm. See sources for details.

EVAL

private BasicBlock EVAL(BasicBlock block)

This method inspects the passed block and returns the following:

• block, if block is a root of a tree in the forest
• any vertex, u != r such that r is the root of the tree containing block and semi(u) is minimum on the path r -> v, otherwise

See TOPLAS 1(1), July 1979, p 128 for details.

Parameters:

block - the block to evaluate

Returns:

the block as described above

compress

private void compress(BasicBlock block)

This recursive method performs the path compression

Parameters:

block - the block of interest

LINK

private void LINK(BasicBlock block1,
                  BasicBlock block2)

Adds edge (block1, block2) to the forest maintained as an auxiliary data structure. This implementation uses path compression and results in a O(e * alpha(e,n)) complexity, where e is the number of edges in the CFG and n is the number of nodes.

Parameters:

block1 - a basic block corresponding to the source of the new edge

block2 - a basic block corresponding to the source of the new edge

step3

private void step3()

This final step sets the final dominator information.

getDom

private BasicBlock getDom(BasicBlock block)

Returns the current dominator for the passed block

Parameters:

block -

Returns:

the domiator for the passed block

getParent

private BasicBlock getParent(BasicBlock block)

Returns the parent for the passed block

Parameters:

block -

Returns:

the parent for the passed block

getAncestor

private BasicBlock getAncestor(BasicBlock block)

Returns the ancestor for the passed block

Parameters:

block -

Returns:

the ancestor for the passed block

getLabel

private BasicBlock getLabel(BasicBlock block)

returns the label for the passed block or null if the block is null

Parameters:

block -

Returns:

the label for the passed block or null if the block is null

getSemi

private int getSemi(BasicBlock block)

Returns the current semidominator for the passed block

Parameters:

block -

Returns:

the semidominator for the passed block

getSize

private int getSize(BasicBlock block)

returns the size associated with the block

Parameters:

block -

Returns:

the size of the block or 0 if the block is null

getChild

private BasicBlock getChild(BasicBlock block)

Get the child node for this block

Parameters:

block -

Returns:

the child node

printResults

private void printResults(IR ir)

Print the nodes that dominate each basic block

Parameters:

ir - the IR

printDFSNumbers

private void printDFSNumbers()

Print the result of the DFS numbering performed in Step 1