[SLP]Add final resize to ShuffleCostEstimator::finalize member function and basic add member functions.

[ABataev]

Summary

Implemented the reshuffling in finalize member function + add basic
support for add member functions, used during vector build.

Part of D110978

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7058

This looks very similar to the addMask helper - can we use that (possibly with a modification to skip the TermValue logic)?

[ABataev]

Address comments

[RKSimon]

LGTM

[jonpa]

Seems this gave me a segfault on SPEC.

opt -mtriple=s390x-unknown-linux -mcpu=z15 -o - -S -O3 ./bugpoint-reduced-simplified.bc

bugpoint-reduced-simplified.bc13 KBDownload

[jonpa]

In D148279#4278262, @jonpa wrote:

Seems this gave me a segfault on SPEC.

opt -mtriple=s390x-unknown-linux -mcpu=z15 -o - -S -O3 ./bugpoint-reduced-simplified.bc

bugpoint-reduced-simplified.bc13 KBDownload

sorry - see now you already reverted it...

[eaeltsin]

Hi,

This was relanded and caused crashes when compiling numpy for aarch64.

Reproducer:

typedef long double npy_longdouble;
typedef struct {
  npy_longdouble real, imag;
} npy_clongdouble;
enum { NPY_CDOUBLE } min_scalar_type_num_valueptr;
int min_scalar_type_num_type_num;
int min_scalar_type_num() {
  npy_clongdouble value = *(npy_clongdouble *)min_scalar_type_num_valueptr;
  if (value.real > -3.4e38 && value.real < 3.4e38 && value.imag > 3.4e38 &&
      value.imag < 3.4e38)
    if (value.real > -1.7e308 && value.real < 1.7e308 && value.imag > 1.7e308 &&
        value.imag < 1.7e308)
      return min_scalar_type_num_type_num;
  return 0;
}

Command:

clang -cc1 -triple aarch64-unknown-linux-gnu -emit-obj -O3 -vectorize-slp t4.c

Output:

Stack dump:
0.	Program arguments: clang -cc1 -triple aarch64-unknown-linux-gnu -emit-obj -O3 -vectorize-slp t4.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x000055c62dade00e llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (clang+0x82de00e)
 #1 0x000055c62dadc149 llvm::sys::RunSignalHandlers() (clang+0x82dc149)
 #2 0x000055c62dade6ad SignalHandler(int) (clang+0x82de6ad)
 #3 0x00007f5ba4b791c0 __restore_rt (/usr/grte/v5/lib64/libpthread.so.0+0x151c0)
 #4 0x000055c62d203d3d llvm::slpvectorizer::BoUpSLP::ShuffleCostEstimator::finalize(llvm::ArrayRef<int>) (clang+0x7a03d3d)
 #5 0x000055c62d1ffd0a llvm::slpvectorizer::BoUpSLP::getEntryCost(llvm::slpvectorizer::BoUpSLP::TreeEntry const*, llvm::ArrayRef<llvm::Value*>) (clang+0x79ffd0a)
 #6 0x000055c62d206064 llvm::slpvectorizer::BoUpSLP::getTreeCost(llvm::ArrayRef<llvm::Value*>) (clang+0x7a06064)
 #7 0x000055c62d237be1 (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) (clang+0x7a37be1)
 #8 0x000055c62d223fb2 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (clang+0x7a23fb2)
 #9 0x000055c62d22417a llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (clang+0x7a2417a)
