LLVM API Documentation

Briggs.h

Go to the documentation of this file.
00001 //===-- Briggs.h --- Briggs Heuristic for PBQP -----------------*- C++ --*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This class implements the Briggs test for "allocability" of nodes in a
00011 // PBQP graph representing a register allocation problem. Nodes which can be
00012 // proven allocable (by a safe and relatively accurate test) are removed from
00013 // the PBQP graph first. If no provably allocable node is present in the graph
00014 // then the node with the minimal spill-cost to degree ratio is removed.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
00019 #define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
00020 
00021 #include "../HeuristicSolver.h"
00022 
00023 #include <set>
00024 
00025 namespace PBQP {
00026 namespace Heuristics {
00027 
00028 class Briggs {
00029   public:
00030 
00031     class NodeData;
00032     class EdgeData;
00033 
00034   private:
00035 
00036     typedef HeuristicSolverImpl<Briggs> Solver;
00037     typedef HSITypes<NodeData, EdgeData> HSIT;
00038     typedef HSIT::SolverGraph SolverGraph;
00039     typedef HSIT::GraphNodeIterator GraphNodeIterator;
00040     typedef HSIT::GraphEdgeIterator GraphEdgeIterator;
00041 
00042     class LinkDegreeComparator {
00043       public:
00044         LinkDegreeComparator() : g(0) {}
00045         LinkDegreeComparator(SolverGraph *g) : g(g) {}
00046 
00047         bool operator()(const GraphNodeIterator &node1Itr,
00048                         const GraphNodeIterator &node2Itr) const {
00049           assert((g != 0) && "Graph object not set, cannot access node data.");
00050           unsigned n1Degree = g->getNodeData(node1Itr).getLinkDegree(),
00051                    n2Degree = g->getNodeData(node2Itr).getLinkDegree();
00052           if (n1Degree > n2Degree) {
00053             return true;
00054           }
00055           else if (n1Degree < n2Degree) {
00056             return false;
00057           }
00058           // else they're "equal" by degree, differentiate based on ID.
00059           return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
00060         }
00061 
00062       private:
00063         SolverGraph *g;
00064     };
00065 
00066     class SpillPriorityComparator {
00067       public:
00068         SpillPriorityComparator() : g(0) {}
00069         SpillPriorityComparator(SolverGraph *g) : g(g) {}
00070 
00071         bool operator()(const GraphNodeIterator &node1Itr,
00072                         const GraphNodeIterator &node2Itr) const {
00073           assert((g != 0) && "Graph object not set, cannot access node data.");
00074           PBQPNum cost1 =
00075             g->getNodeCosts(node1Itr)[0] /
00076             g->getNodeData(node1Itr).getLinkDegree(),
00077             cost2 =
00078               g->getNodeCosts(node2Itr)[0] /
00079               g->getNodeData(node2Itr).getLinkDegree();
00080 
00081           if (cost1 < cost2) {
00082             return true;
00083           }
00084           else if (cost1 > cost2) {
00085             return false;
00086           }
00087           // else they'er "equal" again, differentiate based on address again.
00088           return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
00089         }
00090 
00091       private:
00092         SolverGraph *g;
00093     };
00094 
00095     typedef std::set<GraphNodeIterator, LinkDegreeComparator>
00096       RNAllocableNodeList;
00097     typedef RNAllocableNodeList::iterator RNAllocableNodeListIterator;
00098 
00099     typedef std::set<GraphNodeIterator, SpillPriorityComparator>
00100       RNUnallocableNodeList;
00101     typedef RNUnallocableNodeList::iterator RNUnallocableNodeListIterator;
00102 
00103   public:
00104 
00105     class NodeData {
00106       private:
00107         RNAllocableNodeListIterator rNAllocableNodeListItr;
00108         RNUnallocableNodeListIterator rNUnallocableNodeListItr;
00109         unsigned numRegOptions, numDenied, numSafe;
00110         std::vector<unsigned> unsafeDegrees;
00111         bool allocable;
00112 
00113         void addRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
00114             const GraphEdgeIterator &edgeItr, bool add) {
00115 
00116           //assume we're adding...
00117           unsigned udTarget = 0, dir = 1;
00118 
00119           if (!add) {
00120             udTarget = 1;
00121             dir = -1;
00122           }
00123 
00124           EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData();
00125 
00126           EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd;
00127 
00128           if (nodeItr == g.getEdgeNode1Itr(edgeItr)) {
00129             numDenied += (dir * linkEdgeData.getWorstDegree());
00130             edgeUnsafeBegin = linkEdgeData.unsafeBegin();
00131             edgeUnsafeEnd = linkEdgeData.unsafeEnd();
00132           }
00133           else {
00134             numDenied += (dir * linkEdgeData.getReverseWorstDegree());
00135             edgeUnsafeBegin = linkEdgeData.reverseUnsafeBegin();
00136             edgeUnsafeEnd = linkEdgeData.reverseUnsafeEnd();
00137           }
00138 
00139           assert((unsafeDegrees.size() ==
00140                 static_cast<unsigned>(
00141                   std::distance(edgeUnsafeBegin, edgeUnsafeEnd)))
00142               && "Unsafe array size mismatch.");
00143 
00144           std::vector<unsigned>::iterator unsafeDegreesItr =
00145             unsafeDegrees.begin();
00146 
00147           for (EdgeData::ConstUnsafeIterator edgeUnsafeItr = edgeUnsafeBegin;
00148               edgeUnsafeItr != edgeUnsafeEnd;
00149               ++edgeUnsafeItr, ++unsafeDegreesItr) {
00150 
00151             if ((*edgeUnsafeItr == 1) && (*unsafeDegreesItr == udTarget))  {
00152               numSafe -= dir;
00153             }
00154             *unsafeDegreesItr += (dir * (*edgeUnsafeItr));
00155           }
00156 
00157           allocable = (numDenied < numRegOptions) || (numSafe > 0);
00158         }
00159 
00160       public:
00161 
00162         void setup(SolverGraph &g, const GraphNodeIterator &nodeItr) {
00163 
00164           numRegOptions = g.getNodeCosts(nodeItr).getLength() - 1;
00165 
00166           numSafe = numRegOptions; // Optimistic, correct below.
00167           numDenied = 0; // Also optimistic.
00168           unsafeDegrees.resize(numRegOptions, 0);
00169 
00170           HSIT::NodeData &nodeData = g.getNodeData(nodeItr);
00171 
00172           for (HSIT::NodeData::AdjLinkIterator
00173               adjLinkItr = nodeData.adjLinksBegin(),
00174               adjLinkEnd = nodeData.adjLinksEnd();
00175               adjLinkItr != adjLinkEnd; ++adjLinkItr) {
00176 
00177             addRemoveLink(g, nodeItr, *adjLinkItr, true);
00178           }
00179         }
00180 
00181         bool isAllocable() const { return allocable; }
00182 
00183         void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
00184             const GraphEdgeIterator &adjEdge) {
00185           addRemoveLink(g, nodeItr, adjEdge, true);
00186         }
00187 
00188         void handleRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
00189             const GraphEdgeIterator &adjEdge) {
00190           addRemoveLink(g, nodeItr, adjEdge, false);
00191         }
00192 
00193         void setRNAllocableNodeListItr(
00194             const RNAllocableNodeListIterator &rNAllocableNodeListItr) {
00195 
00196           this->rNAllocableNodeListItr = rNAllocableNodeListItr;
00197         }
00198 
00199         RNAllocableNodeListIterator getRNAllocableNodeListItr() const {
00200           return rNAllocableNodeListItr;
00201         }
00202 
00203         void setRNUnallocableNodeListItr(
00204             const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) {
00205 
00206           this->rNUnallocableNodeListItr = rNUnallocableNodeListItr;
00207         }
00208 
00209         RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const {
00210           return rNUnallocableNodeListItr;
00211         }
00212 
00213 
00214     };
00215 
00216     class EdgeData {
00217       private:
00218 
00219         typedef std::vector<unsigned> UnsafeArray;
00220 
00221         unsigned worstDegree,
00222                  reverseWorstDegree;
00223         UnsafeArray unsafe, reverseUnsafe;
00224 
00225       public:
00226 
00227         EdgeData() : worstDegree(0), reverseWorstDegree(0) {}
00228 
00229         typedef UnsafeArray::const_iterator ConstUnsafeIterator;
00230 
00231         void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) {
00232           const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
00233           unsigned numRegs = edgeCosts.getRows() - 1,
00234                    numReverseRegs = edgeCosts.getCols() - 1;
00235 
00236           unsafe.resize(numRegs, 0);
00237           reverseUnsafe.resize(numReverseRegs, 0);
00238 
00239           std::vector<unsigned> rowInfCounts(numRegs, 0),
00240                                 colInfCounts(numReverseRegs, 0);
00241 
00242           for (unsigned i = 0; i < numRegs; ++i) {
00243             for (unsigned j = 0; j < numReverseRegs; ++j) {
00244               if (edgeCosts[i + 1][j + 1] ==
00245                   std::numeric_limits<PBQPNum>::infinity()) {
00246                 unsafe[i] = 1;
00247                 reverseUnsafe[j] = 1;
00248                 ++rowInfCounts[i];
00249                 ++colInfCounts[j];
00250 
00251                 if (colInfCounts[j] > worstDegree) {
00252                   worstDegree = colInfCounts[j];
00253                 }
00254 
00255                 if (rowInfCounts[i] > reverseWorstDegree) {
00256                   reverseWorstDegree = rowInfCounts[i];
00257                 }
00258               }
00259             }
00260           }
00261         }
00262 
00263         unsigned getWorstDegree() const { return worstDegree; }
00264         unsigned getReverseWorstDegree() const { return reverseWorstDegree; }
00265         ConstUnsafeIterator unsafeBegin() const { return unsafe.begin(); }
00266         ConstUnsafeIterator unsafeEnd() const { return unsafe.end(); }
00267         ConstUnsafeIterator reverseUnsafeBegin() const {
00268           return reverseUnsafe.begin();
00269         }
00270         ConstUnsafeIterator reverseUnsafeEnd() const {
00271           return reverseUnsafe.end();
00272         }
00273     };
00274 
00275   void initialise(Solver &solver) {
00276     this->s = &solver;
00277     g = &s->getGraph();
00278     rNAllocableBucket = RNAllocableNodeList(LinkDegreeComparator(g));
00279     rNUnallocableBucket =
00280       RNUnallocableNodeList(SpillPriorityComparator(g));
00281     
00282     for (GraphEdgeIterator
00283          edgeItr = g->edgesBegin(), edgeEnd = g->edgesEnd();
00284          edgeItr != edgeEnd; ++edgeItr) {
00285 
00286       g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
00287     }
00288 
00289     for (GraphNodeIterator
00290          nodeItr = g->nodesBegin(), nodeEnd = g->nodesEnd();
00291          nodeItr != nodeEnd; ++nodeItr) {
00292 
00293       g->getNodeData(nodeItr).getHeuristicData().setup(*g, nodeItr);
00294     }
00295   }
00296 
00297   void addToRNBucket(const GraphNodeIterator &nodeItr) {
00298     NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
00299 
00300     if (nodeData.isAllocable()) {
00301       nodeData.setRNAllocableNodeListItr(
00302         rNAllocableBucket.insert(rNAllocableBucket.begin(), nodeItr));
00303     }
00304     else {
00305       nodeData.setRNUnallocableNodeListItr(
00306         rNUnallocableBucket.insert(rNUnallocableBucket.begin(), nodeItr));
00307     }
00308   }
00309 
00310   void removeFromRNBucket(const GraphNodeIterator &nodeItr) {
00311     NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
00312 
00313     if (nodeData.isAllocable()) {
00314       rNAllocableBucket.erase(nodeData.getRNAllocableNodeListItr());
00315     }
00316     else {
00317       rNUnallocableBucket.erase(nodeData.getRNUnallocableNodeListItr());
00318     }
00319   }
00320 
00321   void handleAddLink(const GraphEdgeIterator &edgeItr) {
00322     // We assume that if we got here this edge is attached to at least
00323     // one high degree node.
00324     g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
00325 
00326     GraphNodeIterator n1Itr = g->getEdgeNode1Itr(edgeItr),
00327                       n2Itr = g->getEdgeNode2Itr(edgeItr);
00328    
00329     HSIT::NodeData &n1Data = g->getNodeData(n1Itr),
00330                    &n2Data = g->getNodeData(n2Itr);
00331 
00332     if (n1Data.getLinkDegree() > 2) {
00333       n1Data.getHeuristicData().handleAddLink(*g, n1Itr, edgeItr);
00334     }
00335     if (n2Data.getLinkDegree() > 2) {
00336       n2Data.getHeuristicData().handleAddLink(*g, n2Itr, edgeItr);
00337     }
00338   }
00339 
00340   void handleRemoveLink(const GraphEdgeIterator &edgeItr,
00341                         const GraphNodeIterator &nodeItr) {
00342     NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
00343     nodeData.handleRemoveLink(*g, nodeItr, edgeItr);
00344   }
00345 
00346   void processRN() {
00347     
00348     if (!rNAllocableBucket.empty()) {
00349       GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin();
00350       //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n";
00351       rNAllocableBucket.erase(rNAllocableBucket.begin());
00352       s->pushStack(selectedNodeItr);
00353       s->unlinkNode(selectedNodeItr);
00354     }
00355     else {
00356       GraphNodeIterator selectedNodeItr = *rNUnallocableBucket.begin();
00357       //std::cerr << "RN optimistically pushing " << g->getNodeID(selectedNodeItr) << "\n";
00358       rNUnallocableBucket.erase(rNUnallocableBucket.begin());
00359       s->pushStack(selectedNodeItr);
00360       s->unlinkNode(selectedNodeItr);
00361     }
00362  
00363   }
00364 
00365   bool rNBucketEmpty() const {
00366     return (rNAllocableBucket.empty() && rNUnallocableBucket.empty());
00367   }
00368 
00369 private:
00370 
00371   Solver *s;
00372   SolverGraph *g;
00373   RNAllocableNodeList rNAllocableBucket;
00374   RNUnallocableNodeList rNUnallocableBucket;
00375 };
00376 
00377 
00378 
00379 }
00380 }
00381 
00382 
00383 #endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H