LLVM 19.0.0git
Graph.h
Go to the documentation of this file.
1//===- Graph.h - PBQP Graph -------------------------------------*- 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// PBQP Graph class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
14#define LLVM_CODEGEN_PBQP_GRAPH_H
15
16#include "llvm/ADT/STLExtras.h"
17#include <algorithm>
18#include <cassert>
19#include <iterator>
20#include <limits>
21#include <vector>
22
23namespace llvm {
24namespace PBQP {
25
26 class GraphBase {
27 public:
30
31 /// Returns a value representing an invalid (non-existent) node.
33 return std::numeric_limits<NodeId>::max();
34 }
35
36 /// Returns a value representing an invalid (non-existent) edge.
38 return std::numeric_limits<EdgeId>::max();
39 }
40 };
41
42 /// PBQP Graph class.
43 /// Instances of this class describe PBQP problems.
44 ///
45 template <typename SolverT>
46 class Graph : public GraphBase {
47 private:
48 using CostAllocator = typename SolverT::CostAllocator;
49
50 public:
51 using RawVector = typename SolverT::RawVector;
52 using RawMatrix = typename SolverT::RawMatrix;
53 using Vector = typename SolverT::Vector;
54 using Matrix = typename SolverT::Matrix;
55 using VectorPtr = typename CostAllocator::VectorPtr;
56 using MatrixPtr = typename CostAllocator::MatrixPtr;
57 using NodeMetadata = typename SolverT::NodeMetadata;
58 using EdgeMetadata = typename SolverT::EdgeMetadata;
59 using GraphMetadata = typename SolverT::GraphMetadata;
60
61 private:
62 class NodeEntry {
63 public:
64 using AdjEdgeList = std::vector<EdgeId>;
65 using AdjEdgeIdx = AdjEdgeList::size_type;
66 using AdjEdgeItr = AdjEdgeList::const_iterator;
67
68 NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}
69
70 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
71 return std::numeric_limits<AdjEdgeIdx>::max();
72 }
73
74 AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
75 AdjEdgeIdx Idx = AdjEdgeIds.size();
76 AdjEdgeIds.push_back(EId);
77 return Idx;
78 }
79
80 void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
81 // Swap-and-pop for fast removal.
82 // 1) Update the adj index of the edge currently at back().
83 // 2) Move last Edge down to Idx.
84 // 3) pop_back()
85 // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
86 // redundant, but both operations are cheap.
87 G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
88 AdjEdgeIds[Idx] = AdjEdgeIds.back();
89 AdjEdgeIds.pop_back();
90 }
91
92 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
93
94 VectorPtr Costs;
96
97 private:
98 AdjEdgeList AdjEdgeIds;
99 };
100
101 class EdgeEntry {
102 public:
103 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
104 : Costs(std::move(Costs)) {
105 NIds[0] = N1Id;
106 NIds[1] = N2Id;
107 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
108 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
109 }
110
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);
116 }
117
118 void connect(Graph &G, EdgeId ThisEdgeId) {
119 connectToN(G, ThisEdgeId, 0);
120 connectToN(G, ThisEdgeId, 1);
121 }
122
123 void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
124 if (NId == NIds[0])
125 ThisEdgeAdjIdxs[0] = NewIdx;
126 else {
127 assert(NId == NIds[1] && "Edge not connected to NId");
128 ThisEdgeAdjIdxs[1] = NewIdx;
129 }
130 }
131
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();
138 }
139
140 void disconnectFrom(Graph &G, NodeId NId) {
141 if (NId == NIds[0])
142 disconnectFromN(G, 0);
143 else {
144 assert(NId == NIds[1] && "Edge does not connect NId");
145 disconnectFromN(G, 1);
146 }
147 }
148
149 NodeId getN1Id() const { return NIds[0]; }
150 NodeId getN2Id() const { return NIds[1]; }
151
152 MatrixPtr Costs;
154
155 private:
156 NodeId NIds[2];
157 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
158 };
159
160 // ----- MEMBERS -----
161
162 GraphMetadata Metadata;
163 CostAllocator CostAlloc;
164 SolverT *Solver = nullptr;
165
166 using NodeVector = std::vector<NodeEntry>;
167 using FreeNodeVector = std::vector<NodeId>;
168 NodeVector Nodes;
169 FreeNodeVector FreeNodeIds;
170
171 using EdgeVector = std::vector<EdgeEntry>;
172 using FreeEdgeVector = std::vector<EdgeId>;
173 EdgeVector Edges;
174 FreeEdgeVector FreeEdgeIds;
175
176 Graph(const Graph &Other) {}
177
178 // ----- INTERNAL METHODS -----
179
180 NodeEntry &getNode(NodeId NId) {
181 assert(NId < Nodes.size() && "Out of bound NodeId");
182 return Nodes[NId];
183 }
184 const NodeEntry &getNode(NodeId NId) const {
185 assert(NId < Nodes.size() && "Out of bound NodeId");
186 return Nodes[NId];
187 }
188
189 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
190 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
191
192 NodeId addConstructedNode(NodeEntry N) {
193 NodeId NId = 0;
194 if (!FreeNodeIds.empty()) {
195 NId = FreeNodeIds.back();
196 FreeNodeIds.pop_back();
197 Nodes[NId] = std::move(N);
198 } else {
199 NId = Nodes.size();
200 Nodes.push_back(std::move(N));
201 }
202 return NId;
203 }
204
205 EdgeId addConstructedEdge(EdgeEntry E) {
206 assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
207 "Attempt to add duplicate edge.");
208 EdgeId EId = 0;
209 if (!FreeEdgeIds.empty()) {
210 EId = FreeEdgeIds.back();
211 FreeEdgeIds.pop_back();
212 Edges[EId] = std::move(E);
213 } else {
214 EId = Edges.size();
215 Edges.push_back(std::move(E));
216 }
217
218 EdgeEntry &NE = getEdge(EId);
219
220 // Add the edge to the adjacency sets of its nodes.
221 NE.connect(*this, EId);
222 return EId;
223 }
224
225 void operator=(const Graph &Other) {}
226
227 public:
228 using AdjEdgeItr = typename NodeEntry::AdjEdgeItr;
229
230 class NodeItr {
231 public:
232 using iterator_category = std::forward_iterator_tag;
234 using difference_type = int;
235 using pointer = NodeId *;
236 using reference = NodeId &;
237
238 NodeItr(NodeId CurNId, const Graph &G)
239 : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
240 this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
241 }
242
243 bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
244 bool operator!=(const NodeItr &O) const { return !(*this == O); }
245 NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
246 NodeId operator*() const { return CurNId; }
247
248 private:
249 NodeId findNextInUse(NodeId NId) const {
250 while (NId < EndNId && is_contained(FreeNodeIds, NId)) {
251 ++NId;
252 }
253 return NId;
254 }
255
256 NodeId CurNId, EndNId;
257 const FreeNodeVector &FreeNodeIds;
258 };
259
260 class EdgeItr {
261 public:
262 EdgeItr(EdgeId CurEId, const Graph &G)
263 : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
264 this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
265 }
266
267 bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
268 bool operator!=(const EdgeItr &O) const { return !(*this == O); }
269 EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
270 EdgeId operator*() const { return CurEId; }
271
272 private:
273 EdgeId findNextInUse(EdgeId EId) const {
274 while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {
275 ++EId;
276 }
277 return EId;
278 }
279
280 EdgeId CurEId, EndEId;
281 const FreeEdgeVector &FreeEdgeIds;
282 };
283
284 class NodeIdSet {
285 public:
286 NodeIdSet(const Graph &G) : G(G) {}
287
288 NodeItr begin() const { return NodeItr(0, G); }
289 NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
290
291 bool empty() const { return G.Nodes.empty(); }
292
293 typename NodeVector::size_type size() const {
294 return G.Nodes.size() - G.FreeNodeIds.size();
295 }
296
297 private:
298 const Graph& G;
299 };
300
301 class EdgeIdSet {
302 public:
303 EdgeIdSet(const Graph &G) : G(G) {}
304
305 EdgeItr begin() const { return EdgeItr(0, G); }
306 EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
307
308 bool empty() const { return G.Edges.empty(); }
309
310 typename NodeVector::size_type size() const {
311 return G.Edges.size() - G.FreeEdgeIds.size();
312 }
313
314 private:
315 const Graph& G;
316 };
317
319 public:
320 AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {}
321
322 typename NodeEntry::AdjEdgeItr begin() const {
323 return NE.getAdjEdgeIds().begin();
324 }
325
326 typename NodeEntry::AdjEdgeItr end() const {
327 return NE.getAdjEdgeIds().end();
328 }
329
330 bool empty() const { return NE.getAdjEdgeIds().empty(); }
331
332 typename NodeEntry::AdjEdgeList::size_type size() const {
333 return NE.getAdjEdgeIds().size();
334 }
335
336 private:
337 const NodeEntry &NE;
338 };
339
340 /// Construct an empty PBQP graph.
341 Graph() = default;
342
343 /// Construct an empty PBQP graph with the given graph metadata.
345
346 /// Get a reference to the graph metadata.
348
349 /// Get a const-reference to the graph metadata.
350 const GraphMetadata& getMetadata() const { return Metadata; }
351
352 /// Lock this graph to the given solver instance in preparation
353 /// for running the solver. This method will call solver.handleAddNode for
354 /// each node in the graph, and handleAddEdge for each edge, to give the
355 /// solver an opportunity to set up any requried metadata.
356 void setSolver(SolverT &S) {
357 assert(!Solver && "Solver already set. Call unsetSolver().");
358 Solver = &S;
359 for (auto NId : nodeIds())
360 Solver->handleAddNode(NId);
361 for (auto EId : edgeIds())
362 Solver->handleAddEdge(EId);
363 }
364
365 /// Release from solver instance.
366 void unsetSolver() {
367 assert(Solver && "Solver not set.");
368 Solver = nullptr;
369 }
370
371 /// Add a node with the given costs.
372 /// @param Costs Cost vector for the new node.
373 /// @return Node iterator for the added node.
374 template <typename OtherVectorT>
375 NodeId addNode(OtherVectorT Costs) {
376 // Get cost vector from the problem domain
377 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
378 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
379 if (Solver)
380 Solver->handleAddNode(NId);
381 return NId;
382 }
383
384 /// Add a node bypassing the cost allocator.
385 /// @param Costs Cost vector ptr for the new node (must be convertible to
386 /// VectorPtr).
387 /// @return Node iterator for the added node.
388 ///
389 /// This method allows for fast addition of a node whose costs don't need
390 /// to be passed through the cost allocator. The most common use case for
391 /// this is when duplicating costs from an existing node (when using a
392 /// pooling allocator). These have already been uniqued, so we can avoid
393 /// re-constructing and re-uniquing them by attaching them directly to the
394 /// new node.
395 template <typename OtherVectorPtrT>
396 NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
397 NodeId NId = addConstructedNode(NodeEntry(Costs));
398 if (Solver)
399 Solver->handleAddNode(NId);
400 return NId;
401 }
402
403 /// Add an edge between the given nodes with the given costs.
404 /// @param N1Id First node.
405 /// @param N2Id Second node.
406 /// @param Costs Cost matrix for new edge.
407 /// @return Edge iterator for the added edge.
408 template <typename OtherVectorT>
409 EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
410 assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
411 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
412 "Matrix dimensions mismatch.");
413 // Get cost matrix from the problem domain.
414 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
415 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
416 if (Solver)
417 Solver->handleAddEdge(EId);
418 return EId;
419 }
420
421 /// Add an edge bypassing the cost allocator.
422 /// @param N1Id First node.
423 /// @param N2Id Second node.
424 /// @param Costs Cost matrix for new edge.
425 /// @return Edge iterator for the added edge.
426 ///
427 /// This method allows for fast addition of an edge whose costs don't need
428 /// to be passed through the cost allocator. The most common use case for
429 /// this is when duplicating costs from an existing edge (when using a
430 /// pooling allocator). These have already been uniqued, so we can avoid
431 /// re-constructing and re-uniquing them by attaching them directly to the
432 /// new edge.
433 template <typename OtherMatrixPtrT>
435 OtherMatrixPtrT Costs) {
436 assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
437 getNodeCosts(N2Id).getLength() == Costs->getCols() &&
438 "Matrix dimensions mismatch.");
439 // Get cost matrix from the problem domain.
440 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
441 if (Solver)
442 Solver->handleAddEdge(EId);
443 return EId;
444 }
445
446 /// Returns true if the graph is empty.
447 bool empty() const { return NodeIdSet(*this).empty(); }
448
449 NodeIdSet nodeIds() const { return NodeIdSet(*this); }
450 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
451
452 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
453
454 /// Get the number of nodes in the graph.
455 /// @return Number of nodes in the graph.
456 unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
457
458 /// Get the number of edges in the graph.
459 /// @return Number of edges in the graph.
460 unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
461
462 /// Set a node's cost vector.
463 /// @param NId Node to update.
464 /// @param Costs New costs to set.
465 template <typename OtherVectorT>
466 void setNodeCosts(NodeId NId, OtherVectorT Costs) {
467 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
468 if (Solver)
469 Solver->handleSetNodeCosts(NId, *AllocatedCosts);
470 getNode(NId).Costs = AllocatedCosts;
471 }
472
473 /// Get a VectorPtr to a node's cost vector. Rarely useful - use
474 /// getNodeCosts where possible.
475 /// @param NId Node id.
476 /// @return VectorPtr to node cost vector.
477 ///
478 /// This method is primarily useful for duplicating costs quickly by
479 /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
480 /// getNodeCosts when dealing with node cost values.
481 const VectorPtr& getNodeCostsPtr(NodeId NId) const {
482 return getNode(NId).Costs;
483 }
484
485 /// Get a node's cost vector.
486 /// @param NId Node id.
487 /// @return Node cost vector.
488 const Vector& getNodeCosts(NodeId NId) const {
489 return *getNodeCostsPtr(NId);
490 }
491
493 return getNode(NId).Metadata;
494 }
495
497 return getNode(NId).Metadata;
498 }
499
500 typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
501 return getNode(NId).getAdjEdgeIds().size();
502 }
503
504 /// Update an edge's cost matrix.
505 /// @param EId Edge id.
506 /// @param Costs New cost matrix.
507 template <typename OtherMatrixT>
508 void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
509 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
510 if (Solver)
511 Solver->handleUpdateCosts(EId, *AllocatedCosts);
512 getEdge(EId).Costs = AllocatedCosts;
513 }
514
515 /// Get a MatrixPtr to a node's cost matrix. Rarely useful - use
516 /// getEdgeCosts where possible.
517 /// @param EId Edge id.
518 /// @return MatrixPtr to edge cost matrix.
519 ///
520 /// This method is primarily useful for duplicating costs quickly by
521 /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
522 /// getEdgeCosts when dealing with edge cost values.
523 const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
524 return getEdge(EId).Costs;
525 }
526
527 /// Get an edge's cost matrix.
528 /// @param EId Edge id.
529 /// @return Edge cost matrix.
530 const Matrix& getEdgeCosts(EdgeId EId) const {
531 return *getEdge(EId).Costs;
532 }
533
535 return getEdge(EId).Metadata;
536 }
537
539 return getEdge(EId).Metadata;
540 }
541
542 /// Get the first node connected to this edge.
543 /// @param EId Edge id.
544 /// @return The first node connected to the given edge.
546 return getEdge(EId).getN1Id();
547 }
548
549 /// Get the second node connected to this edge.
550 /// @param EId Edge id.
551 /// @return The second node connected to the given edge.
553 return getEdge(EId).getN2Id();
554 }
555
556 /// Get the "other" node connected to this edge.
557 /// @param EId Edge id.
558 /// @param NId Node id for the "given" node.
559 /// @return The iterator for the "other" node connected to this edge.
561 EdgeEntry &E = getEdge(EId);
562 if (E.getN1Id() == NId) {
563 return E.getN2Id();
564 } // else
565 return E.getN1Id();
566 }
567
568 /// Get the edge connecting two nodes.
569 /// @param N1Id First node id.
570 /// @param N2Id Second node id.
571 /// @return An id for edge (N1Id, N2Id) if such an edge exists,
572 /// otherwise returns an invalid edge id.
574 for (auto AEId : adjEdgeIds(N1Id)) {
575 if ((getEdgeNode1Id(AEId) == N2Id) ||
576 (getEdgeNode2Id(AEId) == N2Id)) {
577 return AEId;
578 }
579 }
580 return invalidEdgeId();
581 }
582
583 /// Remove a node from the graph.
584 /// @param NId Node id.
585 void removeNode(NodeId NId) {
586 if (Solver)
587 Solver->handleRemoveNode(NId);
588 NodeEntry &N = getNode(NId);
589 // TODO: Can this be for-each'd?
590 for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
591 AEEnd = N.adjEdgesEnd();
592 AEItr != AEEnd;) {
593 EdgeId EId = *AEItr;
594 ++AEItr;
595 removeEdge(EId);
596 }
597 FreeNodeIds.push_back(NId);
598 }
599
600 /// Disconnect an edge from the given node.
601 ///
602 /// Removes the given edge from the adjacency list of the given node.
603 /// This operation leaves the edge in an 'asymmetric' state: It will no
604 /// longer appear in an iteration over the given node's (NId's) edges, but
605 /// will appear in an iteration over the 'other', unnamed node's edges.
606 ///
607 /// This does not correspond to any normal graph operation, but exists to
608 /// support efficient PBQP graph-reduction based solvers. It is used to
609 /// 'effectively' remove the unnamed node from the graph while the solver
610 /// is performing the reduction. The solver will later call reconnectNode
611 /// to restore the edge in the named node's adjacency list.
612 ///
613 /// Since the degree of a node is the number of connected edges,
614 /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
615 /// drop by 1.
616 ///
617 /// A disconnected edge WILL still appear in an iteration over the graph
618 /// edges.
619 ///
620 /// A disconnected edge should not be removed from the graph, it should be
621 /// reconnected first.
622 ///
623 /// A disconnected edge can be reconnected by calling the reconnectEdge
624 /// method.
625 void disconnectEdge(EdgeId EId, NodeId NId) {
626 if (Solver)
627 Solver->handleDisconnectEdge(EId, NId);
628
629 EdgeEntry &E = getEdge(EId);
630 E.disconnectFrom(*this, NId);
631 }
632
633 /// Convenience method to disconnect all neighbours from the given
634 /// node.
636 for (auto AEId : adjEdgeIds(NId))
637 disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
638 }
639
640 /// Re-attach an edge to its nodes.
641 ///
642 /// Adds an edge that had been previously disconnected back into the
643 /// adjacency set of the nodes that the edge connects.
644 void reconnectEdge(EdgeId EId, NodeId NId) {
645 EdgeEntry &E = getEdge(EId);
646 E.connectTo(*this, EId, NId);
647 if (Solver)
648 Solver->handleReconnectEdge(EId, NId);
649 }
650
651 /// Remove an edge from the graph.
652 /// @param EId Edge id.
653 void removeEdge(EdgeId EId) {
654 if (Solver)
655 Solver->handleRemoveEdge(EId);
656 EdgeEntry &E = getEdge(EId);
657 E.disconnect();
658 FreeEdgeIds.push_back(EId);
659 Edges[EId].invalidate();
660 }
661
662 /// Remove all nodes and edges from the graph.
663 void clear() {
664 Nodes.clear();
665 FreeNodeIds.clear();
666 Edges.clear();
667 FreeEdgeIds.clear();
668 }
669 };
670
671} // end namespace PBQP
672} // end namespace llvm
673
674#endif // LLVM_CODEGEN_PBQP_GRAPH_H
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
#define G(x, y, z)
Definition: MD5.cpp:56
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
Root of the metadata hierarchy.
Definition: Metadata.h:62
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
Definition: Graph.h:32
unsigned EdgeId
Definition: Graph.h:29
unsigned NodeId
Definition: Graph.h:28
static EdgeId invalidEdgeId()
Returns a value representing an invalid (non-existent) edge.
Definition: Graph.h:37
NodeEntry::AdjEdgeItr begin() const
Definition: Graph.h:322
AdjEdgeIdSet(const NodeEntry &NE)
Definition: Graph.h:320
NodeEntry::AdjEdgeItr end() const
Definition: Graph.h:326
NodeEntry::AdjEdgeList::size_type size() const
Definition: Graph.h:332
EdgeItr begin() const
Definition: Graph.h:305
EdgeIdSet(const Graph &G)
Definition: Graph.h:303
NodeVector::size_type size() const
Definition: Graph.h:310
EdgeItr end() const
Definition: Graph.h:306
EdgeItr(EdgeId CurEId, const Graph &G)
Definition: Graph.h:262
EdgeId operator*() const
Definition: Graph.h:270
bool operator==(const EdgeItr &O) const
Definition: Graph.h:267
EdgeItr & operator++()
Definition: Graph.h:269
bool operator!=(const EdgeItr &O) const
Definition: Graph.h:268
NodeIdSet(const Graph &G)
Definition: Graph.h:286
NodeVector::size_type size() const
Definition: Graph.h:293
NodeItr begin() const
Definition: Graph.h:288
NodeItr end() const
Definition: Graph.h:289
bool operator!=(const NodeItr &O) const
Definition: Graph.h:244
std::forward_iterator_tag iterator_category
Definition: Graph.h:232
bool operator==(const NodeItr &O) const
Definition: Graph.h:243
NodeItr(NodeId CurNId, const Graph &G)
Definition: Graph.h:238
NodeItr & operator++()
Definition: Graph.h:245
NodeId operator*() const
Definition: Graph.h:246
PBQP Graph class.
Definition: Graph.h:46
void unsetSolver()
Release from solver instance.
Definition: Graph.h:366
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
Definition: Graph.h:500
NodeMetadata & getNodeMetadata(NodeId NId)
Definition: Graph.h:492
void disconnectEdge(EdgeId EId, NodeId NId)
Disconnect an edge from the given node.
Definition: Graph.h:625
void setNodeCosts(NodeId NId, OtherVectorT Costs)
Set a node's cost vector.
Definition: Graph.h:466
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
Add an edge between the given nodes with the given costs.
Definition: Graph.h:409
typename SolverT::GraphMetadata GraphMetadata
Definition: Graph.h:59
const GraphMetadata & getMetadata() const
Get a const-reference to the graph metadata.
Definition: Graph.h:350
typename SolverT::EdgeMetadata EdgeMetadata
Definition: Graph.h:58
void removeNode(NodeId NId)
Remove a node from the graph.
Definition: Graph.h:585
NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId)
Get the "other" node connected to this edge.
Definition: Graph.h:560
AdjEdgeIdSet adjEdgeIds(NodeId NId)
Definition: Graph.h:452
Graph()=default
Construct an empty PBQP graph.
typename SolverT::Matrix Matrix
Definition: Graph.h:54
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
Definition: Graph.h:552
unsigned getNumNodes() const
Get the number of nodes in the graph.
Definition: Graph.h:456
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
Definition: Graph.h:545
EdgeMetadata & getEdgeMetadata(EdgeId EId)
Definition: Graph.h:534
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge's cost matrix.
Definition: Graph.h:530
typename SolverT::Vector Vector
Definition: Graph.h:53
NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs)
Add a node bypassing the cost allocator.
Definition: Graph.h:396
NodeIdSet nodeIds() const
Definition: Graph.h:449
bool empty() const
Returns true if the graph is empty.
Definition: Graph.h:447
void setSolver(SolverT &S)
Lock this graph to the given solver instance in preparation for running the solver.
Definition: Graph.h:356
void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs)
Update an edge's cost matrix.
Definition: Graph.h:508
typename SolverT::NodeMetadata NodeMetadata
Definition: Graph.h:57
typename CostAllocator::MatrixPtr MatrixPtr
Definition: Graph.h:56
const MatrixPtr & getEdgeCostsPtr(EdgeId EId) const
Get a MatrixPtr to a node's cost matrix.
Definition: Graph.h:523
typename SolverT::RawMatrix RawMatrix
Definition: Graph.h:52
void clear()
Remove all nodes and edges from the graph.
Definition: Graph.h:663
typename SolverT::RawVector RawVector
Definition: Graph.h:51
const NodeMetadata & getNodeMetadata(NodeId NId) const
Definition: Graph.h:496
typename NodeEntry::AdjEdgeItr AdjEdgeItr
Definition: Graph.h:228
Graph(GraphMetadata Metadata)
Construct an empty PBQP graph with the given graph metadata.
Definition: Graph.h:344
void disconnectAllNeighborsFromNode(NodeId NId)
Convenience method to disconnect all neighbours from the given node.
Definition: Graph.h:635
void reconnectEdge(EdgeId EId, NodeId NId)
Re-attach an edge to its nodes.
Definition: Graph.h:644
const EdgeMetadata & getEdgeMetadata(EdgeId EId) const
Definition: Graph.h:538
void removeEdge(EdgeId EId)
Remove an edge from the graph.
Definition: Graph.h:653
const Vector & getNodeCosts(NodeId NId) const
Get a node's cost vector.
Definition: Graph.h:488
NodeId addNode(OtherVectorT Costs)
Add a node with the given costs.
Definition: Graph.h:375
GraphMetadata & getMetadata()
Get a reference to the graph metadata.
Definition: Graph.h:347
unsigned getNumEdges() const
Get the number of edges in the graph.
Definition: Graph.h:460
typename CostAllocator::VectorPtr VectorPtr
Definition: Graph.h:55
const VectorPtr & getNodeCostsPtr(NodeId NId) const
Get a VectorPtr to a node's cost vector.
Definition: Graph.h:481
EdgeId findEdge(NodeId N1Id, NodeId N2Id)
Get the edge connecting two nodes.
Definition: Graph.h:573
EdgeIdSet edgeIds() const
Definition: Graph.h:450
NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
Add an edge bypassing the cost allocator.
Definition: Graph.h:434
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
Definition: STLExtras.h:1689
@ Other
Any other memory.
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:1858
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N