org.jikesrvm.compilers.opt.regalloc
Class GenericStackManager

java.lang.Object
  org.jikesrvm.compilers.opt.ir.IRTools
      org.jikesrvm.compilers.opt.regalloc.GenericStackManager

Direct Known Subclasses:

StackManager

public abstract class GenericStackManager
extends IRTools

Class to manage the allocation of the "compiler-independent" portion of the stackframe.

DEBUG

protected static final boolean DEBUG

See Also:

Constant Field Values

VERBOSE

protected static final boolean VERBOSE

See Also:

Constant Field Values

VERBOSE_DEBUG

protected static final boolean VERBOSE_DEBUG

See Also:

Constant Field Values

WORDSIZE

protected static final int WORDSIZE

Size of a word, in bytes

See Also:

Constant Field Values

ir

protected IR ir

frameSize

protected int frameSize

allocFrame

protected boolean allocFrame

pref

protected final ArchitectureSpecificOpt.RegisterPreferences pref

Object holding register preferences

restrict

protected ArchitectureSpecificOpt.RegisterRestrictions restrict

Object holding register restrictions

spillPointer

protected int spillPointer

Spill pointer (in bytes) relative to the beginning of the stack frame (starts after the header).

frameRequired

private boolean frameRequired

Have we decided that a stack frame is required for this method?

conversionOffset

private int conversionOffset

Memory location (8 bytes) to be used for type conversions

caughtExceptionOffset

private int caughtExceptionOffset

Memory location (4 bytes) to be used for caughtExceptions

prologueYieldpoint

private boolean prologueYieldpoint

Is there a prologue yieldpoint in this method?

sysCallOffset

private int sysCallOffset

We will have to save and restore all non-volatile registers around system calls, to protect ourselve from malicious native code that may bash these registers. This field, when non-zero, holds the stack-frame offset reserved to hold this data.

scratchInUse

protected final ArrayList<GenericStackManager.ScratchRegister> scratchInUse

For each physical register, holds a ScratchRegister which records the current scratch assignment for the physical register.

nonVolatileGPRLocation

protected final int[] nonVolatileGPRLocation

An array which holds the spill location number used to stash nonvolatile registers.

nonVolatileFPRLocation

protected final int[] nonVolatileFPRLocation

saveVolatileGPRLocation

protected final int[] saveVolatileGPRLocation

An array which holds the spill location number used to stash volatile registers in the SaveVolatile protocol.

saveVolatileFPRLocation

protected final int[] saveVolatileFPRLocation

scratchMap

protected final ScratchMap scratchMap

An object used to track adjustments to the GC maps induced by scratch registers

USE_LINEAR_SCAN

private static boolean USE_LINEAR_SCAN

Should we use information from linear scan in choosing scratch registers?

activeSet

private LinearScan.ActiveSet activeSet

We may rely on information from linear scan to choose scratch registers. If so, the following holds a pointer to some information from linear scan analysis.

GenericStackManager

public GenericStackManager()

getPreferences

ArchitectureSpecificOpt.RegisterPreferences getPreferences()

getRestrictions

ArchitectureSpecificOpt.RegisterRestrictions getRestrictions()

getScratchMap

ScratchMap getScratchMap()

initForArch

public abstract void initForArch(IR ir)

Perform some architecture-specific initialization.

isSysCall

public abstract boolean isSysCall(Instruction s)

Is a particular instruction a system call?

needScratch

public abstract boolean needScratch(Register r,
                                    Instruction s)

Given symbolic register r in instruction s, do we need to ensure that r is in a scratch register is s (as opposed to a memory operand)

allocateNewSpillLocation

public abstract int allocateNewSpillLocation(int type)

Allocate a new spill location and grow the frame size to reflect the new layout.

Parameters:

type - the type to spill

Returns:

the spill location

cleanUpAndInsertEpilogue

public abstract void cleanUpAndInsertEpilogue()

Clean up some junk that's left in the IR after register allocation, and add epilogue code.

getFrameFixedSize

public abstract int getFrameFixedSize()

Return the size of the fixed portion of the stack. (in other words, the difference between the framepointer and the stackpointer after the prologue of the method completes).

Returns:

size in bytes of the fixed portion of the stackframe

computeNonVolatileArea

public abstract void computeNonVolatileArea()

Compute the number of stack words needed to hold nonvolatile registers. Side effects:

• updates the OptCompiler structure
• updates the frameSize field of this object
• updates the frameRequired field of this object

insertNormalPrologue

