org.jikesrvm.compilers.opt.controlflow

Class DominanceFrontier

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.compilers.opt.controlflow.DominanceFrontier

public class DominanceFrontier
extends CompilerPhase

Calculate dominance frontier for a set of basic blocks.

Uses the algorithm of Cytron et al., TOPLAS Oct. 91:

 for each X in a bottom-up traversal of the dominator tree do

      DF(X) < - null
      for each Y in Succ(X) do
        if (idom(Y)!=X) then DF(X) <- DF(X) U Y
      end
      for each Z in {idom(z) = X} do
        for each Y in DF(Z) do
              if (idom(Y)!=X) then DF(X) <- DF(X) U Y
        end
      end
 

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

Field Summary

Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

container

Constructor Summary

Constructors

Constructor and Description
DominanceFrontier()

Method Summary

Modifier and Type	Method and Description
static BitVector	getDominanceFrontier(IR ir, BitVector bits) Calculate the dominance frontier for the set of basic blocks represented by a BitVector.
static BitVector	getIteratedDominanceFrontier(IR ir, BitVector S) Calculate the iterated dominance frontier for a set of basic blocks represented by a BitVector.
String	getName() Return a String representation for this phase
CompilerPhase	newExecution(IR ir) Return this instance of this phase.
void	perform(IR ir) Calculate the dominance frontier for each basic block in the CFG.
boolean	printingEnabled(OptOptions options, boolean before) Should the IR be printed either before or after performing this phase?
boolean	shouldPerform(OptOptions options) Should this phase be performed?

Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

dumpIR, dumpIR, getClassConstructor, getCompilerPhaseConstructor, getCompilerPhaseConstructor, performPhase, reportAdditionalStats, setContainer, verify

Methods inherited from class java.lang.Object

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

Constructor Detail

DominanceFrontier

public DominanceFrontier()

Method Detail

shouldPerform

public final boolean shouldPerform(OptOptions options)

Should this phase be performed? This is a member of a composite phase, so always return true. The parent composite phase will dictate.

Overrides:

shouldPerform in class CompilerPhase

Parameters:

options - controlling compiler options

Returns:

true

newExecution

public CompilerPhase newExecution(IR ir)

Return this instance of this phase. This phase contains no per-compilation instance fields.

Overrides:

newExecution in class CompilerPhase

Parameters:

ir - not used

Returns:

this

getName

public final String getName()

Return a String representation for this phase

Specified by:

getName in class CompilerPhase

Returns:

a String representation for this phase

printingEnabled

public final boolean printingEnabled(OptOptions options,
                                     boolean before)

Should the IR be printed either before or after performing this phase?

Overrides:

printingEnabled in class CompilerPhase

Parameters:

options - controlling compiler options

before - true iff querying before the phase

Returns:

false

perform

public void perform(IR ir)

Calculate the dominance frontier for each basic block in the CFG. Stores the result in the DominatorTree for the governing IR.

NOTE: The dominator tree MUST be calculated BEFORE calling this routine.

Specified by:

perform in class CompilerPhase

Parameters:

ir - the governing IR

getDominanceFrontier

public static BitVector getDominanceFrontier(IR ir,
                                             BitVector bits)

Calculate the dominance frontier for the set of basic blocks represented by a BitVector.

NOTE: The dominance frontiers for the IR MUST be calculated BEFORE calling this routine.

Parameters:

ir - the governing IR

bits - the BitVector representing the set of basic blocks

Returns:

a BitVector representing the dominance frontier for the set

getIteratedDominanceFrontier

public static BitVector getIteratedDominanceFrontier(IR ir,
                                                     BitVector S)

Calculate the iterated dominance frontier for a set of basic blocks represented by a BitVector.

NOTE: The dominance frontiers for the IR MUST be calculated BEFORE calling this routine.

Parameters:

ir - The governing IR

S - The BitVector representing the set of basic blocks

Returns:

an BitVector representing the dominance frontier for the set