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
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 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
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 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
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 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
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 llvm
444
445#endif // LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
446