[SLP]Improve analysis of same/alternate code ops and scheduling.

[ABataev]

Summary

Should improve compile time for analysis and vectorization.

Metric: SLP.NumVectorInstructions

Program SLP.NumVectorInstructions
test-suite :: External/SPEC/CINT2017speed/623.xalancbmk_s/623.xalancbmk_s.test 6380.00 6378.00 -0.0%
test-suite :: External/SPEC/CINT2017rate/523.xalancbmk_r/523.xalancbmk_r.test 6380.00 6378.00 -0.0%
test-suite :: External/SPEC/CINT2006/483.xalancbmk/483.xalancbmk.test 2023.00 2022.00 -0.0%
test-suite :: External/SPEC/CINT2006/471.omnetpp/471.omnetpp.test 148.00 146.00 -1.4%

Generated more vector instructions.

[ABataev]

Ping!

[vdmitrie]

I'm not sure about how the test case affected supposed to execute the changes.
Could you please consider adding more tests to be clearer about the patch purpose?

[ABataev]

In D127531#3602215, @vdmitrie wrote:

I'm not sure about how the test case affected supposed to execute the changes.
Could you please consider adding more tests to be clearer about the patch purpose?

It is for compile time mostly, nothing else. Just allows to detect gathered elements before scheduling.

[vdmitrie]

In D127531#3602238, @ABataev wrote:

In D127531#3602215, @vdmitrie wrote:

I'm not sure about how the test case affected supposed to execute the changes.
Could you please consider adding more tests to be clearer about the patch purpose?

It is for compile time mostly, nothing else. Just allows to detect gathered elements before scheduling.

Yes, but the summary also says more vector instructions generated. What specific cases are handled now but failed previously?

[ABataev]

In D127531#3602270, @vdmitrie wrote:

In D127531#3602238, @ABataev wrote:

In D127531#3602215, @vdmitrie wrote:

I'm not sure about how the test case affected supposed to execute the changes.
Could you please consider adding more tests to be clearer about the patch purpose?

It is for compile time mostly, nothing else. Just allows to detect gathered elements before scheduling.

Yes, but the summary also says more vector instructions generated. What specific cases are handled now but failed previously?

1-2 more instruction. The effect is caused by the better operand reordering. getSameOpcode is used to detect compatible operations, when SLP tries to find better ordering of the operands. The patch just make getSameOpcode a bit better on detecting such compatible ops.

[ABataev]

Rebase

[ABataev]

Ping!

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

I'm not sure I understand why this is scored as alternating opcodes.
If underlying objects are same that probably means Dist variable must have a value and the value is 0.
i.e. these loads are from same location. right? It sounds like splat load.
Where alternating opcodes come from?

7317

TTI argument is unused.

11805

TTI argument is unused.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

No. If you have Geps with non-const indices, the Dist might be None. But the loads still may be the source of masked gather.

7317

Will remove

11805

Will remove

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

No. If you have Geps with non-const indices, the Dist might be None. But the loads still may be the source of masked gather.

Ah. right. I forgot that we now vectorize non-const indices. But still, why alternate opcode?
It sounds like we need to introduce named constant dedicated to gather.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

Because we return alternate if the distance is very big and most probably will result in masked gather with constant indices.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

That seems to only confirm my suggestion - we need to introduce dedicated named constant and fix that place too. Even though it does have same value semantics is different.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

Why semnatics is different? Still same masked gather.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

It is masked gather load but has nothing to do with alternate ops

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

Ah, I see. I suggest to add something like MaskedGatherCandidate and use here and for large Dists.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1205

Exactly!

[ABataev]

Rebase + address comments

[vdmitrie]

Looks good. Thanks!

[kda]

Looks like this is breaking MSAN buildbot: https://lab.llvm.org/buildbot/#/builders/74/builds/14584

Log snippet:

