LLVM  14.0.0git
ImmutableGraph.h
Go to the documentation of this file.
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 {
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;
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;
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; }
75  return makeArrayRef(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;
88 
89 public:
90  ArrayRef<Node> nodes() const { return makeArrayRef(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 makeArrayRef(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 
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} {}
176  iterator Tmp = *this;
177  advance();
178  return Tmp;
179  }
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 
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} {}
264  iterator Tmp = *this;
265  advance();
266  return Tmp;
267  }
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(
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> *> {
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(); }
416  return {N->edges_begin(), &edge_dest};
417  }
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)>;
426  return {G->nodes_begin(), &getNode};
427  }
429  return {G->nodes_end(), &getNode};
430  }
431 
432  using ChildEdgeIteratorType = typename GraphT::Edge const *;
433 
435  return N->edges_begin();
436  }
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
llvm::ImmutableGraph::EdgeSet::insert
bool insert(const Edge &E)
Definition: ImmutableGraph.h:206
llvm::ImmutableGraph::Node::edges_end
const Edge * edges_end() const
Definition: ImmutableGraph.h:73
llvm::ImmutableGraph::nodes_size
size_type nodes_size() const
Definition: ImmutableGraph.h:98
llvm::ImmutableGraph::NodeSet
Definition: ImmutableGraph.h:111
llvm::ImmutableGraph::edges_end
const Edge * edges_end() const
Definition: ImmutableGraph.h:96
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ImmutableGraph
Definition: ImmutableGraph.h:38
llvm::ImmutableGraph::NodeSet::clear
void clear()
Definition: ImmutableGraph.h:132
llvm::ImmutableGraphBuilder::trim
static std::unique_ptr< GraphT > trim(const GraphT &G, const NodeSet &TrimNodes, const EdgeSet &TrimEdges, ArgT &&... Args)
Definition: ImmutableGraph.h:354
llvm::ImmutableGraphBuilder
Definition: ImmutableGraph.h:294
llvm::ImmutableGraph::edges_size
size_type edges_size() const
Definition: ImmutableGraph.h:99
llvm::ImmutableGraph::EdgeSet::end
iterator end() const
Definition: ImmutableGraph.h:284
llvm::ImmutableGraph::Node::getValue
const node_value_type & getValue() const
Definition: ImmutableGraph.h:66
llvm::ImmutableGraph::size_type
int size_type
Definition: ImmutableGraph.h:45
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ImmutableGraph.h:415
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::EdgeRef
typename GraphT::Edge const & EdgeRef
Definition: ImmutableGraph.h:408
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::size
static GraphT::size_type size(GraphT *G)
Definition: ImmutableGraph.h:440
llvm::ImmutableGraphBuilder::get
std::unique_ptr< GraphT > get(ArgT &&... Args)
Definition: ImmutableGraph.h:327
llvm::ImmutableGraph::nodes_begin
const Node * nodes_begin() const
Definition: ImmutableGraph.h:91
llvm::BitVector::none
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:180
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::ChildEdgeIteratorType
typename GraphT::Edge const * ChildEdgeIteratorType
Definition: ImmutableGraph.h:432
llvm::ImmutableGraph::EdgeSet::index_begin
index_iterator index_begin() const
Definition: ImmutableGraph.h:246
llvm::ImmutableGraph::EdgeSet::operator&=
EdgeSet & operator&=(const EdgeSet &RHS)
Set intersection.
Definition: ImmutableGraph.h:233
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::getNode
static NodeRef getNode(typename GraphT::Node const &N)
Definition: ImmutableGraph.h:422
llvm::ImmutableGraph::NodeSet::iterator::iterator
iterator(const NodeSet &Set, size_type Begin)
Definition: ImmutableGraph.h:173
llvm::ImmutableGraph::Node::edges_begin
const Edge * edges_begin() const
Definition: ImmutableGraph.h:68
llvm::ImmutableGraph::EdgeSet::reset
void reset(size_type Idx)
Definition: ImmutableGraph.h:249
llvm::ImmutableGraph::NodeSet::operator^=
NodeSet & operator^=(const NodeSet &RHS)
Set disjoint union.
Definition: ImmutableGraph.h:151
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >
Definition: ImmutableGraph.h:405
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: ImmutableGraph.h:434
llvm::ImmutableGraph::EdgeSet::iterator::operator++
iterator operator++(int)
Definition: ImmutableGraph.h:263
llvm::mapped_iterator
Definition: STLExtras.h:277
llvm::BitVector::set_bits_begin
const_set_bits_iterator set_bits_begin() const
Definition: BitVector.h:126
llvm::ImmutableGraphBuilder::addVertex
BuilderNodeRef addVertex(const node_value_type &V)
Definition: ImmutableGraph.h:315
STLExtras.h
llvm::ImmutableGraph::NodeSet::insert
bool insert(const Node &N)
Definition: ImmutableGraph.h:118
llvm::ImmutableGraph::Node
Definition: ImmutableGraph.h:58
llvm::ImmutableGraph::NodeSet::iterator::operator++
iterator & operator++()
Definition: ImmutableGraph.h:180
llvm::ImmutableGraph::NodeSet::iterator::operator*
Node * operator*() const
Definition: ImmutableGraph.h:184
GraphTraits.h
llvm::ImmutableGraph::EdgeSet::iterator
Definition: ImmutableGraph.h:251
llvm::ImmutableGraphBuilder::empty
bool empty() const
Definition: ImmutableGraph.h:325
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::nodes_begin
static nodes_iterator nodes_begin(GraphT *G)
Definition: ImmutableGraph.h:425
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: ImmutableGraph.h:437
llvm::ImmutableGraph::EdgeSet::iterator::operator==
bool operator==(const iterator &other) const
Definition: ImmutableGraph.h:276
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::BitVector::count
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:154
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::getEntryNode
static NodeRef getEntryNode(GraphT *G)
Definition: ImmutableGraph.h:414
llvm::ImmutableGraph::NodeSet::begin
iterator begin() const
Definition: ImmutableGraph.h:195
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::BitVector::size
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:151
llvm::ImmutableGraph::EdgeSet::iterator::operator++
iterator & operator++()
Definition: ImmutableGraph.h:268
llvm::ImmutableGraph::NodeSet::reset
void reset(size_type Idx)
Definition: ImmutableGraph.h:161
llvm::ImmutableGraph::edges
ArrayRef< Edge > edges() const
Definition: ImmutableGraph.h:94
llvm::ImmutableGraph::EdgeSet::iterator::iterator
iterator(const EdgeSet &Set, size_type Begin)
Definition: ImmutableGraph.h:261
BitVector.h
llvm::ImmutableGraph::Edge
Definition: ImmutableGraph.h:47
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::edge_dest
static NodeRef edge_dest(EdgeRef E)
Definition: ImmutableGraph.h:410
llvm::BitVector
Definition: BitVector.h:74
llvm::ImmutableGraph::EdgeSet
Definition: ImmutableGraph.h:199
llvm::ImmutableGraph::node_value_type
NodeValueT node_value_type
Definition: ImmutableGraph.h:43
llvm::ImmutableGraphBuilder::BuilderNodeRef
size_type BuilderNodeRef
Definition: ImmutableGraph.h:313
llvm::ImmutableGraph::NodeSet::index_begin
index_iterator index_begin() const
Definition: ImmutableGraph.h:158
llvm::ImmutableGraph::NodeSet::set
void set(size_type Idx)
Definition: ImmutableGraph.h:160
llvm::ImmutableGraph::EdgeSet::index_end
index_iterator index_end() const
Definition: ImmutableGraph.h:247
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
VI
@ VI
Definition: SIInstrInfo.cpp:7679
llvm::ImmutableGraph::EdgeSet::operator|=
EdgeSet & operator|=(const EdgeSet &RHS)
Set union.
Definition: ImmutableGraph.h:227
llvm::ImmutableGraph::nodes_end
const Node * nodes_end() const
Definition: ImmutableGraph.h:92
llvm::ImmutableGraph::NodeSet::end
iterator end() const
Definition: ImmutableGraph.h:196
llvm::ImmutableGraph::getEdgeIndex
size_type getEdgeIndex(const Edge &E) const
Definition: ImmutableGraph.h:106
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::nodes_end
static nodes_iterator nodes_end(GraphT *G)
Definition: ImmutableGraph.h:428
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::ImmutableGraph::EdgeSet::index_iterator
typename BitVector::const_set_bits_iterator index_iterator
Definition: ImmutableGraph.h:245
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ImmutableGraph::NodeSet::iterator
Definition: ImmutableGraph.h:163
G
#define G(x, y, z)
Definition: MD5.cpp:57
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ImmutableGraph::getNodeIndex
size_type getNodeIndex(const Node &N) const
Definition: ImmutableGraph.h:102
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1607
llvm::ImmutableGraph::EdgeSet::iterator::operator!=
bool operator!=(const iterator &other) const
Definition: ImmutableGraph.h:280
llvm::ImmutableGraph::EdgeSet::iterator::operator*
Edge * operator*() const
Definition: ImmutableGraph.h:272
llvm::ImmutableGraph::EdgeSet::set
void set(size_type Idx)
Definition: ImmutableGraph.h:248
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::ImmutableGraph::EdgeSet::erase
void erase(const Edge &E)
Definition: ImmutableGraph.h:212
llvm::ImmutableGraph::EdgeSet::size
size_type size() const
Return the size of the set's domain.
Definition: ImmutableGraph.h:225
llvm::ImmutableGraph::EdgeSet::EdgeSet
EdgeSet(const ImmutableGraph &G, bool ContainsAll=false)
Definition: ImmutableGraph.h:204
llvm::ImmutableGraph::NodeSet::contains
bool contains(const Node &N) const
Definition: ImmutableGraph.h:128
Node
Definition: ItaniumDemangle.h:234
llvm::ImmutableGraph::ImmutableGraph
ImmutableGraph(std::unique_ptr< Node[]> Nodes, std::unique_ptr< Edge[]> Edges, size_type NodesSize, size_type EdgesSize)
Definition: ImmutableGraph.h:80
llvm::ImmutableGraph::EdgeSet::begin
iterator begin() const
Definition: ImmutableGraph.h:283
llvm::ImmutableGraph::Edge::getDest
const Node * getDest() const
Definition: ImmutableGraph.h:55
llvm::ImmutableGraph::NodeSet::size
size_type size() const
Return the size of the set's domain.
Definition: ImmutableGraph.h:137
llvm::BitVector::const_set_bits_iterator
const_set_bits_iterator_impl< BitVector > const_set_bits_iterator
Definition: BitVector.h:123
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
llvm::ImmutableGraph::Edge::getValue
const edge_value_type & getValue() const
Definition: ImmutableGraph.h:56
llvm::ImmutableGraph::NodeSet::NodeSet
NodeSet(const ImmutableGraph &G, bool ContainsAll=false)
Definition: ImmutableGraph.h:116
std
Definition: BitVector.h:838
llvm::ImmutableGraph::nodes
ArrayRef< Node > nodes() const
Definition: ImmutableGraph.h:90
llvm::ImmutableGraph::NodeSet::erase
void erase(const Node &N)
Definition: ImmutableGraph.h:124
llvm::BitVector::set_bits_end
const_set_bits_iterator set_bits_end() const
Definition: BitVector.h:129
llvm::ImmutableGraph::NodeSet::iterator::operator++
iterator operator++(int)
Definition: ImmutableGraph.h:175
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::ImmutableGraph::edge_value_type
EdgeValueT edge_value_type
Definition: ImmutableGraph.h:44
llvm::ImmutableGraph::NodeSet::index_end
index_iterator index_end() const
Definition: ImmutableGraph.h:159
llvm::ImmutableGraph::Node::edges
ArrayRef< Edge > edges() const
Definition: ImmutableGraph.h:74
llvm::ImmutableGraph::NodeSet::index_iterator
typename BitVector::const_set_bits_iterator index_iterator
Definition: ImmutableGraph.h:157
llvm::BitVector::find_next
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:300
llvm::ImmutableGraph::EdgeSet::contains
bool contains(const Edge &E) const
Definition: ImmutableGraph.h:216
llvm::ImmutableGraph::EdgeSet::empty
bool empty() const
Definition: ImmutableGraph.h:221
llvm::BitVector::reset
BitVector & reset()
Definition: BitVector.h:384
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::ImmutableGraph::operator=
ImmutableGraph & operator=(const ImmutableGraph &)=delete
llvm::ImmutableGraph::EdgeSet::operator^=
EdgeSet & operator^=(const EdgeSet &RHS)
Set disjoint union.
Definition: ImmutableGraph.h:239
llvm::ImmutableGraph::NodeSet::empty
size_type empty() const
Definition: ImmutableGraph.h:133
llvm::rdf::NodeSet
std::set< NodeId > NodeSet
Definition: RDFGraph.h:513
llvm::ImmutableGraph::EdgeSet::clear
void clear()
Definition: ImmutableGraph.h:220
N
#define N
llvm::BitVector::find_first
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:292
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ImmutableGraph.h:418
llvm::ImmutableGraph::edges_begin
const Edge * edges_begin() const
Definition: ImmutableGraph.h:95
llvm::ImmutableGraph::NodeSet::iterator::operator==
bool operator==(const iterator &other) const
Definition: ImmutableGraph.h:188
llvm::GraphTraits
Definition: GraphTraits.h:35
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::ImmutableGraph::NodeSet::operator|=
NodeSet & operator|=(const NodeSet &RHS)
Set union.
Definition: ImmutableGraph.h:139
llvm::ImmutableGraph::EdgeSet::count
size_type count() const
Return the number of elements in the set.
Definition: ImmutableGraph.h:223
llvm::ImmutableGraph::NodeSet::iterator::operator!=
bool operator!=(const iterator &other) const
Definition: ImmutableGraph.h:192
llvm::ImmutableGraph::NodeSet::count
size_type count() const
Return the number of elements in the set.
Definition: ImmutableGraph.h:135
llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >::NodeRef
typename GraphT::Node const * NodeRef
Definition: ImmutableGraph.h:407
llvm::ImmutableGraph::NodeSet::operator&=
NodeSet & operator&=(const NodeSet &RHS)
Set intersection.
Definition: ImmutableGraph.h:145
llvm::ImmutableGraphBuilder::addEdge
void addEdge(const edge_value_type &E, BuilderNodeRef From, BuilderNodeRef To)
Definition: ImmutableGraph.h:320