Index: lib/Transforms/Vectorize/LoopVectorize.cpp
===================================================================
--- lib/Transforms/Vectorize/LoopVectorize.cpp
+++ lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -1893,6 +1893,10 @@
   /// Collect values we want to ignore in the cost model.
   void collectValuesToIgnore();
 
+  /// Find the set of instructions that is likely to be eliminated by Loop
+  /// Strength Reduction.
+  void collectLikelyLSRed();
+
   /// \returns The smallest bitwidth each instruction can be represented with.
   /// The vector equivalents of these instructions should be truncated to this
   /// type.
@@ -2068,6 +2072,10 @@
   /// as a vector operation.
   bool isConsecutiveLoadOrStore(Instruction *I);
 
+  /// A set of instructions that is likely to be eliminated by Loop Strength
+  /// Reduction.
+  SmallPtrSet<Instruction*, 4> LikelyLSRed;
+
   /// Create an analysis remark that explains why vectorization failed
   ///
   /// \p RemarkName is the identifier for the remark.  \return the remark object
@@ -7225,6 +7233,9 @@
   if (VF > 1 && isProfitableToScalarize(I, VF))
     return VectorizationCostTy(InstsToScalarize[VF][I], false);
 
+  if (VF == 1 && LikelyLSRed.count(I))
+    return VectorizationCostTy(0, false);
+
   Type *VectorTy;
   unsigned C = getInstructionCost(I, VF, VectorTy);
 
@@ -7561,6 +7572,57 @@
   return false;
 }
 
+void LoopVectorizationCostModel::collectLikelyLSRed() {
+  BasicBlock *Header = TheLoop->getHeader();
+
+  std::vector<Instruction*> worklist;
+  for (BasicBlock::iterator PHI = Header->begin(); isa<PHINode>(PHI); ++PHI)
+    worklist.push_back(&*PHI);
+
+  while (!worklist.empty()) {
+    Instruction *PhiChain = worklist.back();
+    worklist.pop_back();
+
+    for (User *U : PhiChain->users()) {
+      Instruction *UI = cast<Instruction>(U);
+
+      // Find a user that in turn has only one use,
+      if (!UI->hasOneUse() ||
+          (UI->getOpcode() != Instruction::Add &&
+           UI->getOpcode() != Instruction::Sub &&
+           UI->getOpcode() != Instruction::Mul &&
+           UI->getOpcode() != Instruction::Trunc))
+        continue;
+
+      // that is not a compare or a PHI
+      Instruction *UUI = UI->user_back();
+      if (isa<CmpInst>(UUI) || isa<PHINode>(UUI))
+        continue;
+
+      // and only uses a loop invariant value or constant, in addition to the
+      // PHI.
+      bool UsingLoopValue = false;
+      for (Value *Op : UI->operands()) {
+        if (Instruction *OpI = dyn_cast<Instruction>(Op)) {
+          if (OpI == PhiChain || !TheLoop->contains(OpI) ||
+              LikelyLSRed.count(OpI))
+            continue;
+        }
+        if (isa<Constant>(Op))
+          continue;
+
+        UsingLoopValue = true;
+        break;
+      }
+
+      if (!UsingLoopValue) {
+        worklist.push_back(UI);
+        LikelyLSRed.insert(UI);
+      }
+    }
+  }
+}
+
 void LoopVectorizationCostModel::collectValuesToIgnore() {
   // Ignore ephemeral values.
   CodeMetrics::collectEphemeralValues(TheLoop, AC, ValuesToIgnore);
@@ -7782,6 +7844,7 @@
   LoopVectorizationCostModel CM(L, PSE, LI, &LVL, *TTI, TLI, DB, AC, ORE, F,
                                 &Hints);
   CM.collectValuesToIgnore();
+  CM.collectLikelyLSRed();
 
   // Use the planner for vectorization.
   LoopVectorizationPlanner LVP(CM);