[llvm][TailDuplicator] don't taildup isInlineAsmBrIndirectTargets

[nickdesaulniers]

Summary

This fixes a crash observed after
https://reviews.llvm.org/D129997.

Similar to D88823.

[nickdesaulniers]

Going to throw a -1 on this; I think we should instead revert https://reviews.llvm.org/D129997 for now. This patch needs the test case from https://reviews.llvm.org/D129997#3663878 added anyways.

I also think it might be something else going wrong in TailDuplicator::tailDuplicate that's messing up the predaccessor list.

[nickdesaulniers]

TODO: I should review the intent of llvm/test/CodeGen/X86/tail-dup-asm-goto.ll.

[nickdesaulniers]

• rebase, restore -filetype=obj tests, add previously crashing test case

[nickdesaulniers]

llvm/test/CodeGen/X86/tail-dup-asm-goto.ll

74

I should test that this crashes prior to my change, since the reproducer was found on ppc, though I don't think the issue is target specific. If so, I will pre-commit the additional test, and rebase this so we can better see the resulting changes to the test.

[nickdesaulniers]

llvm/test/CodeGen/X86/tail-dup-asm-goto.ll

74

Cool; yeah, after I rebase I should add -verify-machineinstrs to this test; it now asserts for this addition with the assertion I added recently in D130290.

[nickdesaulniers]

• rebase test onto D132609

[nickdesaulniers]

• remove fixme

[nickdesaulniers]

Sorry for the churn/delays here. This is now ready for review (as is the parent patch D132609 and child patch D129997).

[efriedma]

llvm/lib/CodeGen/TailDuplicator.cpp

801

If I'm understanding correctly, the issue here is that PredBB might contain an INLINEASM_BR. We're checking TailBB->isInlineAsmBrIndirectTarget because we don't have any convenient way to check the relevant property of PredBB. This makes the code in callbr-asm-outputs.ll, but we can't easily avoid it. Is that correct?

Please add a comment to explain that. And maybe we should consider adding some more direct way to check if a block contains an INLINEASM_BR.

[nickdesaulniers]

• rebase, add comment as per @efriedma

[nickdesaulniers]

• fix typo in comment. :set spell

[efriedma]

LGTM

[mingmingl]

llvm/lib/CodeGen/TailDuplicator.cpp

804–805

If I'm reading correctly, the 2nd condition is "the edge is from the indirect target list && TailBB is a fall-through block of PredBB". Correct me if I'm reading this wrong.

How is a fall-through TailBB different from a non-fall-through TailBB when it comes to corrupted successor/predecessor list? (This is purely for my education and thanks for any enlightening point!)

[nickdesaulniers]

llvm/lib/CodeGen/TailDuplicator.cpp

804–805

If I'm reading correctly, the 2nd condition is "the edge is from the indirect target list && TailBB is a fall-through block of PredBB". Correct me if I'm reading this wrong.

That's correct. If TailBB is a fallthrough block of PredBB, there is an edge from PredBB to TailBB. If PredBB contains an INLINEASM_BR, and TailBB is in the indirect target list, there is also an edge from PredBB to TailBB. TailDuplicator::tailDuplicate seems to make the assumption that MachineBasicBlocks can only have one edge from a predecessor to a successor, but that's not necessarily true, as my added test case demonstrates. But maybe there is some invariant that MachineBasicBlocks cannot have more than one edge between the same blocks? Maybe @MatzeB would know if such an invariant exists? While INLINEASM_BR is not a terminating instruction (today, it was, and might become so again), I can imagine a jcc .Ltmp1; jmp .Ltmp1; also getting messed up by TailDuplicator::tailDuplicate here (since there would also be 2 edges from pred to succ in that case as well).

How is a fall-through TailBB different from a non-fall-through TailBB when it comes to corrupted successor/predecessor list?

