harpoon.Analysis.Instr
Class RegAlloc

java.lang.Object
  harpoon.Analysis.Instr.RegAlloc

Direct Known Subclasses:

AppelRegAlloc, DemandDrivenRegAlloc, GraphColoringRegAlloc, LocalCffRegAlloc

public abstract class RegAlloc
extends Object

RegAlloc performs Register Allocation for a set of Instrs in a Backend.Generic.Code. After register allocation is completed for a set of Instrs, references to non-register Temps in the Instrs will have been replaced by references to machine registers. Since the number of simultaneously live temporaries will exceed the space in the register file, spill code will also be inserted to maintain the state of the register file at each instruction, storing values to the stack and reloading them as needed.
DESIGN NOTE: The abstractSpillFactory method relies on the subclasses of RegAlloc to perform actual allocation. This causes a cycle in our module dependency graph, which, while not strictly illegal, tends to be a sign of a design flaw. Consider moving the code factory generator out of the RegAlloc class into a seperate class to get rid of the cycle. In the meantime, any new RegAlloc subclasses can be incorporated into this method to be used in the compiler. Perhaps should also design a way to parameterize which RegAlloc subclasses will be used.

Version:

$Id: RegAlloc.java,v 1.10 2005/01/20 21:57:06 cananian Exp $

Author:

Felix S. Klock II <pnkfelix@mit.edu>

Nested Class Summary

static class	RegAlloc.Factory
static interface	RegAlloc.IntermediateCode IntermediateCode is a code which has been register allocated but the architecture-specific spill instructions and method prologue/epilogue have not been inserted yet.
static interface	RegAlloc.IntermediateCodeFactory IntermediateCodeFactory is an HCodeFactory that is guaranteed to produce IntermediateCodes.
protected class	RegAlloc.RestoreProxy
static class	RegAlloc.SpillLoad Class for RegAlloc usage in loading registers.
protected class	RegAlloc.SpillProxy
static class	RegAlloc.SpillStore Class for RegAlloc usage in spilling registers.

Field Summary

protected BasicBlock.Factory	bbFact BasicBlock.Factory for BasicBlocks of this.code.
protected HashSet	checked Tracks Instrs that have been verified for debugging purposes.
protected Code	code Generic.Code for this.
static boolean	DEBUG Flags whether debugging information should be printed to System.out.
protected Frame	frame Generic.Frame for this.
static RegAlloc.Factory	GLOBAL
static RegAlloc.Factory	LOCAL
static boolean	TIME Flags whether timing information should be printed to System.out.

Constructor Summary

protected

RegAlloc(Code code) Creates a RegAlloc.

Method Summary

static RegAlloc.IntermediateCodeFactory	abstractSpillFactory(HCodeFactory parent, Frame frame) Produces an IntermediateCodeFactory which can be used to extract Derivation information about code it generates.
static RegAlloc.IntermediateCodeFactory	abstractSpillFactory(HCodeFactory parent, Frame frame, RegAlloc.Factory raFact)
protected boolean	allRegs(Collection c)
protected void	back(Instr instr, Instr back) adds a mapping instr to back in to the BackedInstrs.
static HCodeFactory	codeFactory(HCodeFactory parentFactory, Frame frame) Creates a register-allocating HCodeFactory for "instr" form.
static HCodeFactory	codeFactory(HCodeFactory pFact, Frame frame, RegAlloc.Factory raFact)
protected BasicBlock.Factory	computeBasicBlocks() Computes BasicBlocks for the Code associated with this.
static HCodeFactory	concreteSpillFactory(RegAlloc.IntermediateCodeFactory parent, Frame frame) Produces an HCodeFactory which will transform the abstract spills into concrete spills.
List	expand(Temp t) Returns a List of the Component Temps that compose t
protected void	fixupSpillCode() Replaces the proxy instructions with symbolic loads and stores.
protected abstract void	generateRegAssignment() Assigns registers in the code for this.
protected Instr	getBack(Instr i) returns the root backing i.
protected abstract Derivation	getDerivation() returns a Derivation for analyses to use on the register-allocated code.
protected CFGrapher	getGrapherFor(InstrGroup.Type t) (Helper method) Returns a CFGrapher that treats InstrGroups of Type t as single atomic elements.
protected UseDefer	getUseDeferFor(InstrGroup.Type t) (Helper method) Returns a UseDefer that treats InstrGroups of Type t as single atomic elements.
protected boolean	hasRegister(Collection c) Checks if any element of c is a register (Helper method).
protected boolean	isRegister(Temp t) Checks if t is a register (Helper method).
protected static boolean	lastUse(Temp reg, UseDefable i, Iterator iter) Checks if i is last use of reg in the block of instructions listed in iter.
protected Iterator	reachableInstrs() Iterates over a view of the code which skips over instrs that are not in our basic block set.
protected void	replace(Instr orig, Instr repl) replaces 'orig' with 'repl', and modifies internal data structures to reflect that replacement as necessary.
protected List	resolveOutstandingTemps() Transforms Temp references for this into appropriate offsets from the Stack Pointer in the Memory.
protected RegFileInfo	rfi() (Helper method) Returns the RegFileInfo for the frame of the code being analyzed.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEBUG

