//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H #define LLVM_CODEGEN_PBQP_HEURISTICBASE_H #include "HeuristicSolver.h" namespace PBQP { /// \brief Abstract base class for heuristic implementations. /// /// This class provides a handy base for heuristic implementations with common /// solver behaviour implemented for a number of methods. /// /// To implement your own heuristic using this class as a base you'll have to /// implement, as a minimum, the following methods: /// <ul> /// <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the /// heuristic reduction list. /// <li> void heuristicReduce() : Perform a single heuristic reduction. /// <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent) /// change to the cost matrix on the given edge (by R2). /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new /// costs on the given edge. /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new /// edge into the PBQP graph (by R2). /// <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the /// disconnection of the given edge from the given node. /// <li> A constructor for your derived class : to pass back a reference to /// the solver which is using this heuristic. /// </ul> /// /// These methods are implemented in this class for documentation purposes, /// but will assert if called. /// /// Note that this class uses the curiously recursive template idiom to /// forward calls to the derived class. These methods need not be made /// virtual, and indeed probably shouldn't for performance reasons. /// /// You'll also need to provide NodeData and EdgeData structs in your class. /// These can be used to attach data relevant to your heuristic to each /// node/edge in the PBQP graph. template <typename HImpl> class HeuristicBase { private: typedef std::list<Graph::NodeId> OptimalList; HeuristicSolverImpl<HImpl> &s; Graph &g; OptimalList optimalList; // Return a reference to the derived heuristic. HImpl& impl() { return static_cast<HImpl&>(*this); } // Add the given node to the optimal reductions list. Keep an iterator to // its location for fast removal. void addToOptimalReductionList(Graph::NodeId nId) { optimalList.insert(optimalList.end(), nId); } public: /// \brief Construct an instance with a reference to the given solver. /// @param solver The solver which is using this heuristic instance. HeuristicBase(HeuristicSolverImpl<HImpl> &solver) : s(solver), g(s.getGraph()) { } /// \brief Get the solver which is using this heuristic instance. /// @return The solver which is using this heuristic instance. /// /// You can use this method to get access to the solver in your derived /// heuristic implementation. HeuristicSolverImpl<HImpl>& getSolver() { return s; } /// \brief Get the graph representing the problem to be solved. /// @return The graph representing the problem to be solved. Graph& getGraph() { return g; } /// \brief Tell the solver to simplify the graph before the reduction phase. /// @return Whether or not the solver should run a simplification phase /// prior to the main setup and reduction. /// /// HeuristicBase returns true from this method as it's a sensible default, /// however you can over-ride it in your derived class if you want different /// behaviour. bool solverRunSimplify() const { return true; } /// \brief Decide whether a node should be optimally or heuristically /// reduced. /// @return Whether or not the given node should be listed for optimal /// reduction (via R0, R1 or R2). /// /// HeuristicBase returns true for any node with degree less than 3. This is /// sane and sensible for many situations, but not all. You can over-ride /// this method in your derived class if you want a different selection /// criteria. Note however that your criteria for selecting optimal nodes /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or /// higher should not be selected under any circumstances. bool shouldOptimallyReduce(Graph::NodeId nId) { if (g.getNodeDegree(nId) < 3) return true; // else return false; } /// \brief Add the given node to the list of nodes to be optimally reduced. /// @param nId Node id to be added. /// /// You probably don't want to over-ride this, except perhaps to record /// statistics before calling this implementation. HeuristicBase relies on /// its behaviour. void addToOptimalReduceList(Graph::NodeId nId) { optimalList.push_back(nId); } /// \brief Initialise the heuristic. /// /// HeuristicBase iterates over all nodes in the problem and adds them to /// the appropriate list using addToOptimalReduceList or /// addToHeuristicReduceList based on the result of shouldOptimallyReduce. /// /// This behaviour should be fine for most situations. void setup() { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { if (impl().shouldOptimallyReduce(*nItr)) { addToOptimalReduceList(*nItr); } else { impl().addToHeuristicReduceList(*nItr); } } } /// \brief Optimally reduce one of the nodes in the optimal reduce list. /// @return True if a reduction takes place, false if the optimal reduce /// list is empty. /// /// Selects a node from the optimal reduce list and removes it, applying /// R0, R1 or R2 as appropriate based on the selected node's degree. bool optimalReduce() { if (optimalList.empty()) return false; Graph::NodeId nId = optimalList.front(); optimalList.pop_front(); switch (s.getSolverDegree(nId)) { case 0: s.applyR0(nId); break; case 1: s.applyR1(nId); break; case 2: s.applyR2(nId); break; default: llvm_unreachable( "Optimal reductions of degree > 2 nodes is invalid."); } return true; } /// \brief Perform the PBQP reduction process. /// /// Reduces the problem to the empty graph by repeated application of the /// reduction rules R0, R1, R2 and RN. /// R0, R1 or R2 are always applied if possible before RN is used. void reduce() { bool finished = false; while (!finished) { if (!optimalReduce()) { if (impl().heuristicReduce()) { getSolver().recordRN(); } else { finished = true; } } } } /// \brief Add a node to the heuristic reduce list. /// @param nId Node id to add to the heuristic reduce list. void addToHeuristicList(Graph::NodeId nId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Heuristically reduce one of the nodes in the heuristic /// reduce list. /// @return True if a reduction takes place, false if the heuristic reduce /// list is empty. bool heuristicReduce() { llvm_unreachable("Must be implemented in derived class."); return false; } /// \brief Prepare a change in the costs on the given edge. /// @param eId Edge id. void preUpdateEdgeCosts(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle the change in the costs on the given edge. /// @param eId Edge id. void postUpdateEdgeCostts(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle the addition of a new edge into the PBQP graph. /// @param eId Edge id for the added edge. void handleAddEdge(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle disconnection of an edge from a node. /// @param eId Edge id for edge being disconnected. /// @param nId Node id for the node being disconnected from. /// /// Edges are frequently removed due to the removal of a node. This /// method allows for the effect to be computed only for the remaining /// node in the graph. void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Clean up any structures used by HeuristicBase. /// /// At present this just performs a sanity check: that the optimal reduce /// list is empty now that reduction has completed. /// /// If your derived class has more complex structures which need tearing /// down you should over-ride this method but include a call back to this /// implementation. void cleanup() { assert(optimalList.empty() && "Nodes left over in optimal reduce list?"); } }; } #endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H