This is an archive of the discontinued LLVM Phabricator instance.

Differential D94833

[LICM] permit CallBr critical edge to default dest to be split
AbandonedPublic

Authored by nickdesaulniers on Jan 15 2021, 3:07 PM.

Details

Reviewers
void
efriedma
jyknight
Summary

Follow up to
commit 2fe457690da0 ("Filter callbr insts from critical edge splitting")
@void and @efriedma pointed out in D88438 that we can split a critical
edge from a CallBrInst if that edge is to the default (non-indirect)
destination.

Permit this such an edge to be split for LICM, and as a result of
D88438, we can now drop the guard from llvm::SplitAllCriticalEdges() as
it will simply call into llvm::SplitCriticalEdge() and hit the guard
there that was newly added in D88438.

Realistically, we shouldn't often see a CallBrInst will no indirect
destinations (otherwise, why use CallBrInst, as CallInst would suffice),
but still a modest cleanup of llvm::SplitAllCriticalEdges().

Diff Detail

Event Timeline

nickdesaulniers created this revision.Jan 15 2021, 3:07 PM
Herald added subscribers: asbirlea, hiraditya. · View Herald TranscriptJan 15 2021, 3:07 PM
nickdesaulniers requested review of this revision.Jan 15 2021, 3:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 15 2021, 3:07 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B85434: Diff 317087.Jan 15 2021, 4:24 PM
nathanchance added a comment.Jan 21 2021, 7:35 AM

OpenSUSE's x86_64 config exposed an issue with this patch:

$ curl -LSso .config https://github.com/openSUSE/kernel-source/raw/master/config/x86_64/default

$ make -skj"$(nproc)" LLVM=1 olddefconfig mm/page_alloc.o
clang-12: /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp:897: llvm::BasicBlock *SplitBlockPredecessorsImpl(llvm::BasicBlock *, ArrayRef<llvm::BasicBlock *>, const char *, llvm::DomTreeUpdater *, 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: /tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12 -cc1 -triple x86_64-unknown-linux-gnu -S -disable-free -main-file-name page_alloc.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 -debug-info-kind=limited -dwarf-version=4 -debugger-tuning=gdb -nostdsysteminc -nobuiltininc -resource-dir /tmp/tmp.B700tKdD6c/llvm-D94833/lib/clang/12.0.0 -dependency-file mm/.page_alloc.o.d -MT mm/page_alloc.o -isystem /tmp/tmp.B700tKdD6c/llvm-D94833/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 CONFIG_X86_X32_ABI -D CC_USING_FENTRY -D KBUILD_MODFILE=\"mm/page-alloc\" -D KBUILD_BASENAME=\"page_alloc\" -D KBUILD_MODNAME=\"page_alloc\" -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 -ferror-limit 19 -pg -mfentry -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/page_alloc-d529d5.s -x c mm/page_alloc.c
1.	<eof> parser at end of file
2.	Per-module optimization passes
3.	Running pass 'CallGraph Pass Manager' on module 'mm/page_alloc.c'.
4.	Running pass 'Loop Pass Manager' on function '@__rmqueue_pcplist'
5.	Running pass 'Loop Invariant Code Motion' on basic block '%do.body'
 #0 0x0000000002694313 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x2694313)
 #1 0x00000000026920ce llvm::sys::RunSignalHandlers() (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x26920ce)
 #2 0x00000000026947df SignalHandler(int) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x26947df)
 #3 0x00007f633a6733c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
 #4 0x00007f633a13818b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4618b)
 #5 0x00007f633a117859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x25859)
 #6 0x00007f633a117729 (/lib/x86_64-linux-gnu/libc.so.6+0x25729)
 #7 0x00007f633a128f36 (/lib/x86_64-linux-gnu/libc.so.6+0x36f36)
 #8 0x00000000026a23db SplitBlockPredecessorsImpl(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DomTreeUpdater*, llvm::DominatorTree*, llvm::LoopInfo*, llvm::MemorySSAUpdater*, bool) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x26a23db)
 #9 0x00000000026a1caf llvm::SplitBlockPredecessors(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DominatorTree*, llvm::LoopInfo*, llvm::MemorySSAUpdater*, bool) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x26a1caf)
#10 0x000000000248998f llvm::sinkRegion(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::Loop*, llvm::AliasSetTracker*, llvm::MemorySSAUpdater*, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x248998f)
#11 0x000000000248732e (anonymous namespace)::LoopInvariantCodeMotion::runOnLoop(llvm::Loop*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::ScalarEvolution*, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter*) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x248732e)
#12 0x0000000002492b59 (anonymous namespace)::LegacyLICMPass::runOnLoop(llvm::Loop*, llvm::LPPassManager&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x2492b59)
#13 0x0000000001bb7ba3 llvm::LPPassManager::runOnFunction(llvm::Function&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1bb7ba3)
#14 0x0000000001fef788 llvm::FPPassManager::runOnFunction(llvm::Function&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1fef788)
#15 0x0000000001cfe273 (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1cfe273)
#16 0x0000000001fefdac llvm::legacy::PassManagerImpl::run(llvm::Module&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1fefdac)
#17 0x00000000028ca2d5 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> >) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x28ca2d5)
#18 0x000000000312e2dc clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x312e2dc)
#19 0x0000000003853924 clang::ParseAST(clang::Sema&, bool, bool) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x3853924)
#20 0x0000000003090e60 clang::FrontendAction::Execute() (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x3090e60)
#21 0x0000000002fee80a clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x2fee80a)
#22 0x0000000003128278 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x3128278)
#23 0x0000000001599322 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1599322)
#24 0x0000000001597252 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1597252)
#25 0x0000000001596fc2 main (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x1596fc2)
#26 0x00007f633a1190b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b3)
#27 0x000000000159412e _start (/tmp/tmp.B700tKdD6c/llvm-D94833/bin/clang-12+0x159412e)
clang-12: error: unable to execute command: Aborted
clang-12: error: clang frontend command failed due to signal (use -v to see invocation)
ClangBuiltLinux clang version 12.0.0 (https://github.com/llvm/llvm-project d27b6116abcc793ec4545b213e442014d667cdb1)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /tmp/tmp.B700tKdD6c/llvm-D94833/bin

cvise spits out:

check_new_pcp_page, __rmqueue_pcplist_list_0;
*__rmqueue_pcplist_page;
enum { false, true } arch_static_branch() {
  asm goto("" : : : : l_yes);
  return false;
l_yes:
  return true;
}
_Bool check_new_pcp() {
  _Bool __trans_tmp_1 = ({ arch_static_branch(); });
  if (__trans_tmp_1)
    return check_new_pcp_page;
}
*__rmqueue_pcplist() {
  do {
    if (list_empty())
      return 0;
    __rmqueue_pcplist_page = __rmqueue_pcplist_list_0;
  } while (check_new_pcp());
  return __rmqueue_pcplist_list_0;
}

and it can be reproduced with just clang -O2 -c -o /dev/null page_alloc.i.

nickdesaulniers mentioned this in D129205: [BasicBlockUtils] Allow splitting predecessors with callbr terminators.Jul 6 2022, 9:37 AM

See also: https://reviews.llvm.org/D129205.

Herald added a project: Restricted Project. · View Herald TranscriptJul 6 2022, 9:38 AM
nickdesaulniers abandoned this revision.Jul 6 2022, 2:42 PM

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
10 lines
Utils/
10 lines

Diff 317087

llvm/lib/Transforms/Scalar/LICM.cpp

Show First 20 Lines • Show All 1,536 Lines • ▼ Show 20 Linesstatic bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
if (!BB->canSplitPredecessors()) if (!BB->canSplitPredecessors())
return false; return false;
// It's not impossible to split EHPad blocks, but if BlockColors already exist // It's not impossible to split EHPad blocks, but if BlockColors already exist
// it require updating BlockColors for all offspring blocks accordingly. By // it require updating BlockColors for all offspring blocks accordingly. By
// skipping such corner case, we can make updating BlockColors after splitting // skipping such corner case, we can make updating BlockColors after splitting
// predecessor fairly simple. // predecessor fairly simple.
if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad()) if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad())
return false; return false;
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { for (BasicBlock *BBPred : predecessors(BB)) {
BasicBlock *BBPred = *PI; const Instruction *T = BBPred->getTerminator();
if (isa<IndirectBrInst>(BBPred->getTerminator()) || if (auto *CBR = dyn_cast<CallBrInst>(T))
Lint: Pre-merge checks
Inline Actions

clang-tidy: warning: 'auto *CBR' can be declared as 'const auto *CBR' [llvm-qualified-auto]
not useful

Lint: Pre-merge checks: clang-tidy: warning: 'auto *CBR' can be declared as 'const auto *CBR' [llvm-qualified-auto]…
isa<CallBrInst>(BBPred->getTerminator())) if (CBR->getDefaultDest() != BB)
return false;
if (isa<IndirectBrInst>(T))
return false; return false;
} }
return true; return true;
} }
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
LoopInfo *LI, const Loop *CurLoop, LoopInfo *LI, const Loop *CurLoop,
LoopSafetyInfo *SafetyInfo, LoopSafetyInfo *SafetyInfo,
▲ Show 20 Lines • Show All 803 Lines • Show Last 20 Lines

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

