Introduce iterator sentinel to make graph traversal implementation more efficient and cleaner

[rusyaev-roman]

Summary

As of C++17, for "range-based for loop" the types of the begin-expr and the end-expr do not have to be the same,
and in fact the type of the end-expr does not have to be an iterator. This makes it possible to delimit
a range by a predicate for graph traversal iterators. To be more specific, it's not necessary to comapre
two containers in order to check that an iterator is the end iterator.
For more information see https://en.cppreference.com/w/cpp/language/range-for#Notes

[rusyaev-roman]

Fix mlir build and rebase

[rusyaev-roman]

In sum, this change brings the following improvements for all graph traversal iterators that are used in 'range-based for loop':

• avoid creating an empty iterator (that holds containers inside) to compare with the end iterator
• make 'empty()' call explicit (instead of comparing two containers of iterators) when an iterator is compared with the end iterator

[mtrofin]

lgtm for the MLInlineAdvisor bit

[ygribov]

LGTM.

[dblaikie]

Direction seems pretty good - some of the details I'm fuzzy on. If there's easy ways to keep some of the existing syntax (like I see at least one loop that I think was querying the incremented iterator for "isAtEnd" - maybe that can be preserved initially) to reduce the number of places this patch has to touch, then incremental patches after this, and then removing the backcompat API?

llvm/include/llvm/ADT/BreadthFirstIterator.h

128–131

Generally any operator that can be a non-member should be a non-member (but can still be a friend) so there's equal conversion handling for LHS and RHS. Could you make these non-members? (maybe a separate patch to do the same to the existing op overloads, so the new ones don't look weird)

do you need the inverse operators too, so the sentinel can appear on either side of the comparison?

llvm/include/llvm/ADT/SCCIterator.h

49–50

does this need a value type too? (& then define the reference and pointer types relative to that)

152–162

I'm not quite following why this requires the proxy object - even after reading the comment above. It looks like this function is entirely in terms of the SCC object that's returned from operator* - so maybe this could be a free function, called with hasCycle(*some_iterator)?

165–170

I always forget in which cases you're allowed to return a proxy object from an iterator - I thought some iterator concepts (maybe random access is the level at which this kicks in?) that required something that amounts to "there has to be a real object that outlives the iterator"

Could you refresh my memory on that/on why proxy objects are acceptable for this iterator type? (where/how does this iterator declare what concept it models anyway, since this removed the facade helper?)

[lattner]

I haven't reviewed this in detail, but oh my I love LOVE LOVE this! llvm::scc_traversal(x) is so nice, great work!

[rusyaev-roman]

First of all, thank you for your feedback! I've tried to address all your comments.

llvm/include/llvm/ADT/BreadthFirstIterator.h

128–131

Absolutely agree with all your points!

But I didn't want to make the code inconsistent and complicated in this patch. So, I suggest making all these operators 'friend' in a separate patch, otherwise it can lead to some boilerplate code like this:

friend bool operator==(const scc_iterator &SCCI, iterator_sentinel) {
  return SCCI.isAtEnd();
}

friend bool operator==(iterator_sentinel IS, const scc_iterator &SCCI) {
  return SCCI == IS;
}

friend bool operator!=(const scc_iterator &SCCI, iterator_sentinel IS) {
  return !(SCCI == IS);
}

friend bool operator!=(const scc_iterator &SCCI, iterator_sentinel IS) {
  return !(IS == SCCI);
}

This boilerplate code can be avoided using special helper classes, but I wouldn't like to implement them in this patch in order to keep it simple.

What do you think?

llvm/include/llvm/ADT/SCCIterator.h

49–50

Thanks, good point! I forgot to add additional types and member functions to satisfy forward iterator requirements when I removed iterator_facade base class. I'll update the patch (maybe get iterator_facade back)

152–162

maybe this could be a free function, called with hasCycle(*some_iterator)?

This was my initial intention.

But in the case of free function (or maybe static function of scc_iterator class) a user should write the following code:

for (const auto& SCC : scc_traversal(Graph))
  if (hasCycle<decltype(Graph)>(SCC)) // or in more complicated case when GraphTraits cannot be deduced from Graph type -- hasCycle<decltype(Graph), SubtGraphTraits>(SCC))
     ...

This is the main reason of SCCProxy introduction -- to make it possible to write like this:

for (const auto& SCC : scc_traversal(Graph))
  if (SCC.hasCycle())
     ...

165–170

A proxy object is allowed to be returned while dereferencing an input iterator (https://en.cppreference.com/w/cpp/named_req/InputIterator#Notes)

The reference type for an input iterator that is not also a LegacyForwardIterator does not have to be a reference type: dereferencing an input iterator may return a proxy object or value_type itself by value

For our case (that's forward iterator) we need to satisfy the following thing:

 The type std::iterator_traits<It>::reference must be exactly 
   ...
   * const T& otherwise (It is constant), 

(where T is the type denoted by std::iterator_traits<It>::value_type)

I'll also update the patch according to this point. Other things are ok for using a proxy object.

[dblaikie]

llvm/include/llvm/ADT/BreadthFirstIterator.h

128–131

Sure sure - before or after's fine by me.

llvm/include/llvm/ADT/SCCIterator.h

152–162

Ooh, it's the graph traits that's the extra (type) parameter. Makes sense.

Yeah, if this is workable while meeting the iterator requirements/proxy discussion elsewhere, sounds good.

165–170

Thanks for doing the legwork/quotations there.

so what's the solution here, if we're going to meet the forward iterator requirements but want a proxy object?

[dexonsmith]

llvm/include/llvm/ADT/SCCIterator.h

165–170

IIRC, one solution is to store a proxy object inside the iterator, make using value_type = ProxyT, update what the stored proxy points at on operator*(), and return ProxyT& when dereferencing. But maybe I'm misremembering. (I'm pretty sure iterator_facade_base has machinery to help with this stuff, either way; might be worth looking at other uses of it.)

[rusyaev-roman]

For a while I will be in a place where the Internet does not work well. I'll finish the patch when I come back.

[rusyaev-roman]

llvm/include/llvm/ADT/SCCIterator.h

165–170

so what's the solution here, if we're going to meet the forward iterator requirements but want a proxy object?

We need to modify the code according to the above comment. I'm highlighting it below. (maybe, I was not clear. Sorry for this. @dexonsmith has provided more detailed explanation)

For our case (that's forward iterator) we need to satisfy the following thing:

 The type std::iterator_traits<It>::reference must be exactly 
   ...
   * const T& otherwise (It is constant), 

(where T is the type denoted by std::iterator_traits<It>::value_type)

I'll also update the patch according to this point. Other things are ok for using a proxy object.

[craig.topper]

llvm/include/llvm/ADT/iterator_range.h

50

"based-range" should be "range-based" shouldn't it?

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

 void NoRecursionCheck::check(const MatchFinder::MatchResult &Result) {
   // Build call graph for the entire translation unit.
   const auto *TU = Result.Nodes.getNodeAs<TranslationUnitDecl>("TUDecl");
   CallGraph CG;
   CG.addToCallGraph(const_cast<TranslationUnitDecl *>(TU));
 
   // Look for cycles in call graph,
   // by looking for Strongly Connected Components (SCC's)
-  for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
-                                       SCCE = llvm::scc_end(&CG);
-       SCCI != SCCE; ++SCCI) {
-    if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.
+  for (auto SCC : llvm::scc_traversal(&CG)) {
+    if (!SCC.hasCycle()) // We only care about cycles, not standalone nodes.
       continue;
-    handleSCC(*SCCI);
+    handleSCC(*SCC);
   }
 }
 
 } // namespace misc
 } // namespace tidy
 } // namespace clang

