[SLP][NFC] Cleanup: Separate vectorization of Inserts and CmpInsts.

[vporpo]

Summary

This deprecates vectorizeSimpleInstructions() and replaces it with separate
functions that vectorize CmpInsts and Inserts.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

14708–14709

It does not make it simpler

14740–14741

Same

14749–14753

You have to duplicate the same code, which is more complex than before

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

14749–14753

The check for it->isTerminator() controls whether we vectorize CmpInsts. Hiding it within vectorizeSimpleInstructions is just confusing and makes it harder to read.
To avoid repeating the code we can use a lambda for this, but the separation of vectorizing Inserts and CmpInsts should be clear. Wdyt?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

14749–14753

You can try, but check that the logic does not become more complex than before.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

14749–14753

OK let me give it a try.

[vporpo]

Using lambdas to avoid repetition.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

14651–14653

Use dyn_cast:

if (auto *Cmp = dyn_cast<CmpInst>(I))
  return PostProcessCmps.contains(Cmp);
return isa<InsertElementInst, InsertValueInst>(I) && PostProcessInserts.contains(I);

[vporpo]

Using dyn_cast<CmpInst>.

[ABataev]

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

148–149

Why need a template here since looks like it accepts only ArrayRef?

[vporpo]

Using CmpInst * instead of Instruction * in the loops of vectorizeCmpInsts(). This makes it a bit more explicit that we are expecting a range of CmpInst *.

[vporpo]

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

148–149

We are passing an iterator_range and there is no ArrayRef constructor with an iterator_range argument.
I could use the actual type iterator_range<std::reverse_iterator<SmallSetVector<CmpInst *, 8>::iterator>> but it is pretty ugly and if we ever need to remove the reverse order at the call-site we would have to change this type too. Wdyt?

[ABataev]

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

148–149

SmallSetVector class, used to store instruction, has getArrayRef() member function, which can return ArrayRef.

[vporpo]

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

148–149

I don't see how getting the ArrayRef from the SmallSetVector would help. We still need to pass an iterator_range as we need to iterate in reverse.
The only way this would work is if we reverse the iteration within vectorizeCmpInsts which I don't think we should do.

[ABataev]

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

148–149

Better to avoid template. Better to pass ArrayRef and reverse it there (adding the explanation, why need to do it).

[vporpo]

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

148–149

Reversing the iteration order in vectorizeCmpInsts is not a good solution, because no one expects that the function would walk the array in reverse.

Using a range seems to be the best option here. This pattern with a template <typename RangeT> is being used in several other places throughout LLVM. I am not sure I understand why you don't like it.

[ABataev]

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

148–149

It just makes less obvous constraints and requirements for tje parameter, while ArrayRef explicitly provides it. Would be good somehow specify the expected constraints, like iterator_range<T> or something similar.

[vporpo]

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

148–149

I agree, something like iterator_range<T> makes it more explicit. Let me update the patch.

[vporpo]

Changed RangeT to iterator_range<ItT> CmpInsts.

[ABataev]

LG

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

private:
   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
                                 slpvectorizer::BoUpSLP &R);
 
   /// Try to vectorize trees that start at insertelement instructions.
   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
                                   slpvectorizer::BoUpSLP &R);
 
   /// Tries to vectorize \p CmpInts. \Returns true on success.
-  bool vectorizeCmpInsts(ArrayRef<CmpInst *> CmpInsts, BasicBlock *BB,
+  template <typename RangeT>
+  bool vectorizeCmpInsts(RangeT CmpInsts, BasicBlock *BB,
                          slpvectorizer::BoUpSLP &R);
 
-  /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
+  /// Tries to vectorize constructs started from InsertValueInst or
   /// InsertElementInst instructions.
-  bool vectorizeSimpleInstructions(InstSetVector &Instructions, BasicBlock *BB,
-                                   slpvectorizer::BoUpSLP &R,
-                                   bool AtTerminator);
+  bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB,
+                        slpvectorizer::BoUpSLP &R);
 
   /// Scan the basic block and look for patterns that are likely to start
   /// a vectorization chain.
   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 
   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
                            unsigned Idx, unsigned MinVF);
 

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

if (auto *I1 = dyn_cast<Instruction>(Op1))
         if (S.getOpcode())
           continue;
         return false;
       }
   }
   return IsCompatibility;
 }
 
