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 "../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         const Vector& nCosts = getGraph().getNodeCosts(nItr);
 422         for (unsigned i = 1; i < nCosts.getLength(); ++i) {
 423           if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity())
 424             ++nd.numDenied;
 425         }
 426
 427         nd.numSafe = numRegs;
 428         nd.unsafeDegrees.resize(numRegs, 0);
 429
 430         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
 431
 432         for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
 433                            aeEnd = getSolver().solverEdgesEnd(nItr);
 434              aeItr != aeEnd; ++aeItr) {
 435
 436           Graph::EdgeItr eItr = *aeItr;
 437           computeEdgeContributions(eItr);
 438           addEdgeContributions(eItr, nItr);
 439         }
 440
 441         updateAllocability(nItr);
 442         nd.isInitialized = true;
 443       }
 444
 445       void handleRemoveNode(Graph::NodeItr xnItr) {
 446         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
 447         std::vector<Graph::EdgeItr> edgesToRemove;
 448         for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
 449                            aeEnd = getSolver().solverEdgesEnd(xnItr);
 450              aeItr != aeEnd; ++aeItr) {
 451           Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
 452           handleRemoveEdge(*aeItr, ynItr);
 453           edgesToRemove.push_back(*aeItr);
 454         }
 455         while (!edgesToRemove.empty()) {
 456           getSolver().removeSolverEdge(edgesToRemove.back());
 457           edgesToRemove.pop_back();
 458         }
 459       }
 460
 461       RNAllocableList rnAllocableList;
 462       RNUnallocableList rnUnallocableList;
 463     };
 464
 465   }
 466 }
 467
 468
 469 #endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H