llvm/include/llvm/ADT/BreadthFirstIterator.h

 
 #ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H
 #define LLVM_ADT_BREADTHFIRSTITERATOR_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include <iterator>
 #include <queue>
 #include <utility>
 
 namespace llvm {
 
 // bf_iterator_storage - A private class which is used to figure out where to
public:
   static bf_iterator end(const GraphT &G) { return bf_iterator(); }
 
   bool operator==(const bf_iterator &RHS) const {
     return VisitQueue == RHS.VisitQueue;
   }
 
   bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
 
+  bool operator==(iterator_sentinel) const { return VisitQueue.empty(); }
+
+  bool operator!=(iterator_sentinel RHS) const { return !(*this == RHS); }
+
   const NodeRef &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
   // contained type is a pointer.
   NodeRef operator->() const { return **this; }
 
   bf_iterator &operator++() { // Pre-increment
template <class T> bf_iterator<T> bf_begin(const T &G) {
   return bf_iterator<T>::begin(G);
 }
 
 template <class T> bf_iterator<T> bf_end(const T &G) {
   return bf_iterator<T>::end(G);
 }
 
 // Provide an accessor method to use them in range-based patterns.
-template <class T> iterator_range<bf_iterator<T>> breadth_first(const T &G) {
-  return make_range(bf_begin(G), bf_end(G));
+template <class T>
+iterator_range_with_sentinel<bf_iterator<T>> breadth_first(const T &G) {
+  return make_range_with_sentinel(bf_begin(G));
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_BREADTHFIRSTITERATOR_H

llvm/include/llvm/ADT/DepthFirstIterator.h

public:
   }
   static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
 
   bool operator==(const df_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   bool operator!=(const df_iterator &x) const { return !(*this == x); }
 
+  bool operator==(iterator_sentinel) const { return VisitStack.empty(); }
+  bool operator!=(iterator_sentinel x) const { return !(*this == x); }
+
   const NodeRef &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
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
   NodeRef operator->() const { return **this; }
 

 }
 
 template <class T, class SetTy>
 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
   return df_ext_iterator<T, SetTy>::end(G, S);
 }
 
 template <class T, class SetTy>
-iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
-                                                          SetTy &S) {
-  return make_range(df_ext_begin(G, S), df_ext_end(G, S));
+iterator_range_with_sentinel<df_ext_iterator<T, SetTy>>
+depth_first_ext(const T &G, SetTy &S) {
+  return make_range_with_sentinel(df_ext_begin(G, S));
 }
 
 // Provide global definitions of inverse depth first iterators...
 template <class T,
           class SetTy =
               df_iterator_default_set<typename GraphTraits<T>::NodeRef>,
           bool External = false>
 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
     : df_iterator<Inverse<T>, SetTy, External>(V) {}
 };
 
 template <class T>
 idf_iterator<T> idf_begin(const T& G) {
   return idf_iterator<T>::begin(Inverse<T>(G));
 }
 
 template <class T>
 idf_iterator<T> idf_end(const T& G){
   return idf_iterator<T>::end(Inverse<T>(G));
 }
 
 // Provide an accessor method to use them in range-based patterns.
 template <class T>
-iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
-  return make_range(idf_begin(G), idf_end(G));
+iterator_range_with_sentinel<idf_iterator<T>> inverse_depth_first(const T &G) {
+  return make_range_with_sentinel(idf_begin(G));
 }
 
 // Provide global definitions of external inverse depth first iterators...
 template <class T, class SetTy = df_iterator_default_set<typename GraphTraits<T>::NodeRef>>
 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
     : idf_iterator<T, SetTy, true>(V) {}
   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
     : idf_iterator<T, SetTy, true>(V) {}
 };
 
 template <class T, class SetTy>
 idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) {
   return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S);
 }
 
 template <class T, class SetTy>
 idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
   return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
 }
 
 template <class T, class SetTy>
-iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G,
-                                                                   SetTy &S) {
-  return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
+iterator_range_with_sentinel<idf_ext_iterator<T, SetTy>>
+inverse_depth_first_ext(const T &G, SetTy &S) {
+  return make_range_with_sentinel(idf_ext_begin(G, S));
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H

llvm/include/llvm/ADT/PostOrderIterator.h

public:
   }
   static po_iterator end(const GraphT &G, SetType &S) { return po_iterator(S); }
 
   bool operator==(const po_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   bool operator!=(const po_iterator &x) const { return !(*this == x); }
 
+  bool operator==(iterator_sentinel) const { return VisitStack.empty(); }
+  bool operator!=(iterator_sentinel x) const { return !(*this == x); }
+
   const NodeRef &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 BasicBlock, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
   NodeRef operator->() const { return **this; }
 

 
 // Provide global constructors that automatically figure out correct types...
 //
 template <class T>
 po_iterator<T> po_begin(const T &G) { return po_iterator<T>::begin(G); }
 template <class T>
 po_iterator<T> po_end  (const T &G) { return po_iterator<T>::end(G); }
 
-template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
-  return make_range(po_begin(G), po_end(G));
+template <typename T>
+iterator_range_with_sentinel<po_iterator<T>> post_order(const T &G) {
+  return make_range_with_sentinel(po_begin(G));
 }
 
 // Provide global definitions of external postorder iterators...
 template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
 struct po_ext_iterator : public po_iterator<T, SetType, true> {
   po_ext_iterator(const po_iterator<T, SetType, true> &V) :
   po_iterator<T, SetType, true>(V) {}
 };
 
 template<class T, class SetType>
 po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
   return po_ext_iterator<T, SetType>::begin(G, S);
 }
 
 template<class T, class SetType>
 po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
   return po_ext_iterator<T, SetType>::end(G, S);
 }
 
 template <class T, class SetType>
-iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) {
-  return make_range(po_ext_begin(G, S), po_ext_end(G, S));
+iterator_range_with_sentinel<po_ext_iterator<T, SetType>>
+post_order_ext(const T &G, SetType &S) {
+  return make_range_with_sentinel(po_ext_begin(G, S));
 }
 
 // Provide global definitions of inverse post order iterators...
 template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>,
           bool External = false>
 struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External> {
   ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
      po_iterator<Inverse<T>, SetType, External> (V) {}
 };
 
 template <class T>
 ipo_iterator<T> ipo_begin(const T &G) {
   return ipo_iterator<T>::begin(G);
 }
 
 template <class T>
 ipo_iterator<T> ipo_end(const T &G){
   return ipo_iterator<T>::end(G);
 }
 
 template <class T>
-iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) {
-  return make_range(ipo_begin(G), ipo_end(G));
+iterator_range_with_sentinel<ipo_iterator<T>> inverse_post_order(const T &G) {
+  return make_range_with_sentinel(ipo_begin(G));
 }
 
 // Provide global definitions of external inverse postorder iterators...
 template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
 struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
   ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
     ipo_iterator<T, SetType, true>(V) {}
   ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
     ipo_iterator<T, SetType, true>(V) {}
 };
 
 template <class T, class SetType>
 ipo_ext_iterator<T, SetType> ipo_ext_begin(const T &G, SetType &S) {
   return ipo_ext_iterator<T, SetType>::begin(G, S);
 }
 
 template <class T, class SetType>
 ipo_ext_iterator<T, SetType> ipo_ext_end(const T &G, SetType &S) {
   return ipo_ext_iterator<T, SetType>::end(G, S);
 }
 
 template <class T, class SetType>
-iterator_range<ipo_ext_iterator<T, SetType>>
+iterator_range_with_sentinel<ipo_ext_iterator<T, SetType>>
 inverse_post_order_ext(const T &G, SetType &S) {
-  return make_range(ipo_ext_begin(G, S), ipo_ext_end(G, S));
+  return make_range_with_sentinel(ipo_ext_begin(G, S));
 }
 
 //===--------------------------------------------------------------------===//
 // Reverse Post Order CFG iterator code
 //===--------------------------------------------------------------------===//
 //
 // This is used to visit basic blocks in a method in reverse post order.  This
 // class is awkward to use because I don't know a good incremental algorithm to

llvm/include/llvm/ADT/SCCIterator.h

 namespace llvm {
 
 /// Enumerate the SCCs of a directed graph in reverse topological order
 /// of the SCC DAG.
 ///
 /// This is implemented using Tarjan's DFS algorithm using an internal stack to
 /// build up a vector of nodes in a particular SCC. Note that it is a forward
 /// iterator and thus you cannot backtrack or re-visit nodes.
-template <class GraphT, class GT = GraphTraits<GraphT>>
-class scc_iterator : public iterator_facade_base<
-                         scc_iterator<GraphT, GT>, std::forward_iterator_tag,
-                         const std::vector<typename GT::NodeRef>, ptrdiff_t> {
+template <class GraphT, class GT = GraphTraits<GraphT>> class scc_iterator {
   using NodeRef = typename GT::NodeRef;
   using ChildItTy = typename GT::ChildIteratorType;
   using SccTy = std::vector<NodeRef>;
-  using reference = typename scc_iterator::reference;
+  using reference = const SccTy &;
+  using pointer = const SccTy *;
 
   /// Element of VisitStack during DFS.
   struct StackElement {
     NodeRef Node;         ///< The current node pointer.
     ChildItTy NextChild;  ///< The next child, modified inplace during DFS.
     unsigned MinVisited;  ///< Minimum uplink value of all children of Node.
 
     StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
bool isAtEnd() const {
     assert(!CurrentSCC.empty() || VisitStack.empty());
     return CurrentSCC.empty();
   }
 
   bool operator==(const scc_iterator &x) const {
     return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
   }
 
+  bool operator!=(const scc_iterator &x) const { return !(*this == x); }
+
+  bool operator==(iterator_sentinel) const { return isAtEnd(); }
+
+  bool operator!=(iterator_sentinel RHS) const { return !(*this == RHS); }
+
   scc_iterator &operator++() {
     GetNextSCC();
     return *this;
   }
 
-  reference operator*() const {
+  /// A proxy object that is returned from scc_iterator operator* and operator->
+  /// member functions. It allows performing implicit conversion to SccTy and
+  /// provides operator* and operator-> member functions to access underlying
+  /// object with SccTy type. This class is necessary to provide additional
+  /// functionality (e.g. hasCycle) that cannot be provided by SccTy object.
+  class SCCProxy {
+    friend scc_iterator;
+
+    reference SCC;
+
+    SCCProxy(reference SCC) : SCC(SCC) {}
+
+  public:
+    operator reference() const { return SCC; }
+
+    reference operator*() const { return SCC; }
+    pointer operator->() const { return &SCC; }
+
+    /// Test if the current SCC has a cycle.
+    ///
+    /// If the SCC has more than one node, this is trivially true.  If not, it
+    /// may still contain a cycle if the node has an edge back to itself.
+    bool hasCycle() const {
+      assert(!SCC.empty() && "Dereferencing END SCC iterator!");
+      if (SCC.size() > 1)
+        return true;
+      NodeRef N = SCC.front();
+      for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
+           ++CI)
+        if (*CI == N)
+          return true;
+      return false;
+    }
+  };
+
+  SCCProxy operator*() const {
     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     return CurrentSCC;
   }
 
-  /// Test if the current SCC has a cycle.
-  ///
-  /// If the SCC has more than one node, this is trivially true.  If not, it may
-  /// still contain a cycle if the node has an edge back to itself.
-  bool hasCycle() const;
+  SCCProxy operator->() const { return operator*(); }
 
   /// This informs the \c scc_iterator that the specified \c Old node
   /// has been deleted, and \c New is to be used in its place.
   void ReplaceNode(NodeRef Old, NodeRef New) {
     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
     // Do the assignment in two steps, in case 'New' is not yet in the map, and
     // inserting it causes the map to grow.
     auto tempVal = nodeVisitNumbers[Old];
do {
       CurrentSCC.push_back(SCCNodeStack.back());
       SCCNodeStack.pop_back();
       nodeVisitNumbers[CurrentSCC.back()] = ~0U;
     } while (CurrentSCC.back() != visitingN);
     return;
   }
 }
 
-template <class GraphT, class GT>
-bool scc_iterator<GraphT, GT>::hasCycle() const {
-    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
-    if (CurrentSCC.size() > 1)
-      return true;
-    NodeRef N = CurrentSCC.front();
-    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
-         ++CI)
-      if (*CI == N)
-        return true;
-    return false;
-  }
-
 /// Construct the begin iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_begin(const T &G) {
   return scc_iterator<T>::begin(G);
 }
 
 /// Construct the end iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_end(const T &G) {
   return scc_iterator<T>::end(G);
 }
 
