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 to select a node for reduction.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
17 #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
21 #include "llvm/Support/raw_ostream.h"
27 /// \brief Heuristic PBQP solver implementation.
29 /// This class should usually be created (and destroyed) indirectly via a call
30 /// to HeuristicSolver<HImpl>::solve(Graph&).
31 /// See the comments for HeuristicSolver.
33 /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules,
34 /// backpropagation phase, and maintains the internal copy of the graph on
35 /// which the reduction is carried out (the original being kept to facilitate
37 template <typename HImpl>
38 class HeuristicSolverImpl {
41 typedef typename HImpl::NodeData HeuristicNodeData;
42 typedef typename HImpl::EdgeData HeuristicEdgeData;
44 typedef std::list<Graph::EdgeItr> SolverEdges;
48 /// \brief Iterator type for edges in the solver graph.
49 typedef SolverEdges::iterator SolverEdgeItr;
55 NodeData() : solverDegree(0) {}
57 HeuristicNodeData& getHeuristicData() { return hData; }
59 SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
61 return solverEdges.insert(solverEdges.end(), eItr);
64 void removeSolverEdge(SolverEdgeItr seItr) {
66 solverEdges.erase(seItr);
69 SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
70 SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
71 unsigned getSolverDegree() const { return solverDegree; }
72 void clearSolverEdges() {
78 HeuristicNodeData hData;
79 unsigned solverDegree;
80 SolverEdges solverEdges;
85 HeuristicEdgeData& getHeuristicData() { return hData; }
87 void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
88 this->n1SolverEdgeItr = n1SolverEdgeItr;
91 SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
93 void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
94 this->n2SolverEdgeItr = n2SolverEdgeItr;
97 SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
101 HeuristicEdgeData hData;
102 SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
108 std::vector<Graph::NodeItr> stack;
110 typedef std::list<NodeData> NodeDataList;
111 NodeDataList nodeDataList;
113 typedef std::list<EdgeData> EdgeDataList;
114 EdgeDataList edgeDataList;
118 /// \brief Construct a heuristic solver implementation to solve the given
120 /// @param g The graph representing the problem instance to be solved.
121 HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}
123 /// \brief Get the graph being solved by this solver.
124 /// @return The graph representing the problem instance being solved by this
126 Graph& getGraph() { return g; }
128 /// \brief Get the heuristic data attached to the given node.
129 /// @param nItr Node iterator.
130 /// @return The heuristic data attached to the given node.
131 HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
132 return getSolverNodeData(nItr).getHeuristicData();
135 /// \brief Get the heuristic data attached to the given edge.
136 /// @param eItr Edge iterator.
137 /// @return The heuristic data attached to the given node.
138 HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
139 return getSolverEdgeData(eItr).getHeuristicData();
142 /// \brief Begin iterator for the set of edges adjacent to the given node in
143 /// the solver graph.
144 /// @param nItr Node iterator.
145 /// @return Begin iterator for the set of edges adjacent to the given node
146 /// in the solver graph.
147 SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
148 return getSolverNodeData(nItr).solverEdgesBegin();
151 /// \brief End iterator for the set of edges adjacent to the given node in
152 /// the solver graph.
153 /// @param nItr Node iterator.
154 /// @return End iterator for the set of edges adjacent to the given node in
155 /// the solver graph.
156 SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
157 return getSolverNodeData(nItr).solverEdgesEnd();
160 /// \brief Remove a node from the solver graph.
161 /// @param eItr Edge iterator for edge to be removed.
163 /// Does <i>not</i> notify the heuristic of the removal. That should be
164 /// done manually if necessary.
165 void removeSolverEdge(Graph::EdgeItr eItr) {
166 EdgeData &eData = getSolverEdgeData(eItr);
167 NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
168 &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
170 n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
171 n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
174 /// \brief Compute a solution to the PBQP problem instance with which this
175 /// heuristic solver was constructed.
176 /// @return A solution to the PBQP problem.
178 /// Performs the full PBQP heuristic solver algorithm, including setup,
179 /// calls to the heuristic (which will call back to the reduction rules in
180 /// this class), and cleanup.
181 Solution computeSolution() {
191 /// \brief Add to the end of the stack.
192 /// @param nItr Node iterator to add to the reduction stack.
193 void pushToStack(Graph::NodeItr nItr) {
194 getSolverNodeData(nItr).clearSolverEdges();
195 stack.push_back(nItr);
198 /// \brief Returns the solver degree of the given node.
199 /// @param nItr Node iterator for which degree is requested.
200 /// @return Node degree in the <i>solver</i> graph (not the original graph).
201 unsigned getSolverDegree(Graph::NodeItr nItr) {
202 return getSolverNodeData(nItr).getSolverDegree();
205 /// \brief Set the solution of the given node.
206 /// @param nItr Node iterator to set solution for.
207 /// @param selection Selection for node.
208 void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
209 s.setSelection(nItr, selection);
211 for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
212 aeEnd = g.adjEdgesEnd(nItr);
213 aeItr != aeEnd; ++aeItr) {
214 Graph::EdgeItr eItr(*aeItr);
215 Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
216 getSolverNodeData(anItr).addSolverEdge(eItr);
220 /// \brief Apply rule R0.
221 /// @param nItr Node iterator for node to apply R0 to.
223 /// Node will be automatically pushed to the solver stack.
224 void applyR0(Graph::NodeItr nItr) {
225 assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
226 "R0 applied to node with degree != 0.");
228 // Nothing to do. Just push the node onto the reduction stack.
232 /// \brief Apply rule R1.
233 /// @param nItr Node iterator for node to apply R1 to.
235 /// Node will be automatically pushed to the solver stack.
236 void applyR1(Graph::NodeItr xnItr) {
237 NodeData &nd = getSolverNodeData(xnItr);
238 assert(nd.getSolverDegree() == 1 &&
239 "R1 applied to node with degree != 1.");
241 Graph::EdgeItr eItr = *nd.solverEdgesBegin();
243 const Matrix &eCosts = g.getEdgeCosts(eItr);
244 const Vector &xCosts = g.getNodeCosts(xnItr);
246 // Duplicate a little to avoid transposing matrices.
247 if (xnItr == g.getEdgeNode1(eItr)) {
248 Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
249 Vector &yCosts = g.getNodeCosts(ynItr);
250 for (unsigned j = 0; j < yCosts.getLength(); ++j) {
251 PBQPNum min = eCosts[0][j] + xCosts[0];
252 for (unsigned i = 1; i < xCosts.getLength(); ++i) {
253 PBQPNum c = eCosts[i][j] + xCosts[i];
259 h.handleRemoveEdge(eItr, ynItr);
261 Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
262 Vector &yCosts = g.getNodeCosts(ynItr);
263 for (unsigned i = 0; i < yCosts.getLength(); ++i) {
264 PBQPNum min = eCosts[i][0] + xCosts[0];
265 for (unsigned j = 1; j < xCosts.getLength(); ++j) {
266 PBQPNum c = eCosts[i][j] + xCosts[j];
272 h.handleRemoveEdge(eItr, ynItr);
274 removeSolverEdge(eItr);
275 assert(nd.getSolverDegree() == 0 &&
276 "Degree 1 with edge removed should be 0.");
280 /// \brief Apply rule R2.
281 /// @param nItr Node iterator for node to apply R2 to.
283 /// Node will be automatically pushed to the solver stack.
284 void applyR2(Graph::NodeItr xnItr) {
285 assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
286 "R2 applied to node with degree != 2.");
288 NodeData &nd = getSolverNodeData(xnItr);
289 const Vector &xCosts = g.getNodeCosts(xnItr);
291 SolverEdgeItr aeItr = nd.solverEdgesBegin();
292 Graph::EdgeItr yxeItr = *aeItr,
295 Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
296 znItr = g.getEdgeOtherNode(zxeItr, xnItr);
298 bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
299 flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
301 const Matrix *yxeCosts = flipEdge1 ?
302 new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
303 &g.getEdgeCosts(yxeItr);
305 const Matrix *zxeCosts = flipEdge2 ?
306 new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
307 &g.getEdgeCosts(zxeItr);
309 unsigned xLen = xCosts.getLength(),
310 yLen = yxeCosts->getRows(),
311 zLen = zxeCosts->getRows();
313 Matrix delta(yLen, zLen);
315 for (unsigned i = 0; i < yLen; ++i) {
316 for (unsigned j = 0; j < zLen; ++j) {
317 PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0];
318 for (unsigned k = 1; k < xLen; ++k) {
319 PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k];
334 Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
335 bool addedEdge = false;
337 if (yzeItr == g.edgesEnd()) {
338 yzeItr = g.addEdge(ynItr, znItr, delta);
341 Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
342 h.preUpdateEdgeCosts(yzeItr);
343 if (ynItr == g.getEdgeNode1(yzeItr)) {
346 yzeCosts += delta.transpose();
350 bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
353 // If we modified the edge costs let the heuristic know.
354 h.postUpdateEdgeCosts(yzeItr);
358 // If this edge ended up null remove it.
360 // We didn't just add it, so we need to notify the heuristic
361 // and remove it from the solver.
362 h.handleRemoveEdge(yzeItr, ynItr);
363 h.handleRemoveEdge(yzeItr, znItr);
364 removeSolverEdge(yzeItr);
366 g.removeEdge(yzeItr);
367 } else if (addedEdge) {
368 // If the edge was added, and non-null, finish setting it up, add it to
369 // the solver & notify heuristic.
370 edgeDataList.push_back(EdgeData());
371 g.setEdgeData(yzeItr, &edgeDataList.back());
372 addSolverEdge(yzeItr);
373 h.handleAddEdge(yzeItr);
376 h.handleRemoveEdge(yxeItr, ynItr);
377 removeSolverEdge(yxeItr);
378 h.handleRemoveEdge(zxeItr, znItr);
379 removeSolverEdge(zxeItr);
386 NodeData& getSolverNodeData(Graph::NodeItr nItr) {
387 return *static_cast<NodeData*>(g.getNodeData(nItr));
390 EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
391 return *static_cast<EdgeData*>(g.getEdgeData(eItr));
394 void addSolverEdge(Graph::EdgeItr eItr) {
395 EdgeData &eData = getSolverEdgeData(eItr);
396 NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
397 &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
399 eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
400 eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
404 if (h.solverRunSimplify()) {
408 // Create node data objects.
409 for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
410 nItr != nEnd; ++nItr) {
411 nodeDataList.push_back(NodeData());
412 g.setNodeData(nItr, &nodeDataList.back());
415 // Create edge data objects.
416 for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
417 eItr != eEnd; ++eItr) {
418 edgeDataList.push_back(EdgeData());
419 g.setEdgeData(eItr, &edgeDataList.back());
425 disconnectTrivialNodes();
426 eliminateIndependentEdges();
429 // Eliminate trivial nodes.
430 void disconnectTrivialNodes() {
431 unsigned numDisconnected = 0;
433 for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
434 nItr != nEnd; ++nItr) {
436 if (g.getNodeCosts(nItr).getLength() == 1) {
438 std::vector<Graph::EdgeItr> edgesToRemove;
440 for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
441 aeEnd = g.adjEdgesEnd(nItr);
442 aeItr != aeEnd; ++aeItr) {
444 Graph::EdgeItr eItr = *aeItr;
446 if (g.getEdgeNode1(eItr) == nItr) {
447 Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
448 g.getNodeCosts(otherNodeItr) +=
449 g.getEdgeCosts(eItr).getRowAsVector(0);
452 Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
453 g.getNodeCosts(otherNodeItr) +=
454 g.getEdgeCosts(eItr).getColAsVector(0);
457 edgesToRemove.push_back(eItr);
460 if (!edgesToRemove.empty())
463 while (!edgesToRemove.empty()) {
464 g.removeEdge(edgesToRemove.back());
465 edgesToRemove.pop_back();
471 void eliminateIndependentEdges() {
472 std::vector<Graph::EdgeItr> edgesToProcess;
473 unsigned numEliminated = 0;
475 for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
476 eItr != eEnd; ++eItr) {
477 edgesToProcess.push_back(eItr);
480 while (!edgesToProcess.empty()) {
481 if (tryToEliminateEdge(edgesToProcess.back()))
483 edgesToProcess.pop_back();
487 bool tryToEliminateEdge(Graph::EdgeItr eItr) {
488 if (tryNormaliseEdgeMatrix(eItr)) {
495 bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
497 Matrix &edgeCosts = g.getEdgeCosts(eItr);
498 Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
499 &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
501 for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
502 PBQPNum rowMin = edgeCosts.getRowMin(r);
504 if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
505 edgeCosts.subFromRow(r, rowMin);
508 edgeCosts.setRow(r, 0);
512 for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
513 PBQPNum colMin = edgeCosts.getColMin(c);
515 if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
516 edgeCosts.subFromCol(c, colMin);
519 edgeCosts.setCol(c, 0);
523 return edgeCosts.isZero();
526 void backpropagate() {
527 while (!stack.empty()) {
528 computeSolution(stack.back());
533 void computeSolution(Graph::NodeItr nItr) {
535 NodeData &nodeData = getSolverNodeData(nItr);
537 Vector v(g.getNodeCosts(nItr));
539 // Solve based on existing solved edges.
540 for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
541 solvedEdgeEnd = nodeData.solverEdgesEnd();
542 solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
544 Graph::EdgeItr eItr(*solvedEdgeItr);
545 Matrix &edgeCosts = g.getEdgeCosts(eItr);
547 if (nItr == g.getEdgeNode1(eItr)) {
548 Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
549 unsigned adjSolution = s.getSelection(adjNode);
550 v += edgeCosts.getColAsVector(adjSolution);
553 Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
554 unsigned adjSolution = s.getSelection(adjNode);
555 v += edgeCosts.getRowAsVector(adjSolution);
560 setSolution(nItr, v.minIndex());
565 nodeDataList.clear();
566 edgeDataList.clear();
570 /// \brief PBQP heuristic solver class.
572 /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
574 /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
576 /// The choice of heuristic for the H parameter will affect both the solver
577 /// speed and solution quality. The heuristic should be chosen based on the
578 /// nature of the problem being solved.
579 /// Currently the only solver included with LLVM is the Briggs heuristic for
580 /// register allocation.
581 template <typename HImpl>
582 class HeuristicSolver {
584 static Solution solve(Graph &g) {
585 HeuristicSolverImpl<HImpl> hs(g);
586 return hs.computeSolution();
592 #endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H