diff options
Diffstat (limited to 'include/llvm/CodeGen/PBQP/HeuristicBase.h')
| -rw-r--r-- | include/llvm/CodeGen/PBQP/HeuristicBase.h | 247 |
1 files changed, 0 insertions, 247 deletions
diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h deleted file mode 100644 index 8bcbb9e..0000000 --- a/include/llvm/CodeGen/PBQP/HeuristicBase.h +++ /dev/null @@ -1,247 +0,0 @@ -//===-- 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 |