[SLP][NFC]Add missing finalize params in the CostEstimator, NFC.

[ABataev]

Summary

Prepare functions for generalization of codegen/cost estimation.

[ABataev]

Rebase

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7126–7133

"Adds another" suggests we can combine these, but all it does it overwrite the mask/vector list - should we assert(CommonMask.empty() && InVectors.empty()) ?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7126–7133

Yes, will combine in the next patches, currently this functionality is not used, so just added a simple version. Will add assertions

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7312

(style) unnecessary control-flow (please excuse the bad indentation)

if (all_of(GatheredScalars, PoisonValue ::classof))
  return Estimator.finalize(E->ReuseShuffleIndices);

return Estimator.finalize(E->ReuseShuffleIndices, E->Scalars.size(),
                                  [&](Value *&Vec, SmallVectorImpl<int> &Mask) {
                                    Vec = Estimator.gather(
                                        GatheredScalars, Constant::getNullValue(FixedVectorType::get(
                                                             GatheredScalars.front()->getType(),
                                                             GatheredScalars.size())));
                                  });

[ABataev]

Rebase + address comments

[RKSimon]

LGTM with one minor

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7123

maybe add the assertion in these other add() methods as well (in a separate commit).

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7123

Most probably the next patch will make these functions more smart.

[ArturGainullin]

Hi @ABataev, this commit causes assertion failure on the following test:

; ModuleID = 'reduced.bc'
target datalayout = "e-i64:64-i128:128-v16:16-v32:32-n16:32:64"
target triple = "nvptx64-unknown-unknown"

define <2 x float> @baz() {
bb:
  %extractelement = extractelement <2 x float> zeroinitializer, i64 0
  %fcmp = fcmp uno float %extractelement, 0.000000e+00
  %fcmp1 = fcmp uno float 0.000000e+00, 0.000000e+00
  %or = or i1 %fcmp, %fcmp1
  %fcmp2 = fcmp oeq float 0.000000e+00, 0.000000e+00
  %or3 = or i1 %fcmp2, %or
  %fcmp4 = fcmp oeq float 0.000000e+00, 0.000000e+00
  %or5 = or i1 %fcmp4, %or3
  br i1 %or5, label %bb6, label %bb7

bb6:                                              ; preds = %bb
  ret <2 x float> zeroinitializer

bb7:                                              ; preds = %bb
  ret <2 x float> zeroinitializer
}

Could you please take a look?