public abstract void insertNormalPrologue()

Insert the prologue for a normal method.

restoreScratchRegistersBefore

public abstract void restoreScratchRegistersBefore(Instruction s)

Walk over the currently available scratch registers.

For any scratch register r which is def'ed by instruction s, spill r before s and remove r from the pool of available scratch registers.

For any scratch register r which is used by instruction s, restore r before s and remove r from the pool of available scratch registers.

For any scratch register r which has current contents symb, and symb is spilled to location M, and s defs M: the old value of symb is dead. Mark this.

Invalidate any scratch register assignments that are illegal in s.

replaceOperandWithSpillLocation

public abstract void replaceOperandWithSpillLocation(Instruction s,
                                                     RegisterOperand symb)

In instruction s, replace all appearances of a symbolic register operand with uses of the appropriate spill location, as cached by the register allocator.

Parameters:

s - the instruction to mutate.

symb - the symbolic register operand to replace

replaceRegisterWithScratch

private void replaceRegisterWithScratch(Instruction s,
                                        Register r1,
                                        Register r2)

Replace all occurrences of register r1 in an instruction with register r2. Also, for any register r3 that is spilled to the same location as r1, replace r3 with r2.

allocateSpaceForSysCall

public int allocateSpaceForSysCall(int n)

We will have to save and restore all non-volatile registers around system calls, to protect ourselves from malicious native code that may bash these registers. Call this routine before register allocation in order to allocate space on the stack frame to store these registers.

Parameters:

n - the number of GPR registers to save and restore.

Returns:

the offset into the stack where n*4 contiguous words are reserved

getOffsetForSysCall

public int getOffsetForSysCall()

We will have to save and restore all non-volatile registers around system calls, to protect ourselves from malicious native code that may bash these registers. Call this routine before register allocation in order to get the stack-frame offset previously reserved for this data.

Returns:

the offset into the stack where n*4 contiguous words are reserved

unloadScratchRegisterBefore

protected void unloadScratchRegisterBefore(Instruction s,
                                           GenericStackManager.ScratchRegister scratch)

Spill the contents of a scratch register to memory before instruction s.

reloadScratchRegisterBefore

protected void reloadScratchRegisterBefore(Instruction s,
                                           GenericStackManager.ScratchRegister scratch)

Restore the contents of a scratch register before instruction s.

getReservedScratchRegisters

private ArrayList<Register> getReservedScratchRegisters(Instruction s)

Return the set of scratch registers which are currently reserved for use in instruction s.

getCurrentScratchRegister

private GenericStackManager.ScratchRegister getCurrentScratchRegister(Register r,
                                                                      Instruction s)

If there is a scratch register available which currently holds the value of symbolic register r, then return that scratch register.

Additionally, if there is a scratch register available which is mapped to the same stack location as r, then return that scratch register.

Else return null.

Parameters:

r - the symbolic register to hold

s - the instruction for which we need r in a register

getPhysicalScratchRegister

private GenericStackManager.ScratchRegister getPhysicalScratchRegister(Register r)

If register r is currently in use as a scratch register, then return that scratch register.

Else return null.

markDirtyScratchRegisters

private void markDirtyScratchRegisters(Instruction s)

Walk over the currently available scratch registers.

For any register which is dirty, note this in the scratch map for instruction s.

restoreAllScratchRegistersBefore

private void restoreAllScratchRegistersBefore(Instruction s)

Walk over the currently available scratch registers, and spill their contents to memory before instruction s. Also restore the correct live value for each scratch register. Normally, s should end a basic block.

SPECIAL CASE: If s is a return instruction, only restore the scratch registers that are used by s. The others are dead.

isDeadBefore

public boolean isDeadBefore(Register r,
                            Instruction s)

Is a particular register dead immediately before instruction s.

holdInScratchAfter

private GenericStackManager.ScratchRegister holdInScratchAfter(Instruction s,
                                                               Register symb,
                                                               boolean beCheap)

Insert code as needed so that after instruction s, the value of a symbolic register will be held in a particular scratch physical register.

Parameters:

beCheap - don't expend much effort optimizing scratch assignments

Returns:

the physical scratch register that holds the value after instruction s

isLegal

protected boolean isLegal(Register symb,
                          Register phys,
                          Instruction s)

Is it legal to assign symbolic register symb to scratch register phys in instruction s?

getScratchRegister

private GenericStackManager.ScratchRegister getScratchRegister(Register symb,
                                                               Instruction s,
                                                               boolean beCheap)

