[Local] Allow creating callbr with duplicate successors

[nikic]

Summary

Since D129288, callbr is allowed to have duplicate successors. This patch removes a limitation which prevents optimizations from actually producing such callbrs.

This is probably the riskiest of all the recent callbr changes, because code with incorrect assumptions might be lurking somewhere. I fixed the one case I encountered ahead of time in https://github.com/llvm/llvm-project/commit/8201e3ef5c84561260218bc041209611aac690e3.

[nikic]

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

77

I believe this change is correct, because we know from a previous condition that w0 must already be zero at this point. The full assembly is:

test3:                                  // @test3
  .cfi_startproc
// %bb.0:
  str x30, [sp, #-16]!                // 8-byte Folded Spill
  .cfi_def_cfa_offset 16
  .cfi_offset w30, -16
  bl  g
  cbz w0, .LBB2_3
// %bb.1:
  bl  i
  cmp w0, #0
  cset  w0, ne
.Ltmp4:                                 // Block address taken
// %bb.2:
  ldr x30, [sp], #16                  // 8-byte Folded Reload
  ret
.LBB2_3:
  //APP
.Ltmp5:
  nop
  .xword  c
  b .Ltmp4
  .xword  0
  //NO_APP
  ldr x30, [sp], #16                  // 8-byte Folded Reload
  ret
.Lfunc_end2:
  .size test3, .Lfunc_end2-test3
  .cfi_endproc
                                        // -- End function
  .hidden l                               // @l
  .type l,@object
  .comm l,4,4
  .section  ".note.GNU-stack","",@progbits

This code path is reached through the cbz w0.

[nickdesaulniers]

Thanks for fixing this up!

[nathanchance]

Sorry I didn't get a chance to report this until after it was merged (my first round of tests forgot to update Linux to fix some unrelated build breakage) but I see a crash in some PowerPC Linux kernel builds as a result of this change in net/ceph/messenger_v2.c. A reduced C reproducer below.

struct ceph_connection_v2_info {
  int in_state;
};
struct ceph_connection {
  struct {
    struct ceph_connection_v2_info v2;
  };
};
int process_message_header_con_0;
int ceph_con_in_msg_alloc(int *);
int prepare_read_tail_plain() { return 2; }
int process_message_header() {
  int skip = ceph_con_in_msg_alloc(&skip);
  if (skip)
    return 0;
  if (__builtin_constant_p(process_message_header_con_0))
    ;
  else
    asm goto("" : : : : __label_warn_on);
__label_warn_on:
  return 1;
}
int __handle_control() {
  int ret = process_message_header();
  if (ret == 0)
    return 0;
  return prepare_read_tail_plain();
}
void ceph_con_v2_try_read(struct ceph_connection *con) {
  for (;;) {
    struct ceph_connection __trans_tmp_3 = *con;
    switch (__trans_tmp_3.v2.in_state)
    case 1:
      __handle_control();
  }
}

$ clang --target=powerpc64le-linux-gnu -fno-PIE -O2 -c -o /dev/null messenger_v2.i
Use of %0 does not have a corresponding definition on every path:
fatal error: error in backend: Use not jointly dominated by defs.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: clang --target=powerpc64le-linux-gnu -fno-PIE -O2 -c -o /dev/null messenger_v2.i
1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module 'messenger_v2.i'.
4.      Running pass 'Live Interval Analysis' on function '@ceph_con_v2_try_read'
 #0 0x00005590013c98e3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4fdc8e3)
 #1 0x00005590013c787e llvm::sys::RunSignalHandlers() (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4fda87e)
 #2 0x0000559001349713 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x000055900134968f llvm::CrashRecoveryContext::HandleExit(int) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4f5c68f)
 #4 0x00005590013c40f7 llvm::sys::Process::Exit(int, bool) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4fd70f7)
 #5 0x0000558fff6a7772 (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x32ba772)
 #6 0x000055900134e599 llvm::report_fatal_error(llvm::Twine const&, bool) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4f61599)
 #7 0x000055900134e486 (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4f61486)
 #8 0x0000559000717b8c llvm::LiveRangeCalc::findReachingDefs(llvm::LiveRange&, llvm::MachineBasicBlock&, llvm::SlotIndex, unsigned int, llvm::ArrayRef<llvm::SlotIndex>) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x432ab8c)
 #9 0x0000559000716c96 llvm::LiveRangeCalc::extend(llvm::LiveRange&, llvm::SlotIndex, unsigned int, llvm::ArrayRef<llvm::SlotIndex>) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4329c96)
#10 0x000055900071a465 llvm::LiveIntervalCalc::extendToUses(llvm::LiveRange&, llvm::Register, llvm::LaneBitmask, llvm::LiveInterval*) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x432d465)
#11 0x000055900071a084 llvm::LiveIntervalCalc::calculate(llvm::LiveInterval&, bool) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x432d084)
#12 0x0000559000703542 llvm::LiveIntervals::computeVirtRegInterval(llvm::LiveInterval&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4316542)
#13 0x0000559000702131 llvm::LiveIntervals::computeVirtRegs() (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4315131)
#14 0x0000559000701f11 llvm::LiveIntervals::runOnMachineFunction(llvm::MachineFunction&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4314f11)
#15 0x0000559000778cbd llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x438bcbd)
#16 0x0000559000c263d7 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x48393d7)
#17 0x0000559000c2de81 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4840e81)
#18 0x0000559000c26de5 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4839de5)
#19 0x0000559001bccafd clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x57dfafd)
#20 0x0000559001fbec6e clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#21 0x000055900283e564 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x6451564)
#22 0x0000559001f02220 clang::FrontendAction::Execute() (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x5b15220)
#23 0x0000559001e752cf clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x5a882cf)
#24 0x0000559001fb8312 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x5bcb312)
#25 0x0000558fff6a7240 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x32ba240)
#26 0x0000558fff6a4f0f ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#27 0x0000559001cf4842 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const::$_1>(long) Job.cpp:0:0
#28 0x0000559001349627 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x4f5c627)
#29 0x0000559001cf439f clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x590739f)
#30 0x0000559001cb42fe clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x58c72fe)
#31 0x0000559001cb45ae clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x58c75ae)
#32 0x0000559001cd05d0 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x58e35d0)
#33 0x0000558fff6a458b clang_main(int, char**) (/home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin/clang-15+0x32b758b)
#34 0x00007f4538e10550 __libc_start_call_main (/lib64/libc.so.6+0x23550)
#35 0x00007f4538e10609 __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x23609)
#36 0x0000558fff6a1b35 _start /build/glibc/src/glibc/csu/../sysdeps/x86_64/start.S:117:0
clang-15: error: clang frontend command failed with exit code 70 (use -v to see invocation)
ClangBuiltLinux clang version 15.0.0 (https://github.com/llvm/llvm-project 08860f525a2363ccd697ebb3ff59769e37b1be21)
Target: powerpc64le-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/tmp/tmp.A3o6TI3QI1/install/llvm/08860f525a2363ccd697ebb3ff59769e37b1be21/bin
clang-15: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.

The same reproducer does not trigger on the parent commit. -fno-PIE is needed for reproducing the crash, it doesn't happen without it. If there is any more information that I can provide or patches I can test, please let me know!

[nickdesaulniers]

@nikic are you online to revert? Otherwise I will do so in 40 minutes.

Looks like early-tailduplication is messing up the predacessor lists, such that LiveRangeCalc::findReachingDefs chokes.

[nickdesaulniers]

Initial IR reduction:

; llc -O2 -mtriple=powerpc64le-unknown-linux-gnu reduced.ll
target datalayout = "e-m:e-i64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"

; Function Attrs: argmemonly nocallback nofree nosync nounwind willreturn
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #0

define void @ceph_con_v2_try_read(i32 %__trans_tmp_3.sroa.0.0.copyload, i1 %tobool.not.i.i) {
entry:
  %skip.i.i = alloca i32, i32 0, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.cond.backedge, %entry
  %cond = icmp eq i32 %__trans_tmp_3.sroa.0.0.copyload, 0
  br i1 %cond, label %sw.bb, label %for.cond.backedge

sw.bb:                                            ; preds = %for.cond
  %call.i.i2 = call i32 null(ptr %skip.i.i)
  br i1 %tobool.not.i.i, label %if.else.i.i, label %process_message_header.exit.i

if.else.i.i:                                      ; preds = %sw.bb
  callbr void asm sideeffect "", "!i"()
          to label %if.end.i [label %if.end.i]

process_message_header.exit.i:                    ; preds = %sw.bb
  call void @llvm.lifetime.end.p0(i64 0, ptr %skip.i.i)
  br label %for.cond.backedge

if.end.i:                                         ; preds = %if.else.i.i, %if.else.i.i
  call void @llvm.lifetime.end.p0(i64 0, ptr %skip.i.i)
  br label %for.cond.backedge

for.cond.backedge:                                ; preds = %if.end.i, %process_message_header.exit.i, %for.cond
  br label %for.cond
}

attributes #0 = { argmemonly nocallback nofree nosync nounwind willreturn }

[nickdesaulniers]

I think I have a fix:

diff --git a/llvm/lib/CodeGen/TailDuplicator.cpp b/llvm/lib/CodeGen/TailDuplicator.cpp
index 18507b8fa84f..dff17df42e74 100644
--- a/llvm/lib/CodeGen/TailDuplicator.cpp
+++ b/llvm/lib/CodeGen/TailDuplicator.cpp
@@ -799,6 +799,8 @@ bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,
     return false;
   if (!PredCond.empty())
     return false;
+  if (TailBB->isInlineAsmBrIndirectTarget())
+    return false;
   return true;
 }

[nikic]

In D129997#3663872, @nickdesaulniers wrote:

@nikic are you online to revert? Otherwise I will do so in 40 minutes.

Feel free to revert, I won't get around to this until tomorrow.

[nickdesaulniers]

Reverted in commit 1cf6b93df168 ("Revert "[Local] Allow creating callbr with duplicate successors"")

[nickdesaulniers]

Basically, before early-tailduplication we have:

bb.3.if.else.i.i:
; predecessors: %bb.2
  successors: %bb.5(0x80000000); %bb.5(100.00%)

  INLINEASM_BR &"" [sideeffect] [attdialect], $0:[imm], blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
  B %bb.5

bb.5.if.end.i (address-taken, inlineasm-br-indirect-target):
; predecessors: %bb.3
  successors: %bb.1(0x80000000); %bb.1(100.00%)

  LIFETIME_END %stack.0.skip.i.i
  B %bb.1

after:

bb.3.if.else.i.i:
; predecessors: %bb.2
  successors: %bb.1(0x80000000); %bb.1(100.00%)

  INLINEASM_BR &"" [sideeffect] [attdialect], $0:[imm], blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
  LIFETIME_END %stack.0.skip.i.i
  B %bb.1

bb.5.if.end.i (address-taken, inlineasm-br-indirect-target):
  successors: %bb.1(0x80000000); %bb.1(100.00%)

  LIFETIME_END %stack.0.skip.i.i
  B %bb.1

TailDuplicator::tailDuplicate<llvm/lib/CodeGen/TailDuplicator.cpp> has code like:

 866     // Remove PredBB's unconditional branch.                                    
 867     TII->removeBranch(*PredBB);
...
 887     // Update the CFG.                                                          
 888     PredBB->removeSuccessor(PredBB->succ_begin());

which is going to mess up the TailBB's predecessor list. (Notice: it's broken in the after example).

[nickdesaulniers]

I'm working on a MachineVerifier check for this case first.

[nickdesaulniers]

• rebase on top of D130127

[nickdesaulniers]

@nikic do you want to recommit this (once you have approved then landed D132609 then D130127 first), or shall I? I'm happy to ensure you retain authorship in git and commit the three.

[nathanchance]

With D132609, D130127, and D129997 applied, I do not see any crashes when compiling the Linux kernel with a variety of architectures and configurations.