#10 0x000055c62d21ce5a llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (clang+0x7a1ce5a)
#11 0x000055c62d21ae15 llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (clang+0x7a1ae15)
#12 0x000055c62d21a746 llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (clang+0x7a1a746)
#13 0x000055c62c353a72 llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (clang+0x6b53a72)
#14 0x000055c62d9478b5 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (clang+0x81478b5)
#15 0x000055c6295354b2 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>&) (clang+0x3d354b2)
#16 0x000055c62d949c09 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (clang+0x8149c09)
#17 0x000055c629537552 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (clang+0x3d37552)
#18 0x000055c62d946d95 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (clang+0x8146d95)
#19 0x000055c62952cfad (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::__u::unique_ptr<llvm::raw_pwrite_stream, std::__u::default_delete<llvm::raw_pwrite_stream>>&, std::__u::unique_ptr<llvm::ToolOutputFile, std::__u::default_delete<llvm::ToolOutputFile>>&) (clang+0x3d2cfad)
#20 0x000055c629525ca7 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::__u::unique_ptr<llvm::raw_pwrite_stream, std::__u::default_delete<llvm::raw_pwrite_stream>>) (clang+0x3d25ca7)
#21 0x000055c629523816 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (clang+0x3d23816)
#22 0x000055c62a2742c6 clang::ParseAST(clang::Sema&, bool, bool) (clang+0x4a742c6)
#23 0x000055c629fe159a clang::FrontendAction::Execute() (clang+0x47e159a)
#24 0x000055c629f50f64 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (clang+0x4750f64)
#25 0x000055c6291c85ce clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (clang+0x39c85ce)
#26 0x000055c6291bd16f cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (clang+0x39bd16f)
#27 0x000055c6291b9ea4 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) (clang+0x39b9ea4)
#28 0x000055c6291b8a9f clang_main(int, char**, llvm::ToolContext const&) (clang+0x39b8a9f)
#29 0x000055c6291b5d84 main (clang+0x39b5d84)
#30 0x00007f5ba4a0c633 __libc_start_main (libc.so.6+0x61633)
#31 0x000055c6291b5cea _start (clang+0x39b5cea)

[ABataev]

In D148279#4286548, @eaeltsin wrote:

Hi,

This was relanded and caused crashes when compiling numpy for aarch64.

Reproducer:

typedef long double npy_longdouble;
typedef struct {
  npy_longdouble real, imag;
} npy_clongdouble;
enum { NPY_CDOUBLE } min_scalar_type_num_valueptr;
int min_scalar_type_num_type_num;
int min_scalar_type_num() {
  npy_clongdouble value = *(npy_clongdouble *)min_scalar_type_num_valueptr;
  if (value.real > -3.4e38 && value.real < 3.4e38 && value.imag > 3.4e38 &&
      value.imag < 3.4e38)
    if (value.real > -1.7e308 && value.real < 1.7e308 && value.imag > 1.7e308 &&
        value.imag < 1.7e308)
      return min_scalar_type_num_type_num;
  return 0;
}

Command:

clang -cc1 -triple aarch64-unknown-linux-gnu -emit-obj -O3 -vectorize-slp t4.c

Output:

Stack dump:
0.	Program arguments: clang -cc1 -triple aarch64-unknown-linux-gnu -emit-obj -O3 -vectorize-slp t4.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x000055c62dade00e llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (clang+0x82de00e)
 #1 0x000055c62dadc149 llvm::sys::RunSignalHandlers() (clang+0x82dc149)
 #2 0x000055c62dade6ad SignalHandler(int) (clang+0x82de6ad)
 #3 0x00007f5ba4b791c0 __restore_rt (/usr/grte/v5/lib64/libpthread.so.0+0x151c0)
 #4 0x000055c62d203d3d llvm::slpvectorizer::BoUpSLP::ShuffleCostEstimator::finalize(llvm::ArrayRef<int>) (clang+0x7a03d3d)
 #5 0x000055c62d1ffd0a llvm::slpvectorizer::BoUpSLP::getEntryCost(llvm::slpvectorizer::BoUpSLP::TreeEntry const*, llvm::ArrayRef<llvm::Value*>) (clang+0x79ffd0a)
 #6 0x000055c62d206064 llvm::slpvectorizer::BoUpSLP::getTreeCost(llvm::ArrayRef<llvm::Value*>) (clang+0x7a06064)
 #7 0x000055c62d237be1 (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) (clang+0x7a37be1)
 #8 0x000055c62d223fb2 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (clang+0x7a23fb2)
 #9 0x000055c62d22417a llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Value*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (clang+0x7a2417a)
