Re: [Patch,AVR] Light-weight DImode implementation.

[Paolo Bonzini <bonzini at gnu dot org>]

On 11/22/2011 01:15 AM, Georg-Johann Lay wrote:
>      ldi r30,lo8(1)     ;  25    *movqi/2    [length = 1]
>      cp r10,r18     ;  26    *cmpqi/2    [length = 1]
>      brlo .L2     ;  27    branch    [length = 1]
>      ldi r30,lo8(0)     ;  28    *movqi/1    [length = 1]
> .L2:
>      add r11,r19     ;  30    addqi3/1    [length = 1]

(WARNING: there are a lot of "if"s in this message.  However, some of 
the ideas here might give better code in general).

I noticed that the AVR backend does not have cstore, movcc, addcc. 
These are quite useful in general, and especially with the kind of code 
that expand_binop produces.  For example all of these can be implemented 
in terms of adc or sbc:

    x = (a < b)            (cstore ltu, using ldi+adc)
    x = (a < b) ? -1 : 0   (movcc ltu, using ldi+sbc)
    x += (a < b) ? 1 : 0   (addcc ltu, using adc)
    x += (a < b) ? -1 : 0  (addcc ltu, using sbc)

In the code above, cstore could change the brlo/ldi pair to a single adc 
or sbc.  addcc could also change a ldi/cp/brlo/ldi/add to cp+adc. 
expand_binop does not try to use addcc currently, but it could do so 
instead of cstore+or in the computation of the carry.

Then if final can successfully combine the "add" and "cp" instructions, 
you'd get something like:

    add r10,r18             ; sum 0
    ldi r30,lo8(0)          ; carryout 0
    adc r30,__zero_reg__
    add r11,r19             ; sum 1
    ldi r18,lo8(0)          ; carryout 1
    adc r18,__zero_reg__
    mov r19,r30             ; sum carry 1
    add r19,r11
    adc r18,__zero_reg__    ; carryout 1
    add r12,r20             ; sum 2
    ldi r30,lo8(0)          ; carryout 2
    adc r30,__zero_reg__
    mov r20,r18             ; sum carry 2
    add r20,r12
    adc r30,__zero_reg__    ; carryout 2
    add r13,r21             ; sum 3
    ldi r18,lo8(0)          ; carryout 3
    adc r18,__zero_reg__
    mov r21,r30             ; sum carry 3
    add r21,r13
    adc r18,__zero_reg__    ; carryout 3
    add r14,r22             ; sum 4
    ldi r30,lo8(0)          ; carryout 4
    adc r30,__zero_reg__
    mov r22,r18             ; sum carry 4
    add r22,r14
    adc r30,__zero_reg__    ; carryout 4
    add r15,r23             ; sum 5
    ldi r18,lo8(0)          ; carryout 5
    adc r18,__zero_reg__
    mov r23,r30             ; sum carry 5
    add r23,r15
    adc r18,__zero_reg__    ; carryout 5
    add r16,r24             ; sum 6
    ldi r30,lo8(0)          ; carryout 6
    adc r30,__zero_reg__
    mov r24,r18             ; sum carry 6
    add r24,r16
    adc r30,__zero_reg__    ; carryout 6
    add r25,r17             ; sum 7
    mov r18,r10
    add r25,r30             ; sum carry 7

Still suboptimal, but already much better than what you get now.

expand_binop could also sum the carry first, and the operand second, 
which would avoid overlapping live ranges for the carry:

    add r18,r10             ; sum 0
    ldi r30,lo8(0)          ; carryout 0
    adc r30,__zero_reg__
    add r19,r30             ; sum carry 1
    ldi r30,lo8(0)          ; carryout 1
    adc r30,__zero_reg__
    add r19,r11             ; sum 1
    adc r30,__zero_reg__    ; carryout 1
    add r20,r30             ; sum carry 2
    ldi r30,lo8(0)          ; carryout 2
    adc r30,__zero_reg__
    add r20,r12             ; sum 2
    adc r30,__zero_reg__    ; carryout 2
    add r21,r30             ; sum carry 3
    ldi r30,lo8(0)          ; carryout 3
    adc r30,__zero_reg__
    add r21,r13             ; sum 3
    adc r30,__zero_reg__    ; carryout 3
    add r22,r30             ; sum carry 4
    ldi r30,lo8(0)          ; carryout 4
    adc r30,__zero_reg__
    add r22,r14             ; sum 4
    adc r30,__zero_reg__    ; carryout 4
    add r23,r30             ; sum carry 5
    ldi r30,lo8(0)          ; carryout 5
    adc r30,__zero_reg__
    add r23,r15             ; sum 5
    adc r30,__zero_reg__    ; carryout 5
    add r24,r30             ; sum carry 6
    ldi r30,lo8(0)          ; carryout 6
    adc r30,__zero_reg__
    add r24,r16             ; sum 6
    adc r30,__zero_reg__    ; carryout 6
    add r25,r30             ; sum carry 7
    add r25,r17             ; sum 7

The code now is very regular and r30 dies often, so that playing with 
peephole2 could give decent code.  This code:

    (cp rAA, rBB)                          ; eliminated by final
    ldi r30,lo8(0)          ; carryout 0
    adc r30,__zero_reg__
    add rXX,r30             ; sum carry 1
    (cp rXX, r30)                          ; eliminated by final
    ldi r30,lo8(0)          ; carryout 1
    adc r30,__zero_reg__
    add rXX,rZZ             ; sum 1
    (cp rXX, rZZ)                          ; eliminated by final
    adc r30,__zero_reg__    ; carryout 1
    add rYY,r30             ; sum carry 2

can be rewritten to

    (cp rAA, rBB)                          ; eliminated by final
    adc rXX,rZZ
    (cp rXX, rZZ)                          ; eliminated by final
    ldi r30,lo8(0)          ; carryout 1
    adc r30,__zero_reg__
    add rYY,r30             ; sum carry 2

Now, in theory the final four instructions would chain again into the 
same pattern (not sure peephole2 does this properly because it scan 
backwards; if it doesn't, you have to code the peepholes from the 
bottom) until you have

    add r18,r10
    adc r19,r11
    adc r20,r12
    adc r21,r13
    adc r22,r14
    adc r23,r15
    adc r24,r16
    ldi r30,lo8(0)          ; carryout 6
    adc r30,__zero_reg__
    add r25,r30             ; sum carry 7
    add r25,r17             ; sum 7

and finally with a simpler peephole (cp/ldi+adc/add/add to cp/adc):

    add r18,r10
    adc r19,r11
    adc r20,r12
    adc r21,r13
    adc r22,r14
    adc r23,r15
    adc r24,r16
    adc r25,r17

Paolo