Index: include/llvm/Analysis/LoopInfo.h
===================================================================
--- include/llvm/Analysis/LoopInfo.h
+++ include/llvm/Analysis/LoopInfo.h
@@ -412,7 +412,10 @@
   bool isLCSSAForm(DominatorTree &DT) const;
 
   /// Return true if this Loop and all inner subloops are in LCSSA form.
-  bool isRecursivelyLCSSAForm(DominatorTree &DT) const;
+  /// When 'LI' is null this function has quadratic complexity on the number
+  /// of loop blocks. Linear algorithm is used otherwise.
+  bool isRecursivelyLCSSAForm(DominatorTree &DT,
+                              const LoopInfo *LI = nullptr) const;
 
   /// Return true if the Loop is in the form that the LoopSimplify form
   /// transforms loops to, which is sometimes called normal form.
Index: lib/Analysis/LoopInfo.cpp
===================================================================
--- lib/Analysis/LoopInfo.cpp
+++ lib/Analysis/LoopInfo.cpp
@@ -143,8 +143,14 @@
   return nullptr;
 }
 
-bool Loop::isLCSSAForm(DominatorTree &DT) const {
-  for (BasicBlock *BB : this->blocks()) {
+// Return true if the Loop is in LCSSA form.
+// When 'LI' is non-null we only check blocks located directly inside 'L' and
+// not in one of it's sub-loops.
+// This functionality is used in 'isRecursivelyLCSSAForm' to prevent us
+// from re-checking basic blocks from the nested loops.
+static bool isLCSSAFormImpl(const Loop &L, DominatorTree &DT,
+                            const LoopInfo *LI) {
+  for (BasicBlock *BB : L.blocks()) {
     for (Instruction &I : *BB) {
       // Tokens can't be used in PHI nodes and live-out tokens prevent loop
       // optimizations, so for the purposes of considered LCSSA form, we
@@ -152,6 +158,10 @@
       if (I.getType()->isTokenTy())
         continue;
 
+      // Only visit blocks located directly inside the current loop
+      if (LI && LI->getLoopFor(BB) != &L)
+        continue;
+
       for (Use &U : I.uses()) {
         Instruction *UI = cast<Instruction>(U.getUser());
         BasicBlock *UserBB = UI->getParent();
@@ -163,7 +173,7 @@
         // block they are defined in.  Also, blocks not reachable from the
         // entry are special; uses in them don't need to go through PHIs.
         if (UserBB != BB &&
-            !contains(UserBB) &&
+            !L.contains(UserBB) &&
             DT.isReachableFromEntry(UserBB))
           return false;
       }
@@ -173,12 +183,17 @@
   return true;
 }
 
-bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const {
-  if (!isLCSSAForm(DT))
+bool Loop::isLCSSAForm(DominatorTree &DT) const {
+  return isLCSSAFormImpl(*this, DT, nullptr);
+}
+
+bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT,
+                                  const LoopInfo *LI /* = nullptr */) const {
+  if (!isLCSSAFormImpl(*this, DT, LI))
     return false;
 
-  return all_of(*this,
-                [&](const Loop *L) { return L->isRecursivelyLCSSAForm(DT); });
+  return all_of(
+      *this, [&](const Loop *L) { return L->isRecursivelyLCSSAForm(DT, LI); });
 }
 
 bool Loop::isLoopSimplifyForm() const {
Index: lib/Transforms/Scalar/IndVarSimplify.cpp
===================================================================
--- lib/Transforms/Scalar/IndVarSimplify.cpp
+++ lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -506,7 +506,8 @@
 /// constant operands at the beginning of the loop.
 void IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
   // Check a pre-condition.
-  assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
+  assert(L->isRecursivelyLCSSAForm(*DT, LI) &&
+         "Indvars did not preserve LCSSA!");
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
@@ -2185,7 +2186,8 @@
 
 bool IndVarSimplify::run(Loop *L) {
   // We need (and expect!) the incoming loop to be in LCSSA.
-  assert(L->isRecursivelyLCSSAForm(*DT) && "LCSSA required to run indvars!");
+  assert(L->isRecursivelyLCSSAForm(*DT, LI) &&
+         "LCSSA required to run indvars!");
 
   // If LoopSimplify form is not available, stay out of trouble. Some notes:
   //  - LSR currently only supports LoopSimplify-form loops. Indvars'
@@ -2278,7 +2280,8 @@
   Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
 
   // Check a post-condition.
-  assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
+  assert(L->isRecursivelyLCSSAForm(*DT, LI) &&
+         "Indvars did not preserve LCSSA!");
 
   // Verify that LFTR, and any other change have not interfered with SCEV's
   // ability to compute trip count.
Index: lib/Transforms/Utils/LCSSA.cpp
===================================================================
--- lib/Transforms/Utils/LCSSA.cpp
+++ lib/Transforms/Utils/LCSSA.cpp
@@ -323,7 +323,8 @@
   bool runOnFunction(Function &F) override;
   void verifyAnalysis() const override {
     assert(
-        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); }) &&
+        all_of(*LI,
+               [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, LI); }) &&
         "LCSSA form is broken!");
   };
 
Index: lib/Transforms/Utils/LoopSimplify.cpp
===================================================================
--- lib/Transforms/Utils/LoopSimplify.cpp
+++ lib/Transforms/Utils/LoopSimplify.cpp
@@ -366,7 +366,7 @@
     // already be a use of an LCSSA phi node.
     formLCSSA(*L, *DT, LI, SE);
 
-    assert(NewOuter->isRecursivelyLCSSAForm(*DT) &&
+    assert(NewOuter->isRecursivelyLCSSAForm(*DT, LI) &&
            "LCSSA is broken after separating nested loops!");
   }
 
@@ -810,8 +810,8 @@
   if (PreserveLCSSA) {
     assert(DT && "DT not available.");
     assert(LI && "LI not available.");
-    bool InLCSSA =
-        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+    bool InLCSSA = all_of(
+        *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, LI); });
     assert(InLCSSA && "Requested to preserve LCSSA, but it's already broken.");
   }
 #endif
@@ -822,8 +822,8 @@
 
 #ifndef NDEBUG
   if (PreserveLCSSA) {
-    bool InLCSSA =
-        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+    bool InLCSSA = all_of(
+        *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, LI); });
     assert(InLCSSA && "LCSSA is broken after loop-simplify.");
   }
 #endif