This is an archive of the discontinued LLVM Phabricator instance.

Generalize getInvertibleOperand recurrence handling slightly
ClosedPublic

Authored by reames on Apr 20 2021, 1:12 PM.

Details

Summary

Follow up to D99912, specifically the revert, fix, and reapply thereof.

This generalizes the invertible recurrence logic in two ways:

  • By allowing mismatching operand numbers of the phi, we can recurse through a pair of phi recurrences whose operand orders have not been canonicalized.
  • By allowing recurrences through operand 1, we can invert these odd (but legal) recurrence.

Diff Detail

Event Timeline

reames created this revision.Apr 20 2021, 1:12 PM
reames requested review of this revision.Apr 20 2021, 1:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 20 2021, 1:12 PM
nikic added a comment.Apr 20 2021, 2:30 PM

I don't think this is particularly valuable in terms of optimization power, but I do think the interface makes a bit more sense that way. Though I would suggest to go one step further and return std::pair<Value *, Value *>. That is, for a pair of input values, it returns a pair of output values that preserve the equality relationship. This should make the phi case particularly nice, because you can simply return {Start1, Start2} rather than checking for different possibilities of operand orders.

I don't think this is particularly valuable in terms of optimization power, but I do think the interface makes a bit more sense that way. Though I would suggest to go one step further and return std::pair<Value *, Value *>. That is, for a pair of input values, it returns a pair of output values that preserve the equality relationship. This should make the phi case particularly nice, because you can simply return {Start1, Start2} rather than checking for different possibilities of operand orders.

I played with this, but it turns out a bit more ugly than it sounds. It requires a bunch of duplicated boilerplate for the non-phi return points, and more importantly, greatly complicates the check to see that the recurrence is the LHS of the operation. I really didn't care for the resulting code structure.

nikic added a comment.Apr 21 2021, 9:15 AM

I don't think this is particularly valuable in terms of optimization power, but I do think the interface makes a bit more sense that way. Though I would suggest to go one step further and return std::pair<Value *, Value *>. That is, for a pair of input values, it returns a pair of output values that preserve the equality relationship. This should make the phi case particularly nice, because you can simply return {Start1, Start2} rather than checking for different possibilities of operand orders.

I played with this, but it turns out a bit more ugly than it sounds. It requires a bunch of duplicated boilerplate for the non-phi return points, and more importantly, greatly complicates the check to see that the recurrence is the LHS of the operation. I really didn't care for the resulting code structure.

Right, the LHS check would become rather ugly ... but upon further consideration, why do we need that check at all? I believe the logic holds either way. While a cycle over sub 0, %A and sub 0, %B is certainly odd, the reasoning (sequence of invertible operations) remains correct.

I believe it would be correct to reduce the phi case to just:

auto Values = getInvertibleOperand(cast<Operator>(BO1), cast<Operator>(BO2));
if (!Values)
  break;
assert(Values->first == PN1 && Values->second == PN2);
return std::make_pair(Start1, Start2);
reames planned changes to this revision.Apr 25 2021, 12:31 PM

I don't think this is particularly valuable in terms of optimization power, but I do think the interface makes a bit more sense that way. Though I would suggest to go one step further and return std::pair<Value *, Value *>. That is, for a pair of input values, it returns a pair of output values that preserve the equality relationship. This should make the phi case particularly nice, because you can simply return {Start1, Start2} rather than checking for different possibilities of operand orders.

I played with this, but it turns out a bit more ugly than it sounds. It requires a bunch of duplicated boilerplate for the non-phi return points, and more importantly, greatly complicates the check to see that the recurrence is the LHS of the operation. I really didn't care for the resulting code structure.

Right, the LHS check would become rather ugly ... but upon further consideration, why do we need that check at all? I believe the logic holds either way. While a cycle over sub 0, %A and sub 0, %B is certainly odd, the reasoning (sequence of invertible operations) remains correct.

I believe it would be correct to reduce the phi case to just:

auto Values = getInvertibleOperand(cast<Operator>(BO1), cast<Operator>(BO2));
if (!Values)
  break;
assert(Values->first == PN1 && Values->second == PN2);
return std::make_pair(Start1, Start2);

