[ADT] Generic BFS graph iterator

[davide]

Summary

As we discussed on IRC a couple of days ago, we want to speed up some skip checks in LCSSA, and we need to walk the BB of a loop in BFS order to do so.
I decided to make this a piece of ADT, just in case we need for something else. I'll add some other tests and give some testing, but I want to make sure we agree it's fine having this being a generic iterator.

[• dberlin]

I'm trying to understand how you are level numbering.
The level numbering can't be done on a cyclic graph without help (or, at the very least, if it is defined as "the minimum depth from root we ever saw this node as" or sometihng, so you would use min(current, last level)".
It works fine for free.

[• dberlin]

In D31694#718809, @dberlin wrote:

I'm trying to understand how you are level numbering.
The level numbering can't be done on a cyclic graph without help (or, at the very least, if it is defined as "the minimum depth from root we ever saw this node as" or sometihng, so you would use min(current, last level)".
It works fine for free.

Forget it, i'm being dumb.
It's unweighted bfs, so if there was a shorter path, we would have already hit it, so if we revisit something, it can't change the lowest level.

[davide]

• Updated test to be more comprehensive
• Add a test with a cyclic graph
• Fixed a bug in the marker logic where we were looping indefinitely (now covered by testing).

I think this is ready to be used in LCSSA now.

[davide]

Also, I added some comments to explain how we put the markers, but please let me know if I'm missing something

[• dberlin]

This looks correct to me.

include/llvm/ADT/BreadthFirstIterator.h

+//===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file builds on the ADT/GraphTraits.h file to build a generic breadth
+// first graph iterator.  This file exposes the following functions/types:
+//
+// bf_begin/bf_end/bf_iterator
+//   * Normal breadth-first iteration - visit a graph level-by-level.
+//
+//===----------------------------------------------------------------------===//
+
+#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_range.h"
+#include <iterator>
+#include <queue>
+#include <set>
+#include <utility>
+
+namespace llvm {
+
+// bf_iterator_storage - A private class which is used to figure out where to
+// store the visited set. We only provide a non-external variant for now.
+template <class SetType> class bf_iterator_storage {
+public:
+  SetType Visited;
+};
+
+// The visited state for the iteration is a simple set.
+template <typename NodeRef, unsigned SmallSize = 8>
+using bf_iterator_default_set = SmallPtrSet<NodeRef, SmallSize>;
+
+// Generic Breadth first search iterator.
+template <class GraphT,
+          class SetType =
+              bf_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
+          class GT = GraphTraits<GraphT>>
+class bf_iterator
+    : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
+      public bf_iterator_storage<SetType> {
+  typedef std::iterator<std::forward_iterator_tag, typename GT::NodeRef> super;
+
+  typedef typename GT::NodeRef NodeRef;
+  typedef typename GT::ChildIteratorType ChildItTy;
+
+  // First element is the node reference, second is the next child to visit.
+  typedef std::pair<NodeRef, Optional<ChildItTy>> QueueElement;
+
+  // Visit queue - used to maintain BFS ordering.
+  // Optional<> because we need markers for levels.
+  std::queue<Optional<QueueElement>> VisitQueue;
+
+  // Current level.
+  unsigned Level;
+
+private:
+  inline bf_iterator(NodeRef Node) {
+    this->Visited.insert(Node);
+    Level = 0;
+
+    // Also, insert a dummy node as marker.
+    VisitQueue.push(QueueElement(Node, None));
+    VisitQueue.push(None);
+  }
+
+  inline bf_iterator() = default;
+
+  inline void toNext() {
+    Optional<QueueElement> Head;
+
+    if (!VisitQueue.empty()) {
+      Optional<QueueElement> Head = VisitQueue.front();
+      QueueElement H = Head.getValue();
+      NodeRef Node = H.first;
+      Optional<ChildItTy> &ChildIt = H.second;
+
+      if (!ChildIt)
+        ChildIt.emplace(GT::child_begin(Node));
+      while (*ChildIt != GT::child_end(Node)) {
+        NodeRef Next = *(*ChildIt)++;
+
+        // Already visited?
+        if (this->Visited.insert(Next).second)
+          VisitQueue.push(QueueElement(Next, None));
+      }
+      VisitQueue.pop();
+    }
+
+    if (!VisitQueue.empty()) {
+      Head = VisitQueue.front();
+
+      // Found a marker.
+      if (Head == None) {
+        Level += 1;
+        VisitQueue.pop();
+        VisitQueue.push(None);
+      }
+    }
+  }
+
+public:
+  typedef typename super::pointer pointer;
+
+  // Provide static begin and end methods as our public "constructors"
+  static bf_iterator begin(const GraphT &G) {
+    return bf_iterator(GT::getEntryNode(G));
+  }
+
+  static bf_iterator end(const GraphT &G) { return bf_iterator(); }
+
+  bool operator==(const bf_iterator &RHS) {
+    return VisitQueue == RHS.VisitQueue;
+  }
+
+  bool operator!=(const bf_iterator &RHS) { return !(*this == RHS); }
+
+  const NodeRef &operator*() const { return VisitQueue.front()->first; }
+
+  // This is a nonstandard operator-> that dereferenfces 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
+    toNext();
+    return *this;
+  }
+
+  bf_iterator operator++(int) { // Post-increment
+    bf_iterator ItCopy = *this;
+    ++*this;
+    return ItCopy;
+  }
+
+  unsigned getLevel() const { return Level; }
+};
+
+// Provide global constructors that automatically figure out correct types.
+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));
+}
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_BREADTHFIRSTITERATOR_H

unittests/ADT/BreadthFirstIteratorTest.cpp

+//=== llvm/unittest/ADT/BreadthFirstIteratorTest.cpp - BFS iterator tests -===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/BreadthFirstIterator.h"
+#include "TestGraph.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace llvm {
+
+TEST(BreadthFristIteratorTest, Basic) {
+  typedef bf_iterator<Graph<4>> BFIter;
+
+  Graph<4> G;
+  G.AddEdge(0, 1);
+  G.AddEdge(0, 2);
+  G.AddEdge(1, 3);
+
+  auto It = BFIter::begin(G);
+  EXPECT_EQ(It.getLevel(), 0U);
+  ++It;
+  EXPECT_EQ(It.getLevel(), 1U);
+  ++It;
+  EXPECT_EQ(It.getLevel(), 1U);
+  ++It;
+  EXPECT_EQ(It.getLevel(), 2U);
+}
+
+} // end namespace llvm

unittests/ADT/CMakeLists.txt

   ArrayRefTest.cpp
   BitmaskEnumTest.cpp
   BitVectorTest.cpp
+  BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp