diff --git a/llvm/include/llvm/ADT/GenericCycleImpl.h b/llvm/include/llvm/ADT/GenericCycleImpl.h
--- a/llvm/include/llvm/ADT/GenericCycleImpl.h
+++ b/llvm/include/llvm/ADT/GenericCycleImpl.h
@@ -144,8 +144,12 @@
 };
 
 template <typename ContextT>
-auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(
-    const BlockT *Block) const -> CycleT * {
+auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(BlockT *Block)
+    -> CycleT * {
+  auto Cycle = BlockMapTopLevel.find(Block);
+  if (Cycle != BlockMapTopLevel.end())
+    return Cycle->second;
+
   auto MapIt = BlockMap.find(Block);
   if (MapIt == BlockMap.end())
     return nullptr;
@@ -153,6 +157,7 @@
   auto *C = MapIt->second;
   while (C->ParentCycle)
     C = C->ParentCycle;
+  BlockMapTopLevel.try_emplace(Block, C);
   return C;
 }
 
@@ -169,6 +174,13 @@
   *Pos = std::move(CurrentContainer.back());
   CurrentContainer.pop_back();
   Child->ParentCycle = NewParent;
+
+  NewParent->Blocks.insert(NewParent->Blocks.end(), Child->block_begin(),
+                           Child->block_end());
+
+  for (auto &It : BlockMapTopLevel)
+    if (It.second == Child)
+      It.second = NewParent;
 }
 
 /// \brief Main function of the cycle info computations.
@@ -241,9 +253,6 @@
                      << Info.Context.print(BlockParent->getHeader()) << "\n");
           // Make BlockParent the child of NewCycle.
           Info.moveToNewParent(NewCycle.get(), BlockParent);
-          NewCycle->Blocks.insert(NewCycle->Blocks.end(),
-                                  BlockParent->block_begin(),
-                                  BlockParent->block_end());
 
           for (auto *ChildEntry : BlockParent->entries())
             ProcessPredecessors(ChildEntry);
@@ -257,6 +266,7 @@
         assert(!is_contained(NewCycle->Blocks, Block));
         NewCycle->Blocks.push_back(Block);
         ProcessPredecessors(Block);
+        Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
       }
     } while (!Worklist.empty());
 
@@ -336,6 +346,7 @@
 template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
   TopLevelCycles.clear();
   BlockMap.clear();
+  BlockMapTopLevel.clear();
 }
 
 /// \brief Compute the cycle info for a function.
diff --git a/llvm/include/llvm/ADT/GenericCycleInfo.h b/llvm/include/llvm/ADT/GenericCycleInfo.h
--- a/llvm/include/llvm/ADT/GenericCycleInfo.h
+++ b/llvm/include/llvm/ADT/GenericCycleInfo.h
@@ -232,9 +232,12 @@
 private:
   ContextT Context;
 
-  /// Map basic blocks to their inner-most containing loop.
+  /// Map basic blocks to their inner-most containing cycle.
   DenseMap<BlockT *, CycleT *> BlockMap;
 
+  /// Map basic blocks to their top level containing cycle.
+  DenseMap<BlockT *, CycleT *> BlockMapTopLevel;
+
   /// Top-level cycles discovered by any DFS.
   ///
   /// Note: The implementation treats the nullptr as the parent of
@@ -254,12 +257,12 @@
 
   CycleT *getCycle(const BlockT *Block) const;
   unsigned getCycleDepth(const BlockT *Block) const;
-  CycleT *getTopLevelParentCycle(const BlockT *Block) const;
+  CycleT *getTopLevelParentCycle(BlockT *Block);
 
   /// Move \p Child to \p NewParent by manipulating Children vectors.
   ///
-  /// Note: This is an incomplete operation that does not update the
-  /// list of blocks in the new parent or the depth of the subtree.
+  /// Note: This is an incomplete operation that does not update the depth of
+  /// the subtree.
   void moveToNewParent(CycleT *NewParent, CycleT *Child);
 
   /// Methods for debug and self-test.