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.

Field Summary

Fields

Modifier and Type	Field and Description
private ControlFlowGraph	cfg a convenient place to locate the cfg to avoid passing it internally
(package private) static boolean	DEBUG
protected int	DFSCounter a counter for assigning DFS numbers
private 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.
private IR	ir
private Map<BasicBlock,LTDominatorInfo>	ltDominators
private BasicBlock[]	vertex a mapping from DFS number to their basic blocks

Constructor Summary

Constructors

Constructor and Description
LTDominators(IR ir, boolean forward) The constructor, called by the perform method

Method Summary

Modifier and Type	Method and Description
protected void	analyze(IR ir)
static void	approximate(IR ir, boolean forward) Compute approximate dominator/post dominator without unfactoring exception handlers.
private void	checkReachability(IR ir) Checks that all nodes were reached.
private void	compress(BasicBlock block) This recursive method performs the path compression
private void	DFS()
protected void	DFS(BasicBlock block) The non-recursive depth-first numbering code called from Step 1.
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 !
private BasicBlock	getAncestor(BasicBlock block)
private BasicBlock	getChild(BasicBlock block)
private BasicBlock	getDom(BasicBlock block)
private BasicBlock	getFirstNode() Get the first node, either entry or exit depending on which way we are viewing the graph
(package private) LTDominatorInfo	getInfo(BasicBlock bb)
private BasicBlock	getLabel(BasicBlock block)
private Enumeration<BasicBlock>	getNextNodes(BasicBlock block)
private BasicBlock	getParent(BasicBlock block)
private Enumeration<BasicBlock>	getPrevNodes(BasicBlock block)
private int	getSemi(BasicBlock block)
private int	getSize(BasicBlock block)
private void	LINK(BasicBlock block1, BasicBlock block2) Adds edge (block1, block2) to the forest maintained as an auxiliary data structure.
static void	perform(IR ir, boolean forward, boolean unfactor) The entry point for this phase
private void	printDFSNumbers() Print the result of the DFS numbering performed in Step 1
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
private void	printResults(IR ir) Print the nodes that dominate each basic block
private void	step1() The goal of this step is to perform a DFS numbering on the CFG, starting at the root.
private void	step2() This is the heart of the algorithm.
private void	step3() This final step sets the final dominator information.

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

compare, copy, empty, getTOS, isEmpty, iterator, peek, pop, push, shallowCopy, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

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

private Map<BasicBlock,LTDominatorInfo> ltDominators

ir

private final IR ir

Constructor Detail

LTDominators

LTDominators(IR ir,
             boolean forward)

The constructor, called by the perform method

Parameters:

ir - the governing IR

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

Method Detail

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)

checkReachability

private void checkReachability(IR ir)

Checks that all nodes were reached.

Parameters:

ir - the governing IR

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)

Parameters:

block - the basic block of interest

Returns:

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

getPrevNodes

private Enumeration<BasicBlock> getPrevNodes(BasicBlock block)

Parameters:

block - the basic block of interest

Returns:

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

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)

Parameters:

block - the block whose dominator is of interest

Returns:

the dominator for the passed block

getParent

private BasicBlock getParent(BasicBlock block)

Parameters:

block - the block whose parent is of interest

Returns:

the parent for the passed block

getAncestor

private BasicBlock getAncestor(BasicBlock block)

Parameters:

block - the block whose ancestor is of interest

Returns:

the ancestor for the passed block

getLabel

private BasicBlock getLabel(BasicBlock block)

Parameters:

block - the block whose label is of interest

Returns:

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

getSemi

private int getSemi(BasicBlock block)

Parameters:

block - the block whose semidominator is of interest

Returns:

the semidominator for the passed block

getSize

private int getSize(BasicBlock block)

Parameters:

block - block the block whose size is of interest

Returns:

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

getChild

private BasicBlock getChild(BasicBlock block)

Parameters:

block - the block whose child is of interest

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

getInfo

LTDominatorInfo getInfo(BasicBlock bb)