lib/CodeGen/PBQP/HeuristicBase.h

   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: assert(false &&
 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             finished = true;
 179       }
 180     }
 181
 182     /// \brief Add a node to the heuristic reduce list.
 183     /// @param nItr Node iterator to add to the heuristic reduce list.
 184     void addToHeuristicList(Graph::NodeItr nItr) {
 185       assert(false && "Must be implemented in derived class.");
 186     }
 187
 188     /// \brief Heuristically reduce one of the nodes in the heuristic
 189     ///        reduce list.
 190     /// @return True if a reduction takes place, false if the heuristic reduce
 191     ///         list is empty.
 192     void heuristicReduce() {
 193       assert(false && "Must be implemented in derived class.");
 194     }
 195
 196     /// \brief Prepare a change in the costs on the given edge.
 197     /// @param eItr Edge iterator.
 198     void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
 199       assert(false && "Must be implemented in derived class.");
 200     }
 201
 202     /// \brief Handle the change in the costs on the given edge.
 203     /// @param eItr Edge iterator.
 204     void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
 205       assert(false && "Must be implemented in derived class.");
 206     }
 207
 208     /// \brief Handle the addition of a new edge into the PBQP graph.
 209     /// @param eItr Edge iterator for the added edge.
 210     void handleAddEdge(Graph::EdgeItr eItr) {
 211       assert(false && "Must be implemented in derived class.");
 212     }
 213
 214     /// \brief Handle disconnection of an edge from a node.
 215     /// @param eItr Edge iterator for edge being disconnected.
 216     /// @param nItr Node iterator for the node being disconnected from.
 217     ///
 218     /// Edges are frequently removed due to the removal of a node. This
 219     /// method allows for the effect to be computed only for the remaining
 220     /// node in the graph.
 221     void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
 222       assert(false && "Must be implemented in derived class.");
 223     }
 224
 225     /// \brief Clean up any structures used by HeuristicBase.
 226     ///
 227     /// At present this just performs a sanity check: that the optimal reduce
 228     /// list is empty now that reduction has completed.
 229     ///
 230     /// If your derived class has more complex structures which need tearing
 231     /// down you should over-ride this method but include a call back to this
 232     /// implementation.
 233     void cleanup() {
 234       assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
 235     }
 236
 237   };
 238
 239 }
 240
 241
 242 #endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H