1 files changed, 445 insertions, 0 deletions
diff --git a/llvm/lib/Target/X86/ImmutableGraph.h b/llvm/lib/Target/X86/ImmutableGraph.h
new file mode 100644
index 000000000000..56738e9cfa73
--- /dev/null
+++ b/llvm/lib/Target/X86/ImmutableGraph.h
@@ -0,0 +1,445 @@
+//==========-- ImmutableGraph.h - A fast DAG implementation ---------=========//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+///
+/// Description: ImmutableGraph is a fast DAG implementation that cannot be
+/// modified, except by creating a new ImmutableGraph. ImmutableGraph is
+/// implemented as two arrays: one containing nodes, and one containing edges.
+/// The advantages to this implementation are two-fold:
+/// 1. Iteration and traversal operations benefit from cache locality.
+/// 2. Operations on sets of nodes/edges are efficient, and representations of
+///    those sets in memory are compact. For instance, a set of edges is
+///    implemented as a bit vector, wherein each bit corresponds to one edge in
+///    the edge array. This implies a lower bound of 64x spatial improvement
+///    over, e.g., an llvm::DenseSet or llvm::SmallSet. It also means that
+///    insert/erase/contains operations complete in negligible constant time:
+///    insert and erase require one load and one store, and contains requires
+///    just one load.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
+#define LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/STLExtras.h"
+#include <algorithm>
+#include <iterator>
+#include <utility>
+#include <vector>
+
+namespace llvm {
+
+template <typename NodeValueT, typename EdgeValueT> class ImmutableGraph {
+  using Traits = GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *>;
+  template <typename> friend class ImmutableGraphBuilder;
+
+public:
+  using node_value_type = NodeValueT;
+  using edge_value_type = EdgeValueT;
+  using size_type = int;
+  class Node;
+  class Edge {
+    friend class ImmutableGraph;
+    template <typename> friend class ImmutableGraphBuilder;
+
+    const Node *Dest;
+    edge_value_type Value;
+
+  public:
+    const Node *getDest() const { return Dest; };
+    const edge_value_type &getValue() const { return Value; }
+  };
+  class Node {
+    friend class ImmutableGraph;
+    template <typename> friend class ImmutableGraphBuilder;
+
+    const Edge *Edges;
+    node_value_type Value;
+
+  public:
+    const node_value_type &getValue() const { return Value; }
+
+    const Edge *edges_begin() const { return Edges; }
+    // Nodes are allocated sequentially. Edges for a node are stored together.
+    // The end of this Node's edges is the beginning of the next node's edges.
+    // An extra node was allocated to hold the end pointer for the last real
+    // node.
+    const Edge *edges_end() const { return (this + 1)->Edges; }
+    ArrayRef<Edge> edges() const {
+      return makeArrayRef(edges_begin(), edges_end());
+    }
+  };
+
+protected:
+  ImmutableGraph(std::unique_ptr<Node[]> Nodes, std::unique_ptr<Edge[]> Edges,
+                 size_type NodesSize, size_type EdgesSize)
+      : Nodes(std::move(Nodes)), Edges(std::move(Edges)), NodesSize(NodesSize),
+        EdgesSize(EdgesSize) {}
+  ImmutableGraph(const ImmutableGraph &) = delete;
+  ImmutableGraph(ImmutableGraph &&) = delete;
+  ImmutableGraph &operator=(const ImmutableGraph &) = delete;
+  ImmutableGraph &operator=(ImmutableGraph &&) = delete;
+
+public:
+  ArrayRef<Node> nodes() const { return makeArrayRef(Nodes.get(), NodesSize); }
+  const Node *nodes_begin() const { return nodes().begin(); }
+  const Node *nodes_end() const { return nodes().end(); }
+
+  ArrayRef<Edge> edges() const { return makeArrayRef(Edges.get(), EdgesSize); }
+  const Edge *edges_begin() const { return edges().begin(); }
+  const Edge *edges_end() const { return edges().end(); }
+
+  size_type nodes_size() const { return NodesSize; }
+  size_type edges_size() const { return EdgesSize; }
+
+  // Node N must belong to this ImmutableGraph.
+  size_type getNodeIndex(const Node &N) const {
+    return std::distance(nodes_begin(), &N);
+  }
+  // Edge E must belong to this ImmutableGraph.
+  size_type getEdgeIndex(const Edge &E) const {
+    return std::distance(edges_begin(), &E);
+  }
+
+  // FIXME: Could NodeSet and EdgeSet be templated to share code?
+  class NodeSet {
+    const ImmutableGraph &G;
+    BitVector V;
+
+  public:
+    NodeSet(const ImmutableGraph &G, bool ContainsAll = false)
+        : G{G}, V{static_cast<unsigned>(G.nodes_size()), ContainsAll} {}
+    bool insert(const Node &N) {
+      size_type Idx = G.getNodeIndex(N);
+      bool AlreadyExists = V.test(Idx);
+      V.set(Idx);
+      return !AlreadyExists;
+    }
+    void erase(const Node &N) {
+      size_type Idx = G.getNodeIndex(N);
+      V.reset(Idx);
+    }
+    bool contains(const Node &N) const {
+      size_type Idx = G.getNodeIndex(N);
+      return V.test(Idx);
+    }
+    void clear() { V.reset(); }
+    size_type empty() const { return V.none(); }
+    /// Return the number of elements in the set
+    size_type count() const { return V.count(); }
+    /// Return the size of the set's domain
+    size_type size() const { return V.size(); }
+    /// Set union
+    NodeSet &operator|=(const NodeSet &RHS) {
+      assert(&this->G == &RHS.G);
+      V |= RHS.V;
+      return *this;
+    }
+    /// Set intersection
+    NodeSet &operator&=(const NodeSet &RHS) {
+      assert(&this->G == &RHS.G);
+      V &= RHS.V;
+      return *this;
+    }
+    /// Set disjoint union
+    NodeSet &operator^=(const NodeSet &RHS) {
+      assert(&this->G == &RHS.G);
+      V ^= RHS.V;
+      return *this;
+    }
+
+    using index_iterator = typename BitVector::const_set_bits_iterator;
+    index_iterator index_begin() const { return V.set_bits_begin(); }
+    index_iterator index_end() const { return V.set_bits_end(); }
+    void set(size_type Idx) { V.set(Idx); }
+    void reset(size_type Idx) { V.reset(Idx); }
+
+    class iterator {
+      const NodeSet &Set;
+      size_type Current;
+
+      void advance() {
+        assert(Current != -1);
+        Current = Set.V.find_next(Current);
+      }
+
+    public:
+      iterator(const NodeSet &Set, size_type Begin)
+          : Set{Set}, Current{Begin} {}
+      iterator operator++(int) {
+        iterator Tmp = *this;
+        advance();
+        return Tmp;
+      }
+      iterator &operator++() {
+        advance();
+        return *this;
+      }
+      Node *operator*() const {
+        assert(Current != -1);
+        return Set.G.nodes_begin() + Current;
+      }
+      bool operator==(const iterator &other) const {
+        assert(&this->Set == &other.Set);
+        return this->Current == other.Current;
+      }
+      bool operator!=(const iterator &other) const { return !(*this == other); }
+    };
+
+    iterator begin() const { return iterator{*this, V.find_first()}; }
+    iterator end() const { return iterator{*this, -1}; }
+  };
+
+  class EdgeSet {
+    const ImmutableGraph &G;
+    BitVector V;
+
+  public:
+    EdgeSet(const ImmutableGraph &G, bool ContainsAll = false)
+        : G{G}, V{static_cast<unsigned>(G.edges_size()), ContainsAll} {}
+    bool insert(const Edge &E) {
+      size_type Idx = G.getEdgeIndex(E);
+      bool AlreadyExists = V.test(Idx);
+      V.set(Idx);
+      return !AlreadyExists;
+    }
+    void erase(const Edge &E) {
+      size_type Idx = G.getEdgeIndex(E);
+      V.reset(Idx);
+    }
+    bool contains(const Edge &E) const {
+      size_type Idx = G.getEdgeIndex(E);
+      return V.test(Idx);
+    }
+    void clear() { V.reset(); }
+    bool empty() const { return V.none(); }
+    /// Return the number of elements in the set
+    size_type count() const { return V.count(); }
+    /// Return the size of the set's domain
+    size_type size() const { return V.size(); }
+    /// Set union
+    EdgeSet &operator|=(const EdgeSet &RHS) {
+      assert(&this->G == &RHS.G);
+      V |= RHS.V;
+      return *this;
+    }
+    /// Set intersection
+    EdgeSet &operator&=(const EdgeSet &RHS) {
+      assert(&this->G == &RHS.G);
+      V &= RHS.V;
+      return *this;
+    }
+    /// Set disjoint union
+    EdgeSet &operator^=(const EdgeSet &RHS) {
+      assert(&this->G == &RHS.G);
+      V ^= RHS.V;
+      return *this;
+    }
+
+    using index_iterator = typename BitVector::const_set_bits_iterator;
+    index_iterator index_begin() const { return V.set_bits_begin(); }
+    index_iterator index_end() const { return V.set_bits_end(); }
+    void set(size_type Idx) { V.set(Idx); }
+    void reset(size_type Idx) { V.reset(Idx); }
+
+    class iterator {
+      const EdgeSet &Set;
+      size_type Current;
+
+      void advance() {
+        assert(Current != -1);
+        Current = Set.V.find_next(Current);
+      }
+
+    public:
+      iterator(const EdgeSet &Set, size_type Begin)
+          : Set{Set}, Current{Begin} {}
+      iterator operator++(int) {
+        iterator Tmp = *this;
+        advance();
+        return Tmp;
+      }
+      iterator &operator++() {
+        advance();
+        return *this;
+      }
+      Edge *operator*() const {
+        assert(Current != -1);
+        return Set.G.edges_begin() + Current;
+      }
+      bool operator==(const iterator &other) const {
+        assert(&this->Set == &other.Set);
+        return this->Current == other.Current;
+      }
+      bool operator!=(const iterator &other) const { return !(*this == other); }
+    };
+
+    iterator begin() const { return iterator{*this, V.find_first()}; }
+    iterator end() const { return iterator{*this, -1}; }
+  };
+
+private:
+  std::unique_ptr<Node[]> Nodes;
+  std::unique_ptr<Edge[]> Edges;
+  size_type NodesSize;
+  size_type EdgesSize;
+};
+
+template <typename GraphT> class ImmutableGraphBuilder {
+  using node_value_type = typename GraphT::node_value_type;
+  using edge_value_type = typename GraphT::edge_value_type;
+  static_assert(
+      std::is_base_of<ImmutableGraph<node_value_type, edge_value_type>,
+                      GraphT>::value,
+      "Template argument to ImmutableGraphBuilder must derive from "
+      "ImmutableGraph<>");
+  using size_type = typename GraphT::size_type;
+  using NodeSet = typename GraphT::NodeSet;
+  using Node = typename GraphT::Node;
+  using EdgeSet = typename GraphT::EdgeSet;
+  using Edge = typename GraphT::Edge;
+  using BuilderEdge = std::pair<edge_value_type, size_type>;
+  using EdgeList = std::vector<BuilderEdge>;
+  using BuilderVertex = std::pair<node_value_type, EdgeList>;
+  using VertexVec = std::vector<BuilderVertex>;
+
+public:
+  using BuilderNodeRef = size_type;
+
+  BuilderNodeRef addVertex(const node_value_type &V) {
+    auto I = AdjList.emplace(AdjList.end(), V, EdgeList{});
+    return std::distance(AdjList.begin(), I);
+  }
+
+  void addEdge(const edge_value_type &E, BuilderNodeRef From,
+               BuilderNodeRef To) {
+    AdjList[From].second.emplace_back(E, To);
+  }
+
+  bool empty() const { return AdjList.empty(); }
+
+  template <typename... ArgT> std::unique_ptr<GraphT> get(ArgT &&... Args) {
+    size_type VertexSize = AdjList.size(), EdgeSize = 0;
+    for (const auto &V : AdjList) {
+      EdgeSize += V.second.size();
+    }
+    auto VertexArray =
+        std::make_unique<Node[]>(VertexSize + 1 /* terminator node */);
+    auto EdgeArray = std::make_unique<Edge[]>(EdgeSize);
+    size_type VI = 0, EI = 0;
+    for (; VI < VertexSize; ++VI) {
+      VertexArray[VI].Value = std::move(AdjList[VI].first);
+      VertexArray[VI].Edges = &EdgeArray[EI];
+      auto NumEdges = static_cast<size_type>(AdjList[VI].second.size());
+      for (size_type VEI = 0; VEI < NumEdges; ++VEI, ++EI) {
+        auto &E = AdjList[VI].second[VEI];
+        EdgeArray[EI].Value = std::move(E.first);
+        EdgeArray[EI].Dest = &VertexArray[E.second];
+      }
+    }
+    assert(VI == VertexSize && EI == EdgeSize && "ImmutableGraph malformed");
+    VertexArray[VI].Edges = &EdgeArray[EdgeSize]; // terminator node
+    return std::make_unique<GraphT>(std::move(VertexArray),
+                                    std::move(EdgeArray), VertexSize, EdgeSize,
+                                    std::forward<ArgT>(Args)...);
+  }
+
+  template <typename... ArgT>
+  static std::unique_ptr<GraphT> trim(const GraphT &G, const NodeSet &TrimNodes,
+                                      const EdgeSet &TrimEdges,
+                                      ArgT &&... Args) {
+    size_type NewVertexSize = G.nodes_size() - TrimNodes.count();
+    size_type NewEdgeSize = G.edges_size() - TrimEdges.count();
+    auto NewVertexArray =
+        std::make_unique<Node[]>(NewVertexSize + 1 /* terminator node */);
+    auto NewEdgeArray = std::make_unique<Edge[]>(NewEdgeSize);
+
+    // Walk the nodes and determine the new index for each node.
+    size_type NewNodeIndex = 0;
+    std::vector<size_type> RemappedNodeIndex(G.nodes_size());
+    for (const Node &N : G.nodes()) {
+      if (TrimNodes.contains(N))
+        continue;
+      RemappedNodeIndex[G.getNodeIndex(N)] = NewNodeIndex++;
+    }
+    assert(NewNodeIndex == NewVertexSize &&
+           "Should have assigned NewVertexSize indices");
+
+    size_type VertexI = 0, EdgeI = 0;
+    for (const Node &N : G.nodes()) {
+      if (TrimNodes.contains(N))
+        continue;
+      NewVertexArray[VertexI].Value = N.getValue();
+      NewVertexArray[VertexI].Edges = &NewEdgeArray[EdgeI];
+      for (const Edge &E : N.edges()) {
+        if (TrimEdges.contains(E))
+          continue;
+        NewEdgeArray[EdgeI].Value = E.getValue();
+        size_type DestIdx = G.getNodeIndex(*E.getDest());
+        size_type NewIdx = RemappedNodeIndex[DestIdx];
+        assert(NewIdx < NewVertexSize);
+        NewEdgeArray[EdgeI].Dest = &NewVertexArray[NewIdx];
+        ++EdgeI;
+      }
+      ++VertexI;
+    }
+    assert(VertexI == NewVertexSize && EdgeI == NewEdgeSize &&
+           "Gadget graph malformed");
+    NewVertexArray[VertexI].Edges = &NewEdgeArray[NewEdgeSize]; // terminator
+    return std::make_unique<GraphT>(std::move(NewVertexArray),
+                                    std::move(NewEdgeArray), NewVertexSize,
+                                    NewEdgeSize, std::forward<ArgT>(Args)...);
+  }
+
+private:
+  VertexVec AdjList;
+};
+
+template <typename NodeValueT, typename EdgeValueT>
+struct GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *> {
+  using GraphT = ImmutableGraph<NodeValueT, EdgeValueT>;
+  using NodeRef = typename GraphT::Node const *;
+  using EdgeRef = typename GraphT::Edge const &;
+
+  static NodeRef edge_dest(EdgeRef E) { return E.getDest(); }
+  using ChildIteratorType =
+      mapped_iterator<typename GraphT::Edge const *, decltype(&edge_dest)>;
+
+  static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); }
+  static ChildIteratorType child_begin(NodeRef N) {
+    return {N->edges_begin(), &edge_dest};
+  }
+  static ChildIteratorType child_end(NodeRef N) {
+    return {N->edges_end(), &edge_dest};
+  }
+
+  static NodeRef getNode(typename GraphT::Node const &N) { return NodeRef{&N}; }
+  using nodes_iterator =
+      mapped_iterator<typename GraphT::Node const *, decltype(&getNode)>;
+  static nodes_iterator nodes_begin(GraphT *G) {
+    return {G->nodes_begin(), &getNode};
+  }
+  static nodes_iterator nodes_end(GraphT *G) {
+    return {G->nodes_end(), &getNode};
+  }
+
+  using ChildEdgeIteratorType = typename GraphT::Edge const *;
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->edges_begin();
+  }
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) {
+    return N->edges_end();
+  }
+  static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H