+template <typename T>
+iterator_range_with_sentinel<scc_iterator<T>> scc_traversal(const T &G) {
+  return make_range_with_sentinel(scc_begin(G));
+}
+
 /// Sort the nodes of a directed SCC in the decreasing order of the edge
 /// weights. The instantiating GraphT type should have weighted edge type
 /// declared in its graph traits in order to use this iterator.
 ///
 /// This is implemented using Kruskal's minimal spanning tree algorithm followed
 /// by a BFS walk. First a maximum spanning tree (forest) is built based on all
 /// edges within the SCC collection. Then a BFS walk is initiated on tree nodes
 /// that do not have a predecessor. Finally, the BFS order computed is the

llvm/include/llvm/ADT/iterator_range.h

iterator_range(IteratorT begin_iterator, IteratorT end_iterator)
       : begin_iterator(std::move(begin_iterator)),
         end_iterator(std::move(end_iterator)) {}
 
   IteratorT begin() const { return begin_iterator; }
   IteratorT end() const { return end_iterator; }
   bool empty() const { return begin_iterator == end_iterator; }
 };
 
+/// As of C++17, the types of the begin-expr and the end-expr do not have to be
+/// the same in 'based-range for loop'. This class represents a tag that should
+/// be returned from the 'end' member function of an iterator.
+class iterator_sentinel {};
+
+/// A range adaptor for an iterator that wants iterator_sentinel as the
+/// end iterator. The iterator should provide operator!=(iterator_sentinel)
+/// function.
+template <typename IteratorT> class iterator_range_with_sentinel {
+  IteratorT begin_iterator;
+
+public:
+  explicit iterator_range_with_sentinel(IteratorT begin_iterator)
+      : begin_iterator(std::move(begin_iterator)) {}
+
+  IteratorT begin() const { return begin_iterator; }
+  iterator_sentinel end() const { return iterator_sentinel(); }
+};
+
 /// Convenience function for iterating over sub-ranges.
 ///
 /// This provides a bit of syntactic sugar to make using sub-ranges
 /// in for loops a bit easier. Analogous to std::make_pair().
 template <class T> iterator_range<T> make_range(T x, T y) {
   return iterator_range<T>(std::move(x), std::move(y));
 }
 
 template <typename T> iterator_range<T> make_range(std::pair<T, T> p) {
   return iterator_range<T>(std::move(p.first), std::move(p.second));
 }
 
+template <typename T>
+iterator_range_with_sentinel<T> make_range_with_sentinel(T begin) {
+  return iterator_range_with_sentinel<T>(std::move(begin));
+}
 }
 
 #endif

llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp

 
 iterator_range<std::list<LoopData>::iterator>
 BlockFrequencyInfoImplBase::analyzeIrreducible(
     const IrreducibleGraph &G, LoopData *OuterLoop,
     std::list<LoopData>::iterator Insert) {
   assert((OuterLoop == nullptr) == (Insert == Loops.begin()));
   auto Prev = OuterLoop ? std::prev(Insert) : Loops.end();
 
-  for (auto I = scc_begin(G); !I.isAtEnd(); ++I) {
-    if (I->size() < 2)
+  for (auto SCC : scc_traversal(G)) {
+    if (SCC->size() < 2)
       continue;
 
     // Translate the SCC into RPO.
-    createIrreducibleLoop(*this, G, OuterLoop, Insert, *I);
+    createIrreducibleLoop(*this, G, OuterLoop, Insert, SCC);
   }
 
   if (OuterLoop)
     return make_range(std::next(Prev), Insert);
   return make_range(Loops.begin(), Insert);
 }
 
 void

llvm/lib/Analysis/BranchProbabilityInfo.cpp

enum class BlockExecWeight : std::uint32_t {
   DEFAULT = 0xfffff
 };
 
 BranchProbabilityInfo::SccInfo::SccInfo(const Function &F) {
   // Record SCC numbers of blocks in the CFG to identify irreducible loops.
   // FIXME: We could only calculate this if the CFG is known to be irreducible
   // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
   int SccNum = 0;
-  for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
-       ++It, ++SccNum) {
+  for (auto SCC : scc_traversal(&F)) {
+    ++SccNum;
     // Ignore single-block SCCs since they either aren't loops or LoopInfo will
     // catch them.
-    const std::vector<const BasicBlock *> &Scc = *It;
-    if (Scc.size() == 1)
+    if (SCC->size() == 1)
       continue;
 
     LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
-    for (const auto *BB : Scc) {
+    for (const auto *BB : *SCC) {
       LLVM_DEBUG(dbgs() << " " << BB->getName());
       SccNums[BB] = SccNum;
       calculateSccBlockType(BB, SccNum);
     }
     LLVM_DEBUG(dbgs() << "\n");
   }
 }
 

llvm/lib/Analysis/CFGPrinter.cpp

auto evaluateBB = [&](const BasicBlock *Node) {
     }
     isOnDeoptOrUnreachablePath[Node] =
         llvm::all_of(successors(Node), [this](const BasicBlock *BB) {
           return isOnDeoptOrUnreachablePath[BB];
         });
   };
   /// The post order traversal iteration is done to know the status of
   /// isOnDeoptOrUnreachablePath for all the successors on the current BB.
-  llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB);
+  for (auto &BB : post_order(&F->getEntryBlock()))
+    evaluateBB(BB);
 }
 
 bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node,
                                                  const DOTFuncInfo *CFGInfo) {
   if (HideColdPaths.getNumOccurrences() > 0)
     if (auto *BFI = CFGInfo->getBFI()) {
       uint64_t NodeFreq = BFI->getBlockFreq(Node).getFrequency();
       uint64_t EntryFreq = BFI->getEntryFreq();

llvm/lib/Analysis/DDG.cpp

 //===--------------------------------------------------------------------===//
 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
 
 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
     : DependenceGraphInfo(F.getName().str(), D) {
   // Put the basic blocks in program order for correct dependence
   // directions.
   BasicBlockListType BBList;
-  for (const auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
-    append_range(BBList, SCC);
+  for (auto SCC : scc_traversal(&F))
+    append_range(BBList, *SCC);
   std::reverse(BBList.begin(), BBList.end());
   DDGBuilder(*this, D, BBList).populate();
 }
 
 DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
                                          DependenceInfo &D)
     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
                                 L.getHeader()->getName())

llvm/lib/Analysis/DependenceGraphBuilder.cpp

template <class G> void AbstractDependenceGraphBuilder<G>::createPiBlocks() {
 
   // Adding nodes as we iterate through the SCCs cause the SCC
   // iterators to get invalidated. To prevent this invalidation, we first
   // collect a list of nodes that are part of an SCC, and then iterate over
   // those lists to create the pi-block nodes. Each element of the list is a
   // list of nodes in an SCC. Note: trivial SCCs containing a single node are
   // ignored.
   SmallVector<NodeListType, 4> ListOfSCCs;
-  for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
-    if (SCC.size() > 1)
-      ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
+  for (auto SCC : scc_traversal(&Graph)) {
+    if (SCC->size() > 1)
+      ListOfSCCs.emplace_back(SCC->begin(), SCC->end());
   }
 
   for (NodeListType &NL : ListOfSCCs) {
     LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()
                       << " nodes in it.\n");
 
     // SCC iterator may put the nodes in an order that's different from the
     // program order. To preserve original program order, we sort the list of

llvm/lib/Analysis/GlobalsModRef.cpp

bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
   Handles.front().I = Handles.begin();
   return true;
 }
 
 void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {
   // We do a bottom-up SCC traversal of the call graph.  In other words, we
   // visit all callees before callers (leaf-first).
   unsigned SCCID = 0;
-  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
-    const std::vector<CallGraphNode *> &SCC = *I;
-    assert(!SCC.empty() && "SCC with no functions?");
+  for (auto SCC : scc_traversal(&CG)) {
+    assert(!SCC->empty() && "SCC with no functions?");
 
-    for (auto *CGN : SCC)
+    for (auto *CGN : *SCC)
       if (Function *F = CGN->getFunction())
         FunctionToSCCMap[F] = SCCID;
     ++SCCID;
   }
 }
 
 /// AnalyzeCallGraph - At this point, we know the functions where globals are
 /// immediately stored to and read from.  Propagate this information up the call
 /// graph to all callers and compute the mod/ref info for all memory for each
 /// function.
 void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
   // We do a bottom-up SCC traversal of the call graph.  In other words, we
   // visit all callees before callers (leaf-first).
-  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
-    const std::vector<CallGraphNode *> &SCC = *I;
+  for (auto I : scc_traversal(&CG)) {
+    const std::vector<CallGraphNode *> &SCC = I;
     assert(!SCC.empty() && "SCC with no functions?");
 
     Function *F = SCC[0]->getFunction();
 
     if (!F || !F->isDefinitionExact()) {
       // Calls externally or not exact - can't say anything useful. Remove any
       // existing function records (may have been created when scanning
       // globals).

llvm/lib/Analysis/LoopCacheAnalysis.cpp

 CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,
                         DependenceInfo &DI, Optional<unsigned> TRT) {
   if (!Root.isOutermost()) {
     LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
     return nullptr;
   }
 
   LoopVectorTy Loops;
-  append_range(Loops, breadth_first(&Root));
+  append_range(Loops, make_range(bf_begin(&Root), bf_end(&Root)));
 
   if (!getInnerMostLoop(Loops)) {
     LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
                          "than one innermost loop\n");
     return nullptr;
   }
 
   return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);

llvm/lib/Analysis/LoopNestAnalysis.cpp

static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                 ScalarEvolution &SE);
 
 //===----------------------------------------------------------------------===//
 // LoopNest implementation
 //
 
 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
     : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
