Linear-scan register allocator adapted

I've adapted the SSA Linear-Scan allocator, originally designed by Mössenböck and Pfeiffer for Hotspot, for my Propeller Java compiler.

It has some advantages:

1. It's simple.


2. It's fast.


3. It does a pretty good job.


4. It can deal with destructive arithmetic ops (as in the Propeller) and pre-colored registers (as in calling conventions) easily.

Handling pre-colored registers well is particularly important to me, since I'm trying to do all lowering and allocation without leaving SSA. This includes the calling conventions. With this algorithm, it's a matter of

• Before each call, insert extra movs to clone each argument value. Pre-color these clone values with the appropriate registers in the calling convention.


• After each call, rewrite the return value to go into a temporary, which is pre-colored with the returned-result register, and which gets immediately mov-d to the right value.


• Rely on the phi-equivalence coalescing algorithm (still adapted from Pereira) to merge the non-interfering values and eliminate the copies.

I've altered Pereira's algorithm to deal with the "join families" that Mössenb&oml;/Pfeiffer generate. (Arguably in doing so I've recreated their coalesce algorithm, but hey.)

Here's a new test function with some interfering values:

  public int function(int x) {
    int y = 1;
    int z = 0;
    
    while (y < x) {
      z = y;
      y++;
    }
    
    return z;
  }

And here's the new output with the new register allocator and dramatically better interference analysis. Note that I don't actually build an interference graph at any point; not sure if this is going to come back to bite me.

Remember that the code runs backwards.

method$:L27312399
  IF_ALWAYS JMPRET prim_return_ret, #prim_return

  long @method$:L27312399
  long @method$:L11631043
  IF_ALWAYS JMPRET prim_jmplt_ret, #prim_jmplt
method$:L10840700
  IF_ALWAYS CMPS lmmr10, lmmr1

  long @method$:L10840700
  IF_ALWAYS RDWORD PC, PC
  IF_ALWAYS ADD lmmr10, #1
  IF_ALWAYS MOV lmmr10, lmmr10
method$:L11631043
  IF_ALWAYS MOV lmmr0, lmmr10

  long @method$:L10840700
  IF_ALWAYS RDWORD PC, PC
  IF_ALWAYS MOV lmmr0, #0
method
method$:L29315749
  IF_ALWAYS MOV lmmr10, #1

lmmr0 and lmmr1 are the two function arguments (x and this). We smash this almost immediately, reusing lmmr0 to hold z, since it's the register used to return values from functions.

One of these days it would be fun to take a class in this stuff, I think. These are neat problems.