LLVM  14.0.0git
Graph.h
Go to the documentation of this file.
1 //===-- Graph.h - XRay Graph Class ------------------------------*- C++ -*-===//
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 //
9 // A Graph Datatype for XRay.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_XRAY_GRAPH_H
14 #define LLVM_XRAY_GRAPH_H
15 
16 #include <initializer_list>
17 #include <stdint.h>
18 #include <type_traits>
19 #include <utility>
20 
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/iterator.h"
24 #include "llvm/Support/Error.h"
25 
26 namespace llvm {
27 namespace xray {
28 
29 /// A Graph object represents a Directed Graph and is used in XRay to compute
30 /// and store function call graphs and associated statistical information.
31 ///
32 /// The graph takes in four template parameters, these are:
33 /// - VertexAttribute, this is a structure which is stored for each vertex.
34 /// Must be DefaultConstructible, CopyConstructible, CopyAssignable and
35 /// Destructible.
36 /// - EdgeAttribute, this is a structure which is stored for each edge
37 /// Must be DefaultConstructible, CopyConstructible, CopyAssignable and
38 /// Destructible.
39 /// - EdgeAttribute, this is a structure which is stored for each variable
40 /// - VI, this is a type over which DenseMapInfo is defined and is the type
41 /// used look up strings, available as VertexIdentifier.
42 /// - If the built in DenseMapInfo is not defined, provide a specialization
43 /// class type here.
44 ///
45 /// Graph is CopyConstructible, CopyAssignable, MoveConstructible and
46 /// MoveAssignable but is not EqualityComparible or LessThanComparible.
47 ///
48 /// Usage Example Graph with weighted edges and vertices:
49 /// Graph<int, int, int> G;
50 ///
51 /// G[1] = 0;
52 /// G[2] = 2;
53 /// G[{1,2}] = 1;
54 /// G[{2,1}] = -1;
55 /// for(const auto &v : G.vertices()){
56 /// // Do something with the vertices in the graph;
57 /// }
58 /// for(const auto &e : G.edges()){
59 /// // Do something with the edges in the graph;
60 /// }
61 ///
62 /// Usage Example with StrRef keys.
63 /// Graph<int, double, StrRef> StrG;
64 /// char va[] = "Vertex A";
65 /// char vaa[] = "Vertex A";
66 /// char vb[] = "Vertex B"; // Vertices are referenced by String Refs.
67 /// G[va] = 0;
68 /// G[vb] = 1;
69 /// G[{va, vb}] = 1.0;
70 /// cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".
71 ///
72 template <typename VertexAttribute, typename EdgeAttribute,
73  typename VI = int32_t>
74 class Graph {
75 public:
76  /// These objects are used to name edges and vertices in the graph.
78  typedef std::pair<VI, VI> EdgeIdentifier;
79 
80  /// This type is the value_type of all iterators which range over vertices,
81  /// Determined by the Vertices DenseMap
82  using VertexValueType =
84 
85  /// This type is the value_type of all iterators which range over edges,
86  /// Determined by the Edges DenseMap.
88 
89  using size_type = std::size_t;
90 
91 private:
92  /// The type used for storing the EdgeAttribute for each edge in the graph
94 
95  /// The type used for storing the VertexAttribute for each vertex in
96  /// the graph.
98 
99  /// The type used for storing the edges entering a vertex. Indexed by
100  /// the VertexIdentifier of the start of the edge. Only used to determine
101  /// where the incoming edges are, the EdgeIdentifiers are stored in an
102  /// InnerEdgeMapT.
104 
105  /// The type storing the InnerInvGraphT corresponding to each vertex in
106  /// the graph (When a vertex has an incoming edge incident to it)
108 
109 private:
110  /// Stores the map from the start and end vertex of an edge to it's
111  /// EdgeAttribute
112  EdgeMapT Edges;
113 
114  /// Stores the map from VertexIdentifier to VertexAttribute
115  VertexMapT Vertices;
116 
117  /// Allows fast lookup for the incoming edge set of any given vertex.
118  NeighborLookupT InNeighbors;
119 
120  /// Allows fast lookup for the outgoing edge set of any given vertex.
121  NeighborLookupT OutNeighbors;
122 
123  /// An Iterator adapter using an InnerInvGraphT::iterator as a base iterator,
124  /// and storing the VertexIdentifier the iterator range comes from. The
125  /// dereference operator is then performed using a pointer to the graph's edge
126  /// set.
127  template <bool IsConst, bool IsOut,
128  typename BaseIt = typename NeighborSetT::const_iterator,
129  typename T =
130  std::conditional_t<IsConst, const EdgeValueType, EdgeValueType>>
131  class NeighborEdgeIteratorT
132  : public iterator_adaptor_base<
133  NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
134  typename std::iterator_traits<BaseIt>::iterator_category, T> {
135  using InternalEdgeMapT =
136  std::conditional_t<IsConst, const EdgeMapT, EdgeMapT>;
137 
138  friend class NeighborEdgeIteratorT<false, IsOut, BaseIt, EdgeValueType>;
139  friend class NeighborEdgeIteratorT<true, IsOut, BaseIt,
141 
142  InternalEdgeMapT *MP;
144 
145  public:
146  template <bool IsConstDest,
147  typename = std::enable_if<IsConstDest && !IsConst>>
148  operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
149  const EdgeValueType>() const {
150  return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
151  const EdgeValueType>(this->I, MP, SI);
152  }
153 
154  NeighborEdgeIteratorT() = default;
155  NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,
156  VertexIdentifier _SI)
158  NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
159  typename std::iterator_traits<BaseIt>::iterator_category, T>(_I),
160  MP(_MP), SI(_SI) {}
161 
162  T &operator*() const {
163  if (!IsOut)
164  return *(MP->find({*(this->I), SI}));
165  else
166  return *(MP->find({SI, *(this->I)}));
167  }
168  };
169 
170 public:
171  /// A const iterator type for iterating through the set of edges entering a
172  /// vertex.
173  ///
174  /// Has a const EdgeValueType as its value_type
175  using ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>;
176 
177  /// An iterator type for iterating through the set of edges leaving a vertex.
178  ///
179  /// Has an EdgeValueType as its value_type
180  using InEdgeIterator = NeighborEdgeIteratorT<false, false>;
181 
182  /// A const iterator type for iterating through the set of edges entering a
183  /// vertex.
184  ///
185  /// Has a const EdgeValueType as its value_type
186  using ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>;
187 
188  /// An iterator type for iterating through the set of edges leaving a vertex.
189  ///
190  /// Has an EdgeValueType as its value_type
191  using OutEdgeIterator = NeighborEdgeIteratorT<false, true>;
192 
193  /// A class for ranging over the incoming edges incident to a vertex.
194  ///
195  /// Like all views in this class it provides methods to get the beginning and
196  /// past the range iterators for the range, as well as methods to determine
197  /// the number of elements in the range and whether the range is empty.
198  template <bool isConst, bool isOut> class InOutEdgeView {
199  public:
200  using iterator = NeighborEdgeIteratorT<isConst, isOut>;
201  using const_iterator = NeighborEdgeIteratorT<true, isOut>;
202  using GraphT = std::conditional_t<isConst, const Graph, Graph>;
203  using InternalEdgeMapT =
204  std::conditional_t<isConst, const EdgeMapT, EdgeMapT>;
205 
206  private:
207  InternalEdgeMapT &M;
208  const VertexIdentifier A;
209  const NeighborLookupT &NL;
210 
211  public:
213  auto It = NL.find(A);
214  if (It == NL.end())
215  return iterator();
216  return iterator(It->second.begin(), &M, A);
217  }
218 
220  auto It = NL.find(A);
221  if (It == NL.end())
222  return const_iterator();
223  return const_iterator(It->second.begin(), &M, A);
224  }
225 
226  const_iterator begin() const { return cbegin(); }
227 
229  auto It = NL.find(A);
230  if (It == NL.end())
231  return iterator();
232  return iterator(It->second.end(), &M, A);
233  }
235  auto It = NL.find(A);
236  if (It == NL.end())
237  return const_iterator();
238  return const_iterator(It->second.end(), &M, A);
239  }
240 
241  const_iterator end() const { return cend(); }
242 
243  size_type size() const {
244  auto I = NL.find(A);
245  if (I == NL.end())
246  return 0;
247  else
248  return I->second.size();
249  }
250 
251  bool empty() const { return NL.count(A) == 0; };
252 
254  : M(G.Edges), A(A), NL(isOut ? G.OutNeighbors : G.InNeighbors) {}
255  };
256 
257  /// A const iterator type for iterating through the whole vertex set of the
258  /// graph.
259  ///
260  /// Has a const VertexValueType as its value_type
262 
263  /// An iterator type for iterating through the whole vertex set of the graph.
264  ///
265  /// Has a VertexValueType as its value_type
267 
268  /// A class for ranging over the vertices in the graph.
269  ///
270  /// Like all views in this class it provides methods to get the beginning and
271  /// past the range iterators for the range, as well as methods to determine
272  /// the number of elements in the range and whether the range is empty.
273  template <bool isConst> class VertexView {
274  public:
275  using iterator =
276  std::conditional_t<isConst, ConstVertexIterator, VertexIterator>;
278  using GraphT = std::conditional_t<isConst, const Graph, Graph>;
279 
280  private:
281  GraphT &G;
282 
283  public:
284  iterator begin() { return G.Vertices.begin(); }
285  iterator end() { return G.Vertices.end(); }
286  const_iterator cbegin() const { return G.Vertices.cbegin(); }
287  const_iterator cend() const { return G.Vertices.cend(); }
288  const_iterator begin() const { return G.Vertices.begin(); }
289  const_iterator end() const { return G.Vertices.end(); }
290  size_type size() const { return G.Vertices.size(); }
291  bool empty() const { return G.Vertices.empty(); }
292  VertexView(GraphT &_G) : G(_G) {}
293  };
294 
295  /// A const iterator for iterating through the entire edge set of the graph.
296  ///
297  /// Has a const EdgeValueType as its value_type
299 
300  /// An iterator for iterating through the entire edge set of the graph.
301  ///
302  /// Has an EdgeValueType as its value_type
304 
305  /// A class for ranging over all the edges in the graph.
306  ///
307  /// Like all views in this class it provides methods to get the beginning and
308  /// past the range iterators for the range, as well as methods to determine
309  /// the number of elements in the range and whether the range is empty.
310  template <bool isConst> class EdgeView {
311  public:
312  using iterator =
313  std::conditional_t<isConst, ConstEdgeIterator, EdgeIterator>;
315  using GraphT = std::conditional_t<isConst, const Graph, Graph>;
316 
317  private:
318  GraphT &G;
319 
320  public:
321  iterator begin() { return G.Edges.begin(); }
322  iterator end() { return G.Edges.end(); }
323  const_iterator cbegin() const { return G.Edges.cbegin(); }
324  const_iterator cend() const { return G.Edges.cend(); }
325  const_iterator begin() const { return G.Edges.begin(); }
326  const_iterator end() const { return G.Edges.end(); }
327  size_type size() const { return G.Edges.size(); }
328  bool empty() const { return G.Edges.empty(); }
329  EdgeView(GraphT &_G) : G(_G) {}
330  };
331 
332 public:
333  // TODO: implement constructor to enable Graph Initialisation.\
334  // Something like:
335  // Graph<int, int, int> G(
336  // {1, 2, 3, 4, 5},
337  // {{1, 2}, {2, 3}, {3, 4}});
338 
339  /// Empty the Graph
340  void clear() {
341  Edges.clear();
342  Vertices.clear();
343  InNeighbors.clear();
344  OutNeighbors.clear();
345  }
346 
347  /// Returns a view object allowing iteration over the vertices of the graph.
348  /// also allows access to the size of the vertex set.
350 
351  VertexView<true> vertices() const { return VertexView<true>(*this); }
352 
353  /// Returns a view object allowing iteration over the edges of the graph.
354  /// also allows access to the size of the edge set.
355  EdgeView<false> edges() { return EdgeView<false>(*this); }
356 
357  EdgeView<true> edges() const { return EdgeView<true>(*this); }
358 
359  /// Returns a view object allowing iteration over the edges which start at
360  /// a vertex I.
362  return InOutEdgeView<false, true>(*this, I);
363  }
364 
366  return InOutEdgeView<true, true>(*this, I);
367  }
368 
369  /// Returns a view object allowing iteration over the edges which point to
370  /// a vertex I.
372  return InOutEdgeView<false, false>(*this, I);
373  }
374 
376  return InOutEdgeView<true, false>(*this, I);
377  }
378 
379  /// Looks up the vertex with identifier I, if it does not exist it default
380  /// constructs it.
381  VertexAttribute &operator[](const VertexIdentifier &I) {
382  return Vertices.FindAndConstruct(I).second;
383  }
384 
385  /// Looks up the edge with identifier I, if it does not exist it default
386  /// constructs it, if it's endpoints do not exist it also default constructs
387  /// them.
388  EdgeAttribute &operator[](const EdgeIdentifier &I) {
389  auto &P = Edges.FindAndConstruct(I);
390  Vertices.FindAndConstruct(I.first);
391  Vertices.FindAndConstruct(I.second);
392  InNeighbors[I.second].insert(I.first);
393  OutNeighbors[I.first].insert(I.second);
394  return P.second;
395  }
396 
397  /// Looks up a vertex with Identifier I, or an error if it does not exist.
399  auto It = Vertices.find(I);
400  if (It == Vertices.end())
401  return make_error<StringError>(
402  "Vertex Identifier Does Not Exist",
403  std::make_error_code(std::errc::invalid_argument));
404  return It->second;
405  }
406 
408  auto It = Vertices.find(I);
409  if (It == Vertices.end())
410  return make_error<StringError>(
411  "Vertex Identifier Does Not Exist",
412  std::make_error_code(std::errc::invalid_argument));
413  return It->second;
414  }
415 
416  /// Looks up an edge with Identifier I, or an error if it does not exist.
418  auto It = Edges.find(I);
419  if (It == Edges.end())
420  return make_error<StringError>(
421  "Edge Identifier Does Not Exist",
422  std::make_error_code(std::errc::invalid_argument));
423  return It->second;
424  }
425 
427  auto It = Edges.find(I);
428  if (It == Edges.end())
429  return make_error<StringError>(
430  "Edge Identifier Does Not Exist",
431  std::make_error_code(std::errc::invalid_argument));
432  return It->second;
433  }
434 
435  /// Looks for a vertex with identifier I, returns 1 if one exists, and
436  /// 0 otherwise
438  return Vertices.count(I);
439  }
440 
441  /// Looks for an edge with Identifier I, returns 1 if one exists and 0
442  /// otherwise
443  size_type count(const EdgeIdentifier &I) const { return Edges.count(I); }
444 
445  /// Inserts a vertex into the graph with Identifier Val.first, and
446  /// Attribute Val.second.
447  std::pair<VertexIterator, bool>
448  insert(const std::pair<VertexIdentifier, VertexAttribute> &Val) {
449  return Vertices.insert(Val);
450  }
451 
452  std::pair<VertexIterator, bool>
453  insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {
454  return Vertices.insert(std::move(Val));
455  }
456 
457  /// Inserts an edge into the graph with Identifier Val.first, and
458  /// Attribute Val.second. If the key is already in the map, it returns false
459  /// and doesn't update the value.
460  std::pair<EdgeIterator, bool>
461  insert(const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {
462  const auto &p = Edges.insert(Val);
463  if (p.second) {
464  const auto &EI = Val.first;
465  Vertices.FindAndConstruct(EI.first);
466  Vertices.FindAndConstruct(EI.second);
467  InNeighbors[EI.second].insert(EI.first);
468  OutNeighbors[EI.first].insert(EI.second);
469  };
470 
471  return p;
472  }
473 
474  /// Inserts an edge into the graph with Identifier Val.first, and
475  /// Attribute Val.second. If the key is already in the map, it returns false
476  /// and doesn't update the value.
477  std::pair<EdgeIterator, bool>
478  insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {
479  auto EI = Val.first;
480  const auto &p = Edges.insert(std::move(Val));
481  if (p.second) {
482  Vertices.FindAndConstruct(EI.first);
483  Vertices.FindAndConstruct(EI.second);
484  InNeighbors[EI.second].insert(EI.first);
485  OutNeighbors[EI.first].insert(EI.second);
486  };
487 
488  return p;
489  }
490 };
491 }
492 }
493 #endif
llvm::xray::Graph::operator[]
EdgeAttribute & operator[](const EdgeIdentifier &I)
Looks up the edge with identifier I, if it does not exist it default constructs it,...
Definition: Graph.h:388
llvm::xray::Graph::EdgeView::size
size_type size() const
Definition: Graph.h:327
llvm::xray::Graph::outEdges
InOutEdgeView< false, true > outEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which start at a vertex I.
Definition: Graph.h:361
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::xray::Graph::at
Expected< EdgeAttribute & > at(const EdgeIdentifier &I)
Looks up an edge with Identifier I, or an error if it does not exist.
Definition: Graph.h:417
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::xray::Graph::inEdges
InOutEdgeView< true, false > inEdges(const VertexIdentifier I) const
Definition: Graph.h:375
llvm::xray::Graph::ConstEdgeIterator
typename EdgeMapT::const_iterator ConstEdgeIterator
A const iterator for iterating through the entire edge set of the graph.
Definition: Graph.h:298
llvm::xray::Graph::EdgeView::empty
bool empty() const
Definition: Graph.h:328
llvm::xray::Graph::EdgeView::cbegin
const_iterator cbegin() const
Definition: Graph.h:323
llvm::xray::Graph::VertexView::begin
iterator begin()
Definition: Graph.h:284
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::xray::Graph::InOutEdgeView::end
const_iterator end() const
Definition: Graph.h:241
llvm::xray::Graph::EdgeView::end
const_iterator end() const
Definition: Graph.h:326
llvm::xray::Graph::InOutEdgeView::iterator
NeighborEdgeIteratorT< isConst, isOut > iterator
Definition: Graph.h:200
llvm::xray::Graph::InOutEdgeView::end
iterator end()
Definition: Graph.h:228
llvm::xray::Graph
A Graph object represents a Directed Graph and is used in XRay to compute and store function call gra...
Definition: Graph.h:74
llvm::xray::Graph::VertexView::const_iterator
ConstVertexIterator const_iterator
Definition: Graph.h:277
llvm::xray::Graph::size_type
std::size_t size_type
Definition: Graph.h:89
Error.h
NL
#define NL
Definition: DetailedRecordsBackend.cpp:30
DenseMap.h
llvm::xray::Graph::InOutEdgeView::InternalEdgeMapT
std::conditional_t< isConst, const EdgeMapT, EdgeMapT > InternalEdgeMapT
Definition: Graph.h:204
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:211
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::Expected
Tagged union holding either a T or a Error.
Definition: APFloat.h:42
llvm::xray::Graph::clear
void clear()
Empty the Graph.
Definition: Graph.h:340
llvm::xray::Graph::EdgeView::const_iterator
ConstEdgeIterator const_iterator
Definition: Graph.h:314
llvm::xray::Graph::VertexView::cbegin
const_iterator cbegin() const
Definition: Graph.h:286
llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute >
p
the resulting code requires compare and branches when and if * p
Definition: README.txt:396
llvm::xray::Graph::InEdgeIterator
NeighborEdgeIteratorT< false, false > InEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
Definition: Graph.h:180
llvm::xray::Graph::VertexView::empty
bool empty() const
Definition: Graph.h:291
llvm::xray::Graph::insert
std::pair< VertexIterator, bool > insert(const std::pair< VertexIdentifier, VertexAttribute > &Val)
Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.
Definition: Graph.h:448
llvm::xray::Graph::outEdges
InOutEdgeView< true, true > outEdges(const VertexIdentifier I) const
Definition: Graph.h:365
llvm::DenseMapBase< DenseMap< VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute > >, VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute > >::const_iterator
DenseMapIterator< VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute >, true > const_iterator
Definition: DenseMap.h:72
llvm::xray::Graph::at
Expected< const EdgeAttribute & > at(const EdgeIdentifier &I) const
Definition: Graph.h:426
llvm::xray::Graph::EdgeIdentifier
std::pair< VI, VI > EdgeIdentifier
Definition: Graph.h:78
llvm::xray::Graph::EdgeIterator
typename EdgeMapT::iterator EdgeIterator
An iterator for iterating through the entire edge set of the graph.
Definition: Graph.h:303
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
llvm::xray::Graph::insert
std::pair< EdgeIterator, bool > insert(std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
Definition: Graph.h:478
llvm::xray::Graph::ConstOutEdgeIterator
NeighborEdgeIteratorT< true, true > ConstOutEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
Definition: Graph.h:186
llvm::xray::Graph::InOutEdgeView::begin
const_iterator begin() const
Definition: Graph.h:226
llvm::xray::Graph::VertexIdentifier
VI VertexIdentifier
These objects are used to name edges and vertices in the graph.
Definition: Graph.h:77
llvm::xray::Graph::VertexView::VertexView
VertexView(GraphT &_G)
Definition: Graph.h:292
llvm::xray::Graph::VertexView::end
iterator end()
Definition: Graph.h:285
llvm::xray::Graph::VertexView::cend
const_iterator cend() const
Definition: Graph.h:287
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
VI
@ VI
Definition: SIInstrInfo.cpp:7679
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
llvm::xray::Graph::InOutEdgeView::cbegin
const_iterator cbegin() const
Definition: Graph.h:219
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::const_iterator
ConstIterator const_iterator
Definition: DenseSet.h:171
llvm::xray::Graph::VertexIterator
typename VertexMapT::iterator VertexIterator
An iterator type for iterating through the whole vertex set of the graph.
Definition: Graph.h:266
llvm::xray::Graph::InOutEdgeView::cend
const_iterator cend() const
Definition: Graph.h:234
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::DenseMap< EdgeIdentifier, EdgeAttribute >
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::xray::Graph::InOutEdgeView::size
size_type size() const
Definition: Graph.h:243
llvm::xray::Graph::vertices
VertexView< false > vertices()
Returns a view object allowing iteration over the vertices of the graph.
Definition: Graph.h:349
G
#define G(x, y, z)
Definition: MD5.cpp:57
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::xray::Graph::edges
EdgeView< false > edges()
Returns a view object allowing iteration over the edges of the graph.
Definition: Graph.h:355
llvm::xray::Graph::insert
std::pair< EdgeIterator, bool > insert(const std::pair< EdgeIdentifier, EdgeAttribute > &Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
Definition: Graph.h:461
llvm::xray::Graph::VertexView::end
const_iterator end() const
Definition: Graph.h:289
llvm::xray::Graph::EdgeView::iterator
std::conditional_t< isConst, ConstEdgeIterator, EdgeIterator > iterator
Definition: Graph.h:313
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::DenseMapBase::FindAndConstruct
value_type & FindAndConstruct(const KeyT &Key)
Definition: DenseMap.h:321
llvm::xray::Graph::VertexView::size
size_type size() const
Definition: Graph.h:290
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2098
llvm::AMDGPU::HSAMD::Kernel::Arg::Key::IsConst
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
Definition: AMDGPUMetadata.h:190
llvm::xray::Graph::edges
EdgeView< true > edges() const
Definition: Graph.h:357
llvm::xray::Graph::EdgeView::begin
const_iterator begin() const
Definition: Graph.h:325
llvm::xray::Graph::count
size_type count(const EdgeIdentifier &I) const
Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.
Definition: Graph.h:443
llvm::xray::Graph::insert
std::pair< VertexIterator, bool > insert(std::pair< VertexIdentifier, VertexAttribute > &&Val)
Definition: Graph.h:453
llvm::xray::Graph::VertexView::begin
const_iterator begin() const
Definition: Graph.h:288
llvm::xray::Graph::OutEdgeIterator
NeighborEdgeIteratorT< false, true > OutEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
Definition: Graph.h:191
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::make_error_code
std::error_code make_error_code(BitcodeError E)
Definition: BitcodeReader.h:270
llvm::xray::Graph::EdgeView::begin
iterator begin()
Definition: Graph.h:321
llvm::xray::Graph::EdgeView::cend
const_iterator cend() const
Definition: Graph.h:324
llvm::xray::Graph::EdgeView::GraphT
std::conditional_t< isConst, const Graph, Graph > GraphT
Definition: Graph.h:315
llvm::xray::Graph::InOutEdgeView::begin
iterator begin()
Definition: Graph.h:212
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::xray::Graph::EdgeView::end
iterator end()
Definition: Graph.h:322
llvm::xray::Graph::InOutEdgeView
A class for ranging over the incoming edges incident to a vertex.
Definition: Graph.h:198
llvm::xray::Graph::EdgeView
A class for ranging over all the edges in the graph.
Definition: Graph.h:310
llvm::xray::Graph::count
size_type count(const VertexIdentifier &I) const
Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.
Definition: Graph.h:437
llvm::xray::Graph::ConstVertexIterator
typename VertexMapT::const_iterator ConstVertexIterator
A const iterator type for iterating through the whole vertex set of the graph.
Definition: Graph.h:261
llvm::xray::Graph::InOutEdgeView::empty
bool empty() const
Definition: Graph.h:251
llvm::DenseMapBase< DenseMap< VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute > >, VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute > >::iterator
DenseMapIterator< VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute > > iterator
Definition: DenseMap.h:70
llvm::xray::Graph::VertexView::GraphT
std::conditional_t< isConst, const Graph, Graph > GraphT
Definition: Graph.h:278
llvm::xray::Graph::vertices
VertexView< true > vertices() const
Definition: Graph.h:351
llvm::xray::Graph::EdgeView::EdgeView
EdgeView(GraphT &_G)
Definition: Graph.h:329
llvm::xray::Graph::at
Expected< const VertexAttribute & > at(const VertexIdentifier &I) const
Definition: Graph.h:407
llvm::xray::Graph::ConstInEdgeIterator
NeighborEdgeIteratorT< true, false > ConstInEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
Definition: Graph.h:175
llvm::xray::Graph::operator[]
VertexAttribute & operator[](const VertexIdentifier &I)
Looks up the vertex with identifier I, if it does not exist it default constructs it.
Definition: Graph.h:381
llvm::xray::Graph::at
Expected< VertexAttribute & > at(const VertexIdentifier &I)
Looks up a vertex with Identifier I, or an error if it does not exist.
Definition: Graph.h:398
llvm::xray::Graph::VertexView
A class for ranging over the vertices in the graph.
Definition: Graph.h:273
llvm::xray::Graph::InOutEdgeView::GraphT
std::conditional_t< isConst, const Graph, Graph > GraphT
Definition: Graph.h:202
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::xray::Graph::InOutEdgeView::const_iterator
NeighborEdgeIteratorT< true, isOut > const_iterator
Definition: Graph.h:201
llvm::xray::Graph::inEdges
InOutEdgeView< false, false > inEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which point to a vertex I.
Definition: Graph.h:371
llvm::xray::Graph::VertexView::iterator
std::conditional_t< isConst, ConstVertexIterator, VertexIterator > iterator
Definition: Graph.h:276
llvm::xray::Graph::InOutEdgeView::InOutEdgeView
InOutEdgeView(GraphT &G, VertexIdentifier A)
Definition: Graph.h:253