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 "../HeuristicBase.h"
22 #include "../HeuristicSolver.h"
26 namespace Heuristics {
28 /// \brief PBQP Heuristic which applies an allocability test based on
31 /// This heuristic assumes that the elements of cost vectors in the PBQP
32 /// problem represent storage options, with the first being the spill
33 /// option and subsequent elements representing legal registers for the
34 /// corresponding node. Edge cost matrices are likewise assumed to represent
35 /// register constraints.
36 /// If one or more nodes can be proven allocable by this heuristic (by
37 /// inspection of their constraint matrices) then the allocable node of
38 /// highest degree is selected for the next reduction and pushed to the
39 /// solver stack. If no nodes can be proven allocable then the node with
40 /// the lowest estimated spill cost is selected and push to the solver stack
43 /// This implementation is built on top of HeuristicBase.
44 class Briggs : public HeuristicBase<Briggs> {
47 class LinkDegreeComparator {
49 LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
50 bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
51 if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
56 HeuristicSolverImpl<Briggs> *s;
59 class SpillCostComparator {
61 SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
62 : s(&s), g(&s.getGraph()) {}
63 bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
64 const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
65 const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);
67 PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
68 PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);
76 HeuristicSolverImpl<Briggs> *s;
80 typedef std::list<Graph::NodeItr> RNAllocableList;
81 typedef RNAllocableList::iterator RNAllocableListItr;
83 typedef std::list<Graph::NodeItr> RNUnallocableList;
84 typedef RNUnallocableList::iterator RNUnallocableListItr;
89 typedef std::vector<unsigned> UnsafeDegreesArray;
90 bool isHeuristic, isAllocable, isInitialized;
91 unsigned numDenied, numSafe;
92 UnsafeDegreesArray unsafeDegrees;
93 RNAllocableListItr rnaItr;
94 RNUnallocableListItr rnuItr;
97 : isHeuristic(false), isAllocable(false), isInitialized(false),
98 numDenied(0), numSafe(0) { }
102 typedef std::vector<unsigned> UnsafeArray;
103 unsigned worst, reverseWorst;
104 UnsafeArray unsafe, reverseUnsafe;
107 EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
110 /// \brief Construct an instance of the Briggs heuristic.
111 /// @param solver A reference to the solver which is using this heuristic.
112 Briggs(HeuristicSolverImpl<Briggs> &solver) :
113 HeuristicBase<Briggs>(solver) {}
115 /// \brief Determine whether a node should be reduced using optimal
117 /// @param nItr Node iterator to be considered.
118 /// @return True if the given node should be optimally reduced, false
121 /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one
122 /// exception. Nodes whose spill cost (element 0 of their cost vector) is
123 /// infinite are checked for allocability first. Allocable nodes may be
124 /// optimally reduced, but nodes whose allocability cannot be proven are
125 /// selected for heuristic reduction instead.
126 bool shouldOptimallyReduce(Graph::NodeItr nItr) {
127 if (getSolver().getSolverDegree(nItr) < 3) {
134 /// \brief Add a node to the heuristic reduce list.
135 /// @param nItr Node iterator to add to the heuristic reduce list.
136 void addToHeuristicReduceList(Graph::NodeItr nItr) {
137 NodeData &nd = getHeuristicNodeData(nItr);
138 initializeNode(nItr);
139 nd.isHeuristic = true;
140 if (nd.isAllocable) {
141 nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
143 nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
147 /// \brief Heuristically reduce one of the nodes in the heuristic
149 /// @return True if a reduction takes place, false if the heuristic reduce
152 /// If the list of allocable nodes is non-empty a node is selected
153 /// from it and pushed to the stack. Otherwise if the non-allocable list
154 /// is non-empty a node is selected from it and pushed to the stack.
155 /// If both lists are empty the method simply returns false with no action
157 bool heuristicReduce() {
158 if (!rnAllocableList.empty()) {
159 RNAllocableListItr rnaItr =
160 min_element(rnAllocableList.begin(), rnAllocableList.end(),
161 LinkDegreeComparator(getSolver()));
162 Graph::NodeItr nItr = *rnaItr;
163 rnAllocableList.erase(rnaItr);
164 handleRemoveNode(nItr);
165 getSolver().pushToStack(nItr);
167 } else if (!rnUnallocableList.empty()) {
168 RNUnallocableListItr rnuItr =
169 min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
170 SpillCostComparator(getSolver()));
171 Graph::NodeItr nItr = *rnuItr;
172 rnUnallocableList.erase(rnuItr);
173 handleRemoveNode(nItr);
174 getSolver().pushToStack(nItr);
181 /// \brief Prepare a change in the costs on the given edge.
182 /// @param eItr Edge iterator.
183 void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
184 Graph &g = getGraph();
185 Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
186 n2Itr = g.getEdgeNode2(eItr);
187 NodeData &n1 = getHeuristicNodeData(n1Itr),
188 &n2 = getHeuristicNodeData(n2Itr);
191 subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
193 subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
195 EdgeData &ed = getHeuristicEdgeData(eItr);
196 ed.isUpToDate = false;
199 /// \brief Handle the change in the costs on the given edge.
200 /// @param eItr Edge iterator.
201 void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
202 // This is effectively the same as adding a new edge now, since
203 // we've factored out the costs of the old one.
207 /// \brief Handle the addition of a new edge into the PBQP graph.
208 /// @param eItr Edge iterator for the added edge.
210 /// Updates allocability of any nodes connected by this edge which are
211 /// being managed by the heuristic. If allocability changes they are
212 /// moved to the appropriate list.
213 void handleAddEdge(Graph::EdgeItr eItr) {
214 Graph &g = getGraph();
215 Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
216 n2Itr = g.getEdgeNode2(eItr);
217 NodeData &n1 = getHeuristicNodeData(n1Itr),
218 &n2 = getHeuristicNodeData(n2Itr);
220 // If neither node is managed by the heuristic there's nothing to be
222 if (!n1.isHeuristic && !n2.isHeuristic)
225 // Ok - we need to update at least one node.
226 computeEdgeContributions(eItr);
228 // Update node 1 if it's managed by the heuristic.
229 if (n1.isHeuristic) {
230 bool n1WasAllocable = n1.isAllocable;
231 addEdgeContributions(eItr, n1Itr);
232 updateAllocability(n1Itr);
233 if (n1WasAllocable && !n1.isAllocable) {
234 rnAllocableList.erase(n1.rnaItr);
236 rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
240 // Likewise for node 2.
241 if (n2.isHeuristic) {
242 bool n2WasAllocable = n2.isAllocable;
243 addEdgeContributions(eItr, n2Itr);
244 updateAllocability(n2Itr);
245 if (n2WasAllocable && !n2.isAllocable) {
246 rnAllocableList.erase(n2.rnaItr);
248 rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
253 /// \brief Handle disconnection of an edge from a node.
254 /// @param eItr Edge iterator for edge being disconnected.
255 /// @param nItr Node iterator for the node being disconnected from.
257 /// Updates allocability of the given node and, if appropriate, moves the
258 /// node to a new list.
259 void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
260 NodeData &nd = getHeuristicNodeData(nItr);
262 // If the node is not managed by the heuristic there's nothing to be
267 EdgeData &ed = getHeuristicEdgeData(eItr);
269 assert(ed.isUpToDate && "Edge data is not up to date.");
272 bool ndWasAllocable = nd.isAllocable;
273 subtractEdgeContributions(eItr, nItr);
274 updateAllocability(nItr);
276 // If the node has gone optimal...
277 if (shouldOptimallyReduce(nItr)) {
278 nd.isHeuristic = false;
279 addToOptimalReduceList(nItr);
280 if (ndWasAllocable) {
281 rnAllocableList.erase(nd.rnaItr);
283 rnUnallocableList.erase(nd.rnuItr);
286 // Node didn't go optimal, but we might have to move it
287 // from "unallocable" to "allocable".
288 if (!ndWasAllocable && nd.isAllocable) {
289 rnUnallocableList.erase(nd.rnuItr);
290 nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
297 NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
298 return getSolver().getHeuristicNodeData(nItr);
301 EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
302 return getSolver().getHeuristicEdgeData(eItr);
305 // Work out what this edge will contribute to the allocability of the
306 // nodes connected to it.
307 void computeEdgeContributions(Graph::EdgeItr eItr) {
308 EdgeData &ed = getHeuristicEdgeData(eItr);
311 return; // Edge data is already up to date.
313 Matrix &eCosts = getGraph().getEdgeCosts(eItr);
315 unsigned numRegs = eCosts.getRows() - 1,
316 numReverseRegs = eCosts.getCols() - 1;
318 std::vector<unsigned> rowInfCounts(numRegs, 0),
319 colInfCounts(numReverseRegs, 0);
324 ed.unsafe.resize(numRegs, 0);
325 ed.reverseUnsafe.clear();
326 ed.reverseUnsafe.resize(numReverseRegs, 0);
328 for (unsigned i = 0; i < numRegs; ++i) {
329 for (unsigned j = 0; j < numReverseRegs; ++j) {
330 if (eCosts[i + 1][j + 1] ==
331 std::numeric_limits<PBQPNum>::infinity()) {
333 ed.reverseUnsafe[j] = 1;
337 if (colInfCounts[j] > ed.worst) {
338 ed.worst = colInfCounts[j];
341 if (rowInfCounts[i] > ed.reverseWorst) {
342 ed.reverseWorst = rowInfCounts[i];
348 ed.isUpToDate = true;
351 // Add the contributions of the given edge to the given node's
352 // numDenied and safe members. No action is taken other than to update
353 // these member values. Once updated these numbers can be used by clients
354 // to update the node's allocability.
355 void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
356 EdgeData &ed = getHeuristicEdgeData(eItr);
358 assert(ed.isUpToDate && "Using out-of-date edge numbers.");
360 NodeData &nd = getHeuristicNodeData(nItr);
361 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
363 bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
364 EdgeData::UnsafeArray &unsafe =
365 nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
366 nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
368 for (unsigned r = 0; r < numRegs; ++r) {
370 if (nd.unsafeDegrees[r]==0) {
373 ++nd.unsafeDegrees[r];
378 // Subtract the contributions of the given edge to the given node's
379 // numDenied and safe members. No action is taken other than to update
380 // these member values. Once updated these numbers can be used by clients
381 // to update the node's allocability.
382 void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
383 EdgeData &ed = getHeuristicEdgeData(eItr);
385 assert(ed.isUpToDate && "Using out-of-date edge numbers.");
387 NodeData &nd = getHeuristicNodeData(nItr);
388 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
390 bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
391 EdgeData::UnsafeArray &unsafe =
392 nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
393 nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
395 for (unsigned r = 0; r < numRegs; ++r) {
397 if (nd.unsafeDegrees[r] == 1) {
400 --nd.unsafeDegrees[r];
405 void updateAllocability(Graph::NodeItr nItr) {
406 NodeData &nd = getHeuristicNodeData(nItr);
407 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
408 nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
411 void initializeNode(Graph::NodeItr nItr) {
412 NodeData &nd = getHeuristicNodeData(nItr);
414 if (nd.isInitialized)
415 return; // Node data is already up to date.
417 unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
420 const Vector& nCosts = getGraph().getNodeCosts(nItr);
421 for (unsigned i = 1; i < nCosts.getLength(); ++i) {
422 if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity())
426 nd.numSafe = numRegs;
427 nd.unsafeDegrees.resize(numRegs, 0);
429 typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
431 for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
432 aeEnd = getSolver().solverEdgesEnd(nItr);
433 aeItr != aeEnd; ++aeItr) {
435 Graph::EdgeItr eItr = *aeItr;
436 computeEdgeContributions(eItr);
437 addEdgeContributions(eItr, nItr);
440 updateAllocability(nItr);
441 nd.isInitialized = true;
444 void handleRemoveNode(Graph::NodeItr xnItr) {
445 typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
446 std::vector<Graph::EdgeItr> edgesToRemove;
447 for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
448 aeEnd = getSolver().solverEdgesEnd(xnItr);
449 aeItr != aeEnd; ++aeItr) {
450 Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
451 handleRemoveEdge(*aeItr, ynItr);
452 edgesToRemove.push_back(*aeItr);
454 while (!edgesToRemove.empty()) {
455 getSolver().removeSolverEdge(edgesToRemove.back());
456 edgesToRemove.pop_back();
460 RNAllocableList rnAllocableList;
461 RNUnallocableList rnUnallocableList;
468 #endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H