[SLP] Allow vectorization of the instruction from the same basic blocks only, NFC.

[ABataev]

Summary

After some changes in SLP vectorizer we missed some additional checks to
limit the number of instructions for vectorization. We should not perform analysis
of the instructions if the parent of instruction is not the same as the
parent of the first instruction in the tree or it was analyzed already.

[ABataev]

Update

[anna]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4771 ↗

(On Diff #104886)

Could you please explain why you bail out here? If it's for clamping the number of operands, that'll get operated on the loop below, why not just limit the recursion depth to 6 instead of 12?

4825 ↗

(On Diff #104886)

Please add a comment here explicitly stating that you're limiting this to the same basic block to save compile time.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4771 ↗

(On Diff #104886)

I tried to reduce the number of checks for PHINode inside the loop and reduce number of ush_backs/pop_backs to Stack. In the existing code if the next instruction is PHINode, we push_back it to Stack, then pop it up from Stack and drop it. New code tries to avoid such extra dummy operations.

4825 ↗

(On Diff #104886)

Will do

[ABataev]

Update after review

[anna]

LGTM.

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

static bool tryToVectorizeHorReductionOrInstOperands(
     TargetTransformInfo *TTI,
     const function_ref<bool(BinaryOperator *, BoUpSLP &)> Vectorize) {
   if (!ShouldVectorizeHor)
     return false;
 
   if (!Root)
     return false;
 
-  if (Root->getParent() != BB)
+  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.
   SmallVector<std::pair<WeakTrackingVH, unsigned>, 8> Stack(1, {Root, 0});
   SmallSet<Value *, 8> VisitedInstrs;
   bool Res = false;
   while (!Stack.empty()) {
     Value *V;
     unsigned Level;
     std::tie(V, Level) = Stack.pop_back_val();
     if (!V)
       continue;
     auto *Inst = dyn_cast<Instruction>(V);
-    if (!Inst || isa<PHINode>(Inst))
+    if (!Inst)
       continue;
     if (auto *BI = dyn_cast<BinaryOperator>(Inst)) {
       HorizontalReduction HorRdx;
       if (HorRdx.matchAssociativeReduction(P, BI)) {
         if (HorRdx.tryToReduce(R, TTI)) {
           Res = true;
           // Set P to nullptr to avoid re-analysis of phi node in
           // matchAssociativeReduction function unless this is the root node.
while (!Stack.empty()) {
     // matchAssociativeReduction function unless this is the root node.
     P = nullptr;
     if (Vectorize(dyn_cast<BinaryOperator>(Inst), R)) {
       Res = true;
       continue;
     }
 
     // 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))
+            if (!isa<PHINode>(Inst) && I->getParent() == BB)
               Stack.emplace_back(Op, Level);
   }
   return Res;
 }
 
 bool SLPVectorizerPass::vectorizeRootInstruction(PHINode *P, Value *V,
                                                  BasicBlock *BB, BoUpSLP &R,
                                                  TargetTransformInfo *TTI) {
   if (!V)