Linux: Failed assertion in drivers/char/random.c with -fprofile-generate

[nathanchance]

While testing @gwelymernans 's PGO patch, I observe the following assertion failure:

$ make -skj"$(nproc)" LLVM=1 distclean defconfig

$ scripts/config -e PGO_CLANG

$ make -skj"$(nproc)" LLVM=1 olddefconfig drivers/char/random.o
clang-12: /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp:837: llvm::BasicBlock *llvm::SplitBlockPredecessors(llvm::BasicBlock *, ArrayRef<llvm::BasicBlock *>, const char *, llvm::DominatorTree *, llvm::LoopInfo *, llvm::MemorySSAUpdater *, bool): Assertion `!isa<CallBrInst>(Preds[i]->getTerminator()) && "Cannot split an edge from a CallBrInst"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12 -cc1 -triple x86_64-unknown-linux-gnu -S -disable-free -main-file-name random.c -mrelocation-model static -fno-delete-null-pointer-checks -mllvm -warn-stack-size=2048 -mframe-pointer=none -relaxed-aliasing -fmath-errno -fno-rounding-math -no-integrated-as -mconstructor-aliases -mcmodel=kernel -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -target-feature -sse -target-feature -mmx -target-feature -sse2 -target-feature -3dnow -target-feature -avx -target-feature -x87 -target-feature +retpoline-external-thunk -disable-red-zone -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -fprofile-instrument=llvm -nostdsysteminc -nobuiltininc -resource-dir /home/nathan/cbl/github/tc-build/build/llvm/stage1/lib/clang/12.0.0 -dependency-file drivers/char/.random.o.d -MT drivers/char/random.o -isystem /home/nathan/cbl/github/tc-build/build/llvm/stage1/lib/clang/12.0.0/include -include ./include/linux/kconfig.h -include ./include/linux/compiler_types.h -I ./arch/x86/include -I ./arch/x86/include/generated -I ./include -I ./arch/x86/include/uapi -I ./arch/x86/include/generated/uapi -I ./include/uapi -I ./include/generated/uapi -D __KERNEL__ -D KBUILD_MODFILE=\"drivers/char/random\" -D KBUILD_BASENAME=\"random\" -D KBUILD_MODNAME=\"random\" -fmacro-prefix-map=./= -O2 -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -Werror=implicit-function-declaration -Werror=implicit-int -Werror=return-type -Wno-format-security -Werror=unknown-warning-option -Wno-sign-compare -Wno-frame-address -Wno-address-of-packed-member -Wno-format-invalid-specifier -Wno-gnu -Wno-unused-const-variable -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -Wno-array-bounds -Werror=date-time -Werror=incompatible-pointer-types -Wno-initializer-overrides -Wno-format -Wno-sign-compare -Wno-format-zero-length -Wno-pointer-to-enum-cast -Wno-tautological-constant-out-of-range-compare -std=gnu89 -fno-dwarf-directory-asm -fdebug-compilation-dir /home/nathan/cbl/src/linux-pgo -ferror-limit 19 -fwrapv -stack-protector 2 -mstack-alignment=8 -fcf-protection=none -fwchar-type=short -fno-signed-wchar -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -o /tmp/random-6423ed.s -x c drivers/char/random.c
1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module 'drivers/char/random.c'.
4.      Running pass 'Loop Pass Manager' on function '@extract_buf'
5.      Running pass 'Loop Strength Reduction' on basic block '%do.body.i.i.do.body.i.i_crit_edge'
#0 0x00000000026e3073 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x26e3073)
#1 0x00000000026e0f1e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x26e0f1e)
#2 0x00000000026e353f SignalHandler(int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x26e353f)                                                                                                                                                         
#3 0x00007f11267a93c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
#4 0x00007f112626e18b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4618b)
#5 0x00007f112624d859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x25859)
#6 0x00007f112624d729 (/lib/x86_64-linux-gnu/libc.so.6+0x25729)
#7 0x00007f112625ef36 (/lib/x86_64-linux-gnu/libc.so.6+0x36f36)
#8 0x00000000026f0ef7 llvm::SplitBlockPredecessors(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DominatorTree*, llvm::LoopInfo*, llvm::MemorySSAUpdater*, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x26f0ef7)
#9 0x00000000026f9064 llvm::SplitCriticalEdge(llvm::Instruction*, unsigned int, llvm::CriticalEdgeSplittingOptions const&, llvm::Twine const&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x26f9064)
#10 0x0000000002529bcb (anonymous namespace)::LSRInstance::LSRInstance(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSAUpdater*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2529bcb)
#11 0x0000000002521f44 ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2521f44)
#12 0x000000000254bbf4 (anonymous namespace)::LoopStrengthReduce::runOnLoop(llvm::Loop*, llvm::LPPassManager&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x254bbf4)
#13 0x0000000001beccd3 llvm::LPPassManager::runOnFunction(llvm::Function&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x1beccd3)
#14 0x0000000002031168 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2031168)
#15 0x0000000002037de1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2037de1)
#16 0x000000000203178c llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x203178c)
#17 0x000000000291ebd6 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x291ebd6)
#18 0x00000000031b48fc clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x31b48fc)
#19 0x000000000391ece4 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x391ece4)
#20 0x0000000003115650 clang::FrontendAction::Execute() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x3115650)
#21 0x00000000030740ca clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x30740ca)
#22 0x00000000031ae878 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x31ae878)
#23 0x00000000015be8c2 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x15be8c2)
#24 0x00000000015bc59c ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x15bc59c)
#25 0x00000000015bc2dd main (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x15bc2dd)
#26 0x00007f112624f0b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b3)
#27 0x00000000015b934e _start (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x15b934e)
clang-12: error: unable to execute command: Aborted
clang-12: error: clang frontend command failed due to signal (use -v to see invocation)
...

cvise spuits out:

enum { false, true };
rdrand_int_ok, write_pool_count, random_ioctl_cmd, random_ioctl_bytes,
    random_ioctl_b;
_Bool _static_cpu_has() {
  asm goto("" : : : : t_yes, t_no);
t_yes:
  return true;
t_no:
  return false;
}
rdrand_int() {
  int retry = 0;
  do {
    asm("");
    if (rdrand_int_ok)
      return true;
  } while (--retry);
  return false;
}
_Bool arch_get_random_int() { return _static_cpu_has() ? rdrand_int() : false; }
random_ioctl() {
  switch (random_ioctl_cmd)
  case 0: {
    for (;; random_ioctl_b -= sizeof(int))
      if (!arch_get_random_int())
        break;
    write_pool_count -= random_ioctl_bytes;
  }
}

with this interestingness test.

[gwelymernans]

I think I found the issue. We're trying to split a critical edge from a callbr instruction during loop strength reduction. That's prohibited for indirect branches and case switches (landing pads are handled separately). We prohibit this in other places where we also prohibit the splitting of an indirect branch. The hacky fix is below. Checking to verify that it's the correct fix.

diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index d189d946ab42..886bcaa4e886 100644
--- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -5377,7 +5377,8 @@ void LSRInstance::RewriteForPHI(
       // users.
       if (e != 1 && BB->getTerminator()->getNumSuccessors() > 1 &&
           !isa<IndirectBrInst>(BB->getTerminator()) &&
-          !isa<CatchSwitchInst>(BB->getTerminator())) {
+          !isa<CatchSwitchInst>(BB->getTerminator()) &&
+          !isa<CallBrInst>(BB->getTerminator())) {
         BasicBlock *Parent = PN->getParent();
         Loop *PNLoop = LI.getLoopFor(Parent);
         if (!PNLoop || Parent != PNLoop->getHeader()) {

[gwelymernans]

Could someone help me create a testcase that replicates the failure using opt and llc? So far I'm having zero luck.

[gwelymernans]

Below is the patch I'm considering. I submitted a new patch to the lists that should cover the comments on the first patch.

diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index d189d946ab42..210ee8f8dfbf 100644
--- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -5579,16 +5579,23 @@ LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                         << "\n");
       return;
     }
-    // Bail out if we have a PHI on an EHPad that gets a value from a
-    // CatchSwitchInst.  Because the CatchSwitchInst cannot be split, there is
-    // no good place to stick any instructions.
+
     if (auto *PN = dyn_cast<PHINode>(U.getUser())) {
        auto *FirstNonPHI = PN->getParent()->getFirstNonPHI();
        if (isa<FuncletPadInst>(FirstNonPHI) ||
            isa<CatchSwitchInst>(FirstNonPHI))
+         // Bail out if we have a PHI on an EHPad that gets a value from a
+         // CatchSwitchInst. Because the CatchSwitchInst cannot be split, there
+         // is no good place to stick any instructions.
          for (BasicBlock *PredBB : PN->blocks())
            if (isa<CatchSwitchInst>(PredBB->getFirstNonPHI()))
              return;
+
+       // Also bail out if we have a PHI with a value from a block ending in a
+       // CallBrInst, because those also can't be split for similar reasons.
+       for (BasicBlock *PredBB : PN->blocks())
+         if (isa<CallBrInst>(PredBB->getTerminator()))
+           return;
     }
   }

[gwelymernans]

https://reviews.llvm.org/D94470

[nathanchance]

Yes, this appears to be good. I will throw it at 5.4, 5.10, and mainline with all of my configurations overnight to see if anything else explodes.

[MaskRay]

(Sorry that I requested changes on D94470.. I think BreakCriticalEdges likely needs a fix, regardless of the decision on LoopStrengthReduce. That is why I have added two other people on that patch.)

[gwelymernans]

Sorry I flew off the handle.

The thing with BreakCriticalEdges is that everyone knows it needs to be overhauled (this isn't the first time it's been discussed), but it always gets placed to the side or becomes more of a hassle than it's worth. I'd rather not deal with it for this patch though. :-)