[llvm-dev] Register spilling fix for experimental 6502 backend

[N. E. C. via llvm-dev]

So I've been designing an experimental 6502 backend for LLVM. Link:
<https://github.com/beholdnec/llvm-m6502>

The 6502 only has a few registers, one accumulator and two indexes, none of
which are large enough to hold an absolute pointer. Because of this, the
backend really tests the power of LLVM's register allocator (RA).

I've made a change to the RA that might be of interest to devs of other
backends, read on.

Other devs suggested reserving the zero page of memory (addresses $00-$FF) and
treating it as a giant set of registers. And I don't know, because doesn't that
sort of defeat the purpose of register allocation? It might be inevitable that
we have to lie to LLVM about the 6502's registers, but, for now, I want to see
how far I can get using the allocator as intended.

The registers are A, X, and Y. They belong to a hierarchy of Register Classes:
  Acc class: A
  Index class: X, Y
  General class: Acc, Index

There's a fictional instruction "SUBidx Acc, Index". It subtracts an Index from
an Acc. Bear with me.

What if we want to subtract A from X?
We can't say "SUBidx X, A". The operands must be Acc, Index.

The DAG looks something like this:

  %vreg2 = COPY %X ; %vreg2 is Index
  %vreg0 = COPY %A ; %vreg0 is Acc
  SUBidx %vreg2, %vreg0

To make this work, we first have to swap A and X.
For technical reasons, we can't use Y as temporary storage. Instead, we must
spill to the stack.

When spilling a reg to the stack, the RA needs two virtual regs, one to store
and one to load. Currently, the loaded reg always has the same class as the
stored reg. Because of this limitation, I ran into a problem: the RA would try
to assign two Accs to physical regs, but only one is available, and the RA
would fail.

Line 1290 of InlineSpiller.cpp, inside the function spillAroundUses, says:
"// FIXME: Infer regclass from instruction alone"
(As opposed to the current behavior of always using the same class as the reg
being spilled.)
The line refers to this very limitation. It was written in 2010, so we've known
about the limitation since the beginning.

My RA patch can be found in this commit:
<https://github.com/beholdnec/llvm-m6502/commit/a4b492f63>

This patch allows spills to use a more general reg class, so a spilled Acc can
be reloaded as a General.

Previously, the RA would fail because it would spill X, but it couldn't reload
X into an Acc.

Now, with the patch, the DAG compiles into this:

  # store X to stack
  STX_stack [0]
  # transfer A to X
  TAX
  # load A from stack
  LDA_stack [0]
  # now that A and X are swapped, we can subtract!
  SUBidx A, X

It works, but I'm not sure if I used the best approach. If you're familiar with
the RA, feel free to look at the patch and leave feedback.

- Nolan