INLINEASM_BR has an explicit fallthough MBB. This may differ from what follows immediately after that MCinstr; there may be an explicit branch to another MBB, or no instruction (which I'd also call fallthrough, though that's implicit fallthrough as compared to INLINEASM_BR's explicit fallthrough).

This patch addresses a case of successor/predecessor list corruption stemming from TailDuplicator::tailDuplicate when TailBB is BOTH the explicit fallthrough of an INLINEASM_BR AND indirect target simultaneously.

This is purely for my education and thanks for any enlightening point!

Always! Never hesitate to ask; if there's a way I could modify the wording of the comment or commit message to make anything clearer; I'm open to suggestions. Otherwise I'll land this when I get back from lunch in ~1hr. Thanks for taking the time to look over my patch.

[mingmingl]

llvm/lib/CodeGen/TailDuplicator.cpp

804–805

TailDuplicator::tailDuplicate seems to make the assumption that MachineBasicBlocks can only have one edge from a predecessor to a successor, but that's not necessarily true, as my added test case demonstrates.

Ah I was also assuming there is only one edge from Pred to each one of its Succ. This is helpful!

This patch addresses a case of successor/predecessor list corruption stemming from TailDuplicator::tailDuplicate when TailBB is BOTH the explicit fallthrough of an INLINEASM_BR AND indirect target simultaneously.

To confirm my understanding, when TailBB is both the explicit fall through and implicit fall-through, tail-duplicate eliminate both edges (from PredBB to TailBB, and from INLINEASM_BR to TailBB) while INLINEASM_BR edge should be kept, is that correct? (if yes, I think I understand the issue better!)

I'm not a fan of terms, but just to clarify a little bit, does fall-through really mean the edge (that connects basic blocks) here? Ask since I originally thought fall-through indicates layout (e.g., TailBB is placed right after PredBB in the generated machine function) -> in that sense, whether TailBB is placed right after PredBB or not (i.e., whether TailBB is a layout fall-through or not), TailBB shouldn't be tail duplicated (otherwise, both edges are deleted and issue happen).

if there's a way I could modify the wording of the comment or commit message to make anything clearer; I'm open to suggestions.

Your explanation is much appreciated! Thanks for taking the time to reply!

It took me sometime to wrap my head and figure out what i missed, so don't bother with wording it again.

[nickdesaulniers]

llvm/lib/CodeGen/TailDuplicator.cpp

804–805

Oh, I'm mixing up the MCInstr (lower level IR) with the Instruction (higher level IR). INLINEASM_BR (MCInstr) does not have an explicit fallthrough. callbr (Instruction) does.

when TailBB is both the explicit fall through and implicit fall-through, tail-duplicate eliminate both edges (from PredBB to TailBB, and from INLINEASM_BR to TailBB) while INLINEASM_BR edge should be kept, is that correct?

That wasn't the specific case I was referring to, but I think the answer for that case would be still be "yes."

i.e.

%bb.4:
INLINEASM_BR &"", 1 /* sideeffect attdialect */, 13 /* imm */, %bb.5
JMP_1 %bb.5

so there's 2 edges from Pred (%bb.4) to Succ (%bb.5). It's probably ok for taildup to subsume the contents of %bb.5 into %bb.4, removing the JMP, but it should not remove %bb.5 from the successor list, because INLINEASM_BR still exists and hasn't been updated. I'm not sure yet if that transform is even profitable or not.

does fall-through really mean the edge (that connects basic blocks) here?

Yes, I believe MachineBasicBlocks don't need explicit terminators and may implicitly fallthrough. I might be mis-remembering though.

[mingmingl]

llvm/lib/CodeGen/TailDuplicator.cpp

804–805

so there's 2 edges from Pred (%bb.4) to Succ (%bb.5). It's probably ok for taildup to subsume the contents of %bb.5 into %bb.4, removing the JMP, but it should not remove %bb.5 from the successor list

Got it. Thanks again for the following up!! My previous confusion is from tie-ing 'fall-through' to block layout.

Re if duplicating is profitable or not, TailDuplicator::canTailDuplicate is used by both MachineBlockPlacement.cpp and TailDuplication.cpp. MBP pass queries this method to see if 'TailBB' can be placed into all its (unplaced) predecessor blocks when placing all blocks in a chain, so an answer 'no' (from PredBB1) (when it's performance neutral in PredBB1 -> TailBB edge, and correct to do so) may prevent 'TailBB' being duplicated into 'PredBB2' (if that reduces dynamic branches taken).

Yes, I believe MachineBasicBlocks don't need explicit terminators and may implicitly fallthrough.

This is true (e.g., anallyzeBranch depends on the implicit fall-through)

llvm/lib/CodeGen/TailDuplicator.cpp

if (PredBB->succ_size() > 1)
     return false;
 
   MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
   SmallVector<MachineOperand, 4> PredCond;
   if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
     return false;
   if (!PredCond.empty())
     return false;
+  // FIXME: This is overly conservative; it may be ok to relax this in the
+  // future under more specific conditions. If TailBB is an INLINEASM_BR
+  // indirect target, we need to see if the edge from PredBB to TailBB is from
+  // an INLINEASM_BR in PredBB, and then also if that edge was from the
+  // indirect target list, fallthrough/default target, or potentially both. If
+  // it's both, TailDuplicator::tailDuplicate will remove the edge, corrupting
+  // the successor list in PredBB and predecessor list in TailBB.
+  if (TailBB->isInlineAsmBrIndirectTarget())
+    return false;
   return true;
 }
 
 /// If it is profitable, duplicate TailBB's contents in each
 /// of its predecessors.
 /// \p IsSimple result of isSimpleBB
 /// \p TailBB   Block to be duplicated.
 /// \p ForcedLayoutPred  When non-null, use this block as the layout predecessor

llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll

 
 10:                                               ; preds = %7, %0, %6, %9
   ret i32 undef
 }
 
 ; CHECK-LABEL: <test3>:
 ; CHECK-LABEL: <$d.9>:
 ; CHECK-LABEL: <$x.10>:
-; CHECK-NEXT:    b {{.*}} <test3+0x18>
+; CHECK-NEXT:    b {{.*}} <$x.12+0x4>
 ; CHECK-LABEL: <$x.12>:
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ldr x30, [sp], #16
 ; CHECK-NEXT:    ret
 define internal i1 @test3() {
   %1 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)()
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %3, label %5