I think you are correct here. I had to stare at this a bit, but I'm not seeing any problems with it.

I'll go back to the Value approach and add tests for these cases next week.

reames updated this revision to Diff 341303.Apr 28 2021, 1:36 PM

Reworked using pair of values, pending test update, rebase, and description change.

reames updated this revision to Diff 341309.Apr 28 2021, 1:52 PM
reames retitled this revision from Generalize getInvertibleOperand to support mismatched phi operand order to Generalize getInvertibleOperand recurrence handling slightly.
reames edited the summary of this revision. (Show Details)

rebase over added tests and update description

nikic accepted this revision.Apr 28 2021, 2:26 PM

LGTM

llvm/lib/Analysis/ValueTracking.cpp
2531

Should probably be getInvertibleOperands (with s) now?

This revision is now accepted and ready to land.Apr 28 2021, 2:26 PM
This revision was landed with ongoing or failed builds.Apr 28 2021, 2:38 PM
This revision was automatically updated to reflect the committed changes.
nathanchance added a subscriber: nathanchance.EditedApr 28 2021, 9:38 PM

This patch breaks compiling the Linux kernel for 32-bit ARM when using KASAN:

$ make -skj"$(nproc)" ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- LLVM=1 LLVM_IAS=1 distclean allmodconfig drivers/vhost/vringh.o
clang: /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Analysis/ValueTracking.cpp:2608: Optional<std::pair<Value *, Value *>> getInvertibleOperands(const llvm::Operator *, const llvm::Operator *): Assertion `Values->first == PN1 && Values->second == PN2' 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 -mlittle-endian -Qunused-arguments -fmacro-prefix-map=./= -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE -Werror=implicit-function-declaration -Werror=implicit-int -Werror=return-type -Wno-format-security -std=gnu89 -Werror=unknown-warning-option --target=arm-linux-gnueabi -integrated-as -fno-dwarf2-cfi-asm -mabi=aapcs-linux -mfpu=vfp -funwind-tables -meabi gnu -marm -march=armv6k -mtune=arm1136j-s -msoft-float -fno-delete-null-pointer-checks -Wno-frame-address -Wno-address-of-packed-member -O2 -Wframe-larger-than=1024 -fstack-protector-strong -Wno-format-invalid-specifier -Wno-gnu -mno-global-merge -Wno-unused-const-variable -ftrivial-auto-var-init=pattern -fno-stack-clash-protection -pg -falign-functions=32 -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -Wno-array-bounds -fno-strict-overflow -fno-stack-check -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 -fsanitize=kernel-address -mllvm -asan-mapping-offset=0x9f000000 -mllvm -asan-globals=1 -mllvm -asan-instrumentation-with-call-threshold=0 -mllvm -asan-stack=0 --param asan-instrument-allocas=1 -fsanitize-coverage=trace-pc -fsanitize-coverage=trace-cmp -Wa,-W -nostdinc -isystem /home/nathan/cbl/github/tc-build/build/llvm/stage1/lib/clang/13.0.0/include -I./arch/arm/include -I./arch/arm/include/generated -I./include -I./arch/arm/include/uapi -I./arch/arm/include/generated/uapi -I./include/uapi -I./include/generated/uapi -include ./include/linux/compiler-version.h -include ./include/linux/kconfig.h -include ./include/linux/compiler_types.h -D__KERNEL__ -D__LINUX_ARM_ARCH__=6 -Uarm -DMODULE -DKBUILD_BASENAME=\"vringh\" -DKBUILD_MODNAME=\"vringh\" -D__KBUILD_MODNAME=kmod_vringh -c -Wp,-MMD,drivers/vhost/.vringh.o.d -fcolor-diagnostics -o drivers/vhost/vringh.o drivers/vhost/vringh.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000000002e47bc3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2e47bc3)
 #1 0x0000000002e45a2e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2e45a2e)
 #2 0x0000000002dd6273 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x0000000002dd63ae CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007fb7dbbba960 __restore_rt sigaction.c:0:0
 #5 0x00007fb7db6acef5 raise (/usr/lib/libc.so.6+0x3cef5)
 #6 0x00007fb7db696862 abort (/usr/lib/libc.so.6+0x26862)
 #7 0x00007fb7db696747 _nl_load_domain.cold loadmsgcat.c:0:0
 #8 0x00007fb7db6a5646 (/usr/lib/libc.so.6+0x35646)
 #9 0x00000000021f60fd (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x21f60fd)
#10 0x00000000021d5176 isKnownNonEqual(llvm::Value const*, llvm::Value const*, unsigned int, (anonymous namespace)::Query const&) ValueTracking.cpp:0:0
#11 0x00000000021d506e llvm::isKnownNonEqual(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, llvm::AssumptionCache*, llvm::Instruction const*, llvm::DominatorTree const*, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x21d506e)
#12 0x000000000207953c SimplifyICmpInst(unsigned int, llvm::Value*, llvm::Value*, llvm::SimplifyQuery const&, unsigned int) InstructionSimplify.cpp:0:0
#13 0x0000000002081db1 llvm::SimplifyInstruction(llvm::Instruction*, llvm::SimplifyQuery const&, llvm::OptimizationRemarkEmitter*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2081db1)
#14 0x000000000356bd50 simplifyLoopInst(llvm::Loop&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::AssumptionCache&, llvm::TargetLibraryInfo const&, llvm::MemorySSAUpdater*) LoopInstSimplify.cpp:0:0
#15 0x000000000356b56a llvm::LoopInstSimplifyPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x356b56a)
#16 0x000000000415601d llvm::detail::PassModel<llvm::Loop, llvm::LoopInstSimplifyPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) PassBuilder.cpp:0:0
#17 0x000000000419419f llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x419419f)
#18 0x0000000004193ef7 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x4193ef7)
#19 0x00000000041935df llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x41935df)
#20 0x000000000414bd6d llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) PassBuilder.cpp:0:0
#21 0x000000000419531d llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x419531d)
#22 0x00000000041566dd llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#23 0x00000000027c6e35 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x27c6e35)
#24 0x0000000003518a2d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) BackendUtil.cpp:0:0
#25 0x000000000282cc3e llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x282cc3e)
#26 0x0000000004159ebd llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) PassBuilder.cpp:0:0
#27 0x0000000002827328 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2827328)
#28 0x0000000002919a5d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) Inliner.cpp:0:0
#29 0x000000000282aeda llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x282aeda)
#30 0x0000000002919d9d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) Inliner.cpp:0:0
#31 0x0000000002829370 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2829370)
#32 0x0000000002919bfd llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) Inliner.cpp:0:0
#33 0x00000000027c57b8 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x27c57b8)
#34 0x0000000002917ab2 llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2917ab2)
#35 0x000000000415a16d llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) PassBuilder.cpp:0:0
#36 0x00000000027c57b8 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x27c57b8)
#37 0x000000000350ee2a (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) BackendUtil.cpp:0:0
#38 0x0000000003508f4c 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/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3508f4c)
#39 0x0000000003993e41 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#40 0x00000000042bb034 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x42bb034)
#41 0x00000000038e9fd0 clang::FrontendAction::Execute() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x38e9fd0)
#42 0x00000000038610ea clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x38610ea)
#43 0x000000000398dd18 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x398dd18)
#44 0x0000000001ab9904 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1ab9904)
#45 0x0000000001ab72ad ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#46 0x0000000003708942 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
#47 0x0000000002dd6187 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2dd6187)
#48 0x00000000037084a7 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/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x37084a7)
#49 0x00000000036d05d8 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x36d05d8)
#50 0x00000000036d08d7 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x36d08d7)
#51 0x00000000036e9251 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x36e9251)
#52 0x0000000001ab6b76 main (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1ab6b76)
#53 0x00007fb7db697b25 __libc_start_main (/usr/lib/libc.so.6+0x27b25)
#54 0x0000000001ab3efe _start (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1ab3efe)
clang-13: error: clang frontend command failed with exit code 134 (use -v to see invocation)
ClangBuiltLinux clang version 13.0.0 (https://github.com/llvm/llvm-project 0c01b37eeb18a51a7e9c9153330d8009de0f600e)
Target: arm-unknown-linux-gnueabi
Thread model: posix
InstalledDir: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin
clang-13: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-13: note: diagnostic msg: /tmp/vringh-18be9e.c
clang-13: note: diagnostic msg: /tmp/vringh-18be9e.sh
clang-13: note: diagnostic msg: 

********************
make[3]: *** [scripts/Makefile.build:273: drivers/vhost/vringh.o] Error 134
make[3]: Target '__build' not remade because of errors.
make[2]: *** [scripts/Makefile.build:534: drivers/vhost] Error 2
make[2]: Target '__build' not remade because of errors.
make[1]: *** [Makefile:1967: drivers] Error 2
make[1]: Target 'drivers/vhost/vringh.o' not remade because of errors.
make: *** [Makefile:353: __build_one_by_one] Error 2
make: Target 'distclean' not remade because of errors.
make: Target 'allmodconfig' not remade because of errors.
make: Target 'drivers/vhost/vringh.o' not remade because of errors.

A reduced reproducer:

$ cat vringh.i
_Bool no_range_check() {}
__vringh_iov(_Bool rcheck()) {
  int desc_1, len;
again:
  len = desc_1;
  if (rcheck(&len))
    if (__builtin_expect(len != desc_1, 0)) {
      desc_1 = desc_1 - len;
      goto again;
    }
}
copydesc_kern() { __vringh_iov(no_range_check); }

$ clang --target=arm-linux-gnueabi -march=armv6k -O2 -c -o /dev/null vringh.i
vringh.i:1:25: warning: non-void function does not return a value [-Wreturn-type]
_Bool no_range_check() {}
                        ^
vringh.i:2:1: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
__vringh_iov(_Bool rcheck()) {
^
vringh.i:11:1: warning: non-void function does not return a value [-Wreturn-type]
}
^
vringh.i:12:1: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
copydesc_kern() { __vringh_iov(no_range_check); }
^
vringh.i:12:49: warning: non-void function does not return a value [-Wreturn-type]
copydesc_kern() { __vringh_iov(no_range_check); }
                                                ^
5 warnings generated.

$ clang --target=arm-linux-gnueabi -march=armv6k -O2 -fsanitize=kernel-address -c -o /dev/null vringh.i
vringh.i:1:25: warning: non-void function does not return a value [-Wreturn-type]
_Bool no_range_check() {}
                        ^
vringh.i:2:1: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
__vringh_iov(_Bool rcheck()) {
^
vringh.i:11:1: warning: non-void function does not return a value [-Wreturn-type]
}
^
vringh.i:12:1: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
copydesc_kern() { __vringh_iov(no_range_check); }
^
vringh.i:12:49: warning: non-void function does not return a value [-Wreturn-type]
copydesc_kern() { __vringh_iov(no_range_check); }
                                                ^
clang: /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Analysis/ValueTracking.cpp:2608: Optional<std::pair<Value *, Value *>> getInvertibleOperands(const llvm::Operator *, const llvm::Operator *): Assertion `Values->first == PN1 && Values->second == PN2' 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: clang --target=arm-linux-gnueabi -march=armv6k -O2 -fsanitize=kernel-address -c -o /dev/null vringh.i
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000000002e47bc3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2e47bc3)
 #1 0x0000000002e45a2e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2e45a2e)
 #2 0x0000000002dd6273 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x0000000002dd63ae CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007f011e70d960 __restore_rt sigaction.c:0:0
 #5 0x00007f011e1ffef5 raise (/usr/lib/libc.so.6+0x3cef5)
 #6 0x00007f011e1e9862 abort (/usr/lib/libc.so.6+0x26862)
 #7 0x00007f011e1e9747 _nl_load_domain.cold loadmsgcat.c:0:0
 #8 0x00007f011e1f8646 (/usr/lib/libc.so.6+0x35646)
 #9 0x00000000021f60fd (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x21f60fd)
