org.jikesrvm.compilers.opt.ssa

Class LICM

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

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

Fields

Modifier and Type	Field and Description
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 Map<Instruction,Integer>	instructionNumbers
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

Constructors

Constructor and Description
LICM()

Method Summary

Modifier and Type	Method and Description
private int	_checkLoop(Instruction inst, HeapOperand<?> hop, int xidx)
private int	checkLoop(Instruction inst, HeapOperand<Object> hop, int xidx, BasicBlock block)
private BasicBlock	commonDominator(BasicBlock a, BasicBlock b)
(package private) Instruction	definingInstruction(Operand op)
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) Determines how expensive it is to place an instruction in this block.
(package private) BasicBlock	getBlock(Instruction inst)
Constructor<CompilerPhase>	getClassConstructor() Get a constructor object for this compiler phase
(package private) Instruction	getEarlyPos(Instruction inst)
String	getName()
(package private) BasicBlock	getOrigBlock(Instruction inst)
(package private) Operand	getResult(Instruction inst)
(package private) int	getState(Instruction inst) In what state (initial, early, late, done) is this instruction
(package private) void	initialize(IR ir)
private boolean	inVariantLocation(Instruction inst, BasicBlock block)
private Instruction	maxDominatorDepth(Instruction a, Instruction b) Compares two instructions according to their depth in the dominator tree and return the one with the greatest depth.
(package private) void	move(Instruction inst, BasicBlock to)
void	perform(IR ir) Execute loop invariant code motion on the given IR.
(package private) boolean	postDominates(BasicBlock a, BasicBlock b, IR ir) does a post dominate b?
private boolean	replaceUses(Instruction inst, HeapOperand<?> replacement, BasicBlockOperand replacementBlock, boolean onlyPEIs)
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) Schedules an instruction as early as possible, but behind the definitions of op[i] and behind earlyPos.
(package private) BasicBlock	scheduleHeapUsesLate(Instruction inst, BasicBlock lateBlock)
(package private) BasicBlock	scheduleLate(Instruction inst)
private Instruction	scheduleScalarDefsEarly(Enumeration<Operand> e, Instruction earlyPos, Instruction inst) Schedules an instruction as early as possible, but behind the definitions in e and behind earlyPos
private BasicBlock	scheduleScalarUsesLate(Instruction inst, BasicBlock lateBlock)
(package private) void	setBlock(Instruction inst, BasicBlock b)
(package private) void	setEarlyPos(Instruction inst, Instruction pos)
(package private) void	setOrigBlock(Instruction inst, BasicBlock b)
(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)
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) Visits 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?

instructionNumbers

private Map<Instruction,Integer> instructionNumbers

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()

Specified by:

getName in class CompilerPhase

Returns:

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)

Parameters:

inst - the instruction that might be moved

ir - the governing iR

Returns:

whether it is safe to move the given instruction, depending on the properties of the IR (is it in heapSSA form or not?)

scheduleEarly

private Instruction scheduleEarly(Instruction inst)

Schedule this instruction as early as possible

Parameters:

inst - the instruction to schedule

Returns:

the instruction that serves as the new lower bound (exclusive) for further scheduling

scheduleLate

BasicBlock scheduleLate(Instruction 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.

Parameters:

a - an instruction matching the constraints from the description

b - another instruction matching the constraints from the description

Returns:

the dominance successor of a

maxDominatorDepth

private Instruction maxDominatorDepth(Instruction a,
                                      Instruction b)

Compares two instructions according to their depth in the dominator tree and return the one with the greatest depth.

Parameters:

a - an instruction

b - another instruction

Returns:

the instruction with the greatest depth in the dominator tree

commonDominator

private BasicBlock commonDominator(BasicBlock a,
                                   BasicBlock b)

scheduleScalarDefsEarly

private Instruction scheduleScalarDefsEarly(Enumeration<Operand> e,
                                            Instruction earlyPos,
                                            Instruction inst)

Schedules an instruction as early as possible, but behind the definitions in e and behind earlyPos

Parameters:

e - the definitions that must have been occurred before the new position of the instruction

earlyPos - the instruction that serves as a lower bound (exclusive) for the position

inst - the instruction to schedule

Returns:

the instruction that serves as the new lower bound (exclusive) for further scheduling

scheduleHeapDefsEarly

Instruction scheduleHeapDefsEarly(HeapOperand<?>[] op,
                                  Instruction earlyPos,
                                  Instruction me)

Schedules an instruction as early as possible, but behind the definitions of op[i] and behind earlyPos.

Parameters:

op - the definitions that must have been occurred before the new position of the instruction

earlyPos - the instruction that serves as a lower bound (exclusive) for the position

me - the instruction to schedule

Returns:

the instruction that serves as the new lower bound (exclusive) for further scheduling

useBlock

BasicBlock useBlock(Instruction use,
                    Operand op)

scheduleScalarUsesLate

private BasicBlock scheduleScalarUsesLate(Instruction inst,
                                          BasicBlock lateBlock)

scheduleHeapUsesLate

BasicBlock scheduleHeapUsesLate(Instruction inst,
                                BasicBlock lateBlock)

definingInstruction

Instruction definingInstruction(Operand op)

Parameters:

op - the operand that's being defined

Returns:

the instruction that defines the operand.

getResult

Operand getResult(Instruction inst)

Parameters:

inst - an instruction

Returns:

the result operand of the instruction

upto

BasicBlock upto(Instruction earlyPos,
                BasicBlock lateBlock,
                Instruction inst)

Visits the blocks between the late and the early position along their path in the dominator tree.

Parameters:

earlyPos - the early position

lateBlock - the late position

inst - the instruction to schedule

Returns:

the block with the smallest execution costs

frequency

final float frequency(BasicBlock b)

Determines how expensive it is to place an instruction in this block.

Parameters:

b - a basic block

Returns:

the block's execution frequency

move

void move(Instruction inst,
          BasicBlock to)

postDominates

boolean postDominates(BasicBlock a,
                      BasicBlock b,
                      IR ir)

does a post dominate b?

Parameters:

a - the possible post-dominator

b - the possibly post-dominated block

ir - the IR that contains the blocks

Returns:

whether the first block post-dominates the second block

getBlock

BasicBlock getBlock(Instruction inst)

setBlock

void setBlock(Instruction inst,
              BasicBlock b)

getEarlyPos

Instruction getEarlyPos(Instruction inst)

setEarlyPos

void setEarlyPos(Instruction inst,
                 Instruction pos)

getOrigBlock

BasicBlock getOrigBlock(Instruction inst)

setOrigBlock

void setOrigBlock(Instruction inst,
                  BasicBlock b)

getState

int getState(Instruction inst)

In what state (initial, early, late, done) is this instruction

Parameters:

inst - the instruction to check

Returns:

the instruction's state

setState

void setState(Instruction inst,
              int s)

Set the state (initial, early, late, done) of the instruction

Parameters:

inst - the instruction

s - the state

initialize

void initialize(IR ir)

simplify

private boolean simplify(Instruction inst,
                         BasicBlock block)

_checkLoop

private int _checkLoop(Instruction inst,
                       HeapOperand<?> hop,
                       int xidx)

checkLoop

private int checkLoop(Instruction inst,
                      HeapOperand<Object> hop,
                      int xidx,
                      BasicBlock block)

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)

resetLandingPads

private void resetLandingPads()