llvm/test/CodeGen/X86/callbr-asm-outputs.ll

 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    testl %ecx, %edx
 ; CHECK-NEXT:    testl %ecx, %edx
 ; CHECK-NEXT:    jne .LBB3_4
 ; CHECK-NEXT:    #NO_APP
 ; CHECK-NEXT:  # %bb.2: # %asm.fallthrough2
 ; CHECK-NEXT:    addl %edx, %ecx
 ; CHECK-NEXT:    movl %ecx, %eax
+; CHECK-NEXT:  .LBB3_4: # Block address taken
+; CHECK-NEXT:    # %return
+; CHECK-NEXT:    # Label of block must be emitted
 ; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB3_3: # Block address taken
 ; CHECK-NEXT:    # %label_true
 ; CHECK-NEXT:    # Label of block must be emitted
 ; CHECK-NEXT:    movl $-2, %eax
-; CHECK-NEXT:  .LBB3_4: # Block address taken
-; CHECK-NEXT:    # %return
-; CHECK-NEXT:    # Label of block must be emitted
-; CHECK-NEXT:    retl
+; CHECK-NEXT:    jmp .LBB3_4
 entry:
   %0 = callbr { i32, i32 } asm sideeffect "testl $0, $0; testl $1, $2; jne ${3:l}", "=r,=r,r,!i,!i,~{dirflag},~{fpsr},~{flags}"(i32 %out1)
           to label %asm.fallthrough [label %label_true, label %return]
 
 asm.fallthrough:                                  ; preds = %entry
   %asmresult = extractvalue { i32, i32 } %0, 0
   %asmresult1 = extractvalue { i32, i32 } %0, 1
   %1 = callbr { i32, i32 } asm sideeffect "testl $0, $1; testl $2, $3; jne ${5:l}", "=r,=r,r,r,!i,!i,~{dirflag},~{fpsr},~{flags}"(i32 %asmresult, i32 %asmresult1)

llvm/test/CodeGen/X86/tail-dup-asm-goto.ll

 ; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 ; RUN: llc -mtriple=x86_64-linux -stop-after=early-tailduplication \
-; RUN:   -verify-machineinstrs=0 < %s | FileCheck %s
+; RUN:  -verify-machineinstrs < %s | FileCheck %s
 
 ; Ensure that we don't duplicate a block with an "INLINEASM_BR" instruction
 ; during code gen.
 declare dso_local void @foo()
 
 define ptr @test1(ptr %arg1, ptr %arg2) {
   ; CHECK-LABEL: name: test1
   ; CHECK: bb.0.bb:

 
 bb17.i.i.i:                                       ; preds = %bb110
   br label %kmem_cache_has_cpu_partial.exit
 
 kmem_cache_has_cpu_partial.exit:                  ; preds = %bb110
   ret ptr %i10.1
 }
 
 ; The intent of this test is to test what happens when we have a callbr where
 ; BOTH the fallthrough/direct target and the indirect target are the same basic
 ; block. We might one day permit tail duplication here, but we need to ensure
 ; that we don't crash or run afoul of any MachineVerifier checks.
-; FIXME: enable -verify-machineinstrs for this test!
 define void @ceph_con_v2_try_read(i32 %__trans_tmp_3.sroa.0.0.copyload, i1 %tobool.not.i.i) nounwind {
   ; CHECK-LABEL: name: ceph_con_v2_try_read
   ; CHECK: bb.0.entry:
   ; CHECK-NEXT:   successors: %bb.1(0x80000000)
   ; CHECK-NEXT:   liveins: $edi, $esi
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr32 = COPY $esi
   ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gr32 = COPY $edi
define void @ceph_con_v2_try_read(i32 %__trans_tmp_3.sroa.0.0.copyload, i1 %tobool.not.i.i) nounwind {
   ; CHECK-NEXT:   CALL64r killed [[SUBREG_TO_REG]], csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $eax
   ; CHECK-NEXT:   ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
   ; CHECK-NEXT:   [[COPY3:%[0-9]+]]:gr32 = COPY $eax
   ; CHECK-NEXT:   TEST8ri [[COPY2]], 1, implicit-def $eflags
   ; CHECK-NEXT:   JCC_1 %bb.4, 4, implicit $eflags
   ; CHECK-NEXT:   JMP_1 %bb.3
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.3.if.else.i.i:
-  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT:   successors: %bb.5(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   INLINEASM_BR &"", 1 /* sideeffect attdialect */, 13 /* imm */, %bb.5
-  ; CHECK-NEXT:   LIFETIME_END %stack.0.skip.i.i
-  ; CHECK-NEXT:   JMP_1 %bb.1
+  ; CHECK-NEXT:   JMP_1 %bb.5
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.4.process_message_header.exit.i:
   ; CHECK-NEXT:   successors: %bb.1(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   LIFETIME_END %stack.0.skip.i.i
   ; CHECK-NEXT:   JMP_1 %bb.1
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.5.if.end.i (machine-block-address-taken, inlineasm-br-indirect-target):