Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.jikesrvm.compilers.opt.ssa
Class LICM

java.lang.Object
  extended by org.jikesrvm.compilers.opt.driver.CompilerPhase
      extended by org.jikesrvm.compilers.opt.ssa.LICM

public class LICM
extends CompilerPhase

This class does loop invariant code movement. It is a subphase of GCP (global code placement).

Field Summary
private  BasicBlock[] block
           
(package private) static int CL_COMPLEX
           
(package private) static int CL_LOADS_AND_STORES
           
(package private) static int CL_LOADS_ONLY
           
(package private) static int CL_NONE
           
(package private) static int CL_STORES_ONLY
           
private static Constructor<CompilerPhase> constructor
          Constructor for this compiler phase
private static boolean DEBUG
          Generate debug output?
private  DominatorTree dominator
           
private static int done
           
private static int early
           
private  Instruction[] earlyPos
           
private static int initial
           
private  IR ir
           
private static int late
           
private  HashSet<Operator> moved
           
private  BasicBlock[] origBlock
           
private  HashSet<Instruction> relocated
           
private  SSADictionary ssad
           
private  int[] state
           
private static boolean VERBOSE
          Generate verbose debug output?
 
Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase
container
 
Constructor Summary
LICM()
           
 
Method Summary
private  int _checkLoop(Instruction inst, HeapOperand<?> hop, int xidx)
          check that inside the loop, the heap variable is only used/defed by simple, non-volatile loads/stores returns one of: CL_LOADS_ONLY, CL_STORES_ONLY, CL_LOADS_AND_STORES, CL_COMPLEX
private  int checkLoop(Instruction inst, HeapOperand<Object> hop, int xidx, BasicBlock block)
          check that inside the loop, the heap variable is only used/defed by simple, non-volatile loads/stores returns one of: CL_LOADS_ONLY, CL_STORES_ONLY, CL_LOADS_AND_STORES, CL_COMPLEX
private  BasicBlock commonDominator(BasicBlock a, BasicBlock b)
           
(package private)  Instruction definingInstruction(Operand op)
          Return the instruction that defines the operand.
private  Instruction dominanceSuccessor(Instruction a, Instruction b)
          return `a's successor on the path from `a' to `b' in the dominator tree.
(package private)  float frequency(BasicBlock b)
          How expensive is it to place an instruction in this block?
(package private)  BasicBlock getBlock(Instruction inst)
          Get the basic block of an instruction
 Constructor<CompilerPhase> getClassConstructor()
          Get a constructor object for this compiler phase
(package private)  Instruction getEarlyPos(Instruction inst)
          Get the early position of an instruction
 String getName()
          Returns the name of the phase
(package private)  BasicBlock getOrigBlock(Instruction inst)
          Get the block, where the instruction was originally located
(package private)  Operand getResult(Instruction inst)
          Get the result operand of the instruction
(package private)  int getState(Instruction inst)
          In what state (initial, early, late, done) is this instruction
(package private)  void initialize(IR ir)
          initialize the state of the algorithm
private  boolean inVariantLocation(Instruction inst, BasicBlock block)
           
private  Instruction maxDominatorDepth(Instruction a, Instruction b)
          compare a and b according to their depth in the dominator tree and return the one with the greatest depth.
(package private)  void move(Instruction inst, BasicBlock to)
          move `inst' behind `pred'
 void perform(IR ir)
          Execute loop invariant code motion on the given IR.
(package private)  boolean postDominates(BasicBlock a, BasicBlock b)
          does a post dominate b?
private  boolean replaceUses(Instruction inst, HeapOperand<?> replacement, BasicBlockOperand replacementBlock, boolean onlyPEIs)
          In the consumers of `inst', replace uses of `inst's result with uses of `replacement'
private  void resetLandingPads()
           
private  Instruction scheduleEarly(Instruction inst)
          Schedule this instruction as early as possible
(package private)  Instruction scheduleHeapDefsEarly(HeapOperand<?>[] op, Instruction earlyPos, Instruction me)
          Schedule me as early as possible, but behind the definitions of op[i] and behind earlyPos
(package private)  BasicBlock scheduleHeapUsesLate(Instruction inst, BasicBlock lateBlock)
          Schedule me as early as possible, but behind the definitions of op[i] and behind earlyPos
(package private)  BasicBlock scheduleLate(Instruction inst)
          Schedule as late as possible.
