harpoon.Backend.Generic.RegFileInfo
harpoon.Backend.StrongARM.RegFileInfo
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Object
public class RegFileInfo
RegFileInfo encapsulates information about the
StrongARM register set. This object also implements
Generic.LocationFactory, allowing the creation of
global registers for the use of the runtime.
| Nested Class Summary |
|---|
| Nested classes/interfaces inherited from class harpoon.Backend.Generic.RegFileInfo |
|---|
RegFileInfo.CommonLoc, RegFileInfo.MachineRegLoc, RegFileInfo.SpillException, RegFileInfo.StackOffsetLoc, RegFileInfo.TempLocator |
| Nested classes/interfaces inherited from interface harpoon.Backend.Generic.LocationFactory |
|---|
LocationFactory.Location |
| Constructor Summary | |
|---|---|
RegFileInfo()
Creates a RegFileInfo. |
|
| Method Summary | |
|---|---|
LocationFactory.Location |
allocateLocation(int type)
Allocate a global register of the specified type and return a handle to it. |
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. |
Set |
calleeSave()
|
Set |
callerSave()
|
List |
expand(Temp temp)
Returns a List of the Component Temps that compose t. |
Temp[] |
getAllRegisters()
Returns an array of Temps which represent all
the available registers on the machine. |
Temp[] |
getGeneralRegisters()
Returns an array 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. |
boolean |
isRegister(Temp t)
Checks if t is a element of the register file for
this architecture. |
Set |
liveOnExit()
Returns the Set of registers live at a method's
exit. |
HData |
makeLocationData(Frame f)
Create an HData which allocates static space for
any LocationFactory.Locations that have been created. |
int |
maxRegIndex()
maxRegIndex returns an upper bound on the indexes that will be returned by the MachineRegLocs for this backend. |
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 harpoon.Backend.Generic.RegFileInfo |
|---|
allRegs, getAllRegistersC, getGeneralRegistersC |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
|---|
public RegFileInfo()
RegFileInfo.
| Method Detail |
|---|
public int maxRegIndex()
MachineRegLocs for this backend.
The indexes will fall in the range
0 <= index < maxRegIndex().
This implementation returns 16, which includes system specific
registers such as PC and SP; this may be an over-conservative
value in need of revision!
maxRegIndex in class RegFileInfopublic Temp[] getAllRegisters()
RegFileInfoTemps which represent all
the available registers on the machine.
getAllRegisters in class RegFileInfopublic Temp getRegister(int index)
RegFileInfogetRegister(index)==getAllRegisters()[index]
getRegister in class RegFileInfopublic Temp[] getGeneralRegisters()
RegFileInfoTemps for all the registers
that the register allocator can feel free to play with
getGeneralRegisters in class RegFileInfopublic boolean isRegister(Temp t)
RegFileInfot is a element of the register file for
this architecture.
t is an element of the register file,
Then returns true,
Else returns false.
isRegister in class RegFileInfot - Temp that may be part of the register
file.public List expand(Temp temp)
RegFileInfot. 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.
expand in class RegFileInfopublic Set getRegAssignments(Temp t)
RegFileInfoSet of register assignments
that can hold t. FSK: experimental method.
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.
getRegAssignments in class RegFileInfo
public Iterator suggestRegAssignment(Temp t,
Map regFile,
Collection preassignedTemps)
throws RegFileInfo.SpillException
RegFileInforegfile 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))
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.
suggestRegAssignment in class RegFileInfot - 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).
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.
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.public Set liveOnExit()
RegFileInfoSet of registers live at a method's
exit.
Set
of register Temps of the registers that
should be considered live at the end of a method.
liveOnExit in class RegFileInfopublic Set callerSave()
public Set calleeSave()
public LocationFactory.Location allocateLocation(int type)
allocateLocation in interface LocationFactorytype - a IR.Tree.Type specifying the type
of the register.public HData makeLocationData(Frame f)
HData which allocates static space for
any LocationFactory.Locations that have been created.
As this implementation only allocates global registers, the
HData returned is always empty.
makeLocationData in interface LocationFactoryf - the Generic.Frame to which the
HData will belong.public int occupancy(Temp t)
RegFileInfot'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.
occupancy in class RegFileInfo
public int pressure(Temp a,
Temp b)
RegFileInfob 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].
pressure in class RegFileInfo
public List assignment(Temp needy,
Collection occupied)
RegFileInfoneedy, 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.
assignment in class RegFileInfopublic Collection illegal(Temp t)
RegFileInfot.
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.
illegal in class RegFileInfo
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||