| //===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Heuristic PBQP solver. This solver is able to perform optimal reductions for |
| // nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is |
| // used to select a node for reduction. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H |
| #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H |
| |
| #include "Graph.h" |
| #include "Solution.h" |
| #include <vector> |
| #include <limits> |
| |
| namespace PBQP { |
| |
| /// \brief Heuristic PBQP solver implementation. |
| /// |
| /// This class should usually be created (and destroyed) indirectly via a call |
| /// to HeuristicSolver<HImpl>::solve(Graph&). |
| /// See the comments for HeuristicSolver. |
| /// |
| /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules, |
| /// backpropagation phase, and maintains the internal copy of the graph on |
| /// which the reduction is carried out (the original being kept to facilitate |
| /// backpropagation). |
| template <typename HImpl> |
| class HeuristicSolverImpl { |
| private: |
| |
| typedef typename HImpl::NodeData HeuristicNodeData; |
| typedef typename HImpl::EdgeData HeuristicEdgeData; |
| |
| typedef std::list<Graph::EdgeItr> SolverEdges; |
| |
| public: |
| |
| /// \brief Iterator type for edges in the solver graph. |
| typedef SolverEdges::iterator SolverEdgeItr; |
| |
| private: |
| |
| class NodeData { |
| public: |
| NodeData() : solverDegree(0) {} |
| |
| HeuristicNodeData& getHeuristicData() { return hData; } |
| |
| SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) { |
| ++solverDegree; |
| return solverEdges.insert(solverEdges.end(), eItr); |
| } |
| |
| void removeSolverEdge(SolverEdgeItr seItr) { |
| --solverDegree; |
| solverEdges.erase(seItr); |
| } |
| |
| SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); } |
| SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); } |
| unsigned getSolverDegree() const { return solverDegree; } |
| void clearSolverEdges() { |
| solverDegree = 0; |
| solverEdges.clear(); |
| } |
| |
| private: |
| HeuristicNodeData hData; |
| unsigned solverDegree; |
| SolverEdges solverEdges; |
| }; |
| |
| class EdgeData { |
| public: |
| HeuristicEdgeData& getHeuristicData() { return hData; } |
| |
| void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) { |
| this->n1SolverEdgeItr = n1SolverEdgeItr; |
| } |
| |
| SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; } |
| |
| void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){ |
| this->n2SolverEdgeItr = n2SolverEdgeItr; |
| } |
| |
| SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; } |
| |
| private: |
| |
| HeuristicEdgeData hData; |
| SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr; |
| }; |
| |
| Graph &g; |
| HImpl h; |
| Solution s; |
| std::vector<Graph::NodeItr> stack; |
| |
| typedef std::list<NodeData> NodeDataList; |
| NodeDataList nodeDataList; |
| |
| typedef std::list<EdgeData> EdgeDataList; |
| EdgeDataList edgeDataList; |
| |
| public: |
| |
| /// \brief Construct a heuristic solver implementation to solve the given |
| /// graph. |
| /// @param g The graph representing the problem instance to be solved. |
| HeuristicSolverImpl(Graph &g) : g(g), h(*this) {} |
| |
| /// \brief Get the graph being solved by this solver. |
| /// @return The graph representing the problem instance being solved by this |
| /// solver. |
| Graph& getGraph() { return g; } |
| |
| /// \brief Get the heuristic data attached to the given node. |
| /// @param nItr Node iterator. |
| /// @return The heuristic data attached to the given node. |
| HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) { |
| return getSolverNodeData(nItr).getHeuristicData(); |
| } |
| |
| /// \brief Get the heuristic data attached to the given edge. |
| /// @param eItr Edge iterator. |
| /// @return The heuristic data attached to the given node. |
| HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { |
| return getSolverEdgeData(eItr).getHeuristicData(); |
| } |
| |
| /// \brief Begin iterator for the set of edges adjacent to the given node in |
| /// the solver graph. |
| /// @param nItr Node iterator. |
| /// @return Begin iterator for the set of edges adjacent to the given node |
| /// in the solver graph. |
| SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) { |
| return getSolverNodeData(nItr).solverEdgesBegin(); |
| } |
| |
| /// \brief End iterator for the set of edges adjacent to the given node in |
| /// the solver graph. |
| /// @param nItr Node iterator. |
| /// @return End iterator for the set of edges adjacent to the given node in |
| /// the solver graph. |
| SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) { |
| return getSolverNodeData(nItr).solverEdgesEnd(); |
| } |
| |
| /// \brief Remove a node from the solver graph. |
| /// @param eItr Edge iterator for edge to be removed. |
| /// |
| /// Does <i>not</i> notify the heuristic of the removal. That should be |
| /// done manually if necessary. |
| void removeSolverEdge(Graph::EdgeItr eItr) { |
| EdgeData &eData = getSolverEdgeData(eItr); |
| NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), |
| &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); |
| |
| n1Data.removeSolverEdge(eData.getN1SolverEdgeItr()); |
| n2Data.removeSolverEdge(eData.getN2SolverEdgeItr()); |
| } |
| |
| /// \brief Compute a solution to the PBQP problem instance with which this |
| /// heuristic solver was constructed. |
| /// @return A solution to the PBQP problem. |
| /// |
| /// Performs the full PBQP heuristic solver algorithm, including setup, |
| /// calls to the heuristic (which will call back to the reduction rules in |
| /// this class), and cleanup. |
| Solution computeSolution() { |
| setup(); |
| h.setup(); |
| h.reduce(); |
| backpropagate(); |
| h.cleanup(); |
| cleanup(); |
| return s; |
| } |
| |
| /// \brief Add to the end of the stack. |
| /// @param nItr Node iterator to add to the reduction stack. |
| void pushToStack(Graph::NodeItr nItr) { |
| getSolverNodeData(nItr).clearSolverEdges(); |
| stack.push_back(nItr); |
| } |
| |
| /// \brief Returns the solver degree of the given node. |
| /// @param nItr Node iterator for which degree is requested. |
| /// @return Node degree in the <i>solver</i> graph (not the original graph). |
| unsigned getSolverDegree(Graph::NodeItr nItr) { |
| return getSolverNodeData(nItr).getSolverDegree(); |
| } |
| |
| /// \brief Set the solution of the given node. |
| /// @param nItr Node iterator to set solution for. |
| /// @param selection Selection for node. |
| void setSolution(const Graph::NodeItr &nItr, unsigned selection) { |
| s.setSelection(nItr, selection); |
| |
| for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), |
| aeEnd = g.adjEdgesEnd(nItr); |
| aeItr != aeEnd; ++aeItr) { |
| Graph::EdgeItr eItr(*aeItr); |
| Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr)); |
| getSolverNodeData(anItr).addSolverEdge(eItr); |
| } |
| } |
| |
| /// \brief Apply rule R0. |
| /// @param nItr Node iterator for node to apply R0 to. |
| /// |
| /// Node will be automatically pushed to the solver stack. |
| void applyR0(Graph::NodeItr nItr) { |
| assert(getSolverNodeData(nItr).getSolverDegree() == 0 && |
| "R0 applied to node with degree != 0."); |
| |
| // Nothing to do. Just push the node onto the reduction stack. |
| pushToStack(nItr); |
| |
| s.recordR0(); |
| } |
| |
| /// \brief Apply rule R1. |
| /// @param xnItr Node iterator for node to apply R1 to. |
| /// |
| /// Node will be automatically pushed to the solver stack. |
| void applyR1(Graph::NodeItr xnItr) { |
| NodeData &nd = getSolverNodeData(xnItr); |
| assert(nd.getSolverDegree() == 1 && |
| "R1 applied to node with degree != 1."); |
| |
| Graph::EdgeItr eItr = *nd.solverEdgesBegin(); |
| |
| const Matrix &eCosts = g.getEdgeCosts(eItr); |
| const Vector &xCosts = g.getNodeCosts(xnItr); |
| |
| // Duplicate a little to avoid transposing matrices. |
| if (xnItr == g.getEdgeNode1(eItr)) { |
| Graph::NodeItr ynItr = g.getEdgeNode2(eItr); |
| Vector &yCosts = g.getNodeCosts(ynItr); |
| for (unsigned j = 0; j < yCosts.getLength(); ++j) { |
| PBQPNum min = eCosts[0][j] + xCosts[0]; |
| for (unsigned i = 1; i < xCosts.getLength(); ++i) { |
| PBQPNum c = eCosts[i][j] + xCosts[i]; |
| if (c < min) |
| min = c; |
| } |
| yCosts[j] += min; |
| } |
| h.handleRemoveEdge(eItr, ynItr); |
| } else { |
| Graph::NodeItr ynItr = g.getEdgeNode1(eItr); |
| Vector &yCosts = g.getNodeCosts(ynItr); |
| for (unsigned i = 0; i < yCosts.getLength(); ++i) { |
| PBQPNum min = eCosts[i][0] + xCosts[0]; |
| for (unsigned j = 1; j < xCosts.getLength(); ++j) { |
| PBQPNum c = eCosts[i][j] + xCosts[j]; |
| if (c < min) |
| min = c; |
| } |
| yCosts[i] += min; |
| } |
| h.handleRemoveEdge(eItr, ynItr); |
| } |
| removeSolverEdge(eItr); |
| assert(nd.getSolverDegree() == 0 && |
| "Degree 1 with edge removed should be 0."); |
| pushToStack(xnItr); |
| s.recordR1(); |
| } |
| |
| /// \brief Apply rule R2. |
| /// @param xnItr Node iterator for node to apply R2 to. |
| /// |
| /// Node will be automatically pushed to the solver stack. |
| void applyR2(Graph::NodeItr xnItr) { |
| assert(getSolverNodeData(xnItr).getSolverDegree() == 2 && |
| "R2 applied to node with degree != 2."); |
| |
| NodeData &nd = getSolverNodeData(xnItr); |
| const Vector &xCosts = g.getNodeCosts(xnItr); |
| |
| SolverEdgeItr aeItr = nd.solverEdgesBegin(); |
| Graph::EdgeItr yxeItr = *aeItr, |
| zxeItr = *(++aeItr); |
| |
| Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr), |
| znItr = g.getEdgeOtherNode(zxeItr, xnItr); |
| |
| bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr), |
| flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr); |
| |
| const Matrix *yxeCosts = flipEdge1 ? |
| new Matrix(g.getEdgeCosts(yxeItr).transpose()) : |
| &g.getEdgeCosts(yxeItr); |
| |
| const Matrix *zxeCosts = flipEdge2 ? |
| new Matrix(g.getEdgeCosts(zxeItr).transpose()) : |
| &g.getEdgeCosts(zxeItr); |
| |
| unsigned xLen = xCosts.getLength(), |
| yLen = yxeCosts->getRows(), |
| zLen = zxeCosts->getRows(); |
| |
| Matrix delta(yLen, zLen); |
| |
| for (unsigned i = 0; i < yLen; ++i) { |
| for (unsigned j = 0; j < zLen; ++j) { |
| PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0]; |
| for (unsigned k = 1; k < xLen; ++k) { |
| PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k]; |
| if (c < min) { |
| min = c; |
| } |
| } |
| delta[i][j] = min; |
| } |
| } |
| |
| if (flipEdge1) |
| delete yxeCosts; |
| |
| if (flipEdge2) |
| delete zxeCosts; |
| |
| Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr); |
| bool addedEdge = false; |
| |
| if (yzeItr == g.edgesEnd()) { |
| yzeItr = g.addEdge(ynItr, znItr, delta); |
| addedEdge = true; |
| } else { |
| Matrix &yzeCosts = g.getEdgeCosts(yzeItr); |
| h.preUpdateEdgeCosts(yzeItr); |
| if (ynItr == g.getEdgeNode1(yzeItr)) { |
| yzeCosts += delta; |
| } else { |
| yzeCosts += delta.transpose(); |
| } |
| } |
| |
| bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr); |
| |
| if (!addedEdge) { |
| // If we modified the edge costs let the heuristic know. |
| h.postUpdateEdgeCosts(yzeItr); |
| } |
| |
| if (nullCostEdge) { |
| // If this edge ended up null remove it. |
| if (!addedEdge) { |
| // We didn't just add it, so we need to notify the heuristic |
| // and remove it from the solver. |
| h.handleRemoveEdge(yzeItr, ynItr); |
| h.handleRemoveEdge(yzeItr, znItr); |
| removeSolverEdge(yzeItr); |
| } |
| g.removeEdge(yzeItr); |
| } else if (addedEdge) { |
| // If the edge was added, and non-null, finish setting it up, add it to |
| // the solver & notify heuristic. |
| edgeDataList.push_back(EdgeData()); |
| g.setEdgeData(yzeItr, &edgeDataList.back()); |
| addSolverEdge(yzeItr); |
| h.handleAddEdge(yzeItr); |
| } |
| |
| h.handleRemoveEdge(yxeItr, ynItr); |
| removeSolverEdge(yxeItr); |
| h.handleRemoveEdge(zxeItr, znItr); |
| removeSolverEdge(zxeItr); |
| |
| pushToStack(xnItr); |
| s.recordR2(); |
| } |
| |
| /// \brief Record an application of the RN rule. |
| /// |
| /// For use by the HeuristicBase. |
| void recordRN() { s.recordRN(); } |
| |
| private: |
| |
| NodeData& getSolverNodeData(Graph::NodeItr nItr) { |
| return *static_cast<NodeData*>(g.getNodeData(nItr)); |
| } |
| |
| EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) { |
| return *static_cast<EdgeData*>(g.getEdgeData(eItr)); |
| } |
| |
| void addSolverEdge(Graph::EdgeItr eItr) { |
| EdgeData &eData = getSolverEdgeData(eItr); |
| NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), |
| &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); |
| |
| eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr)); |
| eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr)); |
| } |
| |
| void setup() { |
| if (h.solverRunSimplify()) { |
| simplify(); |
| } |
| |
| // Create node data objects. |
| for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); |
| nItr != nEnd; ++nItr) { |
| nodeDataList.push_back(NodeData()); |
| g.setNodeData(nItr, &nodeDataList.back()); |
| } |
| |
| // Create edge data objects. |
| for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); |
| eItr != eEnd; ++eItr) { |
| edgeDataList.push_back(EdgeData()); |
| g.setEdgeData(eItr, &edgeDataList.back()); |
| addSolverEdge(eItr); |
| } |
| } |
| |
| void simplify() { |
| disconnectTrivialNodes(); |
| eliminateIndependentEdges(); |
| } |
| |
| // Eliminate trivial nodes. |
| void disconnectTrivialNodes() { |
| unsigned numDisconnected = 0; |
| |
| for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); |
| nItr != nEnd; ++nItr) { |
| |
| if (g.getNodeCosts(nItr).getLength() == 1) { |
| |
| std::vector<Graph::EdgeItr> edgesToRemove; |
| |
| for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), |
| aeEnd = g.adjEdgesEnd(nItr); |
| aeItr != aeEnd; ++aeItr) { |
| |
| Graph::EdgeItr eItr = *aeItr; |
| |
| if (g.getEdgeNode1(eItr) == nItr) { |
| Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr); |
| g.getNodeCosts(otherNodeItr) += |
| g.getEdgeCosts(eItr).getRowAsVector(0); |
| } |
| else { |
| Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr); |
| g.getNodeCosts(otherNodeItr) += |
| g.getEdgeCosts(eItr).getColAsVector(0); |
| } |
| |
| edgesToRemove.push_back(eItr); |
| } |
| |
| if (!edgesToRemove.empty()) |
| ++numDisconnected; |
| |
| while (!edgesToRemove.empty()) { |
| g.removeEdge(edgesToRemove.back()); |
| edgesToRemove.pop_back(); |
| } |
| } |
| } |
| } |
| |
| void eliminateIndependentEdges() { |
| std::vector<Graph::EdgeItr> edgesToProcess; |
| unsigned numEliminated = 0; |
| |
| for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); |
| eItr != eEnd; ++eItr) { |
| edgesToProcess.push_back(eItr); |
| } |
| |
| while (!edgesToProcess.empty()) { |
| if (tryToEliminateEdge(edgesToProcess.back())) |
| ++numEliminated; |
| edgesToProcess.pop_back(); |
| } |
| } |
| |
| bool tryToEliminateEdge(Graph::EdgeItr eItr) { |
| if (tryNormaliseEdgeMatrix(eItr)) { |
| g.removeEdge(eItr); |
| return true; |
| } |
| return false; |
| } |
| |
| bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) { |
| |
| const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity(); |
| |
| Matrix &edgeCosts = g.getEdgeCosts(eItr); |
| Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)), |
| &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr)); |
| |
| for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { |
| PBQPNum rowMin = infinity; |
| |
| for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { |
| if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin) |
| rowMin = edgeCosts[r][c]; |
| } |
| |
| uCosts[r] += rowMin; |
| |
| if (rowMin != infinity) { |
| edgeCosts.subFromRow(r, rowMin); |
| } |
| else { |
| edgeCosts.setRow(r, 0); |
| } |
| } |
| |
| for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { |
| PBQPNum colMin = infinity; |
| |
| for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { |
| if (uCosts[r] != infinity && edgeCosts[r][c] < colMin) |
| colMin = edgeCosts[r][c]; |
| } |
| |
| vCosts[c] += colMin; |
| |
| if (colMin != infinity) { |
| edgeCosts.subFromCol(c, colMin); |
| } |
| else { |
| edgeCosts.setCol(c, 0); |
| } |
| } |
| |
| return edgeCosts.isZero(); |
| } |
| |
| void backpropagate() { |
| while (!stack.empty()) { |
| computeSolution(stack.back()); |
| stack.pop_back(); |
| } |
| } |
| |
| void computeSolution(Graph::NodeItr nItr) { |
| |
| NodeData &nodeData = getSolverNodeData(nItr); |
| |
| Vector v(g.getNodeCosts(nItr)); |
| |
| // Solve based on existing solved edges. |
| for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(), |
| solvedEdgeEnd = nodeData.solverEdgesEnd(); |
| solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) { |
| |
| Graph::EdgeItr eItr(*solvedEdgeItr); |
| Matrix &edgeCosts = g.getEdgeCosts(eItr); |
| |
| if (nItr == g.getEdgeNode1(eItr)) { |
| Graph::NodeItr adjNode(g.getEdgeNode2(eItr)); |
| unsigned adjSolution = s.getSelection(adjNode); |
| v += edgeCosts.getColAsVector(adjSolution); |
| } |
| else { |
| Graph::NodeItr adjNode(g.getEdgeNode1(eItr)); |
| unsigned adjSolution = s.getSelection(adjNode); |
| v += edgeCosts.getRowAsVector(adjSolution); |
| } |
| |
| } |
| |
| setSolution(nItr, v.minIndex()); |
| } |
| |
| void cleanup() { |
| h.cleanup(); |
| nodeDataList.clear(); |
| edgeDataList.clear(); |
| } |
| }; |
| |
| /// \brief PBQP heuristic solver class. |
| /// |
| /// Given a PBQP Graph g representing a PBQP problem, you can find a solution |
| /// by calling |
| /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt> |
| /// |
| /// The choice of heuristic for the H parameter will affect both the solver |
| /// speed and solution quality. The heuristic should be chosen based on the |
| /// nature of the problem being solved. |
| /// Currently the only solver included with LLVM is the Briggs heuristic for |
| /// register allocation. |
| template <typename HImpl> |
| class HeuristicSolver { |
| public: |
| static Solution solve(Graph &g) { |
| HeuristicSolverImpl<HImpl> hs(g); |
| return hs.computeSolution(); |
| } |
| }; |
| |
| } |
| |
| #endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H |