contrib/llvm/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h

   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