harpoon.Analysis.Instr
Class AppelRegAlloc

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

Direct Known Subclasses:

AppelRegAllocFsk, AppelRegAllocStd

public abstract class AppelRegAlloc
extends RegAlloc

AppelRegAlloc

Version:

$Id: AppelRegAlloc.java,v 1.7 2004/02/08 04:55:22 cananian Exp $

Author:

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

Nested Class Summary

Nested classes/interfaces inherited from class harpoon.Analysis.Instr.RegAlloc

RegAlloc.Factory, RegAlloc.IntermediateCode, RegAlloc.IntermediateCodeFactory, RegAlloc.RestoreProxy, RegAlloc.SpillLoad, RegAlloc.SpillProxy, RegAlloc.SpillStore

Field Summary

static boolean	CHECK_INV
protected HashSet	dontSpillTheseDefs
static boolean	PRINT_CLEANING_INFO
static boolean	PRINT_DEPTH_TO_SPILL_INFO
static boolean	PRINT_HEURISTIC_INFO

Fields inherited from class harpoon.Analysis.Instr.RegAlloc

bbFact, checked, code, DEBUG, frame, GLOBAL, LOCAL, TIME

Constructor Summary

protected

AppelRegAlloc(Code code)

Method Summary

protected abstract void	addEdge(harpoon.Analysis.Instr.AppelRegAllocClasses.Node u, harpoon.Analysis.Instr.AppelRegAllocClasses.Node v) Introduces an edge between u and v in both the interference graph and in the neighbor lists for u and v.
protected Iterator	allNodes()
void	appelLoopBody(SpillHeuristics.SpillHeuristic sh)
protected abstract void	assignColors() Gives the nodes a legal color assignment.
protected abstract void	buildInterferenceGraph() Builds the interference graph for the code.
protected abstract void	checkDegreeInv() Checks degree invariant documented in Tiger book; abstract because a variant of the algorithm breaks it on purpose.
void	checkDisjointInv()
void	checkFreezeWorklistInv()
void	checkInv()
protected void	checkpointState() Saves the current state of this for later retrieval using resetState().
void	checkPrecolored()
void	checkSimplifyWorklistInv()
void	checkSpillWorklistInv()
void	coalesce()
void	coalesce(harpoon.Analysis.Instr.AppelRegAllocClasses.Move m, harpoon.Analysis.Instr.AppelRegAllocClasses.Node x, harpoon.Analysis.Instr.AppelRegAllocClasses.Node y)
protected Temp[]	colorToReg()
protected abstract boolean	conservative(harpoon.Analysis.Instr.AppelRegAllocClasses.Node u, harpoon.Analysis.Instr.AppelRegAllocClasses.Node v) conservative coalescing heuristic due to Preston Briggs.
protected abstract void	decrementDegree(harpoon.Analysis.Instr.AppelRegAllocClasses.Node m, harpoon.Analysis.Instr.AppelRegAllocClasses.Node n) Updates m to account for n being removed from the interference graph.
protected harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter	def(Instr i)
protected Collection	defCN(Instr i)
protected Collection<Temp>	defCT(Instr i)
protected void	enableMoves(harpoon.Analysis.Instr.AppelRegAllocClasses.Node node)
protected void	enableMoves(harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter nodes)
protected Instr	firstStm(BasicBlock b)
void	freeze()
void	generateRegAssignment() Assigns registers in the code for this.
protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node	getAlias(harpoon.Analysis.Instr.AppelRegAllocClasses.Node n)
Derivation	getDerivation() returns a Derivation for analyses to use on the register-allocated code.
protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node	getNode(int i)
protected void	initializeSets()
protected Instr	lastStm(BasicBlock b)
protected Set	liveOut(BasicBlock b)
protected abstract void	makeInitial(Temp t) Creates node(s) for t in the interference graph.
protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node	makePrecolored(Temp reg)
void	makeWorklist() Moves Nodes from initial to appropriate set in { spill, freeze, simplify }_worklist.
protected SpillHeuristics.SpillHeuristic	minimum(SpillHeuristics.SpillHeuristic[] h) Finds the minimum cost heuristic in h.
boolean	moveRelated(harpoon.Analysis.Instr.AppelRegAllocClasses.Node n)
protected abstract List	nodesFor(harpoon.Analysis.Instr.AppelRegAllocClasses.Web w) Returns a List of Node mapped to by w.
protected harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter	nodesIter(Iterator i)
protected abstract void	performFinalAssignment(Temp[] regs) Gives each Instr in the code a register assignment.
protected Instr	pred(Instr i)
protected void	resetState() Restores the state of this to the state it was in on the last call to checkpointState().
void	rewriteProgram()
void	simplify()
protected String	spillStats(int[] stats)
protected String	stateString()
protected Set	tempCtoNodes(Collection temps, Instr i)
protected Collection	useCN(Instr i)
protected Collection<Temp>	useCT(Instr i)
protected harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter	usedef(Instr i)
protected harpoon.Analysis.Instr.AppelRegAllocClasses.Web	webFor(Temp t, Instr i)
protected List	webToRegAssignment(harpoon.Analysis.Instr.AppelRegAllocClasses.Web w)

