docs/local-regalloc.txt

   1
   2 * Proposal for the local register allocator
   3
   4         The local register allocator deals with allocating registers
   5         for temporaries inside a single basic block, while the global
   6         register allocator is concerned with method-wide allocation of
   7         variables.
   8         The global register allocator uses callee-saved register for it's
   9         purpouse so that there is no need to save and restore these registers
  10         at call sites.
  11
  12         There are a number of issues the local allocator needs to deal with:
  13         *) some instructions expect operands in specific registers (for example
  14                 the shl instruction on x86, or the call instruction with thiscall
  15                 convention, or the equivalent call instructions on other architectures,
  16                 such as the need to put output registers in %oX on sparc)
  17         *) some instructions deliver results only in specific registers (for example
  18                 the div instruction on x86, or the call instructionson on almost all
  19                 the architectures).
  20         *) it needs to know what registers may be clobbered by an instruction
  21                 (such as in a method call)
  22         *) it should avoid excessive reloads or stores to improve performance
  23
  24         While which specific instructions have limitations is architecture-dependent,
  25         the problem shold be solved in an arch-independent way to reduce code duplication.
  26         The register allocator will be 'driven' by the arch-dependent code, but it's
  27         implementation should be arch-independent.
  28
  29         To improve the current local register allocator, we need to
  30         keep more state in it than the current setup that only keeps busy/free info.
  31
  32         Possible state information is:
  33
  34         free: the resgister is free to use and it doesn't contain useful info
  35         freeable: the register contains data loaded from a local (there is
  36                 also info about _which_ local it contains) as a result from previous
  37                 instructions (like, there was a store from the register to the local)
  38         moveable: it contains live data that is needed in a following instruction, but
  39                 the contents may be moved to a different register
  40         busy: the register contains live data and it is placed there because
  41                 the following instructions need it exactly in that register
  42         allocated: the register is used by the global allocator
  43
  44         The local register allocator will have the following interfaces:
  45
  46         int get_register ();
  47                 Searches for a register in the free state. If it doesn't find it,
  48                 searches for a freeable register. Sets the status to moveable.
  49                 Looking for a 'free' register before a freeable one should allow for
  50                 removing a few redundant loads (though I'm still unsure if such
  51                 things should be delegated entirely to the peephole pass).
  52
  53         int get_register_force (int reg);
  54                 Returns 'reg' if it is free or freeable. If it is moveable, it moves it
  55                 to another free or freeable register.
  56                 Sets the status of 'reg' to busy.
  57
  58         void set_register_freeable (int reg);
  59                 Sets the status of 'reg' to freeable.
  60
  61         void set_register_free (int reg);
  62                 Sets the status of 'reg' to free.
  63
  64         void will_clobber (int reg);
  65                 Spills the register to the stack. Sets the status to freeable.
  66                 After the clobbering has occurred, set the status to free.
  67
  68         void register_unspill (int reg);
  69                 Un-spills register reg and sets the status to moveable.
  70
  71         FIXME: how is the 'local' information represented? Maybe a MonoInst* pointer.
  72
  73         Note: the register allocator will insert instructions in the basic block
  74         during it's operation.
  75
  76 * Examples
  77
  78         Given the tree (on x86 the right argument to shl needs to be in ecx):
  79
  80         store (local1, shl (local1, call (some_arg)))
  81
  82         At the start of the basic block, the registers are set to the free state.
  83         The sequence of instructions may be:
  84                 instruction             register status -> [%eax %ecx %edx]
  85                 start                                       free free free
  86                 eax = load local1                           mov  free free
  87                 /* call clobbers eax, ecx, edx */
  88                 spill eax                                   free free free
  89                 call                                        mov  free free
  90                 /* now eax contains the right operand of the shl */
  91                 mov %eax -> %ecx                            free busy free
  92                 un-spill                                    mov  busy free
  93                 shl %cl, %eax                               mov  free free
  94
  95         The resulting x86 code is:
  96                 mov $fffc(%ebp), %eax
  97                 mov %eax, $fff0(%ebp)
  98                 push some_arg
  99                 call func
 100                 mov %eax, %ecx
 101                 mov $fff0(%ebp), %eax
 102                 shl %cl, %eax
 103
 104         Note that since shl could operate directly on memory, we could have:
 105
 106                 push some_arg
 107                 call func
 108                 mov %eax, %ecx
 109                 shl %cl, $fffc(%ebp)
 110
 111         The above example with loading the operand in a register is just to complicate
 112         the example and show that the algorithm should be able to handle it.
 113
 114         Let's take another example with the this-call call convention (the first argument
 115         is passed in %ecx).
 116         In this case, will_clobber() will be called only on %eax and %edx, while %ecx
 117         will be allocated with get_register_force ().
 118         Note: when a register is allocated with get_register_force(), it should be set
 119         to a different state as soon as possible.
 120
 121         store (local1, shl (local1, this-call (local1)))
 122
 123                 instruction             register status -> [%eax %ecx %edx]
 124                 start                                       free free free
 125                 eax = load local1                           mov  free free
 126                 /* force load in %ecx */
 127                 ecx = load local1                           mov  busy free
 128                 spill eax                                   free busy free
 129                 call                                        mov  free free
 130                 /* now eax contains the right operand of the shl */
 131                 mov %eax -> %ecx                            free busy free
 132                 un-spill                                    mov  busy free
 133                 shl %cl, %eax                               mov  free free
 134
 135         What happens when a register that we need to allocate with get_register_force ()
 136         contains an operand for the next instruction?
 137
 138                 instruction             register status -> [%eax %ecx %edx]
 139                 eax = load local0                           mov  free free
 140                 ecx = load local1                           mov  mov  free
 141                 get_register_force (ecx) here.
 142                 We have two options:
 143                         mov %ecx, %edx
 144                 or:
 145                         spill %ecx
 146                 The first option is way better (and allows the peephole pass to
 147                 just load the value in %edx directly, instead of loading first to %ecx).
 148                 This doesn't work, though, if the instruction clobbers the %edx register
 149                 (like in a this-call). So, we first need to clobber the registers
 150                 (so the state of %ecx changes to freebale and there is no issue
 151                 with get_register_force ()).
 152                 What if an instruction both clobbers a register and requires it as
 153                 an operand? Lets' take the x86 idiv instruction as an example: it
 154                 requires the dividend in edx:eax and returns the result in eax,
 155                 with the modulus in edx.
 156
 157         store (local1, div (local1, local2))
 158
 159                 instruction             register status -> [%eax %ecx %edx]
 160                 eax = load local0                           mov  free free
 161                 will_clobber eax, edx                       free mov  free
 162                 force mov %ecx, %eax                        busy free free
 163                 set %edx                                    busy free busy
 164                 idiv                                        mov  free free
 165
 166         Note: edx is set to free after idiv, because the modulus is not needed
 167         (if it was a rem, eax would have been freed).
 168         If we load the divisor before will_clobber(), we'll have to spill
 169         eax and reload it later. If we load it just after the idiv, there is no issue.
 170         In any case, the algorithm should give the correct results and allow the operation.
 171
 172         Working recursively on the isntructions there shouldn't be huge issues
 173         with this algorithm (though, of course, it's not optimal and it may
 174         introduce excessive spills or register moves). The advantage over the current
 175         local reg allocator is that:
 176         1) the number of spills/moves would be smaller anyway
 177         2) a separate peephole pass could be able to eliminate reg moves
 178         3) we'll be able to remove the 'forced' spills we currently do with
 179                 the return value of method calls
 180
 181 * Issues
 182
 183         How to best integrate such a reg allocator with the burg stuff.
 184
 185         Think about a call os sparc with two arguments: they got into %o0 and %o1
 186         and each of them sets the register as busy. But what if the values to put there
 187         are themselves the result of a call? %o0 is no problem, but for all the
 188         next argument n the above algorithm would spill all the 0...n-1 registers...
 189
 190 * Papers
 191
 192         More complex solutions to the local register allocator problem:
 193         http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-33.html
 194
 195         Combining register allocation and instruction scheduling:
 196         http://citeseer.nj.nec.com/motwani95combining.html
 197
 198         More on LRA euristics:
 199         http://citeseer.nj.nec.com/liberatore97hardness.html
 200
 201         Linear-time optimal code scheduling for delayedload architectures
 202         http://www.cs.wisc.edu/~fischer/cs701.f01/inst.sched.ps.gz
 203
 204         Precise Register Allocation for Irregular Architectures
 205         http://citeseer.nj.nec.com/kong98precise.html
 206
 207         Allocate registers first to subtrees that need more of them.
 208         http://www.upb.de/cs/ag-kastens/compii/folien/comment401-409.2.pdf