LLVM  9.0.0svn
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 
23 namespace llvm {
24 namespace PBQP {
25 
26  class GraphBase {
27  public:
28  using NodeId = unsigned;
29  using EdgeId = unsigned;
30 
31  /// Returns a value representing an invalid (non-existent) node.
32  static NodeId invalidNodeId() {
34  }
35 
36  /// Returns a value representing an invalid (non-existent) edge.
37  static EdgeId invalidEdgeId() {
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() {
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 
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 
318  class AdjEdgeIdSet {
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.
344  Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {}
345 
346  /// Get a reference to the graph metadata.
347  GraphMetadata& getMetadata() { return 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 
496  const NodeMetadata& getNodeMetadata(NodeId NId) const {
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 
538  const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
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.
573  EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
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_HPP
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
EdgeIdSet(const Graph &G)
Definition: Graph.h:303
NodeVector::size_type size() const
Definition: Graph.h:293
This class represents lattice values for constants.
Definition: AllocatorList.h:23
NodeEntry::AdjEdgeItr begin() const
Definition: Graph.h:322
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
Add an edge between the given nodes with the given costs.
Definition: Graph.h:409
bool empty() const
Returns true if the graph is empty.
Definition: Graph.h:447
typename RegAllocSolverImpl ::EdgeMetadata EdgeMetadata
Definition: Graph.h:58
EdgeId findEdge(NodeId N1Id, NodeId N2Id)
Get the edge connecting two nodes.
Definition: Graph.h:573
NodeVector::size_type size() const
Definition: Graph.h:310
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
Definition: Graph.h:32
bool operator==(const NodeItr &O) const
Definition: Graph.h:243
typename CostAllocator::VectorPtr VectorPtr
Definition: Graph.h:55
NodeItr(NodeId CurNId, const Graph &G)
Definition: Graph.h:238
bool operator!=(const NodeItr &O) const
Definition: Graph.h:244
void reconnectEdge(EdgeId EId, NodeId NId)
Re-attach an edge to its nodes.
Definition: Graph.h:644
void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs)
Update an edge&#39;s cost matrix.
Definition: Graph.h:508
NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
Add an edge bypassing the cost allocator.
Definition: Graph.h:434
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
Definition: Graph.h:545
EdgeIdSet edgeIds() const
Definition: Graph.h:450
NodeItr end() const
Definition: Graph.h:289
Live Register Matrix
NodeMetadata & getNodeMetadata(NodeId NId)
Definition: Graph.h:492
Definition: BitVector.h:937
void disconnectEdge(EdgeId EId, NodeId NId)
Disconnect an edge from the given node.
Definition: Graph.h:625
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
Definition: Graph.h:59
const EdgeMetadata & getEdgeMetadata(EdgeId EId) const
Definition: Graph.h:538
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:870
NodeIdSet nodeIds() const
Definition: Graph.h:449
NodeEntry::AdjEdgeList::size_type size() const
Definition: Graph.h:332
NodeEntry::AdjEdgeItr end() const
Definition: Graph.h:326
unsigned getNumNodes() const
Get the number of nodes in the graph.
Definition: Graph.h:456
NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId)
Get the "other" node connected to this edge.
Definition: Graph.h:560
typename RegAllocSolverImpl ::Matrix Matrix
Definition: Graph.h:54
NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs)
Add a node bypassing the cost allocator.
Definition: Graph.h:396
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge&#39;s cost matrix.
Definition: Graph.h:530
void removeNode(NodeId NId)
Remove a node from the graph.
Definition: Graph.h:585
AdjEdgeIdSet adjEdgeIds(NodeId NId)
Definition: Graph.h:452
unsigned NodeId
Definition: Graph.h:28
const MatrixPtr & getEdgeCostsPtr(EdgeId EId) const
Get a MatrixPtr to a node&#39;s cost matrix.
Definition: Graph.h:523
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
Definition: Graph.h:552
unsigned getNumEdges() const
Get the number of edges in the graph.
Definition: Graph.h:460
typename NodeEntry::AdjEdgeItr AdjEdgeItr
Definition: Graph.h:228
const Vector & getNodeCosts(NodeId NId) const
Get a node&#39;s cost vector.
Definition: Graph.h:488
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
NodeId operator*() const
Definition: Graph.h:246
NodeItr begin() const
Definition: Graph.h:288
void setSolver(SolverT &S)
Lock this graph to the given solver instance in preparation for running the solver.
Definition: Graph.h:356
NodeItr & operator++()
Definition: Graph.h:245
EdgeItr begin() const
Definition: Graph.h:305
PBQP Graph class.
Definition: Graph.h:46
void clear()
Remove all nodes and edges from the graph.
Definition: Graph.h:663
bool operator==(const EdgeItr &O) const
Definition: Graph.h:267
EdgeItr(EdgeId CurEId, const Graph &G)
Definition: Graph.h:262
GraphMetadata & getMetadata()
Get a reference to the graph metadata.
Definition: Graph.h:347
void removeEdge(EdgeId EId)
Remove an edge from the graph.
Definition: Graph.h:653
AdjEdgeIdSet(const NodeEntry &NE)
Definition: Graph.h:320
void unsetSolver()
Release from solver instance.
Definition: Graph.h:366
EdgeId operator*() const
Definition: Graph.h:270
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1173
const NodeMetadata & getNodeMetadata(NodeId NId) const
Definition: Graph.h:496
const VectorPtr & getNodeCostsPtr(NodeId NId) const
Get a VectorPtr to a node&#39;s cost vector.
Definition: Graph.h:481
Graph(GraphMetadata Metadata)
Construct an empty PBQP graph with the given graph metadata.
Definition: Graph.h:344
const GraphMetadata & getMetadata() const
Get a const-reference to the graph metadata.
Definition: Graph.h:350
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
Definition: Graph.h:500
EdgeItr & operator++()
Definition: Graph.h:269
bool operator!=(const EdgeItr &O) const
Definition: Graph.h:268
typename RegAllocSolverImpl ::RawVector RawVector
Definition: Graph.h:51
static EdgeId invalidEdgeId()
Returns a value representing an invalid (non-existent) edge.
Definition: Graph.h:37
EdgeItr end() const
Definition: Graph.h:306
void disconnectAllNeighborsFromNode(NodeId NId)
Convenience method to disconnect all neighbours from the given node.
Definition: Graph.h:635
#define N
typename RegAllocSolverImpl ::Vector Vector
Definition: Graph.h:53
EdgeMetadata & getEdgeMetadata(EdgeId EId)
Definition: Graph.h:534
typename CostAllocator::MatrixPtr MatrixPtr
Definition: Graph.h:56
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
typename RegAllocSolverImpl ::NodeMetadata NodeMetadata
Definition: Graph.h:57
NodeIdSet(const Graph &G)
Definition: Graph.h:286
std::forward_iterator_tag iterator_category
Definition: Graph.h:232
typename RegAllocSolverImpl ::RawMatrix RawMatrix
Definition: Graph.h:52
NodeId addNode(OtherVectorT Costs)
Add a node with the given costs.
Definition: Graph.h:375
Root of the metadata hierarchy.
Definition: Metadata.h:57
void setNodeCosts(NodeId NId, OtherVectorT Costs)
Set a node&#39;s cost vector.
Definition: Graph.h:466
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1251