Go to the documentation of this file.
13 #ifndef LLVM_XRAY_GRAPH_H
14 #define LLVM_XRAY_GRAPH_H
16 #include <initializer_list>
18 #include <type_traits>
72 template <
typename VertexAttribute,
typename EdgeAttribute,
73 typename VI = int32_t>
127 template <
bool IsConst,
bool IsOut,
130 std::conditional_t<IsConst, const EdgeValueType, EdgeValueType>>
131 class NeighborEdgeIteratorT
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>;
139 friend class NeighborEdgeIteratorT<
true, IsOut, BaseIt,
142 InternalEdgeMapT *MP;
146 template <
bool IsConstDest,
147 typename = std::enable_if<IsConstDest && !IsConst>>
148 operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
150 return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
154 NeighborEdgeIteratorT() =
default;
155 NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,
158 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
159 typename std::iterator_traits<BaseIt>::iterator_category,
T>(_I),
164 return *(MP->find({*(this->
I), SI}));
166 return *(MP->find({
SI, *(this->
I)}));
200 using iterator = NeighborEdgeIteratorT<isConst, isOut>;
202 using GraphT = std::conditional_t<isConst, const Graph, Graph>;
204 std::conditional_t<isConst, const EdgeMapT, EdgeMapT>;
213 auto It =
NL.find(A);
216 return iterator(It->second.begin(), &
M, A);
220 auto It =
NL.find(A);
229 auto It =
NL.find(A);
232 return iterator(It->second.end(), &
M, A);
235 auto It =
NL.find(A);
248 return I->second.size();
251 bool empty()
const {
return NL.count(A) == 0; };
254 :
M(
G.Edges), A(A),
NL(isOut ?
G.OutNeighbors :
G.InNeighbors) {}
276 std::conditional_t<isConst, ConstVertexIterator, VertexIterator>;
278 using GraphT = std::conditional_t<isConst, const Graph, Graph>;
291 bool empty()
const {
return G.Vertices.empty(); }
313 std::conditional_t<isConst, ConstEdgeIterator, EdgeIterator>;
315 using GraphT = std::conditional_t<isConst, const Graph, Graph>;
328 bool empty()
const {
return G.Edges.empty(); }
344 OutNeighbors.
clear();
392 InNeighbors[
I.second].
insert(
I.first);
393 OutNeighbors[
I.first].
insert(
I.second);
399 auto It = Vertices.
find(
I);
400 if (It == Vertices.
end())
401 return make_error<StringError>(
402 "Vertex Identifier Does Not Exist",
408 auto It = Vertices.
find(
I);
409 if (It == Vertices.
end())
410 return make_error<StringError>(
411 "Vertex Identifier 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",
427 auto It = Edges.
find(
I);
428 if (It == Edges.
end())
429 return make_error<StringError>(
430 "Edge Identifier Does Not Exist",
447 std::pair<VertexIterator, bool>
448 insert(
const std::pair<VertexIdentifier, VertexAttribute> &Val) {
449 return Vertices.
insert(Val);
452 std::pair<VertexIterator, bool>
453 insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {
460 std::pair<EdgeIterator, bool>
461 insert(
const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {
462 const auto &
p = Edges.
insert(Val);
464 const auto &EI = Val.first;
467 InNeighbors[EI.second].
insert(EI.first);
468 OutNeighbors[EI.first].
insert(EI.second);
477 std::pair<EdgeIterator, bool>
478 insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {
484 InNeighbors[EI.second].
insert(EI.first);
485 OutNeighbors[EI.first].
insert(EI.second);
EdgeAttribute & operator[](const EdgeIdentifier &I)
Looks up the edge with identifier I, if it does not exist it default constructs it,...
InOutEdgeView< false, true > outEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which start at a vertex I.
This is an optimization pass for GlobalISel generic memory operations.
Expected< EdgeAttribute & > at(const EdgeIdentifier &I)
Looks up an edge with Identifier I, or an error if it does not exist.
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
InOutEdgeView< true, false > inEdges(const VertexIdentifier I) const
typename EdgeMapT::const_iterator ConstEdgeIterator
A const iterator for iterating through the entire edge set of the graph.
const_iterator cbegin() const
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
const_iterator end() const
const_iterator end() const
NeighborEdgeIteratorT< isConst, isOut > iterator
A Graph object represents a Directed Graph and is used in XRay to compute and store function call gra...
ConstVertexIterator const_iterator
std::conditional_t< isConst, const EdgeMapT, EdgeMapT > InternalEdgeMapT
CRTP base class for adapting an iterator to a different type.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Tagged union holding either a T or a Error.
void clear()
Empty the Graph.
ConstEdgeIterator const_iterator
const_iterator cbegin() const
the resulting code requires compare and branches when and if * p
NeighborEdgeIteratorT< false, false > InEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
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.
InOutEdgeView< true, true > outEdges(const VertexIdentifier I) const
DenseMapIterator< VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute >, true > const_iterator
Expected< const EdgeAttribute & > at(const EdgeIdentifier &I) const
std::pair< VI, VI > EdgeIdentifier
typename EdgeMapT::iterator EdgeIterator
An iterator for iterating through the entire edge set of the graph.
std::pair< EdgeIterator, bool > insert(std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
NeighborEdgeIteratorT< true, true > ConstOutEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
const_iterator begin() const
VI VertexIdentifier
These objects are used to name edges and vertices in the graph.
const_iterator cend() const
Implements a dense probed hash-table based set.
const_iterator cbegin() const
ConstIterator const_iterator
typename VertexMapT::iterator VertexIterator
An iterator type for iterating through the whole vertex set of the graph.
const_iterator cend() const
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
VertexView< false > vertices()
Returns a view object allowing iteration over the vertices of the graph.
iterator find(const_arg_type_t< KeyT > Val)
EdgeView< false > edges()
Returns a view object allowing iteration over the edges of the graph.
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.
const_iterator end() const
std::conditional_t< isConst, ConstEdgeIterator, EdgeIterator > iterator
StandardInstrumentations SI(Debug, VerifyEach)
value_type & FindAndConstruct(const KeyT &Key)
APInt operator*(APInt a, uint64_t RHS)
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
EdgeView< true > edges() const
const_iterator begin() const
size_type count(const EdgeIdentifier &I) const
Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.
std::pair< VertexIterator, bool > insert(std::pair< VertexIdentifier, VertexAttribute > &&Val)
const_iterator begin() const
NeighborEdgeIteratorT< false, true > OutEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::error_code make_error_code(BitcodeError E)
const_iterator cend() const
std::conditional_t< isConst, const Graph, Graph > GraphT
A class for ranging over the incoming edges incident to a vertex.
A class for ranging over all the edges in the graph.
size_type count(const VertexIdentifier &I) const
Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.
typename VertexMapT::const_iterator ConstVertexIterator
A const iterator type for iterating through the whole vertex set of the graph.
DenseMapIterator< VertexIdentifier, VertexAttribute, DenseMapInfo< VertexIdentifier >, llvm::detail::DenseMapPair< VertexIdentifier, VertexAttribute > > iterator
std::conditional_t< isConst, const Graph, Graph > GraphT
VertexView< true > vertices() const
Expected< const VertexAttribute & > at(const VertexIdentifier &I) const
NeighborEdgeIteratorT< true, false > ConstInEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
VertexAttribute & operator[](const VertexIdentifier &I)
Looks up the vertex with identifier I, if it does not exist it default constructs it.
Expected< VertexAttribute & > at(const VertexIdentifier &I)
Looks up a vertex with Identifier I, or an error if it does not exist.
A class for ranging over the vertices in the graph.
std::conditional_t< isConst, const Graph, Graph > GraphT
NeighborEdgeIteratorT< true, isOut > const_iterator
InOutEdgeView< false, false > inEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which point to a vertex I.
std::conditional_t< isConst, ConstVertexIterator, VertexIterator > iterator
InOutEdgeView(GraphT &G, VertexIdentifier A)