#10 0x00000000021d5176 isKnownNonEqual(llvm::Value const*, llvm::Value const*, unsigned int, (anonymous namespace)::Query const&) ValueTracking.cpp:0:0
#11 0x00000000021d506e llvm::isKnownNonEqual(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, llvm::AssumptionCache*, llvm::Instruction const*, llvm::DominatorTree const*, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x21d506e)
#12 0x000000000207953c SimplifyICmpInst(unsigned int, llvm::Value*, llvm::Value*, llvm::SimplifyQuery const&, unsigned int) InstructionSimplify.cpp:0:0
#13 0x0000000002a02160 llvm::InstCombinerImpl::visitICmpInst(llvm::ICmpInst&) InstCombineCompares.cpp:0:0
#14 0x000000000298e100 llvm::InstCombinerImpl::run() InstructionCombining.cpp:0:0
#15 0x00000000029900d8 combineInstructionsOverFunction(llvm::Function&, llvm::InstCombineWorklist&, llvm::AAResults*, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::OptimizationRemarkEmitter&, llvm::BlockFrequencyInfo*, llvm::ProfileSummaryInfo*, unsigned int, llvm::LoopInfo*) InstructionCombining.cpp:0:0
#16 0x000000000298f80a llvm::InstCombinePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x298f80a)
#17 0x0000000004155c3d llvm::detail::PassModel<llvm::Function, llvm::InstCombinePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#18 0x00000000027c6e35 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x27c6e35)
#19 0x0000000003518a2d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) BackendUtil.cpp:0:0
#20 0x000000000282cc3e llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x282cc3e)
#21 0x0000000004159ebd llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) PassBuilder.cpp:0:0
#22 0x0000000002827328 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2827328)
#23 0x0000000002919a5d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) Inliner.cpp:0:0
#24 0x000000000282aeda llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x282aeda)
#25 0x0000000002919d9d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) Inliner.cpp:0:0
#26 0x0000000002829370 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2829370)
#27 0x0000000002919bfd llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) Inliner.cpp:0:0
#28 0x00000000027c57b8 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x27c57b8)
#29 0x0000000002917ab2 llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2917ab2)
#30 0x000000000415a16d llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) PassBuilder.cpp:0:0
#31 0x00000000027c57b8 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x27c57b8)
#32 0x000000000350ee2a (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) BackendUtil.cpp:0:0
#33 0x0000000003508f4c 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/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3508f4c)
#34 0x0000000003993e41 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#35 0x00000000042bb034 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x42bb034)
#36 0x00000000038e9fd0 clang::FrontendAction::Execute() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x38e9fd0)
#37 0x00000000038610ea clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x38610ea)
#38 0x000000000398dd18 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x398dd18)
#39 0x0000000001ab9904 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1ab9904)
#40 0x0000000001ab72ad ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#41 0x0000000003708942 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
#42 0x0000000002dd6187 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2dd6187)
#43 0x00000000037084a7 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/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x37084a7)
#44 0x00000000036d05d8 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x36d05d8)
#45 0x00000000036d08d7 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x36d08d7)
#46 0x00000000036e9251 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x36e9251)
#47 0x0000000001ab6b76 main (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1ab6b76)
#48 0x00007f011e1eab25 __libc_start_main (/usr/lib/libc.so.6+0x27b25)
#49 0x0000000001ab3efe _start (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1ab3efe)
clang-13: error: clang frontend command failed with exit code 134 (use -v to see invocation)
ClangBuiltLinux clang version 13.0.0 (https://github.com/llvm/llvm-project 0c01b37eeb18a51a7e9c9153330d8009de0f600e)
Target: arm-unknown-linux-gnueabi
Thread model: posix
InstalledDir: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin
clang-13: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.

Full preprocessed file is available here: https://github.com/nathanchance/creduce-files/tree/87c4dc5b9ed63eeaba8347eeb32b5d128a54de0e/D100884-arm

This patch breaks compiling the Linux kernel for 32-bit ARM when using KASAN:

Reverted for the moment. I'm not going to have a chance to look at this for a day or so, revert to green in the meantime.

Thank you for the reduced example. I should be able to figure out what's going fairly quickly.

reames reopened this revision.May 3 2021, 3:23 PM
This revision is now accepted and ready to land.May 3 2021, 3:23 PM
reames added a comment.May 3 2021, 3:27 PM

It turns out the issue which triggered the revert was latent in the previous code as well. Sanjay fixed that in 15a4233. The root issue was that with the current definition of recurrence we can have two recurrence phis which share an increment. I had not realized this, and thus the overly strong asserts.

Now that the reduced test case has been submitted, I'm going to tweak this one and resubmit.