Methods inherited from class harpoon.Analysis.Instr.RegAlloc

abstractSpillFactory, abstractSpillFactory, allRegs, back, codeFactory, codeFactory, computeBasicBlocks, concreteSpillFactory, expand, fixupSpillCode, getBack, getGrapherFor, getUseDeferFor, hasRegister, isRegister, lastUse, reachableInstrs, replace, resolveOutstandingTemps, rfi

Methods inherited from class java.lang.Object

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

Field Detail

PRINT_DEPTH_TO_SPILL_INFO

public static final boolean PRINT_DEPTH_TO_SPILL_INFO

See Also:

Constant Field Values

PRINT_HEURISTIC_INFO

public static final boolean PRINT_HEURISTIC_INFO

See Also:

Constant Field Values

PRINT_CLEANING_INFO

public static final boolean PRINT_CLEANING_INFO

See Also:

Constant Field Values

CHECK_INV

public static final boolean CHECK_INV

See Also:

Constant Field Values

dontSpillTheseDefs

protected HashSet dontSpillTheseDefs

Constructor Detail

AppelRegAlloc

protected AppelRegAlloc(Code code)

Method Detail

spillStats

protected String spillStats(int[] stats)

getDerivation

public Derivation getDerivation()

Description copied from class: RegAlloc

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.

Specified by:

getDerivation in class RegAlloc

checkInv

public void checkInv()

checkPrecolored

public void checkPrecolored()

checkDisjointInv

public void checkDisjointInv()

checkDegreeInv

protected abstract void checkDegreeInv()

Checks degree invariant documented in Tiger book; abstract because a variant of the algorithm breaks it on purpose. The invariant, as given in the Tiger book, is:

         u isIn (simplifyWorklist \/ freezeWorklist \/ spillWorklist ) ==>
           degree(u) = | adjList(u) /\ ( precolored \/ simplifyWorklist \/ 
                                         freezeWorklist \/ spillWorklist ) |
        

checkSimplifyWorklistInv

public void checkSimplifyWorklistInv()

checkFreezeWorklistInv

public void checkFreezeWorklistInv()

checkSpillWorklistInv

public void checkSpillWorklistInv()

appelLoopBody

public void appelLoopBody(SpillHeuristics.SpillHeuristic sh)
                   throws harpoon.Analysis.Instr.AppelRegAlloc.CouldntFindSpillExn

Throws:

harpoon.Analysis.Instr.AppelRegAlloc.CouldntFindSpillExn

minimum

protected SpillHeuristics.SpillHeuristic minimum(SpillHeuristics.SpillHeuristic[] h)

Finds the minimum cost heuristic in h.
requires: all h' in h have been run.

Returns:

the h' in h with minimum actualCost.

generateRegAssignment

public void generateRegAssignment()

Description copied from class: RegAlloc

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.

Specified by:

generateRegAssignment in class RegAlloc

See Also:

RegAlloc.resolveOutstandingTemps()

colorToReg

protected Temp[] colorToReg()

webToRegAssignment

protected List webToRegAssignment(harpoon.Analysis.Instr.AppelRegAllocClasses.Web w)

performFinalAssignment

protected abstract void performFinalAssignment(Temp[] regs)

Gives each Instr in the code a register assignment. This is the last step in generateRegAssignment; it is abstract because different variants have different node to color mappings and so they extract the assignments in different ways.

Parameters:

regs - (regs[i] == n.web.temp) ==> (n in precolored && n.color = i).

buildInterferenceGraph

protected abstract void buildInterferenceGraph()

