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
15namespace 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::NodeId> 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::NodeId nId) {
67      optimalList.insert(optimalList.end(), nId);
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::NodeId nId) {
109      if (g.getNodeDegree(nId) < 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    /// @param nId Node id 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::NodeId nId) {
122      optimalList.push_back(nId);
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::NodeId nId = optimalList.front();
154      optimalList.pop_front();
155
156      switch (s.getSolverDegree(nId)) {
157        case 0: s.applyR0(nId); break;
158        case 1: s.applyR1(nId); break;
159        case 2: s.applyR2(nId); 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 nId Node id to add to the heuristic reduce list.
188    void addToHeuristicList(Graph::NodeId nId) {
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    bool heuristicReduce() {
197      llvm_unreachable("Must be implemented in derived class.");
198      return false;
199    }
200
201    /// \brief Prepare a change in the costs on the given edge.
202    /// @param eId Edge id.
203    void preUpdateEdgeCosts(Graph::EdgeId eId) {
204      llvm_unreachable("Must be implemented in derived class.");
205    }
206
207    /// \brief Handle the change in the costs on the given edge.
208    /// @param eId Edge id.
209    void postUpdateEdgeCostts(Graph::EdgeId eId) {
210      llvm_unreachable("Must be implemented in derived class.");
211    }
212
213    /// \brief Handle the addition of a new edge into the PBQP graph.
214    /// @param eId Edge id for the added edge.
215    void handleAddEdge(Graph::EdgeId eId) {
216      llvm_unreachable("Must be implemented in derived class.");
217    }
218
219    /// \brief Handle disconnection of an edge from a node.
220    /// @param eId Edge id for edge being disconnected.
221    /// @param nId Node id for the node being disconnected from.
222    ///
223    /// Edges are frequently removed due to the removal of a node. This
224    /// method allows for the effect to be computed only for the remaining
225    /// node in the graph.
226    void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
227      llvm_unreachable("Must be implemented in derived class.");
228    }
229
230    /// \brief Clean up any structures used by HeuristicBase.
231    ///
232    /// At present this just performs a sanity check: that the optimal reduce
233    /// list is empty now that reduction has completed.
234    ///
235    /// If your derived class has more complex structures which need tearing
236    /// down you should over-ride this method but include a call back to this
237    /// implementation.
238    void cleanup() {
239      assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
240    }
241
242  };
243
244}
245
246
247#endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H
248