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
@@ -177,8 +177,7 @@
   CurrentContainer.pop_back();
   Child->ParentCycle = NewParent;
 
-  NewParent->Blocks.insert(NewParent->Blocks.end(), Child->block_begin(),
-                           Child->block_end());
+  NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
 
   for (auto &It : BlockMapTopLevel)
     if (It.second == Child)
@@ -266,7 +265,7 @@
       } else {
         Info.BlockMap.try_emplace(Block, NewCycle.get());
         assert(!is_contained(NewCycle->Blocks, Block));
-        NewCycle->Blocks.push_back(Block);
+        NewCycle->Blocks.insert(Block);
         ProcessPredecessors(Block);
         Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
       }
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
@@ -32,6 +32,8 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/GenericSSAContext.h"
 #include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/Support/Debug.h"
@@ -67,7 +69,9 @@
 
   /// Basic blocks that are contained in the cycle, including entry blocks,
   /// and including blocks that are part of a child cycle.
-  std::vector<BlockT *> Blocks;
+  using BlockSetVectorT =
+      SetVector<BlockT *, std::vector<BlockT *>, SmallPtrSet<BlockT *, 8>>;
+  BlockSetVectorT Blocks;
 
   /// Depth of the cycle in the tree. The root "cycle" is at depth 0.
   ///
@@ -85,7 +89,7 @@
   }
 
   void appendEntry(BlockT *Block) { Entries.push_back(Block); }
-  void appendBlock(BlockT *Block) { Blocks.push_back(Block); }
+  void appendBlock(BlockT *Block) { Blocks.insert(Block); }
 
   GenericCycle(const GenericCycle &) = delete;
   GenericCycle &operator=(const GenericCycle &) = delete;
@@ -111,7 +115,10 @@
 
   /// \brief Return whether \p Block is contained in the cycle.
   bool contains(const BlockT *Block) const {
-    return is_contained(Blocks, Block);
+    // We are forced to do a const_cast because our key_type is a pointer, and
+    // the "const" qualifier in SetVector::contains(const key_type&) gets
+    // applied to the wrong part of the type.
+    return Blocks.contains(const_cast<BlockT *>(Block));
   }
 
   /// \brief Returns true iff this cycle contains \p C.
@@ -171,7 +178,7 @@
 
   /// Iteration over blocks in the cycle (including entry blocks).
   //@{
-  using const_block_iterator = typename std::vector<BlockT *>::const_iterator;
+  using const_block_iterator = typename BlockSetVectorT::const_iterator;
 
   const_block_iterator block_begin() const {
     return const_block_iterator{Blocks.begin()};