text: //===-- 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
  