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