Register allocation and spilling, the easy way?

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 on Wikipedia), 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:

1. Correctness -- an algorithm that will generate correct code regardless of how many local variables there are.
2. Simplicity -- something I can understand without having to read too much literature.
3. Efficiency -- it needs to be better than the current method, which is:

Translate an operation x = y # z to:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

As I'm targeting Intel 386, some relevant constraints are:

• Binary operations take two arguments, one of which is a source and destination. Unary operations take a single argument.
• Operations can only access one memory location; binary operations therefore need at least one argument in a register.
• There is a maximum of six registers available: %eax %ebx %ecx %edx %esi %edi. (%ebp could also be included as a last resort.)
• There are special cases such as for integer division and return registers, but I can ignore them for now.

There are three steps the compiler gets through at the moment:

• i386ification: all operations are converted to a form a = a # b (or a = #a for unary operations).
• Liveness analysis: the sets of live variables before and after each operation are determined.
• Register allocation: an interference graph is built and coloured.

And then the compiler throws its crayons in the air and doesn