1 //===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- 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 class implements the Briggs test for "allocability" of nodes in a 11 // PBQP graph representing a register allocation problem. Nodes which can be 12 // proven allocable (by a safe and relatively accurate test) are removed from 13 // the PBQP graph first. If no provably allocable node is present in the graph 14 // then the node with the minimal spill-cost to degree ratio is removed. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H 19 #define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H 20 21 #include "../HeuristicBase.h" 22 #include "../HeuristicSolver.h" 23 #include <limits> 24 25 namespace PBQP { 26 namespace Heuristics { 27 28 /// \brief PBQP Heuristic which applies an allocability test based on 29 /// Briggs. 30 /// 31 /// This heuristic assumes that the elements of cost vectors in the PBQP 32 /// problem represent storage options, with the first being the spill 33 /// option and subsequent elements representing legal registers for the 34 /// corresponding node. Edge cost matrices are likewise assumed to represent 35 /// register constraints. 36 /// If one or more nodes can be proven allocable by this heuristic (by 37 /// inspection of their constraint matrices) then the allocable node of 38 /// highest degree is selected for the next reduction and pushed to the 39 /// solver stack. If no nodes can be proven allocable then the node with 40 /// the lowest estimated spill cost is selected and push to the solver stack 41 /// instead. 42 /// 43 /// This implementation is built on top of HeuristicBase. 44 class Briggs : public HeuristicBase<Briggs> { 45 private: 46 47 class LinkDegreeComparator { 48 public: 49 LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {} 50 bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { 51 if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr)) 52 return true; 53 return false; 54 } 55 private: 56 HeuristicSolverImpl<Briggs> *s; 57 }; 58 59 class SpillCostComparator { 60 public: 61 SpillCostComparator(HeuristicSolverImpl<Briggs> &s) 62 : s(&s), g(&s.getGraph()) {} 63 bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { 64 const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr); 65 const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr); 66 67 PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr); 68 PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr); 69 70 if (cost1 < cost2) 71 return true; 72 return false; 73 } 74 75 private: 76 HeuristicSolverImpl<Briggs> *s; 77 Graph *g; 78 }; 79 80 typedef std::list<Graph::NodeItr> RNAllocableList; 81 typedef RNAllocableList::iterator RNAllocableListItr; 82 83 typedef std::list<Graph::NodeItr> RNUnallocableList; 84 typedef RNUnallocableList::iterator RNUnallocableListItr; 85 86 public: 87 88 struct NodeData { 89 typedef std::vector<unsigned> UnsafeDegreesArray; 90 bool isHeuristic, isAllocable, isInitialized; 91 unsigned numDenied, numSafe; 92 UnsafeDegreesArray unsafeDegrees; 93 RNAllocableListItr rnaItr; 94 RNUnallocableListItr rnuItr; 95 96 NodeData() 97 : isHeuristic(false), isAllocable(false), isInitialized(false), 98 numDenied(0), numSafe(0) { } 99 }; 100 101 struct EdgeData { 102 typedef std::vector<unsigned> UnsafeArray; 103 unsigned worst, reverseWorst; 104 UnsafeArray unsafe, reverseUnsafe; 105 bool isUpToDate; 106 107 EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {} 108 }; 109 110 /// \brief Construct an instance of the Briggs heuristic. 111 /// @param solver A reference to the solver which is using this heuristic. 112 Briggs(HeuristicSolverImpl<Briggs> &solver) : 113 HeuristicBase<Briggs>(solver) {} 114 115 /// \brief Determine whether a node should be reduced using optimal 116 /// reduction. 117 /// @param nItr Node iterator to be considered. 118 /// @return True if the given node should be optimally reduced, false 119 /// otherwise. 120 /// 121 /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one 122 /// exception. Nodes whose spill cost (element 0 of their cost vector) is 123 /// infinite are checked for allocability first. Allocable nodes may be 124 /// optimally reduced, but nodes whose allocability cannot be proven are 125 /// selected for heuristic reduction instead. 126 bool shouldOptimallyReduce(Graph::NodeItr nItr) { 127 if (getSolver().getSolverDegree(nItr) < 3) { 128 return true; 129 } 130 // else 131 return false; 132 } 133 134 /// \brief Add a node to the heuristic reduce list. 135 /// @param nItr Node iterator to add to the heuristic reduce list. 136 void addToHeuristicReduceList(Graph::NodeItr nItr) { 137 NodeData &nd = getHeuristicNodeData(nItr); 138 initializeNode(nItr); 139 nd.isHeuristic = true; 140 if (nd.isAllocable) { 141 nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); 142 } else { 143 nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr); 144 } 145 } 146 147 /// \brief Heuristically reduce one of the nodes in the heuristic 148 /// reduce list. 149 /// @return True if a reduction takes place, false if the heuristic reduce 150 /// list is empty. 151 /// 152 /// If the list of allocable nodes is non-empty a node is selected 153 /// from it and pushed to the stack. Otherwise if the non-allocable list 154 /// is non-empty a node is selected from it and pushed to the stack. 155 /// If both lists are empty the method simply returns false with no action 156 /// taken. 157 bool heuristicReduce() { 158 if (!rnAllocableList.empty()) { 159 RNAllocableListItr rnaItr = 160 min_element(rnAllocableList.begin(), rnAllocableList.end(), 161 LinkDegreeComparator(getSolver())); 162 Graph::NodeItr nItr = *rnaItr; 163 rnAllocableList.erase(rnaItr); 164 handleRemoveNode(nItr); 165 getSolver().pushToStack(nItr); 166 return true; 167 } else if (!rnUnallocableList.empty()) { 168 RNUnallocableListItr rnuItr = 169 min_element(rnUnallocableList.begin(), rnUnallocableList.end(), 170 SpillCostComparator(getSolver())); 171 Graph::NodeItr nItr = *rnuItr; 172 rnUnallocableList.erase(rnuItr); 173 handleRemoveNode(nItr); 174 getSolver().pushToStack(nItr); 175 return true; 176 } 177 // else 178 return false; 179 } 180 181 /// \brief Prepare a change in the costs on the given edge. 182 /// @param eItr Edge iterator. 183 void preUpdateEdgeCosts(Graph::EdgeItr eItr) { 184 Graph &g = getGraph(); 185 Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), 186 n2Itr = g.getEdgeNode2(eItr); 187 NodeData &n1 = getHeuristicNodeData(n1Itr), 188 &n2 = getHeuristicNodeData(n2Itr); 189 190 if (n1.isHeuristic) 191 subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr)); 192 if (n2.isHeuristic) 193 subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr)); 194 195 EdgeData &ed = getHeuristicEdgeData(eItr); 196 ed.isUpToDate = false; 197 } 198 199 /// \brief Handle the change in the costs on the given edge. 200 /// @param eItr Edge iterator. 201 void postUpdateEdgeCosts(Graph::EdgeItr eItr) { 202 // This is effectively the same as adding a new edge now, since 203 // we've factored out the costs of the old one. 204 handleAddEdge(eItr); 205 } 206 207 /// \brief Handle the addition of a new edge into the PBQP graph. 208 /// @param eItr Edge iterator for the added edge. 209 /// 210 /// Updates allocability of any nodes connected by this edge which are 211 /// being managed by the heuristic. If allocability changes they are 212 /// moved to the appropriate list. 213 void handleAddEdge(Graph::EdgeItr eItr) { 214 Graph &g = getGraph(); 215 Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), 216 n2Itr = g.getEdgeNode2(eItr); 217 NodeData &n1 = getHeuristicNodeData(n1Itr), 218 &n2 = getHeuristicNodeData(n2Itr); 219 220 // If neither node is managed by the heuristic there's nothing to be 221 // done. 222 if (!n1.isHeuristic && !n2.isHeuristic) 223 return; 224 225 // Ok - we need to update at least one node. 226 computeEdgeContributions(eItr); 227 228 // Update node 1 if it's managed by the heuristic. 229 if (n1.isHeuristic) { 230 bool n1WasAllocable = n1.isAllocable; 231 addEdgeContributions(eItr, n1Itr); 232 updateAllocability(n1Itr); 233 if (n1WasAllocable && !n1.isAllocable) { 234 rnAllocableList.erase(n1.rnaItr); 235 n1.rnuItr = 236 rnUnallocableList.insert(rnUnallocableList.end(), n1Itr); 237 } 238 } 239 240 // Likewise for node 2. 241 if (n2.isHeuristic) { 242 bool n2WasAllocable = n2.isAllocable; 243 addEdgeContributions(eItr, n2Itr); 244 updateAllocability(n2Itr); 245 if (n2WasAllocable && !n2.isAllocable) { 246 rnAllocableList.erase(n2.rnaItr); 247 n2.rnuItr = 248 rnUnallocableList.insert(rnUnallocableList.end(), n2Itr); 249 } 250 } 251 } 252 253 /// \brief Handle disconnection of an edge from a node. 254 /// @param eItr Edge iterator for edge being disconnected. 255 /// @param nItr Node iterator for the node being disconnected from. 256 /// 257 /// Updates allocability of the given node and, if appropriate, moves the 258 /// node to a new list. 259 void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { 260 NodeData &nd = getHeuristicNodeData(nItr); 261 262 // If the node is not managed by the heuristic there's nothing to be 263 // done. 264 if (!nd.isHeuristic) 265 return; 266 267 EdgeData &ed = getHeuristicEdgeData(eItr); 268 (void)ed; 269 assert(ed.isUpToDate && "Edge data is not up to date."); 270 271 // Update node. 272 bool ndWasAllocable = nd.isAllocable; 273 subtractEdgeContributions(eItr, nItr); 274 updateAllocability(nItr); 275 276 // If the node has gone optimal... 277 if (shouldOptimallyReduce(nItr)) { 278 nd.isHeuristic = false; 279 addToOptimalReduceList(nItr); 280 if (ndWasAllocable) { 281 rnAllocableList.erase(nd.rnaItr); 282 } else { 283 rnUnallocableList.erase(nd.rnuItr); 284 } 285 } else { 286 // Node didn't go optimal, but we might have to move it 287 // from "unallocable" to "allocable". 288 if (!ndWasAllocable && nd.isAllocable) { 289 rnUnallocableList.erase(nd.rnuItr); 290 nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); 291 } 292 } 293 } 294 295 private: 296 297 NodeData& getHeuristicNodeData(Graph::NodeItr nItr) { 298 return getSolver().getHeuristicNodeData(nItr); 299 } 300 301 EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { 302 return getSolver().getHeuristicEdgeData(eItr); 303 } 304 305 // Work out what this edge will contribute to the allocability of the 306 // nodes connected to it. 307 void computeEdgeContributions(Graph::EdgeItr eItr) { 308 EdgeData &ed = getHeuristicEdgeData(eItr); 309 310 if (ed.isUpToDate) 311 return; // Edge data is already up to date. 312 313 Matrix &eCosts = getGraph().getEdgeCosts(eItr); 314 315 unsigned numRegs = eCosts.getRows() - 1, 316 numReverseRegs = eCosts.getCols() - 1; 317 318 std::vector<unsigned> rowInfCounts(numRegs, 0), 319 colInfCounts(numReverseRegs, 0); 320 321 ed.worst = 0; 322 ed.reverseWorst = 0; 323 ed.unsafe.clear(); 324 ed.unsafe.resize(numRegs, 0); 325 ed.reverseUnsafe.clear(); 326 ed.reverseUnsafe.resize(numReverseRegs, 0); 327 328 for (unsigned i = 0; i < numRegs; ++i) { 329 for (unsigned j = 0; j < numReverseRegs; ++j) { 330 if (eCosts[i + 1][j + 1] == 331 std::numeric_limits<PBQPNum>::infinity()) { 332 ed.unsafe[i] = 1; 333 ed.reverseUnsafe[j] = 1; 334 ++rowInfCounts[i]; 335 ++colInfCounts[j]; 336 337 if (colInfCounts[j] > ed.worst) { 338 ed.worst = colInfCounts[j]; 339 } 340 341 if (rowInfCounts[i] > ed.reverseWorst) { 342 ed.reverseWorst = rowInfCounts[i]; 343 } 344 } 345 } 346 } 347 348 ed.isUpToDate = true; 349 } 350 351 // Add the contributions of the given edge to the given node's 352 // numDenied and safe members. No action is taken other than to update 353 // these member values. Once updated these numbers can be used by clients 354 // to update the node's allocability. 355 void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { 356 EdgeData &ed = getHeuristicEdgeData(eItr); 357 358 assert(ed.isUpToDate && "Using out-of-date edge numbers."); 359 360 NodeData &nd = getHeuristicNodeData(nItr); 361 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 362 363 bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); 364 EdgeData::UnsafeArray &unsafe = 365 nIsNode1 ? ed.unsafe : ed.reverseUnsafe; 366 nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst; 367 368 for (unsigned r = 0; r < numRegs; ++r) { 369 if (unsafe[r]) { 370 if (nd.unsafeDegrees[r]==0) { 371 --nd.numSafe; 372 } 373 ++nd.unsafeDegrees[r]; 374 } 375 } 376 } 377 378 // Subtract the contributions of the given edge to the given node's 379 // numDenied and safe members. No action is taken other than to update 380 // these member values. Once updated these numbers can be used by clients 381 // to update the node's allocability. 382 void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { 383 EdgeData &ed = getHeuristicEdgeData(eItr); 384 385 assert(ed.isUpToDate && "Using out-of-date edge numbers."); 386 387 NodeData &nd = getHeuristicNodeData(nItr); 388 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 389 390 bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); 391 EdgeData::UnsafeArray &unsafe = 392 nIsNode1 ? ed.unsafe : ed.reverseUnsafe; 393 nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst; 394 395 for (unsigned r = 0; r < numRegs; ++r) { 396 if (unsafe[r]) { 397 if (nd.unsafeDegrees[r] == 1) { 398 ++nd.numSafe; 399 } 400 --nd.unsafeDegrees[r]; 401 } 402 } 403 } 404 405 void updateAllocability(Graph::NodeItr nItr) { 406 NodeData &nd = getHeuristicNodeData(nItr); 407 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 408 nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; 409 } 410 411 void initializeNode(Graph::NodeItr nItr) { 412 NodeData &nd = getHeuristicNodeData(nItr); 413 414 if (nd.isInitialized) 415 return; // Node data is already up to date. 416 417 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 418 419 nd.numDenied = 0; 420 const Vector& nCosts = getGraph().getNodeCosts(nItr); 421 for (unsigned i = 1; i < nCosts.getLength(); ++i) { 422 if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity()) 423 ++nd.numDenied; 424 } 425 426 nd.numSafe = numRegs; 427 nd.unsafeDegrees.resize(numRegs, 0); 428 429 typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; 430 431 for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr), 432 aeEnd = getSolver().solverEdgesEnd(nItr); 433 aeItr != aeEnd; ++aeItr) { 434 435 Graph::EdgeItr eItr = *aeItr; 436 computeEdgeContributions(eItr); 437 addEdgeContributions(eItr, nItr); 438 } 439 440 updateAllocability(nItr); 441 nd.isInitialized = true; 442 } 443 444 void handleRemoveNode(Graph::NodeItr xnItr) { 445 typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; 446 std::vector<Graph::EdgeItr> edgesToRemove; 447 for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr), 448 aeEnd = getSolver().solverEdgesEnd(xnItr); 449 aeItr != aeEnd; ++aeItr) { 450 Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr); 451 handleRemoveEdge(*aeItr, ynItr); 452 edgesToRemove.push_back(*aeItr); 453 } 454 while (!edgesToRemove.empty()) { 455 getSolver().removeSolverEdge(edgesToRemove.back()); 456 edgesToRemove.pop_back(); 457 } 458 } 459 460 RNAllocableList rnAllocableList; 461 RNUnallocableList rnUnallocableList; 462 }; 463 464 } 465 } 466 467 468 #endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H 469