Get a scratch register to hold symbolic register symb in instruction s.

Parameters:

beCheap - don't expend too much effort

getScratchRegisterUsingIntervals

private GenericStackManager.ScratchRegister getScratchRegisterUsingIntervals(Register r,
                                                                             Instruction s)

Find a register which can serve as a scratch register for symbolic register r in instruction s.

Insert spills if necessary to ensure that the returned scratch register is free for use.

getFirstAvailableScratchRegister

private GenericStackManager.ScratchRegister getFirstAvailableScratchRegister(Register r,
                                                                             Instruction s)

Find the first available register which can serve as a scratch register for symbolic register r in instruction s.

Insert spills if necessary to ensure that the returned scratch register is free for use.

moveToScratchBefore

private GenericStackManager.ScratchRegister moveToScratchBefore(Instruction s,
                                                                Register symb,
                                                                boolean beCheap)

Assign symbolic register symb to a physical register, and insert code before instruction s to load the register from the appropriate stack location.

Parameters:

beCheap - don't expend to much effort to optimize scratch assignments

Returns:

the physical register used to hold the value when it is loaded from the spill location

createScratchBefore

private GenericStackManager.ScratchRegister createScratchBefore(Instruction s,
                                                                Register r,
                                                                Register symb)

Make physical register r available to be used as a scratch register before instruction s. In instruction s, r will hold the value of register symb.

usesSpillLocation

private boolean usesSpillLocation(Register r,
                                  Instruction s)

Does instruction s use the spill location for a given register?

spillLocationUse

private Register spillLocationUse(Register r,
                                  Instruction s)

Assuming instruction s uses the spill location for a given register, return the symbolic register that embodies that use.

definesSpillLocation

private boolean definesSpillLocation(Register r,
                                     Instruction s)

Does instruction s define the spill location for a given register?

definesSpillLocation

private boolean definesSpillLocation(int loc,
                                     Instruction s)

Does instruction s define spill location loc?

usesSpillLocation

private boolean usesSpillLocation(int loc,
                                  Instruction s)

Does instruction s use spill location loc?

spillLocationUse

private Register spillLocationUse(int loc,
                                  Instruction s)

Assuming instruction s uses the spill location loc, return the symbolic register that embodies that use.

Note that at most one such register can be used, since at most one live register can use a given spill location.

getFirstFPRNotUsedIn

private Register getFirstFPRNotUsedIn(Register r,
                                      Instruction s,
                                      ArrayList<Register> reserved)

Return a FPR that does not appear in instruction s, to be used as a scratch register to hold register r. Except, do NOT return any register that is a member of the reserved set.

Throw an exception if none found.

getFirstDeadFPRNotUsedIn

private Register getFirstDeadFPRNotUsedIn(Register r,
                                          Instruction s,
                                          ArrayList<Register> reserved)

Return a FPR that does not appear in instruction s, and is dead before instruction s, to hold symbolic register r. Except, do NOT return any register that is a member of the reserved set.

Return null if none found

getFirstGPRNotUsedIn

private Register getFirstGPRNotUsedIn(Register r,
                                      Instruction s,
                                      ArrayList<Register> reserved)

Return a GPR that does not appear in instruction s, to hold symbolic register r. Except, do NOT return any register that is a member of the reserved set. Throw an exception if none found.

getFirstDeadGPRNotUsedIn

private Register getFirstDeadGPRNotUsedIn(Register r,
                                          Instruction s,
                                          ArrayList<Register> reserved)

Return a GPR that does not appear in instruction s, and is dead before instruction s, to hold symbolic register r. Except, do NOT return any register that is a member of the reserved set.

return null if none found.

appearsIn

private boolean appearsIn(Register r,
                          Instruction s)

Does register r appear in instruction s?

isPEIWithCatch

private boolean isPEIWithCatch(Instruction s)

Is s a PEI with a reachable catch block?

getNonvolatileGPROffset

protected int getNonvolatileGPROffset(int n)

Return the offset from the frame pointer for the place to store the nth nonvolatile GPR.

getNonvolatileFPROffset

protected int getNonvolatileFPROffset(int n)

Return the offset from the frame pointer for the place to store the nth nonvolatile FPR.

insertPrologueAndEpilogue

public final void insertPrologueAndEpilogue()

PROLOGUE/EPILOGUE. must be done after register allocation

insertPrologue

private void insertPrologue()

Insert the prologue.

insertSpillCode

public void insertSpillCode()