$ opt -passes=slp-vectorizer -disable-output test.ll
opt: /iusers/againull/llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:7128: void llvm::slpvectorizer::BoUpSLP::ShuffleCostEstimator::add(llvm::Value*, llvm::ArrayRef<int>): Assertion `CommonMask.empty() && InVectors.empty() && "Expected empty input mask/vectors."' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: opt -passes=slp-vectorizer -disable-output test.ll
 #0 0x00007f593ce67301 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMSupport.so.17git+0x1aa301)
 #1 0x00007f593ce64d24 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f593c7d5db0 __restore_rt (/lib64/libc.so.6+0x59db0)
 #3 0x00007f593c82242c __pthread_kill_implementation (/lib64/libc.so.6+0xa642c)
 #4 0x00007f593c7d5d06 gsignal (/lib64/libc.so.6+0x59d06)
 #5 0x00007f593c7a87d3 abort (/lib64/libc.so.6+0x2c7d3)
 #6 0x00007f593c7a86fb _nl_load_domain.cold (/lib64/libc.so.6+0x2c6fb)
 #7 0x00007f593c7cec86 (/lib64/libc.so.6+0x52c86)
 #8 0x00007f593e20aa60 llvm::slpvectorizer::BoUpSLP::getEntryCost(llvm::slpvectorizer::BoUpSLP::TreeEntry const*, llvm::ArrayRef<llvm::Value*>, llvm::SmallPtrSetImpl<llvm::Value*>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x116a60)
 #9 0x00007f593e23188b llvm::slpvectorizer::BoUpSLP::getTreeCost(llvm::ArrayRef<llvm::Value*>) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x13d88b)
#10 0x00007f593e23513e (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) SLPVectorizer.cpp:0:0
#11 0x00007f593e237e03 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Instruction*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x143e03)
#12 0x00007f593e23c0f4 llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Instruction*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (.constprop.0) SLPVectorizer.cpp:0:0
#13 0x00007f593e23f740 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x14b740)
#14 0x00007f593e2426db llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (.part.0) SLPVectorizer.cpp:0:0
#15 0x00007f593e242fe2 llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x14efe2)
#16 0x00007f593fbb50ce llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMPasses.so.17git+0x5e0ce)
#17 0x00007f593feb79fb 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>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMNVPTXCodeGen.so.17git+0x9b9fb)
#18 0x00007f593d2674dd llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMCore.so.17git+0x2c54dd)
#19 0x00007f593fea00ee llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMNVPTXCodeGen.so.17git+0x840ee)
#20 0x00007f593d26538c llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMCore.so.17git+0x2c338c)
#21 0x0000000000422c9d llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (/localdisk2/againull/llvm-project/build/bin/opt+0x422c9d)
#22 0x0000000000415baa main (/localdisk2/againull/llvm-project/build/bin/opt+0x415baa)
#23 0x00007f593c7c0e50 __libc_start_call_main (/lib64/libc.so.6+0x44e50)
#24 0x00007f593c7c0efc __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x44efc)
#25 0x00000000004167e5 _start (/localdisk2/againull/llvm-project/build/bin/opt+0x4167e5)
Aborted (core dumped)

[ABataev]

In D150121#4347435, @ArturGainullin wrote:

Hi @ABataev, this commit causes assertion failure on the following test:

; ModuleID = 'reduced.bc'
target datalayout = "e-i64:64-i128:128-v16:16-v32:32-n16:32:64"
target triple = "nvptx64-unknown-unknown"

define <2 x float> @baz() {
bb:
  %extractelement = extractelement <2 x float> zeroinitializer, i64 0
  %fcmp = fcmp uno float %extractelement, 0.000000e+00
  %fcmp1 = fcmp uno float 0.000000e+00, 0.000000e+00
  %or = or i1 %fcmp, %fcmp1
  %fcmp2 = fcmp oeq float 0.000000e+00, 0.000000e+00
  %or3 = or i1 %fcmp2, %or
  %fcmp4 = fcmp oeq float 0.000000e+00, 0.000000e+00
  %or5 = or i1 %fcmp4, %or3
  br i1 %or5, label %bb6, label %bb7

bb6:                                              ; preds = %bb
  ret <2 x float> zeroinitializer

bb7:                                              ; preds = %bb
  ret <2 x float> zeroinitializer
}

Could you please take a look?

$ opt -passes=slp-vectorizer -disable-output test.ll
opt: /iusers/againull/llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:7128: void llvm::slpvectorizer::BoUpSLP::ShuffleCostEstimator::add(llvm::Value*, llvm::ArrayRef<int>): Assertion `CommonMask.empty() && InVectors.empty() && "Expected empty input mask/vectors."' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: opt -passes=slp-vectorizer -disable-output test.ll
 #0 0x00007f593ce67301 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMSupport.so.17git+0x1aa301)
 #1 0x00007f593ce64d24 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f593c7d5db0 __restore_rt (/lib64/libc.so.6+0x59db0)
 #3 0x00007f593c82242c __pthread_kill_implementation (/lib64/libc.so.6+0xa642c)
 #4 0x00007f593c7d5d06 gsignal (/lib64/libc.so.6+0x59d06)
 #5 0x00007f593c7a87d3 abort (/lib64/libc.so.6+0x2c7d3)
 #6 0x00007f593c7a86fb _nl_load_domain.cold (/lib64/libc.so.6+0x2c6fb)
 #7 0x00007f593c7cec86 (/lib64/libc.so.6+0x52c86)
 #8 0x00007f593e20aa60 llvm::slpvectorizer::BoUpSLP::getEntryCost(llvm::slpvectorizer::BoUpSLP::TreeEntry const*, llvm::ArrayRef<llvm::Value*>, llvm::SmallPtrSetImpl<llvm::Value*>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x116a60)
 #9 0x00007f593e23188b llvm::slpvectorizer::BoUpSLP::getTreeCost(llvm::ArrayRef<llvm::Value*>) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x13d88b)
#10 0x00007f593e23513e (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) SLPVectorizer.cpp:0:0
#11 0x00007f593e237e03 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Instruction*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x143e03)
#12 0x00007f593e23c0f4 llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Instruction*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (.constprop.0) SLPVectorizer.cpp:0:0
#13 0x00007f593e23f740 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x14b740)
#14 0x00007f593e2426db llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (.part.0) SLPVectorizer.cpp:0:0
#15 0x00007f593e242fe2 llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMVectorize.so.17git+0x14efe2)
#16 0x00007f593fbb50ce llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMPasses.so.17git+0x5e0ce)
#17 0x00007f593feb79fb 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>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMNVPTXCodeGen.so.17git+0x9b9fb)
#18 0x00007f593d2674dd llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMCore.so.17git+0x2c54dd)
#19 0x00007f593fea00ee llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMNVPTXCodeGen.so.17git+0x840ee)
#20 0x00007f593d26538c llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/localdisk2/againull/llvm-project/build/bin/../lib/libLLVMCore.so.17git+0x2c338c)
#21 0x0000000000422c9d llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (/localdisk2/againull/llvm-project/build/bin/opt+0x422c9d)
#22 0x0000000000415baa main (/localdisk2/againull/llvm-project/build/bin/opt+0x415baa)
#23 0x00007f593c7c0e50 __libc_start_call_main (/lib64/libc.so.6+0x44e50)
#24 0x00007f593c7c0efc __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x44efc)
#25 0x00000000004167e5 _start (/localdisk2/againull/llvm-project/build/bin/opt+0x4167e5)
Aborted (core dumped)

