[ARM] Make MachineVerifier more strict about terminators

[samparker]

Summary

Per a recent thread on llvmdev, MachineVerifier is a bit loose about the rule that terminators are always at the end of a basic block. Fix the ARM backend's analyzeBranch so it doesn't ignore predicated return instructions, and make the MachineVerifier rule more strict.

WIP because I'm not happy with the change in the generated code for atomic-cmpxchg.ll. IfConversion creates a BB which is a predicated return followed by an unconditional branch, and analyzeBranch can't analyze that, so we end up with a very stupid-looking branch after MachineBlockPlacement. Maybe we should be putting the unconditional branch into a separate block? Or should we be able to analyze the construct somehow? Or should we be avoiding IfConversion in cases where we can't fall through? (It might be possible to end up in a similar situation with a jump table branch followed by a unconditional branch, but I don't have a testcase for that.)

[MatzeB]

Uh, I wasn't aware that if-conversion could produce terminator instructions in the middle of a basic block, and I would suspect this to break other things like MachineBasicBlock::isReturnBlock() which assume terminators are at the end...

I must admit I don't understand how a change in analyzeBranch() allows you to drop that MachineVerifier special case. But I am all for dropping strange special cases in the machine verifier :)

[efriedma]

IfConversion itself doesn't produce blocks with branches in the middle. It produces something like "bxne lr; b .LBB5_5" (a conditional return followed by an unconditional branch). From the verifier's perspective, that's fine because they're both terminators. But analyzeBranch was ignoring the conditional return, so MachineBlockPlacement would merge the block with the following block.

I would guess this didn't break anything because IfConversion runs pretty late in the pipeline.

[uabelho]

So now you make all returns (predicated or not) non-analyzable from analyzeBranch's perspective?

Do you know if all targets follow this? I suppose all tests under test/ still pass with the stricter
verifier checks, but have you looked at the different analyzeBranch implementations?

I think the change makes sense but I also know that fiddling with analyzeBranch can have
unexpected consequences so it's very hard to really know if it works or not.

[efriedma]

So now you make all returns (predicated or not) non-analyzable from analyzeBranch's perspective?

Yes.

but have you looked at the different analyzeBranch implementations?

I just tried looking. I think this is consistent with what other targets do (e.g. PowerPC has a conditional return instruction, which it treats an unanalyzable).

[uabelho]

I ran the stricter verifier tests on my out-of-tree target all weekend without finding anything
so that seems good at least.

[samparker]

Dragged this patch in 2020 and the original concerns around inefficient codegen now appear to be gone. Most of these changes are MIR test changes where I've had to insert a block after a tBX_RET, but I've also add to regenerate a few MIR tests completely to save my sanity.

[yroux]

I've tested the patch and it fixes the liveness issue seen with Machine Outliner enabled.

The patch LGTM but maybe needs another review

[efriedma]

llvm/test/CodeGen/Thumb2/mve-satmul-loops.ll

1141 ↗

(On Diff #286529)

This is an instance of the problem I was running into with the original patch.

[samparker]

Thanks both. I think I've got rid of the pesky branches.

• All return instructions are now not analysable.
• The block iterators have been changed within analyzeBranch so we can look at each instruction within a bundle.
• If the last instruction in the block is an unpredicated unconditional branch, that targets the layout successor, we remove the branch.

[yroux]

Hi,

I think a few more testcases need to be updated:

CodeGen/Thumb2/LowOverheadLoops/mve-float-loops.ll
CodeGen/Thumb2/mve-postinc-distribute.ll
CodeGen/Thumb2/mve-postinc-lsr.ll
CodeGen/Thumb2/mve-selectcc.ll
Profile-armhf :: instrprof-lto-pgogen.c

[samparker]

Hi @yroux , I've rebased and updated test/CodeGen/Thumb2/mve-selectcc.ll test, but the others that you mentioned seemed fine. Was there particular parts of those tests that you think should change?

[yroux]

Hi Sam,

I've tested the patch on top of 4d90ff5 rev on a native ARM plateform the issues I see are:

Thumb2/LowOverheadLoops/mve-float-loops.ll:908:15: error: CHECK-NEXT: expected string not found in input
; CHECK-NEXT: b .LBB4_6

^

<stdin>:511:1: note: scanning from here
.LBB4_6: @ %for.body.preheader11

Thumb2/mve-postinc-lsr.ll:41:15: error: CHECK-NEXT: expected string not found in input
; CHECK-NEXT: b .LBB0_6

^

<stdin>:62:1: note: scanning from here
.LBB0_6: @ %for.body.preheader12

Thumb2/mve-postinc-distribute.ll:307:15: error: CHECK-NEXT: expected string not found in input
; CHECK-NEXT: b .LBB2_6

^

<stdin>:181:1: note: scanning from here
.LBB2_6: @ %for.body.preheader12

I'll try to find what is wrong with compiler-rt/test/profile/instrprof-lto-pgogen.c and let you know

[samparker]

Hi Yvan,

Could you post the output of those failing tests so I can compare them fully? I'm on an X86 machine but I hope that isn't making a difference...
Thanks.

[yroux]

My bad, I applied the previous version where a branch was inserted in those tests but your last version is fine.

I'm ok with the patch

[samparker]

Thanks for confirming. What do you think @efriedma?

[efriedma]

LGTM

lib/CodeGen/MachineVerifier.cpp

if (Indexes && Indexes->hasIndex(*MI)) {
     if (!(idx > lastIndex)) {
       report("Instruction index out of order", MI);
       errs() << "Last instruction was at " << lastIndex << '\n';
     }
     lastIndex = idx;
   }
 
   // Ensure non-terminators don't follow terminators.
-  // Ignore predicated terminators formed by if conversion.
-  // FIXME: If conversion shouldn't need to violate this rule.
-  if (MI->isTerminator() && !TII->isPredicated(*MI)) {
+  if (MI->isTerminator()) {
     if (!FirstTerminator)
       FirstTerminator = MI;
   } else if (FirstTerminator) {
     report("Non-terminator instruction after the first terminator", MI);
     errs() << "First terminator was:\t" << *FirstTerminator;
   }
 }
 

lib/Target/ARM/ARMBaseInstrInfo.cpp

if (isIndirectBranchOpcode(I->getOpcode()) ||
       if (!Cond.empty())
         return true;
 
       assert(!FBB && "FBB should have been null.");
       FBB = TBB;
       TBB = I->getOperand(0).getMBB();
       Cond.push_back(I->getOperand(1));
       Cond.push_back(I->getOperand(2));
-    } else if (I->isReturn()) {
+    } else if (I->isReturn() && !isPredicated(*I)) {
       // Returns can't be analyzed, but we should run cleanup.
-      CantAnalyze = !isPredicated(*I);
+      CantAnalyze = true;
     } else {
       // We encountered other unrecognized terminator. Bail out immediately.
       return true;
     }
 
     // Cleanup code - to be run for unpredicated unconditional branches and
     //                returns.
     if (!isPredicated(*I) &&

test/CodeGen/ARM/2013-05-05-IfConvertBug.ll

 ; <rdar://problem/14379453>
 
 ; Hard-coded registers comes from the ABI.
 ; CHECK-LABEL: wrapDistance:
 ; CHECK: cmp r1, #59
 ; CHECK-NEXT: itt le
 ; CHECK-NEXT: suble r0, r2, #1
 ; CHECK-NEXT: bxle lr
+; CHECK-NEXT: LBB{{[0-9]_[0-9]}}:
 ; CHECK-NEXT: subs [[REG:r[0-9]+]], #120
 ; CHECK-NEXT: cmp [[REG]], r1
 ; CHECK-NOT: it lt
 ; CHECK-NEXT: bge [[LABEL:.+]]
 ; Next BB
 ; CHECK-NOT: cmplt
 ; CHECK: cmp r0, #119
 ; CHECK-NEXT: itt le

test/CodeGen/ARM/atomic-cmpxchg.ll

 ; CHECK-ARMV6-LABEL: test_cmpxchg_res_i8:
 ; CHECK-ARMV6-NEXT:  .fnstart
 ; CHECK-ARMV6-NEXT: uxtb [[DESIRED:r[0-9]+]], r1
 ; CHECK-ARMV6-NEXT: [[TRY:.LBB[0-9_]+]]:
 ; CHECK-ARMV6-NEXT: ldrexb [[LD:r[0-9]+]], [r0]
 ; CHECK-ARMV6-NEXT: cmp [[LD]], [[DESIRED]]
 ; CHECK-ARMV6-NEXT: movne [[RES:r[0-9]+]], #0
 ; CHECK-ARMV6-NEXT: bxne lr
+; CHECK-ARMV6-NEXT: LBB{{[0-9]_[0-9]}}:
 ; CHECK-ARMV6-NEXT: strexb [[SUCCESS:r[0-9]+]], r2, [r0]
 ; CHECK-ARMV6-NEXT: cmp [[SUCCESS]], #0
 ; CHECK-ARMV6-NEXT: moveq [[RES]], #1
 ; CHECK-ARMV6-NEXT: bxeq lr
 ; CHECK-ARMV6-NEXT: b [[TRY]]
 
 ; CHECK-THUMBV6-LABEL: test_cmpxchg_res_i8:
 ; CHECK-THUMBV6:       mov [[EXPECTED:r[0-9]+]], r1

 ; CHECK-ARMV7-NEXT: .fnstart
 ; CHECK-ARMV7-NEXT: uxtb [[DESIRED:r[0-9]+]], r1
 ; CHECK-ARMV7-NEXT: b [[TRY:.LBB[0-9_]+]]
 ; CHECK-ARMV7-NEXT: [[HEAD:.LBB[0-9_]+]]:
 ; CHECK-ARMV7-NEXT: strexb [[SUCCESS:r[0-9]+]], r2, [r0]
 ; CHECK-ARMV7-NEXT: cmp [[SUCCESS]], #0
 ; CHECK-ARMV7-NEXT: moveq r0, #1
 ; CHECK-ARMV7-NEXT: bxeq lr
+; CHECK-ARMV7-NEXT: b [[TRY]]
 ; CHECK-ARMV7-NEXT: [[TRY]]:
 ; CHECK-ARMV7-NEXT: ldrexb [[SUCCESS]], [r0]
 ; CHECK-ARMV7-NEXT: cmp [[SUCCESS]], r1
 ; CHECK-ARMV7-NEXT: beq [[HEAD]]
 ; CHECK-ARMV7-NEXT: mov r0, #0
 ; CHECK-ARMV7-NEXT: clrex
 ; CHECK-ARMV7-NEXT: bx lr
 
 ; CHECK-THUMBV7-LABEL: test_cmpxchg_res_i8:
 ; CHECK-THUMBV7-NEXT: .fnstart
 ; CHECK-THUMBV7-NEXT: uxtb [[DESIRED:r[0-9]+]], r1
 ; CHECK-THUMBV7-NEXT: b [[TRYLD:.LBB[0-9_]+]]
 ; CHECK-THUMBV7-NEXT: [[TRYST:.LBB[0-9_]+]]:
 ; CHECK-THUMBV7-NEXT: strexb [[SUCCESS:r[0-9]+]], r2, [r0]
 ; CHECK-THUMBV7-NEXT: cmp [[SUCCESS]], #0
 ; CHECK-THUMBV7-NEXT: itt eq
 ; CHECK-THUMBV7-NEXT: moveq r0, #1
 ; CHECK-THUMBV7-NEXT: bxeq lr
+; CHECK-THUMBV7-NEXT: b [[TRYLD]]
 ; CHECK-THUMBV7-NEXT: [[TRYLD]]:
 ; CHECK-THUMBV7-NEXT: ldrexb [[LD:r[0-9]+]], [r0]
 ; CHECK-THUMBV7-NEXT: cmp [[LD]], [[DESIRED]]
 ; CHECK-THUMBV7-NEXT: beq [[TRYST:.LBB[0-9_]+]]
 ; CHECK-THUMBV7-NEXT: movs r0, #0
 ; CHECK-THUMBV7-NEXT: clrex
 ; CHECK-THUMBV7-NEXT: bx lr

test/CodeGen/ARM/call-tc.ll

 ; rdar://8309338
 declare void @foo() nounwind
 
 define void @t7() nounwind "no-frame-pointer-elim"="true" {
 entry:
 ; CHECKT2D-LABEL: t7:
 ; CHECKT2D: it ne
 ; CHECKT2D-NEXT: bne.w _foo
+; CHECKT2D-NEXT: LBB{{[0-9]_[0-9]}}:
 ; CHECKT2D-NEXT: push
 ; CHECKT2D-NEXT: mov r7, sp
 ; CHECKT2D-NEXT: bl _foo
   br i1 undef, label %bb, label %bb1.lr.ph
 
 bb1.lr.ph:
   tail call void @foo() nounwind
   unreachable

test/CodeGen/ARM/cmpxchg-weak.ll

 ; CHECK-NEXT:     cmp     [[LOADED]], r2
 ; CHECK-NEXT:     bne     [[LDFAILBB:LBB[0-9]+_[0-9]+]]
 ; CHECK-NEXT: BB#1:
 ; CHECK-NEXT:     dmb ish
 ; CHECK-NEXT:     mov     r0, #0
 ; CHECK-NEXT:     strex   [[SUCCESS:r[0-9]+]], r3, [r1]
 ; CHECK-NEXT:     cmp     [[SUCCESS]], #0
 ; CHECK-NEXT:     bxne    lr
+; CHECK-NEXT: LBB{{[0-9]_[0-9]}}:
 ; CHECK-NEXT:     mov     r0, #1
 ; CHECK-NEXT:     dmb     ish
 ; CHECK-NEXT:     bx      lr
 ; CHECK-NEXT: [[LDFAILBB]]:
 ; CHECK-NEXT:     mov     r0, #0
 ; CHECK-NEXT:     clrex
 ; CHECK-NEXT:     bx      lr
 
   ret i1 %success
 }

test/CodeGen/ARM/code-placement.ll

 ; RUN: llc < %s -mtriple=armv7-apple-darwin | FileCheck %s
 ; PHI elimination shouldn't break backedge.
 ; rdar://8263994
 
 %struct.list_data_s = type { i16, i16 }
 %struct.list_head = type { %struct.list_head*, %struct.list_data_s* }
 
 define arm_apcscc %struct.list_head* @t1(%struct.list_head* %list) nounwind {
 entry:
 ; CHECK-LABEL: t1:
   %0 = icmp eq %struct.list_head* %list, null
   br i1 %0, label %bb2, label %bb
 
 bb:
+; CHECK: LBB0_{{[0-9]}}:
 ; CHECK: LBB0_[[LABEL:[0-9]]]:
 ; CHECK: bne LBB0_[[LABEL]]
 ; CHECK-NOT: b LBB0_[[LABEL]]
 ; CHECK: bx lr
   %list_addr.05 = phi %struct.list_head* [ %2, %bb ], [ %list, %entry ]
   %next.04 = phi %struct.list_head* [ %list_addr.05, %bb ], [ null, %entry ]
   %1 = getelementptr inbounds %struct.list_head, %struct.list_head* %list_addr.05, i32 0, i32 0
   %2 = load %struct.list_head*, %struct.list_head** %1, align 4

test/CodeGen/ARM/sched-it-debug-nodes.mir

bb.0.entry:
     DBG_VALUE debug-use %r1, debug-use _, !19, !27, debug-location !28
     DBG_VALUE debug-use %r2, debug-use _, !20, !27, debug-location !28
     DBG_VALUE debug-use %r3, debug-use _, !21, !27, debug-location !28
     t2CMPri %r3, 4, 14, _, implicit-def %cpsr, debug-location !31
     DBG_VALUE debug-use %r1, debug-use _, !19, !27, debug-location !28
     %r0 = t2MOVi -1, 3, %cpsr, _, implicit undef %r0
     DBG_VALUE debug-use %r1, debug-use _, !19, !27, debug-location !28
     tBX_RET 3, %cpsr, implicit %r0, debug-location !34
+
+  bb.1:
+    liveins: %r0, %r1, %r2, %r3, %lr
     %sp = frame-setup t2STMDB_UPD %sp, 14, _, killed %r7, killed %lr
     frame-setup CFI_INSTRUCTION def_cfa_offset 8
     frame-setup CFI_INSTRUCTION offset %lr, -4
     frame-setup CFI_INSTRUCTION offset %r7, -8
     DBG_VALUE debug-use %r0, debug-use _, !18, !27, debug-location !28
     DBG_VALUE debug-use %r1, debug-use _, !19, !27, debug-location !28
     DBG_VALUE debug-use %r2, debug-use _, !20, !27, debug-location !28
     DBG_VALUE debug-use %r3, debug-use _, !21, !27, debug-location !28
     %r1 = tMOVr killed %r2, 14, _, debug-location !32
     %r2 = tMOVr killed %r3, 14, _, debug-location !32
     tBL 14, _, @g, csr_aapcs, implicit-def dead %lr, implicit %sp, implicit %r0, implicit %r1, implicit %r2, implicit-def %sp, debug-location !32
     %r0 = t2MOVi 0, 14, _, _
     %sp = t2LDMIA_RET %sp, 14, _, def %r7, def %pc, implicit %r0
 
 ...