Index: include/llvm/ADT/SCCIterator.h
===================================================================
--- include/llvm/ADT/SCCIterator.h
+++ include/llvm/ADT/SCCIterator.h
@@ -26,6 +26,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
+#include <set>
 #include <vector>
 
 namespace llvm {
@@ -79,6 +80,8 @@
   /// node, the next child to visit, and the minimum uplink value of all child
   std::vector<StackElement> VisitStack;
 
+  std::set<NodeType *> *DontRevisitNodes;
+
   /// A single "visit" within the non-recursive DFS traversal.
   void DFSVisitOne(NodeType *N);
 
@@ -88,7 +91,8 @@
   /// Compute the next SCC using the DFS traversal.
   void GetNextSCC();
 
-  scc_iterator(NodeType *entryN) : visitNum(0) {
+  scc_iterator(NodeType *entryN, std::set<NodeType *> *DRN = nullptr) :
+      visitNum(0), DontRevisitNodes(DRN) {
     DFSVisitOne(entryN);
     GetNextSCC();
   }
@@ -97,8 +101,9 @@
   scc_iterator() {}
 
 public:
-  static scc_iterator begin(const GraphT &G) {
-    return scc_iterator(GT::getEntryNode(G));
+  static scc_iterator begin(const GraphT &G,
+                            std::set<NodeType *> *DontRevisitNodes = nullptr) {
+    return scc_iterator(GT::getEntryNode(G), DontRevisitNodes);
   }
   static scc_iterator end(const GraphT &) { return scc_iterator(); }
 
@@ -135,11 +140,19 @@
     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
     nodeVisitNumbers[New] = nodeVisitNumbers[Old];
     nodeVisitNumbers.erase(Old);
+    if (DontRevisitNodes && DontRevisitNodes->count(Old)) {
+      DontRevisitNodes->erase(Old);
+      DontRevisitNodes->insert(New);
+    }
   }
 };
 
 template <class GraphT, class GT>
 void scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) {
+  if (DontRevisitNodes && DontRevisitNodes->count(N))
+    return;
+  if (DontRevisitNodes)
+    DontRevisitNodes->insert(N);
   ++visitNum;
   nodeVisitNumbers[N] = visitNum;
   SCCNodeStack.push_back(N);
@@ -221,8 +234,12 @@
   }
 
 /// \brief Construct the begin iterator for a deduced graph type T.
-template <class T> scc_iterator<T> scc_begin(const T &G) {
-  return scc_iterator<T>::begin(G);
+// template <class T, class GT = GraphTraits<T>>
+template <class T>
+scc_iterator<T> scc_begin(
+    const T &G,
+    std::set<typename GraphTraits<T>::NodeType *> *DontRevisitNodes = nullptr) {
+  return scc_iterator<T>::begin(G, DontRevisitNodes);
 }
 
 /// \brief Construct the end iterator for a deduced graph type T.
@@ -231,8 +248,12 @@
 }
 
 /// \brief Construct the begin iterator for a deduced graph type T's Inverse<T>.