Fixed in 9a7248f56164b44b07df421384c12541a91e6d84

[ArturGainullin]

@ABataev Thanks a lot!

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

for (const auto &Data : ExtractVectorsTys) {
       }
     }
     // 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.
     Cost += computeExtractCost(VL, Mask, ShuffleKind);
-    InVectors.assign(1, E);
     return VecBase;
   }
   void add(const TreeEntry *E1, const TreeEntry *E2, ArrayRef<int> Mask) {
     CommonMask.assign(Mask.begin(), Mask.end());
     InVectors.assign({E1, E2});
   }
   void add(const TreeEntry *E1, ArrayRef<int> Mask) {
     CommonMask.assign(Mask.begin(), Mask.end());
     InVectors.assign(1, E1);
   }
-  void gather(ArrayRef<Value *> VL, Value *Root = nullptr) {
+  /// Adds another one input vector and the mask for the shuffling.
+  void add(Value *V1, ArrayRef<int> Mask) {
+    assert(CommonMask.empty() && InVectors.empty() &&
+           "Expected empty input mask/vectors.");
+    CommonMask.assign(Mask.begin(), Mask.end());
+    InVectors.assign(1, V1);
+  }
+  Value *gather(ArrayRef<Value *> VL, Value *Root = nullptr) {
     Cost += getBuildVectorCost(VL, Root);
     if (!Root) {
       assert(InVectors.empty() && "Unexpected input vectors for buildvector.");
       // FIXME: Need to find a way to avoid use of getNullValue here.
-      InVectors.assign(1, Constant::getNullValue(FixedVectorType::get(
-                              VL.front()->getType(), VL.size())));
+      SmallVector<Constant *> Vals;
+      for (Value *V : VL) {
+        if (isa<UndefValue>(V)) {
+          Vals.push_back(cast<Constant>(V));
+          continue;
+        }
+        Vals.push_back(Constant::getNullValue(V->getType()));
       }
+      return ConstantVector::get(Vals);
+    }
+    return ConstantVector::getSplat(
+        ElementCount::getFixed(VL.size()),
+        Constant::getNullValue(VL.front()->getType()));
   }
   /// Finalize emission of the shuffles.
-  InstructionCost finalize(ArrayRef<int> ExtMask) {
+  InstructionCost
+  finalize(ArrayRef<int> ExtMask, unsigned VF = 0,
+           function_ref<void(Value *&, SmallVectorImpl<int> &)> Action = {}) {
     IsFinalized = true;
+    if (Action) {
+      const PointerUnion<Value *, const TreeEntry *> &Vec = InVectors.front();
+      if (InVectors.size() == 2) {
+        Cost += createShuffle(Vec, InVectors.back(), CommonMask);
+        InVectors.pop_back();
+      } else {
+        Cost += createShuffle(Vec, nullptr, CommonMask);
+      }
+      for (unsigned Idx = 0, Sz = CommonMask.size(); Idx < Sz; ++Idx)
+        if (CommonMask[Idx] != PoisonMaskElem)
+          CommonMask[Idx] = Idx;
+      assert(VF > 0 &&
+             "Expected vector length for the final value before action.");
+      Value *V = Vec.dyn_cast<Value *>();
+      if (!Vec.isNull() && !V)
+        V = Constant::getNullValue(FixedVectorType::get(
+            Vec.get<const TreeEntry *>()->Scalars.front()->getType(),
+            CommonMask.size()));
+      Action(V, CommonMask);
+    }
     ::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 +
if (GatherShuffle) {
       }
       LLVM_DEBUG(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())));
+      if (all_of(GatheredScalars, PoisonValue ::classof))
         return Estimator.finalize(E->ReuseShuffleIndices);
+      return Estimator.finalize(
+          E->ReuseShuffleIndices, E->Scalars.size(),
+          [&](Value *&Vec, SmallVectorImpl<int> &Mask) {
+            Vec = Estimator.gather(GatheredScalars,
+                                   Constant::getNullValue(FixedVectorType::get(
+                                       GatheredScalars.front()->getType(),
+                                       GatheredScalars.size())));
+          });
     }
-    Estimator.gather(
-        GatheredScalars,
-        VL.equals(GatheredScalars)
-            ? nullptr
+    if (!all_of(GatheredScalars, PoisonValue::classof)) {
+      auto Gathers = ArrayRef(GatheredScalars).take_front(VL.size());
+      bool SameGathers = VL.equals(Gathers);
+      Value *BV = Estimator.gather(
+          Gathers, SameGathers ? nullptr
                                : Constant::getNullValue(FixedVectorType::get(
-                  GatheredScalars.front()->getType(), GatheredScalars.size())));
+                                     GatheredScalars.front()->getType(),
+                                     GatheredScalars.size())));
+      SmallVector<int> ReuseMask(Gathers.size(), PoisonMaskElem);
+      std::iota(ReuseMask.begin(), ReuseMask.end(), 0);
+      Estimator.add(BV, ReuseMask);
+    }
+    if (ExtractShuffle)
+      Estimator.add(E, std::nullopt);
     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.