contrib/llvm-project/llvm/lib/Target/X86/ImmutableGraph.h

   1 //==========-- ImmutableGraph.h - A fast DAG implementation ---------=========//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// Description: ImmutableGraph is a fast DAG implementation that cannot be
  10 /// modified, except by creating a new ImmutableGraph. ImmutableGraph is
  11 /// implemented as two arrays: one containing nodes, and one containing edges.
  12 /// The advantages to this implementation are two-fold:
  13 /// 1. Iteration and traversal operations benefit from cache locality.
  14 /// 2. Operations on sets of nodes/edges are efficient, and representations of
  15 ///    those sets in memory are compact. For instance, a set of edges is
  16 ///    implemented as a bit vector, wherein each bit corresponds to one edge in
  17 ///    the edge array. This implies a lower bound of 64x spatial improvement
  18 ///    over, e.g., an llvm::DenseSet or llvm::SmallSet. It also means that
  19 ///    insert/erase/contains operations complete in negligible constant time:
  20 ///    insert and erase require one load and one store, and contains requires
  21 ///    just one load.
  22 ///
  23 //===----------------------------------------------------------------------===//
  24
  25 #ifndef LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
  26 #define LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
  27
  28 #include "llvm/ADT/BitVector.h"
  29 #include "llvm/ADT/GraphTraits.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include <algorithm>
  33 #include <iterator>
  34 #include <utility>
  35 #include <vector>
  36
  37 namespace llvm {
  38
  39 template <typename NodeValueT, typename EdgeValueT> class ImmutableGraph {
  40   using Traits = GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *>;
  41   template <typename> friend class ImmutableGraphBuilder;
  42
  43 public:
  44   using node_value_type = NodeValueT;
  45   using edge_value_type = EdgeValueT;
  46   using size_type = int;
  47   class Node;
  48   class Edge {
  49     friend class ImmutableGraph;
  50     template <typename> friend class ImmutableGraphBuilder;
  51
  52     const Node *Dest;
  53     edge_value_type Value;
  54
  55   public:
  56     const Node *getDest() const { return Dest; };
  57     const edge_value_type &getValue() const { return Value; }
  58   };
  59   class Node {
  60     friend class ImmutableGraph;
  61     template <typename> friend class ImmutableGraphBuilder;
  62
  63     const Edge *Edges;
  64     node_value_type Value;
  65
  66   public:
  67     const node_value_type &getValue() const { return Value; }
  68
  69     const Edge *edges_begin() const { return Edges; }
  70     // Nodes are allocated sequentially. Edges for a node are stored together.
  71     // The end of this Node's edges is the beginning of the next node's edges.
  72     // An extra node was allocated to hold the end pointer for the last real
  73     // node.
  74     const Edge *edges_end() const { return (this + 1)->Edges; }
  75     ArrayRef<Edge> edges() const {
  76       return makeArrayRef(edges_begin(), edges_end());
  77     }
  78   };
  79
  80 protected:
  81   ImmutableGraph(std::unique_ptr<Node[]> Nodes, std::unique_ptr<Edge[]> Edges,
  82                  size_type NodesSize, size_type EdgesSize)
  83       : Nodes(std::move(Nodes)), Edges(std::move(Edges)), NodesSize(NodesSize),
  84         EdgesSize(EdgesSize) {}
  85   ImmutableGraph(const ImmutableGraph &) = delete;
  86   ImmutableGraph(ImmutableGraph &&) = delete;
  87   ImmutableGraph &operator=(const ImmutableGraph &) = delete;
  88   ImmutableGraph &operator=(ImmutableGraph &&) = delete;
  89
  90 public:
  91   ArrayRef<Node> nodes() const { return makeArrayRef(Nodes.get(), NodesSize); }
  92   const Node *nodes_begin() const { return nodes().begin(); }
  93   const Node *nodes_end() const { return nodes().end(); }
  94
  95   ArrayRef<Edge> edges() const { return makeArrayRef(Edges.get(), EdgesSize); }
  96   const Edge *edges_begin() const { return edges().begin(); }
  97   const Edge *edges_end() const { return edges().end(); }
  98
  99   size_type nodes_size() const { return NodesSize; }
 100   size_type edges_size() const { return EdgesSize; }
 101
 102   // Node N must belong to this ImmutableGraph.
 103   size_type getNodeIndex(const Node &N) const {
 104     return std::distance(nodes_begin(), &N);
 105   }
 106   // Edge E must belong to this ImmutableGraph.
 107   size_type getEdgeIndex(const Edge &E) const {
 108     return std::distance(edges_begin(), &E);
 109   }
 110
 111   // FIXME: Could NodeSet and EdgeSet be templated to share code?
 112   class NodeSet {
 113     const ImmutableGraph &G;
 114     BitVector V;
 115
 116   public:
 117     NodeSet(const ImmutableGraph &G, bool ContainsAll = false)
 118         : G{G}, V{static_cast<unsigned>(G.nodes_size()), ContainsAll} {}
 119     bool insert(const Node &N) {
 120       size_type Idx = G.getNodeIndex(N);
 121       bool AlreadyExists = V.test(Idx);
 122       V.set(Idx);
 123       return !AlreadyExists;
 124     }
 125     void erase(const Node &N) {
 126       size_type Idx = G.getNodeIndex(N);
 127       V.reset(Idx);
 128     }
 129     bool contains(const Node &N) const {
 130       size_type Idx = G.getNodeIndex(N);
 131       return V.test(Idx);
 132     }
 133     void clear() { V.reset(); }
 134     size_type empty() const { return V.none(); }
 135     /// Return the number of elements in the set
 136     size_type count() const { return V.count(); }
 137     /// Return the size of the set's domain
 138     size_type size() const { return V.size(); }
 139     /// Set union
 140     NodeSet &operator|=(const NodeSet &RHS) {
 141       assert(&this->G == &RHS.G);
 142       V |= RHS.V;
 143       return *this;
 144     }
 145     /// Set intersection
 146     NodeSet &operator&=(const NodeSet &RHS) {
 147       assert(&this->G == &RHS.G);
 148       V &= RHS.V;
 149       return *this;
 150     }
 151     /// Set disjoint union
 152     NodeSet &operator^=(const NodeSet &RHS) {
 153       assert(&this->G == &RHS.G);
 154       V ^= RHS.V;
 155       return *this;
 156     }
 157
 158     using index_iterator = typename BitVector::const_set_bits_iterator;
 159     index_iterator index_begin() const { return V.set_bits_begin(); }
 160     index_iterator index_end() const { return V.set_bits_end(); }
 161     void set(size_type Idx) { V.set(Idx); }
 162     void reset(size_type Idx) { V.reset(Idx); }
 163
 164     class iterator {
 165       const NodeSet &Set;
 166       size_type Current;
 167
 168       void advance() {
 169         assert(Current != -1);
 170         Current = Set.V.find_next(Current);
 171       }
 172
 173     public:
 174       iterator(const NodeSet &Set, size_type Begin)
 175           : Set{Set}, Current{Begin} {}
 176       iterator operator++(int) {
 177         iterator Tmp = *this;
 178         advance();
 179         return Tmp;
 180       }
 181       iterator &operator++() {
 182         advance();
 183         return *this;
 184       }
 185       Node *operator*() const {
 186         assert(Current != -1);
 187         return Set.G.nodes_begin() + Current;
 188       }
 189       bool operator==(const iterator &other) const {
 190         assert(&this->Set == &other.Set);
 191         return this->Current == other.Current;
 192       }
 193       bool operator!=(const iterator &other) const { return !(*this == other); }
 194     };
 195
 196     iterator begin() const { return iterator{*this, V.find_first()}; }
 197     iterator end() const { return iterator{*this, -1}; }
 198   };
 199
 200   class EdgeSet {
 201     const ImmutableGraph &G;
 202     BitVector V;
 203
 204   public:
 205     EdgeSet(const ImmutableGraph &G, bool ContainsAll = false)
 206         : G{G}, V{static_cast<unsigned>(G.edges_size()), ContainsAll} {}
 207     bool insert(const Edge &E) {
 208       size_type Idx = G.getEdgeIndex(E);
 209       bool AlreadyExists = V.test(Idx);
 210       V.set(Idx);
 211       return !AlreadyExists;
 212     }
 213     void erase(const Edge &E) {
 214       size_type Idx = G.getEdgeIndex(E);
 215       V.reset(Idx);
 216     }
 217     bool contains(const Edge &E) const {
 218       size_type Idx = G.getEdgeIndex(E);
 219       return V.test(Idx);
 220     }
 221     void clear() { V.reset(); }
 222     bool empty() const { return V.none(); }
 223     /// Return the number of elements in the set
 224     size_type count() const { return V.count(); }
 225     /// Return the size of the set's domain
 226     size_type size() const { return V.size(); }
 227     /// Set union
 228     EdgeSet &operator|=(const EdgeSet &RHS) {
 229       assert(&this->G == &RHS.G);
 230       V |= RHS.V;
 231       return *this;
 232     }
 233     /// Set intersection
 234     EdgeSet &operator&=(const EdgeSet &RHS) {
 235       assert(&this->G == &RHS.G);
 236       V &= RHS.V;
 237       return *this;
 238     }
 239     /// Set disjoint union
 240     EdgeSet &operator^=(const EdgeSet &RHS) {
 241       assert(&this->G == &RHS.G);
 242       V ^= RHS.V;
 243       return *this;
 244     }
 245
 246     using index_iterator = typename BitVector::const_set_bits_iterator;
 247     index_iterator index_begin() const { return V.set_bits_begin(); }
 248     index_iterator index_end() const { return V.set_bits_end(); }
 249     void set(size_type Idx) { V.set(Idx); }
 250     void reset(size_type Idx) { V.reset(Idx); }
 251
 252     class iterator {
 253       const EdgeSet &Set;
 254       size_type Current;
 255
 256       void advance() {
 257         assert(Current != -1);
 258         Current = Set.V.find_next(Current);
 259       }
 260
 261     public:
 262       iterator(const EdgeSet &Set, size_type Begin)
 263           : Set{Set}, Current{Begin} {}
 264       iterator operator++(int) {
 265         iterator Tmp = *this;
 266         advance();
 267         return Tmp;
 268       }
 269       iterator &operator++() {
 270         advance();
 271         return *this;
 272       }
 273       Edge *operator*() const {
 274         assert(Current != -1);
 275         return Set.G.edges_begin() + Current;
 276       }
 277       bool operator==(const iterator &other) const {
 278         assert(&this->Set == &other.Set);
 279         return this->Current == other.Current;
 280       }
 281       bool operator!=(const iterator &other) const { return !(*this == other); }
 282     };
 283
 284     iterator begin() const { return iterator{*this, V.find_first()}; }
 285     iterator end() const { return iterator{*this, -1}; }
 286   };
 287
 288 private:
 289   std::unique_ptr<Node[]> Nodes;
 290   std::unique_ptr<Edge[]> Edges;
 291   size_type NodesSize;
 292   size_type EdgesSize;
 293 };
 294
 295 template <typename GraphT> class ImmutableGraphBuilder {
 296   using node_value_type = typename GraphT::node_value_type;
 297   using edge_value_type = typename GraphT::edge_value_type;
 298   static_assert(
 299       std::is_base_of<ImmutableGraph<node_value_type, edge_value_type>,
 300                       GraphT>::value,
 301       "Template argument to ImmutableGraphBuilder must derive from "
 302       "ImmutableGraph<>");
 303   using size_type = typename GraphT::size_type;
 304   using NodeSet = typename GraphT::NodeSet;
 305   using Node = typename GraphT::Node;
 306   using EdgeSet = typename GraphT::EdgeSet;
 307   using Edge = typename GraphT::Edge;
 308   using BuilderEdge = std::pair<edge_value_type, size_type>;
 309   using EdgeList = std::vector<BuilderEdge>;
 310   using BuilderVertex = std::pair<node_value_type, EdgeList>;
 311   using VertexVec = std::vector<BuilderVertex>;
 312
 313 public:
 314   using BuilderNodeRef = size_type;
 315
 316   BuilderNodeRef addVertex(const node_value_type &V) {
 317     auto I = AdjList.emplace(AdjList.end(), V, EdgeList{});
 318     return std::distance(AdjList.begin(), I);
 319   }
 320
 321   void addEdge(const edge_value_type &E, BuilderNodeRef From,
 322                BuilderNodeRef To) {
 323     AdjList[From].second.emplace_back(E, To);
 324   }
 325
 326   bool empty() const { return AdjList.empty(); }
 327
 328   template <typename... ArgT> std::unique_ptr<GraphT> get(ArgT &&... Args) {
 329     size_type VertexSize = AdjList.size(), EdgeSize = 0;
 330     for (const auto &V : AdjList) {
 331       EdgeSize += V.second.size();
 332     }
 333     auto VertexArray =
 334         std::make_unique<Node[]>(VertexSize + 1 /* terminator node */);
 335     auto EdgeArray = std::make_unique<Edge[]>(EdgeSize);
 336     size_type VI = 0, EI = 0;
 337     for (; VI < VertexSize; ++VI) {
 338       VertexArray[VI].Value = std::move(AdjList[VI].first);
 339       VertexArray[VI].Edges = &EdgeArray[EI];
 340       auto NumEdges = static_cast<size_type>(AdjList[VI].second.size());
 341       for (size_type VEI = 0; VEI < NumEdges; ++VEI, ++EI) {
 342         auto &E = AdjList[VI].second[VEI];
 343         EdgeArray[EI].Value = std::move(E.first);
 344         EdgeArray[EI].Dest = &VertexArray[E.second];
 345       }
 346     }
 347     assert(VI == VertexSize && EI == EdgeSize && "ImmutableGraph malformed");
 348     VertexArray[VI].Edges = &EdgeArray[EdgeSize]; // terminator node
 349     return std::make_unique<GraphT>(std::move(VertexArray),
 350                                     std::move(EdgeArray), VertexSize, EdgeSize,
 351                                     std::forward<ArgT>(Args)...);
 352   }
 353
 354   template <typename... ArgT>
 355   static std::unique_ptr<GraphT> trim(const GraphT &G, const NodeSet &TrimNodes,
 356                                       const EdgeSet &TrimEdges,
 357                                       ArgT &&... Args) {
 358     size_type NewVertexSize = G.nodes_size() - TrimNodes.count();
 359     size_type NewEdgeSize = G.edges_size() - TrimEdges.count();
 360     auto NewVertexArray =
 361         std::make_unique<Node[]>(NewVertexSize + 1 /* terminator node */);
 362     auto NewEdgeArray = std::make_unique<Edge[]>(NewEdgeSize);
 363
 364     // Walk the nodes and determine the new index for each node.
 365     size_type NewNodeIndex = 0;
 366     std::vector<size_type> RemappedNodeIndex(G.nodes_size());
 367     for (const Node &N : G.nodes()) {
 368       if (TrimNodes.contains(N))
 369         continue;
 370       RemappedNodeIndex[G.getNodeIndex(N)] = NewNodeIndex++;
 371     }
 372     assert(NewNodeIndex == NewVertexSize &&
 373            "Should have assigned NewVertexSize indices");
 374
 375     size_type VertexI = 0, EdgeI = 0;
 376     for (const Node &N : G.nodes()) {
 377       if (TrimNodes.contains(N))
 378         continue;
 379       NewVertexArray[VertexI].Value = N.getValue();
 380       NewVertexArray[VertexI].Edges = &NewEdgeArray[EdgeI];
 381       for (const Edge &E : N.edges()) {
 382         if (TrimEdges.contains(E))
 383           continue;
 384         NewEdgeArray[EdgeI].Value = E.getValue();
 385         size_type DestIdx = G.getNodeIndex(*E.getDest());
 386         size_type NewIdx = RemappedNodeIndex[DestIdx];
 387         assert(NewIdx < NewVertexSize);
 388         NewEdgeArray[EdgeI].Dest = &NewVertexArray[NewIdx];
 389         ++EdgeI;
 390       }
 391       ++VertexI;
 392     }
 393     assert(VertexI == NewVertexSize && EdgeI == NewEdgeSize &&
 394            "Gadget graph malformed");
 395     NewVertexArray[VertexI].Edges = &NewEdgeArray[NewEdgeSize]; // terminator
 396     return std::make_unique<GraphT>(std::move(NewVertexArray),
 397                                     std::move(NewEdgeArray), NewVertexSize,
 398                                     NewEdgeSize, std::forward<ArgT>(Args)...);
 399   }
 400
 401 private:
 402   VertexVec AdjList;
 403 };
 404
 405 template <typename NodeValueT, typename EdgeValueT>
 406 struct GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *> {
 407   using GraphT = ImmutableGraph<NodeValueT, EdgeValueT>;
 408   using NodeRef = typename GraphT::Node const *;
 409   using EdgeRef = typename GraphT::Edge const &;
 410
 411   static NodeRef edge_dest(EdgeRef E) { return E.getDest(); }
 412   using ChildIteratorType =
 413       mapped_iterator<typename GraphT::Edge const *, decltype(&edge_dest)>;
 414
 415   static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); }
 416   static ChildIteratorType child_begin(NodeRef N) {
 417     return {N->edges_begin(), &edge_dest};
 418   }
 419   static ChildIteratorType child_end(NodeRef N) {
 420     return {N->edges_end(), &edge_dest};
 421   }
 422
 423   static NodeRef getNode(typename GraphT::Node const &N) { return NodeRef{&N}; }
 424   using nodes_iterator =
 425       mapped_iterator<typename GraphT::Node const *, decltype(&getNode)>;
 426   static nodes_iterator nodes_begin(GraphT *G) {
 427     return {G->nodes_begin(), &getNode};
 428   }
 429   static nodes_iterator nodes_end(GraphT *G) {
 430     return {G->nodes_end(), &getNode};
 431   }
 432
 433   using ChildEdgeIteratorType = typename GraphT::Edge const *;
 434
 435   static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
 436     return N->edges_begin();
 437   }
 438   static ChildEdgeIteratorType child_edge_end(NodeRef N) {
 439     return N->edges_end();
 440   }
 441   static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); }
 442 };
 443
 444 } // end namespace llvm
 445
 446 #endif // LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H