llvm dev - Apr 2009 - [LLVMdev] Unnecessary moves after sign-extension in 2-address target

My two-address target machine has sign-extension instructions to extend
i8->i32 and i16->i32.  When I compile this simple program:

    int
    sext (unsigned a, unsigned b, int c)
    {
      return (signed char) a + (signed short) b + c;
    }

I get this IR:

    define i32 @sext(i32 %a, i32 %b, i32 %c) nounwind readnone {
    entry:
        %conv = trunc i32 %a to i8        ; <i8> [#uses=1]
        %conv1 = sext i8 %conv to i32        ; <i32> [#uses=1]
        %conv3 = trunc i32 %b to i16        ; <i16> [#uses=1]
        %conv4 = sext i16 %conv3 to i32        ; <i32> [#uses=1]
        %add = add i32 %conv1, %c        ; <i32> [#uses=1]
        %add6 = add i32 %add, %conv4        ; <i32> [#uses=1]
        ret i32 %add6
    }

And this not-so-great assembler code:

sext:
    sextb r1
    mov r4,r1    ### unnecessary move
    add r4,r3
    sextw r2
    mov r1,r2    ### unnecessary move
    add r1,r4
    jmp [r30]

Which should  be this:

sext:
    sextb r1
    add r1,r3
    sextw r2
    add r1,r2
    jmp [r30]

The debug output from LLVM shows this:

********** REWRITING TWO-ADDR INSTRS **********
********** Function: sext
    %reg1028<def> = sextb_r %reg1025<kill>
        prepend:    %reg1028<def> = mov_rr %reg1025<kill>
        rewrite to:    %reg1028<def> = sextb_r %reg1028
...
    %reg1030<def> = sextw_r %reg1026<kill>
        prepend:    %reg1030<def> = mov_rr %reg1026<kill>
        rewrite to:    %reg1030<def> = sextw_r %reg1030

Because sextb_r and sextw_r have destination tied to source operands,
TwoAddressInstructionPass thinks it needs a copy.  However, since the
sext kills its source, the copy is unnecessary.  Why does this happen?
Is TwoAddressInstructionPass relying on a later pass to notice this and
transform it again?

G

On Apr 19, 2009, at 6:15 PM, Greg McGary wrote:
>
> Because sextb_r and sextw_r have destination tied to source operands,
> TwoAddressInstructionPass thinks it needs a copy.  However, since the
> sext kills its source, the copy is unnecessary.  Why does this happen?
> Is TwoAddressInstructionPass relying on a later pass to notice this  
> and
> transform it again?
Yes, the later pass is the coalescer. It would be worthwhile to
understand why it is not coalescing the copies.

Dan

Greg McGary wrote:
> ********** REWRITING TWO-ADDR INSTRS **********
> ********** Function: sext
>     %reg1028<def> = sextb_r %reg1025<kill>
>         prepend:    %reg1028<def> = mov_rr %reg1025<kill>
>         rewrite to:    %reg1028<def> = sextb_r %reg1028
> ...
>     %reg1030<def> = sextw_r %reg1026<kill>
>         prepend:    %reg1030<def> = mov_rr %reg1026<kill>
>         rewrite to:    %reg1030<def> = sextw_r %reg1030
>
> Because sextb_r and sextw_r have destination tied to source operands,
> TwoAddressInstructionPass thinks it needs a copy.  However, since the
> sext kills its source, the copy is unnecessary.  Why does this happen?
> Is TwoAddressInstructionPass relying on a later pass to notice this and
> transform it again?
>   
Since no one responded, I'll assume that this situation doesn't ring a
bell with anyone, so I'll need to dig deeper...

G

Greg McGary wrote:
> Since no one responded, I'll assume that this situation doesn't
ring a
> bell with anyone, so I'll need to dig deeper...
>   
Sorry, I wrote this too soon--I just saw Dan's response.  Thanks!  I'm 
examining the coalescer now.

G

Dan Gohman wrote:
> On Apr 19, 2009, at 6:15 PM, Greg McGary wrote:
>   
>> Because sextb_r and sextw_r have destination tied to source operands,
>> TwoAddressInstructionPass thinks it needs a copy.  However, since the
>> sext kills its source, the copy is unnecessary.  Why does this happen?
>> Is TwoAddressInstructionPass relying on a later pass to notice this  
>> and
>> transform it again?
>>     
>
> Yes, the later pass is the coalescer. It would be worthwhile to
> understand why it is not coalescing the copies.
>   
I discovered a curious phenomenon:

The copies are necessary because TwoAddressInstructionPass commutes
the second add.  When I suppress the commute, the movs disappear and
the code became optimal.  It seems the two-address commuter is either buggy
or inherently short-sighted/simple-minded and paints itself into a corner.

How do you recommend I approach this problem?

G