Previous: Compile-Time Register Allocation Up: Register Allocation for Deferred Compilation

Run-Time Register Allocation

Although compile-time register allocation leads to fast run-time code generation, it suffers several limitations. Inlining and loop unrolling may occur at run time, so an exact interference graph cannot be constructed at compile time. Also, fixing the register assignment of a function at compile time makes it difficult to inline in some contexts. For example, registers must be shuffled if the formal and actual parameters are assigned to different registers, and so forth. If the number of contexts in which a function will be inlined is small, compile-time code duplication combined with fixed register assignments can be effective, but in general the space required will be prohibitive.

It is therefore desirable to perform run-time register allocation in some cases. Although register allocation can be performed on a run-time intermediate representation of code, the cost of processing such a representation is likely to pay off only when the generated code is executed many times. A more efficient strategy is to perform register allocation at compile time but defer register assignment until run time. A static approximation of the interference graph can be constructed as described in the previous section, and the run-time code generators can be parameterized by some representation of the desired register mapping. For example, powgen can perform run-time register assignment as follows: 


     powgen:  beq     r1, r0, L1
              sub     r1, r1, 1
              emit    mul     r[r3], r[r3], r[r2]
              jmp     powgen
     L1:      emit    move    r[r4], r[r3]
              ret

This function takes four arguments: the value of exp (in r1), the numbers of the registers assigned to base and accum (in r2 and r3), and the number of the destination register (in r4). The emit pseudo-instruction used here determines the operands of the emitted instruction from the contents of the specified registers. This takes more time than emitting instructions with fixed operands, but the generated code will be more efficient in contexts that would otherwise require the register shuffling described above.

The representation of register mappings has a significant impact on the cost of run-time register assignment. In the above example, register mappings are maintained in registers throughout early stages of computation; instructions can be emitted quickly because no memory access is required to determine their arguments. It remains to be seen whether this savings will in general justify the increased register pressure suffered by early computations.

mleone@cs.cmu.edu