[90/6916] Building CXX object lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o
FAILED: lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o 
/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/lib/CodeGen -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/CodeGen -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/include -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/include -nostdinc++ -isystem /b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/include -isystem /b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/include/c++/v1 -fsanitize=memory -fsanitize-memory-use-after-dtor -fsanitize-memory-param-retval -Oz -mllvm -sanitizer-early-opt-ep -Wl,--rpath=/b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/lib -L/b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/lib -w -stdlib=libc++ -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-class-memaccess -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fno-omit-frame-pointer -gline-tables-only -fsanitize=memory -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG  -fno-exceptions -fno-rtti -UNDEBUG -std=c++17 -MD -MT lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o -MF lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o.d -o lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o -c /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/CodeGen/LLVMTargetMachine.cpp
clang++: /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/IR/Type.cpp:688: static llvm::FixedVectorType *llvm::FixedVectorType::get(llvm::Type *, unsigned int): Assertion `isValidElementType(ElementType) && "Element type of a VectorType must " "be an integer, floating point, or " "pointer type."' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/lib/CodeGen -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/CodeGen -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/include -I/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/include -nostdinc++ -isystem /b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/include -isystem /b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/include/c++/v1 -fsanitize=memory -fsanitize-memory-use-after-dtor -fsanitize-memory-param-retval -Oz -mllvm -sanitizer-early-opt-ep -Wl,--rpath=/b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/lib -L/b/sanitizer-x86_64-linux-bootstrap-msan/build/libcxx_build_msan/lib -w -stdlib=libc++ -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-class-memaccess -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fno-omit-frame-pointer -gline-tables-only -fsanitize=memory -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -fno-exceptions -fno-rtti -UNDEBUG -std=c++17 -MD -MT lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o -MF lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o.d -o lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/LLVMTargetMachine.cpp.o -c /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/CodeGen/LLVMTargetMachine.cpp
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000558f40a8a9f3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x72919f3)
 #1 0x0000558f40a889ce llvm::sys::RunSignalHandlers() (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x728f9ce)
 #2 0x0000558f409f216e (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x0000558f409f23c0 CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007f31965f6520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #5 0x00007f319664aa7c pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x96a7c)
 #6 0x00007f31965f6476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #7 0x00007f31965dc7f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #8 0x00007f31965dc71b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #9 0x00007f31965ede96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
#10 0x0000558f4031d348 llvm::FixedVectorType::get(llvm::Type*, unsigned int) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x6b24348)
#11 0x0000558f40cea9ff llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getShallowScore(llvm::Value*, llvm::Value*, llvm::Instruction*, llvm::Instruction*, llvm::ArrayRef<llvm::Value*>) const SLPVectorizer.cpp:0:0
#12 0x0000558f40ce9c40 llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getScoreAtLevelRec(llvm::Value*, llvm::Value*, llvm::Instruction*, llvm::Instruction*, int, llvm::ArrayRef<llvm::Value*>) const SLPVectorizer.cpp:0:0
#13 0x0000558f40ce9fbd llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getScoreAtLevelRec(llvm::Value*, llvm::Value*, llvm::Instruction*, llvm::Instruction*, int, llvm::ArrayRef<llvm::Value*>) const SLPVectorizer.cpp:0:0
#14 0x0000558f40ce9404 llvm::slpvectorizer::BoUpSLP::VLOperands::getLookAheadScore(llvm::Value*, llvm::Value*, llvm::ArrayRef<llvm::Value*>, int, unsigned int, unsigned int, bool&) SLPVectorizer.cpp:0:0
#15 0x0000558f40ce8200 llvm::slpvectorizer::BoUpSLP::VLOperands::getBestOperand(unsigned int, int, int, llvm::ArrayRef<llvm::slpvectorizer::BoUpSLP::VLOperands::ReorderingMode>, llvm::ArrayRef<llvm::Value*>) SLPVectorizer.cpp:0:0
#16 0x0000558f40cc2843 llvm::slpvectorizer::BoUpSLP::VLOperands::reorder() SLPVectorizer.cpp:0:0
#17 0x0000558f40cb5118 llvm::slpvectorizer::BoUpSLP::reorderInputsAccordingToOpcode(llvm::ArrayRef<llvm::Value*>, llvm::SmallVectorImpl<llvm::Value*>&, llvm::SmallVectorImpl<llvm::Value*>&, llvm::TargetLibraryInfo const&, llvm::DataLayout const&, llvm::ScalarEvolution&, llvm::slpvectorizer::BoUpSLP const&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74bc118)
#18 0x0000558f40cab0bd llvm::slpvectorizer::BoUpSLP::buildTree_rec(llvm::ArrayRef<llvm::Value*>, unsigned int, llvm::slpvectorizer::BoUpSLP::EdgeInfo const&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74b20bd)
#19 0x0000558f40cae733 llvm::slpvectorizer::BoUpSLP::buildTree(llvm::ArrayRef<llvm::Value*>) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74b5733)
#20 0x0000558f40cdcb95 llvm::SLPVectorizerPass::tryToVectorizeList(llvm::ArrayRef<llvm::Value*>, llvm::slpvectorizer::BoUpSLP&, bool) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74e3b95)
#21 0x0000558f40ce2d59 bool tryToVectorizeSequence<llvm::Value>(llvm::SmallVectorImpl<llvm::Value*>&, llvm::function_ref<unsigned int (llvm::Value*)>, llvm::function_ref<bool (llvm::Value*, llvm::Value*)>, llvm::function_ref<bool (llvm::Value*, llvm::Value*)>, llvm::function_ref<bool (llvm::ArrayRef<llvm::Value*>, bool)>, bool) SLPVectorizer.cpp:0:0
#22 0x0000558f40ce2661 llvm::SLPVectorizerPass::vectorizeSimpleInstructions(llvm::SmallSetVector<llvm::Instruction*, 8u>&, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, bool) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74e9661)
#23 0x0000558f40cd7db2 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74dedb2)
#24 0x0000558f40cd57cc llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74dc7cc)
#25 0x0000558f40cd4c87 llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x74dbc87)
#26 0x0000558f41e4a95d llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#27 0x0000558f40307ee5 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x6b0eee5)
#28 0x0000558f3e93e9dd 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>&) AMDGPUTargetMachine.cpp:0:0
#29 0x0000558f4030bd7c llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x6b12d7c)
#30 0x0000558f3e93e78d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) AMDGPUTargetMachine.cpp:0:0
#31 0x0000558f403070a5 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x6b0e0a5)
#32 0x0000558f4132b596 (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>&, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile>>&) BackendUtil.cpp:0:0
#33 0x0000558f41323b0d 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>>) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7b2ab0d)
#34 0x0000558f4178a959 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#35 0x0000558f42a1e25f clang::ParseAST(clang::Sema&, bool, bool) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x922525f)
#36 0x0000558f416a6f30 clang::FrontendAction::Execute() (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7eadf30)
#37 0x0000558f4161477f clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7e1b77f)
#38 0x0000558f41783ce3 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7f8ace3)
#39 0x0000558f3e5ef3b2 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x4df63b2)
#40 0x0000558f3e5ecf52 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#41 0x0000558f4148c4c2 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 0x0000558f409f1fe9 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x71f8fe9)
#43 0x0000558f4148bd20 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7c92d20)
#44 0x0000558f4144f27e clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7c5627e)
#45 0x0000558f4144f52e clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7c5652e)
#46 0x0000558f4146c4a0 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x7c734a0)
#47 0x0000558f3e5ec5ad clang_main(int, char**) (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x4df35ad)
#48 0x00007f31965ddd90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#49 0x00007f31965dde40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#50 0x0000558f3e5e9a65 _start (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin/clang+++0x4df0a65)
clang-16: error: clang frontend command failed with exit code 134 (use -v to see invocation)
clang version 16.0.0 (https://github.com/llvm/llvm-project.git 7841f557ea3df1987ceb1c033e458790f5828795)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build0/bin
clang-16: note: diagnostic msg: 
********************
PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-16: note: diagnostic msg: /tmp/LLVMTargetMachine-972989.cpp
clang-16: note: diagnostic msg: /tmp/LLVMTargetMachine-972989.sh
clang-16: note: diagnostic msg: 
*******************

[paulkirth]

We're seeing some Clang assertion failures in the Fuchsia build. I've bisected it down to this patch.

You can find the failing bot here: https://ci.chromium.org/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.arm64-release/b8799099192459783297/overview

I've filed an issue on github with the reproducer: https://github.com/llvm/llvm-project/issues/58675

[paulkirth]

If this will take some time to fix, would you mind reverting until a fix is ready?

[ABataev]

In D127531#3892537, @paulkirth wrote:

If this will take some time to fix, would you mind reverting until a fix is ready?

Will do, though after this it definitely won't be fixed

[paulkirth]

hey, sorry, I think I grabbed the wrong commit from my bisect earlier, so I think your patch is fine. I hope you didn't waste too much time over this.

[uabelho]

Hello,

The following starts crashing with this patch:
opt --passes=slp-vectorizer bbi-75302.ll -o /dev/null

I get

opt: ../include/llvm/ADT/ArrayRef.h:256: const T &llvm::ArrayRef<llvm::Value *>::operator[](size_t) const [T = llvm::Value *]: Assertion `Index < Length && "Invalid index!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: build-all/bin/opt --passes=slp-vectorizer /home/uabelho/bbi-75302.ll -o /dev/null
 #0 0x0000000002e58093 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/opt+0x2e58093)
 #1 0x0000000002e55dae llvm::sys::RunSignalHandlers() (build-all/bin/opt+0x2e55dae)
 #2 0x0000000002e58416 SignalHandler(int) (build-all/bin/opt+0x2e58416)
 #3 0x00007ff50079f630 __restore_rt (/lib64/libpthread.so.0+0xf630)
 #4 0x00007ff4fdee6387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007ff4fdee7a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007ff4fdedf1a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007ff4fdedf252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000002f40627 (build-all/bin/opt+0x2f40627)
 #9 0x00000000030ae5b2 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry*) (build-all/bin/opt+0x30ae5b2)
#10 0x00000000030aa658 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::ArrayRef<llvm::Value*>) (build-all/bin/opt+0x30aa658)
#11 0x00000000030ab1e7 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry*) (build-all/bin/opt+0x30ab1e7)
#12 0x00000000030b2659 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::MapVector<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u>, llvm::DenseMap<llvm::Value*, unsigned int, llvm::DenseMapInfo<llvm::Value*, void>, llvm::detail::DenseMapPair<llvm::Value*, unsigned int> >, std::vector<std::pair<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u> >, std::allocator<std::pair<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u> > > > >&) (build-all/bin/opt+0x30b2659)
#13 0x00000000030d9d6f (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) (build-all/bin/opt+0x30d9d6f)
#14 0x00000000030c7588 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (build-all/bin/opt+0x30c7588)
#15 0x00000000030c8969 llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (build-all/bin/opt+0x30c8969)
#16 0x00000000030bf821 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (build-all/bin/opt+0x30bf821)
#17 0x00000000030bd85c llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (build-all/bin/opt+0x30bd85c)
#18 0x00000000030bcbff llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x30bcbff)
#19 0x00000000031c7c4d llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x31c7c4d)
#20 0x000000000266850c llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x266850c)
#21 0x0000000000aefdbd 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>&) (build-all/bin/opt+0xaefdbd)
#22 0x000000000266c7ee llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x266c7ee)
#23 0x0000000000aefb9d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0xaefb9d)
#24 0x00000000026677bc llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x26677bc)
#25 0x0000000000721779 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (build-all/bin/opt+0x721779)
#26 0x0000000000730c61 main (build-all/bin/opt+0x730c61)
#27 0x00007ff4fded2555 __libc_start_main (/lib64/libc.so.6+0x22555)
#28 0x000000000071a3e0 _start (build-all/bin/opt+0x71a3e0)
Abort

bbi-75302.ll1 KBDownload

[ABataev]

In D127531#3896257, @uabelho wrote:

Hello,

The following starts crashing with this patch:
opt --passes=slp-vectorizer bbi-75302.ll -o /dev/null

I get

