llvm dev - Oct 2017 - {ARM} IfConversion does not detect BX instruction as a branch

Hi all, 

I got a silly bug when compiling our project with the latest Clang.
Here's the outputted assembly:
> tst r3, #255
> strbeq r6, [r7]
> ldreq r6, [r4, r6, lsl #2]
> strne r6, [r7, #4]
> ldr r6, [r4, r6, lsl #2]
> bx r6
For the code to execute correctly, either the _ldr_ should be a _ldrne_
instruction or the _ldreq_ instruction should be removed. The error
seems to come from the IfConvertion MachinePass. Here's is what it looks
like before and after.
> #BEFORE IfConversion MachinePass 
> 
> BB#7:
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#5 BB#6
> STRBi12 %R5, %R6<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%cond.i23.i.i.i]
> %R6<def> = LDRBi12 %R7, 0, pred:14, pred:%noreg;
mem:LD1[%15](align=4)
> %R3<def> = EORri %R6, 254, pred:14, pred:%noreg, opt:%noreg
> %R3<def> = ANDrr %R3<kill>, %R6<kill>, pred:14,
pred:%noreg, opt:%noreg
> %R6<def> = MOVi 0, pred:14, pred:%noreg, opt:%noreg
> TSTri %R3<kill>, 255, pred:14, pred:%noreg, %CPSR<imp-def>; 
> Bcc <BB#9>, pred:0, pred:%CPSR<kill>; 
> 
> BB#8:
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#7
> STRi12 %R6, %R7<kill>, 4, pred:14, pred:%noreg;
mem:ST4[%__size_.i3.i.i.i.i]
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
> BX %R6<kill> 
> 
> BB#9:
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#7
> STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
> BX %R6<kill> 
> 
> #AFTER IfConversion MachinePass 
> 
> BB#7:
> ...
> TSTri %R3<kill>, 255, pred:14, pred:%noreg, %CPSR<imp-def>; 
> STRBi12 %R6, %R7, 0, pred:0, pred:%CPSR; mem:ST1[%21](align=4) 
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:0, pred:%CPSR,
%R6<imp-use,kill>; mem:LD4[%0]
> STRi12 %R6, %R7<kill>, 4, pred:1, pred:%CPSR<kill>;
mem:ST4[%__size_.i3.i.i.i.i]
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
> BX %R6<kill>
Inside the _IfConvertDiamondCommon(...)_ function of IfConversion.cpp,
the function is called with _NumDups2=1_, which makes sense because BB#8
and BB#9 share the same _LDRrs_ instruction with the same operands. The
problem is the call to _TTI->removeBranch(...)_ function that does not
remove the _BX_ instruction. Thus, when removing the common
instructions, the _BX_ is removed instead of the _LDRs_ instruction.
> # Before removeBranch call on MBB1
> BB#9: derived from LLVM BB %if.else.i.i.i.i
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#7
> STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
> BX %R6<kill>
> 
> # After removeBranch call on MBB1, returned value:0
> BB#9: derived from LLVM BB %if.else.i.i.i.i
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#7
> STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
> BX %R6<kill>
> 
> #After removing common instructions (NumDups2=1) on MBB1
> BB#9: derived from LLVM BB %if.else.i.i.i.i
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#7
> STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
> 
> #After predicated on MBB1
> BB#9: derived from LLVM BB %if.else.i.i.i.i
> Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
> Predecessors according to CFG: BB#7
> STRBi12 %R6, %R7<kill>, 0, pred:0, pred:%CPSR; mem:ST1[%21](align=4) 
> %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:0, pred:%CPSR;
mem:LD4[%0]
We can clearly see that the _LDRrs_ is still there. As a result, after
BB#9 and BB#8 have been merged into BB#7, the _LDRs_ instruction is done
twice when the "positive" path is taken. 

My current fix is the following:
> @@ -408,7 +408,8 @@ unsigned
ARMBaseInstrInfo::removeBranch(MachineBasicBlock &MBB,
> return 0;
> 
> if (!isUncondBranchOpcode(I->getOpcode()) &&
> -      !isCondBranchOpcode(I->getOpcode()))
> +     !isCondBranchOpcode(I->getOpcode()) &&
> +     !isIndirectBranchOpcode(I->getOpcode()))
> return 0;
Does that makes sense? 

Regards, 

Gael
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171009/76f60f27/attachment.html>

On Mon, Oct 9, 2017 at 3:10 AM, Gaël Jobin via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> My current fix is the following:
>
> @@ -408,7 +408,8 @@ unsigned
ARMBaseInstrInfo::removeBranch(MachineBasicBlock
> &MBB,
>    return 0;
>
>    if (!isUncondBranchOpcode(I->getOpcode()) &&
> -      !isCondBranchOpcode(I->getOpcode()))
> +     !isCondBranchOpcode(I->getOpcode()) &&
> +     !isIndirectBranchOpcode(I->getOpcode()))
>       return 0;
>
> Does that makes sense?
>
>
> Independent of anything else, that looks like a bug
in  ARMBaseInstrInfo::removeBranch

It probably has escaped unnoticed because there aren't many code paths that
will try to remove an indirect branch.
I'll let ARM folks chime in, but it looks correct to me.

Kyle.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171009/01adcfb9/attachment.html>

On 2017-10-09 20:00, Kyle Butt wrote:
> It probably has escaped unnoticed because there aren't many code paths
that will try to remove an indirect branch.
> I'll let ARM folks chime in, but it looks correct to me.
Thank you for your point of view. Anyway, after many tests, it appears
that the changes fixed my issue. I tried to reproduce a minimal piece of
C to trigger the bug, without success. In fact, I am still wondering if
_removeBranch(...)_ should support removing "jump-table" branches as
well (_i__sJumpTableBranchOpcode()_). I didn't hit that specific case,
but I will keep those emails preciously to remember the issue if
something similar appears again. 

Regards; 

Gael
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171010/33390f4c/attachment.html>

On 10/9/2017 3:10 AM, Gaël Jobin via llvm-dev wrote:
>
> Hi all,
>
> I got a silly bug when compiling our project with the latest Clang. 
> Here's the outputted assembly:
>
>> tst r3, #255
>> strbeq r6, [r7]
>> ldreq r6, [r4, r6, lsl #2]
>> strne r6, [r7, #4]
>> ldr r6, [r4, r6, lsl #2]
>> bx r6
>>
> For the code to execute correctly, either the /ldr/ should be a 
> /ldrne/ instruction or the /ldreq/ instruction should be removed. The 
> error seems to come from the IfConvertion MachinePass. Here's is what 
> it looks like before and after.
>
>> #BEFORE IfConversion MachinePass
>>
>> BB#7:
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#5 BB#6
>>    STRBi12 %R5, %R6<kill>, 0, pred:14, pred:%noreg; 
>> mem:ST1[%cond.i23.i.i.i]
>>    %R6<def> = LDRBi12 %R7, 0, pred:14, pred:%noreg; 
>> mem:LD1[%15](align=4)
>>    %R3<def> = EORri %R6, 254, pred:14, pred:%noreg, opt:%noreg
>>    %R3<def> = ANDrr %R3<kill>, %R6<kill>, pred:14,
pred:%noreg,
>> opt:%noreg
>>    %R6<def> = MOVi 0, pred:14, pred:%noreg, opt:%noreg
>>    TSTri %R3<kill>, 255, pred:14, pred:%noreg,
%CPSR<imp-def>;
>>    Bcc <BB#9>, pred:0, pred:%CPSR<kill>;
>>
>>
>> BB#8:
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#7
>>    STRi12 %R6, %R7<kill>, 4, pred:14, pred:%noreg; 
>> mem:ST4[%__size_.i3.i.i.i.i]
>>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
>> mem:LD4[%0]
>>    BX %R6<kill>
>>
>> BB#9:
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#7
>>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg; 
>> mem:ST1[%21](align=4)
>>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
>> mem:LD4[%0]
>>    BX %R6<kill>
>>
>> #AFTER IfConversion MachinePass
>>
>> BB#7:
>>    ...
>>    TSTri %R3<kill>, 255, pred:14, pred:%noreg,
%CPSR<imp-def>;
>>    STRBi12 %R6, %R7, 0, pred:0, pred:%CPSR; mem:ST1[%21](align=4)
>>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:0,
pred:%CPSR,
>> %R6<imp-use,kill>; mem:LD4[%0]
>>    STRi12 %R6, %R7<kill>, 4, pred:1, pred:%CPSR<kill>; 
>> mem:ST4[%__size_.i3.i.i.i.i]
>>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
>> mem:LD4[%0]
>>    BX %R6<kill>
>>
> Inside the /IfConvertDiamondCommon(...)/ function of IfConversion.cpp, 
> the function is called with /NumDups2=1/, which makes sense because 
> BB#8 and BB#9 share the same /LDRrs/ instruction with the same 
> operands. The problem is the call to /TTI->removeBranch(...)/ function 
> that does not remove the /BX/ instruction. Thus, when removing the 
> common instructions, the /BX/ is removed instead of the /LDRs/ 
> instruction.
>
>> # Before removeBranch call on MBB1
>> BB#9: derived from LLVM BB %if.else.i.i.i.i
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#7
>>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg; 
>> mem:ST1[%21](align=4)
>>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
>> mem:LD4[%0]
>>    BX %R6<kill>
>>
>> # After removeBranch call on MBB1, returned value:0
>> BB#9: derived from LLVM BB %if.else.i.i.i.i
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#7
>>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg; 
>> mem:ST1[%21](align=4)
>>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
>> mem:LD4[%0]
>>    BX %R6<kill>
>>
>> #After removing common instructions (NumDups2=1) on MBB1
>> BB#9: derived from LLVM BB %if.else.i.i.i.i
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#7
>>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg; 
>> mem:ST1[%21](align=4)
>>   %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
>> mem:LD4[%0]
>>
>> #After predicated on MBB1
>> BB#9: derived from LLVM BB %if.else.i.i.i.i
>>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>>    Predecessors according to CFG: BB#7
>>    STRBi12 %R6, %R7<kill>, 0, pred:0, pred:%CPSR;
mem:ST1[%21](align=4)
>>   %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:0,
pred:%CPSR; mem:LD4[%0]
>>
> We can clearly see that the /LDRrs/ is still there. As a result, after 
> BB#9 and BB#8 have been merged into BB#7, the /LDRs/ instruction is 
> done twice when the "positive" path is taken.
>
> My current fix is the following:
>
>> @@ -408,7 +408,8 @@ unsigned 
>> ARMBaseInstrInfo::removeBranch(MachineBasicBlock &MBB,
>>    return 0;
>>
>>    if (!isUncondBranchOpcode(I->getOpcode()) &&
>> -      !isCondBranchOpcode(I->getOpcode()))
>> +     !isCondBranchOpcode(I->getOpcode()) &&
>> +     !isIndirectBranchOpcode(I->getOpcode()))
>>       return 0;
>>
> Does that makes sense?
>
Target-independent code is only supposed to call removeBranch in cases 
where analyzeBranch returns false; as far as I can tell, 
ARMBaseInstrInfo::analyzeBranch will never return false for an indirect 
branch.  So I would guess there's a bug in IfConversion, rather than the 
ARM backend.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171010/ecbce300/attachment.html>

On Tue, Oct 10, 2017 at 4:48 PM, Friedman, Eli via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On 10/9/2017 3:10 AM, Gaël Jobin via llvm-dev wrote:
>
> Hi all,
>
> I got a silly bug when compiling our project with the latest Clang.
Here's
> the outputted assembly:
>
> tst r3, #255
> strbeq r6, [r7]
> ldreq r6, [r4, r6, lsl #2]
> strne r6, [r7, #4]
> ldr r6, [r4, r6, lsl #2]
> bx r6
>
> For the code to execute correctly, either the *ldr* should be a *ldrne*
> instruction or the *ldreq* instruction should be removed. The error seems
> to come from the IfConvertion MachinePass. Here's is what it looks like
> before and after.
>
> #BEFORE IfConversion MachinePass
>
> BB#7:
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#5 BB#6
>    STRBi12 %R5, %R6<kill>, 0, pred:14, pred:%noreg;
> mem:ST1[%cond.i23.i.i.i]
>    %R6<def> = LDRBi12 %R7, 0, pred:14, pred:%noreg;
mem:LD1[%15](align=4)
>    %R3<def> = EORri %R6, 254, pred:14, pred:%noreg, opt:%noreg
>    %R3<def> = ANDrr %R3<kill>, %R6<kill>, pred:14,
pred:%noreg, opt:%noreg
>    %R6<def> = MOVi 0, pred:14, pred:%noreg, opt:%noreg
>    TSTri %R3<kill>, 255, pred:14, pred:%noreg, %CPSR<imp-def>;
>    Bcc <BB#9>, pred:0, pred:%CPSR<kill>;
>
>
> BB#8:
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#7
>    STRi12 %R6, %R7<kill>, 4, pred:14, pred:%noreg;
> mem:ST4[%__size_.i3.i.i.i.i]
>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
> mem:LD4[%0]
>    BX %R6<kill>
>
> BB#9:
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#7
>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
> mem:LD4[%0]
>    BX %R6<kill>
>
> #AFTER IfConversion MachinePass
>
> BB#7:
>    ...
>    TSTri %R3<kill>, 255, pred:14, pred:%noreg, %CPSR<imp-def>;
>    STRBi12 %R6, %R7, 0, pred:0, pred:%CPSR; mem:ST1[%21](align=4)
>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:0, pred:%CPSR,
> %R6<imp-use,kill>; mem:LD4[%0]
>    STRi12 %R6, %R7<kill>, 4, pred:1, pred:%CPSR<kill>;
> mem:ST4[%__size_.i3.i.i.i.i]
>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
> mem:LD4[%0]
>    BX %R6<kill>
>
> Inside the *IfConvertDiamondCommon(...)* function of IfConversion.cpp,
> the function is called with *NumDups2=1*, which makes sense because BB#8
> and BB#9 share the same *LDRrs* instruction with the same operands. The
> problem is the call to *TTI->removeBranch(...)* function that does not
> remove the *BX* instruction. Thus, when removing the common instructions,
> the *BX* is removed instead of the *LDRs* instruction.
>
> # Before removeBranch call on MBB1
> BB#9: derived from LLVM BB %if.else.i.i.i.i
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#7
>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
> mem:LD4[%0]
>    BX %R6<kill>
>
> # After removeBranch call on MBB1, returned value:0
> BB#9: derived from LLVM BB %if.else.i.i.i.i
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#7
>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
>    %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14,
pred:%noreg;
> mem:LD4[%0]
>    BX %R6<kill>
>
> #After removing common instructions (NumDups2=1) on MBB1
> BB#9: derived from LLVM BB %if.else.i.i.i.i
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#7
>    STRBi12 %R6, %R7<kill>, 0, pred:14, pred:%noreg;
mem:ST1[%21](align=4)
>   %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:14, pred:%noreg;
mem:LD4[%0]
>
> #After predicated on MBB1
> BB#9: derived from LLVM BB %if.else.i.i.i.i
>    Live Ins: %LR %R0 %R1 %R2 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R12
>    Predecessors according to CFG: BB#7
>    STRBi12 %R6, %R7<kill>, 0, pred:0, pred:%CPSR;
mem:ST1[%21](align=4)
>   %R6<def> = LDRrs %R4, %R6<kill>, 16386, pred:0, pred:%CPSR;
mem:LD4[%0]
>
> We can clearly see that the *LDRrs* is still there. As a result, after
> BB#9 and BB#8 have been merged into BB#7, the *LDRs* instruction is done
> twice when the "positive" path is taken.
>
> My current fix is the following:
>
> @@ -408,7 +408,8 @@ unsigned
ARMBaseInstrInfo::removeBranch(MachineBasicBlock
> &MBB,
>    return 0;
>
>    if (!isUncondBranchOpcode(I->getOpcode()) &&
> -      !isCondBranchOpcode(I->getOpcode()))
> +     !isCondBranchOpcode(I->getOpcode()) &&
> +     !isIndirectBranchOpcode(I->getOpcode()))
>       return 0;
>
> Does that makes sense?
>
>
> Target-independent code is only supposed to call removeBranch in cases
> where analyzeBranch returns false; as far as I can tell,
ARMBaseInstrInfo::analyzeBranch
> will never return false for an indirect branch.  So I would guess
there's a
> bug in IfConversion, rather than the ARM backend.
>
> -Eli
>
Eli's right.

Gaël, do you think you could patch ifconversion to remove the instructions
rather than relying on removeBranch?
>
> --
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171010/fac0f6b2/attachment.html>