Generalize getInvertibleOperand recurrence handling slightly

[reames]

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.

[nikic]

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.

[reames]

In D100884#2703064, @nikic wrote:

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]

In D100884#2703133, @reames wrote:

In D100884#2703064, @nikic wrote:

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]

In D100884#2705497, @nikic wrote:

In D100884#2703133, @reames wrote:

In D100884#2703064, @nikic wrote:

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]

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

[reames]

rebase over added tests and update description

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

2531

Should probably be getInvertibleOperands (with s) now?

[nathanchance]

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

[reames]

In D100884#2724725, @nathanchance wrote:

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]

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.

llvm/lib/Analysis/ValueTracking.cpp

if (isa<ScalableVectorType>(V->getType()))
     return false;
 
   auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
   APInt DemandedElts =
       FVTy ? APInt::getAllOnesValue(FVTy->getNumElements()) : APInt(1, 1);
   return isKnownNonZero(V, DemandedElts, Depth, Q);
 }
 
-/// If the pair of operators are the same invertible function of a single
-/// operand return the index of that operand.  Otherwise, return None.  An
-/// invertible function is one that is 1-to-1 and maps every input value
-/// to exactly one output value.  This is equivalent to saying that Op1
-/// and Op2 are equal exactly when the specified pair of operands are equal,
-/// (except that Op1 and Op2 may be poison more often.)
-static Optional<unsigned> getInvertibleOperand(const Operator *Op1,
-                                               const Operator *Op2) {
+/// If the pair of operators are the same invertible function, return the
+/// the operands of the function corresponding to each input. Otherwise,
+/// return None.  An invertible function is one that is 1-to-1 and maps
+/// every input value to exactly one output value.  This is equivalent to
+/// saying that Op1 and Op2 are equal exactly when the specified pair of
+/// operands are equal, (except that Op1 and Op2 may be poison more often.)
+static Optional<std::pair<Value*, Value*>>
+getInvertibleOperands(const Operator *Op1,
   if (Op1->getOpcode() != Op2->getOpcode())
     return None;
 
+  auto getOperands = [&](unsigned OpNum) -> auto {
+    return std::make_pair(Op1->getOperand(OpNum), Op2->getOperand(OpNum));
+  };
+
   switch (Op1->getOpcode()) {
   default:
     break;
   case Instruction::Add:
   case Instruction::Sub:
     if (Op1->getOperand(0) == Op2->getOperand(0))
-      return 1;
+      return getOperands(1);
     if (Op1->getOperand(1) == Op2->getOperand(1))
-      return 0;
+      return getOperands(0);
     break;
   case Instruction::Mul: {
     // invertible if A * B == (A * B) mod 2^N where A, and B are integers
     // and N is the bitwdith.  The nsw case is non-obvious, but proven by
     // alive2: https://alive2.llvm.org/ce/z/Z6D5qK
     auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
     auto *OBO2 = cast<OverflowingBinaryOperator>(Op2);
     if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
         (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
       break;
 
     // Assume operand order has been canonicalized
     if (Op1->getOperand(1) == Op2->getOperand(1) &&
         isa<ConstantInt>(Op1->getOperand(1)) &&
         !cast<ConstantInt>(Op1->getOperand(1))->isZero())
-      return 0;
+      return getOperands(0);
     break;
   }
   case Instruction::Shl: {
     // Same as multiplies, with the difference that we don't need to check
     // for a non-zero multiply. Shifts always multiply by non-zero.
     auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
     auto *OBO2 = cast<OverflowingBinaryOperator>(Op2);
     if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
         (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
       break;
 
     if (Op1->getOperand(1) == Op2->getOperand(1))
-      return 0;
+      return getOperands(0);
     break;
   }
   case Instruction::AShr:
   case Instruction::LShr: {
     auto *PEO1 = cast<PossiblyExactOperator>(Op1);
     auto *PEO2 = cast<PossiblyExactOperator>(Op2);
     if (!PEO1->isExact() || !PEO2->isExact())
       break;
 
     if (Op1->getOperand(1) == Op2->getOperand(1))
-      return 0;
+      return getOperands(0);
     break;
   }
   case Instruction::SExt:
   case Instruction::ZExt:
     if (Op1->getOperand(0)->getType() == Op2->getOperand(0)->getType())
-      return 0;
+      return getOperands(0);
     break;
   case Instruction::PHI: {
     const PHINode *PN1 = cast<PHINode>(Op1);
     const PHINode *PN2 = cast<PHINode>(Op2);
 
     // If PN1 and PN2 are both recurrences, can we prove the entire recurrences
     // are a single invertible function of the start values? Note that repeated
     // application of an invertible function is also invertible
     BinaryOperator *BO1 = nullptr;
     Value *Start1 = nullptr, *Step1 = nullptr;
     BinaryOperator *BO2 = nullptr;
     Value *Start2 = nullptr, *Step2 = nullptr;
     if (PN1->getParent() != PN2->getParent() ||
         !matchSimpleRecurrence(PN1, BO1, Start1, Step1) ||
         !matchSimpleRecurrence(PN2, BO2, Start2, Step2))
       break;
 
-    Optional<unsigned> Idx = getInvertibleOperand(cast<Operator>(BO1),
-                                                  cast<Operator>(BO2));
-    if (!Idx || *Idx != 0)
+    auto Values = getInvertibleOperands(cast<Operator>(BO1),
+    if (!Values)
        break;
-    if (BO1->getOperand(*Idx) != PN1 || BO2->getOperand(*Idx) != PN2)
+
+    // We have to be careful of mutually defined recurrences here.  Ex:
+    // * X_i = X_(i-1) OP Y_(i-1), and Y_i = X_(i-1) OP V
+    // * X_i = Y_i = X_(i-1) OP Y_(i-1)
+    // The invertibility of these is complicated, and not worth reasoning
+    // about (yet?).
+    if (Values->first != PN1 || Values->second != PN2)
       break;
 
-    // Phi operands might not be in the same order.  TODO: generalize
-    // interface to return pair of operands.
-    if (PN1->getOperand(0) == BO1 && PN2->getOperand(0) == BO2)
-      return 1;
-    if (PN1->getOperand(1) == BO1 && PN2->getOperand(1) == BO2)
-      return 0;
+    return std::make_pair(Start1, Start2);
   }
   }
   return None;
 }
 
 /// Return true if V2 == V1 + X, where X is known non-zero.
 static bool isAddOfNonZero(const Value *V1, const Value *V2, unsigned Depth,
                            const Query &Q) {
if (Depth >= MaxAnalysisRecursionDepth)
     return false;
 
   // See if we can recurse through (exactly one of) our operands.  This
   // requires our operation be 1-to-1 and map every input value to exactly
   // one output value.  Such an operation is invertible.
   auto *O1 = dyn_cast<Operator>(V1);
   auto *O2 = dyn_cast<Operator>(V2);
   if (O1 && O2 && O1->getOpcode() == O2->getOpcode()) {
-    if (Optional<unsigned> Opt = getInvertibleOperand(O1, O2)) {
-      unsigned Idx = *Opt;
-      return isKnownNonEqual(O1->getOperand(Idx), O2->getOperand(Idx),
-                             Depth + 1, Q);
-    }
+    if (auto Values = getInvertibleOperands(O1, O2))
+      return isKnownNonEqual(Values->first, Values->second, Depth + 1, Q);
+
     if (const PHINode *PN1 = dyn_cast<PHINode>(V1)) {
       const PHINode *PN2 = cast<PHINode>(V2);
       // FIXME: This is missing a generalization to handle the case where one is
       // a PHI and another one isn't.
       if (isNonEqualPHIs(PN1, PN2, Depth, Q))
         return true;
     };
   }

llvm/test/Analysis/ValueTracking/known-non-equal.ll

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 1, [[A_IV]]
 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 1, [[B_IV]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [%iv.next, %loop], [0, %entry]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [%iv.next, %loop], [0, %entry]
   %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 1, [[A_IV]]
 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 1, [[B_IV]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]