org.jikesrvm.compilers.opt.controlflow
Class CFGTransformations

java.lang.Object
  org.jikesrvm.compilers.opt.driver.CompilerPhase
      org.jikesrvm.compilers.opt.controlflow.CFGTransformations

public class CFGTransformations
extends CompilerPhase

This Phase supports

• transforming while into until loops,
• elimination of critical edges,

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

CFGTransformations

public CFGTransformations()

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

perform

public void perform(IR ir)

Description copied from class: CompilerPhase

This is the method that actually does the work of the phase.

Specified by:

perform in class CompilerPhase

Parameters:

ir - the IR on which to apply the phase

staticPerform

static void staticPerform(IR ir)

static version of perform

Parameters:

ir -

shouldPerform

public boolean shouldPerform(OptOptions options)

Should this phase be performed?

Overrides:

shouldPerform in class CompilerPhase

Parameters:

options - the compiler options for the compilation

Returns:

true if the opt level is at least 2 and whiles should be turned into untils

getName

public String getName()

Returns the name of the phase.

Specified by:

getName in class CompilerPhase

Returns:

a String which is the name of the phase.

printingEnabled

public boolean printingEnabled(OptOptions options,
                               boolean before)

Returns true if the phase wants the IR dumped before and/or after it runs.

Overrides:

printingEnabled in class CompilerPhase

Parameters:

options - the compiler options for the compilation

before - true when invoked before perform, false otherwise.

Returns:

true if the IR should be printed, false otherwise.

turnWhilesIntoUntils

private static boolean turnWhilesIntoUntils(IR ir)

treat all loops of the ir

turnLoopTreeIntoUntils

private static boolean turnLoopTreeIntoUntils(LSTNode t,
                                              IR ir)

deal with a sub tree of the loop structure tree

ensureLandingPads

private static void ensureLandingPads(IR ir)

treat all loops of the ir

ensureLandingPads

private static void ensureLandingPads(LSTNode t,
                                      IR ir)

deal with a sub tree of the loop structure tree

edgeFrequency

private static float edgeFrequency(BasicBlock a,
                                   BasicBlock b)

ensureLandingPad

private static void ensureLandingPad(LSTNode n,
                                     IR ir)

turnLoopIntoUntil

private static boolean turnLoopIntoUntil(LSTNode n,
                                         IR ir)

Transform a given loop

Look for the set S of in-loop predecessors of the loop header h. Make a copy h' of the loop header and redirect all edges going from nodes in S to h. Make them point to h' instead.

As an effect of this transformation, the old header is now not anymore part of the loop, but guards it.

loopPredecessors

private static BasicBlock[] loopPredecessors(LSTNode n)

the predecessors of the loop header that are not part of the loop

inLoopPredecessors

private static BasicBlock[] inLoopPredecessors(LSTNode n)

the predecessors of the loop header that are part of the loop.

inLoopSuccessors

private static BasicBlock[] inLoopSuccessors(LSTNode n)

the successors of the loop header that are part of the loop.

killFallThroughs

static void killFallThroughs(IR ir,
                             BitVector nloop)

inLoop

static boolean inLoop(BasicBlock b,
                      BitVector nloop)

exitsLoop

private static boolean exitsLoop(BasicBlock b,
                                 BitVector loop)

splitCriticalEdges

public static void splitCriticalEdges(IR ir)

Critical edge removal: if (a,b) is an edge in the cfg where `a' has more than one out-going edge and `b' has more than one in-coming edge, insert a new empty block `c' on the edge between `a' and `b'.

We do this to provide landing pads for loop-invariant code motion. So we split only edges, where `a' has a lower loop nesting depth than `b'.