Builds the interference graph for the code. Abstract because Moves need to be treated specially by this routine, and variants of the algorithm have different ways of dealing with Moves. The algorithm as given in the Tiger book is:

        forall b : blocks in program
            let live = liveOut(b)
            forall I : instructions(b) in reverse order
               if isMoveInstruction(I) then
                  live <- live \ use(I)
                  forall n : def(I) \/ use(I)
                     moveList[n] <- moveList[n] \/ I
                  worklistMoves <- worklistMoves \/ { I }
               live <- live \/ def(I)
               forall d : def(I)
                  forall l : live
                     AddEdge(l, d)
               live <- use(I) \/ ( live \ def(I) )
        

lastStm

protected Instr lastStm(BasicBlock b)

firstStm

protected Instr firstStm(BasicBlock b)

pred

protected Instr pred(Instr i)

useCT

protected Collection<Temp> useCT(Instr i)

defCT

protected Collection<Temp> defCT(Instr i)

nodesIter

protected harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter nodesIter(Iterator i)

addEdge

protected abstract void addEdge(harpoon.Analysis.Instr.AppelRegAllocClasses.Node u,
                                harpoon.Analysis.Instr.AppelRegAllocClasses.Node v)

Introduces an edge between u and v in both the interference graph and in the neighbor lists for u and v. Abstract because variants of the algorithm have different ways of handling the incrementing of the degrees and of mutating the neighbor lists.

makeWorklist

public void makeWorklist()

Moves Nodes from initial to appropriate set in { spill, freeze, simplify }_worklist. MODIFIES: initial, { spill, freeze, simplify }_worklist

moveRelated

public boolean moveRelated(harpoon.Analysis.Instr.AppelRegAllocClasses.Node n)

simplify

public void simplify()

decrementDegree

protected abstract void decrementDegree(harpoon.Analysis.Instr.AppelRegAllocClasses.Node m,
                                        harpoon.Analysis.Instr.AppelRegAllocClasses.Node n)

Updates m to account for n being removed from the interference graph. Abstract because variants of the algorithm have different ways to represent the interferences between the nodes. modifies: m, active_moves, worklist_moves, spill_worklist, freeze_worklist, simplify_worklist effects: m in Precolored ==> no changes else decrements degree of m, moving it (and associated moves) into the appropriate lists if it has crossed the threshold from K to K-1.

enableMoves

protected void enableMoves(harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter nodes)

enableMoves

protected void enableMoves(harpoon.Analysis.Instr.AppelRegAllocClasses.Node node)

coalesce

public void coalesce()

coalesce

public void coalesce(harpoon.Analysis.Instr.AppelRegAllocClasses.Move m,
                     harpoon.Analysis.Instr.AppelRegAllocClasses.Node x,
                     harpoon.Analysis.Instr.AppelRegAllocClasses.Node y)

conservative

protected abstract boolean conservative(harpoon.Analysis.Instr.AppelRegAllocClasses.Node u,
                                        harpoon.Analysis.Instr.AppelRegAllocClasses.Node v)

conservative coalescing heuristic due to Preston Briggs. Abstracting out because in the prescence of multi-slotted nodes, this changes.

getAlias

protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node getAlias(harpoon.Analysis.Instr.AppelRegAllocClasses.Node n)

freeze

public void freeze()

assignColors

protected abstract void assignColors()

Gives the nodes a legal color assignment. Abstract because different variants have different ways of mapping nodes to colors.

rewriteProgram

public void rewriteProgram()

makePrecolored

protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node makePrecolored(Temp reg)

makeInitial

protected abstract void makeInitial(Temp t)

Creates node(s) for t in the interference graph. Abstract because variants of the algorithm map Temps to nodes differently.

initializeSets

protected void initializeSets()

def

protected harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter def(Instr i)

usedef

protected harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter usedef(Instr i)

useCN

protected Collection useCN(Instr i)

defCN

protected Collection defCN(Instr i)

tempCtoNodes

protected Set tempCtoNodes(Collection temps,
                           Instr i)

liveOut

protected Set liveOut(BasicBlock b)

nodesFor

protected abstract List nodesFor(harpoon.Analysis.Instr.AppelRegAllocClasses.Web w)

Returns a List of Node mapped to by w. Abstract because variants of the algorithm map Webs to Nodes in different ways.

webFor

protected harpoon.Analysis.Instr.AppelRegAllocClasses.Web webFor(Temp t,
                                                                 Instr i)

checkpointState

protected void checkpointState()

Saves the current state of this for later retrieval using resetState(). Note that this only carries Node and Move state; additional state added by subclasses will not be checkpointed unless this method and reset state are overridden.

resetState

protected void resetState()

Restores the state of this to the state it was in on the last call to checkpointState().

stateString

protected String stateString()

getNode

protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node getNode(int i)

allNodes

protected Iterator allNodes()