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