harpoon.Backend.Generic
Class RegFileInfo

java.lang.Object
  harpoon.Backend.Generic.RegFileInfo

All Implemented Interfaces:

Serializable

Direct Known Subclasses:

RegFileInfo, RegFileInfo, RegFileInfo

public abstract class RegFileInfo
extends Object
implements Serializable

RegFileInfo defines an interface that general program analyses can call to find out architecture specific information about the target machine's register file.

A note about Temps: several types of Temps are mentioned in this interface, and the differences between them are worth noting.

A Temp, as used in the rest of the compiler, is a variable suitable for storing some value in. They are temporary storage for intermediate values. I will refer to them as Flex Temps for the remainder of this discussion, to avoid confusion with other kinds of Temps. A Physical Register Temp is a special Temp for representing a physical register in the specific architecture's register file. Some kinds of Flex Temps may require multiple Physical Register Temps to fit in the register file, depending on the variable type and the types of registers offered by the architecture. A Virtual Register Temp is a abstraction of a Physical Register Temp (or several of them): it is not any specific register in the register file, it just represents a location that is somewhere in the register file.

The idea is that the register allocator will first figure out at which points in the program the various Flex Temps will be in the register file, and where the various Loads and Stores for maintaining the state of the register file will go. However, the allocator does not have to actually assign specific Physical Register Temps to the Flex Temps if it does want to; it can delay that until later in the allocation process. This allows for Local and Global Allocation to work together, because Local Allocation can work with Virtual Register Temps, and then the Global Allocator can merge Virtual Registers in different Basic Blocks together before mapping them to Physical Register Temps.

Version:

$Id: RegFileInfo.java,v 1.6 2004/02/08 01:57:30 cananian Exp $

Author:

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

See Also:

Serialized Form

Nested Class Summary

static interface	RegFileInfo.CommonLoc Common super class for StackOffsetLoc and MachineRegLoc.
static interface	RegFileInfo.MachineRegLoc Represents Machine Register Temps.
static class	RegFileInfo.SpillException SpillException tells a register allocator which Temps are appropriate for spilling in order to allocate space for another Temp.
static interface	RegFileInfo.StackOffsetLoc Represents Stack Offset Temps.
static interface	RegFileInfo.TempLocator Defines function from (Temp x DefPoint) -> Set of CommonLoc.

Constructor Summary

RegFileInfo()
Creates a RegFileInfo.

Method Summary

Collection	allRegs() Returns all of the available registers on this architecture.
List	assignment(Temp needy, Collection occupied) Returns a List of Reg that can hold needy, given that the Regs in occupied are not available to hold needy.
List	expand(Temp t) Returns a List of the Component Temps that compose t.
abstract Temp[]	getAllRegisters() Returns an array of Temps which represent all the available registers on the machine.
Collection	getAllRegistersC() Returns a Collection of Temps which represent all the available registers on the machine.
abstract Temp[]	getGeneralRegisters() Returns an array of Temps for all the registers that the register allocator can feel free to play with
Collection	getGeneralRegistersC() Returns a Collection of Temps for all the registers that the register allocator can feel free to play with
Set	getRegAssignments(Temp t) Produces a mutable Set of register assignments that can hold t.
Temp	getRegister(int index) Returns a specific register on the machine.
Collection	illegal(Temp t) Returns the Regs that can never hold t.
abstract boolean	isRegister(Temp t) Checks if t is a element of the register file for this architecture.
abstract Set	liveOnExit() Returns the Set of registers live at a method's exit.
int	maxRegIndex() Defines the upper bound on possible indexes for MachineRegLocs.
int	occupancy(Temp t) Returns the number of slots that t's assigned register sequence occupies in the register file.
int	pressure(Temp a, Temp b) Returns the degree of conflict that b inflicts upon a if the two Temps interfere.
Iterator	suggestRegAssignment(Temp t, Map regfile, Collection preassignedTemps) Analyzes regfile to find free registers that t can be assigned to.

Methods inherited from class java.lang.Object

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

Constructor Detail

RegFileInfo

public RegFileInfo()

Creates a RegFileInfo.

Method Detail

maxRegIndex

public int maxRegIndex()

Defines the upper bound on possible indexes for MachineRegLocs.

liveOnExit

public abstract Set liveOnExit()

Returns the Set of registers live at a method's exit.
effects: Returns an unmodifiable Set of register Temps of the registers that should be considered live at the end of a method.

isRegister

public abstract boolean isRegister(Temp t)

Checks if t is a element of the register file for this architecture.
effects: If t is an element of the register file, Then returns true, Else returns false.

Parameters:

t - Temp that may be part of the register file.

occupancy

public int occupancy(Temp t)

Returns the number of slots that t's assigned register sequence occupies in the register file.

The default implementation returns 1; subclasses should override to account for how their respective architectures handle multi-register temps (such as longs or doubles). In any case, should always return an integer greater than zero.

pressure

public int pressure(Temp a,
                    Temp b)

Returns the degree of conflict that b inflicts upon a if the two Temps interfere.

The default implementation returns 1; subclasses should override to account for how their respect architectures constrain the assignment of multi-register temps (such as longs or doubles).

Also, if the two registers can never be assigned to the same register bank, then it is valid for this method to return 0.

For advice on choosing an appropriate number to return, see the paper "Coloring Register Pairs" by Briggs, Cooper, and Torczon. The mappings recommended by that paper are (double,single) => 2 and (double,double) => 2 [or 3].

assignment

public List assignment(Temp needy,
                       Collection occupied)

Returns a List of Reg that can hold needy, given that the Regs in occupied are not available to hold needy.

Note that the returned List is not a list of possible assignments, but rather a single assignment that may span more than one register. Thus the length of the returned List should equal this.occupies(needy).

Returns null if no assignment is available in the situation where all registers in occupied are in use.

illegal

public Collection illegal(Temp t)

Returns the Regs that can never hold t.

This method is used to increase the degree of Temps which have limited assignments in the register file. For example, if t is a Temp that can only be assigned to a certain register bank, this method will return a Collection containing all of the registers in the other register banks.

allRegs

public Collection allRegs()

Returns all of the available registers on this architecture.

getRegAssignments

public Set getRegAssignments(Temp t)

Produces a mutable Set of register assignments that can hold t. FSK: experimental method.
requires: t is not a physical register Temp.
effects: Returns a Set of possible register assignments for t, where each assignment is an unmodifiable List of Register Temps. The elements of each List are ordered according to proper placement of the Register-bitlength words of the value in t, low-order words first. Every list returned will have the same length. The Set returned may be a SortedSet, in which case the earlier assignments are favored over later ones.

suggestRegAssignment

public Iterator suggestRegAssignment(Temp t,
                                     Map regfile,
                                     Collection preassignedTemps)
                              throws RegFileInfo.SpillException

Analyzes regfile to find free registers that t can be assigned to. (FSK: Need to update this method to incorporate knowledge of Virtual Register Temps (perhaps it is guaranteed not to throw a SpillException when given a Virtual Register Temp))
effects: Either returns an Iterator of possible assignments (though this is not guaranteed to be a complete list of all possible choices, merely the ones that this RegFileInfo chose to find), or throws a RegFileInfo.SpillException with a set of possible spills.

Note to implementors: Resist the urge to generate an Iterator that produces all possible assignments in series. In general, register allocation algorithms need to, at some point, construct an interference graph to represent how the registers should be assigned. Such a graph would contain a node for each register assignment (and put interference edges between assignments that were not allowed for a given Temp), which means that even if your Iterator did not keep all of the assignments in memory at once, code that USES your Iterator may very well do so. Thus, while there may be many assignments for a Temp that occupies more than one register, and it is possible to write an Iterator that produces all such assignments, such an Iterator would cause an time/space explosion when applied to a decently sized register file.
Also, realize that it is not enough to ensure that any one of the set { of possible Iterators that may be returned } traverses a reasonably small subset of the assignment space; you must ensure that the UNION of all possible traversals is of a reasonable size. This is because the interference graph that is constructed will not be built from just one Suggestion Iterator, but rather from an Suggestion Iterator for each variable that is given a register assignment.

Parameters:

t - Temp that needs to be assigned to a set of Registers.

regfile - A mapping from Register Temps to NonRegister Temps representing the current state of the register file. Empty Register Temps should simply not have an entry in regfile (as opposed to the alternative of mapping to some NoValue object).

Returns:

A List Iterator of Register Temps. The Iterator is guaranteed to have at least one element. Each List represents a safe place for the value in t to be stored (safe with regard to the architecture targeted and the type of t, not with regard to the current contents of regfile or the data-flow of the procedure being analyzed). The elements of each List in the Iterator returned are ordered according to proper placement of the Register-bitlength words of the value in t, low-order words first.

Throws:

RegFileInfo.SpillException - if the register file represented by regfile does not have any Register Temps free to hold a new value of the type of t. This exception will contain the necessary information to spill some set of registers. After spilling, a second call to suggestRegAssignment() can not throw an exception, as long as no new values have been loaded into the register file since the point of spilling.

getAllRegisters

public abstract Temp[] getAllRegisters()

Returns an array of Temps which represent all the available registers on the machine.

getAllRegistersC

public Collection getAllRegistersC()

Returns a Collection of Temps which represent all the available registers on the machine.

expand

public List expand(Temp t)

Returns a List of the Component Temps that compose t. If t is not a Composite Temp (ie, it maps directly to a single register in the Register File) then the singleton List [ t ] is returned. Note that the default implementation assumes that t is not a Composite Temp; architectures with Composite Temps should override and properly implement this method.

getRegister

public Temp getRegister(int index)

Returns a specific register on the machine.
getRegister(index)==getAllRegisters()[index]

getGeneralRegisters

public abstract Temp[] getGeneralRegisters()

Returns an array of Temps for all the registers that the register allocator can feel free to play with

getGeneralRegistersC

public Collection getGeneralRegistersC()

Returns a Collection of Temps for all the registers that the register allocator can feel free to play with