Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp
+++ lib/Transforms/Scalar/LICM.cpp
@@ -1542,21 +1542,17 @@
 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
                                                  AliasAnalysis *AA) {
   std::unique_ptr<AliasSetTracker> CurAST;
-  SmallVector<Loop *, 4> RecomputeLoops;
-  auto mergeLoop = [&CurAST](Loop *L) {
-    // Loop over the body of this loop, looking for calls, invokes, and stores.
-    for (BasicBlock *BB : L->blocks())
-      CurAST->add(*BB); // Incorporate the specified basic block
-  };
+  DenseSet<BasicBlock *> HandledBBs;
+
+  // Try to re-use cached info from sub loops.
   for (Loop *InnerL : L->getSubLoops()) {
     auto MapI = LoopToAliasSetMap.find(InnerL);
     // If the AST for this inner loop is missing it may have been merged into
     // some other loop's AST and then that loop unrolled, and so we need to
     // recompute it.
-    if (MapI == LoopToAliasSetMap.end()) {
-      RecomputeLoops.push_back(InnerL);
+    if (MapI == LoopToAliasSetMap.end())
       continue;
-    }
+
     std::unique_ptr<AliasSetTracker> InnerAST = std::move(MapI->second);
 
     if (CurAST) {
@@ -1568,16 +1564,17 @@
       CurAST = std::move(InnerAST);
     }
     LoopToAliasSetMap.erase(MapI);
+    // Inner loop has been handled, so no need to process its BBs again.
+    HandledBBs.insert(InnerL->block_begin(), InnerL->block_end());
   }
   if (!CurAST)
     CurAST = make_unique<AliasSetTracker>(*AA);
 
-  // Add everything from the sub loops that are no longer directly available.
-  for (Loop *InnerL : RecomputeLoops)
-    mergeLoop(InnerL);
-
-  // And merge in this loop.
-  mergeLoop(L);
+  // Loop over the body of this loop, looking for calls, invokes, and stores.
+  // Do not traverse already handled BBs.
+  for (BasicBlock *BB : L->blocks())
+    if (!HandledBBs.count(BB))
+      CurAST->add(*BB); // Incorporate the specified basic block
 
   return CurAST;
 }