title: Register allocation and spilling, the easy way?
body: <p>I'm looking for a way to allocate local variables to registers.  I'm aware of a couple of serious methods for doing it (namely, those mentioned <a href="http://en.wikipedia.org/wiki/Register_allocation" rel="noreferrer">on Wikipedia</a>), but I'm stuck on how "spilling" is accomplished.  Also, the relevant literature is quite intimidating.  I'm hoping there's something simpler that will satisfy my priorities:</p>
  
  <ol>
  <li>Correctness -- an algorithm that will generate correct code regardless of how many local variables there are.</li>
  <li>Simplicity -- something I can understand without having to read too much literature.</li>
  <li>Efficiency -- it needs to be better than the current method, which is:</li>
  </ol>
  
  <p>Translate an operation <code>x = y # z</code> to:</p>
  
  <pre><code>movl y, %eax
  movl z, %ebx
  op %ebx, %eax
  movl %eax, x
  </code></pre>
  
  <p>As I'm targeting Intel 386, some relevant constraints are:</p>
  
  <ul>
  <li>Binary operations take two arguments, one of which is a source and destination.  Unary operations take a single argument.</li>
  <li>Operations can only access one memory location; binary operations therefore need at least one argument in a register.</li>
  <li>There is a maximum of six registers available: <code>%eax</code> <code>%ebx</code> <code>%ecx</code> <code>%edx</code> <code>%esi</code> <code>%edi</code>.  (<code>%ebp</code> could also be included as a last resort.)</li>
  <li>There are special cases such as for integer division and return registers, but I can ignore them for now.</li>
  </ul>
  
  <p>There are three steps the compiler gets through at the moment:</p>
  
  <ul>
  <li>i386ification: all operations are converted to a form <code>a = a # b</code> (or <code>a = #a</code> for unary operations).</li>
  <li>Liveness analysis: the sets of live variables before and after each operation are determined.</li>
  <li>Register allocation: an interference graph is built and coloured.</li>
  </ul>
  
  <p>And then the compiler throws its crayons in the air and doesn't know what to do next.</p>
  
  <h2>Example</h2>
  
  <pre><code>public int mf(int cr, int ci) {
      int i = 0;
      int zr = 0;
      int zi = 0;
  
      while (i &lt; 100 &amp;&amp; zr*zr + zi*zi &lt; 4) {
          int t = zr * zr - zi * zi + cr;
          zi = 2 * zr * zi + ci;
          zr = t;
  
          i = i + 1;
      }
      return i;
  }
  </code></pre>
  
  <p>Here's the rather pretty interference graph for the function, and the CFG with liveness information.  The CFG image does require some vertical scrolling, unfortunately.</p>
  
  <ul>
  <li><a href="https://imgur.com/po88z.png" rel="noreferrer">Interference graph for a function on 14 variables</a></li>
  <li><a href="https://imgur.com/SVyOe.png" rel="noreferrer">Control-flow graph for a function, with liveness information</a></li>
  </ul>
  
  <p>Seven colours were used.  I would like to spill one of them (or the set of variables assigned that colour).  The method of choosing which isn't too important.  What gets tricky is how to deal with the spilt variables.</p>
  
  <p>Let's say I spill "pink", which is the set of variables <code>t</code>, <code>$t4</code>, <code>$t7</code>.  This means that those operations referring to one of these variables will access it from its position on the stack frame, rather than through a register.  This should work for this example.</p>
  
  <p>But what if the program was:</p>
  
  <pre><code>...
  a = a + b
  ...
  </code></pre>
  
  <p>and both <code>a</code> and <code>b</code> had to be spilled?  I can't emit an instruction <code>addl b, a</code> with two memory addresses.  I would need another spare register to temporarily hold one of the operands, and that means spilling another colour.  This suggests a general method of:</p>
  
  <ol>
  <li>If all variables can be coloured with <code>r</code> colours, great!</li>
  <li>Otherwise, spill some colours and their associated variables.</li>
  <li>If an operation exists that accesses two spilled variables, spill another colour and use the spare register for temporary storage for all such operations.</li>
  </ol>
  
  <p>At this point I would suspect that a lot more stuff is being spilled than necessary, and wonder if there is some smarter way to spill things, such as spilling part of a variable's lifetime, rather than the whole variable itself.  Are there some simple(ish) techniques that I could use here?  Again, I'm not aiming particularly high -- certainly not high enough to require reading anything too deep.  ;-)</p>
  
  <h2>Specific problems</h2>
  
  <p>The main specific problem is: when a variable is spilled, how does this affect the instructions generated?  Do all instructions using that variable need to access it directly in memory (from its stack position) ?  How will this work if an operation uses two spilled variables?  (The architecture does not permit instructions to access two distinct memory locations.)</p>
  
  <p>Secondary problems are:</p>
  
  <ul>
  <li>How do I determine where to insert load/store instructions, for correctness (and less importantly, efficiency) ?</li>
  <li>Can I spill a variable for only that part of its lifetime when it is not in immediate use, and unspill it later?  So that all instructions act on unspilled registers.  A variable might live in different registers at different times.</li>
  <li>Can I be a little more efficient with special cases.  For example, <code>%eax</code> is used for the return value, so it would be nice if the variable to be returned happened to be allocated to that register by the time the return was encountered.  Similarly, some registers are "callee-save", so if fewer variables happened to be live at the time of a function call, having them allocated to non-callee-save registers would mean I can avoid storing those registers.</li>
  <li>Would SSA form help much (if at all) ?  Being able to eliminate common subexpressions and evaluate constants might reduce(?) register pressure, but otherwise would it have any effect?</li>
  </ul>
  
  <p>The aspects I'm not concerned about (right now) are:</p>
  
  <ul>
  <li>Stack allocation and optimisation: it's implemented naively already, and can be optimised using the interference graph if need be.</li>
  <li>Compile-time efficiency, just as long as it terminates.  (NP-completeness does not imply a given algorithm should be avoided.)</li>
  </ul>
  
  <h2>Update</h2>
  
  <p>Sorry about the downtime -- I've been thinking about the answers given and trying to find an easy approach to take to start implementing some of the ideas.  To be honest, I've been procrastinating... :-\</p>
  
  <p>I found the very nice presentation (PPT, sadly):</p>
  
  <p><a href="http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt" rel="noreferrer">http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt</a></p>
  
  <p>Which answers the question about how to deal with specific operation needs (like using the same register for source and destination; or needing a certain register for some operations).  What I'm not sure about is whether the Liveness-Colouring-Allocation cycle terminates.</p>
  
  <p>I'll try to do some actual work soon and hopefully close the question.</p>