public static final boolean DEBUG

Flags whether debugging information should be printed to System.out.

See Also:

Constant Field Values

TIME

public static final boolean TIME

Flags whether timing information should be printed to System.out.

See Also:

Constant Field Values

frame

protected Frame frame

Generic.Frame for this.

code

protected Code code

Generic.Code for this.

bbFact

protected BasicBlock.Factory bbFact

BasicBlock.Factory for BasicBlocks of this.code.

checked

protected HashSet checked

Tracks Instrs that have been verified for debugging purposes.

GLOBAL

public static final RegAlloc.Factory GLOBAL

LOCAL

public static final RegAlloc.Factory LOCAL

Constructor Detail

RegAlloc

protected RegAlloc(Code code)

Creates a RegAlloc. RegAllocs are each associated with a unique Code which they are responsible for performing register allocation and assignment for.
modifies: `this.{frame, code, bbFact}'
effects: sets the frame, code in accordance with the code argument, and computesBasicBlocks.

Method Detail

getGrapherFor

protected CFGrapher getGrapherFor(InstrGroup.Type t)

(Helper method) Returns a CFGrapher that treats InstrGroups of Type t as single atomic elements.

getUseDeferFor

protected UseDefer getUseDeferFor(InstrGroup.Type t)

(Helper method) Returns a UseDefer that treats InstrGroups of Type t as single atomic elements.

rfi

protected final RegFileInfo rfi()

(Helper method) Returns the RegFileInfo for the frame of the code being analyzed.

back

protected void back(Instr instr,
                    Instr back)

adds a mapping instr to back in to the BackedInstrs.

replace

protected void replace(Instr orig,
                       Instr repl)

replaces 'orig' with 'repl', and modifies internal data structures to reflect that replacement as necessary.

getBack

protected Instr getBack(Instr i)

returns the root backing i. Instrs not present in BackedInstrs are their own root.

fixupSpillCode

protected void fixupSpillCode()

Replaces the proxy instructions with symbolic loads and stores. (The proxys don't have register assignment info internally, the new instructions do.)

getDerivation

protected abstract Derivation getDerivation()

returns a Derivation for analyses to use on the register-allocated code. This allows for register allocation routines to make transformations on the code and still allow Derivation information to propagate to later analyses.
requires: this.generateRegAssignment() has been called.

computeBasicBlocks

protected BasicBlock.Factory computeBasicBlocks()

Computes BasicBlocks for the Code associated with this.
requires: `this.code' has been set

Returns:

