Implement live-range splitting in the register allocator

[ShivamSarodia]

I noticed that the following function benefits from live range splitting:

int fib(int i) {
  if(i == 0) {
    return 0;
  } else if(i == 1) {
    return 1;
  } else {
    return fib(i-1) + fib(i-2);
  }
}

As ShivyC compiles this today, the output code is about 25% slower than GCC on my machine for i = 9. ShivyC allocates i on the stack, not in a register, because it must survive a call to the fib function. GCC, on the other hand, places i into the EBX register which is not currently possible in ShivyC because ShivyC does not support callee-saved registers. When adding a range split manually, as follows, ShivyC output performance is roughly comparable to GCC:

int fib(int i) {
  if(i == 0) {
    return 0;
  } else if(i == 1) {
    return 1;
  } else {
    int i2 = i;
    return fib(i2-1) + fib(i2-2);
  }
}

Here, ShivyC keeps i in the edi register, and allocates only i2 on the stack, which improves performance significantly on the comparisons.

The paper Live Range Splitting in a Graph Coloring Register Allocator (link) looks very relevant.