446 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// Description: ImmutableGraph is a fast DAG implementation that cannot be10/// modified, except by creating a new ImmutableGraph. ImmutableGraph is11/// 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 of15/// those sets in memory are compact. For instance, a set of edges is16/// implemented as a bit vector, wherein each bit corresponds to one edge in17/// the edge array. This implies a lower bound of 64x spatial improvement18/// over, e.g., an llvm::DenseSet or llvm::SmallSet. It also means that19/// insert/erase/contains operations complete in negligible constant time:20/// insert and erase require one load and one store, and contains requires21/// just one load.22///23//===----------------------------------------------------------------------===//24 25#ifndef LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H26#define LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H27 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 36namespace llvm {37 38template <typename NodeValueT, typename EdgeValueT> class ImmutableGraph {39 using Traits = GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *>;40 template <typename> friend class ImmutableGraphBuilder;41 42public: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 real72 // 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 79protected: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 89public: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 set135 size_type count() const { return V.count(); }136 /// Return the size of the set's domain137 size_type size() const { return V.size(); }138 /// Set union139 NodeSet &operator|=(const NodeSet &RHS) {140 assert(&this->G == &RHS.G);141 V |= RHS.V;142 return *this;143 }144 /// Set intersection145 NodeSet &operator&=(const NodeSet &RHS) {146 assert(&this->G == &RHS.G);147 V &= RHS.V;148 return *this;149 }150 /// Set disjoint union151 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 set223 size_type count() const { return V.count(); }224 /// Return the size of the set's domain225 size_type size() const { return V.size(); }226 /// Set union227 EdgeSet &operator|=(const EdgeSet &RHS) {228 assert(&this->G == &RHS.G);229 V |= RHS.V;230 return *this;231 }232 /// Set intersection233 EdgeSet &operator&=(const EdgeSet &RHS) {234 assert(&this->G == &RHS.G);235 V &= RHS.V;236 return *this;237 }238 /// Set disjoint union239 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 287private:288 std::unique_ptr<Node[]> Nodes;289 std::unique_ptr<Edge[]> Edges;290 size_type NodesSize;291 size_type EdgesSize;292};293 294template <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 312public: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 node348 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]; // terminator395 return std::make_unique<GraphT>(std::move(NewVertexArray),396 std::move(NewEdgeArray), NewVertexSize,397 NewEdgeSize, std::forward<ArgT>(Args)...);398 }399 400private:401 VertexVec AdjList;402};403 404template <typename NodeValueT, typename EdgeValueT>405struct 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 llvm444 445#endif // LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H446