diff --git a/llvm/include/llvm/Analysis/LoopNestAnalysis.h b/llvm/include/llvm/Analysis/LoopNestAnalysis.h
--- a/llvm/include/llvm/Analysis/LoopNestAnalysis.h
+++ b/llvm/include/llvm/Analysis/LoopNestAnalysis.h
@@ -146,6 +146,17 @@
 
   StringRef getName() const { return Loops.front()->getName(); }
 
+  /// Interchange two loops. The outer loop is specified by \p OuterLoopId while
+  /// the inner loop is specified by \p InnerLoopId. Interchange is only allowed
+  /// for nested loops pair, that is, the inner loop should be the only subloop
+  /// of the outer loop.
+  void interchangeNestedLoops(unsigned OuterLoopId, unsigned InnerLoopId) {
+    assert((Loops[InnerLoopId]->getParentLoop() == Loops[OuterLoopId] &&
+            Loops[OuterLoopId]->getSubLoops().size() == 1) &&
+           "Loops that are interchanged should be nested.");
+    std::swap(Loops[OuterLoopId], Loops[InnerLoopId]);
+  }
+
 protected:
   const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
   LoopVectorTy Loops; // the loops in the nest (in breadth first order).
diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
--- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
@@ -86,7 +86,7 @@
 #endif
 
 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
-                                     Loop *L, DependenceInfo *DI) {
+                                     const Loop *L, DependenceInfo *DI) {
   using ValueVector = SmallVector<Value *, 16>;
 
   ValueVector MemInstr;
@@ -269,28 +269,6 @@
   return true;
 }
 
-static LoopVector populateWorklist(Loop &L) {
-  LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
-                    << L.getHeader()->getParent()->getName() << " Loop: %"
-                    << L.getHeader()->getName() << '\n');
-  LoopVector LoopList;
-  Loop *CurrentLoop = &L;
-  const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
-  while (!Vec->empty()) {
-    // The current loop has multiple subloops in it hence it is not tightly
-    // nested.
-    // Discard all loops above it added into Worklist.
-    if (Vec->size() != 1)
-      return {};
-
-    LoopList.push_back(CurrentLoop);
-    CurrentLoop = Vec->front();
-    Vec = &CurrentLoop->getSubLoops();
-  }
-  LoopList.push_back(CurrentLoop);
-  return LoopList;
-}
-
 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
   PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
   if (InnerIndexVar)
@@ -438,23 +416,16 @@
                   DominatorTree *DT, OptimizationRemarkEmitter *ORE)
       : SE(SE), LI(LI), DI(DI), DT(DT), ORE(ORE) {}
 
-  bool run(Loop *L) {
-    if (L->getParentLoop())
-      return false;
-
-    return processLoopList(populateWorklist(*L));
-  }
-
   bool run(LoopNest &LN) {
     const auto &LoopList = LN.getLoops();
     for (unsigned I = 1; I < LoopList.size(); ++I)
       if (LoopList[I]->getParentLoop() != LoopList[I - 1])
         return false;
-    return processLoopList(LoopList);
+    return processLoopNest(LN);
   }
 
-  bool isComputableLoopNest(ArrayRef<Loop *> LoopList) {
-    for (Loop *L : LoopList) {
+  bool isComputableLoopNest(LoopNest &LN) {
+    for (Loop *L : LN.getLoops()) {
       const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
       if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
         LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
@@ -472,15 +443,15 @@
     return true;
   }
 
-  unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
+  unsigned selectLoopForInterchange(LoopNest &LN) {
     // TODO: Add a better heuristic to select the loop to be interchanged based
     // on the dependence matrix. Currently we select the innermost loop.
-    return LoopList.size() - 1;
+    return LN.getNestDepth() - 1;
   }
 
-  bool processLoopList(ArrayRef<Loop *> LoopList) {
+  bool processLoopNest(LoopNest &LN) {
     bool Changed = false;
-    unsigned LoopNestDepth = LoopList.size();
+    unsigned LoopNestDepth = LN.getNestDepth();
     if (LoopNestDepth < 2) {
       LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
       return false;
@@ -490,7 +461,7 @@
                         << MaxLoopNestDepth << "\n");
       return false;
     }
-    if (!isComputableLoopNest(LoopList)) {
+    if (!isComputableLoopNest(LN)) {
       LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
       return false;
     }
@@ -499,9 +470,9 @@
                       << "\n");
 
     CharMatrix DependencyMatrix;
-    Loop *OuterMostLoop = *(LoopList.begin());
+    const Loop &OuterMostLoop = LN.getOutermostLoop();
     if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
-                                  OuterMostLoop, DI)) {
+                                  &OuterMostLoop, DI)) {
       LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
       return false;
     }
@@ -511,18 +482,17 @@
 #endif
 
     // Get the Outermost loop exit.
-    BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
+    BasicBlock *LoopNestExit = OuterMostLoop.getExitBlock();
     if (!LoopNestExit) {
       LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
       return false;
     }
 
-    unsigned SelecLoopId = selectLoopForInterchange(LoopList);
+    unsigned SelecLoopId = selectLoopForInterchange(LN);
     // Move the selected loop outwards to the best possible position.
-    Loop *LoopToBeInterchanged = LoopList[SelecLoopId];
     for (unsigned i = SelecLoopId; i > 0; i--) {
-      bool Interchanged = processLoop(LoopToBeInterchanged, LoopList[i - 1], i,
-                                      i - 1, LoopNestExit, DependencyMatrix);
+      bool Interchanged =
+          processLoop(LN, i, i - 1, LoopNestExit, DependencyMatrix);
       if (!Interchanged)
         return Changed;
       // Update the DependencyMatrix
@@ -531,16 +501,18 @@
       LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
       printDepMatrix(DependencyMatrix);
 #endif
-      Changed |= Interchanged;
+      Changed = true;
     }
     return Changed;
   }
 
-  bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
-                   unsigned OuterLoopId, BasicBlock *LoopNestExit,
+  bool processLoop(LoopNest &LN, unsigned InnerLoopId, unsigned OuterLoopId,
+                   BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
+    Loop *OuterLoop = LN.getLoop(OuterLoopId);
+    Loop *InnerLoop = LN.getLoop(InnerLoopId);
     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
@@ -560,6 +532,7 @@
              << "Loop interchanged with enclosing loop.";
     });
 
+    LN.interchangeNestedLoops(OuterLoopId, InnerLoopId);
     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
                                  LIL);
     LIT.transform();
@@ -1660,7 +1633,8 @@
     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 
-    return LoopInterchange(SE, LI, DI, DT, ORE).run(L);
+    std::unique_ptr<LoopNest> LN = LoopNest::getLoopNest(*L, *SE);
+    return LoopInterchange(SE, LI, DI, DT, ORE).run(*LN);
   }
 };
 
@@ -1689,5 +1663,7 @@
   OptimizationRemarkEmitter ORE(&F);
   if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(LN))
     return PreservedAnalyses::all();
-  return getLoopPassPreservedAnalyses();
+  auto PA = getLoopPassPreservedAnalyses();
+  PA.preserve<LoopNestAnalysis>();
+  return PA;
 }