Experimental: Unleash code generation

[agnat]

Looking a bit deeper into the whole SelectionDAG business I believe this is the root of all evil:

addRegisterClass(MVT::i16, &AVR::DREGSRegClass);

It makes LLVM believe i16 is a native type. So I ripped it out.

The part that immediately collapsed is the calling convention. I kind of kludged the kludge and it works for now (as in: it compiles). But it certainly has bugs. The whole calling convention could use some love...

The other issue is probably a little more involved. LLVM does not provide any help when the targets pointer type is larger than the targets native registers. I'll look into that.

Demo? Sure thing:

16 Bit Multiplication

    muls    r21, r24
    mov r24, r0
    eor r1, r1
    mul r21, r23
    mov r25, r0
    mov r18, r1
    eor r1, r1
    add r18, r24
    muls    r22, r23
    eor r1, r1
    mov r24, r0
    add r24, r18
    mov r23, r25

No more crazy shifting.

64 Bit And

    push    r17
    andi    r17, -3
    andi    r19, -101
    andi    r20, 88
    andi    r21, 76
    andi    r22, 73
    andi    r23, 31
    andi    r24, -14
    pop r17
    ret

Everything fits in registers and is done in place.

[agnat]

Ah, and it does no longer use the 16 bit pseudos, of course ;)

[dylanmckay]

This looks really, really nice. If we get this passing, it will clean up and simplify the backend immensely.

I'm gonna have a look and see if I can diagnose the calling convention problem.

[agnat]

I asked about non-legal pointer types on LLVMdev.

I also found this PIC16 backend. It was removed in LLVM 2.9. It works around the issue by using custom ISD nodes, external symbols and... premature lowering. So, that's just for reference...

[dylanmckay]

If you remove addRegisterClass(MVT::i16, &AVR::DREGSRegClass);, are you still able to perform instruction selection on 16-bit values? From your comments, it looks like you can. Although I am a bit confused as to why LLVM generates three MUL instructions for a single multiplication.

[agnat]

If you remove addRegisterClass(MVT::i16, &AVR::DREGSRegClass);, are you still able to perform instruction selection on 16-bit values?

Nope. There are no i16 values in the graph after type legalization. So there is nothing to match with. Which comment gave you that impression?

Although I am a bit confused as to why LLVM generates three MUL instructions for a single multiplication.

Hehe... yes, that's a bit confusing. However, it is an arithmetic property of multiplication and has nothing to do with computer science. Let me try to explain.

Let's forget about bits and bytes for a second. Subdividing operations on large binary numbers into operations on bytes is exactly equivalent to digit-wise arithmetic on paper like back in school. The only difference is that the former has radix 255 and the later has radix 10. It's easy to see with addition:

  23
+ 42
-----
  65

That is one add and one add with carry. Still with me? Now lets look at the ascii-art for a digit-wise multiplication:

   23
⨉  42
-----
   46
+ 92
-----
  966

That is actually four digit-wise multiplications. However, since we are going to truncate the result to two digits we can skip the fourth (4 * 2 + 1) and get away with three.

[agnat]

... the former has radix 255 ...

256! But you get the idea... ;)