Home | History | Annotate | Download | only in PBQP
      1 //===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 
     10 #ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H
     11 #define LLVM_CODEGEN_PBQP_HEURISTICBASE_H
     12 
     13 #include "HeuristicSolver.h"
     14 
     15 namespace PBQP {
     16 
     17   /// \brief Abstract base class for heuristic implementations.
     18   ///
     19   /// This class provides a handy base for heuristic implementations with common
     20   /// solver behaviour implemented for a number of methods.
     21   ///
     22   /// To implement your own heuristic using this class as a base you'll have to
     23   /// implement, as a minimum, the following methods:
     24   /// <ul>
     25   ///   <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the
     26   ///        heuristic reduction list.
     27   ///   <li> void heuristicReduce() : Perform a single heuristic reduction.
     28   ///   <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent)
     29   ///        change to the cost matrix on the given edge (by R2).
     30   ///   <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new
     31   ///        costs on the given edge.
     32   ///   <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new
     33   ///        edge into the PBQP graph (by R2).
     34   ///   <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the
     35   ///        disconnection of the given edge from the given node.
     36   ///   <li> A constructor for your derived class : to pass back a reference to
     37   ///        the solver which is using this heuristic.
     38   /// </ul>
     39   ///
     40   /// These methods are implemented in this class for documentation purposes,
     41   /// but will assert if called.
     42   ///
     43   /// Note that this class uses the curiously recursive template idiom to
     44   /// forward calls to the derived class. These methods need not be made
     45   /// virtual, and indeed probably shouldn't for performance reasons.
     46   ///
     47   /// You'll also need to provide NodeData and EdgeData structs in your class.
     48   /// These can be used to attach data relevant to your heuristic to each
     49   /// node/edge in the PBQP graph.
     50 
     51   template <typename HImpl>
     52   class HeuristicBase {
     53   private:
     54 
     55     typedef std::list<Graph::NodeItr> OptimalList;
     56 
     57     HeuristicSolverImpl<HImpl> &s;
     58     Graph &g;
     59     OptimalList optimalList;
     60 
     61     // Return a reference to the derived heuristic.
     62     HImpl& impl() { return static_cast<HImpl&>(*this); }
     63 
     64     // Add the given node to the optimal reductions list. Keep an iterator to
     65     // its location for fast removal.
     66     void addToOptimalReductionList(Graph::NodeItr nItr) {
     67       optimalList.insert(optimalList.end(), nItr);
     68     }
     69 
     70   public:
     71 
     72     /// \brief Construct an instance with a reference to the given solver.
     73     /// @param solver The solver which is using this heuristic instance.
     74     HeuristicBase(HeuristicSolverImpl<HImpl> &solver)
     75       : s(solver), g(s.getGraph()) { }
     76 
     77     /// \brief Get the solver which is using this heuristic instance.
     78     /// @return The solver which is using this heuristic instance.
     79     ///
     80     /// You can use this method to get access to the solver in your derived
     81     /// heuristic implementation.
     82     HeuristicSolverImpl<HImpl>& getSolver() { return s; }
     83 
     84     /// \brief Get the graph representing the problem to be solved.
     85     /// @return The graph representing the problem to be solved.
     86     Graph& getGraph() { return g; }
     87 
     88     /// \brief Tell the solver to simplify the graph before the reduction phase.
     89     /// @return Whether or not the solver should run a simplification phase
     90     ///         prior to the main setup and reduction.
     91     ///
     92     /// HeuristicBase returns true from this method as it's a sensible default,
     93     /// however you can over-ride it in your derived class if you want different
     94     /// behaviour.
     95     bool solverRunSimplify() const { return true; }
     96 
     97     /// \brief Decide whether a node should be optimally or heuristically
     98     ///        reduced.
     99     /// @return Whether or not the given node should be listed for optimal
    100     ///         reduction (via R0, R1 or R2).
    101     ///
    102     /// HeuristicBase returns true for any node with degree less than 3. This is
    103     /// sane and sensible for many situations, but not all. You can over-ride
    104     /// this method in your derived class if you want a different selection
    105     /// criteria. Note however that your criteria for selecting optimal nodes
    106     /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
    107     /// higher should not be selected under any circumstances.
    108     bool shouldOptimallyReduce(Graph::NodeItr nItr) {
    109       if (g.getNodeDegree(nItr) < 3)
    110         return true;
    111       // else
    112       return false;
    113     }
    114 
    115     /// \brief Add the given node to the list of nodes to be optimally reduced.
    116     /// @return nItr Node iterator to be added.
    117     ///
    118     /// You probably don't want to over-ride this, except perhaps to record
    119     /// statistics before calling this implementation. HeuristicBase relies on
    120     /// its behaviour.
    121     void addToOptimalReduceList(Graph::NodeItr nItr) {
    122       optimalList.push_back(nItr);
    123     }
    124 
    125     /// \brief Initialise the heuristic.
    126     ///
    127     /// HeuristicBase iterates over all nodes in the problem and adds them to
    128     /// the appropriate list using addToOptimalReduceList or
    129     /// addToHeuristicReduceList based on the result of shouldOptimallyReduce.
    130     ///
    131     /// This behaviour should be fine for most situations.
    132     void setup() {
    133       for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
    134            nItr != nEnd; ++nItr) {
    135         if (impl().shouldOptimallyReduce(nItr)) {
    136           addToOptimalReduceList(nItr);
    137         } else {
    138           impl().addToHeuristicReduceList(nItr);
    139         }
    140       }
    141     }
    142 
    143     /// \brief Optimally reduce one of the nodes in the optimal reduce list.
    144     /// @return True if a reduction takes place, false if the optimal reduce
    145     ///         list is empty.
    146     ///
    147     /// Selects a node from the optimal reduce list and removes it, applying
    148     /// R0, R1 or R2 as appropriate based on the selected node's degree.
    149     bool optimalReduce() {
    150       if (optimalList.empty())
    151         return false;
    152 
    153       Graph::NodeItr nItr = optimalList.front();
    154       optimalList.pop_front();
    155 
    156       switch (s.getSolverDegree(nItr)) {
    157         case 0: s.applyR0(nItr); break;
    158         case 1: s.applyR1(nItr); break;
    159         case 2: s.applyR2(nItr); break;
    160         default: llvm_unreachable(
    161                         "Optimal reductions of degree > 2 nodes is invalid.");
    162       }
    163 
    164       return true;
    165     }
    166 
    167     /// \brief Perform the PBQP reduction process.
    168     ///
    169     /// Reduces the problem to the empty graph by repeated application of the
    170     /// reduction rules R0, R1, R2 and RN.
    171     /// R0, R1 or R2 are always applied if possible before RN is used.
    172     void reduce() {
    173       bool finished = false;
    174 
    175       while (!finished) {
    176         if (!optimalReduce()) {
    177           if (impl().heuristicReduce()) {
    178             getSolver().recordRN();
    179           } else {
    180             finished = true;
    181           }
    182         }
    183       }
    184     }
    185 
    186     /// \brief Add a node to the heuristic reduce list.
    187     /// @param nItr Node iterator to add to the heuristic reduce list.
    188     void addToHeuristicList(Graph::NodeItr nItr) {
    189       llvm_unreachable("Must be implemented in derived class.");
    190     }
    191 
    192     /// \brief Heuristically reduce one of the nodes in the heuristic
    193     ///        reduce list.
    194     /// @return True if a reduction takes place, false if the heuristic reduce
    195     ///         list is empty.
    196     void heuristicReduce() {
    197       llvm_unreachable("Must be implemented in derived class.");
    198     }
    199 
    200     /// \brief Prepare a change in the costs on the given edge.
    201     /// @param eItr Edge iterator.
    202     void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
    203       llvm_unreachable("Must be implemented in derived class.");
    204     }
    205 
    206     /// \brief Handle the change in the costs on the given edge.
    207     /// @param eItr Edge iterator.
    208     void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
    209       llvm_unreachable("Must be implemented in derived class.");
    210     }
    211 
    212     /// \brief Handle the addition of a new edge into the PBQP graph.
    213     /// @param eItr Edge iterator for the added edge.
    214     void handleAddEdge(Graph::EdgeItr eItr) {
    215       llvm_unreachable("Must be implemented in derived class.");
    216     }
    217 
    218     /// \brief Handle disconnection of an edge from a node.
    219     /// @param eItr Edge iterator for edge being disconnected.
    220     /// @param nItr Node iterator for the node being disconnected from.
    221     ///
    222     /// Edges are frequently removed due to the removal of a node. This
    223     /// method allows for the effect to be computed only for the remaining
    224     /// node in the graph.
    225     void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
    226       llvm_unreachable("Must be implemented in derived class.");
    227     }
    228 
    229     /// \brief Clean up any structures used by HeuristicBase.
    230     ///
    231     /// At present this just performs a sanity check: that the optimal reduce
    232     /// list is empty now that reduction has completed.
    233     ///
    234     /// If your derived class has more complex structures which need tearing
    235     /// down you should over-ride this method but include a call back to this
    236     /// implementation.
    237     void cleanup() {
    238       assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
    239     }
    240 
    241   };
    242 
    243 }
    244 
    245 
    246 #endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H
    247