Register Allocation

Register Allocation

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} 

Spilling

The nature of spill code must be a function of front end user information for several reasons:

The spill function required by 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, t200
That 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, t200
Therefore 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.

Reloading

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  

[ INDEX | TOP | Parent | Root ]

Author: Lal George
Last Modified: September 4, 1996
Copyright © 1996 Bell Laboratories