Previous: Register Allocation for Deferred Compilation Up: Register Allocation for Deferred Compilation Next: Run-Time Register Allocation

Compile-Time Register Allocation

We first consider a strategy for performing all register allocation at compile time. The significant complication is that different stages in a program can use the same set of registers because their execution is not interleaved. For example, the powgen function presented in Section 2 can exploit the fact that computations involving the exponent and base belong to different program stages by assigning those variables to the same register: 

     powgen:  beq     r1, r0, L1
              sub     r1, r1, 1
              emit    mul     r2, r2, r1
              jmp     powgen
     L1:      emit    move    r1, r2
              ret

The usual notion of lifetime ranges does not capture this distinction, since the staging being exploited is not explicit in the source program. For example, computations involving exp and base are textually adjacent but belong to different computation stages. Conventional register allocation algorithms may nonetheless be used for deferred compilation by simply modifying the construction of the interference graph. A standard lifetime analysis can be conducted without regard to the staging of the program, followed by an analysis that determines the program stage to which each variable belongs. During construction of the interference graph, edges are only added between overlapping lifetime ranges of variables from the same program stage.

mleone@cs.cmu.edu