diff options
Diffstat (limited to 'include/llvm/CodeGen/PBQP/HeuristicSolver.h')
| -rw-r--r-- | include/llvm/CodeGen/PBQP/HeuristicSolver.h | 618 |
1 files changed, 618 insertions, 0 deletions
diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h new file mode 100644 index 0000000000..e26ca02fff --- /dev/null +++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h @@ -0,0 +1,618 @@ +//===-- 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 <limits> +#include <vector> + +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::EdgeId> 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::EdgeId eId) { + ++solverDegree; + return solverEdges.insert(solverEdges.end(), eId); + } + + 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::NodeId> 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 nId Node id. + /// @return The heuristic data attached to the given node. + HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolverNodeData(nId).getHeuristicData(); + } + + /// \brief Get the heuristic data attached to the given edge. + /// @param eId Edge id. + /// @return The heuristic data attached to the given node. + HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolverEdgeData(eId).getHeuristicData(); + } + + /// \brief Begin iterator for the set of edges adjacent to the given node in + /// the solver graph. + /// @param nId Node id. + /// @return Begin iterator for the set of edges adjacent to the given node + /// in the solver graph. + SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesBegin(); + } + + /// \brief End iterator for the set of edges adjacent to the given node in + /// the solver graph. + /// @param nId Node id. + /// @return End iterator for the set of edges adjacent to the given node in + /// the solver graph. + SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesEnd(); + } + + /// \brief Remove a node from the solver graph. + /// @param eId Edge id 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::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); + + 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 nId Node id to add to the reduction stack. + void pushToStack(Graph::NodeId nId) { + getSolverNodeData(nId).clearSolverEdges(); + stack.push_back(nId); + } + + /// \brief Returns the solver degree of the given node. + /// @param nId Node id for which degree is requested. + /// @return Node degree in the <i>solver</i> graph (not the original graph). + unsigned getSolverDegree(Graph::NodeId nId) { + return getSolverNodeData(nId).getSolverDegree(); + } + + /// \brief Set the solution of the given node. + /// @param nId Node id to set solution for. + /// @param selection Selection for node. + void setSolution(const Graph::NodeId &nId, unsigned selection) { + s.setSelection(nId, selection); + + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); + aeItr != aeEnd; ++aeItr) { + Graph::EdgeId eId(*aeItr); + Graph::NodeId anId(g.getEdgeOtherNode(eId, nId)); + getSolverNodeData(anId).addSolverEdge(eId); + } + } + + /// \brief Apply rule R0. + /// @param nId Node id for node to apply R0 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR0(Graph::NodeId nId) { + assert(getSolverNodeData(nId).getSolverDegree() == 0 && + "R0 applied to node with degree != 0."); + + // Nothing to do. Just push the node onto the reduction stack. + pushToStack(nId); + + s.recordR0(); + } + + /// \brief Apply rule R1. + /// @param xnId Node id for node to apply R1 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR1(Graph::NodeId xnId) { + NodeData &nd = getSolverNodeData(xnId); + assert(nd.getSolverDegree() == 1 && + "R1 applied to node with degree != 1."); + + Graph::EdgeId eId = *nd.solverEdgesBegin(); + + const Matrix &eCosts = g.getEdgeCosts(eId); + const Vector &xCosts = g.getNodeCosts(xnId); + + // Duplicate a little to avoid transposing matrices. + if (xnId == g.getEdgeNode1(eId)) { + Graph::NodeId ynId = g.getEdgeNode2(eId); + Vector &yCosts = g.getNodeCosts(ynId); + 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(eId, ynId); + } else { + Graph::NodeId ynId = g.getEdgeNode1(eId); + Vector &yCosts = g.getNodeCosts(ynId); + 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(eId, ynId); + } + removeSolverEdge(eId); + assert(nd.getSolverDegree() == 0 && + "Degree 1 with edge removed should be 0."); + pushToStack(xnId); + s.recordR1(); + } + + /// \brief Apply rule R2. + /// @param xnId Node id for node to apply R2 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR2(Graph::NodeId xnId) { + assert(getSolverNodeData(xnId).getSolverDegree() == 2 && + "R2 applied to node with degree != 2."); + + NodeData &nd = getSolverNodeData(xnId); + const Vector &xCosts = g.getNodeCosts(xnId); + + SolverEdgeItr aeItr = nd.solverEdgesBegin(); + Graph::EdgeId yxeId = *aeItr, + zxeId = *(++aeItr); + + Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId), + znId = g.getEdgeOtherNode(zxeId, xnId); + + bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId), + flipEdge2 = (g.getEdgeNode1(zxeId) == xnId); + + const Matrix *yxeCosts = flipEdge1 ? + new Matrix(g.getEdgeCosts(yxeId).transpose()) : + &g.getEdgeCosts(yxeId); + + const Matrix *zxeCosts = flipEdge2 ? + new Matrix(g.getEdgeCosts(zxeId).transpose()) : + &g.getEdgeCosts(zxeId); + + 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::EdgeId yzeId = g.findEdge(ynId, znId); + bool addedEdge = false; + + if (yzeId == g.invalidEdgeId()) { + yzeId = g.addEdge(ynId, znId, delta); + addedEdge = true; + } else { + Matrix &yzeCosts = g.getEdgeCosts(yzeId); + h.preUpdateEdgeCosts(yzeId); + if (ynId == g.getEdgeNode1(yzeId)) { + yzeCosts += delta; + } else { + yzeCosts += delta.transpose(); + } + } + + bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId); + + if (!addedEdge) { + // If we modified the edge costs let the heuristic know. + h.postUpdateEdgeCosts(yzeId); + } + + 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(yzeId, ynId); + h.handleRemoveEdge(yzeId, znId); + removeSolverEdge(yzeId); + } + g.removeEdge(yzeId); + } 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(yzeId, &edgeDataList.back()); + addSolverEdge(yzeId); + h.handleAddEdge(yzeId); + } + + h.handleRemoveEdge(yxeId, ynId); + removeSolverEdge(yxeId); + h.handleRemoveEdge(zxeId, znId); + removeSolverEdge(zxeId); + + pushToStack(xnId); + s.recordR2(); + } + + /// \brief Record an application of the RN rule. + /// + /// For use by the HeuristicBase. + void recordRN() { s.recordRN(); } + + private: + + NodeData& getSolverNodeData(Graph::NodeId nId) { + return *static_cast<NodeData*>(g.getNodeData(nId)); + } + + EdgeData& getSolverEdgeData(Graph::EdgeId eId) { + return *static_cast<EdgeData*>(g.getEdgeData(eId)); + } + + void addSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); + + eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId)); + eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId)); + } + + 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) { + + Graph::NodeId nId = *nItr; + + if (g.getNodeCosts(nId).getLength() == 1) { + + std::vector<Graph::EdgeId> edgesToRemove; + + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); + aeItr != aeEnd; ++aeItr) { + + Graph::EdgeId eId = *aeItr; + + if (g.getEdgeNode1(eId) == nId) { + Graph::NodeId otherNodeId = g.getEdgeNode2(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getRowAsVector(0); + } + else { + Graph::NodeId otherNodeId = g.getEdgeNode1(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getColAsVector(0); + } + + edgesToRemove.push_back(eId); + } + + if (!edgesToRemove.empty()) + ++numDisconnected; + + while (!edgesToRemove.empty()) { + g.removeEdge(edgesToRemove.back()); + edgesToRemove.pop_back(); + } + } + } + } + + void eliminateIndependentEdges() { + std::vector<Graph::EdgeId> 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::EdgeId eId) { + if (tryNormaliseEdgeMatrix(eId)) { + g.removeEdge(eId); + return true; + } + return false; + } + + bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) { + + const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity(); + + Matrix &edgeCosts = g.getEdgeCosts(eId); + Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)), + &vCosts = g.getNodeCosts(g.getEdgeNode2(eId)); + + 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::NodeId nId) { + + NodeData &nodeData = getSolverNodeData(nId); + + Vector v(g.getNodeCosts(nId)); + + // Solve based on existing solved edges. + for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(), + solvedEdgeEnd = nodeData.solverEdgesEnd(); + solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) { + + Graph::EdgeId eId(*solvedEdgeItr); + Matrix &edgeCosts = g.getEdgeCosts(eId); + + if (nId == g.getEdgeNode1(eId)) { + Graph::NodeId adjNode(g.getEdgeNode2(eId)); + unsigned adjSolution = s.getSelection(adjNode); + v += edgeCosts.getColAsVector(adjSolution); + } + else { + Graph::NodeId adjNode(g.getEdgeNode1(eId)); + unsigned adjSolution = s.getSelection(adjNode); + v += edgeCosts.getRowAsVector(adjSolution); + } + + } + + setSolution(nId, 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 |