LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - RegAllocPBQP.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 186 189 98.4 %
Date: 2017-09-14 15:23:50 Functions: 28 31 90.3 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13