Gaël Jobin via llvm-dev
2017-Oct-09 10:10 UTC
[llvm-dev] {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 r6For 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>
Kyle Butt via llvm-dev
2017-Oct-09 18:00 UTC
[llvm-dev] {ARM} IfConversion does not detect BX instruction as a branch
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 bugin 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>
Gaël Jobin via llvm-dev
2017-Oct-10 15:50 UTC
[llvm-dev] {ARM} IfConversion does not detect BX instruction as a branch
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>
Friedman, Eli via llvm-dev
2017-Oct-10 23:48 UTC
[llvm-dev] {ARM} IfConversion does not detect BX instruction as a branch
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>
Kyle Butt via llvm-dev
2017-Oct-11 01:07 UTC
[llvm-dev] {ARM} IfConversion does not detect BX instruction as a branch
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>