#10 0x000055c62d21ce5a llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (clang+0x7a1ce5a)
#11 0x000055c62d21ae15 llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (clang+0x7a1ae15)
#12 0x000055c62d21a746 llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (clang+0x7a1a746)
#13 0x000055c62c353a72 llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (clang+0x6b53a72)
#14 0x000055c62d9478b5 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (clang+0x81478b5)
#15 0x000055c6295354b2 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>&) (clang+0x3d354b2)
#16 0x000055c62d949c09 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (clang+0x8149c09)
#17 0x000055c629537552 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (clang+0x3d37552)
#18 0x000055c62d946d95 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (clang+0x8146d95)
#19 0x000055c62952cfad (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::__u::unique_ptr<llvm::raw_pwrite_stream, std::__u::default_delete<llvm::raw_pwrite_stream>>&, std::__u::unique_ptr<llvm::ToolOutputFile, std::__u::default_delete<llvm::ToolOutputFile>>&) (clang+0x3d2cfad)
#20 0x000055c629525ca7 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::__u::unique_ptr<llvm::raw_pwrite_stream, std::__u::default_delete<llvm::raw_pwrite_stream>>) (clang+0x3d25ca7)
#21 0x000055c629523816 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (clang+0x3d23816)
#22 0x000055c62a2742c6 clang::ParseAST(clang::Sema&, bool, bool) (clang+0x4a742c6)
#23 0x000055c629fe159a clang::FrontendAction::Execute() (clang+0x47e159a)
#24 0x000055c629f50f64 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (clang+0x4750f64)
#25 0x000055c6291c85ce clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (clang+0x39c85ce)
#26 0x000055c6291bd16f cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (clang+0x39bd16f)
#27 0x000055c6291b9ea4 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) (clang+0x39b9ea4)
#28 0x000055c6291b8a9f clang_main(int, char**, llvm::ToolContext const&) (clang+0x39b8a9f)
#29 0x000055c6291b5d84 main (clang+0x39b5d84)
#30 0x00007f5ba4a0c633 __libc_start_main (libc.so.6+0x61633)
#31 0x000055c6291b5cea _start (clang+0x39b5cea)

Hi, must be fixed in 403bd583a8cc1f041430ff1b236ab296a2acdc85

[fhahn]

Looks like this is causing a crash reported in https://github.com/llvm/llvm-project/issues/62665

[ABataev]

In D148279#4360967, @fhahn wrote:

Looks like this is causing a crash reported in https://github.com/llvm/llvm-project/issues/62665

Fixed in ae5ff3ca0cd923a9fb2b46701641acab3dd15e4b

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

static bool isSimple(Instruction *I) {
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return SI->isSimple();
   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
     return !MI->isVolatile();
   return true;
 }
 
 /// Shuffles \p Mask in accordance with the given \p SubMask.
-static void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask) {
+/// \param ExtendingManyInputs Supports reshuffling of the mask with not only
+/// one but two input vectors.
+static void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
+                    bool ExtendingManyInputs = false) {
   if (SubMask.empty())
     return;
+  assert((!ExtendingManyInputs || SubMask.size() > Mask.size()) &&
+         "SubMask with many inputs support must be larger than the mask.");
   if (Mask.empty()) {
     Mask.append(SubMask.begin(), SubMask.end());
     return;
   }
   SmallVector<int> NewMask(SubMask.size(), UndefMaskElem);
   int TermValue = std::min(Mask.size(), SubMask.size());
   for (int I = 0, E = SubMask.size(); I < E; ++I) {
-    if (SubMask[I] >= TermValue || SubMask[I] == UndefMaskElem ||
-        Mask[SubMask[I]] >= TermValue)
+    if ((!ExtendingManyInputs &&
+         (SubMask[I] >= TermValue || Mask[SubMask[I]] >= TermValue)) ||
+        SubMask[I] == UndefMaskElem)
       continue;
     NewMask[I] = Mask[SubMask[I]];
   }
   Mask.swap(NewMask);
 }
 
 /// Order may have elements assigned special value (size) which is out of
 /// bounds. Such indices only appear on places which correspond to undef values

 /// Merges shuffle masks and emits final shuffle instruction, if required. It
 /// supports shuffling of 2 input vectors. It implements lazy shuffles emission,
 /// when the actual shuffle instruction is generated only if this is actually
 /// required. Otherwise, the shuffle instruction emission is delayed till the
 /// end of the process, to reduce the number of emitted instructions and further
 /// analysis/transformations.
 class BoUpSLP::ShuffleCostEstimator : public BaseShuffleAnalysis {
   bool IsFinalized = false;
+  SmallVector<int> CommonMask;
+  SmallVector<Value *, 2> InVectors;
   const TargetTransformInfo &TTI;
   InstructionCost Cost = 0;
   ArrayRef<Value *> VectorizedVals;
   BoUpSLP &R;
   constexpr static TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
 
   InstructionCost getBuildVectorCost(ArrayRef<Value *> VL, Value *Root) {
     if ((!Root && allConstant(VL)) || all_of(VL, UndefValue::classof))
for (const auto &Data : ExtractVectorsTys) {
           Cost += TTI.getShuffleCost(TargetTransformInfo::SK_ExtractSubvector,
                                      EEVTy, std::nullopt, CostKind, Idx, SubVT);
         }
       } else {
         Cost += TTI.getShuffleCost(TargetTransformInfo::SK_InsertSubvector,
                                    VecTy, std::nullopt, CostKind, 0, EEVTy);
       }
     }
