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