a basic-block factory for `this.code', using the default control-flow view of the code.

reachableInstrs

protected Iterator reachableInstrs()

Iterates over a view of the code which skips over instrs that are not in our basic block set. This is a useful notion because many of the datastructures used for register allocation barf if given an instruction that wasn't in a basic block (such as a element in a data-table). Note that this method uses the basic-block structure as the basis for its data, so if computeBasicBlocks() is overriden, the behavior of the iteration may change.

Note also that if the compiler emits dead code, the instrs in such code will not ever be yielded from this, but MAY indeed be yielded from code.getElementsI(). Since FLEX seems to be emitting unreachable code in certain cases, an allocator may want still provide some bogus assignment so that we don't die in an assertion failure in this module. Or perhaps one would prefer to fix the earlier part that is generating unreachable code. C:P

generateRegAssignment

protected abstract void generateRegAssignment()

Assigns registers in the code for this.
effects: Partially or completely allocates registers for the values defined and used in the code for this. Values will be preserved in the code; any live value will be stored before its assigned register is overwritten.
Loads and Stores in general are added in the form of SpillLoads and SpillStores; the main RegAlloc class will use resolveOutstandingTemps() to replace these "fake" loads and stores with frame specified Memory instructions.

See Also:

resolveOutstandingTemps()

codeFactory

public static HCodeFactory codeFactory(HCodeFactory pFact,
                                       Frame frame,
                                       RegAlloc.Factory raFact)

codeFactory

public static HCodeFactory codeFactory(HCodeFactory parentFactory,
                                       Frame frame)

Creates a register-allocating HCodeFactory for "instr" form.
requires: parentFactory produces code in a derivative of "instr" form.
effects: Produces an HCodeFactory which allocates registers in the code produced by parentFactory using the machine properties specified in frame.

abstractSpillFactory

public static RegAlloc.IntermediateCodeFactory abstractSpillFactory(HCodeFactory parent,
                                                                    Frame frame)

Produces an IntermediateCodeFactory which can be used to extract Derivation information about code it generates.
requires: parentFactory produces code in a derivative of "instr" form.
effects: Produces an IntermediateCodeFactory which allocates registers in the code produced by parentFactory using the machine properties specified in frame. Spilled temporarys are assigned a stack offset but the actual code does not have the concrete load and store instructions necessary for the spilling. In addition, the architecture specific method prologue and epilogue instructions have not been inserted either. The IntermediateCodeFactory returned can be passed to concreteSpillFactory() to produce a code factory suitable for generating runnable assembly code.

abstractSpillFactory

public static RegAlloc.IntermediateCodeFactory abstractSpillFactory(HCodeFactory parent,
                                                                    Frame frame,
                                                                    RegAlloc.Factory raFact)

allRegs

protected boolean allRegs(Collection c)

concreteSpillFactory

public static HCodeFactory concreteSpillFactory(RegAlloc.IntermediateCodeFactory parent,
                                                Frame frame)

Produces an HCodeFactory which will transform the abstract spills into concrete spills.
effects: Produces an HCodeFactory which takes the codes produced by parent, finds the code spilling abstract stack-offset Temps (generated by parent) and replaces it with concrete, architecture-dependant spill code.

resolveOutstandingTemps

protected final List resolveOutstandingTemps()

Transforms Temp references for this into appropriate offsets from the Stack Pointer in the Memory.
modifies: this
effects: Replaces the SpillLoad and SpillStores with memory instructions for the appropriate Frame. Returns a three-elem list (instr, tempLocator, numLocals) :: Instr x TempLocator x Integer

expand

public List expand(Temp t)

Returns a List of the Component Temps that compose t

hasRegister

protected boolean hasRegister(Collection c)

Checks if any element of c is a register (Helper method).
requires: c is a Collection of Temps.
effects: If c contains any Register Temps, returns true. Else returns false.

isRegister

protected boolean isRegister(Temp t)

Checks if t is a register (Helper method).
effects: If t is a register for the frame associated with this, then returns true. Else returns false.

lastUse

protected static boolean lastUse(Temp reg,
                                 UseDefable i,
                                 Iterator iter)

Checks if i is last use of reg in the block of instructions listed in iter.
requires:
1. i is an element in iter
2. iter is an Iterator of a linear series of Instrs in the order that they will be executed.
3. iter is currently indexed at i
modifies: iter
effects:
1. Returns true if no instruction after i in iter uses reg before reg is redefined (i redefining reg is sufficient). Else returns false.
2. iter is left at an undetermined index.