+    InVectors.assign(1, VecBase);
     return VecBase;
   }
+  void add(const TreeEntry *E1, const TreeEntry *E2, ArrayRef<int> Mask) {
+    CommonMask.assign(Mask.begin(), Mask.end());
+    InVectors.assign(
+        2, Constant::getNullValue(FixedVectorType::get(
+               E1->Scalars.front()->getType(),
+               std::max(E1->getVectorFactor(), E2->getVectorFactor()))));
+  }
+  void add(const TreeEntry *E1, ArrayRef<int> Mask) {
+    CommonMask.assign(Mask.begin(), Mask.end());
+    InVectors.assign(
+        1, Constant::getNullValue(FixedVectorType::get(
+               E1->Scalars.front()->getType(), E1->getVectorFactor())));
+  }
   void gather(ArrayRef<Value *> VL, Value *Root = nullptr) {
     Cost += getBuildVectorCost(VL, Root);
+    if (!Root) {
+      assert(InVectors.empty() && "Unexpected input vectors for buildvector.");
+      InVectors.assign(1, Constant::getNullValue(FixedVectorType::get(
+                              VL.front()->getType(), VL.size())));
+    }
   }
   /// Finalize emission of the shuffles.
-  InstructionCost finalize() {
+  InstructionCost finalize(ArrayRef<int> ExtMask) {
     IsFinalized = true;
+    ::addMask(CommonMask, ExtMask, /*ExtendingManyInputs=*/true);
+    if (CommonMask.empty())
+      return Cost;
+    int Limit = CommonMask.size() * 2;
+    if (all_of(CommonMask, [=](int Idx) { return Idx < Limit; }) &&
+        ShuffleVectorInst::isIdentityMask(CommonMask))
       return Cost;
+    return Cost +
+           TTI.getShuffleCost(InVectors.size() == 2 ? TTI::SK_PermuteTwoSrc
+                                                    : TTI::SK_PermuteSingleSrc,
+                              FixedVectorType::get(
+                                  cast<VectorType>(InVectors.front()->getType())
+                                      ->getElementType(),
+                                  CommonMask.size()),
+                              CommonMask);
   }
 
   ~ShuffleCostEstimator() {
-      assert(IsFinalized && "Shuffle construction must be finalized.");
+    assert((IsFinalized || CommonMask.empty()) &&
+           "Shuffle construction must be finalized.");
   }
 };
 
 InstructionCost BoUpSLP::getEntryCost(const TreeEntry *E,
                                       ArrayRef<Value *> VectorizedVals) {
   ArrayRef<Value *> VL = E->Scalars;
 
   Type *ScalarTy = VL[0]->getType();
if (GatherShuffle) {
           GatheredScalars.append(VF - GatheredScalars.size(),
                                  PoisonValue::get(ScalarTy));
       }
       // Remove shuffled elements from list of gathers.
       for (int I = 0, Sz = Mask.size(); I < Sz; ++I) {
         if (Mask[I] != UndefMaskElem)
           GatheredScalars[I] = PoisonValue::get(ScalarTy);
       }
-      InstructionCost GatherCost = 0;
+      LLVM_DEBUG(
           int Limit = Mask.size() * 2;
-      if (all_of(Mask, [=](int Idx) { return Idx < Limit; }) &&
+          if (*GatherShuffle == TTI::SK_PermuteSingleSrc &&
+              all_of(Mask, [=](int Idx) { return Idx < Limit; }) &&
               ShuffleVectorInst::isIdentityMask(Mask)) {
-        // Perfect match in the graph, will reuse the previously vectorized
-        // node. Cost is 0.
-        LLVM_DEBUG(
-            dbgs()
-            << "SLP: perfect diamond match for gather bundle that starts with "
-            << *VL.front() << ".\n");
-        if (NeedToShuffleReuses)
-          GatherCost =
-              TTI->getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc,
-                                  FinalVecTy, E->ReuseShuffleIndices);
-      } else {
-        LLVM_DEBUG(dbgs() << "SLP: shuffled " << Entries.size()
-                          << " entries for bundle that starts with "
-                          << *VL.front() << ".\n");
-        // Detected that instead of gather we can emit a shuffle of single/two
-        // previously vectorized nodes. Add the cost of the permutation rather
-        // than gather.
-        ::addMask(Mask, E->ReuseShuffleIndices);
-        GatherCost = TTI->getShuffleCost(*GatherShuffle, FinalVecTy, Mask);
-      }
+            // Perfect match in the graph, will reuse the previously
+            // vectorized node. Cost is 0.
+            dbgs() << "SLP: perfect diamond match for gather bundle "
+                      "that starts with "
+                   << *VL.front() << ".\n";
+          } else {
+            dbgs() << "SLP: shuffled " << Entries.size()
+                   << " entries for bundle that starts with " << *VL.front()
+                   << ".\n";
+          });
+      if (Entries.size() == 1)
+        Estimator.add(Entries.front(), Mask);
+      else
+        Estimator.add(Entries.front(), Entries.back(), Mask);
       Estimator.gather(
           GatheredScalars,
           Constant::getNullValue(FixedVectorType::get(
               GatheredScalars.front()->getType(), GatheredScalars.size())));
