1 //===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- 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 // 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.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
17 #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
26 /// \brief Heuristic PBQP solver implementation.
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.
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
36 template <typename HImpl>
37 class HeuristicSolverImpl {
40 typedef typename HImpl::NodeData HeuristicNodeData;
41 typedef typename HImpl::EdgeData HeuristicEdgeData;
43 typedef std::list<Graph::EdgeItr> SolverEdges;
47 /// \brief Iterator type for edges in the solver graph.
48 typedef SolverEdges::iterator SolverEdgeItr;
54 NodeData() : solverDegree(0) {}
56 HeuristicNodeData& getHeuristicData() { return hData; }
58 SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
60 return solverEdges.insert(solverEdges.end(), eItr);
63 void removeSolverEdge(SolverEdgeItr seItr) {
65 solverEdges.erase(seItr);
68 SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
69 SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
70 unsigned getSolverDegree() const { return solverDegree; }
71 void clearSolverEdges() {
77 HeuristicNodeData hData;
78 unsigned solverDegree;
79 SolverEdges solverEdges;
84 HeuristicEdgeData& getHeuristicData() { return hData; }
86 void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
87 this->n1SolverEdgeItr = n1SolverEdgeItr;
90 SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
92 void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
93 this->n2SolverEdgeItr = n2SolverEdgeItr;
96 SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
100 HeuristicEdgeData hData;
101 SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
107 std::vector<Graph::NodeItr> stack;
109 typedef std::list<NodeData> NodeDataList;
110 NodeDataList nodeDataList;
112 typedef std::list<EdgeData> EdgeDataList;
113 EdgeDataList edgeDataList;
117 /// \brief Construct a heuristic solver implementation to solve the given
119 /// @param g The graph representing the problem instance to be solved.
120 HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}
122 /// \brief Get the graph being solved by this solver.
123 /// @return The graph representing the problem instance being solved by this
125 Graph& getGraph() { return g; }
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.
130 HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
131 return getSolverNodeData(nItr).getHeuristicData();
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.
137 HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
138 return getSolverEdgeData(eItr).getHeuristicData();
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.
146 SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
147 return getSolverNodeData(nItr).solverEdgesBegin();
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.
155 SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
156 return getSolverNodeData(nItr).solverEdgesEnd();
159 /// \brief Remove a node from the solver graph.
160 /// @param eItr Edge iterator for edge to be removed.
162 /// Does <i>not</i> notify the heuristic of the removal. That should be
163 /// done manually if necessary.
164 void removeSolverEdge(Graph::EdgeItr eItr) {
165 EdgeData &eData = getSolverEdgeData(eItr);
166 NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
167 &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
169 n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
170 n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
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.
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.
180 Solution computeSolution() {
190 /// \brief Add to the end of the stack.
191 /// @param nItr Node iterator to add to the reduction stack.
192 void pushToStack(Graph::NodeItr nItr) {
193 getSolverNodeData(nItr).clearSolverEdges();
194 stack.push_back(nItr);
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).
200 unsigned getSolverDegree(Graph::NodeItr nItr) {
201 return getSolverNodeData(nItr).getSolverDegree();
204 /// \brief Set the solution of the given node.
205 /// @param nItr Node iterator to set solution for.
206 /// @param selection Selection for node.
207 void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
208 s.setSelection(nItr, selection);
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);
219 /// \brief Apply rule R0.
220 /// @param nItr Node iterator for node to apply R0 to.
222 /// Node will be automatically pushed to the solver stack.
223 void applyR0(Graph::NodeItr nItr) {
224 assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
225 "R0 applied to node with degree != 0.");
227 // Nothing to do. Just push the node onto the reduction stack.
233 /// \brief Apply rule R1.
234 /// @param xnItr Node iterator for node to apply R1 to.
236 /// Node will be automatically pushed to the solver stack.
237 void applyR1(Graph::NodeItr xnItr) {
238 NodeData &nd = getSolverNodeData(xnItr);
239 assert(nd.getSolverDegree() == 1 &&
240 "R1 applied to node with degree != 1.");
242 Graph::EdgeItr eItr = *nd.solverEdgesBegin();
244 const Matrix &eCosts = g.getEdgeCosts(eItr);
245 const Vector &xCosts = g.getNodeCosts(xnItr);
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];
260 h.handleRemoveEdge(eItr, ynItr);
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];
273 h.handleRemoveEdge(eItr, ynItr);
275 removeSolverEdge(eItr);
276 assert(nd.getSolverDegree() == 0 &&
277 "Degree 1 with edge removed should be 0.");
282 /// \brief Apply rule R2.
283 /// @param xnItr Node iterator for node to apply R2 to.
285 /// Node will be automatically pushed to the solver stack.
286 void applyR2(Graph::NodeItr xnItr) {
287 assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
288 "R2 applied to node with degree != 2.");
290 NodeData &nd = getSolverNodeData(xnItr);
291 const Vector &xCosts = g.getNodeCosts(xnItr);
293 SolverEdgeItr aeItr = nd.solverEdgesBegin();
294 Graph::EdgeItr yxeItr = *aeItr,
297 Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
298 znItr = g.getEdgeOtherNode(zxeItr, xnItr);
300 bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
301 flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
303 const Matrix *yxeCosts = flipEdge1 ?
304 new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
305 &g.getEdgeCosts(yxeItr);
307 const Matrix *zxeCosts = flipEdge2 ?
308 new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
309 &g.getEdgeCosts(zxeItr);
311 unsigned xLen = xCosts.getLength(),
312 yLen = yxeCosts->getRows(),
313 zLen = zxeCosts->getRows();
315 Matrix delta(yLen, zLen);
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];
336 Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
337 bool addedEdge = false;
339 if (yzeItr == g.edgesEnd()) {
340 yzeItr = g.addEdge(ynItr, znItr, delta);
343 Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
344 h.preUpdateEdgeCosts(yzeItr);
345 if (ynItr == g.getEdgeNode1(yzeItr)) {
348 yzeCosts += delta.transpose();
352 bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
355 // If we modified the edge costs let the heuristic know.
356 h.postUpdateEdgeCosts(yzeItr);
360 // If this edge ended up null remove it.
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);
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);
378 h.handleRemoveEdge(yxeItr, ynItr);
379 removeSolverEdge(yxeItr);
380 h.handleRemoveEdge(zxeItr, znItr);
381 removeSolverEdge(zxeItr);
387 /// \brief Record an application of the RN rule.
389 /// For use by the HeuristicBase.
390 void recordRN() { s.recordRN(); }
394 NodeData& getSolverNodeData(Graph::NodeItr nItr) {
395 return *static_cast<NodeData*>(g.getNodeData(nItr));
398 EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
399 return *static_cast<EdgeData*>(g.getEdgeData(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));
407 eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
408 eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
412 if (h.solverRunSimplify()) {
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());
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());
433 disconnectTrivialNodes();
434 eliminateIndependentEdges();
437 // Eliminate trivial nodes.
438 void disconnectTrivialNodes() {
439 unsigned numDisconnected = 0;
441 for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
442 nItr != nEnd; ++nItr) {
444 if (g.getNodeCosts(nItr).getLength() == 1) {
446 std::vector<Graph::EdgeItr> edgesToRemove;
448 for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
449 aeEnd = g.adjEdgesEnd(nItr);
450 aeItr != aeEnd; ++aeItr) {
452 Graph::EdgeItr eItr = *aeItr;
454 if (g.getEdgeNode1(eItr) == nItr) {
455 Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
456 g.getNodeCosts(otherNodeItr) +=
457 g.getEdgeCosts(eItr).getRowAsVector(0);
460 Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
461 g.getNodeCosts(otherNodeItr) +=
462 g.getEdgeCosts(eItr).getColAsVector(0);
465 edgesToRemove.push_back(eItr);
468 if (!edgesToRemove.empty())
471 while (!edgesToRemove.empty()) {
472 g.removeEdge(edgesToRemove.back());
473 edgesToRemove.pop_back();
479 void eliminateIndependentEdges() {
480 std::vector<Graph::EdgeItr> edgesToProcess;
481 unsigned numEliminated = 0;
483 for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
484 eItr != eEnd; ++eItr) {
485 edgesToProcess.push_back(eItr);
488 while (!edgesToProcess.empty()) {
489 if (tryToEliminateEdge(edgesToProcess.back()))
491 edgesToProcess.pop_back();
495 bool tryToEliminateEdge(Graph::EdgeItr eItr) {
496 if (tryNormaliseEdgeMatrix(eItr)) {
503 bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
505 const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity();
507 Matrix &edgeCosts = g.getEdgeCosts(eItr);
508 Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
509 &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
511 for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
512 PBQPNum rowMin = infinity;
514 for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
515 if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin)
516 rowMin = edgeCosts[r][c];
521 if (rowMin != infinity) {
522 edgeCosts.subFromRow(r, rowMin);
525 edgeCosts.setRow(r, 0);
529 for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
530 PBQPNum colMin = infinity;
532 for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
533 if (uCosts[r] != infinity && edgeCosts[r][c] < colMin)
534 colMin = edgeCosts[r][c];
539 if (colMin != infinity) {
540 edgeCosts.subFromCol(c, colMin);
543 edgeCosts.setCol(c, 0);
547 return edgeCosts.isZero();
550 void backpropagate() {
551 while (!stack.empty()) {
552 computeSolution(stack.back());
557 void computeSolution(Graph::NodeItr nItr) {
559 NodeData &nodeData = getSolverNodeData(nItr);
561 Vector v(g.getNodeCosts(nItr));
563 // Solve based on existing solved edges.
564 for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
565 solvedEdgeEnd = nodeData.solverEdgesEnd();
566 solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
568 Graph::EdgeItr eItr(*solvedEdgeItr);
569 Matrix &edgeCosts = g.getEdgeCosts(eItr);
571 if (nItr == g.getEdgeNode1(eItr)) {
572 Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
573 unsigned adjSolution = s.getSelection(adjNode);
574 v += edgeCosts.getColAsVector(adjSolution);
577 Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
578 unsigned adjSolution = s.getSelection(adjNode);
579 v += edgeCosts.getRowAsVector(adjSolution);
584 setSolution(nItr, v.minIndex());
589 nodeDataList.clear();
590 edgeDataList.clear();
594 /// \brief PBQP heuristic solver class.
596 /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
598 /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
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 {
608 static Solution solve(Graph &g) {
609 HeuristicSolverImpl<HImpl> hs(g);
610 return hs.computeSolution();
616 #endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H