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!!

DominanceFrontier

public DominanceFrontier()

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