Changes between Version 27 and Version 28 of PIRCDevelopment

Timestamp:

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

Author:

kjs

Comment:

more on reg allc

PIRCDevelopment

@@ -326 +326 @@
 == Vanilla Register Allocator ==
 
+PIRC 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.
+
+Now, 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).
+
+Basically, 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.
+
 == Register Usage Optimizer ==
 
+The 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:
+
+{{{
+
+.sub main
+
+  .local int a, b, c
+  a = 1
+  b = 2
+  c = 3
+
+.end
+
+}}}
+
+The 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.
+
+However, suppose we change the example into the following:
+
+{{{
+
+.sub main
+
+  .local int a, b, c
+  a = 1
+  b = 2
+  c = 3
+  print a
+  print b
+
+.end
+
+}}}
+
+In 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.
+
+The register optimizer is a variant of the Linear Scan Register allocation algorithm as described in [http://www.google.ie/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fwww.cs.ucla.edu%2F~palsberg%2Fcourse%2Fcs132%2Flinearscan.pdf&ei=w9F5SvzVDpOqsAa_7tyeBQ&usg=AFQjCNETIxGGy87F9GzLawd4euXEaldcnQ&sig2=Hd7nnjdQrgnOqix-8sx92g 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. 
+
+The implementation can be found in [source:/trunk/compilers/pirc/src/pirregalloc.c]. 
+
+
+
 == Bytecode Generation ==