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/PBQPRAConstraint.h"
  21 #include "llvm/CodeGen/PBQP/CostAllocator.h"
  22 #include "llvm/CodeGen/PBQP/ReductionRules.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24
  25 namespace llvm {
  26 namespace PBQP {
  27 namespace RegAlloc {
  28
  29 /// @brief Spill option index.
  30 inline unsigned getSpillOptionIdx() { return 0; }
  31
  32 /// \brief Metadata to speed allocatability test.
  33 ///
  34 /// Keeps track of the number of infinities in each row and column.
  35 class MatrixMetadata {
  36 private:
  37   MatrixMetadata(const MatrixMetadata&);
  38   void operator=(const MatrixMetadata&);
  39 public:
  40   MatrixMetadata(const Matrix& M)
  41     : WorstRow(0), WorstCol(0),
  42       UnsafeRows(new bool[M.getRows() - 1]()),
  43       UnsafeCols(new bool[M.getCols() - 1]()) {
  44
  45     unsigned* ColCounts = new unsigned[M.getCols() - 1]();
  46
  47     for (unsigned i = 1; i < M.getRows(); ++i) {
  48       unsigned RowCount = 0;
  49       for (unsigned j = 1; j < M.getCols(); ++j) {
  50         if (M[i][j] == std::numeric_limits<PBQPNum>::infinity()) {
  51           ++RowCount;
  52           ++ColCounts[j - 1];
  53           UnsafeRows[i - 1] = true;
  54           UnsafeCols[j - 1] = true;
  55         }
  56       }
  57       WorstRow = std::max(WorstRow, RowCount);
  58     }
  59     unsigned WorstColCountForCurRow =
  60       *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
  61     WorstCol = std::max(WorstCol, WorstColCountForCurRow);
  62     delete[] ColCounts;
  63   }
  64
  65   ~MatrixMetadata() {
  66     delete[] UnsafeRows;
  67     delete[] UnsafeCols;
  68   }
  69
  70   unsigned getWorstRow() const { return WorstRow; }
  71   unsigned getWorstCol() const { return WorstCol; }
  72   const bool* getUnsafeRows() const { return UnsafeRows; }
  73   const bool* getUnsafeCols() const { return UnsafeCols; }
  74
  75 private:
  76   unsigned WorstRow, WorstCol;
  77   bool* UnsafeRows;
  78   bool* UnsafeCols;
  79 };
  80
  81 class NodeMetadata {
  82 public:
  83   typedef std::vector<unsigned> OptionToRegMap;
  84
  85   typedef enum { Unprocessed,
  86                  OptimallyReducible,
  87                  ConservativelyAllocatable,
  88                  NotProvablyAllocatable } ReductionState;
  89
  90   NodeMetadata() : RS(Unprocessed), DeniedOpts(0), OptUnsafeEdges(nullptr){}
  91   ~NodeMetadata() { delete[] OptUnsafeEdges; }
  92
  93   void setVReg(unsigned VReg) { this->VReg = VReg; }
  94   unsigned getVReg() const { return VReg; }
  95
  96   void setOptionRegs(OptionToRegMap OptionRegs) {
  97     this->OptionRegs = std::move(OptionRegs);
  98   }
  99   const OptionToRegMap& getOptionRegs() const { return OptionRegs; }
 100
 101   void setup(const Vector& Costs) {
 102     NumOpts = Costs.getLength() - 1;
 103     OptUnsafeEdges = new unsigned[NumOpts]();
 104   }
 105
 106   ReductionState getReductionState() const { return RS; }
 107   void setReductionState(ReductionState RS) { this->RS = RS; }
 108
 109   void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
 110     DeniedOpts += Transpose ? MD.getWorstCol() : MD.getWorstRow();
 111     const bool* UnsafeOpts =
 112       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
 113     for (unsigned i = 0; i < NumOpts; ++i)
 114       OptUnsafeEdges[i] += UnsafeOpts[i];
 115   }
 116
 117   void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
 118     DeniedOpts -= Transpose ? MD.getWorstCol() : MD.getWorstRow();
 119     const bool* UnsafeOpts =
 120       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
 121     for (unsigned i = 0; i < NumOpts; ++i)
 122       OptUnsafeEdges[i] -= UnsafeOpts[i];
 123   }
 124
 125   bool isConservativelyAllocatable() const {
 126     return (DeniedOpts < NumOpts) ||
 127       (std::find(OptUnsafeEdges, OptUnsafeEdges + NumOpts, 0) !=
 128        OptUnsafeEdges + NumOpts);
 129   }
 130
 131 private:
 132   ReductionState RS;
 133   unsigned NumOpts;
 134   unsigned DeniedOpts;
 135   unsigned* OptUnsafeEdges;
 136   unsigned VReg;
 137   OptionToRegMap OptionRegs;
 138 };
 139
 140 class RegAllocSolverImpl {
 141 private:
 142   typedef MDMatrix<MatrixMetadata> RAMatrix;
 143 public:
 144   typedef PBQP::Vector RawVector;
 145   typedef PBQP::Matrix RawMatrix;
 146   typedef PBQP::Vector Vector;
 147   typedef RAMatrix     Matrix;
 148   typedef PBQP::PoolCostAllocator<Vector, Matrix> CostAllocator;
 149
 150   typedef GraphBase::NodeId NodeId;
 151   typedef GraphBase::EdgeId EdgeId;
 152
 153   typedef RegAlloc::NodeMetadata NodeMetadata;
 154
 155   struct EdgeMetadata { };
 156
 157   class GraphMetadata {
 158   public:
 159     GraphMetadata(MachineFunction &MF,
 160                   LiveIntervals &LIS,
 161                   MachineBlockFrequencyInfo &MBFI)
 162       : MF(MF), LIS(LIS), MBFI(MBFI) {}
 163
 164     MachineFunction &MF;
 165     LiveIntervals &LIS;
 166     MachineBlockFrequencyInfo &MBFI;
 167
 168     void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
 169       VRegToNodeId[VReg] = NId;
 170     }
 171
 172     GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
 173       auto VRegItr = VRegToNodeId.find(VReg);
 174       if (VRegItr == VRegToNodeId.end())
 175         return GraphBase::invalidNodeId();
 176       return VRegItr->second;
 177     }
 178
 179     void eraseNodeIdForVReg(unsigned VReg) {
 180       VRegToNodeId.erase(VReg);
 181     }
 182
 183   private:
 184     DenseMap<unsigned, NodeId> VRegToNodeId;
 185   };
 186
 187   typedef PBQP::Graph<RegAllocSolverImpl> Graph;
 188
 189   RegAllocSolverImpl(Graph &G) : G(G) {}
 190
 191   Solution solve() {
 192     G.setSolver(*this);
 193     Solution S;
 194     setup();
 195     S = backpropagate(G, reduce());
 196     G.unsetSolver();
 197     return S;
 198   }
 199
 200   void handleAddNode(NodeId NId) {
 201     G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
 202   }
 203   void handleRemoveNode(NodeId NId) {}
 204   void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
 205
 206   void handleAddEdge(EdgeId EId) {
 207     handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
 208     handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
 209   }
 210
 211   void handleRemoveEdge(EdgeId EId) {
 212     handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
 213     handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
 214   }
 215
 216   void handleDisconnectEdge(EdgeId EId, NodeId NId) {
 217     NodeMetadata& NMd = G.getNodeMetadata(NId);
 218     const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
 219     NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
 220     if (G.getNodeDegree(NId) == 3) {
 221       // This node is becoming optimally reducible.
 222       moveToOptimallyReducibleNodes(NId);
 223     } else if (NMd.getReductionState() ==
 224                NodeMetadata::NotProvablyAllocatable &&
 225                NMd.isConservativelyAllocatable()) {
 226       // This node just became conservatively allocatable.
 227       moveToConservativelyAllocatableNodes(NId);
 228     }
 229   }
 230
 231   void handleReconnectEdge(EdgeId EId, NodeId NId) {
 232     NodeMetadata& NMd = G.getNodeMetadata(NId);
 233     const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
 234     NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
 235   }
 236
 237   void handleSetEdgeCosts(EdgeId EId, const Matrix& NewCosts) {
 238     handleRemoveEdge(EId);
 239
 240     NodeId N1Id = G.getEdgeNode1Id(EId);
 241     NodeId N2Id = G.getEdgeNode2Id(EId);
 242     NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
 243     NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
 244     const MatrixMetadata& MMd = NewCosts.getMetadata();
 245     N1Md.handleAddEdge(MMd, N1Id != G.getEdgeNode1Id(EId));
 246     N2Md.handleAddEdge(MMd, N2Id != G.getEdgeNode1Id(EId));
 247   }
 248
 249 private:
 250
 251   void removeFromCurrentSet(NodeId NId) {
 252     switch (G.getNodeMetadata(NId).getReductionState()) {
 253     case NodeMetadata::Unprocessed: break;
 254     case NodeMetadata::OptimallyReducible:
 255       assert(OptimallyReducibleNodes.find(NId) !=
 256              OptimallyReducibleNodes.end() &&
 257              "Node not in optimally reducible set.");
 258       OptimallyReducibleNodes.erase(NId);
 259       break;
 260     case NodeMetadata::ConservativelyAllocatable:
 261       assert(ConservativelyAllocatableNodes.find(NId) !=
 262              ConservativelyAllocatableNodes.end() &&
 263              "Node not in conservatively allocatable set.");
 264       ConservativelyAllocatableNodes.erase(NId);
 265       break;
 266     case NodeMetadata::NotProvablyAllocatable:
 267       assert(NotProvablyAllocatableNodes.find(NId) !=
 268              NotProvablyAllocatableNodes.end() &&
 269              "Node not in not-provably-allocatable set.");
 270       NotProvablyAllocatableNodes.erase(NId);
 271       break;
 272     }
 273   }
 274
 275   void moveToOptimallyReducibleNodes(NodeId NId) {
 276     removeFromCurrentSet(NId);
 277     OptimallyReducibleNodes.insert(NId);
 278     G.getNodeMetadata(NId).setReductionState(
 279       NodeMetadata::OptimallyReducible);
 280   }
 281
 282   void moveToConservativelyAllocatableNodes(NodeId NId) {
 283     removeFromCurrentSet(NId);
 284     ConservativelyAllocatableNodes.insert(NId);
 285     G.getNodeMetadata(NId).setReductionState(
 286       NodeMetadata::ConservativelyAllocatable);
 287   }
 288
 289   void moveToNotProvablyAllocatableNodes(NodeId NId) {
 290     removeFromCurrentSet(NId);
 291     NotProvablyAllocatableNodes.insert(NId);
 292     G.getNodeMetadata(NId).setReductionState(
 293       NodeMetadata::NotProvablyAllocatable);
 294   }
 295
 296   void setup() {
 297     // Set up worklists.
 298     for (auto NId : G.nodeIds()) {
 299       if (G.getNodeDegree(NId) < 3)
 300         moveToOptimallyReducibleNodes(NId);
 301       else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
 302         moveToConservativelyAllocatableNodes(NId);
 303       else
 304         moveToNotProvablyAllocatableNodes(NId);
 305     }
 306   }
 307
 308   // Compute a reduction order for the graph by iteratively applying PBQP
 309   // reduction rules. Locally optimal rules are applied whenever possible (R0,
 310   // R1, R2). If no locally-optimal rules apply then any conservatively
 311   // allocatable node is reduced. Finally, if no conservatively allocatable
 312   // node exists then the node with the lowest spill-cost:degree ratio is
 313   // selected.
 314   std::vector<GraphBase::NodeId> reduce() {
 315     assert(!G.empty() && "Cannot reduce empty graph.");
 316
 317     typedef GraphBase::NodeId NodeId;
 318     std::vector<NodeId> NodeStack;
 319
 320     // Consume worklists.
 321     while (true) {
 322       if (!OptimallyReducibleNodes.empty()) {
 323         NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
 324         NodeId NId = *NItr;
 325         OptimallyReducibleNodes.erase(NItr);
 326         NodeStack.push_back(NId);
 327         switch (G.getNodeDegree(NId)) {
 328         case 0:
 329           break;
 330         case 1:
 331           applyR1(G, NId);
 332           break;
 333         case 2:
 334           applyR2(G, NId);
 335           break;
 336         default: llvm_unreachable("Not an optimally reducible node.");
 337         }
 338       } else if (!ConservativelyAllocatableNodes.empty()) {
 339         // Conservatively allocatable nodes will never spill. For now just
 340         // take the first node in the set and push it on the stack. When we
 341         // start optimizing more heavily for register preferencing, it may
 342         // would be better to push nodes with lower 'expected' or worst-case
 343         // register costs first (since early nodes are the most
 344         // constrained).
 345         NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
 346         NodeId NId = *NItr;
 347         ConservativelyAllocatableNodes.erase(NItr);
 348         NodeStack.push_back(NId);
 349         G.disconnectAllNeighborsFromNode(NId);
 350
 351       } else if (!NotProvablyAllocatableNodes.empty()) {
 352         NodeSet::iterator NItr =
 353           std::min_element(NotProvablyAllocatableNodes.begin(),
 354                            NotProvablyAllocatableNodes.end(),
 355                            SpillCostComparator(G));
 356         NodeId NId = *NItr;
 357         NotProvablyAllocatableNodes.erase(NItr);
 358         NodeStack.push_back(NId);
 359         G.disconnectAllNeighborsFromNode(NId);
 360       } else
 361         break;
 362     }
 363
 364     return NodeStack;
 365   }
 366
 367   class SpillCostComparator {
 368   public:
 369     SpillCostComparator(const Graph& G) : G(G) {}
 370     bool operator()(NodeId N1Id, NodeId N2Id) {
 371       PBQPNum N1SC = G.getNodeCosts(N1Id)[0] / G.getNodeDegree(N1Id);
 372       PBQPNum N2SC = G.getNodeCosts(N2Id)[0] / G.getNodeDegree(N2Id);
 373       return N1SC < N2SC;
 374     }
 375   private:
 376     const Graph& G;
 377   };
 378
 379   Graph& G;
 380   typedef std::set<NodeId> NodeSet;
 381   NodeSet OptimallyReducibleNodes;
 382   NodeSet ConservativelyAllocatableNodes;
 383   NodeSet NotProvablyAllocatableNodes;
 384 };
 385
 386 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
 387 private:
 388   typedef PBQP::Graph<RegAllocSolverImpl> BaseT;
 389 public:
 390   PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {}
 391 };
 392
 393 inline Solution solve(PBQPRAGraph& G) {
 394   if (G.empty())
 395     return Solution();
 396   RegAllocSolverImpl RegAllocSolver(G);
 397   return RegAllocSolver.solve();
 398 }
 399
 400 } // namespace RegAlloc
 401 } // namespace PBQP
 402
 403 /// @brief Create a PBQP register allocator instance.
 404 FunctionPass *
 405 createPBQPRegisterAllocator(char *customPassID = nullptr);
 406
 407 } // namespace llvm
 408
 409 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */