1 //===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H
11 #define LLVM_CODEGEN_PBQP_HEURISTICBASE_H
13 #include "HeuristicSolver.h"
17 /// \brief Abstract base class for heuristic implementations.
19 /// This class provides a handy base for heuristic implementations with common
20 /// solver behaviour implemented for a number of methods.
22 /// To implement your own heuristic using this class as a base you'll have to
23 /// implement, as a minimum, the following methods:
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.
40 /// These methods are implemented in this class for documentation purposes,
41 /// but will assert if called.
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.
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.
51 template <typename HImpl>
55 typedef std::list<Graph::NodeItr> OptimalList;
57 HeuristicSolverImpl<HImpl> &s;
59 OptimalList optimalList;
61 // Return a reference to the derived heuristic.
62 HImpl& impl() { return static_cast<HImpl&>(*this); }
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);
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()) { }
77 /// \brief Get the solver which is using this heuristic instance.
78 /// @return The solver which is using this heuristic instance.
80 /// You can use this method to get access to the solver in your derived
81 /// heuristic implementation.
82 HeuristicSolverImpl<HImpl>& getSolver() { return s; }
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; }
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.
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
95 bool solverRunSimplify() const { return true; }
97 /// \brief Decide whether a node should be optimally or heuristically
99 /// @return Whether or not the given node should be listed for optimal
100 /// reduction (via R0, R1 or R2).
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)
115 /// \brief Add the given node to the list of nodes to be optimally reduced.
116 /// @return nItr Node iterator to be added.
118 /// You probably don't want to over-ride this, except perhaps to record
119 /// statistics before calling this implementation. HeuristicBase relies on
121 void addToOptimalReduceList(Graph::NodeItr nItr) {
122 optimalList.push_back(nItr);
125 /// \brief Initialise the heuristic.
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.
131 /// This behaviour should be fine for most situations.
133 for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
134 nItr != nEnd; ++nItr) {
135 if (impl().shouldOptimallyReduce(nItr)) {
136 addToOptimalReduceList(nItr);
138 impl().addToHeuristicReduceList(nItr);
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
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())
153 Graph::NodeItr nItr = optimalList.front();
154 optimalList.pop_front();
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.");
167 /// \brief Perform the PBQP reduction process.
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.
173 bool finished = false;
176 if (!optimalReduce())
177 if (!impl().heuristicReduce())
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.");
188 /// \brief Heuristically reduce one of the nodes in the heuristic
190 /// @return True if a reduction takes place, false if the heuristic reduce
192 void heuristicReduce() {
193 assert(false && "Must be implemented in derived class.");
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.");
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.");
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.");
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.
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.");
225 /// \brief Clean up any structures used by HeuristicBase.
227 /// At present this just performs a sanity check: that the optimal reduce
228 /// list is empty now that reduction has completed.
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
234 assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
242 #endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H