private  Instruction scheduleScalarDefsEarly(Enumeration<Operand> e, Instruction earlyPos, Instruction inst)
          Schedule me as early as possible, but behind the definitions in e and behind earlyPos
private  BasicBlock scheduleScalarUsesLate(Instruction inst, BasicBlock lateBlock)
          Schedule me as late as possible, but in front of my uses and before latePos
(package private)  void setBlock(Instruction inst, BasicBlock b)
          Set the basic block for an instruction
(package private)  void setEarlyPos(Instruction inst, Instruction pos)
          Set the early position for an instruction
(package private)  void setOrigBlock(Instruction inst, BasicBlock b)
          Set the block, where the instruction is originally located.
(package private)  void setState(Instruction inst, int s)
          Set the state (initial, early, late, done) of the instruction
static boolean shouldMove(Instruction inst, IR ir)
          Is it save to move the given instruction, depending on we are in heapSSA form or not?
 boolean shouldPerform(OptOptions options)
          This method determines if the phase should be run, based on the Options object it is passed.
private  boolean simplify(Instruction inst, BasicBlock block)
           
(package private)  BasicBlock upto(Instruction earlyPos, BasicBlock lateBlock, Instruction inst)
          Visit the blocks between the late and the early position along their path in the dominator tree.
(package private)  BasicBlock useBlock(Instruction use, Operand op)
           
private  boolean useDominates(Operand op, BasicBlock block)
           
 
Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase
dumpIR, dumpIR, getCompilerPhaseConstructor, getCompilerPhaseConstructor, newExecution, performPhase, printingEnabled, reportAdditionalStats, setContainer, verify
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEBUG

private static final boolean DEBUG
Generate debug output?

See Also:
Constant Field Values

VERBOSE

private static boolean VERBOSE
Generate verbose debug output?

constructor

private static final Constructor<CompilerPhase> constructor
Constructor for this compiler phase

initial

private static final int initial
See Also:
Constant Field Values

early

private static final int early
See Also:
Constant Field Values

late

private static final int late
See Also:
Constant Field Values

done

private static final int done
See Also:
Constant Field Values

relocated

private HashSet<Instruction> relocated

state

private int[] state

block

private BasicBlock[] block

origBlock

private BasicBlock[] origBlock

earlyPos

private Instruction[] earlyPos

ssad

private SSADictionary ssad

dominator

private DominatorTree dominator

ir

private IR ir

moved

private final HashSet<Operator> moved

CL_NONE

static final int CL_NONE
See Also:
Constant Field Values

CL_LOADS_ONLY

static final int CL_LOADS_ONLY
See Also:
Constant Field Values

CL_STORES_ONLY

static final int CL_STORES_ONLY
See Also:
Constant Field Values

CL_LOADS_AND_STORES

static final int CL_LOADS_AND_STORES
See Also:
Constant Field Values

CL_COMPLEX

static final int CL_COMPLEX
See Also:
Constant Field Values
Constructor Detail

LICM

public LICM()
Method Detail

getClassConstructor

public Constructor<CompilerPhase> getClassConstructor()
Get a constructor object for this compiler phase

Overrides:
getClassConstructor in class CompilerPhase
Returns:
compiler phase constructor

perform

public void perform(IR ir)
Execute loop invariant code motion on the given IR.

Specified by:
perform in class CompilerPhase
Parameters:
ir - the IR on which to apply the phase

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.

shouldPerform

public boolean shouldPerform(OptOptions options)
Description copied from class: CompilerPhase
This method determines if the phase should be run, based on the Options object it is passed. By default, phases are always performed. Subclasses should override this method if they only want to be performed conditionally.

Overrides:
shouldPerform in class CompilerPhase
Parameters:
options - the compiler options for the compilation
Returns:
true if SSA-based global code placement is being performed

shouldMove

public static boolean shouldMove(Instruction inst,
                                 IR ir)
Is it save to move the given instruction, depending on we are in heapSSA form or not?

Parameters:
inst -
ir -

scheduleEarly

private Instruction scheduleEarly(Instruction inst)
Schedule this instruction as early as possible

Parameters:
inst -

scheduleLate

BasicBlock scheduleLate(Instruction inst)
Schedule as late as possible.

Parameters:
inst -

dominanceSuccessor

private Instruction dominanceSuccessor(Instruction a,
                                       Instruction b)
