org.jikesrvm.compilers.opt.controlflow

Class Dominators

java.lang.Object

org.jikesrvm.compilers.opt.controlflow.Dominators

public class Dominators
extends Object

Calculate dominators for basic blocks.

Uses the algorithm contained in Dragon book, pg. 670-1.

       D(n0) := { n0 }
       for n in N - { n0 } do D(n) := N;
       while changes to any D(n) occur do
         for n in N - {n0} do
             D(n) := {n} U (intersect of D(p) over all predecessors p of n)
 

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

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static boolean	COMPUTE_POST_DOMINATORS Should we compute post-dominators instead of dominators?
(package private) static boolean	DEBUG Control for debug output
private Map<BasicBlock,DominatorInfo>	dominatorInfo

Constructor Summary

Constructors

Constructor and Description
Dominators()

Method Summary

Modifier and Type	Method and Description
void	computeApproxDominators(IR ir) Calculate the "approximate" dominators for an IR i.e., the dominators in the factored CFG rather than the normal CFG.
void	computeApproxPostdominators(IR ir) Calculate the postdominators for an IR.
DominatorInfo	getDominatorInfo(BasicBlock b)
void	perform(IR ir) Calculate the dominators for an IR.
void	printDominators(IR ir) Print the (already calculated) dominators.
void	updateBlocks(DF_Solution solution) Creates a DominatorInfo for each basic block in the data flow system solution.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

static final boolean DEBUG

Control for debug output

See Also:

Constant Field Values

COMPUTE_POST_DOMINATORS

static boolean COMPUTE_POST_DOMINATORS

Should we compute post-dominators instead of dominators? This is false by default.

dominatorInfo

private Map<BasicBlock,DominatorInfo> dominatorInfo

Constructor Detail

Dominators

public Dominators()

Method Detail

perform

public void perform(IR ir)

Calculate the dominators for an IR.

Parameters:

ir - the IR in question

computeApproxDominators

public void computeApproxDominators(IR ir)

Calculate the "approximate" dominators for an IR i.e., the dominators in the factored CFG rather than the normal CFG.

(No exception is thrown if the input IR has handler blocks.)

Parameters:

ir - the IR in question

computeApproxPostdominators

public void computeApproxPostdominators(IR ir)

Calculate the postdominators for an IR.

Parameters:

ir - the IR in question

updateBlocks

public void updateBlocks(DF_Solution solution)

Creates a DominatorInfo for each basic block in the data flow system solution.

Parameters:

solution - the solution to the Dominators equations

printDominators

public void printDominators(IR ir)

Print the (already calculated) dominators.

Parameters:

ir - the IR

getDominatorInfo

public DominatorInfo getDominatorInfo(BasicBlock b)