Show First 20 Lines • Show All 527 Lines • ▼ Show 20 Lines
} }
unsigned unsigned
llvm::SplitAllCriticalEdges(Function &F, llvm::SplitAllCriticalEdges(Function &F,
const CriticalEdgeSplittingOptions &Options) { const CriticalEdgeSplittingOptions &Options) {
unsigned NumBroken = 0; unsigned NumBroken = 0;
for (BasicBlock &BB : F) { for (BasicBlock &BB : F) {
Instruction *TI = BB.getTerminator(); Instruction *TI = BB.getTerminator();
if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) && if (isa<IndirectBrInst>(TI))
!isa<CallBrInst>(TI)) continue;
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
Lint: Pre-merge checks
Inline Actions

clang-tidy: warning: invalid case style for variable 'i' [readability-identifier-naming]
not useful
clang-tidy: warning: invalid case style for variable 'e' [readability-identifier-naming]
not useful

Lint: Pre-merge checks: clang-tidy: warning: invalid case style for variable 'i' [readability-identifier-naming]…
if (SplitCriticalEdge(TI, i, Options)) if (SplitCriticalEdge(TI, i, Options))
++NumBroken; ++NumBroken;
} }
return NumBroken; return NumBroken;
} }
static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt,
DomTreeUpdater *DTU, DominatorTree *DT, DomTreeUpdater *DTU, DominatorTree *DT,
LoopInfo *LI, MemorySSAUpdater *MSSAU, LoopInfo *LI, MemorySSAUpdater *MSSAU,
const Twine &BBName, bool Before) { const Twine &BBName, bool Before) {
▲ Show 20 Lines • Show All 1,031 Lines • Show Last 20 Lines