Index: include/llvm/Analysis/LoopInfo.h
===================================================================
--- include/llvm/Analysis/LoopInfo.h
+++ include/llvm/Analysis/LoopInfo.h
@@ -136,6 +136,7 @@
   bool empty() const { return SubLoops.empty(); }
 
   /// Get a list of the basic blocks which make up this loop.
+  std::vector<BlockT *> &getBlocksVector() { return Blocks; }
   const std::vector<BlockT*> &getBlocks() const { return Blocks; }
   typedef typename std::vector<BlockT*>::const_iterator block_iterator;
   block_iterator block_begin() const { return Blocks.begin(); }
Index: lib/Transforms/Utils/LCSSA.cpp
===================================================================
--- lib/Transforms/Utils/LCSSA.cpp
+++ lib/Transforms/Utils/LCSSA.cpp
@@ -28,6 +28,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/LCSSA.h"
+#include "llvm/ADT/BreadthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
@@ -66,6 +67,10 @@
   return is_contained(ExitBlocks, BB);
 }
 
+// Walk the dom in BFS order keeping track of levels doing numbering.
+DenseMap<BasicBlock *, std::pair<unsigned, unsigned>> RankMap;
+bool UseRankMap = false;
+
 /// For every instruction from the worklist, check to see if it has any uses
 /// that are outside the current loop.  If so, insert LCSSA PHI nodes and
 /// rewrite the uses.
@@ -138,6 +143,7 @@
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
     // value, and add them to the Phi's map.
     for (BasicBlock *ExitBB : ExitBlocks) {
+      // XXX We can probably avoid looking at exits here as well.
       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
         continue;
 
@@ -237,18 +243,6 @@
   return Changed;
 }
 
-/// Return true if the specified block dominates at least
-/// one of the blocks in the specified list.
-static bool
-blockDominatesAnExit(BasicBlock *BB,
-                     DominatorTree &DT,
-                     const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
-  DomTreeNode *DomNode = DT.getNode(BB);
-  return any_of(ExitBlocks, [&](BasicBlock *EB) {
-    return DT.dominates(DomNode, DT.getNode(EB));
-  });
-}
-
 bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
                      ScalarEvolution *SE) {
   bool Changed = false;
@@ -262,13 +256,35 @@
 
   SmallVector<Instruction *, 8> Worklist;
 
+  // Now sort the Loop basic blocks in domtree order.
+  auto LoopTrav = L.getBlocksVector();
+  std::sort(LoopTrav.begin(), LoopTrav.end(), [](BasicBlock *A, BasicBlock *B) {
+    return RankMap[A].first < RankMap[B].first;
+  });
+
+  std::vector<std::pair<BasicBlock *, unsigned>> ExitBBLevel;
+  for (auto *El : ExitBlocks) {
+    ExitBBLevel.push_back(std::make_pair(El, RankMap[El].second));
+  }
+
   // Look at all the instructions in the loop, checking to see if they have uses
   // outside the loop.  If so, put them into the worklist to rewrite those uses.
-  for (BasicBlock *BB : L.blocks()) {
-    // For large loops, avoid use-scanning by using dominance information:  In
-    // particular, if a block does not dominate any of the loop exits, then none
-    // of the values defined in the block could be used outside the loop.
-    if (!blockDominatesAnExit(BB, DT, ExitBlocks))
+  for (BasicBlock *BB : LoopTrav) {
+    bool DoesDominate = false;
+    DomTreeNode *DomNode = DT.getNode(BB);
+    unsigned NodeLevel = RankMap[BB].second;
+    auto ExitAboveMe = [&](std::pair<BasicBlock *, unsigned> A) {
+      return A.second > NodeLevel;
+    };
+    for (auto &BBB : make_filter_range(ExitBBLevel, ExitAboveMe)) {
+      BasicBlock *EBB = BBB.first;
+      if (DT.dominates(DomNode, DT.getNode(EBB))) {
+        DoesDominate = true;
+        break;
+      }
+    }
+
+    if (!DoesDominate)
       continue;
 
     for (Instruction &I : *BB) {
@@ -312,8 +328,19 @@
 static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT,
                                 ScalarEvolution *SE) {
   bool Changed = false;
+
+  UseRankMap = true;
+  RankMap.clear();
+  auto BFI = bf_begin(DT.getRootNode());
+  unsigned Rank = 0;
+  for (auto BFE = bf_end(DT.getRootNode()); BFI != BFE; ++BFI) {
+    BasicBlock *BB = BFI->getBlock();
+    RankMap[BB] = std::make_pair(Rank++, BFI.getLevel());
+  }
+
   for (auto &L : *LI)
     Changed |= formLCSSARecursively(*L, DT, LI, SE);
+  UseRankMap = false;
   return Changed;
 }