Go to the documentation of this file.
13 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
14 #define LLVM_CODEGEN_PBQP_GRAPH_H
45 template <
typename SolverT>
48 using CostAllocator =
typename SolverT::CostAllocator;
55 using VectorPtr =
typename CostAllocator::VectorPtr;
56 using MatrixPtr =
typename CostAllocator::MatrixPtr;
64 using AdjEdgeList = std::vector<EdgeId>;
65 using AdjEdgeIdx = AdjEdgeList::size_type;
66 using AdjEdgeItr = AdjEdgeList::const_iterator;
70 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
74 AdjEdgeIdx addAdjEdgeId(
EdgeId EId) {
75 AdjEdgeIdx Idx = AdjEdgeIds.size();
76 AdjEdgeIds.push_back(EId);
80 void removeAdjEdgeId(
Graph &
G,
NodeId ThisNId, AdjEdgeIdx Idx) {
87 G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
88 AdjEdgeIds[Idx] = AdjEdgeIds.back();
89 AdjEdgeIds.pop_back();
92 const AdjEdgeList& getAdjEdgeIds()
const {
return AdjEdgeIds; }
98 AdjEdgeList AdjEdgeIds;
107 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
108 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
111 void connectToN(
Graph &
G,
EdgeId ThisEdgeId,
unsigned NIdx) {
112 assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
113 "Edge already connected to NIds[NIdx].");
114 NodeEntry &
N =
G.getNode(NIds[NIdx]);
115 ThisEdgeAdjIdxs[NIdx] =
N.addAdjEdgeId(ThisEdgeId);
119 connectToN(
G, ThisEdgeId, 0);
120 connectToN(
G, ThisEdgeId, 1);
123 void setAdjEdgeIdx(
NodeId NId,
typename NodeEntry::AdjEdgeIdx NewIdx) {
125 ThisEdgeAdjIdxs[0] = NewIdx;
127 assert(NId == NIds[1] &&
"Edge not connected to NId");
128 ThisEdgeAdjIdxs[1] = NewIdx;
132 void disconnectFromN(
Graph &
G,
unsigned NIdx) {
133 assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
134 "Edge not connected to NIds[NIdx].");
135 NodeEntry &
N =
G.getNode(NIds[NIdx]);
136 N.removeAdjEdgeId(
G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
137 ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
142 disconnectFromN(
G, 0);
144 assert(NId == NIds[1] &&
"Edge does not connect NId");
145 disconnectFromN(
G, 1);
149 NodeId getN1Id()
const {
return NIds[0]; }
150 NodeId getN2Id()
const {
return NIds[1]; }
157 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
163 CostAllocator CostAlloc;
164 SolverT *Solver =
nullptr;
166 using NodeVector = std::vector<NodeEntry>;
167 using FreeNodeVector = std::vector<NodeId>;
169 FreeNodeVector FreeNodeIds;
171 using EdgeVector = std::vector<EdgeEntry>;
172 using FreeEdgeVector = std::vector<EdgeId>;
174 FreeEdgeVector FreeEdgeIds;
180 NodeEntry &getNode(
NodeId NId) {
181 assert(NId < Nodes.size() &&
"Out of bound NodeId");
184 const NodeEntry &getNode(
NodeId NId)
const {
185 assert(NId < Nodes.size() &&
"Out of bound NodeId");
189 EdgeEntry& getEdge(
EdgeId EId) {
return Edges[EId]; }
190 const EdgeEntry& getEdge(
EdgeId EId)
const {
return Edges[EId]; }
192 NodeId addConstructedNode(NodeEntry
N) {
194 if (!FreeNodeIds.empty()) {
195 NId = FreeNodeIds.back();
196 FreeNodeIds.pop_back();
205 EdgeId addConstructedEdge(EdgeEntry
E) {
207 "Attempt to add duplicate edge.");
209 if (!FreeEdgeIds.empty()) {
210 EId = FreeEdgeIds.back();
211 FreeEdgeIds.pop_back();
218 EdgeEntry &
NE = getEdge(EId);
221 NE.connect(*
this, EId);
225 void operator=(
const Graph &Other) {}
239 : CurNId(CurNId), EndNId(
G.Nodes.
size()), FreeNodeIds(
G.FreeNodeIds) {
240 this->CurNId = findNextInUse(CurNId);
250 while (NId < EndNId &&
is_contained(FreeNodeIds, NId)) {
257 const FreeNodeVector &FreeNodeIds;
263 : CurEId(CurEId), EndEId(
G.Edges.
size()), FreeEdgeIds(
G.FreeEdgeIds) {
264 this->CurEId = findNextInUse(CurEId);
274 while (EId < EndEId &&
is_contained(FreeEdgeIds, EId)) {
281 const FreeEdgeVector &FreeEdgeIds;
291 bool empty()
const {
return G.Nodes.empty(); }
293 typename NodeVector::size_type
size()
const {
294 return G.Nodes.size() -
G.FreeNodeIds.size();
308 bool empty()
const {
return G.Edges.empty(); }
310 typename NodeVector::size_type
size()
const {
311 return G.Edges.size() -
G.FreeEdgeIds.size();
322 typename NodeEntry::AdjEdgeItr
begin()
const {
323 return NE.getAdjEdgeIds().begin();
326 typename NodeEntry::AdjEdgeItr
end()
const {
327 return NE.getAdjEdgeIds().end();
330 bool empty()
const {
return NE.getAdjEdgeIds().empty(); }
332 typename NodeEntry::AdjEdgeList::size_type
size()
const {
333 return NE.getAdjEdgeIds().size();
357 assert(!Solver &&
"Solver already set. Call unsetSolver().");
360 Solver->handleAddNode(NId);
362 Solver->handleAddEdge(EId);
367 assert(Solver &&
"Solver not set.");
374 template <
typename OtherVectorT>
378 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
380 Solver->handleAddNode(NId);
395 template <
typename OtherVectorPtrT>
397 NodeId NId = addConstructedNode(NodeEntry(Costs));
399 Solver->handleAddNode(NId);
408 template <
typename OtherVectorT>
412 "Matrix dimensions mismatch.");
415 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
417 Solver->handleAddEdge(EId);
433 template <
typename OtherMatrixPtrT>
435 OtherMatrixPtrT Costs) {
438 "Matrix dimensions mismatch.");
440 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
442 Solver->handleAddEdge(EId);
447 bool empty()
const {
return NodeIdSet(*this).empty(); }
449 NodeIdSet
nodeIds()
const {
return NodeIdSet(*
this); }
450 EdgeIdSet
edgeIds()
const {
return EdgeIdSet(*
this); }
465 template <
typename OtherVectorT>
469 Solver->handleSetNodeCosts(NId, *AllocatedCosts);
470 getNode(NId).Costs = AllocatedCosts;
482 return getNode(NId).Costs;
493 return getNode(NId).Metadata;
497 return getNode(NId).Metadata;
501 return getNode(NId).getAdjEdgeIds().size();
507 template <
typename OtherMatrixT>
511 Solver->handleUpdateCosts(EId, *AllocatedCosts);
512 getEdge(EId).Costs = AllocatedCosts;
524 return getEdge(EId).Costs;
531 return *getEdge(EId).Costs;
535 return getEdge(EId).Metadata;
539 return getEdge(EId).Metadata;
546 return getEdge(EId).getN1Id();
553 return getEdge(EId).getN2Id();
561 EdgeEntry &
E = getEdge(EId);
562 if (
E.getN1Id() == NId) {
587 Solver->handleRemoveNode(NId);
588 NodeEntry &
N = getNode(NId);
591 AEEnd =
N.adjEdgesEnd();
597 FreeNodeIds.push_back(NId);
627 Solver->handleDisconnectEdge(EId, NId);
629 EdgeEntry &
E = getEdge(EId);
630 E.disconnectFrom(*
this, NId);
645 EdgeEntry &
E = getEdge(EId);
646 E.connectTo(*
this, EId, NId);
648 Solver->handleReconnectEdge(EId, NId);
655 Solver->handleRemoveEdge(EId);
656 EdgeEntry &
E = getEdge(EId);
658 FreeEdgeIds.push_back(EId);
659 Edges[EId].invalidate();
674 #endif // LLVM_CODEGEN_PBQP_GRAPH_H
EdgeId findEdge(NodeId N1Id, NodeId N2Id)
Get the edge connecting two nodes.
This is an optimization pass for GlobalISel generic memory operations.
NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
Add an edge bypassing the cost allocator.
typename RegAllocSolverImpl ::RawVector RawVector
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
typename RegAllocSolverImpl ::Matrix Matrix
unsigned getNumEdges() const
Get the number of edges in the graph.
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
Add an edge between the given nodes with the given costs.
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
NodeEntry::AdjEdgeItr end() const
So we should use XX3Form_Rcr to implement intrinsic Convert DP outs ins xscvdpsp No builtin are required Round &Convert QP DP(dword[1] is set to zero) No builtin are required Round to Quad Precision because you need to assign rounding mode in instruction Provide builtin(set f128:$vT,(int_ppc_vsx_xsrqpi f128:$vB))(set f128 yields< n x< ty > >< result > yields< ty >< result > No builtin are required Load Store Vector
std::forward_iterator_tag iterator_category
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
const GraphMetadata & getMetadata() const
Get a const-reference to the graph metadata.
NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId)
Get the "other" node connected to this edge.
unsigned getNumNodes() const
Get the number of nodes in the graph.
const MatrixPtr & getEdgeCostsPtr(EdgeId EId) const
Get a MatrixPtr to a node's cost matrix.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool operator!=(const NodeItr &O) const
const NodeMetadata & getNodeMetadata(NodeId NId) const
const Vector & getNodeCosts(NodeId NId) const
Get a node's cost vector.
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
EdgeMetadata & getEdgeMetadata(EdgeId EId)
void removeNode(NodeId NId)
Remove a node from the graph.
void disconnectEdge(EdgeId EId, NodeId NId)
Disconnect an edge from the given node.
bool operator!=(const EdgeItr &O) const
typename RegAllocSolverImpl ::Vector Vector
bool operator==(const NodeItr &O) const
EdgeItr(EdgeId CurEId, const Graph &G)
void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs)
Update an edge's cost matrix.
void setNodeCosts(NodeId NId, OtherVectorT Costs)
Set a node's cost vector.
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge's cost matrix.
void disconnectAllNeighborsFromNode(NodeId NId)
Convenience method to disconnect all neighbours from the given node.
GraphMetadata & getMetadata()
Get a reference to the graph metadata.
NodeItr(NodeId CurNId, const Graph &G)
AdjEdgeIdSet(const NodeEntry &NE)
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
const VectorPtr & getNodeCostsPtr(NodeId NId) const
Get a VectorPtr to a node's cost vector.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
typename RegAllocSolverImpl ::RawMatrix RawMatrix
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const EdgeMetadata & getEdgeMetadata(EdgeId EId) const
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool empty() const
Returns true if the graph is empty.
NodeIdSet nodeIds() const
typename CostAllocator::VectorPtr VectorPtr
NodeEntry::AdjEdgeList::size_type size() const
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
static EdgeId invalidEdgeId()
Returns a value representing an invalid (non-existent) edge.
NodeEntry::AdjEdgeItr begin() const
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
AdjEdgeIdSet adjEdgeIds(NodeId NId)
EdgeIdSet edgeIds() const
NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs)
Add a node bypassing the cost allocator.
NodeVector::size_type size() const
Graph()=default
Construct an empty PBQP graph.
NodeMetadata & getNodeMetadata(NodeId NId)
bool operator==(const EdgeItr &O) const
NodeIdSet(const Graph &G)
Graph(GraphMetadata Metadata)
Construct an empty PBQP graph with the given graph metadata.
NodeId addNode(OtherVectorT Costs)
Add a node with the given costs.
void reconnectEdge(EdgeId EId, NodeId NId)
Re-attach an edge to its nodes.
typename RegAllocSolverImpl ::EdgeMetadata EdgeMetadata
void setSolver(SolverT &S)
Lock this graph to the given solver instance in preparation for running the solver.
NodeVector::size_type size() const
void clear()
Remove all nodes and edges from the graph.
EdgeIdSet(const Graph &G)
typename NodeEntry::AdjEdgeItr AdjEdgeItr
void removeEdge(EdgeId EId)
Remove an edge from the graph.
void unsetSolver()
Release from solver instance.
typename CostAllocator::MatrixPtr MatrixPtr
typename RegAllocSolverImpl ::NodeMetadata NodeMetadata