-bool SLPVectorizerPass::vectorizeCmpInsts(ArrayRef<CmpInst *> CmpInsts,
-                                          BasicBlock *BB, BoUpSLP &R) {
+template <typename RangeT>
+bool SLPVectorizerPass::vectorizeCmpInsts(RangeT CmpInsts, BasicBlock *BB,
+                                          BoUpSLP &R) {
   bool Changed = false;
   // Try to find reductions first.
-  for (Instruction *I : CmpInsts) {
+  for (CmpInst *I : CmpInsts) {
     if (R.isDeleted(I))
       continue;
     for (Value *Op : I->operands())
       if (auto *RootOp = dyn_cast<Instruction>(Op))
         Changed |= vectorizeRootInstruction(nullptr, RootOp, BB, R, TTI);
   }
   // Try to vectorize operands as vector bundles.
-  for (Instruction *I : CmpInsts) {
+  for (CmpInst *I : CmpInsts) {
     if (R.isDeleted(I))
       continue;
     Changed |= tryToVectorize(I, R);
   }
   // Try to vectorize list of compares.
   // Sort by type, compare predicate, etc.
   auto CompareSorter = [&](Value *V, Value *V2) {
     return compareCmp<false>(V, V2, *TLI,
Changed |= tryToVectorizeSequence<Value>(
         if (ArePossiblyReducedInOtherBlock)
           return false;
         return tryToVectorizeList(Candidates, R, LimitForRegisterSize);
       },
       /*LimitForRegisterSize=*/true, R);
   return Changed;
 }
 
-bool SLPVectorizerPass::vectorizeSimpleInstructions(InstSetVector &Instructions,
-                                                    BasicBlock *BB, BoUpSLP &R,
-                                                    bool AtTerminator) {
+bool SLPVectorizerPass::vectorizeInserts(InstSetVector &Instructions,
+                                         BasicBlock *BB, BoUpSLP &R) {
   assert(all_of(Instructions,
                 [](auto *I) {
-                  return isa<CmpInst, InsertElementInst, InsertValueInst>(I);
+                  return isa<InsertElementInst, InsertValueInst>(I);
                 }) &&
-         "This function only accepts Cmp and Insert instructions");
+         "This function only accepts Insert instructions");
   bool OpsChanged = false;
-  SmallVector<CmpInst *, 4> PostponedCmps;
   SmallVector<WeakTrackingVH> PostponedInsts;
   // pass1 - try to vectorize reductions only
   for (auto *I : reverse(Instructions)) {
     if (R.isDeleted(I))
       continue;
-    if (isa<CmpInst>(I)) {
-      PostponedCmps.push_back(cast<CmpInst>(I));
-      continue;
-    }
     OpsChanged |= vectorizeHorReduction(nullptr, I, BB, R, TTI, PostponedInsts);
   }
   // pass2 - try to match and vectorize a buildvector sequence.
   for (auto *I : reverse(Instructions)) {
     if (R.isDeleted(I) || isa<CmpInst>(I))
       continue;
     if (auto *LastInsertValue = dyn_cast<InsertValueInst>(I)) {
       OpsChanged |= vectorizeInsertValueInst(LastInsertValue, BB, R);
     } else if (auto *LastInsertElem = dyn_cast<InsertElementInst>(I)) {
       OpsChanged |= vectorizeInsertElementInst(LastInsertElem, BB, R);
     }
   }
   // Now try to vectorize postponed instructions.
   OpsChanged |= tryToVectorize(PostponedInsts, R);
 
-  if (AtTerminator) {
-    OpsChanged |= vectorizeCmpInsts(PostponedCmps, BB, R);
-    Instructions.clear();
-  } else {
-    Instructions.clear();
-    // Insert in reverse order since the PostponedCmps vector was filled in
-    // reverse order.
-    Instructions.insert(PostponedCmps.rbegin(), PostponedCmps.rend());
-  }
   return OpsChanged;
 }
 
 bool SLPVectorizerPass::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {
   bool Changed = false;
   SmallVector<Value *, 4> Incoming;
   SmallPtrSet<Value *, 16> VisitedInstrs;
   // Maps phi nodes to the non-phi nodes found in the use tree for each phi
HaveVectorizedPhiNodes = tryToVectorizeSequence<Value>(
         },
         /*LimitForRegisterSize=*/true, R);
     Changed |= HaveVectorizedPhiNodes;
     VisitedInstrs.insert(Incoming.begin(), Incoming.end());
   } while (HaveVectorizedPhiNodes);
 
   VisitedInstrs.clear();
 
-  InstSetVector PostProcessInstructions;
+  InstSetVector PostProcessInserts;
+  SmallSetVector<CmpInst *, 8> PostProcessCmps;
   SmallDenseSet<Instruction *, 4> KeyNodes;
+  // Vectorizes Inserts in `PostProcessInserts` and if `VecctorizeCmps` is true
+  // also vectorizes `PostProcessCmps`.
+  auto VectorizeInsertsAndCmps = [&](bool VectorizeCmps) {
+    bool Changed = vectorizeInserts(PostProcessInserts, BB, R);
+    if (VectorizeCmps) {
+      Changed |= vectorizeCmpInsts(reverse(PostProcessCmps), BB, R);
+      PostProcessCmps.clear();
+    }
+    PostProcessInserts.clear();
+    return Changed;
+  };
+  // Returns true if `I` is in `PostProcessInserts` or `PostProcessCmps`.
+  auto IsInPostProcessInstrs = [&](Instruction *I) {
+    if (auto *Cmp = dyn_cast<CmpInst>(I))
+      return PostProcessCmps.contains(Cmp);
+    return isa<InsertElementInst, InsertValueInst>(I) &&
+           PostProcessInserts.contains(I);
+  };
   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
     // Skip instructions with scalable type. The num of elements is unknown at
     // compile-time for scalable type.
     if (isa<ScalableVectorType>(it->getType()))
       continue;
 
     // Skip instructions marked for the deletion.
     if (R.isDeleted(&*it))
       continue;
     // We may go through BB multiple times so skip the one we have checked.
     if (!VisitedInstrs.insert(&*it).second) {
       if (it->use_empty() && KeyNodes.contains(&*it) &&
-          vectorizeSimpleInstructions(PostProcessInstructions, BB, R,
-                                      it->isTerminator())) {
+          VectorizeInsertsAndCmps(/*VectorizeCmps=*/it->isTerminator())) {
         // We would like to start over since some instructions are deleted
         // and the iterator may become invalid value.
         Changed = true;
         it = BB->begin();
         e = BB->end();
       }
       continue;
     }
if (PHINode *P = dyn_cast<PHINode>(it)) {
         // after processing BB.
         if (BB == P->getIncomingBlock(I) ||
             !DT->isReachableFromEntry(P->getIncomingBlock(I)))
           continue;
 
         // Postponed instructions should not be vectorized here, delay their
         // vectorization.
         if (auto *PI = dyn_cast<Instruction>(P->getIncomingValue(I));
-            PI && !PostProcessInstructions.contains(PI))
+            PI && !IsInPostProcessInstrs(PI))
           Changed |= vectorizeRootInstruction(nullptr, PI,
                                               P->getIncomingBlock(I), R, TTI);
       }
       continue;
     }
 
     // Ran into an instruction without users, like terminator, or function call
     // with ignored return value, store. Ignore unused instructions (basing on
     // instruction type, except for CallInst and InvokeInst).
if (it->use_empty() &&
         TryToVectorizeRoot = (I == Stores.end() || I->second.size() == 1) &&
                              SI->getValueOperand()->hasOneUse();
       }
       if (TryToVectorizeRoot) {
         for (auto *V : it->operand_values()) {
           // Postponed instructions should not be vectorized here, delay their
           // vectorization.
           if (auto *VI = dyn_cast<Instruction>(V);
-              VI && !PostProcessInstructions.contains(VI))
+              VI && !IsInPostProcessInstrs(VI))
             // Try to match and vectorize a horizontal reduction.
             OpsChanged |= vectorizeRootInstruction(nullptr, VI, BB, R, TTI);
         }
       }
       // Start vectorization of post-process list of instructions from the
       // top-tree instructions to try to vectorize as many instructions as
       // possible.
-      OpsChanged |= vectorizeSimpleInstructions(PostProcessInstructions, BB, R,
-                                                it->isTerminator());
+      OpsChanged |=
+          VectorizeInsertsAndCmps(/*VectorizeCmps=*/it->isTerminator());
       if (OpsChanged) {
         // We would like to start over since some instructions are deleted
         // and the iterator may become invalid value.
         Changed = true;
         it = BB->begin();
         e = BB->end();
         continue;
       }
     }
 
-    if (isa<CmpInst, InsertElementInst, InsertValueInst>(it))
-      PostProcessInstructions.insert(&*it);
+    if (isa<InsertElementInst, InsertValueInst>(it))
+      PostProcessInserts.insert(&*it);
+    else if (isa<CmpInst>(it))
+      PostProcessCmps.insert(cast<CmpInst>(&*it));
   }
 
   return Changed;
 }
 
 bool SLPVectorizerPass::vectorizeGEPIndices(BasicBlock *BB, BoUpSLP &R) {
   auto Changed = false;
   for (auto &Entry : GEPs) {