[SLP][NFC] Refactor SLPVectorizerPass::vectorizeRootInstruction method.

[vdmitrie]

Summary

The goal is to separate collecting items for post-processing and processing them.
Post processing also outlined as dedicated method.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11807–11808

It can be merged:

if (auto *Inst = dyn_cast<Instruction>(Op); Inst && !R.isDeleted(Inst))

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11807–11808

I'll make this cleanup in the main patch during outlining. Is that okay with you?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11807–11808

Can you outline this code in this patch?

[vporpo]

llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h

128

Nit: This function does the actual work, so we should probably use different names for this and for the one below. Perhaps vectorizeRootInstructionImpl ?

[vdmitrie]

Update as per request

[vdmitrie]

llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h

128

To be honest I'm not a big fan of such naming for methods (unless it really necessary).
If you do not insist on the change I'd keep both using same name.

[vporpo]

llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h

128

Well, using the same function name is fine as long as they do the exact same thing, but in this case the caller also dealing with the postponed values. Yeah, I prefer more descriptive names too than *Impl, but in this case I can't think of anything better. Anyway, feel free to keep the same name.

[vdmitrie]

llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h

128

Changing the name to vectorizeHorReduction would probably fit better.

[vdmitrie]

update

[ABataev]

LG

llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h

 class LoopInfo;
 class OptimizationRemarkEmitter;
 class PHINode;
 class ScalarEvolution;
 class StoreInst;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 class Value;
+class WeakTrackingVH;
 
 /// A private "module" namespace for types and utilities used by this pass.
 /// These are implementation details and should not be used by clients.
 namespace slpvectorizer {
 
 class BoUpSLP;
 
 } // end namespace slpvectorizer
private:
   /// size.
   /// \returns true if a value was vectorized.
   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
                           bool LimitForRegisterSize = false);
 
   /// Try to vectorize a chain that may start at the operands of \p I.
   bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
 
+  /// Try to vectorize chains that may start at the operands of
+  /// instructions in \p Insts.
+  bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
+                      slpvectorizer::BoUpSLP &R);
+
   /// Vectorize the store instructions collected in Stores.
   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
 
   /// Vectorize the index computations of the getelementptr instructions
   /// collected in GEPs.
   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 
-  /// Try to find horizontal reduction or otherwise vectorize a chain of binary
-  /// operators.
+  /// Try to find horizontal reduction or otherwise, collect instructions
+  /// for postponed vectorization attempts.
+  /// \a P if not null designates phi node the reduction is fed into
+  /// (with reduction operators \a V or one of its operands, in a basic block
+  /// \a BB).
+  /// \returns true if a horizontal reduction was matched and reduced.
+  /// \returns false if \a V is null or not an instruction,
+  /// or a horizontal reduction was not matched or not possible.
+  bool vectorizeHorReduction(PHINode *P, Value *V, BasicBlock *BB,
+                             slpvectorizer::BoUpSLP &R,
+                             TargetTransformInfo *TTI,
+                             SmallVectorImpl<WeakTrackingVH> &PostponedInsts);
+
+  /// Make an attempt to vectorize reduction and then try to vectorize
+  /// postponed binary operations.
+  /// \returns true on any successfull vectorization.
   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
                                 slpvectorizer::BoUpSLP &R,
                                 TargetTransformInfo *TTI);
 
   /// Try to vectorize trees that start at insertvalue instructions.
   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
                                 slpvectorizer::BoUpSLP &R);
 

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

if (match(I, m_Intrinsic<Intrinsic::smin>(m_Value(V0), m_Value(V1))))
     return true;
   if (match(I, m_Intrinsic<Intrinsic::umax>(m_Value(V0), m_Value(V1))))
     return true;
   if (match(I, m_Intrinsic<Intrinsic::umin>(m_Value(V0), m_Value(V1))))
     return true;
   return false;
 }
 