-  append_range(Loops, breadth_first(&Root));
+  append_range(Loops, make_range(bf_begin(&Root), bf_end(&Root)));
 }
 
 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
                                                 ScalarEvolution &SE) {
   return std::make_unique<LoopNest>(Root, SE);
 }
 
 static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {

llvm/lib/Analysis/MLInlineAdvisor.cpp

MLInlineAdvisor::MLInlineAdvisor(Module &M, ModuleAnalysisManager &MAM,
 
   // Extract the 'call site height' feature - the position of a call site
   // relative to the farthest statically reachable SCC node. We don't mutate
   // this value while inlining happens. Empirically, this feature proved
   // critical in behavioral cloning - i.e. training a model to mimic the manual
   // heuristic's decisions - and, thus, equally important for training for
   // improvement.
   CallGraph CGraph(M);
-  for (auto I = scc_begin(&CGraph); !I.isAtEnd(); ++I) {
-    const std::vector<CallGraphNode *> &CGNodes = *I;
+  for (auto SCC : scc_traversal(&CGraph)) {
+    const std::vector<CallGraphNode *> &CGNodes = SCC;
     unsigned Level = 0;
     for (auto *CGNode : CGNodes) {
       Function *F = CGNode->getFunction();
       if (!F || F->isDeclaration())
         continue;
       for (auto &I : instructions(F)) {
         if (auto *CS = getInlinableCS(I)) {
           auto *Called = CS->getCalledFunction();

llvm/lib/Analysis/SyntheticCountsUtils.cpp

 
 template <typename CallGraphType>
 void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
                                                     GetProfCountTy GetProfCount,
                                                     AddCountTy AddCount) {
   std::vector<SccTy> SCCs;
 
   // Collect all the SCCs.
-  for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
-    SCCs.push_back(*I);
+  for (auto SCC : scc_traversal(CG))
+    SCCs.push_back(SCC);
 
   // The callgraph-scc needs to be visited in top-down order for propagation.
   // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
   // and call propagateFromSCC.
   for (auto &SCC : reverse(SCCs))
     propagateFromSCC(SCC, GetProfCount, AddCount);
 }
 
 template class llvm::SyntheticCountsUtils<const CallGraph *>;
 template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;

llvm/lib/IR/ModuleSummaryIndex.cpp

return !GlobalValue::isInterposableLinkage(S->linkage()) &&
          !S->notEligibleToImport() &&
          (!AnalyzeRefs || !HasRefsPreventingImport(GVS));
 }
 
 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
 // then delete this function and update its tests
 LLVM_DUMP_METHOD
 void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
-  for (scc_iterator<ModuleSummaryIndex *> I =
-           scc_begin<ModuleSummaryIndex *>(this);
-       !I.isAtEnd(); ++I) {
-    O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
-      << ") {\n";
-    for (const ValueInfo &V : *I) {
+  for (auto SCC : scc_traversal(this)) {
+    O << "SCC (" << utostr(SCC->size()) << " node"
+      << (SCC->size() == 1 ? "" : "s") << ") {\n";
+    for (const ValueInfo &V : *SCC) {
       FunctionSummary *F = nullptr;
       if (V.getSummaryList().size())
         F = cast<FunctionSummary>(V.getSummaryList().front().get());
       O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
-        << (I.hasCycle() ? " (has cycle)" : "") << "\n";
+        << (SCC.hasCycle() ? " (has cycle)" : "") << "\n";
     }
     O << "}\n";
   }
 }
 
 namespace {
 struct Attributes {
   void add(const Twine &Name, const Twine &Value,

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

static bool mayContainUnboundedCycle(Function &F, Attributor &A) {
   ScalarEvolution *SE =
       A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(F);
   LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(F);
   // If either SCEV or LoopInfo is not available for the function then we assume
   // any cycle to be unbounded cycle.
   // We use scc_iterator which uses Tarjan algorithm to find all the maximal
   // SCCs.To detect if there's a cycle, we only need to find the maximal ones.
   if (!SE || !LI) {
-    for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
-      if (SCCI.hasCycle())
+    for (auto SCC : scc_traversal(&F))
+      if (SCC.hasCycle())
         return true;
     return false;
   }
 
   // If there's irreducible control, the function may contain non-loop cycles.
   if (mayContainIrreducibleControl(F, LI))
     return true;
 

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

if (InferredFlags.NoUnwind || InferredFlags.NoRecurse) {
               FS->setNoUnwind();
           }
         }
       }
     }
   };
 
   // Call propagation functions on each SCC in the Index
-  for (scc_iterator<ModuleSummaryIndex *> I = scc_begin(&Index); !I.isAtEnd();
-       ++I) {
-    std::vector<ValueInfo> Nodes(*I);
+  for (auto SCC : scc_traversal(&Index)) {
+    std::vector<ValueInfo> Nodes(*SCC);
     PropagateAttributes(Nodes);
   }
   return Changed;
 }
 
 namespace {
 
 /// For a given pointer Argument, this retains a list of Arguments of functions
static void addArgumentAttrs(const SCCNodeSet &SCCNodes,
 
   // The graph we've collected is partial because we stopped scanning for
   // argument uses once we solved the argument trivially. These partial nodes
   // show up as ArgumentGraphNode objects with an empty Uses list, and for
   // these nodes the final decision about whether they capture has already been
   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
   // captures.
 
-  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
-    const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
+  for (auto SCC : scc_traversal(&AG)) {
+    const std::vector<ArgumentGraphNode *> &ArgumentSCC = SCC;
     if (ArgumentSCC.size() == 1) {
       if (!ArgumentSCC[0]->Definition)
         continue; // synthetic root node
 
       // eg. "void f(int* x) { if (...) f(x); }"
       if (ArgumentSCC[0]->Uses.size() == 1 &&
           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
         Argument *A = ArgumentSCC[0]->Definition;
static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
   // We only have a post-order SCC traversal (because SCCs are inherently
   // discovered in post-order), so we accumulate them in a vector and then walk
   // it in reverse. This is simpler than using the RPO iterator infrastructure
   // because we need to combine SCC detection and the PO walk of the call
   // graph. We can also cheat egregiously because we're primarily interested in
   // synthesizing norecurse and so we can only save the singular SCCs as SCCs
   // with multiple functions in them will clearly be recursive.
   SmallVector<Function *, 16> Worklist;
-  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
-    if (I->size() != 1)
+  for (auto SCC : scc_traversal(&CG)) {
+    if (SCC->size() != 1)
       continue;
 
-    Function *F = I->front()->getFunction();
+    Function *F = SCC->front()->getFunction();
     if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
         F->hasInternalLinkage())
       Worklist.push_back(F);
   }
 
   bool Changed = false;
   for (auto *F : llvm::reverse(Worklist))
     Changed |= addNoRecurseAttrsTopDown(*F);

llvm/lib/Transforms/IPO/SampleProfile.cpp

if (UseProfiledCallGraph || (FunctionSamples::ProfileIsCS &&
     // Note that static callgraph edges are completely ignored since they
     // can be conflicting with profiled edges for cyclic SCCs and may result in
     // an SCC order incompatible with profile-defined one. Using strictly
     // profile order ensures a maximum inlining experience. On the other hand,
     // static call edges are not so important when they don't correspond to a
     // context in the profile.
 
     std::unique_ptr<ProfiledCallGraph> ProfiledCG = buildProfiledCallGraph(*CG);
-    scc_iterator<ProfiledCallGraph *> CGI = scc_begin(ProfiledCG.get());
-    while (!CGI.isAtEnd()) {
+    for (auto CGI : scc_traversal(ProfiledCG.get())) {
       auto Range = *CGI;
       if (SortProfiledSCC) {
         // Sort nodes in one SCC based on callsite hotness.
         scc_member_iterator<ProfiledCallGraph *> SI(*CGI);
         Range = *SI;
       }
       for (auto *Node : Range) {
         Function *F = SymbolMap.lookup(Node->Name);
         if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile"))
           FunctionOrderList.push_back(F);
       }
-      ++CGI;
     }
   } else {
-    scc_iterator<CallGraph *> CGI = scc_begin(CG);
-    while (!CGI.isAtEnd()) {
+    for (auto CGI : scc_traversal(CG)) {
       for (CallGraphNode *Node : *CGI) {
         auto *F = Node->getFunction();
         if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile"))
           FunctionOrderList.push_back(F);
       }
-      ++CGI;
     }
   }
 
   LLVM_DEBUG({
     dbgs() << "Function processing order:\n";
     for (auto F : reverse(FunctionOrderList)) {
       dbgs() << F->getName() << "\n";
     }

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

void StructurizeCFG::orderNodes() {
   SmallVector<std::pair<unsigned, unsigned>, 8> WorkList;
   unsigned I = 0, E = Order.size();
   while (true) {
     // Run through all the SCCs in the subgraph starting with Entry.
     for (auto SCCI =
              scc_iterator<SubGraphTraits::NodeRef, SubGraphTraits>::begin(
                  EntryNode);
          !SCCI.isAtEnd(); ++SCCI) {
-      auto &SCC = *SCCI;
+      auto &SCC = **SCCI;
 
       // An SCC up to the size of 2, can be reduced to an entry (the last node),
       // and a possible additional node. Therefore, it is already in order, and
       // there is no need to add it to the work-list.
       unsigned Size = SCC.size();
       if (Size > 2)
         WorkList.emplace_back(I, I + Size);
 

llvm/lib/Transforms/Utils/FixIrreducible.cpp

static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
                               SetVector<BasicBlock *> &Headers) {
   createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
 }
 
 // Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
 template <class Graph>
 static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
   bool Changed = false;
-  for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
+  for (auto Scc : scc_traversal(G)) {
     if (Scc->size() < 2)
       continue;
     SetVector<BasicBlock *> Blocks;
     LLVM_DEBUG(dbgs() << "Found SCC:");
     for (auto N : *Scc) {
       auto BB = unwrapBlock(N);
       LLVM_DEBUG(dbgs() << " " << BB->getName());
       Blocks.insert(BB);

llvm/tools/llvm-profgen/CSPreInliner.cpp

 }
 
 std::vector<StringRef> CSPreInliner::buildTopDownOrder() {
   std::vector<StringRef> Order;
   ProfiledCallGraph ProfiledCG(ContextTracker);
 
   // Now that we have a profiled call graph, construct top-down order
   // by building up SCC and reversing SCC order.
-  scc_iterator<ProfiledCallGraph *> I = scc_begin(&ProfiledCG);
-  while (!I.isAtEnd()) {
-    auto Range = *I;
+  for (auto SCC : scc_traversal(&ProfiledCG)) {
+    auto Range = *SCC;
     if (SortProfiledSCC) {
       // Sort nodes in one SCC based on callsite hotness.
-      scc_member_iterator<ProfiledCallGraph *> SI(*I);
+      scc_member_iterator<ProfiledCallGraph *> SI(*SCC);
       Range = *SI;
     }
     for (auto *Node : Range) {
       if (Node != ProfiledCG.getEntryNode())
         Order.push_back(Node->Name);
     }
-    ++I;
   }
   std::reverse(Order.begin(), Order.end());
 
   return Order;
 }
 
 bool CSPreInliner::getInlineCandidates(ProfiledCandidateQueue &CQueue,
                                        const FunctionSamples *CallerSamples) {

llvm/tools/opt/PrintSCC.cpp

 
 char CallGraphSCC::ID = 0;
 static RegisterPass<CallGraphSCC>
 Z("print-callgraph-sccs", "Print SCCs of the Call Graph");
 
 bool CFGSCC::runOnFunction(Function &F) {
   unsigned sccNum = 0;
   errs() << "SCCs for Function " << F.getName() << " in PostOrder:";
-  for (scc_iterator<Function*> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI) {
-    const std::vector<BasicBlock *> &nextSCC = *SCCI;
+  for (auto SCC : scc_traversal(&F)) {
     errs() << "\nSCC #" << ++sccNum << " : ";
-    for (BasicBlock *BB : nextSCC) {
+    for (BasicBlock *BB : *SCC) {
       BB->printAsOperand(errs(), false);
       errs() << ", ";
     }
-    if (nextSCC.size() == 1 && SCCI.hasCycle())
+    if (SCC->size() == 1 && SCC.hasCycle())
       errs() << " (Has self-loop).";
   }
   errs() << "\n";
 
   return true;
 }
 
 
 // run - Print out SCCs in the call graph for the specified module.
 bool CallGraphSCC::runOnModule(Module &M) {
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   unsigned sccNum = 0;
   errs() << "SCCs for the program in PostOrder:";
-  for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG); !SCCI.isAtEnd();
-       ++SCCI) {
-    const std::vector<CallGraphNode*> &nextSCC = *SCCI;
+  for (auto SCC : scc_traversal(&CG)) {
     errs() << "\nSCC #" << ++sccNum << " : ";
-    for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
-           E = nextSCC.end(); I != E; ++I)
-      errs() << ((*I)->getFunction() ? (*I)->getFunction()->getName()
-                                     : "external node") << ", ";
-    if (nextSCC.size() == 1 && SCCI.hasCycle())
+    for (auto *N : *SCC)
+      errs() << (N->getFunction() ? N->getFunction()->getName()
+                                  : "external node")
+             << ", ";
+
+    if (SCC->size() == 1 && SCC.hasCycle())
       errs() << " (Has self-loop).";
   }
   errs() << "\n";
 
   return true;
 }

llvm/unittests/ADT/DirectedGraphTest.cpp

TEST(DirectedGraphTest, SCC) {
   //             |        ^
   //             +--------+
 
   // Test that there are two SCCs:
   // 1. {N1, N2, N3}
   // 2. {N4}
   using NodeListTy = SmallPtrSet<DGTestNode *, 3>;
   SmallVector<NodeListTy, 4> ListOfSCCs;
-  for (auto &SCC : make_range(scc_begin(&DG), scc_end(&DG)))
-    ListOfSCCs.push_back(NodeListTy(SCC.begin(), SCC.end()));
+  for (auto SCC : scc_traversal(&DG))
+    ListOfSCCs.push_back(NodeListTy(SCC->begin(), SCC->end()));
 
   EXPECT_TRUE(ListOfSCCs.size() == 2);
 
   for (auto &SCC : ListOfSCCs) {
     if (SCC.size() > 1)
       continue;
     EXPECT_TRUE(SCC.size() == 1);
     EXPECT_TRUE(SCC.count(&N4) == 1);

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

TEST(VPBasicBlockTest, TraversingIteratorTest) {
     SmallVector<VPRegionBlock *> FromIteratorVPRegion(
         VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(Start)));
     EXPECT_EQ(2u, FromIteratorVPRegion.size());
     EXPECT_EQ(R1, FromIteratorVPRegion[0]);
     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
 
     // Post-order.
     FromIterator.clear();
-    copy(post_order(Start), std::back_inserter(FromIterator));
+    copy(make_range(po_begin(Start), po_end(Start)),
+         std::back_inserter(FromIterator));
     EXPECT_EQ(8u, FromIterator.size());
     EXPECT_EQ(R2BB2, FromIterator[0]);
     EXPECT_EQ(R2BB1, FromIterator[1]);
     EXPECT_EQ(R2, FromIterator[2]);
     EXPECT_EQ(R1BB4, FromIterator[3]);
     EXPECT_EQ(R1BB2, FromIterator[4]);
     EXPECT_EQ(R1BB3, FromIterator[5]);
     EXPECT_EQ(R1BB1, FromIterator[6]);
copy(VPBlockUtils::blocksOnly<VPBasicBlock>(depth_first(Start)),
          std::back_inserter(FromIteratorVPBB));
     EXPECT_EQ(VPBB1, FromIteratorVPBB[0]);
     EXPECT_EQ(R2BB1, FromIteratorVPBB[1]);
     EXPECT_EQ(R3BB1, FromIteratorVPBB[2]);
     EXPECT_EQ(VPBB2, FromIteratorVPBB[3]);
 
     // Post-order.
     FromIterator.clear();
-    copy(post_order(Start), std::back_inserter(FromIterator));
+    copy(make_range(po_begin(Start), po_end(Start)),
+         std::back_inserter(FromIterator));
     EXPECT_EQ(7u, FromIterator.size());
     EXPECT_EQ(VPBB2, FromIterator[0]);
     EXPECT_EQ(R3BB1, FromIterator[1]);
     EXPECT_EQ(R3, FromIterator[2]);
     EXPECT_EQ(R2BB1, FromIterator[3]);
     EXPECT_EQ(R2, FromIterator[4]);
     EXPECT_EQ(R1, FromIterator[5]);
     EXPECT_EQ(VPBB1, FromIterator[6]);
 
     // Post-order, const VPRegionBlocks only.
     VPBlockRecursiveTraversalWrapper<const VPBlockBase *> StartConst(VPBB1);
     SmallVector<const VPRegionBlock *> FromIteratorVPRegion(
-        VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst)));
+        VPBlockUtils::blocksOnly<const VPRegionBlock>(
+            make_range(po_begin(StartConst), po_end(StartConst))));
     EXPECT_EQ(3u, FromIteratorVPRegion.size());
     EXPECT_EQ(R3, FromIteratorVPRegion[0]);
     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
     EXPECT_EQ(R1, FromIteratorVPRegion[2]);
 
     // Post-order, VPBasicBlocks only.
     FromIterator.clear();
-    copy(VPBlockUtils::blocksOnly<VPBasicBlock>(post_order(Start)),
+    copy(VPBlockUtils::blocksOnly<VPBasicBlock>(
+             make_range(po_begin(Start), po_end(Start))),
          std::back_inserter(FromIterator));
     EXPECT_EQ(FromIterator.size(), 4u);
     EXPECT_EQ(VPBB2, FromIterator[0]);
     EXPECT_EQ(R3BB1, FromIterator[1]);
     EXPECT_EQ(R2BB1, FromIterator[2]);
     EXPECT_EQ(VPBB1, FromIterator[3]);
 
     // Use Plan to properly clean up created blocks.

mlir/lib/Analysis/CallGraph.cpp

for (auto &edge : *node) {
       emitNodeName(edge.getTarget());
       os << "\n";
     }
     os << "//\n";
   }
 
   os << "// -- SCCs --\n";
 
-  for (auto &scc : make_range(llvm::scc_begin(this), llvm::scc_end(this))) {
+  for (auto scc : llvm::scc_traversal(this)) {
     os << "// - SCC : \n";
-    for (auto &node : scc) {
+    for (auto &node : *scc) {
       os << "// -- Node :";
       emitNodeName(node);
       os << "\n";
     }
     os << "\n";
   }
 
   os << "// -------------------\n";
 }