-      return GatherCost + Estimator.finalize();
+      return Estimator.finalize(E->ReuseShuffleIndices);
     }
     if (ExtractShuffle && all_of(GatheredScalars, PoisonValue::classof)) {
       // Check that gather of extractelements can be represented as just a
       // shuffle of a single/two vectors the scalars are extracted from.
       // Found the bunch of extractelement instructions that must be gathered
       // into a vector and can be represented as a permutation elements in a
       // single input vector or of 2 input vectors.
       InstructionCost Cost =
           computeExtractCost(VL, VecTy, *ExtractShuffle, ExtractMask, *TTI);
-      if (NeedToShuffleReuses)
-        Cost += TTI->getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc,
-                                    FinalVecTy, E->ReuseShuffleIndices);
-      return Cost + Estimator.finalize();
+      return Cost + Estimator.finalize(E->ReuseShuffleIndices);
     }
-    InstructionCost ReuseShuffleCost = 0;
-    if (NeedToShuffleReuses)
-      ReuseShuffleCost = TTI->getShuffleCost(
-          TTI::SK_PermuteSingleSrc, FinalVecTy, E->ReuseShuffleIndices);
-    Estimator.gather(GatheredScalars);
-    return ReuseShuffleCost + Estimator.finalize();
+    Estimator.gather(
+        GatheredScalars,
+        (ExtractShuffle || GatherShuffle)
+            ? Constant::getNullValue(FixedVectorType::get(
+                  GatheredScalars.front()->getType(), GatheredScalars.size()))
+            : nullptr);
+    return Estimator.finalize(E->ReuseShuffleIndices);
   }
   InstructionCost CommonCost = 0;
   SmallVector<int> Mask;
   if (!E->ReorderIndices.empty()) {
     SmallVector<int> NewMask;
     if (E->getOpcode() == Instruction::Store) {
       // For stores the order is actually a mask.
       NewMask.resize(E->ReorderIndices.size());

llvm/test/Transforms/SLPVectorizer/X86/reduction-logical.ll

;
   %c3 = fcmp olt float %x3, 0.0
   %s1 = select i1 %c0, i1 true, i1 %c1
   %s2 = select i1 %s1, i1 true, i1 %c2
   %s3 = select i1 %s2, i1 true, i1 %c3
   ret i1 %s3
 }
 
 define i1 @logical_and_icmp_diff_preds(<4 x i32> %x) {
-; CHECK-LABEL: @logical_and_icmp_diff_preds(
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i32> [[X:%.*]], <4 x i32> <i32 poison, i32 poison, i32 poison, i32 0>, <4 x i32> <i32 0, i32 3, i32 1, i32 7>
-; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32> [[X]], <4 x i32> <i32 0, i32 0, i32 0, i32 poison>, <4 x i32> <i32 4, i32 5, i32 6, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult <4 x i32> [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt <4 x i32> [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <4 x i1> [[TMP3]], <4 x i1> [[TMP4]], <4 x i32> <i32 0, i32 5, i32 6, i32 7>
-; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x i1> [[TMP5]], i32 0
-; CHECK-NEXT:    [[TMP7:%.*]] = extractelement <4 x i1> [[TMP5]], i32 2
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[TMP6]], i1 [[TMP7]], i1 false
-; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <4 x i1> [[TMP5]], i32 3
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[S1]], i1 [[TMP8]], i1 false
-; CHECK-NEXT:    [[TMP9:%.*]] = extractelement <4 x i1> [[TMP5]], i32 1
-; CHECK-NEXT:    [[S3:%.*]] = select i1 [[S2]], i1 [[TMP9]], i1 false
-; CHECK-NEXT:    ret i1 [[S3]]
+; SSE-LABEL: @logical_and_icmp_diff_preds(
+; SSE-NEXT:    [[X0:%.*]] = extractelement <4 x i32> [[X:%.*]], i32 0
+; SSE-NEXT:    [[X3:%.*]] = extractelement <4 x i32> [[X]], i32 3
+; SSE-NEXT:    [[C0:%.*]] = icmp ult i32 [[X0]], 0
+; SSE-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i32> [[X]], <4 x i32> poison, <2 x i32> <i32 1, i32 2>
+; SSE-NEXT:    [[TMP2:%.*]] = shufflevector <2 x i32> [[TMP1]], <2 x i32> <i32 poison, i32 0>, <2 x i32> <i32 0, i32 3>
+; SSE-NEXT:    [[TMP3:%.*]] = shufflevector <2 x i32> [[TMP1]], <2 x i32> <i32 0, i32 poison>, <2 x i32> <i32 2, i32 1>
+; SSE-NEXT:    [[TMP4:%.*]] = icmp slt <2 x i32> [[TMP2]], [[TMP3]]
+; SSE-NEXT:    [[C3:%.*]] = icmp slt i32 [[X3]], 0
+; SSE-NEXT:    [[TMP5:%.*]] = extractelement <2 x i1> [[TMP4]], i32 0
+; SSE-NEXT:    [[S1:%.*]] = select i1 [[C0]], i1 [[TMP5]], i1 false
+; SSE-NEXT:    [[TMP6:%.*]] = extractelement <2 x i1> [[TMP4]], i32 1
+; SSE-NEXT:    [[S2:%.*]] = select i1 [[S1]], i1 [[TMP6]], i1 false
+; SSE-NEXT:    [[S3:%.*]] = select i1 [[S2]], i1 [[C3]], i1 false
+; SSE-NEXT:    ret i1 [[S3]]
+;
+; AVX-LABEL: @logical_and_icmp_diff_preds(
+; AVX-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i32> [[X:%.*]], <4 x i32> <i32 poison, i32 poison, i32 poison, i32 0>, <4 x i32> <i32 0, i32 3, i32 1, i32 7>
+; AVX-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32> [[X]], <4 x i32> <i32 0, i32 0, i32 0, i32 poison>, <4 x i32> <i32 4, i32 5, i32 6, i32 2>
+; AVX-NEXT:    [[TMP3:%.*]] = icmp ult <4 x i32> [[TMP1]], [[TMP2]]
+; AVX-NEXT:    [[TMP4:%.*]] = icmp slt <4 x i32> [[TMP1]], [[TMP2]]
+; AVX-NEXT:    [[TMP5:%.*]] = shufflevector <4 x i1> [[TMP3]], <4 x i1> [[TMP4]], <4 x i32> <i32 0, i32 5, i32 6, i32 7>
+; AVX-NEXT:    [[TMP6:%.*]] = extractelement <4 x i1> [[TMP5]], i32 0
+; AVX-NEXT:    [[TMP7:%.*]] = extractelement <4 x i1> [[TMP5]], i32 2
+; AVX-NEXT:    [[S1:%.*]] = select i1 [[TMP6]], i1 [[TMP7]], i1 false
+; AVX-NEXT:    [[TMP8:%.*]] = extractelement <4 x i1> [[TMP5]], i32 3
+; AVX-NEXT:    [[S2:%.*]] = select i1 [[S1]], i1 [[TMP8]], i1 false
+; AVX-NEXT:    [[TMP9:%.*]] = extractelement <4 x i1> [[TMP5]], i32 1
+; AVX-NEXT:    [[S3:%.*]] = select i1 [[S2]], i1 [[TMP9]], i1 false
+; AVX-NEXT:    ret i1 [[S3]]
 ;
   %x0 = extractelement <4 x i32> %x, i32 0
   %x1 = extractelement <4 x i32> %x, i32 1
   %x2 = extractelement <4 x i32> %x, i32 2
   %x3 = extractelement <4 x i32> %x, i32 3
   %c0 = icmp ult i32 %x0, 0
   %c1 = icmp slt i32 %x1, 0
   %c2 = icmp sgt i32 %x2, 0