1 //===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
19 #define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
21 #include "../HeuristicSolver.h"
26 namespace Heuristics {
36 typedef HeuristicSolverImpl<Briggs> Solver;
37 typedef HSITypes<NodeData, EdgeData> HSIT;
38 typedef HSIT::SolverGraph SolverGraph;
39 typedef HSIT::GraphNodeIterator GraphNodeIterator;
40 typedef HSIT::GraphEdgeIterator GraphEdgeIterator;
42 class LinkDegreeComparator {
44 LinkDegreeComparator() : g(0) {}
45 LinkDegreeComparator(SolverGraph *g) : g(g) {}
47 bool operator()(const GraphNodeIterator &node1Itr,
48 const GraphNodeIterator &node2Itr) const {
49 assert((g != 0) && "Graph object not set, cannot access node data.");
50 unsigned n1Degree = g->getNodeData(node1Itr).getLinkDegree(),
51 n2Degree = g->getNodeData(node2Itr).getLinkDegree();
52 if (n1Degree > n2Degree) {
55 else if (n1Degree < n2Degree) {
58 // else they're "equal" by degree, differentiate based on ID.
59 return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
66 class SpillPriorityComparator {
68 SpillPriorityComparator() : g(0) {}
69 SpillPriorityComparator(SolverGraph *g) : g(g) {}
71 bool operator()(const GraphNodeIterator &node1Itr,
72 const GraphNodeIterator &node2Itr) const {
73 assert((g != 0) && "Graph object not set, cannot access node data.");
75 g->getNodeCosts(node1Itr)[0] /
76 g->getNodeData(node1Itr).getLinkDegree(),
78 g->getNodeCosts(node2Itr)[0] /
79 g->getNodeData(node2Itr).getLinkDegree();
84 else if (cost1 > cost2) {
87 // else they'er "equal" again, differentiate based on address again.
88 return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
95 typedef std::set<GraphNodeIterator, LinkDegreeComparator>
97 typedef RNAllocableNodeList::iterator RNAllocableNodeListIterator;
99 typedef std::set<GraphNodeIterator, SpillPriorityComparator>
100 RNUnallocableNodeList;
101 typedef RNUnallocableNodeList::iterator RNUnallocableNodeListIterator;
107 RNAllocableNodeListIterator rNAllocableNodeListItr;
108 RNUnallocableNodeListIterator rNUnallocableNodeListItr;
109 unsigned numRegOptions, numDenied, numSafe;
110 std::vector<unsigned> unsafeDegrees;
113 void addRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
114 const GraphEdgeIterator &edgeItr, bool add) {
116 //assume we're adding...
117 unsigned udTarget = 0, dir = 1;
124 EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData();
126 EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd;
128 if (nodeItr == g.getEdgeNode1Itr(edgeItr)) {
129 numDenied += (dir * linkEdgeData.getWorstDegree());
130 edgeUnsafeBegin = linkEdgeData.unsafeBegin();
131 edgeUnsafeEnd = linkEdgeData.unsafeEnd();
134 numDenied += (dir * linkEdgeData.getReverseWorstDegree());
135 edgeUnsafeBegin = linkEdgeData.reverseUnsafeBegin();
136 edgeUnsafeEnd = linkEdgeData.reverseUnsafeEnd();
139 assert((unsafeDegrees.size() ==
140 static_cast<unsigned>(
141 std::distance(edgeUnsafeBegin, edgeUnsafeEnd)))
142 && "Unsafe array size mismatch.");
144 std::vector<unsigned>::iterator unsafeDegreesItr =
145 unsafeDegrees.begin();
147 for (EdgeData::ConstUnsafeIterator edgeUnsafeItr = edgeUnsafeBegin;
148 edgeUnsafeItr != edgeUnsafeEnd;
149 ++edgeUnsafeItr, ++unsafeDegreesItr) {
151 if ((*edgeUnsafeItr == 1) && (*unsafeDegreesItr == udTarget)) {
154 *unsafeDegreesItr += (dir * (*edgeUnsafeItr));
157 allocable = (numDenied < numRegOptions) || (numSafe > 0);
162 void setup(SolverGraph &g, const GraphNodeIterator &nodeItr) {
164 numRegOptions = g.getNodeCosts(nodeItr).getLength() - 1;
166 numSafe = numRegOptions; // Optimistic, correct below.
167 numDenied = 0; // Also optimistic.
168 unsafeDegrees.resize(numRegOptions, 0);
170 HSIT::NodeData &nodeData = g.getNodeData(nodeItr);
172 for (HSIT::NodeData::AdjLinkIterator
173 adjLinkItr = nodeData.adjLinksBegin(),
174 adjLinkEnd = nodeData.adjLinksEnd();
175 adjLinkItr != adjLinkEnd; ++adjLinkItr) {
177 addRemoveLink(g, nodeItr, *adjLinkItr, true);
181 bool isAllocable() const { return allocable; }
183 void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
184 const GraphEdgeIterator &adjEdge) {
185 addRemoveLink(g, nodeItr, adjEdge, true);
188 void handleRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
189 const GraphEdgeIterator &adjEdge) {
190 addRemoveLink(g, nodeItr, adjEdge, false);
193 void setRNAllocableNodeListItr(
194 const RNAllocableNodeListIterator &rNAllocableNodeListItr) {
196 this->rNAllocableNodeListItr = rNAllocableNodeListItr;
199 RNAllocableNodeListIterator getRNAllocableNodeListItr() const {
200 return rNAllocableNodeListItr;
203 void setRNUnallocableNodeListItr(
204 const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) {
206 this->rNUnallocableNodeListItr = rNUnallocableNodeListItr;
209 RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const {
210 return rNUnallocableNodeListItr;
219 typedef std::vector<unsigned> UnsafeArray;
221 unsigned worstDegree,
223 UnsafeArray unsafe, reverseUnsafe;
227 EdgeData() : worstDegree(0), reverseWorstDegree(0) {}
229 typedef UnsafeArray::const_iterator ConstUnsafeIterator;
231 void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) {
232 const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
233 unsigned numRegs = edgeCosts.getRows() - 1,
234 numReverseRegs = edgeCosts.getCols() - 1;
236 unsafe.resize(numRegs, 0);
237 reverseUnsafe.resize(numReverseRegs, 0);
239 std::vector<unsigned> rowInfCounts(numRegs, 0),
240 colInfCounts(numReverseRegs, 0);
242 for (unsigned i = 0; i < numRegs; ++i) {
243 for (unsigned j = 0; j < numReverseRegs; ++j) {
244 if (edgeCosts[i + 1][j + 1] ==
245 std::numeric_limits<PBQPNum>::infinity()) {
247 reverseUnsafe[j] = 1;
251 if (colInfCounts[j] > worstDegree) {
252 worstDegree = colInfCounts[j];
255 if (rowInfCounts[i] > reverseWorstDegree) {
256 reverseWorstDegree = rowInfCounts[i];
263 unsigned getWorstDegree() const { return worstDegree; }
264 unsigned getReverseWorstDegree() const { return reverseWorstDegree; }
265 ConstUnsafeIterator unsafeBegin() const { return unsafe.begin(); }
266 ConstUnsafeIterator unsafeEnd() const { return unsafe.end(); }
267 ConstUnsafeIterator reverseUnsafeBegin() const {
268 return reverseUnsafe.begin();
270 ConstUnsafeIterator reverseUnsafeEnd() const {
271 return reverseUnsafe.end();
275 void initialise(Solver &solver) {
278 rNAllocableBucket = RNAllocableNodeList(LinkDegreeComparator(g));
279 rNUnallocableBucket =
280 RNUnallocableNodeList(SpillPriorityComparator(g));
282 for (GraphEdgeIterator
283 edgeItr = g->edgesBegin(), edgeEnd = g->edgesEnd();
284 edgeItr != edgeEnd; ++edgeItr) {
286 g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
289 for (GraphNodeIterator
290 nodeItr = g->nodesBegin(), nodeEnd = g->nodesEnd();
291 nodeItr != nodeEnd; ++nodeItr) {
293 g->getNodeData(nodeItr).getHeuristicData().setup(*g, nodeItr);
297 void addToRNBucket(const GraphNodeIterator &nodeItr) {
298 NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
300 if (nodeData.isAllocable()) {
301 nodeData.setRNAllocableNodeListItr(
302 rNAllocableBucket.insert(rNAllocableBucket.begin(), nodeItr));
305 nodeData.setRNUnallocableNodeListItr(
306 rNUnallocableBucket.insert(rNUnallocableBucket.begin(), nodeItr));
310 void removeFromRNBucket(const GraphNodeIterator &nodeItr) {
311 NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
313 if (nodeData.isAllocable()) {
314 rNAllocableBucket.erase(nodeData.getRNAllocableNodeListItr());
317 rNUnallocableBucket.erase(nodeData.getRNUnallocableNodeListItr());
321 void handleAddLink(const GraphEdgeIterator &edgeItr) {
322 // We assume that if we got here this edge is attached to at least
323 // one high degree node.
324 g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
326 GraphNodeIterator n1Itr = g->getEdgeNode1Itr(edgeItr),
327 n2Itr = g->getEdgeNode2Itr(edgeItr);
329 HSIT::NodeData &n1Data = g->getNodeData(n1Itr),
330 &n2Data = g->getNodeData(n2Itr);
332 if (n1Data.getLinkDegree() > 2) {
333 n1Data.getHeuristicData().handleAddLink(*g, n1Itr, edgeItr);
335 if (n2Data.getLinkDegree() > 2) {
336 n2Data.getHeuristicData().handleAddLink(*g, n2Itr, edgeItr);
340 void handleRemoveLink(const GraphEdgeIterator &edgeItr,
341 const GraphNodeIterator &nodeItr) {
342 NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
343 nodeData.handleRemoveLink(*g, nodeItr, edgeItr);
348 if (!rNAllocableBucket.empty()) {
349 GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin();
350 //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n";
351 rNAllocableBucket.erase(rNAllocableBucket.begin());
352 s->pushStack(selectedNodeItr);
353 s->unlinkNode(selectedNodeItr);
356 GraphNodeIterator selectedNodeItr = *rNUnallocableBucket.begin();
357 //std::cerr << "RN optimistically pushing " << g->getNodeID(selectedNodeItr) << "\n";
358 rNUnallocableBucket.erase(rNUnallocableBucket.begin());
359 s->pushStack(selectedNodeItr);
360 s->unlinkNode(selectedNodeItr);
365 bool rNBucketEmpty() const {
366 return (rNAllocableBucket.empty() && rNUnallocableBucket.empty());
373 RNAllocableNodeList rNAllocableBucket;
374 RNUnallocableNodeList rNUnallocableBucket;
383 #endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H