Things that are hard about compiling to x86

It is really hard to compile arithmetic to x86 assembly because:

* (A) add x,y requires at least one of x,y to be a register.
* (B) mul x is predefined to use eax and edx registers.

These make it hard when you're trying to do register allocation because

* (A) What if you spilled x and now need to spill y? You cannot spill both
* (B) This messes with register coloring, you want to precolor the graph but the polytime algorithms (for chordal graphs, which SSA has) break if you precolor.

I'm really stuck, any advice welcome

>>1
It's "really hard" because you're thinking about it in the wrong way.

add x,y requires at least one of x,y to be a register.

So what? Just arrange for either one to be in a register when that instruction is executed. This is not specific to x86 either. Would you also complain about MIPS or ARM, where all the operands of ALU instructions need to be in registers...?

This messes with register coloring, you want to precolor the graph

I've said this multiple times before, don't use graph colouring. It's a stupid algorithm for circlejerking academics that makes no intuitive sense. Basically everyone writing non-toy-compilers has moved on from it.

>>2

x86 originally did not have mul and div.

WRONG.

http://datasheets.chipdb.org/Intel/x86/808x/datashts/8086/231455-005.pdf :

8 and 16-bit Signed and Unsigned Arithmetic in Binary or Decimal Including Multiply and Divide

(emphasis mine)

Here's a hint: start at the result and work backwards. If you know you need a multiply or divide (or modulus), arrange for the input to that instruction to end up in edx:eax. Ditto for non-constant shifts (make sure output gets into cl).