Register allocation is perhaps the most important optimization performed by the back end. Like all optimizations, the register allocator takes a cluster as argument and returns a cluster as result. The signature exported is:
signature RA = sig
structure F : FLOWGRAPH
val ra : F.cluster -> F.cluster
end
The register allocator is a functor over a large number of parameters. A register allocator is obtained by instantiating the functor with both architecture specific information (such as definition/use information for the target instruction set), and user information such as number of available registers to allocate from. The functor RegAllocator implements the graph coloring register allocation algorithm described in TOPLAS v18 #3, May 1996.
functor RegAllocator
(structure RaArch : RA_ARCH_PARAMS)
(structure RaUser : RA_USER_PARAMS
sharing RaArch.I = RaUser.I) : RA
RegAllocator is implemented as a curried functor, where the parameters have been divided up into architecture and user specific parameters. Most of the architecture specific parameters are ones that need not concern a user. Therefore the register allocator for a specific architecture will be a partially applied functor (RegAllocator), to target machine specific parameters. This significantly reduces the number of parameters that a user must provide, and also ensures that the architecture specific parameters are correct.
Because of the nature of graph coloring register allocation, the allocation of different classes of registers (such as floating point and general purpose registers) must be done separately. Most architectures will require register allocation of general purpose and floating point registers, but machines like the IBM RS6000 and PowerPC chips may also perform register allocation of condition code registers. The interface RA_ARCH_PARAMS describes the set of architecture specific parameters required.
signature RA_ARCH_PARAMS = sig
structure Liveness : LIVENESS
structure InsnProps : INSN_PROPERTIES
structure I : INSTRUCTIONS
val firstPseudoR : int
val maxPseudoR : unit -> int
val regSet : I.C.cellset -> int list
val regMap : int Array.array ref list -> int Array.array ref
val defUse : I.instruction -> (int list * int list)
end
The use of most of these parameters in the allocator should be obvious, with the exception of regSet and regMap. The set of variables live on exit or entry to a block is represented by a cellset (see CELLS). A cellset is a collection of registers, and regSet extracts the registers relevant to this allocator. Spilling may introduce new temporaries, and so regMap is used to allocate a new table of register aliases and update the appropriate reference variable. The RA_USER_PARAMS describes the set of user specific parameters required. Most of the parameters required should be obvious with the exception of spill and reload
signature RA_USER_PARAMS = sig
structure I : INSTRUCTIONS
val nFreeRegs : int
val dedicated : int list
val getreg : {pref : int list, proh : int list} -> int
val copyInstr : (int list * int list) -> I.instruction
val spill :
{instr:I.instruction, reg:int}
->
{code: I.instruction list, proh:int list, instr:I.instruction option}
val reload :
{instr : I.instruction, reg : int}
->
{code:I.instruction list, proh : int list}
The nature of spill code must be a function of front end user information for several reasons:
A compiler based on activation records may wish to spill registers in a specific location of the activation frame.
RA_USER_PARAMS takes an argument of type instr: instruction, reg:int. It will always be the case that reg is defined in instr. The type returned is:
{code:instruction list, proh:int list, instr:instruction option}
code is the instruction sequence that will be inserted after the instruction (if any) where spilling has occurred. proh is a list of temporaries, that may have been introduced by this spill, but should never be spilled themselves. This just helps to improve the spill choice hueristic. The instr is usually the input instr unchanged. However, it could be NONE, if the value can be rematerialized from an immutable memory location. It may also be different from the input instr when complex addressing modes have been utilized. Consider the Intel x86 add instruction:
add t100, t200That performs
t100 := t100 + t200. In order to spill t100 the instruction may be rewritten to use a memory effective addressing mode, to become:
add 24@sp, t200Therefore if the the instruction sequence consisted of:
... instr ...
and spill{instr=instr, reg=t100} is invoked returning:
{instr=instr', proh, code}
then, the new instruction stream will be:
... instr', code, ...
There is only one exception to this -- parallel copies. Special care needs to be exercised if the target architecture has a parallel copy instruction. Consider, the parallel copy:
copy [t1, t2, ..., tn] <- [s1, s2, ..., sn]If it is required to spill
t1 one may be tempted to generate:
copy [t2, ..., tn] <- [s2, ..., sn] t1 <- s1 (spill t1)One could actually do a little better by performing peephole optimization and generate:
copy [t2, ..., tn] <- [s2, ..., sn] (spill s1 into spill location for t1)However, all of these are still wrong! The problem is that
s1 now interferes additionally with t2 to tn where it did not before the spill. The correct spill code to generate is:
(spill s1 into spill location for t1) copy [t2, ..., tn] <- [s2, ..., sn]
The register allocator knows about parallel copies and will never invoke spill with an instruction involving parallel copies. However, it will ask how to spill:
copy [d] <- [s]and will automatically rearrange the instruction stream. For reasons described above, peephole optimization must be performed.
The reload function returns something of type:
{code : instruction list, proh: int list}
proh has the same meaning as it did with spill. If the original instruction stream consisted of, ... instr ..., and reload was called, then the resulting stream would be: ... code .... The same considerations for parallel copies applies with reloading.
Submit a comment on this page
Author: Lal George
Last Modified: September 4, 1996
Copyright © 1996 Bell Laboratories