diff --git a/llvm/include/llvm/ADT/BreadthFirstIterator.h b/llvm/include/llvm/ADT/BreadthFirstIterator.h
--- a/llvm/include/llvm/ADT/BreadthFirstIterator.h
+++ b/llvm/include/llvm/ADT/BreadthFirstIterator.h
@@ -50,7 +50,7 @@
   using value_type = typename GT::NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
-  using reference = value_type &;
+  using reference = const value_type &;
 
 private:
   using NodeRef = typename GT::NodeRef;
@@ -123,7 +123,7 @@
 
   bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
 
-  const NodeRef &operator*() const { return VisitQueue.front()->first; }
+  reference operator*() const { return VisitQueue.front()->first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time so that you can actually call methods on the node, because the
diff --git a/llvm/include/llvm/ADT/DepthFirstIterator.h b/llvm/include/llvm/ADT/DepthFirstIterator.h
--- a/llvm/include/llvm/ADT/DepthFirstIterator.h
+++ b/llvm/include/llvm/ADT/DepthFirstIterator.h
@@ -88,7 +88,7 @@
   using value_type = typename GT::NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
-  using reference = value_type &;
+  using reference = const value_type &;
 
 private:
   using NodeRef = typename GT::NodeRef;
@@ -165,7 +165,7 @@
   }
   bool operator!=(const df_iterator &x) const { return !(*this == x); }
 
-  const NodeRef &operator*() const { return VisitStack.back().first; }
+  reference operator*() const { return VisitStack.back().first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the Node, because
diff --git a/llvm/include/llvm/ADT/PostOrderIterator.h b/llvm/include/llvm/ADT/PostOrderIterator.h
--- a/llvm/include/llvm/ADT/PostOrderIterator.h
+++ b/llvm/include/llvm/ADT/PostOrderIterator.h
@@ -100,7 +100,7 @@
   using value_type = typename GT::NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
-  using reference = value_type &;
+  using reference = const value_type &;
 
 private:
   using NodeRef = typename GT::NodeRef;
@@ -161,7 +161,7 @@
   }
   bool operator!=(const po_iterator &x) const { return !(*this == x); }
 
-  const NodeRef &operator*() const { return std::get<0>(VisitStack.back()); }
+  reference operator*() const { return std::get<0>(VisitStack.back()); }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the BasicBlock, because
diff --git a/llvm/unittests/ADT/BreadthFirstIteratorTest.cpp b/llvm/unittests/ADT/BreadthFirstIteratorTest.cpp
--- a/llvm/unittests/ADT/BreadthFirstIteratorTest.cpp
+++ b/llvm/unittests/ADT/BreadthFirstIteratorTest.cpp
@@ -70,4 +70,8 @@
   EXPECT_EQ(It, End);
 }
 
+static_assert(
+    std::is_convertible_v<decltype(*std::declval<bf_iterator<Graph<3>>>()),
+                          typename bf_iterator<Graph<3>>::reference>);
+
 } // end namespace llvm
diff --git a/llvm/unittests/ADT/DepthFirstIteratorTest.cpp b/llvm/unittests/ADT/DepthFirstIteratorTest.cpp
--- a/llvm/unittests/ADT/DepthFirstIteratorTest.cpp
+++ b/llvm/unittests/ADT/DepthFirstIteratorTest.cpp
@@ -50,4 +50,9 @@
 
   EXPECT_EQ(3, S.InsertVisited);
 }
+
+static_assert(
+    std::is_convertible_v<decltype(*std::declval<df_iterator<Graph<3>>>()),
+                          typename df_iterator<Graph<3>>::reference>);
+
 }
diff --git a/llvm/unittests/ADT/PostOrderIteratorTest.cpp b/llvm/unittests/ADT/PostOrderIteratorTest.cpp
--- a/llvm/unittests/ADT/PostOrderIteratorTest.cpp
+++ b/llvm/unittests/ADT/PostOrderIteratorTest.cpp
@@ -36,6 +36,10 @@
   PIExt.insertEdge(std::optional<BasicBlock *>(), NullBB);
 }
 
+static_assert(
+    std::is_convertible_v<decltype(*std::declval<po_iterator<Graph<3>>>()),
+                          typename po_iterator<Graph<3>>::reference>);
+
 // Test post-order and reverse post-order traversals for simple graph type.
 TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) {
   Graph<6> G;