NestedSCC

[david2050]

Summary

Support for building Nested Strongly connected components
for a control flow graph.

[david2050]

remove facebook markers

include/llvm/ADT/NestedSCC.h

+//===- ADT/NestedSCC.h - Nested Strongly Connected Comp. -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// facebook T38406375
+///
+///
+/// This builds a set of nested DAG's corresponding to the
+/// nested strongly connected components of a graph. This initial implemented
+/// only works tested for control flow graphs of a function.
+///
+/// The result is a top-level graph-like object each node of which references
+/// either a basic block or a nested graph. Edges are placed between two nodes
+/// if there is an edge in the underlying graph. Edges are unique even
+/// when the underlying graph may have multiple edges. A single basic block
+/// make be have a self-edge in the underlying graph and this can be determined
+/// by the hasLoop method.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_NESTEDSCC_H
+#define LLVM_ADT_NESTEDSCC_H
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+#include <utility>
+
+namespace llvm {
+//===----------------------------------------------------------------------===//
+// This structure can be used to have a view into a subgraph of some
+// other graph. The GT parameter is expected to be a GraphTraits class.
+// The Iterator is used to traverse successors (GT child nodes) and uses
+// the underling graph iteration which is filtered to ignore nodes not
+// in the current subgraph and also to ignore back edges into the entry node.
+// This last is motivated by the current use case of finding nested strongly
+// connected components.
+//===----------------------------------------------------------------------===//
+template <class GT> class SubGraph {
+public:
+  /// A node in the base graph.
+  using BaseNodeRef = typename GT::NodeRef;
+  /// A node in the subgraph which is a node in the base graph
+  /// plus a pointer to this subgraph.
+  using NodeRef = std::pair<BaseNodeRef, const SubGraph *>;
+  static BaseNodeRef baseNode(NodeRef N) { return N.first; }
+  static const SubGraph *subGraph(NodeRef N) { return N.second; }
+
+  /// Construction which takes an iterable collection of base
+  /// grap nodes and the entry node of the subgraph.
+  template <typename Collection>
+  SubGraph(const Collection &activeNodes, BaseNodeRef entryNode)
+      : entryNode(entryNode) {
+    for (auto N : activeNodes)
+      active.insert(N);
+  }
+
+  /// The unique entry node for this subgraph.
+  NodeRef getEntryNode() const { return {entryNode, this}; }
+
+  /// The set of active base graph nodes for this subgraph.
+  const DenseSet<BaseNodeRef> &getActiveNodes() { return active; }
+
+  class ChildIterator;
+
+private:
+  // The collection of nodes which are part of the subgraph.
+  DenseSet<BaseNodeRef> active;
+  // The designated "entry" node.
+  BaseNodeRef entryNode;
+};
+
+/// This iterator returns nodes in the subgraph by filtering
+/// the nodes in the base graph via the "active" set.
+/// This is used for nested SCC algorithms and so it also
+/// filters out all edges into the "entry node" in order
+/// to break cycles.
+template <class GT> class SubGraph<GT>::ChildIterator {
+  using BaseIterator = typename GT::ChildIteratorType;
+
+public:
+  ChildIterator(NodeRef N)
+      : source(baseNode(N)), Cur(GT::child_begin(baseNode(N))),
+        End(GT::child_end(baseNode(N))), G(subGraph(N)) {
+    if (Cur != End && !validSuccessor(*Cur))
+      advance();
+  }
+  ChildIterator(BaseIterator Cur, const SubGraph *G)
+      : source(nullptr), Cur(Cur), End(Cur), G(G) {}
+  NodeRef operator*() {
+    assert(*Cur != G->entryNode);
+    return {*Cur, G};
+  }
+  bool operator!=(const ChildIterator &It) { return Cur != It.Cur; }
+  bool operator==(const ChildIterator &It) { return Cur == It.Cur; }
+  ChildIterator &operator++() {
+    advance();
+    return *this;
+  }
+  ChildIterator operator++(int) {
+    ChildIterator temp(*this);
+    advance();
+    return temp;
+  }
+
+private:
+  bool validSuccessor(BaseNodeRef N) {
+    return N != G->entryNode && G->active.count(N);
+  }
+  void advance() {
+    if (Cur == End)
+      return;
+    Cur++;
+    while (Cur != End && !validSuccessor(*Cur))
+      Cur++;
+  }
+  BaseNodeRef source; // TODO(dcallahan) remove this field
+  BaseIterator Cur, End;
+  const SubGraph *G;
+};
+namespace NestedSCC_ {
+struct empty {};
+} // namespace NestedSCC_
+
+//===----------------------------------------------------------------------===//
+template <class GraphT, class SubGraphTraits, class GraphTraits,
+          class Base = NestedSCC_::empty>
+class SCCNest;
+
+/// This is a recursive structure where each instances corresponds to a
+/// a function body or a strongly connected component which has been
+/// recursively decomposed by deleting "back edges" into a designated
+/// entry node. Note that "irreducible" loops may be decomposed into
+/// a nest of loops instead of a single natural loop.
+/// Base is used as public base class for elements to allow a client to
+/// customize with per-component fields.
+template <class GraphT, class SubGraphTraits, class GraphTraits,
+          class Base = NestedSCC_::empty>
+class NestedSCC : public Base {
+public:
+  class Element;
+  using BaseNodeRef = typename GraphTraits::NodeRef;
+  using SubGraphT = SubGraph<GraphTraits>;
+  using SCCIterT = scc_iterator<SubGraphT, SubGraphTraits>;
+  NestedSCC(GraphT G);
+  NestedSCC(SubGraphT &G, NestedSCC *Parent, unsigned ParentIndex,
+            GraphT BaseG);
+
+  /// size -- Number of  nodes in this strongly connected component
+  /// where a node may be a base graph node or a nested strongly
+  /// connected component.
+  unsigned size() const { return static_cast<unsigned>(SCCs.size()); }
+  /// The nesting depth of the component.
+  unsigned getDepth() const { return depth; }
+
+  /// A iterable of all of the nodes in the component. This collection
+  /// is topologically sorted to respect non-back-edges in the base graph.
+  const SmallVectorImpl<Element> &getSCCs() const { return SCCs; }
+
+  /// Return the i-th node in this component. 0 <= i < size()
+  const Element &at(unsigned i) const { return SCCs[i]; }
+
+  /// Return the index of an element.
+  unsigned index(const Element &N) const {
+    return static_cast<unsigned>(&N - &at(0));
+  }
+
+  void dump(raw_ostream &OS, bool all = true);
+
+  using NodeIterator = typename SmallVectorImpl<Element>::const_iterator;
+  NodeIterator node_begin() const { return SCCs.begin(); }
+  NodeIterator node_end() const { return SCCs.end(); }
+
+  /// Return the immediately containing strongly connected component
+  /// for this component. This is null for the outermost.
+  NestedSCC *getParent() const { return Parent; }
+
+  /// Return the index of the node in the parent strongly connected
+  /// component corresponding to this scc.
+  unsigned getParentIndex() const { return ParentIndex; }
+
+  class ChildIterator;
+
+private:
+  friend class SCCNest<GraphT, SubGraphTraits, GraphTraits, Base>;
+
+  // Helper functions which completes building the components
+  // where the nodes in each componets are stored in this vector.
+  // Initially these are in reverse toplogical order as that is the
+  // order the underlying scc_iterator<> produces them.
+  void build(SmallVectorImpl<SmallVector<BaseNodeRef, 1>> &components,
+             GraphT BaseB);
+
+  // Reference to the associated node in the containing SCC.
+  NestedSCC *Parent;
+  unsigned ParentIndex;
+
+  // Nesting depth: zero for the top-most, 1 more than parent
+  // othersise.
+  unsigned depth;
+
+  // Components are numbered and stored in the vector SCCs.
+  // Components are toplogically ordered (ignoring backed edgds
+  // into the entry node).
+  SmallVector<Element, 16> SCCs;
+};
+
+// This class is the top-level repesented of the collection of nested
+// strongly connected components. It holds a pointer to the top-most (root)
+// component and a map from base graph nodes to the innermost component where
+// that node appears.
+template <class GraphT, class SubGraphTraits, class GraphTraits, class Base>
+class SCCNest {
+public:
+  using NestedSCCT = NestedSCC<GraphT, SubGraphTraits, GraphTraits, Base>;
+  class DepthFirstIterator;
+  using BaseNodeRef = typename GraphTraits::NodeRef;
+  using SubGraphT = SubGraph<GraphTraits>;
+  using SCCIterT = scc_iterator<SubGraphT, SubGraphTraits>;
+  SCCNest(GraphT G);
+
+  NestedSCCT &getRoot() const { return *root; }
+
+  /// A reference to an element in a paricular strongly connected component
+  /// realized as a pair of the component and the node indexer.
+  using ComponentRef = std::pair<NestedSCCT *, unsigned>;
+  static NestedSCCT *component(ComponentRef C) { return C.first; }
+  static unsigned index(ComponentRef C) { return C.second; }
+
+  /// Defined only for the outer most SCC, map a base graph node to the
+  /// deepest containing stronglly connected compnent in which it occurs.
+  ComponentRef getComponent(BaseNodeRef BN) const {
+    auto iter = map.find(BN);
+    if (iter == map.end())
+      return {nullptr, 0};
+    return iter->second;
+  }
+
+  void dump(raw_ostream &OS) { root->dump(OS, /*all*/ true); }
+
+private:
+  // Combine all maps into the top-level map. This should
+  // only be invoked for the top-level map.
+  void buildMap();
+
+  // Top-most strongly-connected component
+  NestedSCCT *root;
+
+  // map basic blocks to the associated element in
+  // SCCs which corresponds to the component containing
+  // the block. After construction this is only valid
+  // for the top-level strongly connected component.
+  DenseMap<BaseNodeRef, ComponentRef> map;
+};
+
+template <class GraphT, class SGT, class GT, class Base>
+SCCNest<GraphT, SGT, GT, Base>::SCCNest(GraphT G) {
+  root = new NestedSCCT(G);
+  buildMap();
+}
+
+/// This class represents a single strongly connected component
+/// which might be a singlton node (perhaps a self-loop) or a nested
+/// instance. We record as adjacency lists the elements the induced
+/// edges from the base graph.
+template <class GraphT, class SGT, class GT, class Base>
+class NestedSCC<GraphT, SGT, GT, Base>::Element {
+public:
+  Element(const SmallVectorImpl<BaseNodeRef> &It, NestedSCC *Parent,
+          unsigned ParentIndex, GraphT BaseG);
+
+  NestedSCC *getNested() const { return nested.get(); }
+  BaseNodeRef getBaseNode() const {
+    assert(!nested);
+    return leaf;
+  }
+
+private:
+  std::unique_ptr<NestedSCC> nested; // may be null
+  BaseNodeRef leaf = nullptr;        // defined if nested is null
+  friend class NestedSCC;
+};
+
+template <class GraphT, class SGT, class GT, class Base>
+NestedSCC<GraphT, SGT, GT, Base>::NestedSCC(GraphT G)
+    : Parent(nullptr), ParentIndex(0), depth(0) {
+
+  SmallVector<SmallVector<BaseNodeRef, 1>, 32> components;
+  for (scc_iterator<GraphT, GT> It = scc_begin(G); !It.isAtEnd(); ++It)
+    components.emplace_back((*It).begin(), (*It).end());
+  build(components, G);
+}
+
+template <class GraphT, class SGT, class GT, class Base>
+NestedSCC<GraphT, SGT, GT, Base>::NestedSCC(SubGraphT &G, NestedSCC *Parent,
+                                            unsigned ParentIndex, GraphT BaseG)
+    : Parent(Parent), ParentIndex(ParentIndex), depth(Parent->depth + 1) {
+
+  SmallVector<SmallVector<BaseNodeRef, 1>, 32> components;
+  for (auto SIt = SCCIterT::begin(G); !SIt.isAtEnd(); ++SIt) {
+    components.emplace_back();
+    for (auto Pair : *SIt)
+      components.back().push_back(SubGraphT::baseNode(Pair));
+  }
+  build(components, BaseG);
+}
+
+template <class GraphT, class SGT, class GT, class Base>
+void NestedSCC<GraphT, SGT, GT, Base>::build(
+    SmallVectorImpl<SmallVector<BaseNodeRef, 1>> &components, GraphT G) {
+
+  // Reverse order of nodes so they are topological
+  std::reverse(components.begin(), components.end());
+
+  // Recursively build the nested SCCs
+  for (unsigned i = 0; i < components.size(); i++)
+    SCCs.emplace_back(components[i], this, i, G);
+}
+
+template <class GraphT, class SGT, class GT, class Base>
+NestedSCC<GraphT, SGT, GT, Base>::Element::Element(
+    const SmallVectorImpl<BaseNodeRef> &Nodes, NestedSCC *Parent,
+    unsigned ParentIndex, GraphT BaseG) {
+  if (Nodes.size() == 1) {
+    leaf = Nodes[0];
+    return;
+  }
+  SubGraphT subgraph(Nodes, Nodes.back());
+  nested.reset(new NestedSCC(subgraph, Parent, ParentIndex, BaseG));
+}
+
+//===----------------------------------------------------------------------===//
+// Iterator and range-iteration support
+//===----------------------------------------------------------------------===//
+template <class GraphT, class SGT, class GT, class Base>
+iterator_range<typename NestedSCC<GraphT, SGT, GT, Base>::NodeIterator>
+scc_nodes(NestedSCC<GraphT, SGT, GT, Base> &SCCs) {
+  return {SCCs.node_begin(), SCCs.node_end()};
+}
+
+template <class GraphT, class SGT, class GT, class Base>
+class SCCNest<GraphT, SGT, GT, Base>::DepthFirstIterator {
+public:
+  using NestSCCT = SCCNest::NestedSCCT;
+  DepthFirstIterator(NestedSCCT &root) : Stack({{&root, 0u}}) {}
+  DepthFirstIterator() = default;
+  NestedSCCT &operator*() { return *(Stack.back().first); }
+  void operator++() {
+    do {
+      NestedSCCT *cur;
+      unsigned nodeIdx;
+      std::tie(cur, nodeIdx) = Stack.back();
+      for (; nodeIdx < cur->size(); nodeIdx++) {
+        auto &node = cur->at(nodeIdx);
+        if (node.getNested()) {
+          Stack.back().second = nodeIdx + 1;
+          Stack.emplace_back(node.getNested(), 0);
+          return;
+        }
+      }
+      Stack.pop_back();
+    } while (!Stack.empty());
+  }
+  bool operator!=(const DepthFirstIterator &Other) {
+    return Stack.size() != Other.Stack.size();
+  }
+
+private:
+  SmallVector<std::pair<NestedSCCT *, unsigned>, 4> Stack;
+};
+
+template <class GraphT, class SGT, class GT, class Base>
+typename SCCNest<GraphT, SGT, GT, Base>::DepthFirstIterator
+scc_df_begin(SCCNest<GraphT, SGT, GT, Base> &SCC) {
+  return typename SCCNest<GraphT, SGT, GT, Base>::DepthFirstIterator(
+      SCC.getRoot());
+}
+template <class GraphT, class SGT, class GT, class Base>
+typename SCCNest<GraphT, SGT, GT, Base>::DepthFirstIterator
+scc_df_end(SCCNest<GraphT, SGT, GT, Base> &SCC) {
+  return typename SCCNest<GraphT, SGT, GT, Base>::DepthFirstIterator();
+}
+template <class GraphT, class SGT, class GT, class Base>
+iterator_range<typename SCCNest<GraphT, SGT, GT, Base>::DepthFirstIterator>
+scc_depth_first(SCCNest<GraphT, SGT, GT, Base> &SCC) {
+  return {scc_df_begin(SCC), scc_df_end(SCC)};
+}
+
+template <class GraphT, class SGT, class GT, class Base>
+void SCCNest<GraphT, SGT, GT, Base>::buildMap() {
+  for (NestedSCCT &SCC : scc_depth_first(*this))
+    for (typename NestedSCCT::Element &E : SCC.SCCs)
+      if (E.getNested() == nullptr)
+        map.try_emplace(E.getBaseNode(), ComponentRef{&SCC, SCC.index(E)});
+}
+
+//===----------------------------------------------------------------------===//
+// Additional debugging support
+//===----------------------------------------------------------------------===//
+
+template <class GraphT, class SGT, class GT, class Base>
+void NestedSCC<GraphT, SGT, GT, Base>::dump(llvm::raw_ostream &OS, bool all) {
+  OS << "Nested SCC\n";
+  DenseMap<NestedSCC *, unsigned> number;
+  unsigned i = 0;
+  for (NestedSCC &cur : scc_depth_first(*this))
+    number[&cur] = i++;
+
+  for (NestedSCC &cur : scc_depth_first(*this)) {
+    unsigned N = cur.SCCs.size();
+    unsigned i = number[&cur];
+    for (unsigned j = 0; j < N; j++) {
+      OS << i << " " << j;
+      auto &C = cur.at(j);
+      if (!C.getNested()) {
+        OS << " " << C.getBaseNode()->getName();
+      } else {
+        auto &E = C.getNested()->at(0);
+        OS << " {{" << number[C.getNested()] << " "
+           << E.getBaseNode()->getName() << " }}";
+      }
+      OS << "\n";
+    }
+    if (!all)
+      break;
+  }
+}
+
+} // namespace llvm
+#endif

unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   IteratorTest.cpp
   MakeUniqueTest.cpp
   MappedIteratorTest.cpp
   MapVectorTest.cpp
+  NestedSCCTest.cpp # facebook T38406375
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   PriorityWorklistTest.cpp

unittests/ADT/NestedSCCTest.cpp

+//===----- llvm/unittest/ADT/NestedSCC.cpp - NestedSCC tests --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// facebook T38406375
+
+#include "llvm/ADT/NestedSCC.h"
+#include "SimpleGraph.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "gtest/gtest.h"
+#include <limits.h>
+
+#define DEBUG_NESTEDSCC_TEST 0
+using namespace llvm;
+using namespace simple;
+namespace llvm {
+namespace {
+class SimpleRNG {
+  uint64_t state;
+
+public:
+  SimpleRNG(uint64_t seed) : state(seed) {}
+  unsigned next(unsigned range) {
+    state = (state * 1664525 + 1013904223);
+    return state % range;
+  }
+};
+} // namespace
+
+using RNG = SimpleRNG;
+using NodeType = Graph::NodeType;
+
+#if DEBUG_NESTEDSCC_TEST
+static void dump(const Graph &G) {
+  dbgs() << "\n";
+  for (unsigned idx = 0; idx < G.size(); idx++) {
+    NodeType *Node = G.getNode(idx);
+    dbgs() << "node " << idx << " [ " << Node->label() << " ]:";
+    for (NodeType *Succ : children(Node))
+      dbgs() << " " << Succ->index();
+    dbgs() << "\n";
+  }
+}
+#endif
+
+// Build a random DAG with N nodes with a single
+// and a sink exit where every node is on somepath
+// from entry to exit
+static Graph buildDagGraph(unsigned N, RNG *rng) {
+  Graph G(N);
+  for (unsigned i = 1; i < N - 1; i++) {
+    unsigned pred = rng->next(i);
+    unsigned succ = i + 1 + rng->next(N - i - 1);
+    G.addEdge(pred, i);
+    G.addEdge(i, succ);
+  }
+  return G;
+}
+
+using Edge = std::pair<unsigned, unsigned>;
+using BackEdgeSet = DenseSet<Edge>;
+
+// expand node Idx into a loop with N nodes.
+// Add a back edge into Idx and insert that edge into backEdges
+static void makeLoop(Graph &G, unsigned idx, unsigned N, RNG *rng,
+                     DenseMap<unsigned, unsigned> *loopMap,
+                     BackEdgeSet *backEdges, unsigned loopNumber) {
+
+  // Build a random graph,
+  // Copy it as a subgraph where we unify its entry node
+  //    with Idx in G.
+  // The copy of the exit node has a back edge to Idx
+  // Randomly place original successors from Idx to nodes
+  //    in G.
+
+  // These loops are all reducible which makes it easy
+  // to identify via labels node which are in the same loop.
+  // If we create irreducible loops, then they can be treated
+  // as a nest of loops depending on which node is chosen as
+  // the "entry"
+  Graph S = buildDagGraph(N, rng);
+
+  // Save a copy and clear successor for Idx
+  SmallVector<unsigned, 16> successors(std::move(G.successors(idx)));
+
+  SmallVector<unsigned, 32> Map(N);
+  Map[0] = idx;
+  (*loopMap)[idx] = loopNumber;
+  for (unsigned i = 1; i < N; i++) {
+    Map[i] = G.addNode()->index();
+    (*loopMap)[Map[i]] = loopNumber;
+  }
+
+  for (unsigned i = 0; i < N - 1; i++)
+    for (unsigned succ : S.getNode(i)->successors())
+      G.addEdge(Map[i], Map[succ]);
+
+  // Randomly select exits which branch to the
+  // original successors
+  for (unsigned s : successors) {
+    unsigned exit = Map[rng->next(N)];
+    G.addEdge(exit, s);
+    // If an edge was a back edge, then that edge
+    // is no longer an edge (and hence not a backedge)
+    // but this new edge is a back edge.
+    if (backEdges->erase({idx, s}))
+      backEdges->insert({exit, s});
+  }
+
+  // Make a loop by adding a back edge
+  unsigned entryIdx = Map.front();
+  unsigned exitIdx = Map.back();
+  G.addEdge(exitIdx, entryIdx);
+  backEdges->insert({exitIdx, entryIdx});
+}
+
+using SimpleSubGraph = SubGraph<GraphTraits<Graph *>>;
+template <> struct GraphTraits<SimpleSubGraph *> {
+  using NodeRef = SimpleSubGraph::NodeRef;
+  static NodeRef getEntryNode(const SimpleSubGraph &G) {
+    return G.getEntryNode();
+  }
+  using ChildIteratorType = SimpleSubGraph::ChildIterator;
+  static ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N);
+  }
+  static ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType(GraphTraits<Graph *>::child_end(N.first),
+                             N.second);
+  }
+};
+
+using SG = SubGraph<GraphTraits<Graph *>>;
+using SCCNestT = SCCNest<Graph *, GraphTraits<SG *>, GraphTraits<Graph *>>;
+using NestedSCCT = SCCNestT::NestedSCCT;
+using ComponentRef = SCCNestT::ComponentRef;
+// Find common ancestor of two SCC's
+static NestedSCCT *common(NestedSCCT *x, NestedSCCT *y) {
+  unsigned xd = x->getDepth();
+  unsigned yd = y->getDepth();
+  for (; xd > yd; xd -= 1)
+    x = x->getParent();
+  for (; yd > xd; yd -= 1)
+    y = y->getParent();
+  while (x != y) {
+    assert(x->getDepth() > 0);
+    x = x->getParent();
+    y = y->getParent();
+  }
+  return x;
+}
+// Map component ref to parent node in "C"
+static ComponentRef getParent(ComponentRef r, NestedSCCT *C) {
+  while (r.first != C) {
+    r.second = r.first->getParentIndex();
+    r.first = r.first->getParent();
+  }
+  return r;
+}
+
+TEST(NestedSCCTest, EnumeratedGraphs) {
+  // Enumerate graphs with loops:
+  // Enumerate a DAG with "sqrt(N)" nodes.
+  // Randomy pick nodes to expand into loops unto
+  // we reach size N
+  SimpleRNG RNG(1234);
+  // Record where we expanded nodes into loops
+  struct LoopInfo {
+    unsigned Idx;
+    unsigned Size;
+    unsigned ParentLoop;
+  };
+  RNG.next(1);
+  const unsigned MIN_GRAPH_SIZE = 40;
+  // Run a number of graphs
+  for (unsigned i = 0; i < 5; i++) {
+    SmallVector<LoopInfo, 20> Loops;
+    Graph G = buildDagGraph(10, &RNG);
+    DenseSet<unsigned> isLoopEntry;
+    DenseMap<unsigned, unsigned> node2loopMap;
+    auto getLoop = [&node2loopMap](NodeType *N) {
+      return node2loopMap.try_emplace(N->index(), 0).first->second;
+    };
+    BackEdgeSet backEdges;
+    Loops.push_back({0, G.size(), std::numeric_limits<unsigned>::max()});
+
+    // Pick a node and expand it into a loop.
+    // Avoid picking the same node twice so that the
+    // LoopInfo is simple to maintain.
+    while (G.size() < MIN_GRAPH_SIZE) {
+      unsigned loopEntry = 1 + RNG.next(G.size() - 2);
+      if (!isLoopEntry.insert(loopEntry).second)
+        continue;
+      unsigned loopSize = 4 + RNG.next(4);
+      unsigned loopParent = getLoop(G.getNode(loopEntry));
+#if DEBUG_NESTEDSCC_TEST
+      dbgs() << "loop: " << loopEntry << " size " << loopEntry << " in "
+             << loopParent << "\n";
+#endif
+      makeLoop(G, loopEntry, loopSize, &RNG, &node2loopMap, &backEdges,
+               static_cast<unsigned>(Loops.size()));
+      Loops.push_back({loopEntry, loopSize, loopParent});
+    }
+#if DEBUG_NESTEDSCC_TEST
+    dump(G);
+#endif
+    SCCNestT scc(&G);
+#if DEBUG_NESTEDSCC_TEST
+    scc.dump(dbgs());
+#endif
+
+    // Verification steps...
+    // First, all nodes in a loop are mapped to the same component
+    DenseMap<NestedSCCT *, unsigned> labelMap;
+    for (NodeType &Node : G.nodes()) {
+      NestedSCCT *C = scc.getComponent(&Node).first;
+      ASSERT_NE(C, nullptr); // every node is reachable
+      // All nodes in a component should have the same label...
+      auto pair = labelMap.try_emplace(C, getLoop(&Node));
+      if (!pair.second) {
+        // All nodes with the same label are in the same component
+        EXPECT_EQ(pair.first->getSecond(), getLoop(&Node));
+      }
+      NestedSCCT *P = C->getParent();
+      if (!P) {
+        // the root node has label 0
+        EXPECT_EQ(getLoop(&Node), 0u);
+        continue;
+      }
+      unsigned parentLabel = Loops[getLoop(&Node)].ParentLoop;
+      pair = labelMap.try_emplace(P, parentLabel);
+      if (!pair.second) {
+        // The parent is the same as in the loop structure
+        EXPECT_EQ(pair.first->getSecond(), parentLabel);
+      }
+    }
+
+    DenseSet<NestedSCCT *> visited;
+    // Verify iteration over and within regions
+    for (NestedSCCT &C : scc_depth_first(scc)) {
+      auto iter = labelMap.find(&C);
+      ASSERT_TRUE(iter != labelMap.end());
+      if (NestedSCCT *P = C.getParent()) {
+        ASSERT_TRUE(visited.count(P));
+      }
+      visited.insert(&C);
+      unsigned componentLabel = iter->getSecond();
+      for (const NestedSCCT::Element &E : C.getSCCs()) {
+        if (E.getNested())
+          continue;
+        // leaf noes have the same label as the component
+        EXPECT_EQ(componentLabel, getLoop(E.getBaseNode()));
+      }
+    }
+
+    // Verify that SCC nodes are topologically ordered with
+    // respect to the non-backedge in the underlying graph
+    for (NodeType &source : G.nodes()) {
+      unsigned SrcIdx = source.index();
+      ComponentRef sourceComponent = scc.getComponent(&source);
+      for (NodeType *sink : children(&source)) {
+        // Map source and sink to a common SCC
+        SCCNestT::ComponentRef sinkComponent = scc.getComponent(sink);
+        NestedSCCT *commonComponent =
+            common(sourceComponent.first, sinkComponent.first);
+        ComponentRef SourceR = getParent(sourceComponent, commonComponent);
+        ComponentRef SinkR = getParent(sinkComponent, commonComponent);
+        if (backEdges.count({SrcIdx, sink->index()})) {
+          // All loops are reducible so back edges go to the entry
+          EXPECT_EQ(SinkR.second, 0u);
+          continue;
+        }
+        EXPECT_LE(SourceR.second, SinkR.second);
+      }
+    }
+  }
+}
+} // namespace llvm

