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