-/// Attempt to reduce a horizontal reduction.
-/// If it is legal to match a horizontal reduction feeding the phi node \a P
-/// with reduction operators \a Root (or one of its operands) in a basic block
-/// \a BB, then check if it can be done. If horizontal reduction is not found
-/// and root instruction is a binary operation, vectorization of the operands is
-/// attempted.
-/// \returns true if a horizontal reduction was matched and reduced or operands
-/// of one of the binary instruction were vectorized.
-/// \returns false if a horizontal reduction was not matched (or not possible)
-/// or no vectorization of any binary operation feeding \a Root instruction was
-/// performed.
-static bool tryToVectorizeHorReductionOrInstOperands(
-    PHINode *P, Instruction *Root, BasicBlock *BB, BoUpSLP &R,
-    TargetTransformInfo *TTI, ScalarEvolution &SE, const DataLayout &DL,
-    const TargetLibraryInfo &TLI,
-    const function_ref<bool(Instruction *, BoUpSLP &)> Vectorize) {
+bool SLPVectorizerPass::vectorizeHorReduction(
+    PHINode *P, Value *V, BasicBlock *BB, BoUpSLP &R, TargetTransformInfo *TTI,
+    SmallVectorImpl<WeakTrackingVH> &PostponedInsts) {
   if (!ShouldVectorizeHor)
     return false;
 
+  auto *Root = dyn_cast_or_null<Instruction>(V);
   if (!Root)
     return false;
 
+  if (!isa<BinaryOperator>(Root))
+    P = nullptr;
+
   if (Root->getParent() != BB || isa<PHINode>(Root))
     return false;
   // Start analysis starting from Root instruction. If horizontal reduction is
   // found, try to vectorize it. If it is not a horizontal reduction or
   // vectorization is not possible or not effective, and currently analyzed
   // instruction is a binary operation, try to vectorize the operands, using
   // pre-order DFS traversal order. If the operands were not vectorized, repeat
   // the same procedure considering each operand as a possible root of the
   // horizontal reduction.
   // Interrupt the process if the Root instruction itself was vectorized or all
   // sub-trees not higher that RecursionMaxDepth were analyzed/vectorized.
-  // Skip the analysis of CmpInsts. Compiler implements postanalysis of the
-  // CmpInsts so we can skip extra attempts in
-  // tryToVectorizeHorReductionOrInstOperands and save compile time.
+  // If a horizintal reduction was not matched or vectorized we collect
+  // instructions for possible later attempts for vectorization.
   std::queue<std::pair<Instruction *, unsigned>> Stack;
   Stack.emplace(Root, 0);
   SmallPtrSet<Value *, 8> VisitedInstrs;
-  SmallVector<WeakTrackingVH> PostponedInsts;
   bool Res = false;
-  auto &&TryToReduce = [TTI, &SE, &DL, &P, &R, &TLI](Instruction *Inst,
-                                                     Value *&B0,
-                                                     Value *&B1) -> Value * {
+  auto &&TryToReduce = [this, TTI, &P, &R](Instruction *Inst, Value *&B0,
     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))
+      if (HorRdx.matchAssociativeReduction(P, Inst, *SE, *DL, *TLI))
         return HorRdx.tryToReduce(R, TTI);
     }
     return nullptr;
   };
   while (!Stack.empty()) {
     Instruction *Inst;
     unsigned Level;
     std::tie(Inst, Level) = Stack.front();
if (Value *V = TryToReduce(Inst, B0, B1)) {
           // matchAssociativeReduction function unless this is the root node.
           P = nullptr;
           continue;
         }
       }
       // Set P to nullptr to avoid re-analysis of phi node in
       // matchAssociativeReduction function unless this is the root node.
       P = nullptr;
-      // Do not try to vectorize CmpInst operands, this is done separately.
-      // Final attempt for binop args vectorization should happen after the loop
-      // to try to find reductions.
+      // Do not collect CmpInst or InsertElementInst/InsertValueInst as their
+      // analysis is done separately.
       if (!isa<CmpInst, InsertElementInst, InsertValueInst>(Inst))
         PostponedInsts.push_back(Inst);
     }
 
     // Try to vectorize operands.
     // Continue analysis for the instruction from the same basic block only to
     // save compile time.
     if (++Level < RecursionMaxDepth)
       for (auto *Op : Inst->operand_values())
         if (VisitedInstrs.insert(Op).second)
           if (auto *I = dyn_cast<Instruction>(Op))
             // Do not try to vectorize CmpInst operands,  this is done
             // separately.
             if (!isa<PHINode, CmpInst, InsertElementInst, InsertValueInst>(I) &&
                 !R.isDeleted(I) && I->getParent() == BB)
               Stack.emplace(I, Level);
   }
-  // Try to vectorized binops where reductions were not found.
-  for (Value *V : PostponedInsts)
-    if (auto *Inst = dyn_cast<Instruction>(V))
-      if (!R.isDeleted(Inst))
-        Res |= Vectorize(Inst, R);
   return Res;
 }
 
 bool SLPVectorizerPass::vectorizeRootInstruction(PHINode *P, Value *V,
                                                  BasicBlock *BB, BoUpSLP &R,
                                                  TargetTransformInfo *TTI) {
-  auto *I = dyn_cast_or_null<Instruction>(V);
-  if (!I)
-    return false;
+  SmallVector<WeakTrackingVH> PostponedInsts;
+  bool Res = vectorizeHorReduction(P, V, BB, R, TTI, PostponedInsts);
+  Res |= tryToVectorize(PostponedInsts, R);
+  return Res;
+}
 
-  if (!isa<BinaryOperator>(I))
-    P = nullptr;
-  // Try to match and vectorize a horizontal reduction.
-  auto &&ExtraVectorization = [this](Instruction *I, BoUpSLP &R) -> bool {
-    return tryToVectorize(I, R);
-  };
-  return tryToVectorizeHorReductionOrInstOperands(P, I, BB, R, TTI, *SE, *DL,
-                                                  *TLI, ExtraVectorization);
+bool SLPVectorizerPass::tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
+                                       BoUpSLP &R) {
+  bool Res = false;
+  for (Value *V : Insts)
+    if (auto *Inst = dyn_cast<Instruction>(V); Inst && !R.isDeleted(Inst))
+      Res |= tryToVectorize(Inst, R);
+  return Res;
 }
 
 bool SLPVectorizerPass::vectorizeInsertValueInst(InsertValueInst *IVI,
                                                  BasicBlock *BB, BoUpSLP &R) {
   const DataLayout &DL = BB->getModule()->getDataLayout();
   if (!R.canMapToVector(IVI->getType(), DL))
     return false;