Index: llvm/include/llvm/ADT/DirectedGraph.h
===================================================================
--- /dev/null
+++ llvm/include/llvm/ADT/DirectedGraph.h
@@ -0,0 +1,297 @@
+//===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the interface for a directed graph.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_DIRECTEDGRAPH_H
+#define LLVM_ADT_DIRECTEDGRAPH_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+
+/// Represent an edge in the directed graph.
+/// The edge contains the target node it connects to.
+template <class NodeType, class EdgeType> class DGEdge {
+public:
+  /// Create an edge pointing to the given node \p N.
+  explicit DGEdge(NodeType &N) : Node(N) {}
+
+  explicit DGEdge(const DGEdge<NodeType, EdgeType> &E) : Node(E.Node) {}
+  DGEdge<NodeType, EdgeType> &operator=(const DGEdge<NodeType, EdgeType> &E) {
+    Node = E.Node;
+    return *this;
+  }
+
+  /// Static polymorphism: delegate implementation (via isEqualTo) to the
+  /// derived class.
+  bool operator==(const EdgeType &E) const {
+    return static_cast<const EdgeType *>(this)->isEqualTo(E);
+  }
+  bool operator!=(const EdgeType &E) const { return !operator==(E); }
+
+  /// Retrieve the target node this edge connects to.
+  const NodeType &getNode() const { return Node; }
+  NodeType &getNode() {
+    return const_cast<NodeType &>(
+        static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getNode());
+  }
+
+protected:
+  // As the default implementation use address comparison for equality.
+  bool isEqualTo(const EdgeType &E) const { return this == &E; }
+
+  NodeType &Node; // the target node this edge connects to
+};
+
+/// Represent a node in the directed graph.
+/// The node has a (possibly empty) list of outgoing edges.
+template <class NodeType, class EdgeType> class DGNode {
+public:
+  using EdgeList = SmallVector<EdgeType *, 4>;
+  using iterator = typename EdgeList::iterator;
+  using const_iterator = typename EdgeList::const_iterator;
+
+  // Create a node with a single outgoing edge \p E.
+  explicit DGNode(EdgeType &E) : Edges() { Edges.push_back(&E); }
+  DGNode() = default;
+
+  explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {}
+  DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {}
+
+  DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &N) {
+    Edges = N.Edges;
+    return *this;
+  }
+
+  /// Static polymorphism: delegate implementation (via isEqualTo) to the
+  /// derived class.
+  bool operator==(const NodeType &N) const {
+    return static_cast<const NodeType *>(this)->isEqualTo(N);
+  }
+  bool operator!=(const NodeType &N) const { return !operator==(N); }
+
+  const_iterator begin() const { return Edges.begin(); }
+  const_iterator end() const { return Edges.end(); }
+  iterator begin() { return Edges.begin(); }
+  iterator end() { return Edges.end(); }
+  const EdgeType &front() const {
+    assert(!Edges.empty() && "Node has no outgoing edges.");
+    return *Edges.front();
+  }
+  EdgeType &front() {
+    return const_cast<EdgeType &>(static_cast<const DGNode &>(*this).front());
+  }
+  const EdgeType &back() const {
+    assert(!Edges.empty() && "Node has no outgoing edges.");
+    return *Edges.back();
+  }
+  EdgeType &back() {
+    return const_cast<EdgeType &>(static_cast<const DGNode &>(*this).back());
+  }
+
+  /// Collect in \p EL, all the edges from this node to \p N.
+  /// Return true if at least one edge was found, and false otherwise.
+  /// Note that this implementation allows more than one edge to connect
+  /// a given pair of nodes.
+  bool findEdgesTo(const NodeType &N, EdgeList &EL) const {
+    assert(EL.empty() && "Expected the list of edges to be empty.");
+    for (auto *E : Edges)
+      if (E->getNode() == N)
+        EL.push_back(E);
+    return !EL.empty();
+  }
+
+  /// Add the given edge \p E to this node, if it doesn't exist already. Returns
+  /// true if the edge is added and false otherwise.
+  bool addEdge(EdgeType &E) {
+    if (llvm::find_if(Edges, [&E](const EdgeType *Edge) {
+          return *Edge == E;
+        }) != Edges.end())
+      return false;
+    Edges.push_back(&E);
+    return true;
+  }
+
+  /// Remove the given edge \p E from this node, if it exists. Returns true if
+  /// the edge was removed and false otherwise.
+  bool removeEdge(EdgeType &E) {
+    auto IT =
+        llvm::find_if(Edges, [&E](const EdgeType *Edge) { return *Edge == E; });
+    if (IT == Edges.end())
+      return false;
+    Edges.erase(IT);
+    return true;
+  }
+
+  /// Test whether there is an edge that goes from this node to \p N.
+  bool hasEdgeTo(const NodeType &N) const {
+    return (findEdgeTo(N) != Edges.end());
+  }
+
+  /// Retrieve the outgoing edges for the node.
+  const EdgeList &getEdges() const { return Edges; }
+  EdgeList &getEdges() {
+    return const_cast<EdgeList &>(
+        static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
+  }
+
+  /// Clear the outgoing edges.
+  void clear() { Edges.clear(); }
+
+protected:
+  // As the default implementation use address comparison for equality.
+  bool isEqualTo(const NodeType &N) const { return this == &N; }
+
+  /// Find an edge to \p N. If more than one edge exists, this will return
+  /// the first one in the list of edges.
+  const_iterator findEdgeTo(const NodeType &N) const {
+    return llvm::find_if(Edges,
+                         [&N](const EdgeType *E) { return E->getNode() == N; });
+  }
+
+  EdgeList Edges; // outgoing edges
+};
+
+/// Directed graph
+///
+/// The graph is represented by a table of nodes.
+/// Each node contains a (possibly empty) list of outgoing edges.
+/// Each edge contains the target node it connects to.
+template <class NodeType, class EdgeType> class DirectedGraph {
+public:
+  using NodeList = SmallVector<NodeType *, 10>;
+  using EdgeList = typename NodeType::EdgeList;
+  using iterator = typename NodeList::iterator;
+  using const_iterator = typename NodeList::const_iterator;
+  using DGraphType = DirectedGraph<NodeType, EdgeType>;
+
+  DirectedGraph() = default;
+  explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
+  DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {}
+  DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {}
+  DGraphType &operator=(const DGraphType &G) {
+    Nodes = G.Nodes;
+    return *this;
+  }
+
+  const_iterator begin() const { return Nodes.begin(); }
+  const_iterator end() const { return Nodes.end(); }
+  iterator begin() { return Nodes.begin(); }
+  iterator end() { return Nodes.end(); }
+  const NodeType &front() const {
+    assert(!Nodes.empty() && "Graph has no nodes.");
+    return *Nodes.front();
+  }
+  NodeType &front() {
+    return const_cast<NodeType &>(
+        static_cast<const DGraphType &>(*this).front());
+  }
+  const NodeType &back() const {
+    assert(!Nodes.empty() && "Graph has no nodes.");
+    return *Nodes.back();
+  }
+  NodeType &back() {
+    return const_cast<NodeType &>(
+        static_cast<const DGraphType &>(*this).back());
+  }
+
+  unsigned size() const { return Nodes.size(); }
+
+  /// Find the given node \p N in the table.
+  const_iterator findNode(const NodeType &N) const {
+    return llvm::find_if(Nodes,
+                         [&N](const NodeType *Node) { return *Node == N; });
+  }
+  iterator findNode(const NodeType &N) {
+    return const_cast<iterator>(
+        static_cast<const DGraphType &>(*this).findNode(N));
+  }
+
+  /// Add the given node \p N to the graph if it is not already present.
+  bool addNode(NodeType &N) {
+    if (findNode(N) != Nodes.end())
+      return false;
+    Nodes.push_back(&N);
+    return true;
+  }
+
+  /// Collect in \p EL all edges that are coming into node \p N. Return true
+  /// if at least one edge was found, and false otherwise.
+  bool findIncomingEdgesToNode(const NodeType &N, EdgeList &EL) const {
+    assert(EL.empty() && "Expected the list of edges to be empty.");
+    for (auto *Node : Nodes) {
+      if (*Node == N)
+        continue;
+      EdgeList TempList;
+      Node->findEdgesTo(N, TempList);
+      EL.insert(EL.end(), TempList.begin(), TempList.end());
+    }
+    return !EL.empty();
+  }
+
+  /// Remove the given node \p N from the graph. If the node has incoming or
+  /// outgoing edges, they are also removed. Return true if the node was found
+  /// and then removed, and false if the node was not found in the graph to
+  /// begin with.
+  bool removeNode(NodeType &N) {
+    iterator IT = findNode(N);
+    if (IT == Nodes.end())
+      return false;
+    // Remove incoming edges.
+    for (auto *Node : Nodes) {
+      if (*Node == N)
+        continue;
+      EdgeList EL;
+      Node->findEdgesTo(N, EL);
+      for (auto *E : EL)
+        Node->removeEdge(*E);
+    }
+    N.clear();
+    Nodes.erase(IT);
+    return true;
+  }
+
+  /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
+  /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
+  /// not already connected to \p Dst via \p E, and false otherwise.
+  bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
+    assert(findNode(Src) != Nodes.end() && "Src node should be present.");
+    assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
+    assert((E.getNode() == Dst) &&
+           "Target of the given edge does not match Dst.");
+
+    EdgeList EL;
+    Src.findEdgesTo(Dst, EL);
+    if (llvm::find_if(EL, [&E](const EdgeType *Edge) { return *Edge == E; }) !=
+        EL.end())
+      return false;
+    Src.addEdge(E);
+    return true;
+  }
+
+  /// Remove all the nodes and edges from the graph.
+  /// Note that this function does not deallocate any nodes or edges.
+  void clear() {
+    for (NodeType *N : Nodes)
+      N->clear();
+    Nodes.clear();
+  }
+
+protected:
+  NodeList Nodes; // the nodes in the graph
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_DIRECTEDGRAPH_H