-template <class T> scc_iterator<Inverse<T> > scc_begin(const Inverse<T> &G) {
-  return scc_iterator<Inverse<T> >::begin(G);
+template <class T>
+scc_iterator<Inverse<T>> scc_begin(
+    const Inverse<T> &G,
+    std::set<typename GraphTraits<Inverse<T>>::NodeType *> *DontRevisitNodes =
+        nullptr) {
+  return scc_iterator<Inverse<T> >::begin(G, DontRevisitNodes);
 }
 
 /// \brief Construct the end iterator for a deduced graph type T's Inverse<T>.
Index: include/llvm/Support/DataFlow.h
===================================================================
--- include/llvm/Support/DataFlow.h
+++ include/llvm/Support/DataFlow.h
@@ -0,0 +1,104 @@
+//===-- llvm/Support/DataFlow.h - dataflow as graphs ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines specializations of GraphTraits that allows Use-Def and
+// Def-Use relations to be treated as proper graphs for generic algorithms.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_DATAFLOW_H
+#define LLVM_SUPPORT_DATAFLOW_H
+
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/ADT/GraphTraits.h"
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+// Provide specializations of GraphTraits to be able to treat def-use/use-def
+// chains as graphs
+
+template <> struct GraphTraits<const Value*> {
+  typedef const Value NodeType;
+  typedef Value::const_user_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(const Value *G) {
+    return G;
+  }
+
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->user_begin();
+  }
+
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->user_end();
+  }
+};
+
+template <> struct GraphTraits<Value*> {
+  typedef Value NodeType;
+  typedef Value::user_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Value *G) {
+    return G;
+  }
+
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->user_begin();
+  }
+
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->user_end();
+  }
+};
+
+template <> struct GraphTraits<Inverse<const User*> > {
+  typedef const Value NodeType;
+  typedef User::const_op_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Inverse<const User*> G) {
+    return G.Graph;
+  }
+
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    if (const User *U = dyn_cast<User>(N))
+      return U->op_begin();
+    return NULL;
+  }
+
+  static inline ChildIteratorType child_end(NodeType *N) {
+    if(const User *U = dyn_cast<User>(N))
+      return U->op_end();
+    return NULL;
+  }
+};
+
+template <> struct GraphTraits<Inverse<User*> > {
+  typedef Value NodeType;
+  typedef User::op_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Inverse<User*> G) {
+    return G.Graph;
+  }
+
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    if (User *U = dyn_cast<User>(N))
+      return U->op_begin();
+    return NULL;
+  }
+
+  static inline ChildIteratorType child_end(NodeType *N) {
+    if (User *U = dyn_cast<User>(N))
+      return U->op_end();
+    return NULL;
+  }
+};
+
+}
+#endif
Index: lib/Transforms/Vectorize/SLPVectorizer.cpp
===================================================================
--- lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -18,6 +18,7 @@
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
@@ -45,6 +46,7 @@
 #include "llvm/IR/Verifier.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/DataFlow.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Vectorize.h"
@@ -433,6 +435,10 @@
   /// \returns the cost of the vectorizable entry.
   int getEntryCost(TreeEntry *E);
 
+  /// Scan use-def dependence graph to find and mark all scalar instructions
+  /// that belong to the tree and lie on dependence cycles.
+  void markCyclicInstructions();
+
   /// This is the recursive part of buildTree.
   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth);
 
@@ -524,6 +530,12 @@
   /// A list of scalars that we found that we need to keep as scalars.
   ValueSet MustGather;
 
+  /// A list of scalars that we found lying on a dependence cycle.
+  ValueSet OnDependenceCycle;
+
+  /// A list of scalars that we already visited looking for cycles.
+  std::set<Value *> VisitedInstructions;
+
   /// This POD struct describes one external user in the vectorized tree.
   struct ExternalUser {
     ExternalUser (Value *S, llvm::User *U, int L) :
@@ -1000,6 +1012,24 @@
 }
 
 
+void BoUpSLP::markCyclicInstructions() {
+  DEBUG(dbgs() << "SLP: Marking cyclic instructions.\n");
+  ArrayRef<Value*> VL = VectorizableTree[0].Scalars;
+  for (unsigned i = 0, e = VL.size(); i != e; ++i) {
+    Inverse<User *> VLi = cast<User>(VL[i]);
+    DEBUG(dbgs() << "SLP: checking instruction (" << *VL[i] << ").\n");
+    for (scc_iterator<Inverse<User *>> I = scc_begin(VLi, &VisitedInstructions);
+         !I.isAtEnd(); ++I) {
+      const std::vector<Value *> &ValueSCC = *I;
+      for (auto Val : ValueSCC)
+        DEBUG(dbgs() << "SLP: in scc (" << *Val << ").\n");
+      if (ValueSCC.size() > 1)
+        OnDependenceCycle.insert(ValueSCC.begin(), ValueSCC.end());
+    }
+  }
+}
+
+
 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) {
   bool SameTy = getSameType(VL); (void)SameTy;
   bool isAltShuffle = false;
@@ -1797,10 +1827,20 @@
     return INT_MAX;
   }
 
+  markCyclicInstructions();
+
   unsigned BundleWidth = VectorizableTree[0].Scalars.size();
 
   for (TreeEntry &TE : VectorizableTree) {
     int C = getEntryCost(&TE);
+    if (C < 0 && !OnDependenceCycle.empty()) {
+      for (int Lane = 0, LE = TE.Scalars.size(); Lane != LE; ++Lane)
+        if (OnDependenceCycle.count(TE.Scalars[Lane])) {
+          DEBUG(dbgs() << "SLP: Instruction found to lie on cycle.\n");
+          C = 0;
+          break;
+        }
+    }
     DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with "
                  << *TE.Scalars[0] << ".\n");
     Cost += C;