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