Home | History | Annotate | Download | only in Heuristics
      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
    470