return `a's successor on the path from `a' to `b' in the dominator tree. `a' must dominate `b' and `a' and `b' must belong to different blocks.

maxDominatorDepth

private Instruction maxDominatorDepth(Instruction a,
                                      Instruction b)
compare a and b according to their depth in the dominator tree and return the one with the greatest depth.

commonDominator

private BasicBlock commonDominator(BasicBlock a,
                                   BasicBlock b)

scheduleScalarDefsEarly

private Instruction scheduleScalarDefsEarly(Enumeration<Operand> e,
                                            Instruction earlyPos,
                                            Instruction inst)
Schedule me as early as possible, but behind the definitions in e and behind earlyPos

scheduleHeapDefsEarly

Instruction scheduleHeapDefsEarly(HeapOperand<?>[] op,
                                  Instruction earlyPos,
                                  Instruction me)
Schedule me as early as possible, but behind the definitions of op[i] and behind earlyPos

useBlock

BasicBlock useBlock(Instruction use,
                    Operand op)

scheduleScalarUsesLate

private BasicBlock scheduleScalarUsesLate(Instruction inst,
                                          BasicBlock lateBlock)
Schedule me as late as possible, but in front of my uses and before latePos

scheduleHeapUsesLate

BasicBlock scheduleHeapUsesLate(Instruction inst,
                                BasicBlock lateBlock)
Schedule me as early as possible, but behind the definitions of op[i] and behind earlyPos

definingInstruction

Instruction definingInstruction(Operand op)
Return the instruction that defines the operand.

Parameters:
op -

getResult

Operand getResult(Instruction inst)
Get the result operand of the instruction

Parameters:
inst -

upto

BasicBlock upto(Instruction earlyPos,
                BasicBlock lateBlock,
                Instruction inst)
Visit the blocks between the late and the early position along their path in the dominator tree. Return the block with the smallest execution costs.

frequency

final float frequency(BasicBlock b)
How expensive is it to place an instruction in this block?

move

void move(Instruction inst,
          BasicBlock to)
move `inst' behind `pred'

postDominates

boolean postDominates(BasicBlock a,
                      BasicBlock b)
does a post dominate b?

Parameters:
a -
b -

getBlock

BasicBlock getBlock(Instruction inst)
Get the basic block of an instruction

Parameters:
inst -

setBlock

void setBlock(Instruction inst,
              BasicBlock b)
Set the basic block for an instruction

Parameters:
inst -
b -

getEarlyPos

Instruction getEarlyPos(Instruction inst)
Get the early position of an instruction

Parameters:
inst -

setEarlyPos

void setEarlyPos(Instruction inst,
                 Instruction pos)
Set the early position for an instruction

Parameters:
inst -
pos -

getOrigBlock

BasicBlock getOrigBlock(Instruction inst)
Get the block, where the instruction was originally located

Parameters:
inst -

setOrigBlock

void setOrigBlock(Instruction inst,
                  BasicBlock b)
Set the block, where the instruction is originally located.

Parameters:
inst -
b -

getState

int getState(Instruction inst)
In what state (initial, early, late, done) is this instruction

Parameters:
inst -

setState

void setState(Instruction inst,
              int s)
Set the state (initial, early, late, done) of the instruction

Parameters:
inst -
s -

initialize

void initialize(IR ir)
initialize the state of the algorithm

simplify

private boolean simplify(Instruction inst,
                         BasicBlock block)

_checkLoop

private int _checkLoop(Instruction inst,
                       HeapOperand<?> hop,
                       int xidx)
check that inside the loop, the heap variable is only used/defed by simple, non-volatile loads/stores

returns one of: CL_LOADS_ONLY, CL_STORES_ONLY, CL_LOADS_AND_STORES, CL_COMPLEX

checkLoop

private int checkLoop(Instruction inst,
                      HeapOperand<Object> hop,
                      int xidx,
                      BasicBlock block)
check that inside the loop, the heap variable is only used/defed by simple, non-volatile loads/stores

returns one of: CL_LOADS_ONLY, CL_STORES_ONLY, CL_LOADS_AND_STORES, CL_COMPLEX

inVariantLocation

private boolean inVariantLocation(Instruction inst,
                                  BasicBlock block)

useDominates

private boolean useDominates(Operand op,
                             BasicBlock block)

replaceUses

private boolean replaceUses(Instruction inst,
                            HeapOperand<?> replacement,
                            BasicBlockOperand replacementBlock,
                            boolean onlyPEIs)
In the consumers of `inst', replace uses of `inst's result with uses of `replacement'

resetLandingPads

private void resetLandingPads()
Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD