LLVM API Documentation
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