contrib/llvm/include/llvm/CodeGen/RegAllocPBQP.h

   1 //===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the PBQPBuilder interface, for classes which build PBQP
  11 // instances to represent register allocation problems, and the RegAllocPBQP
  12 // interface.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CODEGEN_REGALLOCPBQP_H
  17 #define LLVM_CODEGEN_REGALLOCPBQP_H
  18
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/PBQP/CostAllocator.h"
  21 #include "llvm/CodeGen/PBQP/ReductionRules.h"
  22 #include "llvm/CodeGen/PBQPRAConstraint.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include <set>
  25
  26 namespace llvm {
  27
  28 class raw_ostream;
  29
  30 namespace PBQP {
  31 namespace RegAlloc {
  32
  33 /// @brief Spill option index.
  34 inline unsigned getSpillOptionIdx() { return 0; }
  35
  36 /// \brief Metadata to speed allocatability test.
  37 ///
  38 /// Keeps track of the number of infinities in each row and column.
  39 class MatrixMetadata {
  40 private:
  41   MatrixMetadata(const MatrixMetadata&);
  42   void operator=(const MatrixMetadata&);
  43 public:
  44   MatrixMetadata(const Matrix& M)
  45     : WorstRow(0), WorstCol(0),
  46       UnsafeRows(new bool[M.getRows() - 1]()),
  47       UnsafeCols(new bool[M.getCols() - 1]()) {
  48
  49     unsigned* ColCounts = new unsigned[M.getCols() - 1]();
  50
  51     for (unsigned i = 1; i < M.getRows(); ++i) {
  52       unsigned RowCount = 0;
  53       for (unsigned j = 1; j < M.getCols(); ++j) {
  54         if (M[i][j] == std::numeric_limits<PBQPNum>::infinity()) {
  55           ++RowCount;
  56           ++ColCounts[j - 1];
  57           UnsafeRows[i - 1] = true;
  58           UnsafeCols[j - 1] = true;
  59         }
  60       }
  61       WorstRow = std::max(WorstRow, RowCount);
  62     }
  63     unsigned WorstColCountForCurRow =
  64       *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
  65     WorstCol = std::max(WorstCol, WorstColCountForCurRow);
  66     delete[] ColCounts;
  67   }
  68
  69   unsigned getWorstRow() const { return WorstRow; }
  70   unsigned getWorstCol() const { return WorstCol; }
  71   const bool* getUnsafeRows() const { return UnsafeRows.get(); }
  72   const bool* getUnsafeCols() const { return UnsafeCols.get(); }
  73
  74 private:
  75   unsigned WorstRow, WorstCol;
  76   std::unique_ptr<bool[]> UnsafeRows;
  77   std::unique_ptr<bool[]> UnsafeCols;
  78 };
  79
  80 /// \brief Holds a vector of the allowed physical regs for a vreg.
  81 class AllowedRegVector {
  82   friend hash_code hash_value(const AllowedRegVector &);
  83 public:
  84
  85   AllowedRegVector() : NumOpts(0), Opts(nullptr) {}
  86
  87   AllowedRegVector(const std::vector<unsigned> &OptVec)
  88     : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
  89     std::copy(OptVec.begin(), OptVec.end(), Opts.get());
  90   }
  91
  92   AllowedRegVector(const AllowedRegVector &Other)
  93     : NumOpts(Other.NumOpts), Opts(new unsigned[NumOpts]) {
  94     std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
  95   }
  96
  97   AllowedRegVector(AllowedRegVector &&Other)
  98     : NumOpts(std::move(Other.NumOpts)), Opts(std::move(Other.Opts)) {}
  99
 100   AllowedRegVector& operator=(const AllowedRegVector &Other) {
 101     NumOpts = Other.NumOpts;
 102     Opts.reset(new unsigned[NumOpts]);
 103     std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
 104     return *this;
 105   }
 106
 107   AllowedRegVector& operator=(AllowedRegVector &&Other) {
 108     NumOpts = std::move(Other.NumOpts);
 109     Opts = std::move(Other.Opts);
 110     return *this;
 111   }
 112
 113   unsigned size() const { return NumOpts; }
 114   unsigned operator[](size_t I) const { return Opts[I]; }
 115
 116   bool operator==(const AllowedRegVector &Other) const {
 117     if (NumOpts != Other.NumOpts)
 118       return false;
 119     return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
 120   }
 121
 122   bool operator!=(const AllowedRegVector &Other) const {
 123     return !(*this == Other);
 124   }
 125
 126 private:
 127   unsigned NumOpts;
 128   std::unique_ptr<unsigned[]> Opts;
 129 };
 130
 131 inline hash_code hash_value(const AllowedRegVector &OptRegs) {
 132   unsigned *OStart = OptRegs.Opts.get();
 133   unsigned *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
 134   return hash_combine(OptRegs.NumOpts,
 135                       hash_combine_range(OStart, OEnd));
 136 }
 137
 138 /// \brief Holds graph-level metadata relevant to PBQP RA problems.
 139 class GraphMetadata {
 140 private:
 141   typedef ValuePool<AllowedRegVector> AllowedRegVecPool;
 142 public:
 143
 144   typedef AllowedRegVecPool::PoolRef AllowedRegVecRef;
 145
 146   GraphMetadata(MachineFunction &MF,
 147                 LiveIntervals &LIS,
 148                 MachineBlockFrequencyInfo &MBFI)
 149     : MF(MF), LIS(LIS), MBFI(MBFI) {}
 150
 151   MachineFunction &MF;
 152   LiveIntervals &LIS;
 153   MachineBlockFrequencyInfo &MBFI;
 154
 155   void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
 156     VRegToNodeId[VReg] = NId;
 157   }
 158
 159   GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
 160     auto VRegItr = VRegToNodeId.find(VReg);
 161     if (VRegItr == VRegToNodeId.end())
 162       return GraphBase::invalidNodeId();
 163     return VRegItr->second;
 164   }
 165
 166   void eraseNodeIdForVReg(unsigned VReg) {
 167     VRegToNodeId.erase(VReg);
 168   }
 169
 170   AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
 171     return AllowedRegVecs.getValue(std::move(Allowed));
 172   }
 173
 174 private:
 175   DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
 176   AllowedRegVecPool AllowedRegVecs;
 177 };
 178
 179 /// \brief Holds solver state and other metadata relevant to each PBQP RA node.
 180 class NodeMetadata {
 181 public:
 182   typedef RegAlloc::AllowedRegVector AllowedRegVector;
 183
 184   // The node's reduction state. The order in this enum is important,
 185   // as it is assumed nodes can only progress up (i.e. towards being
 186   // optimally reducible) when reducing the graph.
 187   typedef enum {
 188     Unprocessed,
 189     NotProvablyAllocatable,
 190     ConservativelyAllocatable,
 191     OptimallyReducible
 192   } ReductionState;
 193
 194   NodeMetadata()
 195     : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr),
 196       VReg(0)
 197 #ifndef NDEBUG
 198       , everConservativelyAllocatable(false)
 199 #endif
 200       {}
 201
 202   // FIXME: Re-implementing default behavior to work around MSVC. Remove once
 203   // MSVC synthesizes move constructors properly.
 204   NodeMetadata(const NodeMetadata &Other)
 205     : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
 206       OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
 207       AllowedRegs(Other.AllowedRegs)
 208 #ifndef NDEBUG
 209       , everConservativelyAllocatable(Other.everConservativelyAllocatable)
 210 #endif
 211   {
 212     if (NumOpts > 0) {
 213       std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
 214                 &OptUnsafeEdges[0]);
 215     }
 216   }
 217
 218   // FIXME: Re-implementing default behavior to work around MSVC. Remove once
 219   // MSVC synthesizes move constructors properly.
 220   NodeMetadata(NodeMetadata &&Other)
 221     : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
 222       OptUnsafeEdges(std::move(Other.OptUnsafeEdges)), VReg(Other.VReg),
 223       AllowedRegs(std::move(Other.AllowedRegs))
 224 #ifndef NDEBUG
 225       , everConservativelyAllocatable(Other.everConservativelyAllocatable)
 226 #endif
 227   {}
 228
 229   // FIXME: Re-implementing default behavior to work around MSVC. Remove once
 230   // MSVC synthesizes move constructors properly.
 231   NodeMetadata& operator=(const NodeMetadata &Other) {
 232     RS = Other.RS;
 233     NumOpts = Other.NumOpts;
 234     DeniedOpts = Other.DeniedOpts;
 235     OptUnsafeEdges.reset(new unsigned[NumOpts]);
 236     std::copy(Other.OptUnsafeEdges.get(), Other.OptUnsafeEdges.get() + NumOpts,
 237               OptUnsafeEdges.get());
 238     VReg = Other.VReg;
 239     AllowedRegs = Other.AllowedRegs;
 240 #ifndef NDEBUG
 241     everConservativelyAllocatable = Other.everConservativelyAllocatable;
 242 #endif
 243     return *this;
 244   }
 245
 246   // FIXME: Re-implementing default behavior to work around MSVC. Remove once
 247   // MSVC synthesizes move constructors properly.
 248   NodeMetadata& operator=(NodeMetadata &&Other) {
 249     RS = Other.RS;
 250     NumOpts = Other.NumOpts;
 251     DeniedOpts = Other.DeniedOpts;
 252     OptUnsafeEdges = std::move(Other.OptUnsafeEdges);
 253     VReg = Other.VReg;
 254     AllowedRegs = std::move(Other.AllowedRegs);
 255 #ifndef NDEBUG
 256     everConservativelyAllocatable = Other.everConservativelyAllocatable;
 257 #endif
 258     return *this;
 259   }
 260
 261   void setVReg(unsigned VReg) { this->VReg = VReg; }
 262   unsigned getVReg() const { return VReg; }
 263
 264   void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
 265     this->AllowedRegs = std::move(AllowedRegs);
 266   }
 267   const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
 268
 269   void setup(const Vector& Costs) {
 270     NumOpts = Costs.getLength() - 1;
 271     OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
 272   }
 273
 274   ReductionState getReductionState() const { return RS; }
 275   void setReductionState(ReductionState RS) {
 276     assert(RS >= this->RS && "A node's reduction state can not be downgraded");
 277     this->RS = RS;
 278
 279 #ifndef NDEBUG
 280     // Remember this state to assert later that a non-infinite register
 281     // option was available.
 282     if (RS == ConservativelyAllocatable)
 283       everConservativelyAllocatable = true;
 284 #endif
 285   }
 286
 287
 288   void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
 289     DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
 290     const bool* UnsafeOpts =
 291       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
 292     for (unsigned i = 0; i < NumOpts; ++i)
 293       OptUnsafeEdges[i] += UnsafeOpts[i];
 294   }
 295
 296   void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
 297     DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
 298     const bool* UnsafeOpts =
 299       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
 300     for (unsigned i = 0; i < NumOpts; ++i)
 301       OptUnsafeEdges[i] -= UnsafeOpts[i];
 302   }
 303
 304   bool isConservativelyAllocatable() const {
 305     return (DeniedOpts < NumOpts) ||
 306       (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
 307        &OptUnsafeEdges[NumOpts]);
 308   }
 309
 310 #ifndef NDEBUG
 311   bool wasConservativelyAllocatable() const {
 312     return everConservativelyAllocatable;
 313   }
 314 #endif
 315
 316 private:
 317   ReductionState RS;
 318   unsigned NumOpts;
 319   unsigned DeniedOpts;
 320   std::unique_ptr<unsigned[]> OptUnsafeEdges;
 321   unsigned VReg;
 322   GraphMetadata::AllowedRegVecRef AllowedRegs;
 323
 324 #ifndef NDEBUG
 325   bool everConservativelyAllocatable;
 326 #endif
 327 };
 328
 329 class RegAllocSolverImpl {
 330 private:
 331   typedef MDMatrix<MatrixMetadata> RAMatrix;
 332 public:
 333   typedef PBQP::Vector RawVector;
 334   typedef PBQP::Matrix RawMatrix;
 335   typedef PBQP::Vector Vector;
 336   typedef RAMatrix     Matrix;
 337   typedef PBQP::PoolCostAllocator<Vector, Matrix> CostAllocator;
 338
 339   typedef GraphBase::NodeId NodeId;
 340   typedef GraphBase::EdgeId EdgeId;
 341
 342   typedef RegAlloc::NodeMetadata NodeMetadata;
 343   struct EdgeMetadata { };
 344   typedef RegAlloc::GraphMetadata GraphMetadata;
 345
 346   typedef PBQP::Graph<RegAllocSolverImpl> Graph;
 347
 348   RegAllocSolverImpl(Graph &G) : G(G) {}
 349
 350   Solution solve() {
 351     G.setSolver(*this);
 352     Solution S;
 353     setup();
 354     S = backpropagate(G, reduce());
 355     G.unsetSolver();
 356     return S;
 357   }
 358
 359   void handleAddNode(NodeId NId) {
 360     assert(G.getNodeCosts(NId).getLength() > 1 &&
 361            "PBQP Graph should not contain single or zero-option nodes");
 362     G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
 363   }
 364   void handleRemoveNode(NodeId NId) {}
 365   void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
 366
 367   void handleAddEdge(EdgeId EId) {
 368     handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
 369     handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
 370   }
 371
 372   void handleRemoveEdge(EdgeId EId) {
 373     handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
 374     handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
 375   }
 376
 377   void handleDisconnectEdge(EdgeId EId, NodeId NId) {
 378     NodeMetadata& NMd = G.getNodeMetadata(NId);
 379     const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
 380     NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
 381     promote(NId, NMd);
 382   }
 383
 384   void handleReconnectEdge(EdgeId EId, NodeId NId) {
 385     NodeMetadata& NMd = G.getNodeMetadata(NId);
 386     const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
 387     NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
 388   }
 389
 390   void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
 391     NodeId N1Id = G.getEdgeNode1Id(EId);
 392     NodeId N2Id = G.getEdgeNode2Id(EId);
 393     NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
 394     NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
 395     bool Transpose = N1Id != G.getEdgeNode1Id(EId);
 396
 397     // Metadata are computed incrementally. First, update them
 398     // by removing the old cost.
 399     const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
 400     N1Md.handleRemoveEdge(OldMMd, Transpose);
 401     N2Md.handleRemoveEdge(OldMMd, !Transpose);
 402
 403     // And update now the metadata with the new cost.
 404     const MatrixMetadata& MMd = NewCosts.getMetadata();
 405     N1Md.handleAddEdge(MMd, Transpose);
 406     N2Md.handleAddEdge(MMd, !Transpose);
 407
 408     // As the metadata may have changed with the update, the nodes may have
 409     // become ConservativelyAllocatable or OptimallyReducible.
 410     promote(N1Id, N1Md);
 411     promote(N2Id, N2Md);
 412   }
 413
 414 private:
 415
 416   void promote(NodeId NId, NodeMetadata& NMd) {
 417     if (G.getNodeDegree(NId) == 3) {
 418       // This node is becoming optimally reducible.
 419       moveToOptimallyReducibleNodes(NId);
 420     } else if (NMd.getReductionState() ==
 421                NodeMetadata::NotProvablyAllocatable &&
 422                NMd.isConservativelyAllocatable()) {
 423       // This node just became conservatively allocatable.
 424       moveToConservativelyAllocatableNodes(NId);
 425     }
 426   }
 427
 428   void removeFromCurrentSet(NodeId NId) {
 429     switch (G.getNodeMetadata(NId).getReductionState()) {
 430     case NodeMetadata::Unprocessed: break;
 431     case NodeMetadata::OptimallyReducible:
 432       assert(OptimallyReducibleNodes.find(NId) !=
 433              OptimallyReducibleNodes.end() &&
 434              "Node not in optimally reducible set.");
 435       OptimallyReducibleNodes.erase(NId);
 436       break;
 437     case NodeMetadata::ConservativelyAllocatable:
 438       assert(ConservativelyAllocatableNodes.find(NId) !=
 439              ConservativelyAllocatableNodes.end() &&
 440              "Node not in conservatively allocatable set.");
 441       ConservativelyAllocatableNodes.erase(NId);
 442       break;
 443     case NodeMetadata::NotProvablyAllocatable:
 444       assert(NotProvablyAllocatableNodes.find(NId) !=
 445              NotProvablyAllocatableNodes.end() &&
 446              "Node not in not-provably-allocatable set.");
 447       NotProvablyAllocatableNodes.erase(NId);
 448       break;
 449     }
 450   }
 451
 452   void moveToOptimallyReducibleNodes(NodeId NId) {
 453     removeFromCurrentSet(NId);
 454     OptimallyReducibleNodes.insert(NId);
 455     G.getNodeMetadata(NId).setReductionState(
 456       NodeMetadata::OptimallyReducible);
 457   }
 458
 459   void moveToConservativelyAllocatableNodes(NodeId NId) {
 460     removeFromCurrentSet(NId);
 461     ConservativelyAllocatableNodes.insert(NId);
 462     G.getNodeMetadata(NId).setReductionState(
 463       NodeMetadata::ConservativelyAllocatable);
 464   }
 465
 466   void moveToNotProvablyAllocatableNodes(NodeId NId) {
 467     removeFromCurrentSet(NId);
 468     NotProvablyAllocatableNodes.insert(NId);
 469     G.getNodeMetadata(NId).setReductionState(
 470       NodeMetadata::NotProvablyAllocatable);
 471   }
 472
 473   void setup() {
 474     // Set up worklists.
 475     for (auto NId : G.nodeIds()) {
 476       if (G.getNodeDegree(NId) < 3)
 477         moveToOptimallyReducibleNodes(NId);
 478       else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
 479         moveToConservativelyAllocatableNodes(NId);
 480       else
 481         moveToNotProvablyAllocatableNodes(NId);
 482     }
 483   }
 484
 485   // Compute a reduction order for the graph by iteratively applying PBQP
 486   // reduction rules. Locally optimal rules are applied whenever possible (R0,
 487   // R1, R2). If no locally-optimal rules apply then any conservatively
 488   // allocatable node is reduced. Finally, if no conservatively allocatable
 489   // node exists then the node with the lowest spill-cost:degree ratio is
 490   // selected.
 491   std::vector<GraphBase::NodeId> reduce() {
 492     assert(!G.empty() && "Cannot reduce empty graph.");
 493
 494     typedef GraphBase::NodeId NodeId;
 495     std::vector<NodeId> NodeStack;
 496
 497     // Consume worklists.
 498     while (true) {
 499       if (!OptimallyReducibleNodes.empty()) {
 500         NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
 501         NodeId NId = *NItr;
 502         OptimallyReducibleNodes.erase(NItr);
 503         NodeStack.push_back(NId);
 504         switch (G.getNodeDegree(NId)) {
 505         case 0:
 506           break;
 507         case 1:
 508           applyR1(G, NId);
 509           break;
 510         case 2:
 511           applyR2(G, NId);
 512           break;
 513         default: llvm_unreachable("Not an optimally reducible node.");
 514         }
 515       } else if (!ConservativelyAllocatableNodes.empty()) {
 516         // Conservatively allocatable nodes will never spill. For now just
 517         // take the first node in the set and push it on the stack. When we
 518         // start optimizing more heavily for register preferencing, it may
 519         // would be better to push nodes with lower 'expected' or worst-case
 520         // register costs first (since early nodes are the most
 521         // constrained).
 522         NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
 523         NodeId NId = *NItr;
 524         ConservativelyAllocatableNodes.erase(NItr);
 525         NodeStack.push_back(NId);
 526         G.disconnectAllNeighborsFromNode(NId);
 527
 528       } else if (!NotProvablyAllocatableNodes.empty()) {
 529         NodeSet::iterator NItr =
 530           std::min_element(NotProvablyAllocatableNodes.begin(),
 531                            NotProvablyAllocatableNodes.end(),
 532                            SpillCostComparator(G));
 533         NodeId NId = *NItr;
 534         NotProvablyAllocatableNodes.erase(NItr);
 535         NodeStack.push_back(NId);
 536         G.disconnectAllNeighborsFromNode(NId);
 537       } else
 538         break;
 539     }
 540
 541     return NodeStack;
 542   }
 543
 544   class SpillCostComparator {
 545   public:
 546     SpillCostComparator(const Graph& G) : G(G) {}
 547     bool operator()(NodeId N1Id, NodeId N2Id) {
 548       PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
 549       PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
 550       if (N1SC == N2SC)
 551         return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
 552       return N1SC < N2SC;
 553     }
 554   private:
 555     const Graph& G;
 556   };
 557
 558   Graph& G;
 559   typedef std::set<NodeId> NodeSet;
 560   NodeSet OptimallyReducibleNodes;
 561   NodeSet ConservativelyAllocatableNodes;
 562   NodeSet NotProvablyAllocatableNodes;
 563 };
 564
 565 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
 566 private:
 567   typedef PBQP::Graph<RegAllocSolverImpl> BaseT;
 568 public:
 569   PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {}
 570
 571   /// @brief Dump this graph to dbgs().
 572   void dump() const;
 573
 574   /// @brief Dump this graph to an output stream.
 575   /// @param OS Output stream to print on.
 576   void dump(raw_ostream &OS) const;
 577
 578   /// @brief Print a representation of this graph in DOT format.
 579   /// @param OS Output stream to print on.
 580   void printDot(raw_ostream &OS) const;
 581 };
 582
 583 inline Solution solve(PBQPRAGraph& G) {
 584   if (G.empty())
 585     return Solution();
 586   RegAllocSolverImpl RegAllocSolver(G);
 587   return RegAllocSolver.solve();
 588 }
 589
 590 } // namespace RegAlloc
 591 } // namespace PBQP
 592
 593 /// @brief Create a PBQP register allocator instance.
 594 FunctionPass *
 595 createPBQPRegisterAllocator(char *customPassID = nullptr);
 596
 597 } // namespace llvm
 598
 599 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */