Changes between Version 27 and Version 28 of PIRCDevelopment

08/09/09 12:14:56 (12 years ago)

more on reg allc


  • PIRCDevelopment

    v27 v28  
    326326== Vanilla Register Allocator == 
     328PIRC has a built-in vanilla register allocator. The vanilla register allocator (or "register allocator" as we shall call it from now) maps PIR registers, such as $P44, $I9999, etc., to actual Parrot registers (or "PASM registers" as they are also referred to). Parrot allocates a variable number of registers per sub invocation. Some simple subs only need a few registers, whereas complex subroutines may need several tens of registers. 
     330Now, how does this work? PIR registers should be considered as "pre-declared" symbols; they are just symbols that you can use without declaring them. If you want fancy names, you would use the {{{.local}}} directive to declare them, after which you can use symbolic names (which are more descriptive than PIR registers). 
     332Basically, PIR registers and declared symbols are the same. The register allocator is reset for each subroutine. Whenever a new register is needed, it will start at 0, and increment a counter. PIR registers will always be allocated a PASM register, whereas declared symbols will only be assigned a PASM register if the symbol is actually used. This is because you could declare a bunch of {{{.local}}} symbols, but never use them. Allocating registers to them would be wasteful. 
    328334== Register Usage Optimizer == 
     336The vanilla register allocator is pretty dumb, in the sense that it does not consider the lifetime of variables. Or, put in another way, it assumes that all registers' lifetime is the complete subroutine. However, in real life, a register is typically only used in a small part of the subroutine. Consider this example: 
     340.sub main 
     342  .local int a, b, c 
     343  a = 1 
     344  b = 2 
     345  c = 3 
     351The vanilla register will allocate registers 0 to 2 to these symbols {{{a}}}, {{{b}}} and {{{c}}}. However, as you can guess, since {{{a}}} is never used after the initial assignment, there is no need to assign a different register to {{{b}}}. Likewise for {{{b}}}, which can share the same register with {{{c}}}. So, in the above example, there is really only one register needed. 
     353However, suppose we change the example into the following: 
     357.sub main 
     359  .local int a, b, c 
     360  a = 1 
     361  b = 2 
     362  c = 3 
     363  print a 
     364  print b 
     370In this case, the lifetime of {{{a}}} and {{{b}}} are extended, as both variables are used in the {{{print}}} statements. So, {{{a}}} cannot share a register with {{{b}}} nor with {{{c}}}. The rest of this subsection explains how this can be calculated. 
     372The register optimizer is a variant of the Linear Scan Register allocation algorithm as described in [ this paper]. Since that algorithm assumes there's a fixed number of registers (which is the case for hardware processors), the algorithm is changed in a few places.  
     374The implementation can be found in [source:/trunk/compilers/pirc/src/pirregalloc.c].  
    330378== Bytecode Generation ==