Index: lib/Transforms/Vectorize/SLPVectorizer.cpp
===================================================================
--- lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -4750,55 +4750,63 @@
 }
 
 namespace {
-/// Tracks instructons and its children.
+/// Tracks if the instruction is deleted (replaced by undef value) /replaced by
+/// the new instruction (the vector version, as the result of the whole
+/// vectorization process) + tracks the processing of the instruction operands.
 class WeakTrackingVHWithLevel final : public CallbackVH {
-  /// Operand index of the instruction currently beeing analized.
-  unsigned Level = 0;
-  /// Is this the instruction that should be vectorized, or are we now
-  /// processing children (i.e. operands of this instruction) for potential
-  /// vectorization?
-  bool IsInitial = true;
+  /// Operand index of the instruction currently being analyzed. If None - try
+  /// to vectorize the instruction itself.
+  Optional<unsigned> OperandIndexAnalyzed;
 
 public:
   explicit WeakTrackingVHWithLevel() = default;
   WeakTrackingVHWithLevel(Value *V) : CallbackVH(V){};
-  /// Restart children analysis each time it is repaced by the new instruction.
+  /// Restart children analysis each time it is replaced by the new instruction.
   void allUsesReplacedWith(Value *New) override {
     setValPtr(New);
-    Level = 0;
-    IsInitial = true;
+    OperandIndexAnalyzed.reset();
   }
   /// Check if the instruction was not deleted during vectorization.
   bool isValid() const { return !getValPtr(); }
-  /// Is the istruction itself must be vectorized?
-  bool isInitial() const { return IsInitial; }
+  /// Must the instruction itself be vectorized?
+  bool analyzingInstruction() const { return !OperandIndexAnalyzed.hasValue(); }
   /// Try to vectorize children.
-  void clearInitial() { IsInitial = false; }
+  void setAnalyzingOperands() { OperandIndexAnalyzed = 0; }
   /// Are all children processed already?
-  bool isFinal() const {
-    assert(getValPtr() &&
+  bool areOperandsAnalyzed() const {
+    assert(getValPtr() && !analyzingInstruction() &&
            (isa<Instruction>(getValPtr()) &&
-            cast<Instruction>(getValPtr())->getNumOperands() >= Level));
-    return getValPtr() &&
-           cast<Instruction>(getValPtr())->getNumOperands() == Level;
+            cast<Instruction>(getValPtr())->getNumOperands() >=
+                OperandIndexAnalyzed));
+    return cast<Instruction>(getValPtr())->getNumOperands() ==
+           OperandIndexAnalyzed;
   }
   /// Get next child operation.
-  Value *nextOperand() {
+  Value *getNextOperand() {
     assert(getValPtr() && isa<Instruction>(getValPtr()) &&
-           cast<Instruction>(getValPtr())->getNumOperands() > Level);
-    return cast<Instruction>(getValPtr())->getOperand(Level++);
+           !analyzingInstruction() &&
+           cast<Instruction>(getValPtr())->getNumOperands() >
+               OperandIndexAnalyzed);
+    const unsigned CurrentOperandIndex = OperandIndexAnalyzed.getValue();
+    OperandIndexAnalyzed = CurrentOperandIndex + 1;
+    return cast<Instruction>(getValPtr())->getOperand(CurrentOperandIndex);
   }
   virtual ~WeakTrackingVHWithLevel() = default;
 };
 } // namespace
 
-/// \brief Attempt to reduce a horizontal reduction.
-/// If it is legal to match a horizontal reduction feeding
-/// the phi node P with reduction operators Root in a basic block BB, then check
-/// if it can be done.
-/// \returns true if a horizontal reduction was matched and reduced.
-/// \returns false if a horizontal reduction was not matched.
-static bool canBeVectorized(
+/// 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,
     const function_ref<bool(BinaryOperator *, BoUpSLP &)> Vectorize) {
@@ -4810,6 +4818,16 @@
 
   if (Root->getParent() != BB)
     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 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 were
+  // vectorized or all sub-trees not higher than RecursionMaxDepth were
+  // analyzed/vectorized.
   SmallVector<WeakTrackingVHWithLevel, 8> Stack(1, Root);
   SmallSet<Value *, 8> VisitedInstrs;
   bool Res = false;
@@ -4824,8 +4842,8 @@
       Stack.pop_back();
       continue;
     }
-    if (Stack.back().isInitial()) {
-      Stack.back().clearInitial();
+    if (Stack.back().analyzingInstruction()) {
+      Stack.back().setAnalyzingOperands();
       if (auto *BI = dyn_cast<BinaryOperator>(Inst)) {
         HorizontalReduction HorRdx;
         if (HorRdx.matchAssociativeReduction(P, BI)) {
@@ -4851,12 +4869,12 @@
         continue;
       }
     }
-    if (Stack.back().isFinal()) {
+    if (Stack.back().areOperandsAnalyzed()) {
       Stack.pop_back();
       continue;
     }
 
-    if (auto *NextV = dyn_cast<Instruction>(Stack.back().nextOperand()))
+    if (auto *NextV = dyn_cast<Instruction>(Stack.back().getNextOperand()))
       if (NextV->getParent() == BB && VisitedInstrs.insert(NextV).second &&
           Stack.size() < RecursionMaxDepth)
         Stack.push_back(NextV);
@@ -4876,10 +4894,10 @@
   if (!isa<BinaryOperator>(I))
     P = nullptr;
   // Try to match and vectorize a horizontal reduction.
-  return canBeVectorized(P, I, BB, R, TTI,
-                         [this](BinaryOperator *BI, BoUpSLP &R) -> bool {
-                           return tryToVectorize(BI, R);
-                         });
+  return tryToVectorizeHorReductionOrInstOperands(
+      P, I, BB, R, TTI, [this](BinaryOperator *BI, BoUpSLP &R) -> bool {
+        return tryToVectorize(BI, R);
+      });
 }
 
 bool SLPVectorizerPass::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {