harpoon.Analysis.Instr
Class AppelRegAllocStd

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

public class AppelRegAllocStd
extends AppelRegAlloc

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

Fields inherited from class harpoon.Analysis.Instr.AppelRegAlloc

PRINT_CLEANING_INFO, PRINT_DEPTH_TO_SPILL_INFO, PRINT_HEURISTIC_INFO

Fields inherited from class harpoon.Analysis.Instr.RegAlloc

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

Constructor Summary

AppelRegAllocStd(Code code)

Method Summary

protected 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()
protected void	assignColors() Gives the nodes a legal color assignment.
protected void	buildInterferenceGraph() Builds the interference graph for the code.
protected void	checkDegreeInv() Checks degree invariant documented in Tiger book; abstract because a variant of the algorithm breaks it on purpose.
protected void	checkpointState() Saves the current state of this for later retrieval using resetState().
protected boolean	conservative(harpoon.Analysis.Instr.AppelRegAllocClasses.Node u, harpoon.Analysis.Instr.AppelRegAllocClasses.Node v) conservative coalescing heuristic due to Preston Briggs.
protected 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.Node	getNode(int i)
protected void	initializeSets()
protected void	makeInitial(Temp t) Creates node(s) for t in the interference graph.
protected harpoon.Analysis.Instr.AppelRegAllocClasses.Node	makePrecolored(Temp t)
protected List<harpoon.Analysis.Instr.AppelRegAllocClasses.Node>	nodesFor(harpoon.Analysis.Instr.AppelRegAllocClasses.Web web) Returns a List of Node mapped to by w.
protected void	performFinalAssignment(Temp[] regs) Gives each Instr in the code a register assignment.
protected void	resetState() Restores the state of this to the state it was in on the last call to checkpointState().
protected String	stateString()

Methods inherited from class harpoon.Analysis.Instr.AppelRegAlloc

appelLoopBody, checkDisjointInv, checkFreezeWorklistInv, checkInv, checkPrecolored, checkSimplifyWorklistInv, checkSpillWorklistInv, coalesce, coalesce, colorToReg, def, defCN, defCT, enableMoves, enableMoves, firstStm, freeze, generateRegAssignment, getAlias, getDerivation, lastStm, liveOut, makeWorklist, minimum, moveRelated, nodesIter, pred, rewriteProgram, simplify, spillStats, tempCtoNodes, useCN, useCT, usedef, webFor, webToRegAssignment

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

CHECK_INV

public static final boolean CHECK_INV

See Also:

Constant Field Values

dontSpillTheseDefs

protected HashSet dontSpillTheseDefs

Constructor Detail

AppelRegAllocStd

public AppelRegAllocStd(Code code)

Method Detail

initializeSets

protected void initializeSets()

Overrides:

initializeSets in class AppelRegAlloc

nodesFor

protected List<harpoon.Analysis.Instr.AppelRegAllocClasses.Node> nodesFor(harpoon.Analysis.Instr.AppelRegAllocClasses.Web web)

Description copied from class: AppelRegAlloc

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

Specified by:

nodesFor in class AppelRegAlloc

makePrecolored

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

Overrides:

makePrecolored in class AppelRegAlloc

makeInitial

protected void makeInitial(Temp t)

Description copied from class: AppelRegAlloc

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

Specified by:

makeInitial in class AppelRegAlloc

checkDegreeInv

protected void checkDegreeInv()

Description copied from class: AppelRegAlloc

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

Specified by:

checkDegreeInv in class AppelRegAlloc

buildInterferenceGraph

protected void buildInterferenceGraph()

Description copied from class: AppelRegAlloc

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

Specified by:

buildInterferenceGraph in class AppelRegAlloc

addEdge

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

Description copied from class: AppelRegAlloc

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.

Specified by:

addEdge in class AppelRegAlloc

decrementDegree

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

Description copied from class: AppelRegAlloc

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.

Specified by:

decrementDegree in class AppelRegAlloc

conservative

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

Description copied from class: AppelRegAlloc

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

Specified by:

conservative in class AppelRegAlloc

assignColors

protected void assignColors()

Description copied from class: AppelRegAlloc

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

Specified by:

assignColors in class AppelRegAlloc

performFinalAssignment

protected void performFinalAssignment(Temp[] regs)

Description copied from class: AppelRegAlloc

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.

Specified by:

performFinalAssignment in class AppelRegAlloc

Parameters:

regs - (regs[i] == n.web.temp) ==> (n in precolored && n.color = 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()