13#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
14#define LLVM_CODEGEN_PBQP_GRAPH_H
33 return std::numeric_limits<NodeId>::max();
38 return std::numeric_limits<EdgeId>::max();
45 template <
typename SolverT>
48 using CostAllocator =
typename SolverT::CostAllocator;
53 using Vector =
typename SolverT::Vector;
54 using Matrix =
typename SolverT::Matrix;
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;
68 NodeEntry(
VectorPtr Costs) : Costs(std::move(Costs)) {}
70 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
71 return std::numeric_limits<AdjEdgeIdx>::max();
74 AdjEdgeIdx addAdjEdgeId(
EdgeId EId) {
75 AdjEdgeIdx
Idx = AdjEdgeIds.size();
76 AdjEdgeIds.push_back(EId);
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();
197 Nodes[NId] = std::move(
N);
200 Nodes.push_back(std::move(
N));
205 EdgeId addConstructedEdge(EdgeEntry
E) {
207 "Attempt to add duplicate edge.");
209 if (!FreeEdgeIds.empty()) {
210 EId = FreeEdgeIds.back();
211 FreeEdgeIds.pop_back();
212 Edges[EId] = std::move(
E);
215 Edges.push_back(std::move(
E));
218 EdgeEntry &
NE = getEdge(EId);
221 NE.connect(*
this, EId);
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>
377 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
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.");
414 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
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);
465 template <
typename OtherVectorT>
467 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
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>
509 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
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();
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
static EdgeId invalidEdgeId()
Returns a value representing an invalid (non-existent) edge.
NodeEntry::AdjEdgeItr begin() const
AdjEdgeIdSet(const NodeEntry &NE)
NodeEntry::AdjEdgeItr end() const
NodeEntry::AdjEdgeList::size_type size() const
EdgeIdSet(const Graph &G)
NodeVector::size_type size() const
EdgeItr(EdgeId CurEId, const Graph &G)
bool operator==(const EdgeItr &O) const
bool operator!=(const EdgeItr &O) const
NodeIdSet(const Graph &G)
NodeVector::size_type size() const
bool operator!=(const NodeItr &O) const
std::forward_iterator_tag iterator_category
bool operator==(const NodeItr &O) const
NodeItr(NodeId CurNId, const Graph &G)
void unsetSolver()
Release from solver instance.
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
NodeMetadata & getNodeMetadata(NodeId NId)
void disconnectEdge(EdgeId EId, NodeId NId)
Disconnect an edge from the given node.
void setNodeCosts(NodeId NId, OtherVectorT Costs)
Set a node's cost vector.
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
Add an edge between the given nodes with the given costs.
typename SolverT::GraphMetadata GraphMetadata
const GraphMetadata & getMetadata() const
Get a const-reference to the graph metadata.
typename SolverT::EdgeMetadata EdgeMetadata
void removeNode(NodeId NId)
Remove a node from the graph.
NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId)
Get the "other" node connected to this edge.
AdjEdgeIdSet adjEdgeIds(NodeId NId)
Graph()=default
Construct an empty PBQP graph.
typename SolverT::Matrix Matrix
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
unsigned getNumNodes() const
Get the number of nodes in the graph.
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
EdgeMetadata & getEdgeMetadata(EdgeId EId)
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge's cost matrix.
typename SolverT::Vector Vector
NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs)
Add a node bypassing the cost allocator.
NodeIdSet nodeIds() const
bool empty() const
Returns true if the graph is empty.
void setSolver(SolverT &S)
Lock this graph to the given solver instance in preparation for running the solver.
void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs)
Update an edge's cost matrix.
typename SolverT::NodeMetadata NodeMetadata
typename CostAllocator::MatrixPtr MatrixPtr
const MatrixPtr & getEdgeCostsPtr(EdgeId EId) const
Get a MatrixPtr to a node's cost matrix.
typename SolverT::RawMatrix RawMatrix
void clear()
Remove all nodes and edges from the graph.
typename SolverT::RawVector RawVector
const NodeMetadata & getNodeMetadata(NodeId NId) const
typename NodeEntry::AdjEdgeItr AdjEdgeItr
Graph(GraphMetadata Metadata)
Construct an empty PBQP graph with the given graph metadata.
void disconnectAllNeighborsFromNode(NodeId NId)
Convenience method to disconnect all neighbours from the given node.
void reconnectEdge(EdgeId EId, NodeId NId)
Re-attach an edge to its nodes.
const EdgeMetadata & getEdgeMetadata(EdgeId EId) const
void removeEdge(EdgeId EId)
Remove an edge from the graph.
const Vector & getNodeCosts(NodeId NId) const
Get a node's cost vector.
NodeId addNode(OtherVectorT Costs)
Add a node with the given costs.
GraphMetadata & getMetadata()
Get a reference to the graph metadata.
unsigned getNumEdges() const
Get the number of edges in the graph.
typename CostAllocator::VectorPtr VectorPtr
const VectorPtr & getNodeCostsPtr(NodeId NId) const
Get a VectorPtr to a node's cost vector.
EdgeId findEdge(NodeId N1Id, NodeId N2Id)
Get the edge connecting two nodes.
EdgeIdSet edgeIds() const
NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
Add an edge bypassing the cost allocator.
This is an optimization pass for GlobalISel generic memory operations.
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.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Implement std::hash so that hash_code can be used in STL containers.