opt: ../include/llvm/ADT/ArrayRef.h:256: const T &llvm::ArrayRef<llvm::Value *>::operator[](size_t) const [T = llvm::Value *]: Assertion `Index < Length && "Invalid index!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: build-all/bin/opt --passes=slp-vectorizer /home/uabelho/bbi-75302.ll -o /dev/null
 #0 0x0000000002e58093 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/opt+0x2e58093)
 #1 0x0000000002e55dae llvm::sys::RunSignalHandlers() (build-all/bin/opt+0x2e55dae)
 #2 0x0000000002e58416 SignalHandler(int) (build-all/bin/opt+0x2e58416)
 #3 0x00007ff50079f630 __restore_rt (/lib64/libpthread.so.0+0xf630)
 #4 0x00007ff4fdee6387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007ff4fdee7a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007ff4fdedf1a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007ff4fdedf252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000002f40627 (build-all/bin/opt+0x2f40627)
 #9 0x00000000030ae5b2 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry*) (build-all/bin/opt+0x30ae5b2)
#10 0x00000000030aa658 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::ArrayRef<llvm::Value*>) (build-all/bin/opt+0x30aa658)
#11 0x00000000030ab1e7 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry*) (build-all/bin/opt+0x30ab1e7)
#12 0x00000000030b2659 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::MapVector<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u>, llvm::DenseMap<llvm::Value*, unsigned int, llvm::DenseMapInfo<llvm::Value*, void>, llvm::detail::DenseMapPair<llvm::Value*, unsigned int> >, std::vector<std::pair<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u> >, std::allocator<std::pair<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u> > > > >&) (build-all/bin/opt+0x30b2659)
#13 0x00000000030d9d6f (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) (build-all/bin/opt+0x30d9d6f)
#14 0x00000000030c7588 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (build-all/bin/opt+0x30c7588)
#15 0x00000000030c8969 llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (build-all/bin/opt+0x30c8969)
#16 0x00000000030bf821 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (build-all/bin/opt+0x30bf821)
#17 0x00000000030bd85c llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (build-all/bin/opt+0x30bd85c)
#18 0x00000000030bcbff llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x30bcbff)
#19 0x00000000031c7c4d llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x31c7c4d)
#20 0x000000000266850c llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x266850c)
#21 0x0000000000aefdbd 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>&) (build-all/bin/opt+0xaefdbd)
#22 0x000000000266c7ee llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x266c7ee)
#23 0x0000000000aefb9d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0xaefb9d)
#24 0x00000000026677bc llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x26677bc)
#25 0x0000000000721779 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (build-all/bin/opt+0x721779)
#26 0x0000000000730c61 main (build-all/bin/opt+0x730c61)
#27 0x00007ff4fded2555 __libc_start_main (/lib64/libc.so.6+0x22555)
#28 0x000000000071a3e0 _start (build-all/bin/opt+0x71a3e0)
Abort

bbi-75302.ll1 KBDownload

Not a bug in the patch itself, it revealed the issue in the existing code. Will send a patch in few minutes.

[ABataev]

In D127531#3896257, @uabelho wrote:

Hello,

The following starts crashing with this patch:
opt --passes=slp-vectorizer bbi-75302.ll -o /dev/null

I get

opt: ../include/llvm/ADT/ArrayRef.h:256: const T &llvm::ArrayRef<llvm::Value *>::operator[](size_t) const [T = llvm::Value *]: Assertion `Index < Length && "Invalid index!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: build-all/bin/opt --passes=slp-vectorizer /home/uabelho/bbi-75302.ll -o /dev/null
 #0 0x0000000002e58093 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/opt+0x2e58093)
 #1 0x0000000002e55dae llvm::sys::RunSignalHandlers() (build-all/bin/opt+0x2e55dae)
 #2 0x0000000002e58416 SignalHandler(int) (build-all/bin/opt+0x2e58416)
 #3 0x00007ff50079f630 __restore_rt (/lib64/libpthread.so.0+0xf630)
 #4 0x00007ff4fdee6387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007ff4fdee7a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007ff4fdedf1a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007ff4fdedf252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000002f40627 (build-all/bin/opt+0x2f40627)
 #9 0x00000000030ae5b2 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry*) (build-all/bin/opt+0x30ae5b2)
#10 0x00000000030aa658 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::ArrayRef<llvm::Value*>) (build-all/bin/opt+0x30aa658)
#11 0x00000000030ab1e7 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry*) (build-all/bin/opt+0x30ab1e7)
#12 0x00000000030b2659 llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::MapVector<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u>, llvm::DenseMap<llvm::Value*, unsigned int, llvm::DenseMapInfo<llvm::Value*, void>, llvm::detail::DenseMapPair<llvm::Value*, unsigned int> >, std::vector<std::pair<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u> >, std::allocator<std::pair<llvm::Value*, llvm::SmallVector<llvm::Instruction*, 2u> > > > >&) (build-all/bin/opt+0x30b2659)
#13 0x00000000030d9d6f (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) (build-all/bin/opt+0x30d9d6f)
#14 0x00000000030c7588 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (build-all/bin/opt+0x30c7588)
#15 0x00000000030c8969 llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (build-all/bin/opt+0x30c8969)
#16 0x00000000030bf821 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (build-all/bin/opt+0x30bf821)
#17 0x00000000030bd85c llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (build-all/bin/opt+0x30bd85c)
#18 0x00000000030bcbff llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x30bcbff)
#19 0x00000000031c7c4d llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x31c7c4d)
#20 0x000000000266850c llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x266850c)
#21 0x0000000000aefdbd 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>&) (build-all/bin/opt+0xaefdbd)
#22 0x000000000266c7ee llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x266c7ee)
#23 0x0000000000aefb9d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0xaefb9d)
#24 0x00000000026677bc llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x26677bc)
#25 0x0000000000721779 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (build-all/bin/opt+0x721779)
#26 0x0000000000730c61 main (build-all/bin/opt+0x730c61)
#27 0x00007ff4fded2555 __libc_start_main (/lib64/libc.so.6+0x22555)
#28 0x000000000071a3e0 _start (build-all/bin/opt+0x71a3e0)
Abort

bbi-75302.ll1 KBDownload

Must be fixed in 99f9bd4807d6132b603a1910902e4586e20638e0

[uabelho]

