• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- 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 // Heuristic PBQP solver. This solver is able to perform optimal reductions for
11 // nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is
12 // used to select a node for reduction.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
17 #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
18 
19 #include "Graph.h"
20 #include "Solution.h"
21 #include <vector>
22 #include <limits>
23 
24 namespace PBQP {
25 
26   /// \brief Heuristic PBQP solver implementation.
27   ///
28   /// This class should usually be created (and destroyed) indirectly via a call
29   /// to HeuristicSolver<HImpl>::solve(Graph&).
30   /// See the comments for HeuristicSolver.
31   ///
32   /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules,
33   /// backpropagation phase, and maintains the internal copy of the graph on
34   /// which the reduction is carried out (the original being kept to facilitate
35   /// backpropagation).
36   template <typename HImpl>
37   class HeuristicSolverImpl {
38   private:
39 
40     typedef typename HImpl::NodeData HeuristicNodeData;
41     typedef typename HImpl::EdgeData HeuristicEdgeData;
42 
43     typedef std::list<Graph::EdgeItr> SolverEdges;
44 
45   public:
46 
47     /// \brief Iterator type for edges in the solver graph.
48     typedef SolverEdges::iterator SolverEdgeItr;
49 
50   private:
51 
52     class NodeData {
53     public:
NodeData()54       NodeData() : solverDegree(0) {}
55 
getHeuristicData()56       HeuristicNodeData& getHeuristicData() { return hData; }
57 
addSolverEdge(Graph::EdgeItr eItr)58       SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
59         ++solverDegree;
60         return solverEdges.insert(solverEdges.end(), eItr);
61       }
62 
removeSolverEdge(SolverEdgeItr seItr)63       void removeSolverEdge(SolverEdgeItr seItr) {
64         --solverDegree;
65         solverEdges.erase(seItr);
66       }
67 
solverEdgesBegin()68       SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
solverEdgesEnd()69       SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
getSolverDegree()70       unsigned getSolverDegree() const { return solverDegree; }
clearSolverEdges()71       void clearSolverEdges() {
72         solverDegree = 0;
73         solverEdges.clear();
74       }
75 
76     private:
77       HeuristicNodeData hData;
78       unsigned solverDegree;
79       SolverEdges solverEdges;
80     };
81 
82     class EdgeData {
83     public:
getHeuristicData()84       HeuristicEdgeData& getHeuristicData() { return hData; }
85 
setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr)86       void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
87         this->n1SolverEdgeItr = n1SolverEdgeItr;
88       }
89 
getN1SolverEdgeItr()90       SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
91 
setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr)92       void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
93         this->n2SolverEdgeItr = n2SolverEdgeItr;
94       }
95 
getN2SolverEdgeItr()96       SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
97 
98     private:
99 
100       HeuristicEdgeData hData;
101       SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
102     };
103 
104     Graph &g;
105     HImpl h;
106     Solution s;
107     std::vector<Graph::NodeItr> stack;
108 
109     typedef std::list<NodeData> NodeDataList;
110     NodeDataList nodeDataList;
111 
112     typedef std::list<EdgeData> EdgeDataList;
113     EdgeDataList edgeDataList;
114 
115   public:
116 
117     /// \brief Construct a heuristic solver implementation to solve the given
118     ///        graph.
119     /// @param g The graph representing the problem instance to be solved.
HeuristicSolverImpl(Graph & g)120     HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}
121 
122     /// \brief Get the graph being solved by this solver.
123     /// @return The graph representing the problem instance being solved by this
124     ///         solver.
getGraph()125     Graph& getGraph() { return g; }
126 
127     /// \brief Get the heuristic data attached to the given node.
128     /// @param nItr Node iterator.
129     /// @return The heuristic data attached to the given node.
getHeuristicNodeData(Graph::NodeItr nItr)130     HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
131       return getSolverNodeData(nItr).getHeuristicData();
132     }
133 
134     /// \brief Get the heuristic data attached to the given edge.
135     /// @param eItr Edge iterator.
136     /// @return The heuristic data attached to the given node.
getHeuristicEdgeData(Graph::EdgeItr eItr)137     HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
138       return getSolverEdgeData(eItr).getHeuristicData();
139     }
140 
141     /// \brief Begin iterator for the set of edges adjacent to the given node in
142     ///        the solver graph.
143     /// @param nItr Node iterator.
144     /// @return Begin iterator for the set of edges adjacent to the given node
145     ///         in the solver graph.
solverEdgesBegin(Graph::NodeItr nItr)146     SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
147       return getSolverNodeData(nItr).solverEdgesBegin();
148     }
149 
150     /// \brief End iterator for the set of edges adjacent to the given node in
151     ///        the solver graph.
152     /// @param nItr Node iterator.
153     /// @return End iterator for the set of edges adjacent to the given node in
154     ///         the solver graph.
solverEdgesEnd(Graph::NodeItr nItr)155     SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
156       return getSolverNodeData(nItr).solverEdgesEnd();
157     }
158 
159     /// \brief Remove a node from the solver graph.
160     /// @param eItr Edge iterator for edge to be removed.
161     ///
162     /// Does <i>not</i> notify the heuristic of the removal. That should be
163     /// done manually if necessary.
removeSolverEdge(Graph::EdgeItr eItr)164     void removeSolverEdge(Graph::EdgeItr eItr) {
165       EdgeData &eData = getSolverEdgeData(eItr);
166       NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
167                &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
168 
169       n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
170       n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
171     }
172 
173     /// \brief Compute a solution to the PBQP problem instance with which this
174     ///        heuristic solver was constructed.
175     /// @return A solution to the PBQP problem.
176     ///
177     /// Performs the full PBQP heuristic solver algorithm, including setup,
178     /// calls to the heuristic (which will call back to the reduction rules in
179     /// this class), and cleanup.
computeSolution()180     Solution computeSolution() {
181       setup();
182       h.setup();
183       h.reduce();
184       backpropagate();
185       h.cleanup();
186       cleanup();
187       return s;
188     }
189 
190     /// \brief Add to the end of the stack.
191     /// @param nItr Node iterator to add to the reduction stack.
pushToStack(Graph::NodeItr nItr)192     void pushToStack(Graph::NodeItr nItr) {
193       getSolverNodeData(nItr).clearSolverEdges();
194       stack.push_back(nItr);
195     }
196 
197     /// \brief Returns the solver degree of the given node.
198     /// @param nItr Node iterator for which degree is requested.
199     /// @return Node degree in the <i>solver</i> graph (not the original graph).
getSolverDegree(Graph::NodeItr nItr)200     unsigned getSolverDegree(Graph::NodeItr nItr) {
201       return  getSolverNodeData(nItr).getSolverDegree();
202     }
203 
204     /// \brief Set the solution of the given node.
205     /// @param nItr Node iterator to set solution for.
206     /// @param selection Selection for node.
setSolution(const Graph::NodeItr & nItr,unsigned selection)207     void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
208       s.setSelection(nItr, selection);
209 
210       for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
211                              aeEnd = g.adjEdgesEnd(nItr);
212            aeItr != aeEnd; ++aeItr) {
213         Graph::EdgeItr eItr(*aeItr);
214         Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
215         getSolverNodeData(anItr).addSolverEdge(eItr);
216       }
217     }
218 
219     /// \brief Apply rule R0.
220     /// @param nItr Node iterator for node to apply R0 to.
221     ///
222     /// Node will be automatically pushed to the solver stack.
applyR0(Graph::NodeItr nItr)223     void applyR0(Graph::NodeItr nItr) {
224       assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
225              "R0 applied to node with degree != 0.");
226 
227       // Nothing to do. Just push the node onto the reduction stack.
228       pushToStack(nItr);
229 
230       s.recordR0();
231     }
232 
233     /// \brief Apply rule R1.
234     /// @param xnItr Node iterator for node to apply R1 to.
235     ///
236     /// Node will be automatically pushed to the solver stack.
applyR1(Graph::NodeItr xnItr)237     void applyR1(Graph::NodeItr xnItr) {
238       NodeData &nd = getSolverNodeData(xnItr);
239       assert(nd.getSolverDegree() == 1 &&
240              "R1 applied to node with degree != 1.");
241 
242       Graph::EdgeItr eItr = *nd.solverEdgesBegin();
243 
244       const Matrix &eCosts = g.getEdgeCosts(eItr);
245       const Vector &xCosts = g.getNodeCosts(xnItr);
246 
247       // Duplicate a little to avoid transposing matrices.
248       if (xnItr == g.getEdgeNode1(eItr)) {
249         Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
250         Vector &yCosts = g.getNodeCosts(ynItr);
251         for (unsigned j = 0; j < yCosts.getLength(); ++j) {
252           PBQPNum min = eCosts[0][j] + xCosts[0];
253           for (unsigned i = 1; i < xCosts.getLength(); ++i) {
254             PBQPNum c = eCosts[i][j] + xCosts[i];
255             if (c < min)
256               min = c;
257           }
258           yCosts[j] += min;
259         }
260         h.handleRemoveEdge(eItr, ynItr);
261      } else {
262         Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
263         Vector &yCosts = g.getNodeCosts(ynItr);
264         for (unsigned i = 0; i < yCosts.getLength(); ++i) {
265           PBQPNum min = eCosts[i][0] + xCosts[0];
266           for (unsigned j = 1; j < xCosts.getLength(); ++j) {
267             PBQPNum c = eCosts[i][j] + xCosts[j];
268             if (c < min)
269               min = c;
270           }
271           yCosts[i] += min;
272         }
273         h.handleRemoveEdge(eItr, ynItr);
274       }
275       removeSolverEdge(eItr);
276       assert(nd.getSolverDegree() == 0 &&
277              "Degree 1 with edge removed should be 0.");
278       pushToStack(xnItr);
279       s.recordR1();
280     }
281 
282     /// \brief Apply rule R2.
283     /// @param xnItr Node iterator for node to apply R2 to.
284     ///
285     /// Node will be automatically pushed to the solver stack.
applyR2(Graph::NodeItr xnItr)286     void applyR2(Graph::NodeItr xnItr) {
287       assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
288              "R2 applied to node with degree != 2.");
289 
290       NodeData &nd = getSolverNodeData(xnItr);
291       const Vector &xCosts = g.getNodeCosts(xnItr);
292 
293       SolverEdgeItr aeItr = nd.solverEdgesBegin();
294       Graph::EdgeItr yxeItr = *aeItr,
295                      zxeItr = *(++aeItr);
296 
297       Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
298                      znItr = g.getEdgeOtherNode(zxeItr, xnItr);
299 
300       bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
301            flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
302 
303       const Matrix *yxeCosts = flipEdge1 ?
304         new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
305         &g.getEdgeCosts(yxeItr);
306 
307       const Matrix *zxeCosts = flipEdge2 ?
308         new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
309         &g.getEdgeCosts(zxeItr);
310 
311       unsigned xLen = xCosts.getLength(),
312                yLen = yxeCosts->getRows(),
313                zLen = zxeCosts->getRows();
314 
315       Matrix delta(yLen, zLen);
316 
317       for (unsigned i = 0; i < yLen; ++i) {
318         for (unsigned j = 0; j < zLen; ++j) {
319           PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0];
320           for (unsigned k = 1; k < xLen; ++k) {
321             PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k];
322             if (c < min) {
323               min = c;
324             }
325           }
326           delta[i][j] = min;
327         }
328       }
329 
330       if (flipEdge1)
331         delete yxeCosts;
332 
333       if (flipEdge2)
334         delete zxeCosts;
335 
336       Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
337       bool addedEdge = false;
338 
339       if (yzeItr == g.edgesEnd()) {
340         yzeItr = g.addEdge(ynItr, znItr, delta);
341         addedEdge = true;
342       } else {
343         Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
344         h.preUpdateEdgeCosts(yzeItr);
345         if (ynItr == g.getEdgeNode1(yzeItr)) {
346           yzeCosts += delta;
347         } else {
348           yzeCosts += delta.transpose();
349         }
350       }
351 
352       bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
353 
354       if (!addedEdge) {
355         // If we modified the edge costs let the heuristic know.
356         h.postUpdateEdgeCosts(yzeItr);
357       }
358 
359       if (nullCostEdge) {
360         // If this edge ended up null remove it.
361         if (!addedEdge) {
362           // We didn't just add it, so we need to notify the heuristic
363           // and remove it from the solver.
364           h.handleRemoveEdge(yzeItr, ynItr);
365           h.handleRemoveEdge(yzeItr, znItr);
366           removeSolverEdge(yzeItr);
367         }
368         g.removeEdge(yzeItr);
369       } else if (addedEdge) {
370         // If the edge was added, and non-null, finish setting it up, add it to
371         // the solver & notify heuristic.
372         edgeDataList.push_back(EdgeData());
373         g.setEdgeData(yzeItr, &edgeDataList.back());
374         addSolverEdge(yzeItr);
375         h.handleAddEdge(yzeItr);
376       }
377 
378       h.handleRemoveEdge(yxeItr, ynItr);
379       removeSolverEdge(yxeItr);
380       h.handleRemoveEdge(zxeItr, znItr);
381       removeSolverEdge(zxeItr);
382 
383       pushToStack(xnItr);
384       s.recordR2();
385     }
386 
387     /// \brief Record an application of the RN rule.
388     ///
389     /// For use by the HeuristicBase.
recordRN()390     void recordRN() { s.recordRN(); }
391 
392   private:
393 
getSolverNodeData(Graph::NodeItr nItr)394     NodeData& getSolverNodeData(Graph::NodeItr nItr) {
395       return *static_cast<NodeData*>(g.getNodeData(nItr));
396     }
397 
getSolverEdgeData(Graph::EdgeItr eItr)398     EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
399       return *static_cast<EdgeData*>(g.getEdgeData(eItr));
400     }
401 
addSolverEdge(Graph::EdgeItr eItr)402     void addSolverEdge(Graph::EdgeItr eItr) {
403       EdgeData &eData = getSolverEdgeData(eItr);
404       NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
405                &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
406 
407       eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
408       eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
409     }
410 
setup()411     void setup() {
412       if (h.solverRunSimplify()) {
413         simplify();
414       }
415 
416       // Create node data objects.
417       for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
418            nItr != nEnd; ++nItr) {
419         nodeDataList.push_back(NodeData());
420         g.setNodeData(nItr, &nodeDataList.back());
421       }
422 
423       // Create edge data objects.
424       for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
425            eItr != eEnd; ++eItr) {
426         edgeDataList.push_back(EdgeData());
427         g.setEdgeData(eItr, &edgeDataList.back());
428         addSolverEdge(eItr);
429       }
430     }
431 
simplify()432     void simplify() {
433       disconnectTrivialNodes();
434       eliminateIndependentEdges();
435     }
436 
437     // Eliminate trivial nodes.
disconnectTrivialNodes()438     void disconnectTrivialNodes() {
439       unsigned numDisconnected = 0;
440 
441       for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
442            nItr != nEnd; ++nItr) {
443 
444         if (g.getNodeCosts(nItr).getLength() == 1) {
445 
446           std::vector<Graph::EdgeItr> edgesToRemove;
447 
448           for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
449                                  aeEnd = g.adjEdgesEnd(nItr);
450                aeItr != aeEnd; ++aeItr) {
451 
452             Graph::EdgeItr eItr = *aeItr;
453 
454             if (g.getEdgeNode1(eItr) == nItr) {
455               Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
456               g.getNodeCosts(otherNodeItr) +=
457                 g.getEdgeCosts(eItr).getRowAsVector(0);
458             }
459             else {
460               Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
461               g.getNodeCosts(otherNodeItr) +=
462                 g.getEdgeCosts(eItr).getColAsVector(0);
463             }
464 
465             edgesToRemove.push_back(eItr);
466           }
467 
468           if (!edgesToRemove.empty())
469             ++numDisconnected;
470 
471           while (!edgesToRemove.empty()) {
472             g.removeEdge(edgesToRemove.back());
473             edgesToRemove.pop_back();
474           }
475         }
476       }
477     }
478 
eliminateIndependentEdges()479     void eliminateIndependentEdges() {
480       std::vector<Graph::EdgeItr> edgesToProcess;
481       unsigned numEliminated = 0;
482 
483       for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
484            eItr != eEnd; ++eItr) {
485         edgesToProcess.push_back(eItr);
486       }
487 
488       while (!edgesToProcess.empty()) {
489         if (tryToEliminateEdge(edgesToProcess.back()))
490           ++numEliminated;
491         edgesToProcess.pop_back();
492       }
493     }
494 
tryToEliminateEdge(Graph::EdgeItr eItr)495     bool tryToEliminateEdge(Graph::EdgeItr eItr) {
496       if (tryNormaliseEdgeMatrix(eItr)) {
497         g.removeEdge(eItr);
498         return true;
499       }
500       return false;
501     }
502 
tryNormaliseEdgeMatrix(Graph::EdgeItr & eItr)503     bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
504 
505       const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity();
506 
507       Matrix &edgeCosts = g.getEdgeCosts(eItr);
508       Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
509              &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
510 
511       for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
512         PBQPNum rowMin = infinity;
513 
514         for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
515           if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin)
516             rowMin = edgeCosts[r][c];
517         }
518 
519         uCosts[r] += rowMin;
520 
521         if (rowMin != infinity) {
522           edgeCosts.subFromRow(r, rowMin);
523         }
524         else {
525           edgeCosts.setRow(r, 0);
526         }
527       }
528 
529       for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
530         PBQPNum colMin = infinity;
531 
532         for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
533           if (uCosts[r] != infinity && edgeCosts[r][c] < colMin)
534             colMin = edgeCosts[r][c];
535         }
536 
537         vCosts[c] += colMin;
538 
539         if (colMin != infinity) {
540           edgeCosts.subFromCol(c, colMin);
541         }
542         else {
543           edgeCosts.setCol(c, 0);
544         }
545       }
546 
547       return edgeCosts.isZero();
548     }
549 
backpropagate()550     void backpropagate() {
551       while (!stack.empty()) {
552         computeSolution(stack.back());
553         stack.pop_back();
554       }
555     }
556 
computeSolution(Graph::NodeItr nItr)557     void computeSolution(Graph::NodeItr nItr) {
558 
559       NodeData &nodeData = getSolverNodeData(nItr);
560 
561       Vector v(g.getNodeCosts(nItr));
562 
563       // Solve based on existing solved edges.
564       for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
565                          solvedEdgeEnd = nodeData.solverEdgesEnd();
566            solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
567 
568         Graph::EdgeItr eItr(*solvedEdgeItr);
569         Matrix &edgeCosts = g.getEdgeCosts(eItr);
570 
571         if (nItr == g.getEdgeNode1(eItr)) {
572           Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
573           unsigned adjSolution = s.getSelection(adjNode);
574           v += edgeCosts.getColAsVector(adjSolution);
575         }
576         else {
577           Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
578           unsigned adjSolution = s.getSelection(adjNode);
579           v += edgeCosts.getRowAsVector(adjSolution);
580         }
581 
582       }
583 
584       setSolution(nItr, v.minIndex());
585     }
586 
cleanup()587     void cleanup() {
588       h.cleanup();
589       nodeDataList.clear();
590       edgeDataList.clear();
591     }
592   };
593 
594   /// \brief PBQP heuristic solver class.
595   ///
596   /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
597   /// by calling
598   /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
599   ///
600   /// The choice of heuristic for the H parameter will affect both the solver
601   /// speed and solution quality. The heuristic should be chosen based on the
602   /// nature of the problem being solved.
603   /// Currently the only solver included with LLVM is the Briggs heuristic for
604   /// register allocation.
605   template <typename HImpl>
606   class HeuristicSolver {
607   public:
solve(Graph & g)608     static Solution solve(Graph &g) {
609       HeuristicSolverImpl<HImpl> hs(g);
610       return hs.computeSolution();
611     }
612   };
613 
614 }
615 
616 #endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
617