Index: lib/Transforms/Vectorize/LoopVectorize.cpp
===================================================================
--- lib/Transforms/Vectorize/LoopVectorize.cpp
+++ lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -292,24 +292,6 @@
 
 } // end anonymous namespace
 
-/// Returns true if the given loop body has a cycle, excluding the loop
-/// itself.
-static bool hasCyclesInLoopBody(const Loop &L) {
-  if (!L.empty())
-    return true;
-
-  for (const auto &SCC :
-       make_range(scc_iterator<Loop, LoopBodyTraits>::begin(L),
-                  scc_iterator<Loop, LoopBodyTraits>::end(L))) {
-    if (SCC.size() > 1) {
-      DEBUG(dbgs() << "LVL: Detected a cycle in the loop body:\n");
-      DEBUG(L.dump());
-      return true;
-    }
-  }
-  return false;
-}
-
 /// A helper function for converting Scalar types to vector types.
 /// If the incoming type is void, we return void. If the VF is 1, we return
 /// the scalar type.
@@ -2443,14 +2425,53 @@
 
 } // end anonymous namespace
 
-static void addAcyclicInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) {
+/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to LI.
+/// I.e., check if there exists a loop that contains SrcBB and where DestBB is
+/// the loop header. This code was borrowed from the Machine-specific version in
+/// lib/CodeGen/ShrinkWrap.cpp
+static bool isProperBackedge(LoopInfo *LI, BasicBlock *SrcBB,
+                             BasicBlock *DestBB) {
+  for (Loop *Loop = LI->getLoopFor(SrcBB); Loop; Loop = Loop->getParentLoop()) {
+    if (Loop->getHeader() == DestBB)
+      return true;
+  }
+
+  return false;
+}
+
+/// Check whether the CFG of \p Lp is irreducible. This code was borrowed from
+/// the Machine-specific version in lib/CodeGen/ShrinkWrap.cpp.
+static bool isIrreducibleCFG(Loop *Lp, LoopInfo *LI) {
+  LoopBlocksDFS DFS(Lp);
+  DFS.perform(LI);
+  SmallPtrSet<const BasicBlock *, 32> VisitedBB;
+
+  for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
+    VisitedBB.insert(BB);
+    for (BasicBlock *SuccBB : BB->getTerminator()->successors()) {
+      // SuccBB hasn't been visited yet
+      if (!VisitedBB.count(SuccBB))
+        continue;
+      // We already visited SuccBB, thus BB->SuccBB must be a backedge.
+      // Check that the head matches what we have in the loop information.
+      // Otherwise, we have an irreducible graph.
+      if (!isProperBackedge(LI, BB, SuccBB))
+        return true;
+    }
+  }
+
+  return false;
+}
+
+static void addAcyclicInnerLoop(Loop &L, LoopInfo *LI,
+                                SmallVectorImpl<Loop *> &V) {
   if (L.empty()) {
-    if (!hasCyclesInLoopBody(L))
+    if (!isIrreducibleCFG(&L, LI))
       V.push_back(&L);
     return;
   }
   for (Loop *InnerL : L)
-    addAcyclicInnerLoop(*InnerL, V);
+    addAcyclicInnerLoop(*InnerL, LI, V);
 }
 
 namespace {
@@ -8992,7 +9013,7 @@
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *L : *LI)
-    addAcyclicInnerLoop(*L, Worklist);
+    addAcyclicInnerLoop(*L, LI, Worklist);
 
   LoopsAnalyzed += Worklist.size();