After register allocation, go back through the IR and insert compensating code to deal with spills.

insertSpillCode

public void insertSpillCode(LinearScan.ActiveSet set)

After register allocation, go back through the IR and insert compensating code to deal with spills.

Parameters:

set - information from linear scan analysis

insertSpillBefore

public abstract void insertSpillBefore(Instruction s,
                                       Register r,
                                       byte type,
                                       int location)

Insert a spill of a physical register before instruction s.

Parameters:

s - the instruction before which the spill should occur

r - the register (should be physical) to spill

type - one of INT_VALUE, FLOAT_VALUE, DOUBLE_VALUE, or CONDITION_VALUE

location - the spill location

insertSpillAfter

public final void insertSpillAfter(Instruction s,
                                   Register r,
                                   byte type,
                                   int location)

Insert a spill of a physical register after instruction s.

Parameters:

s - the instruction after which the spill should occur

r - the register (should be physical) to spill

type - one of INT_VALUE, FLOAT_VALUE, DOUBLE_VALUE, or CONDITION_VALUE

location - the spill location

insertUnspillBefore

public abstract void insertUnspillBefore(Instruction s,
                                         Register r,
                                         byte type,
                                         int location)

Insert a load of a physical register from a spill location before instruction s.

Parameters:

s - the instruction before which the spill should occur

r - the register (should be physical) to spill

type - one of INT_VALUE, FLOAT_VALUE, DOUBLE_VALUE, or CONDITION_VALUE

location - the spill location

insertUnspillAfter

public final void insertUnspillAfter(Instruction s,
                                     Register r,
                                     byte type,
                                     int location)

Insert a load of a physical register from a spill location before instruction s.

Parameters:

s - the instruction before which the spill should occur

r - the register (should be physical) to spill

type - one of INT_VALUE, FLOAT_VALUE, DOUBLE_VALUE, or CONDITION_VALUE

location - the spill location

frameIsRequired

protected boolean frameIsRequired()

Are we required to allocate a stack frame for this method?

setFrameRequired

protected void setFrameRequired()

Record that we need a stack frame for this method.

hasPrologueYieldpoint

protected boolean hasPrologueYieldpoint()

Does this IR have a prologue yieldpoint?

allocateParameterSpace

public void allocateParameterSpace(int s)

Ensure param passing area of size - STACKFRAME_HEADER_SIZE bytes

allocateOnStackFrame

public int allocateOnStackFrame(int size)

Allocate the specified number of bytes in the stackframe, returning the offset to the start of the allocated space.

Parameters:

size - the number of bytes to allocate

Returns:

offset to the start of the allocated space.

forceFrameAllocation

public void forceFrameAllocation()

We encountered a magic (get/set framepointer) that is going to force us to acutally create the stack frame.

allocateSpaceForConversion

public int allocateSpaceForConversion()

We encountered a float/int conversion that uses the stack as temporary storage.

allocateSpaceForCaughtException

public int allocateSpaceForCaughtException()

We encountered a catch block that actually uses its caught exception object; allocate a stack slot for the exception delivery code to use to pass the exception object to us.

prepare

public void prepare(IR ir)

Called as part of the register allocator startup. (1) examine the IR to determine whether or not we need to allocate a stack frame (2) given that decison, determine whether or not we need to have prologue/epilogue yieldpoints. If we don't need them, remove them. Set up register preferences. (3) initialization code for the old RegisterManager. (4) save caughtExceptionOffset where the exception deliverer can find it (5) initialize the restrictions object

Parameters:

ir - the IR

computeRestrictions

public final void computeRestrictions(IR ir)

Set up register restrictions

allocateVolatileRegister

public final Register allocateVolatileRegister(Register symbReg)

Find an volatile register to allocate starting at the reg corresponding to the symbolic register passed

Parameters:

symbReg - the place to start the search

Returns:

the allocated register or null

getValueType

public final byte getValueType(Register r)

Given a symbolic register, return a code that indicates the type of the value stored in the register. Note: This routine returns INT_VALUE for longs

Returns:

one of INT_VALUE, FLOAT_VALUE, DOUBLE_VALUE, CONDITION_VALUE

align

protected static int align(int number,
                           int alignment)

allocateNonVolatileRegister

public final Register allocateNonVolatileRegister(Register symbReg)

Find a nonvolatile register to allocate starting at the reg corresponding to the symbolic register passed TODO: Clean up this interface.

Parameters:

symbReg - the place to start the search

Returns:

the allocated register or null