1 //==========-- ImmutableGraph.h - A fast DAG implementation ---------=========//
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
7 //===----------------------------------------------------------------------===//
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
23 //===----------------------------------------------------------------------===//
25 #ifndef LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
26 #define LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
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"
39 template <typename NodeValueT, typename EdgeValueT> class ImmutableGraph {
40 using Traits = GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *>;
41 template <typename> friend class ImmutableGraphBuilder;
44 using node_value_type = NodeValueT;
45 using edge_value_type = EdgeValueT;
46 using size_type = int;
49 friend class ImmutableGraph;
50 template <typename> friend class ImmutableGraphBuilder;
53 edge_value_type Value;
56 const Node *getDest() const { return Dest; };
57 const edge_value_type &getValue() const { return Value; }
60 friend class ImmutableGraph;
61 template <typename> friend class ImmutableGraphBuilder;
64 node_value_type Value;
67 const node_value_type &getValue() const { return Value; }
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
74 const Edge *edges_end() const { return (this + 1)->Edges; }
75 ArrayRef<Edge> edges() const {
76 return makeArrayRef(edges_begin(), edges_end());
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;
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(); }
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(); }
99 size_type nodes_size() const { return NodesSize; }
100 size_type edges_size() const { return EdgesSize; }
102 // Node N must belong to this ImmutableGraph.
103 size_type getNodeIndex(const Node &N) const {
104 return std::distance(nodes_begin(), &N);
106 // Edge E must belong to this ImmutableGraph.
107 size_type getEdgeIndex(const Edge &E) const {
108 return std::distance(edges_begin(), &E);
111 // FIXME: Could NodeSet and EdgeSet be templated to share code?
113 const ImmutableGraph &G;
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);
123 return !AlreadyExists;
125 void erase(const Node &N) {
126 size_type Idx = G.getNodeIndex(N);
129 bool contains(const Node &N) const {
130 size_type Idx = G.getNodeIndex(N);
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(); }
140 NodeSet &operator|=(const NodeSet &RHS) {
141 assert(&this->G == &RHS.G);
146 NodeSet &operator&=(const NodeSet &RHS) {
147 assert(&this->G == &RHS.G);
151 /// Set disjoint union
152 NodeSet &operator^=(const NodeSet &RHS) {
153 assert(&this->G == &RHS.G);
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); }
169 assert(Current != -1);
170 Current = Set.V.find_next(Current);
174 iterator(const NodeSet &Set, size_type Begin)
175 : Set{Set}, Current{Begin} {}
176 iterator operator++(int) {
177 iterator Tmp = *this;
181 iterator &operator++() {
185 Node *operator*() const {
186 assert(Current != -1);
187 return Set.G.nodes_begin() + Current;
189 bool operator==(const iterator &other) const {
190 assert(&this->Set == &other.Set);
191 return this->Current == other.Current;
193 bool operator!=(const iterator &other) const { return !(*this == other); }
196 iterator begin() const { return iterator{*this, V.find_first()}; }
197 iterator end() const { return iterator{*this, -1}; }
201 const ImmutableGraph &G;
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);
211 return !AlreadyExists;
213 void erase(const Edge &E) {
214 size_type Idx = G.getEdgeIndex(E);
217 bool contains(const Edge &E) const {
218 size_type Idx = G.getEdgeIndex(E);
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(); }
228 EdgeSet &operator|=(const EdgeSet &RHS) {
229 assert(&this->G == &RHS.G);
234 EdgeSet &operator&=(const EdgeSet &RHS) {
235 assert(&this->G == &RHS.G);
239 /// Set disjoint union
240 EdgeSet &operator^=(const EdgeSet &RHS) {
241 assert(&this->G == &RHS.G);
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); }
257 assert(Current != -1);
258 Current = Set.V.find_next(Current);
262 iterator(const EdgeSet &Set, size_type Begin)
263 : Set{Set}, Current{Begin} {}
264 iterator operator++(int) {
265 iterator Tmp = *this;
269 iterator &operator++() {
273 Edge *operator*() const {
274 assert(Current != -1);
275 return Set.G.edges_begin() + Current;
277 bool operator==(const iterator &other) const {
278 assert(&this->Set == &other.Set);
279 return this->Current == other.Current;
281 bool operator!=(const iterator &other) const { return !(*this == other); }
284 iterator begin() const { return iterator{*this, V.find_first()}; }
285 iterator end() const { return iterator{*this, -1}; }
289 std::unique_ptr<Node[]> Nodes;
290 std::unique_ptr<Edge[]> Edges;
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;
299 std::is_base_of<ImmutableGraph<node_value_type, edge_value_type>,
301 "Template argument to ImmutableGraphBuilder must derive from "
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>;
314 using BuilderNodeRef = size_type;
316 BuilderNodeRef addVertex(const node_value_type &V) {
317 auto I = AdjList.emplace(AdjList.end(), V, EdgeList{});
318 return std::distance(AdjList.begin(), I);
321 void addEdge(const edge_value_type &E, BuilderNodeRef From,
323 AdjList[From].second.emplace_back(E, To);
326 bool empty() const { return AdjList.empty(); }
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();
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];
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)...);
354 template <typename... ArgT>
355 static std::unique_ptr<GraphT> trim(const GraphT &G, const NodeSet &TrimNodes,
356 const EdgeSet &TrimEdges,
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);
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))
370 RemappedNodeIndex[G.getNodeIndex(N)] = NewNodeIndex++;
372 assert(NewNodeIndex == NewVertexSize &&
373 "Should have assigned NewVertexSize indices");
375 size_type VertexI = 0, EdgeI = 0;
376 for (const Node &N : G.nodes()) {
377 if (TrimNodes.contains(N))
379 NewVertexArray[VertexI].Value = N.getValue();
380 NewVertexArray[VertexI].Edges = &NewEdgeArray[EdgeI];
381 for (const Edge &E : N.edges()) {
382 if (TrimEdges.contains(E))
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];
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)...);
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 &;
411 static NodeRef edge_dest(EdgeRef E) { return E.getDest(); }
412 using ChildIteratorType =
413 mapped_iterator<typename GraphT::Edge const *, decltype(&edge_dest)>;
415 static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); }
416 static ChildIteratorType child_begin(NodeRef N) {
417 return {N->edges_begin(), &edge_dest};
419 static ChildIteratorType child_end(NodeRef N) {
420 return {N->edges_end(), &edge_dest};
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};
429 static nodes_iterator nodes_end(GraphT *G) {
430 return {G->nodes_end(), &getNode};
433 using ChildEdgeIteratorType = typename GraphT::Edge const *;
435 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
436 return N->edges_begin();
438 static ChildEdgeIteratorType child_edge_end(NodeRef N) {
439 return N->edges_end();
441 static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); }
444 } // end namespace llvm
446 #endif // LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H