unittests/ADT/SimpleGraph.h

+//===- llvm/unittest/ADT/TestGraph.h - Graph for testing ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Common unbounded graph data structure for testing.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_ADT_TEST_GRAPH_H
+#define LLVM_UNITTESTS_ADT_TEST_GRAPH_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallVector.h"
+#include <cassert>
+#include <climits>
+#include <string>
+#include <utility>
+
+namespace llvm {
+namespace simple {
+class Graph {
+  void assertValid(unsigned Idx) const {
+    assert(Idx < size() && "Invalid node index!");
+  }
+  using SuccesorVec = SmallVectorImpl<unsigned>;
+
+public:
+  /// NodeSubset - A subset of the graph's nodes.
+  class NodeType {
+    Graph *G;
+    /// Index -- is the index of this node in G->Nodes
+    unsigned Index;
+    /// Indicies (in G->Nodes) of successors of this node.
+    SmallVector<unsigned, 16> Successors;
+
+  public:
+    /// NodeSubset - Default constructor, creates an empty subset.
+    NodeType(Graph *G, unsigned Index) : G(G), Index(Index) {}
+    unsigned index() const { return Index; }
+
+    /// AddNode - Add the node with the given index to the subset.
+    bool addSuccessor(unsigned Index) {
+      G->assertValid(Index);
+      for (unsigned S : Successors)
+        if (S == Index)
+          return false;
+      Successors.push_back(Index);
+      return true;
+    }
+
+    const SuccesorVec &successors() const { return Successors; }
+    SuccesorVec &successors() { return Successors; }
+  };
+
+private:
+  /// Nodes - The list of nodes for this graph.
+  SmallVector<NodeType, 64> Nodes;
+
+public:
+  /// Graph - Default constructor.  Creates an empty graph.
+  Graph(unsigned N) {
+    for (unsigned i = 0; i != N; ++i)
+      addNode();
+  }
+  unsigned size() const { return static_cast<unsigned>(Nodes.size()); }
+  NodeType *addNode() {
+    unsigned result = size();
+    Nodes.emplace_back(this, result);
+    return getNode(result);
+  }
+
+  /// addEdge - Add an edge from the node with index FromIdx to the node with
+  /// index ToIdx.
+  void addEdge(unsigned FromIdx, unsigned ToIdx) {
+    assertValid(FromIdx);
+    Nodes[FromIdx].addSuccessor(ToIdx);
+  }
+
+  /// getNode - Get a pointer to the node with the given index.
+  NodeType *getNode(unsigned Idx) const {
+    assertValid(Idx);
+    // The constant cast is needed when working with GraphTraits, which insists
+    // on taking a constant Graph.
+    return const_cast<NodeType *>(&Nodes[Idx]);
+  }
+
+  /// ChildIterator - Visit all children of a node.
+  class ChildIterator {
+    friend class Graph;
+
+    /// FirstNode - Pointer to first node in the graph's Nodes array.
+    NodeType *FirstNode;
+    /// Children -- base iterator over succesor indices
+    using It = SuccesorVec::const_iterator;
+    It Children;
+
+    ChildIterator(); // Disable default constructor.
+  protected:
+    ChildIterator(NodeType *F, It Children)
+        : FirstNode(F), Children(Children) {}
+
+  public:
+    /// ChildIterator - Copy constructor.
+    ChildIterator(const ChildIterator &other)
+        : FirstNode(other.FirstNode), Children(other.Children) {}
+
+    /// Comparison operators.
+    bool operator==(const ChildIterator &other) const {
+      return other.FirstNode == this->FirstNode &&
+             other.Children == this->Children;
+    }
+    bool operator!=(const ChildIterator &other) const {
+      return !(*this == other);
+    }
+
+    /// Prefix increment operator.
+    ChildIterator &operator++() {
+      Children++;
+      return *this;
+    }
+
+    /// Postfix increment operator.
+    ChildIterator operator++(int) {
+      ChildIterator Result(*this);
+      ++(*this);
+      return Result;
+    }
+
+    /// Dereference operator.
+    NodeType *operator*() { return FirstNode + *Children; }
+  };
+
+  /// child_begin - Return an iterator pointing to the first child of the given
+  /// node.
+  static ChildIterator child_begin(NodeType *Parent) {
+    return ChildIterator(Parent - Parent->index(),
+                         Parent->successors().begin());
+  }
+
+  /// child_end - Return the end iterator for children of the given node.
+  static ChildIterator child_end(NodeType *Parent) {
+    return ChildIterator(Parent - Parent->index(), Parent->successors().end());
+  }
+
+  SuccesorVec &successors(unsigned Idx) { return Nodes[Idx].successors(); }
+  SmallVectorImpl<NodeType> &nodes() { return Nodes; }
+};
+
+iterator_range<Graph::ChildIterator> children(Graph::NodeType *Node) {
+  return {Graph::child_begin(Node), Graph::child_end(Node)};
+}
+
+} // namespace simple
+
+template <> struct GraphTraits<simple::Graph *> {
+  using Graph = simple::Graph;
+  typedef typename Graph::NodeType *NodeRef;
+  typedef typename Graph::ChildIterator ChildIteratorType;
+
+  static NodeRef getEntryNode(const Graph *G) { return G->getNode(0); }
+  static ChildIteratorType child_begin(NodeRef Node) {
+    return Graph::child_begin(Node);
+  }
+  static ChildIteratorType child_end(NodeRef Node) {
+    return Graph::child_end(Node);
+  }
+};
+
+} // End namespace llvm
+
+#endif