Thanks!

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 static bool isValidForAlternation(unsigned Opcode) {
   if (Instruction::isIntDivRem(Opcode))
     return false;
 
   return true;
 }
 
 static InstructionsState getSameOpcode(ArrayRef<Value *> VL,
+                                       const TargetLibraryInfo &TLI,
                                        unsigned BaseIndex = 0);
 
 /// Checks if the provided operands of 2 cmp instructions are compatible, i.e.
 /// compatible instructions or constants, or just some other regular values.
 static bool areCompatibleCmpOps(Value *BaseOp0, Value *BaseOp1, Value *Op0,
-                                Value *Op1) {
+                                Value *Op1, const TargetLibraryInfo &TLI) {
   return (isConstant(BaseOp0) && isConstant(Op0)) ||
          (isConstant(BaseOp1) && isConstant(Op1)) ||
          (!isa<Instruction>(BaseOp0) && !isa<Instruction>(Op0) &&
           !isa<Instruction>(BaseOp1) && !isa<Instruction>(Op1)) ||
-         getSameOpcode({BaseOp0, Op0}).getOpcode() ||
-         getSameOpcode({BaseOp1, Op1}).getOpcode();
+         getSameOpcode({BaseOp0, Op0}, TLI).getOpcode() ||
+         getSameOpcode({BaseOp1, Op1}, TLI).getOpcode();
 }
 
 /// \returns analysis of the Instructions in \p VL described in
 /// InstructionsState, the Opcode that we suppose the whole list
 /// could be vectorized even if its structure is diverse.
 static InstructionsState getSameOpcode(ArrayRef<Value *> VL,
+                                       const TargetLibraryInfo &TLI,
                                        unsigned BaseIndex) {
   // Make sure these are all Instructions.
   if (llvm::any_of(VL, [](Value *V) { return !isa<Instruction>(V); }))
     return InstructionsState(VL[BaseIndex], nullptr, nullptr);
 
   bool IsCastOp = isa<CastInst>(VL[BaseIndex]);
   bool IsBinOp = isa<BinaryOperator>(VL[BaseIndex]);
   bool IsCmpOp = isa<CmpInst>(VL[BaseIndex]);
   CmpInst::Predicate BasePred =
       IsCmpOp ? cast<CmpInst>(VL[BaseIndex])->getPredicate()
               : CmpInst::BAD_ICMP_PREDICATE;
   unsigned Opcode = cast<Instruction>(VL[BaseIndex])->getOpcode();
   unsigned AltOpcode = Opcode;
   unsigned AltIndex = BaseIndex;
 
   // Check for one alternate opcode from another BinaryOperator.
   // TODO - generalize to support all operators (types, calls etc.).
+  auto *IBase = cast<Instruction>(VL[BaseIndex]);
+  Intrinsic::ID BaseID = 0;
+  SmallVector<VFInfo> BaseMappings;
+  if (auto *CallBase = dyn_cast<CallInst>(IBase)) {
+    BaseID = getVectorIntrinsicIDForCall(CallBase, &TLI);
+    BaseMappings = VFDatabase(*CallBase).getMappings(*CallBase);
+    if (!isTriviallyVectorizable(BaseID) && BaseMappings.empty())
+      return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+  }
   for (int Cnt = 0, E = VL.size(); Cnt < E; Cnt++) {
-    unsigned InstOpcode = cast<Instruction>(VL[Cnt])->getOpcode();
-    if (IsBinOp && isa<BinaryOperator>(VL[Cnt])) {
+    auto *I = cast<Instruction>(VL[Cnt]);
+    unsigned InstOpcode = I->getOpcode();
+    if (IsBinOp && isa<BinaryOperator>(I)) {
       if (InstOpcode == Opcode || InstOpcode == AltOpcode)
         continue;
       if (Opcode == AltOpcode && isValidForAlternation(InstOpcode) &&
           isValidForAlternation(Opcode)) {
         AltOpcode = InstOpcode;
         AltIndex = Cnt;
         continue;
       }
-    } else if (IsCastOp && isa<CastInst>(VL[Cnt])) {
-      Type *Ty0 = cast<Instruction>(VL[BaseIndex])->getOperand(0)->getType();
-      Type *Ty1 = cast<Instruction>(VL[Cnt])->getOperand(0)->getType();
+    } else if (IsCastOp && isa<CastInst>(I)) {
+      Value *Op0 = IBase->getOperand(0);
+      Type *Ty0 = Op0->getType();
+      Value *Op1 = I->getOperand(0);
+      Type *Ty1 = Op1->getType();
       if (Ty0 == Ty1) {
         if (InstOpcode == Opcode || InstOpcode == AltOpcode)
           continue;
         if (Opcode == AltOpcode) {
           assert(isValidForAlternation(Opcode) &&
                  isValidForAlternation(InstOpcode) &&
                  "Cast isn't safe for alternation, logic needs to be updated!");
           AltOpcode = InstOpcode;
if (IsBinOp && isa<BinaryOperator>(I)) {
         CmpInst::Predicate CurrentPred =
             cast<CmpInst>(VL[Cnt])->getPredicate();
         CmpInst::Predicate SwappedCurrentPred =
             CmpInst::getSwappedPredicate(CurrentPred);
         // Check for compatible operands. If the corresponding operands are not
         // compatible - need to perform alternate vectorization.
         if (InstOpcode == Opcode) {
           if (BasePred == CurrentPred &&
-              areCompatibleCmpOps(BaseOp0, BaseOp1, Op0, Op1))
+              areCompatibleCmpOps(BaseOp0, BaseOp1, Op0, Op1, TLI))
             continue;
           if (BasePred == SwappedCurrentPred &&
-              areCompatibleCmpOps(BaseOp0, BaseOp1, Op1, Op0))
+              areCompatibleCmpOps(BaseOp0, BaseOp1, Op1, Op0, TLI))
             continue;
           if (E == 2 &&
               (BasePred == CurrentPred || BasePred == SwappedCurrentPred))
             continue;
           auto *AltInst = cast<CmpInst>(VL[AltIndex]);
           CmpInst::Predicate AltPred = AltInst->getPredicate();
           Value *AltOp0 = AltInst->getOperand(0);
           Value *AltOp1 = AltInst->getOperand(1);
           // Check if operands are compatible with alternate operands.
           if (AltPred == CurrentPred &&
-              areCompatibleCmpOps(AltOp0, AltOp1, Op0, Op1))
+              areCompatibleCmpOps(AltOp0, AltOp1, Op0, Op1, TLI))
             continue;
           if (AltPred == SwappedCurrentPred &&
-              areCompatibleCmpOps(AltOp0, AltOp1, Op1, Op0))
+              areCompatibleCmpOps(AltOp0, AltOp1, Op1, Op0, TLI))
             continue;
         }
         if (BaseIndex == AltIndex && BasePred != CurrentPred) {
           assert(isValidForAlternation(Opcode) &&
                  isValidForAlternation(InstOpcode) &&
                  "Cast isn't safe for alternation, logic needs to be updated!");
           AltIndex = Cnt;
           continue;
         }
         auto *AltInst = cast<CmpInst>(VL[AltIndex]);
         CmpInst::Predicate AltPred = AltInst->getPredicate();
         if (BasePred == CurrentPred || BasePred == SwappedCurrentPred ||
             AltPred == CurrentPred || AltPred == SwappedCurrentPred)
           continue;
       }
-    } else if (InstOpcode == Opcode || InstOpcode == AltOpcode)
+    } else if (InstOpcode == Opcode || InstOpcode == AltOpcode) {
+      if (auto *Gep = dyn_cast<GetElementPtrInst>(I)) {
+        if (Gep->getNumOperands() != 2 ||
+            Gep->getOperand(0)->getType() != IBase->getOperand(0)->getType())
+          return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+      } else if (auto *EI = dyn_cast<ExtractElementInst>(I)) {
+        if (!isVectorLikeInstWithConstOps(EI))
+          return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+      } else if (auto *LI = dyn_cast<LoadInst>(I)) {
+        auto *BaseLI = cast<LoadInst>(IBase);
+        if (!LI->isSimple() || !BaseLI->isSimple())
+          return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+      } else if (auto *Call = dyn_cast<CallInst>(I)) {
+        auto *CallBase = cast<CallInst>(IBase);
+        if (Call->getCalledFunction() != CallBase->getCalledFunction())
+          return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+        if (Call->hasOperandBundles() &&
+            !std::equal(Call->op_begin() + Call->getBundleOperandsStartIndex(),
+                        Call->op_begin() + Call->getBundleOperandsEndIndex(),
+                        CallBase->op_begin() +
+                            CallBase->getBundleOperandsStartIndex()))
+          return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+        Intrinsic::ID ID = getVectorIntrinsicIDForCall(Call, &TLI);
+        if (ID != BaseID)
+          return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+        if (!ID) {
+          SmallVector<VFInfo> Mappings = VFDatabase(*Call).getMappings(*Call);
+          if (Mappings.size() != BaseMappings.size() ||
+              Mappings.front().ISA != BaseMappings.front().ISA ||
+              Mappings.front().ScalarName != BaseMappings.front().ScalarName ||
+              Mappings.front().VectorName != BaseMappings.front().VectorName ||
+              Mappings.front().Shape.VF != BaseMappings.front().Shape.VF ||
+              Mappings.front().Shape.Parameters !=
+                  BaseMappings.front().Shape.Parameters)
+            return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+        }
+      }
       continue;
+    }
     return InstructionsState(VL[BaseIndex], nullptr, nullptr);
   }
 
   return InstructionsState(VL[BaseIndex], cast<Instruction>(VL[BaseIndex]),
                            cast<Instruction>(VL[AltIndex]));
 }
 
 /// \returns true if all of the values in \p VL have the same type or false
void dump(raw_ostream &OS) const {
          << " EdgeIdx:" << EdgeIdx << "}";
     }
     LLVM_DUMP_METHOD void dump() const { dump(dbgs()); }
 #endif
   };
 
   /// A helper class used for scoring candidates for two consecutive lanes.
   class LookAheadHeuristics {
+    const TargetLibraryInfo &TLI;
     const DataLayout &DL;
     ScalarEvolution &SE;
     const BoUpSLP &R;
     int NumLanes; // Total number of lanes (aka vectorization factor).
     int MaxLevel; // The maximum recursion depth for accumulating score.
 
   public:
-    LookAheadHeuristics(const DataLayout &DL, ScalarEvolution &SE,
-                        const BoUpSLP &R, int NumLanes, int MaxLevel)
-        : DL(DL), SE(SE), R(R), NumLanes(NumLanes), MaxLevel(MaxLevel) {}
+    LookAheadHeuristics(const TargetLibraryInfo &TLI, const DataLayout &DL,
+                        ScalarEvolution &SE, const BoUpSLP &R, int NumLanes,
+                        int MaxLevel)
+        : TLI(TLI), DL(DL), SE(SE), R(R), NumLanes(NumLanes),
+          MaxLevel(MaxLevel) {}
 
     // The hard-coded scores listed here are not very important, though it shall
     // be higher for better matches to improve the resulting cost. When
     // computing the scores of matching one sub-tree with another, we are
     // basically counting the number of values that are matching. So even if all
     // scores are set to 1, we would still get a decent matching result.
     // However, sometimes we have to break ties. For example we may have to
     // choose between matching loads vs matching opcodes. This is what these
int getShallowScore(Value *V1, Value *V2, Instruction *U1, Instruction *U2,
             return LookAheadHeuristics::ScoreSplatLoads;
         }
         return LookAheadHeuristics::ScoreSplat;
       }
 
       auto *LI1 = dyn_cast<LoadInst>(V1);
       auto *LI2 = dyn_cast<LoadInst>(V2);
       if (LI1 && LI2) {
-        if (LI1->getParent() != LI2->getParent())
+        if (LI1->getParent() != LI2->getParent() || !LI1->isSimple() ||
+            !LI2->isSimple())
           return LookAheadHeuristics::ScoreFail;
 
         Optional<int> Dist = getPointersDiff(
             LI1->getType(), LI1->getPointerOperand(), LI2->getType(),
             LI2->getPointerOperand(), DL, SE, /*StrictCheck=*/true);
         if (!Dist || *Dist == 0)
           return LookAheadHeuristics::ScoreFail;
         // The distance is too large - still may be profitable to use masked
         // loads/gathers.
         if (std::abs(*Dist) > NumLanes / 2)
           return LookAheadHeuristics::ScoreAltOpcodes;
         // This still will detect consecutive loads, but we might have "holes"
         // in some cases. It is ok for non-power-2 vectorization and may produce
         // better results. It should not affect current vectorization.
         return (*Dist > 0) ? LookAheadHeuristics::ScoreConsecutiveLoads
                            : LookAheadHeuristics::ScoreReversedLoads;
       }
 
int getShallowScore(Value *V1, Value *V2, Instruction *U1, Instruction *U2,
       auto *I1 = dyn_cast<Instruction>(V1);
       auto *I2 = dyn_cast<Instruction>(V2);
       if (I1 && I2) {
         if (I1->getParent() != I2->getParent())
           return LookAheadHeuristics::ScoreFail;
         SmallVector<Value *, 4> Ops(MainAltOps.begin(), MainAltOps.end());
         Ops.push_back(I1);
         Ops.push_back(I2);
-        InstructionsState S = getSameOpcode(Ops);
+        InstructionsState S = getSameOpcode(Ops, TLI);
         // Note: Only consider instructions with <= 2 operands to avoid
         // complexity explosion.
         if (S.getOpcode() &&
             (S.MainOp->getNumOperands() <= 2 || !MainAltOps.empty() ||
              !S.isAltShuffle()) &&
             all_of(Ops, [&S](Value *V) {
               return cast<Instruction>(V)->getNumOperands() ==
                      S.MainOp->getNumOperands();
enum class ReorderingMode {
       Failed,   ///< We failed to create a vectorizable group
     };
 
     using OperandDataVec = SmallVector<OperandData, 2>;
 
     /// A vector of operand vectors.
     SmallVector<OperandDataVec, 4> OpsVec;
 
+    const TargetLibraryInfo &TLI;
     const DataLayout &DL;
     ScalarEvolution &SE;
     const BoUpSLP &R;
 
     /// \returns the operand data at \p OpIdx and \p Lane.
     OperandData &getData(unsigned OpIdx, unsigned Lane) {
       return OpsVec[OpIdx][Lane];
     }
class VLOperands {
     /// \Returns the look-ahead score, which tells us how much the sub-trees
     /// rooted at \p LHS and \p RHS match, the more they match the higher the
     /// score. This helps break ties in an informed way when we cannot decide on
     /// the order of the operands by just considering the immediate
     /// predecessors.
     int getLookAheadScore(Value *LHS, Value *RHS, ArrayRef<Value *> MainAltOps,
                           int Lane, unsigned OpIdx, unsigned Idx,
                           bool &IsUsed) {
-      LookAheadHeuristics LookAhead(DL, SE, R, getNumLanes(),
+      LookAheadHeuristics LookAhead(TLI, DL, SE, R, getNumLanes(),
                                     LookAheadMaxDepth);
       // Keep track of the instruction stack as we recurse into the operands
       // during the look-ahead score exploration.
       int Score =
           LookAhead.getScoreAtLevelRec(LHS, RHS, /*U1=*/nullptr, /*U2=*/nullptr,
                                        /*CurrLevel=*/1, MainAltOps);
       if (Score) {
         int SplatScore = getSplatScore(Lane, OpIdx, Idx);
OperandsOrderData getMaxNumOperandsThatCanBeReordered(unsigned Lane) const {
       unsigned Hash = 0;
       for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
         const OperandData &OpData = getData(OpIdx, Lane);
         if (OpData.APO)
           ++CntTrue;
         // Use Boyer-Moore majority voting for finding the majority opcode and
         // the number of times it occurs.
         if (auto *I = dyn_cast<Instruction>(OpData.V)) {
-          if (!OpcodeI || !getSameOpcode({OpcodeI, I}).getOpcode() ||
+          if (!OpcodeI || !getSameOpcode({OpcodeI, I}, TLI).getOpcode() ||
               I->getParent() != Parent) {
             if (NumOpsWithSameOpcodeParent == 0) {
               NumOpsWithSameOpcodeParent = 1;
               OpcodeI = I;
               Parent = I->getParent();
             } else {
               --NumOpsWithSameOpcodeParent;
             }
bool shouldBroadcast(Value *Op, unsigned OpIdx, unsigned Lane) {
         if (!FoundCandidate)
           return false;
       }
       return true;
     }
 
   public:
     /// Initialize with all the operands of the instruction vector \p RootVL.
-    VLOperands(ArrayRef<Value *> RootVL, const DataLayout &DL,
-               ScalarEvolution &SE, const BoUpSLP &R)
-        : DL(DL), SE(SE), R(R) {
+    VLOperands(ArrayRef<Value *> RootVL, const TargetLibraryInfo &TLI,
+               const DataLayout &DL, ScalarEvolution &SE, const BoUpSLP &R)
+        : TLI(TLI), DL(DL), SE(SE), R(R) {
       // Append all the operands of RootVL.
       appendOperandsOfVL(RootVL);
     }
 
     /// \Returns a value vector with the operands across all lanes for the
     /// opearnd at \p OpIdx.
     ValueList getVL(unsigned OpIdx) const {
       ValueList OpVL(OpsVec[OpIdx].size());
void reorder() {
                 ReorderingModes[OpIdx] = ReorderingMode::Failed;
                 // Enable the second pass.
                 StrategyFailed = true;
               }
               // Try to get the alternate opcode and follow it during analysis.
               if (MainAltOps[OpIdx].size() != 2) {
                 OperandData &AltOp = getData(OpIdx, Lane);
                 InstructionsState OpS =
-                    getSameOpcode({MainAltOps[OpIdx].front(), AltOp.V});
+                    getSameOpcode({MainAltOps[OpIdx].front(), AltOp.V}, TLI);
                 if (OpS.getOpcode() && OpS.isAltShuffle())
                   MainAltOps[OpIdx].push_back(AltOp.V);
               }
             }
           }
         }
         // Skip second pass if the strategy did not fail.
         if (!StrategyFailed)
#endif
   /// Evaluate each pair in \p Candidates and return index into \p Candidates
   /// for a pair which have highest score deemed to have best chance to form
   /// root of profitable tree to vectorize. Return None if no candidate scored
   /// above the LookAheadHeuristics::ScoreFail.
   /// \param Limit Lower limit of the cost, considered to be good enough score.
   Optional<int>
   findBestRootPair(ArrayRef<std::pair<Value *, Value *>> Candidates,
                    int Limit = LookAheadHeuristics::ScoreFail) {
-    LookAheadHeuristics LookAhead(*DL, *SE, *this, /*NumLanes=*/2,
+    LookAheadHeuristics LookAhead(*TLI, *DL, *SE, *this, /*NumLanes=*/2,
                                   RootLookAheadMaxDepth);
     int BestScore = Limit;
     Optional<int> Index = None;
     for (int I : seq<int>(0, Candidates.size())) {
       int Score = LookAhead.getScoreAtLevelRec(Candidates[I].first,
                                                Candidates[I].second,
                                                /*U1=*/nullptr, /*U2=*/nullptr,
                                                /*Level=*/1, None);
private:
   /// be beneficial even the tree height is tiny.
   bool isFullyVectorizableTinyTree(bool ForReduction) const;
 
   /// Reorder commutative or alt operands to get better probability of
   /// generating vectorized code.
   static void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
                                              SmallVectorImpl<Value *> &Left,
                                              SmallVectorImpl<Value *> &Right,
+                                             const TargetLibraryInfo &TLI,
+                                             const TargetTransformInfo &TTI,
                                              const DataLayout &DL,
                                              ScalarEvolution &SE,
                                              const BoUpSLP &R);
 
   /// Helper for `findExternalStoreUsersReorderIndices()`. It iterates over the
   /// users of \p TE and collects the stores. It returns the map from the store
   /// pointers to the collected stores.
   DenseMap<Value *, SmallVector<StoreInst *, 4>>
if (ReorderIndices.empty()) {
       // Reorder scalars and build final mask.
       Last->Scalars.assign(VL.size(), nullptr);
       transform(ReorderIndices, Last->Scalars.begin(),
                 [VL](unsigned Idx) -> Value * {
                   if (Idx >= VL.size())
                     return UndefValue::get(VL.front()->getType());
                   return VL[Idx];
                 });
-      InstructionsState S = getSameOpcode(Last->Scalars);
+      InstructionsState S = getSameOpcode(Last->Scalars, *TLI);
       Last->setOperations(S);
       Last->ReorderIndices.append(ReorderIndices.begin(), ReorderIndices.end());
     }
     if (Last->State != TreeEntry::NeedToGather) {
       for (Value *V : VL) {
         assert(!getTreeEntry(V) && "Scalar already in tree!");
         ScalarToTreeEntry[V] = Last;
       }
if (NumUniqueScalarValues == VL.size()) {
         newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
         return false;
       }
       VL = UniqueValues;
     }
     return true;
   };
 
-  InstructionsState S = getSameOpcode(VL);
+  InstructionsState S = getSameOpcode(VL, *TLI);
   if (Depth == RecursionMaxDepth) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
     if (TryToFindDuplicates(S))
       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                    ReuseShuffleIndicies);
     return;
   }
 
case Instruction::FCmp: {
                                    ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of compares.\n");
 
       ValueList Left, Right;
       if (cast<CmpInst>(VL0)->isCommutative()) {
         // Commutative predicate - collect + sort operands of the instructions
         // so that each side is more likely to have the same opcode.
         assert(P0 == SwapP0 && "Commutative Predicate mismatch");
-        reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
+        reorderInputsAccordingToOpcode(VL, Left, Right, *TLI, *TTI, *DL, *SE,
+                                       *this);
       } else {
         // Collect operands - commute if it uses the swapped predicate.
         for (Value *V : VL) {
           auto *Cmp = cast<CmpInst>(V);
           Value *LHS = Cmp->getOperand(0);
           Value *RHS = Cmp->getOperand(1);
           if (Cmp->getPredicate() != P0)
             std::swap(LHS, RHS);
case Instruction::Xor: {
       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
                                    ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of un/bin op.\n");
 
       // Sort operands of the instructions so that each side is more likely to
       // have the same opcode.
       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
         ValueList Left, Right;
-        reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
+        reorderInputsAccordingToOpcode(VL, Left, Right, *TLI, *TTI, *DL, *SE,
+                                       *this);
         TE->setOperand(0, Left);
         TE->setOperand(1, Right);
         buildTree_rec(Left, Depth + 1, {TE, 0});
         buildTree_rec(Right, Depth + 1, {TE, 1});
         return;
       }
 
       TE->setOperandsInOrder();
case Instruction::ShuffleVector: {
 
       // Reorder operands if reordering would enable vectorization.
       auto *CI = dyn_cast<CmpInst>(VL0);
       if (isa<BinaryOperator>(VL0) || CI) {
         ValueList Left, Right;
         if (!CI || all_of(VL, [](Value *V) {
               return cast<CmpInst>(V)->isCommutative();
             })) {
-          reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
+          reorderInputsAccordingToOpcode(VL, Left, Right, *TLI, *TTI, *DL, *SE,
+                                         *this);
         } else {
           CmpInst::Predicate P0 = CI->getPredicate();
           CmpInst::Predicate AltP0 = cast<CmpInst>(S.AltOp)->getPredicate();
           assert(P0 != AltP0 &&
                  "Expected different main/alternate predicates.");
           CmpInst::Predicate AltP0Swapped = CmpInst::getSwappedPredicate(AltP0);
           Value *BaseOp0 = VL0->getOperand(0);
           Value *BaseOp1 = VL0->getOperand(1);
           // Collect operands - commute if it uses the swapped predicate or
           // alternate operation.
           for (Value *V : VL) {
             auto *Cmp = cast<CmpInst>(V);
             Value *LHS = Cmp->getOperand(0);
             Value *RHS = Cmp->getOperand(1);
             CmpInst::Predicate CurrentPred = Cmp->getPredicate();
             if (P0 == AltP0Swapped) {
               if (CI != Cmp && S.AltOp != Cmp &&
                   ((P0 == CurrentPred &&
-                    !areCompatibleCmpOps(BaseOp0, BaseOp1, LHS, RHS)) ||
+                    !areCompatibleCmpOps(BaseOp0, BaseOp1, LHS, RHS, *TLI)) ||
                    (AltP0 == CurrentPred &&
-                    areCompatibleCmpOps(BaseOp0, BaseOp1, LHS, RHS))))
+                    areCompatibleCmpOps(BaseOp0, BaseOp1, LHS, RHS, *TLI))))
                 std::swap(LHS, RHS);
             } else if (P0 != CurrentPred && AltP0 != CurrentPred) {
               std::swap(LHS, RHS);
             }
             Left.push_back(LHS);
             Right.push_back(RHS);
           }
         }
if (!ReusesIndices.empty()) {
     Mask.swap(NewMask);
   }
 }
 
 /// Checks if the specified instruction \p I is an alternate operation for the
 /// given \p MainOp and \p AltOp instructions.
 static bool isAlternateInstruction(const Instruction *I,
                                    const Instruction *MainOp,
-                                   const Instruction *AltOp) {
+                                   const Instruction *AltOp,
+                                   const TargetLibraryInfo &TLI) {
   if (auto *CI0 = dyn_cast<CmpInst>(MainOp)) {
     auto *AltCI0 = cast<CmpInst>(AltOp);
     auto *CI = cast<CmpInst>(I);
     CmpInst::Predicate P0 = CI0->getPredicate();
     CmpInst::Predicate AltP0 = AltCI0->getPredicate();
     assert(P0 != AltP0 && "Expected different main/alternate predicates.");
     CmpInst::Predicate AltP0Swapped = CmpInst::getSwappedPredicate(AltP0);
     CmpInst::Predicate CurrentPred = CI->getPredicate();
     if (P0 == AltP0Swapped)
       return I == AltCI0 ||
              (I != MainOp &&
               !areCompatibleCmpOps(CI0->getOperand(0), CI0->getOperand(1),
-                                   CI->getOperand(0), CI->getOperand(1)));
+                                   CI->getOperand(0), CI->getOperand(1), TLI));
     return AltP0 == CurrentPred || AltP0Swapped == CurrentPred;
   }
   return I->getOpcode() == AltOp->getOpcode();
 }
 
 InstructionCost BoUpSLP::getEntryCost(const TreeEntry *E,
                                       ArrayRef<Value *> VectorizedVals) {
   ArrayRef<Value*> VL = E->Scalars;
if (!UniqueElements.insert(VL[Idx]).second) {
       ShuffledElements.setBit(Idx);
     }
   }
   return getGatherCost(VecTy, ShuffledElements, DuplicateNonConst);
 }
 
 // Perform operand reordering on the instructions in VL and return the reordered
 // operands in Left and Right.
-void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
-                                             SmallVectorImpl<Value *> &Left,
-                                             SmallVectorImpl<Value *> &Right,
-                                             const DataLayout &DL,
-                                             ScalarEvolution &SE,
-                                             const BoUpSLP &R) {
+void BoUpSLP::reorderInputsAccordingToOpcode(
+    ArrayRef<Value *> VL, SmallVectorImpl<Value *> &Left,
+    SmallVectorImpl<Value *> &Right, const TargetLibraryInfo &TLI,
+    const TargetTransformInfo &TTI, const DataLayout &DL, ScalarEvolution &SE,
   if (VL.empty())
     return;
-  VLOperands Ops(VL, DL, SE, R);
+  VLOperands Ops(VL, TLI, DL, SE, R);
   // Reorder the operands in place.
   Ops.reorder();
   Left = Ops.getVL(0);
   Right = Ops.getVL(1);
 }
 
 void BoUpSLP::setInsertPointAfterBundle(const TreeEntry *E) {
   // Get the basic block this bundle is in. All instructions in the bundle
~ShuffleInstructionBuilder() {
     assert((IsFinalized || Mask.empty()) &&
            "Shuffle construction must be finalized.");
   }
 };
 } // namespace
 
 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
   const unsigned VF = VL.size();
-  InstructionsState S = getSameOpcode(VL);
+  InstructionsState S = getSameOpcode(VL, *TLI);
   if (S.getOpcode()) {
     if (TreeEntry *E = getTreeEntry(S.OpValue))
       if (E->isSame(VL)) {
         Value *V = vectorizeTree(E);
         if (VF != cast<FixedVectorType>(V->getType())->getNumElements()) {
           if (!E->ReuseShuffleIndices.empty()) {
             // Reshuffle to get only unique values.
             // If some of the scalars are duplicated in the vectorization tree
Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
 
   if (E->VectorizedValue) {
     LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
     return E->VectorizedValue;
   }
 
   bool NeedToShuffleReuses = !E->ReuseShuffleIndices.empty();
   unsigned VF = E->getVectorFactor();
+  auto &&SetInsertPointAfterOps = [this](ArrayRef<Value *> VL) {
+    // The last instruction in the bundle in program order.
+    Instruction *LastInst = nullptr;
+
+    for (Value *V : VL) {
+      // If the value was vectorized, need to get the vector value for correct
+      // insert point.
+      if (const TreeEntry *TE = getTreeEntry(V))
+        if (TE->VectorizedValue)
+          V = TE->VectorizedValue;
+      auto *I = dyn_cast<Instruction>(V);
+      if (!I)
+        continue;
+      if (!DT->isReachableFromEntry(I->getParent()))
+        continue;
+      if (!LastInst) {
+        LastInst = I;
+        continue;
+      }
+      if ((LastInst->getParent() != I->getParent() &&
+           DT->dominates(LastInst->getParent(), I->getParent())) ||
+          (LastInst->getParent() == I->getParent() && LastInst->comesBefore(I)))
+        LastInst = I;
+    }
+    // Set the insertion point after the last instruction in the bundle. Set
+    // the debug location to Front.
+    if (!LastInst)
+      return;
+    if (isa<PHINode>(LastInst))
+      Builder.SetInsertPoint(LastInst->getParent(),
+                             LastInst->getParent()->getFirstInsertionPt());
+    else
+      Builder.SetInsertPoint(LastInst->getParent(),
+                             std::next(LastInst->getIterator()));
+    Builder.SetCurrentDebugLocation(LastInst->getDebugLoc());
+  };
+
   ShuffleInstructionBuilder ShuffleBuilder(Builder, VF, GatherShuffleSeq,
                                            CSEBlocks);
   if (E->State == TreeEntry::NeedToGather) {
-    if (E->getMainOp())
-      setInsertPointAfterBundle(E);
+    SetInsertPointAfterOps(E->Scalars);
     Value *Vec;
     SmallVector<int> Mask;
     SmallVector<const TreeEntry *> Entries;
     Optional<TargetTransformInfo::ShuffleKind> Shuffle =
         isGatherShuffledEntry(E, Mask, Entries);
     if (Shuffle.hasValue()) {
       assert((Entries.size() == 1 || Entries.size() == 2) &&
              "Expected shuffle of 1 or 2 entries.");
case Instruction::ShuffleVector: {
 
       // Create shuffle to take alternate operations from the vector.
       // Also, gather up main and alt scalar ops to propagate IR flags to
       // each vector operation.
       ValueList OpScalars, AltScalars;
       SmallVector<int> Mask;
       buildShuffleEntryMask(
           E->Scalars, E->ReorderIndices, E->ReuseShuffleIndices,
-          [E](Instruction *I) {
+          [E, this](Instruction *I) {
             assert(E->isOpcodeOrAlt(I) && "Unexpected main/alternate opcode");
-            return isAlternateInstruction(I, E->getMainOp(), E->getAltOp());
+            return isAlternateInstruction(I, E->getMainOp(), E->getAltOp(),
+                                          *TLI);
           },
           Mask, &OpScalars, &AltScalars);
 
       propagateIRFlags(V0, OpScalars);
       propagateIRFlags(V1, AltScalars);
 
       Value *V = Builder.CreateShuffleVector(V0, V1, Mask);
       if (auto *I = dyn_cast<Instruction>(V)) {
bool SLPVectorizerPass::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
   if (VL.size() < 2)
     return false;
 
   LLVM_DEBUG(dbgs() << "SLP: Trying to vectorize a list of length = "
                     << VL.size() << ".\n");
 
   // Check that all of the parts are instructions of the same type,
   // we permit an alternate opcode via InstructionsState.
-  InstructionsState S = getSameOpcode(VL);
+  InstructionsState S = getSameOpcode(VL, *TLI);
   if (!S.getOpcode())
     return false;
 
   Instruction *I0 = cast<Instruction>(S.OpValue);
   // Make sure invalid types (including vector type) are rejected before
   // determining vectorization factor for scalar instructions.
   for (Value *V : VL) {
     Type *Ty = V->getType();
bool matchAssociativeReduction(PHINode *Phi, Instruction *Inst,
     // operand.
     stable_sort(ReducedVals, [](ArrayRef<Value *> P1, ArrayRef<Value *> P2) {
       return P1.size() > P2.size();
     });
     return true;
   }
 
   /// Attempt to vectorize the tree found by matchAssociativeReduction.
-  Value *tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
+  Value *tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI,
+                     const TargetLibraryInfo &TLI) {
     constexpr int ReductionLimit = 4;
     constexpr unsigned RegMaxNumber = 4;
     constexpr unsigned RedValsMaxNumber = 128;
     // If there are a sufficient number of reduction values, reduce
     // to a nearby power-of-2. We can safely generate oversized
     // vectors and rely on the backend to split them to legal sizes.
     unsigned NumReducedVals = std::accumulate(
         ReducedVals.begin(), ReducedVals.end(), 0,
for (ArrayRef<Value *> Candidates : ReducedVals)
         TrackedVals.try_emplace(V, V);
 
     DenseMap<Value *, unsigned> VectorizedVals;
     Value *VectorizedTree = nullptr;
     bool CheckForReusedReductionOps = false;
     // Try to vectorize elements based on their type.
     for (unsigned I = 0, E = ReducedVals.size(); I < E; ++I) {
       ArrayRef<Value *> OrigReducedVals = ReducedVals[I];
-      InstructionsState S = getSameOpcode(OrigReducedVals);
+      InstructionsState S = getSameOpcode(OrigReducedVals, TLI);
       SmallVector<Value *> Candidates;
       DenseMap<Value *, Value *> TrackedToOrig;
       for (unsigned Cnt = 0, Sz = OrigReducedVals.size(); Cnt < Sz; ++Cnt) {
         Value *RdxVal = TrackedVals.find(OrigReducedVals[Cnt])->second;
         // Check if the reduction value was not overriden by the extractelement
         // instruction because of the vectorization and exclude it, if it is not
         // compatible with other values.
         if (auto *Inst = dyn_cast<Instruction>(RdxVal))
           if (isVectorLikeInstWithConstOps(Inst) &&
               (!S.getOpcode() || !S.isOpcodeOrAlt(Inst)))
             continue;
         Candidates.push_back(RdxVal);
         TrackedToOrig.try_emplace(RdxVal, OrigReducedVals[Cnt]);
       }
       bool ShuffledExtracts = false;
       // Try to handle shuffled extractelements.
       if (S.getOpcode() == Instruction::ExtractElement && !S.isAltShuffle() &&
           I + 1 < E) {
-        InstructionsState NextS = getSameOpcode(ReducedVals[I + 1]);
+        InstructionsState NextS = getSameOpcode(ReducedVals[I + 1], TLI);
         if (NextS.getOpcode() == Instruction::ExtractElement &&
             !NextS.isAltShuffle()) {
           SmallVector<Value *> CommonCandidates(Candidates);
           for (Value *RV : ReducedVals[I + 1]) {
             Value *RdxVal = TrackedVals.find(RV)->second;
             // Check if the reduction value was not overriden by the
             // extractelement instruction because of the vectorization and
             // exclude it, if it is not compatible with other values.
auto &&TryToReduce = [TTI, &SE, &DL, &P, &R, &TLI](Instruction *Inst,
                                                      Value *&B1) -> Value * {
     if (R.isAnalyzedReductionRoot(Inst))
       return nullptr;
     bool IsBinop = matchRdxBop(Inst, B0, B1);
     bool IsSelect = match(Inst, m_Select(m_Value(), m_Value(), m_Value()));
     if (IsBinop || IsSelect) {
       HorizontalReduction HorRdx;
       if (HorRdx.matchAssociativeReduction(P, Inst, SE, DL, TLI))
-        return HorRdx.tryToReduce(R, TTI);
+        return HorRdx.tryToReduce(R, TTI, TLI);
     }
     return nullptr;
   };
   while (!Stack.empty()) {
     Instruction *Inst;
     unsigned Level;
     std::tie(Inst, Level) = Stack.front();
     Stack.pop();

 /// Compare two cmp instructions. If IsCompatibility is true, function returns
 /// true if 2 cmps have same/swapped predicates and mos compatible corresponding
 /// operands. If IsCompatibility is false, function implements strict weak
 /// ordering relation between two cmp instructions, returning true if the first
 /// instruction is "less" than the second, i.e. its predicate is less than the
 /// predicate of the second or the operands IDs are less than the operands IDs
 /// of the second cmp instruction.
 template <bool IsCompatibility>
-static bool compareCmp(Value *V, Value *V2,
+static bool compareCmp(Value *V, Value *V2, TargetLibraryInfo &TLI,
+                       const TargetTransformInfo &TTI,
                        function_ref<bool(Instruction *)> IsDeleted) {
   auto *CI1 = cast<CmpInst>(V);
   auto *CI2 = cast<CmpInst>(V2);
   if (IsDeleted(CI2) || !isValidElementType(CI2->getType()))
     return false;
   if (CI1->getOperand(0)->getType()->getTypeID() <
       CI2->getOperand(0)->getType()->getTypeID())
     return !IsCompatibility;
for (int I = 0, E = CI1->getNumOperands(); I < E; ++I) {
     if (Op1->getValueID() < Op2->getValueID())
       return !IsCompatibility;
     if (Op1->getValueID() > Op2->getValueID())
       return false;
     if (auto *I1 = dyn_cast<Instruction>(Op1))
       if (auto *I2 = dyn_cast<Instruction>(Op2)) {
         if (I1->getParent() != I2->getParent())
           return false;
-        InstructionsState S = getSameOpcode({I1, I2});
+        InstructionsState S = getSameOpcode({I1, I2}, TLI);
         if (S.getOpcode())
           continue;
         return false;
       }
   }
   return IsCompatibility;
 }
 
if (AtTerminator) {
     // Try to vectorize operands as vector bundles.
     for (Instruction *I : PostponedCmps) {
       if (R.isDeleted(I))
         continue;
       OpsChanged |= tryToVectorize(I, R);
     }
     // Try to vectorize list of compares.
     // Sort by type, compare predicate, etc.
-    auto &&CompareSorter = [&R](Value *V, Value *V2) {
-      return compareCmp<false>(V, V2,
+    auto &&CompareSorter = [&R, TLI = TLI, TTI = TTI](Value *V, Value *V2) {
+      return compareCmp<false>(V, V2, *TLI, *TTI,
                                [&R](Instruction *I) { return R.isDeleted(I); });
     };
 
-    auto &&AreCompatibleCompares = [&R](Value *V1, Value *V2) {
+    auto &&AreCompatibleCompares = [&R, TLI = TLI, TTI = TTI](Value *V1,
+                                                              Value *V2) {
       if (V1 == V2)
         return true;
-      return compareCmp<true>(V1, V2,
+      return compareCmp<true>(V1, V2, *TLI, *TTI,
                               [&R](Instruction *I) { return R.isDeleted(I); });
     };
     auto Limit = [&R](Value *V) {
       unsigned EltSize = R.getVectorElementSize(V);
       return std::max(2U, R.getMaxVecRegSize() / EltSize);
     };
 
     SmallVector<Value *> Vals(PostponedCmps.begin(), PostponedCmps.end());
for (int I = 0, E = Opcodes1.size(); I < E; ++I) {
             return NodeI2 != nullptr;
           if (!NodeI2)
             return false;
           assert((NodeI1 == NodeI2) ==
                      (NodeI1->getDFSNumIn() == NodeI2->getDFSNumIn()) &&
                  "Different nodes should have different DFS numbers");
           if (NodeI1 != NodeI2)
             return NodeI1->getDFSNumIn() < NodeI2->getDFSNumIn();
-          InstructionsState S = getSameOpcode({I1, I2});
+          InstructionsState S = getSameOpcode({I1, I2}, *TLI);
           if (S.getOpcode())
             continue;
           return I1->getOpcode() < I2->getOpcode();
         }
       if (isa<Constant>(Opcodes1[I]) && isa<Constant>(Opcodes2[I])) {
         if (!ConstOrder)
           ConstOrder = Opcodes1[I]->getValueID() < Opcodes2[I]->getValueID();
         continue;
       }
       if (Opcodes1[I]->getValueID() < Opcodes2[I]->getValueID())
         return true;
       if (Opcodes1[I]->getValueID() > Opcodes2[I]->getValueID())
         return false;
     }
     return ConstOrder && *ConstOrder;
   };
-  auto AreCompatiblePHIs = [&PHIToOpcodes](Value *V1, Value *V2) {
+  auto AreCompatiblePHIs = [&PHIToOpcodes, this](Value *V1, Value *V2) {
     if (V1 == V2)
       return true;
     if (V1->getType() != V2->getType())
       return false;
     ArrayRef<Value *> Opcodes1 = PHIToOpcodes[V1];
     ArrayRef<Value *> Opcodes2 = PHIToOpcodes[V2];
     if (Opcodes1.size() != Opcodes2.size())
       return false;
     for (int I = 0, E = Opcodes1.size(); I < E; ++I) {
       // Undefs are compatible with any other value.
       if (isa<UndefValue>(Opcodes1[I]) || isa<UndefValue>(Opcodes2[I]))
         continue;
       if (auto *I1 = dyn_cast<Instruction>(Opcodes1[I]))
         if (auto *I2 = dyn_cast<Instruction>(Opcodes2[I])) {
           if (I1->getParent() != I2->getParent())
             return false;
-          InstructionsState S = getSameOpcode({I1, I2});
+          InstructionsState S = getSameOpcode({I1, I2}, *TLI);
           if (S.getOpcode())
             continue;
           return false;
         }
       if (isa<Constant>(Opcodes1[I]) && isa<Constant>(Opcodes2[I]))
         continue;
       if (Opcodes1[I]->getValueID() != Opcodes2[I]->getValueID())
         return false;
if (auto *I1 = dyn_cast<Instruction>(V->getValueOperand()))
             DT->getNode(I2->getParent());
         assert(NodeI1 && "Should only process reachable instructions");
         assert(NodeI2 && "Should only process reachable instructions");
         assert((NodeI1 == NodeI2) ==
                    (NodeI1->getDFSNumIn() == NodeI2->getDFSNumIn()) &&
                "Different nodes should have different DFS numbers");
         if (NodeI1 != NodeI2)
           return NodeI1->getDFSNumIn() < NodeI2->getDFSNumIn();
-        InstructionsState S = getSameOpcode({I1, I2});
+        InstructionsState S = getSameOpcode({I1, I2}, *TLI);
         if (S.getOpcode())
           return false;
         return I1->getOpcode() < I2->getOpcode();
       }
     if (isa<Constant>(V->getValueOperand()) &&
         isa<Constant>(V2->getValueOperand()))
       return false;
     return V->getValueOperand()->getValueID() <
            V2->getValueOperand()->getValueID();
   };
 
-  auto &&AreCompatibleStores = [](StoreInst *V1, StoreInst *V2) {
+  auto &&AreCompatibleStores = [this](StoreInst *V1, StoreInst *V2) {
     if (V1 == V2)
       return true;
     if (V1->getPointerOperandType() != V2->getPointerOperandType())
       return false;
     // Undefs are compatible with any other value.
     if (isa<UndefValue>(V1->getValueOperand()) ||
         isa<UndefValue>(V2->getValueOperand()))
       return true;
     if (auto *I1 = dyn_cast<Instruction>(V1->getValueOperand()))
       if (auto *I2 = dyn_cast<Instruction>(V2->getValueOperand())) {
         if (I1->getParent() != I2->getParent())
           return false;
-        InstructionsState S = getSameOpcode({I1, I2});
+        InstructionsState S = getSameOpcode({I1, I2}, *TLI);
         return S.getOpcode() > 0;
       }
     if (isa<Constant>(V1->getValueOperand()) &&
         isa<Constant>(V2->getValueOperand()))
       return true;
     return V1->getValueOperand()->getValueID() ==
            V2->getValueOperand()->getValueID();
   };

llvm/test/Transforms/SLPVectorizer/X86/simplebb.ll

;
   %arrayidx5 = bitcast i8* %carrayidx5 to double*
   store double %mul5, double* %arrayidx5, align 8
   ret void
 }
 
 ; Don't vectorize volatile loads.
 define void @test_volatile_load(double* %a, double* %b, double* %c) {
 ; CHECK-LABEL: @test_volatile_load(
-; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds double, double* [[A:%.*]], i64 1
-; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds double, double* [[B:%.*]], i64 1
-; CHECK-NEXT:    [[I0:%.*]] = load volatile double, double* [[A]], align 8
-; CHECK-NEXT:    [[I1:%.*]] = load volatile double, double* [[B]], align 8
+; CHECK-NEXT:    [[I0:%.*]] = load volatile double, double* [[A:%.*]], align 8
+; CHECK-NEXT:    [[I1:%.*]] = load volatile double, double* [[B:%.*]], align 8
+; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds double, double* [[A]], i64 1
 ; CHECK-NEXT:    [[I3:%.*]] = load double, double* [[ARRAYIDX3]], align 8
+; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds double, double* [[B]], i64 1
 ; CHECK-NEXT:    [[I4:%.*]] = load double, double* [[ARRAYIDX4]], align 8
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> poison, double [[I0]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> [[TMP1]], double [[I3]], i32 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> poison, double [[I1]], i32 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <2 x double> [[TMP3]], double [[I4]], i32 1
 ; CHECK-NEXT:    [[TMP5:%.*]] = fmul <2 x double> [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = bitcast double* [[C:%.*]] to <2 x double>*
 ; CHECK-NEXT:    store <2 x double> [[TMP5]], <2 x double>* [[TMP6]], align 8