diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/PBQP')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PBQP/Graph.h | 425 | ||||
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PBQP/HeuristicBase.h | 246 | ||||
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PBQP/HeuristicSolver.h | 616 | ||||
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h | 460 | ||||
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PBQP/Math.h | 288 | ||||
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PBQP/Solution.h | 89 |
6 files changed, 0 insertions, 2124 deletions
diff --git a/contrib/llvm/lib/CodeGen/PBQP/Graph.h b/contrib/llvm/lib/CodeGen/PBQP/Graph.h deleted file mode 100644 index b2224cb..0000000 --- a/contrib/llvm/lib/CodeGen/PBQP/Graph.h +++ /dev/null @@ -1,425 +0,0 @@ -//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// PBQP Graph class. -// -//===----------------------------------------------------------------------===// - - -#ifndef LLVM_CODEGEN_PBQP_GRAPH_H -#define LLVM_CODEGEN_PBQP_GRAPH_H - -#include "Math.h" - -#include <list> -#include <vector> -#include <map> - -namespace PBQP { - - /// PBQP Graph class. - /// Instances of this class describe PBQP problems. - class Graph { - private: - - // ----- TYPEDEFS ----- - class NodeEntry; - class EdgeEntry; - - typedef std::list<NodeEntry> NodeList; - typedef std::list<EdgeEntry> EdgeList; - - public: - - typedef NodeList::iterator NodeItr; - typedef NodeList::const_iterator ConstNodeItr; - - typedef EdgeList::iterator EdgeItr; - typedef EdgeList::const_iterator ConstEdgeItr; - - private: - - typedef std::list<EdgeItr> AdjEdgeList; - - public: - - typedef AdjEdgeList::iterator AdjEdgeItr; - - private: - - class NodeEntry { - private: - Vector costs; - AdjEdgeList adjEdges; - unsigned degree; - void *data; - public: - NodeEntry(const Vector &costs) : costs(costs), degree(0) {} - Vector& getCosts() { return costs; } - const Vector& getCosts() const { return costs; } - unsigned getDegree() const { return degree; } - AdjEdgeItr edgesBegin() { return adjEdges.begin(); } - AdjEdgeItr edgesEnd() { return adjEdges.end(); } - AdjEdgeItr addEdge(EdgeItr e) { - ++degree; - return adjEdges.insert(adjEdges.end(), e); - } - void removeEdge(AdjEdgeItr ae) { - --degree; - adjEdges.erase(ae); - } - void setData(void *data) { this->data = data; } - void* getData() { return data; } - }; - - class EdgeEntry { - private: - NodeItr node1, node2; - Matrix costs; - AdjEdgeItr node1AEItr, node2AEItr; - void *data; - public: - EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) - : node1(node1), node2(node2), costs(costs) {} - NodeItr getNode1() const { return node1; } - NodeItr getNode2() const { return node2; } - Matrix& getCosts() { return costs; } - const Matrix& getCosts() const { return costs; } - void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; } - AdjEdgeItr getNode1AEItr() { return node1AEItr; } - void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; } - AdjEdgeItr getNode2AEItr() { return node2AEItr; } - void setData(void *data) { this->data = data; } - void *getData() { return data; } - }; - - // ----- MEMBERS ----- - - NodeList nodes; - unsigned numNodes; - - EdgeList edges; - unsigned numEdges; - - // ----- INTERNAL METHODS ----- - - NodeEntry& getNode(NodeItr nItr) { return *nItr; } - const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; } - - EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; } - const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; } - - NodeItr addConstructedNode(const NodeEntry &n) { - ++numNodes; - return nodes.insert(nodes.end(), n); - } - - EdgeItr addConstructedEdge(const EdgeEntry &e) { - assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() && - "Attempt to add duplicate edge."); - ++numEdges; - EdgeItr edgeItr = edges.insert(edges.end(), e); - EdgeEntry &ne = getEdge(edgeItr); - NodeEntry &n1 = getNode(ne.getNode1()); - NodeEntry &n2 = getNode(ne.getNode2()); - // Sanity check on matrix dimensions: - assert((n1.getCosts().getLength() == ne.getCosts().getRows()) && - (n2.getCosts().getLength() == ne.getCosts().getCols()) && - "Edge cost dimensions do not match node costs dimensions."); - ne.setNode1AEItr(n1.addEdge(edgeItr)); - ne.setNode2AEItr(n2.addEdge(edgeItr)); - return edgeItr; - } - - inline void copyFrom(const Graph &other); - public: - - /// \brief Construct an empty PBQP graph. - Graph() : numNodes(0), numEdges(0) {} - - /// \brief Copy construct this graph from "other". Note: Does not copy node - /// and edge data, only graph structure and costs. - /// @param other Source graph to copy from. - Graph(const Graph &other) : numNodes(0), numEdges(0) { - copyFrom(other); - } - - /// \brief Make this graph a copy of "other". Note: Does not copy node and - /// edge data, only graph structure and costs. - /// @param other The graph to copy from. - /// @return A reference to this graph. - /// - /// This will clear the current graph, erasing any nodes and edges added, - /// before copying from other. - Graph& operator=(const Graph &other) { - clear(); - copyFrom(other); - return *this; - } - - /// \brief Add a node with the given costs. - /// @param costs Cost vector for the new node. - /// @return Node iterator for the added node. - NodeItr addNode(const Vector &costs) { - return addConstructedNode(NodeEntry(costs)); - } - - /// \brief Add an edge between the given nodes with the given costs. - /// @param n1Itr First node. - /// @param n2Itr Second node. - /// @return Edge iterator for the added edge. - EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr, - const Matrix &costs) { - assert(getNodeCosts(n1Itr).getLength() == costs.getRows() && - getNodeCosts(n2Itr).getLength() == costs.getCols() && - "Matrix dimensions mismatch."); - return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); - } - - /// \brief Get the number of nodes in the graph. - /// @return Number of nodes in the graph. - unsigned getNumNodes() const { return numNodes; } - - /// \brief Get the number of edges in the graph. - /// @return Number of edges in the graph. - unsigned getNumEdges() const { return numEdges; } - - /// \brief Get a node's cost vector. - /// @param nItr Node iterator. - /// @return Node cost vector. - Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); } - - /// \brief Get a node's cost vector (const version). - /// @param nItr Node iterator. - /// @return Node cost vector. - const Vector& getNodeCosts(ConstNodeItr nItr) const { - return getNode(nItr).getCosts(); - } - - /// \brief Set a node's data pointer. - /// @param nItr Node iterator. - /// @param data Pointer to node data. - /// - /// Typically used by a PBQP solver to attach data to aid in solution. - void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); } - - /// \brief Get the node's data pointer. - /// @param nItr Node iterator. - /// @return Pointer to node data. - void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); } - - /// \brief Get an edge's cost matrix. - /// @param eItr Edge iterator. - /// @return Edge cost matrix. - Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); } - - /// \brief Get an edge's cost matrix (const version). - /// @param eItr Edge iterator. - /// @return Edge cost matrix. - const Matrix& getEdgeCosts(ConstEdgeItr eItr) const { - return getEdge(eItr).getCosts(); - } - - /// \brief Set an edge's data pointer. - /// @param eItr Edge iterator. - /// @param data Pointer to edge data. - /// - /// Typically used by a PBQP solver to attach data to aid in solution. - void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); } - - /// \brief Get an edge's data pointer. - /// @param eItr Edge iterator. - /// @return Pointer to edge data. - void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); } - - /// \brief Get a node's degree. - /// @param nItr Node iterator. - /// @return The degree of the node. - unsigned getNodeDegree(NodeItr nItr) const { - return getNode(nItr).getDegree(); - } - - /// \brief Begin iterator for node set. - NodeItr nodesBegin() { return nodes.begin(); } - - /// \brief Begin const iterator for node set. - ConstNodeItr nodesBegin() const { return nodes.begin(); } - - /// \brief End iterator for node set. - NodeItr nodesEnd() { return nodes.end(); } - - /// \brief End const iterator for node set. - ConstNodeItr nodesEnd() const { return nodes.end(); } - - /// \brief Begin iterator for edge set. - EdgeItr edgesBegin() { return edges.begin(); } - - /// \brief End iterator for edge set. - EdgeItr edgesEnd() { return edges.end(); } - - /// \brief Get begin iterator for adjacent edge set. - /// @param nItr Node iterator. - /// @return Begin iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesBegin(NodeItr nItr) { - return getNode(nItr).edgesBegin(); - } - - /// \brief Get end iterator for adjacent edge set. - /// @param nItr Node iterator. - /// @return End iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesEnd(NodeItr nItr) { - return getNode(nItr).edgesEnd(); - } - - /// \brief Get the first node connected to this edge. - /// @param eItr Edge iterator. - /// @return The first node connected to the given edge. - NodeItr getEdgeNode1(EdgeItr eItr) { - return getEdge(eItr).getNode1(); - } - - /// \brief Get the second node connected to this edge. - /// @param eItr Edge iterator. - /// @return The second node connected to the given edge. - NodeItr getEdgeNode2(EdgeItr eItr) { - return getEdge(eItr).getNode2(); - } - - /// \brief Get the "other" node connected to this edge. - /// @param eItr Edge iterator. - /// @param nItr Node iterator for the "given" node. - /// @return The iterator for the "other" node connected to this edge. - NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) { - EdgeEntry &e = getEdge(eItr); - if (e.getNode1() == nItr) { - return e.getNode2(); - } // else - return e.getNode1(); - } - - /// \brief Get the edge connecting two nodes. - /// @param n1Itr First node iterator. - /// @param n2Itr Second node iterator. - /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists, - /// otherwise returns edgesEnd(). - EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) { - for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr); - aeItr != aeEnd; ++aeItr) { - if ((getEdgeNode1(*aeItr) == n2Itr) || - (getEdgeNode2(*aeItr) == n2Itr)) { - return *aeItr; - } - } - return edges.end(); - } - - /// \brief Remove a node from the graph. - /// @param nItr Node iterator. - void removeNode(NodeItr nItr) { - NodeEntry &n = getNode(nItr); - for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) { - EdgeItr eItr = *itr; - ++itr; - removeEdge(eItr); - } - nodes.erase(nItr); - --numNodes; - } - - /// \brief Remove an edge from the graph. - /// @param eItr Edge iterator. - void removeEdge(EdgeItr eItr) { - EdgeEntry &e = getEdge(eItr); - NodeEntry &n1 = getNode(e.getNode1()); - NodeEntry &n2 = getNode(e.getNode2()); - n1.removeEdge(e.getNode1AEItr()); - n2.removeEdge(e.getNode2AEItr()); - edges.erase(eItr); - --numEdges; - } - - /// \brief Remove all nodes and edges from the graph. - void clear() { - nodes.clear(); - edges.clear(); - numNodes = numEdges = 0; - } - - /// \brief Print a representation of this graph in DOT format. - /// @param os Output stream to print on. - template <typename OStream> - void printDot(OStream &os) { - - os << "graph {\n"; - - for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); - nodeItr != nodeEnd; ++nodeItr) { - - os << " node" << nodeItr << " [ label=\"" - << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n"; - } - - os << " edge [ len=" << getNumNodes() << " ]\n"; - - for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); - edgeItr != edgeEnd; ++edgeItr) { - - os << " node" << getEdgeNode1(edgeItr) - << " -- node" << getEdgeNode2(edgeItr) - << " [ label=\""; - - const Matrix &edgeCosts = getEdgeCosts(edgeItr); - - for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { - os << edgeCosts.getRowAsVector(i) << "\\n"; - } - os << "\" ]\n"; - } - os << "}\n"; - } - - }; - - class NodeItrComparator { - public: - bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const { - return &*n1 < &*n2; - } - - bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const { - return &*n1 < &*n2; - } - }; - - class EdgeItrCompartor { - public: - bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const { - return &*e1 < &*e2; - } - - bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const { - return &*e1 < &*e2; - } - }; - - void Graph::copyFrom(const Graph &other) { - std::map<Graph::ConstNodeItr, Graph::NodeItr, - NodeItrComparator> nodeMap; - - for (Graph::ConstNodeItr nItr = other.nodesBegin(), - nEnd = other.nodesEnd(); - nItr != nEnd; ++nItr) { - nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); - } - - } - -} - -#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP diff --git a/contrib/llvm/lib/CodeGen/PBQP/HeuristicBase.h b/contrib/llvm/lib/CodeGen/PBQP/HeuristicBase.h deleted file mode 100644 index 791c227..0000000 --- a/contrib/llvm/lib/CodeGen/PBQP/HeuristicBase.h +++ /dev/null @@ -1,246 +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::NodeItr> 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::NodeItr nItr) { - optimalList.insert(optimalList.end(), nItr); - } - - 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::NodeItr nItr) { - if (g.getNodeDegree(nItr) < 3) - return true; - // else - return false; - } - - /// \brief Add the given node to the list of nodes to be optimally reduced. - /// @return nItr Node iterator 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::NodeItr nItr) { - optimalList.push_back(nItr); - } - - /// \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::NodeItr nItr = optimalList.front(); - optimalList.pop_front(); - - switch (s.getSolverDegree(nItr)) { - case 0: s.applyR0(nItr); break; - case 1: s.applyR1(nItr); break; - case 2: s.applyR2(nItr); break; - default: assert(false && - "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 nItr Node iterator to add to the heuristic reduce list. - void addToHeuristicList(Graph::NodeItr nItr) { - assert(false && "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. - void heuristicReduce() { - assert(false && "Must be implemented in derived class."); - } - - /// \brief Prepare a change in the costs on the given edge. - /// @param eItr Edge iterator. - void preUpdateEdgeCosts(Graph::EdgeItr eItr) { - assert(false && "Must be implemented in derived class."); - } - - /// \brief Handle the change in the costs on the given edge. - /// @param eItr Edge iterator. - void postUpdateEdgeCostts(Graph::EdgeItr eItr) { - assert(false && "Must be implemented in derived class."); - } - - /// \brief Handle the addition of a new edge into the PBQP graph. - /// @param eItr Edge iterator for the added edge. - void handleAddEdge(Graph::EdgeItr eItr) { - assert(false && "Must be implemented in derived class."); - } - - /// \brief Handle disconnection of an edge from a node. - /// @param eItr Edge iterator for edge being disconnected. - /// @param nItr Node iterator 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::EdgeItr eItr, Graph::NodeItr nItr) { - assert(false && "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 diff --git a/contrib/llvm/lib/CodeGen/PBQP/HeuristicSolver.h b/contrib/llvm/lib/CodeGen/PBQP/HeuristicSolver.h deleted file mode 100644 index 35514f9..0000000 --- a/contrib/llvm/lib/CodeGen/PBQP/HeuristicSolver.h +++ /dev/null @@ -1,616 +0,0 @@ -//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Heuristic PBQP solver. This solver is able to perform optimal reductions for -// nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is -// used to select a node for reduction. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H -#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H - -#include "Graph.h" -#include "Solution.h" -#include <vector> -#include <limits> - -namespace PBQP { - - /// \brief Heuristic PBQP solver implementation. - /// - /// This class should usually be created (and destroyed) indirectly via a call - /// to HeuristicSolver<HImpl>::solve(Graph&). - /// See the comments for HeuristicSolver. - /// - /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules, - /// backpropagation phase, and maintains the internal copy of the graph on - /// which the reduction is carried out (the original being kept to facilitate - /// backpropagation). - template <typename HImpl> - class HeuristicSolverImpl { - private: - - typedef typename HImpl::NodeData HeuristicNodeData; - typedef typename HImpl::EdgeData HeuristicEdgeData; - - typedef std::list<Graph::EdgeItr> SolverEdges; - - public: - - /// \brief Iterator type for edges in the solver graph. - typedef SolverEdges::iterator SolverEdgeItr; - - private: - - class NodeData { - public: - NodeData() : solverDegree(0) {} - - HeuristicNodeData& getHeuristicData() { return hData; } - - SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) { - ++solverDegree; - return solverEdges.insert(solverEdges.end(), eItr); - } - - void removeSolverEdge(SolverEdgeItr seItr) { - --solverDegree; - solverEdges.erase(seItr); - } - - SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); } - SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); } - unsigned getSolverDegree() const { return solverDegree; } - void clearSolverEdges() { - solverDegree = 0; - solverEdges.clear(); - } - - private: - HeuristicNodeData hData; - unsigned solverDegree; - SolverEdges solverEdges; - }; - - class EdgeData { - public: - HeuristicEdgeData& getHeuristicData() { return hData; } - - void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) { - this->n1SolverEdgeItr = n1SolverEdgeItr; - } - - SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; } - - void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){ - this->n2SolverEdgeItr = n2SolverEdgeItr; - } - - SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; } - - private: - - HeuristicEdgeData hData; - SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr; - }; - - Graph &g; - HImpl h; - Solution s; - std::vector<Graph::NodeItr> stack; - - typedef std::list<NodeData> NodeDataList; - NodeDataList nodeDataList; - - typedef std::list<EdgeData> EdgeDataList; - EdgeDataList edgeDataList; - - public: - - /// \brief Construct a heuristic solver implementation to solve the given - /// graph. - /// @param g The graph representing the problem instance to be solved. - HeuristicSolverImpl(Graph &g) : g(g), h(*this) {} - - /// \brief Get the graph being solved by this solver. - /// @return The graph representing the problem instance being solved by this - /// solver. - Graph& getGraph() { return g; } - - /// \brief Get the heuristic data attached to the given node. - /// @param nItr Node iterator. - /// @return The heuristic data attached to the given node. - HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).getHeuristicData(); - } - - /// \brief Get the heuristic data attached to the given edge. - /// @param eItr Edge iterator. - /// @return The heuristic data attached to the given node. - HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { - return getSolverEdgeData(eItr).getHeuristicData(); - } - - /// \brief Begin iterator for the set of edges adjacent to the given node in - /// the solver graph. - /// @param nItr Node iterator. - /// @return Begin iterator for the set of edges adjacent to the given node - /// in the solver graph. - SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).solverEdgesBegin(); - } - - /// \brief End iterator for the set of edges adjacent to the given node in - /// the solver graph. - /// @param nItr Node iterator. - /// @return End iterator for the set of edges adjacent to the given node in - /// the solver graph. - SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).solverEdgesEnd(); - } - - /// \brief Remove a node from the solver graph. - /// @param eItr Edge iterator for edge to be removed. - /// - /// Does <i>not</i> notify the heuristic of the removal. That should be - /// done manually if necessary. - void removeSolverEdge(Graph::EdgeItr eItr) { - EdgeData &eData = getSolverEdgeData(eItr); - NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), - &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); - - n1Data.removeSolverEdge(eData.getN1SolverEdgeItr()); - n2Data.removeSolverEdge(eData.getN2SolverEdgeItr()); - } - - /// \brief Compute a solution to the PBQP problem instance with which this - /// heuristic solver was constructed. - /// @return A solution to the PBQP problem. - /// - /// Performs the full PBQP heuristic solver algorithm, including setup, - /// calls to the heuristic (which will call back to the reduction rules in - /// this class), and cleanup. - Solution computeSolution() { - setup(); - h.setup(); - h.reduce(); - backpropagate(); - h.cleanup(); - cleanup(); - return s; - } - - /// \brief Add to the end of the stack. - /// @param nItr Node iterator to add to the reduction stack. - void pushToStack(Graph::NodeItr nItr) { - getSolverNodeData(nItr).clearSolverEdges(); - stack.push_back(nItr); - } - - /// \brief Returns the solver degree of the given node. - /// @param nItr Node iterator for which degree is requested. - /// @return Node degree in the <i>solver</i> graph (not the original graph). - unsigned getSolverDegree(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).getSolverDegree(); - } - - /// \brief Set the solution of the given node. - /// @param nItr Node iterator to set solution for. - /// @param selection Selection for node. - void setSolution(const Graph::NodeItr &nItr, unsigned selection) { - s.setSelection(nItr, selection); - - for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), - aeEnd = g.adjEdgesEnd(nItr); - aeItr != aeEnd; ++aeItr) { - Graph::EdgeItr eItr(*aeItr); - Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr)); - getSolverNodeData(anItr).addSolverEdge(eItr); - } - } - - /// \brief Apply rule R0. - /// @param nItr Node iterator for node to apply R0 to. - /// - /// Node will be automatically pushed to the solver stack. - void applyR0(Graph::NodeItr nItr) { - assert(getSolverNodeData(nItr).getSolverDegree() == 0 && - "R0 applied to node with degree != 0."); - - // Nothing to do. Just push the node onto the reduction stack. - pushToStack(nItr); - - s.recordR0(); - } - - /// \brief Apply rule R1. - /// @param xnItr Node iterator for node to apply R1 to. - /// - /// Node will be automatically pushed to the solver stack. - void applyR1(Graph::NodeItr xnItr) { - NodeData &nd = getSolverNodeData(xnItr); - assert(nd.getSolverDegree() == 1 && - "R1 applied to node with degree != 1."); - - Graph::EdgeItr eItr = *nd.solverEdgesBegin(); - - const Matrix &eCosts = g.getEdgeCosts(eItr); - const Vector &xCosts = g.getNodeCosts(xnItr); - - // Duplicate a little to avoid transposing matrices. - if (xnItr == g.getEdgeNode1(eItr)) { - Graph::NodeItr ynItr = g.getEdgeNode2(eItr); - Vector &yCosts = g.getNodeCosts(ynItr); - for (unsigned j = 0; j < yCosts.getLength(); ++j) { - PBQPNum min = eCosts[0][j] + xCosts[0]; - for (unsigned i = 1; i < xCosts.getLength(); ++i) { - PBQPNum c = eCosts[i][j] + xCosts[i]; - if (c < min) - min = c; - } - yCosts[j] += min; - } - h.handleRemoveEdge(eItr, ynItr); - } else { - Graph::NodeItr ynItr = g.getEdgeNode1(eItr); - Vector &yCosts = g.getNodeCosts(ynItr); - for (unsigned i = 0; i < yCosts.getLength(); ++i) { - PBQPNum min = eCosts[i][0] + xCosts[0]; - for (unsigned j = 1; j < xCosts.getLength(); ++j) { - PBQPNum c = eCosts[i][j] + xCosts[j]; - if (c < min) - min = c; - } - yCosts[i] += min; - } - h.handleRemoveEdge(eItr, ynItr); - } - removeSolverEdge(eItr); - assert(nd.getSolverDegree() == 0 && - "Degree 1 with edge removed should be 0."); - pushToStack(xnItr); - s.recordR1(); - } - - /// \brief Apply rule R2. - /// @param xnItr Node iterator for node to apply R2 to. - /// - /// Node will be automatically pushed to the solver stack. - void applyR2(Graph::NodeItr xnItr) { - assert(getSolverNodeData(xnItr).getSolverDegree() == 2 && - "R2 applied to node with degree != 2."); - - NodeData &nd = getSolverNodeData(xnItr); - const Vector &xCosts = g.getNodeCosts(xnItr); - - SolverEdgeItr aeItr = nd.solverEdgesBegin(); - Graph::EdgeItr yxeItr = *aeItr, - zxeItr = *(++aeItr); - - Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr), - znItr = g.getEdgeOtherNode(zxeItr, xnItr); - - bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr), - flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr); - - const Matrix *yxeCosts = flipEdge1 ? - new Matrix(g.getEdgeCosts(yxeItr).transpose()) : - &g.getEdgeCosts(yxeItr); - - const Matrix *zxeCosts = flipEdge2 ? - new Matrix(g.getEdgeCosts(zxeItr).transpose()) : - &g.getEdgeCosts(zxeItr); - - unsigned xLen = xCosts.getLength(), - yLen = yxeCosts->getRows(), - zLen = zxeCosts->getRows(); - - Matrix delta(yLen, zLen); - - for (unsigned i = 0; i < yLen; ++i) { - for (unsigned j = 0; j < zLen; ++j) { - PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0]; - for (unsigned k = 1; k < xLen; ++k) { - PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k]; - if (c < min) { - min = c; - } - } - delta[i][j] = min; - } - } - - if (flipEdge1) - delete yxeCosts; - - if (flipEdge2) - delete zxeCosts; - - Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr); - bool addedEdge = false; - - if (yzeItr == g.edgesEnd()) { - yzeItr = g.addEdge(ynItr, znItr, delta); - addedEdge = true; - } else { - Matrix &yzeCosts = g.getEdgeCosts(yzeItr); - h.preUpdateEdgeCosts(yzeItr); - if (ynItr == g.getEdgeNode1(yzeItr)) { - yzeCosts += delta; - } else { - yzeCosts += delta.transpose(); - } - } - - bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr); - - if (!addedEdge) { - // If we modified the edge costs let the heuristic know. - h.postUpdateEdgeCosts(yzeItr); - } - - if (nullCostEdge) { - // If this edge ended up null remove it. - if (!addedEdge) { - // We didn't just add it, so we need to notify the heuristic - // and remove it from the solver. - h.handleRemoveEdge(yzeItr, ynItr); - h.handleRemoveEdge(yzeItr, znItr); - removeSolverEdge(yzeItr); - } - g.removeEdge(yzeItr); - } else if (addedEdge) { - // If the edge was added, and non-null, finish setting it up, add it to - // the solver & notify heuristic. - edgeDataList.push_back(EdgeData()); - g.setEdgeData(yzeItr, &edgeDataList.back()); - addSolverEdge(yzeItr); - h.handleAddEdge(yzeItr); - } - - h.handleRemoveEdge(yxeItr, ynItr); - removeSolverEdge(yxeItr); - h.handleRemoveEdge(zxeItr, znItr); - removeSolverEdge(zxeItr); - - pushToStack(xnItr); - s.recordR2(); - } - - /// \brief Record an application of the RN rule. - /// - /// For use by the HeuristicBase. - void recordRN() { s.recordRN(); } - - private: - - NodeData& getSolverNodeData(Graph::NodeItr nItr) { - return *static_cast<NodeData*>(g.getNodeData(nItr)); - } - - EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) { - return *static_cast<EdgeData*>(g.getEdgeData(eItr)); - } - - void addSolverEdge(Graph::EdgeItr eItr) { - EdgeData &eData = getSolverEdgeData(eItr); - NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), - &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); - - eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr)); - eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr)); - } - - void setup() { - if (h.solverRunSimplify()) { - simplify(); - } - - // Create node data objects. - for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); - nItr != nEnd; ++nItr) { - nodeDataList.push_back(NodeData()); - g.setNodeData(nItr, &nodeDataList.back()); - } - - // Create edge data objects. - for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); - eItr != eEnd; ++eItr) { - edgeDataList.push_back(EdgeData()); - g.setEdgeData(eItr, &edgeDataList.back()); - addSolverEdge(eItr); - } - } - - void simplify() { - disconnectTrivialNodes(); - eliminateIndependentEdges(); - } - - // Eliminate trivial nodes. - void disconnectTrivialNodes() { - unsigned numDisconnected = 0; - - for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); - nItr != nEnd; ++nItr) { - - if (g.getNodeCosts(nItr).getLength() == 1) { - - std::vector<Graph::EdgeItr> edgesToRemove; - - for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), - aeEnd = g.adjEdgesEnd(nItr); - aeItr != aeEnd; ++aeItr) { - - Graph::EdgeItr eItr = *aeItr; - - if (g.getEdgeNode1(eItr) == nItr) { - Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr); - g.getNodeCosts(otherNodeItr) += - g.getEdgeCosts(eItr).getRowAsVector(0); - } - else { - Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr); - g.getNodeCosts(otherNodeItr) += - g.getEdgeCosts(eItr).getColAsVector(0); - } - - edgesToRemove.push_back(eItr); - } - - if (!edgesToRemove.empty()) - ++numDisconnected; - - while (!edgesToRemove.empty()) { - g.removeEdge(edgesToRemove.back()); - edgesToRemove.pop_back(); - } - } - } - } - - void eliminateIndependentEdges() { - std::vector<Graph::EdgeItr> edgesToProcess; - unsigned numEliminated = 0; - - for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); - eItr != eEnd; ++eItr) { - edgesToProcess.push_back(eItr); - } - - while (!edgesToProcess.empty()) { - if (tryToEliminateEdge(edgesToProcess.back())) - ++numEliminated; - edgesToProcess.pop_back(); - } - } - - bool tryToEliminateEdge(Graph::EdgeItr eItr) { - if (tryNormaliseEdgeMatrix(eItr)) { - g.removeEdge(eItr); - return true; - } - return false; - } - - bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) { - - const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity(); - - Matrix &edgeCosts = g.getEdgeCosts(eItr); - Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)), - &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr)); - - for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { - PBQPNum rowMin = infinity; - - for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { - if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin) - rowMin = edgeCosts[r][c]; - } - - uCosts[r] += rowMin; - - if (rowMin != infinity) { - edgeCosts.subFromRow(r, rowMin); - } - else { - edgeCosts.setRow(r, 0); - } - } - - for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { - PBQPNum colMin = infinity; - - for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { - if (uCosts[r] != infinity && edgeCosts[r][c] < colMin) - colMin = edgeCosts[r][c]; - } - - vCosts[c] += colMin; - - if (colMin != infinity) { - edgeCosts.subFromCol(c, colMin); - } - else { - edgeCosts.setCol(c, 0); - } - } - - return edgeCosts.isZero(); - } - - void backpropagate() { - while (!stack.empty()) { - computeSolution(stack.back()); - stack.pop_back(); - } - } - - void computeSolution(Graph::NodeItr nItr) { - - NodeData &nodeData = getSolverNodeData(nItr); - - Vector v(g.getNodeCosts(nItr)); - - // Solve based on existing solved edges. - for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(), - solvedEdgeEnd = nodeData.solverEdgesEnd(); - solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) { - - Graph::EdgeItr eItr(*solvedEdgeItr); - Matrix &edgeCosts = g.getEdgeCosts(eItr); - - if (nItr == g.getEdgeNode1(eItr)) { - Graph::NodeItr adjNode(g.getEdgeNode2(eItr)); - unsigned adjSolution = s.getSelection(adjNode); - v += edgeCosts.getColAsVector(adjSolution); - } - else { - Graph::NodeItr adjNode(g.getEdgeNode1(eItr)); - unsigned adjSolution = s.getSelection(adjNode); - v += edgeCosts.getRowAsVector(adjSolution); - } - - } - - setSolution(nItr, v.minIndex()); - } - - void cleanup() { - h.cleanup(); - nodeDataList.clear(); - edgeDataList.clear(); - } - }; - - /// \brief PBQP heuristic solver class. - /// - /// Given a PBQP Graph g representing a PBQP problem, you can find a solution - /// by calling - /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt> - /// - /// The choice of heuristic for the H parameter will affect both the solver - /// speed and solution quality. The heuristic should be chosen based on the - /// nature of the problem being solved. - /// Currently the only solver included with LLVM is the Briggs heuristic for - /// register allocation. - template <typename HImpl> - class HeuristicSolver { - public: - static Solution solve(Graph &g) { - HeuristicSolverImpl<HImpl> hs(g); - return hs.computeSolution(); - } - }; - -} - -#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H diff --git a/contrib/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h b/contrib/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h deleted file mode 100644 index 18eaf7c..0000000 --- a/contrib/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h +++ /dev/null @@ -1,460 +0,0 @@ -//===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This class implements the Briggs test for "allocability" of nodes in a -// PBQP graph representing a register allocation problem. Nodes which can be -// proven allocable (by a safe and relatively accurate test) are removed from -// the PBQP graph first. If no provably allocable node is present in the graph -// then the node with the minimal spill-cost to degree ratio is removed. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H -#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H - -#include "../HeuristicSolver.h" -#include "../HeuristicBase.h" - -#include <set> -#include <limits> - -namespace PBQP { - namespace Heuristics { - - /// \brief PBQP Heuristic which applies an allocability test based on - /// Briggs. - /// - /// This heuristic assumes that the elements of cost vectors in the PBQP - /// problem represent storage options, with the first being the spill - /// option and subsequent elements representing legal registers for the - /// corresponding node. Edge cost matrices are likewise assumed to represent - /// register constraints. - /// If one or more nodes can be proven allocable by this heuristic (by - /// inspection of their constraint matrices) then the allocable node of - /// highest degree is selected for the next reduction and pushed to the - /// solver stack. If no nodes can be proven allocable then the node with - /// the lowest estimated spill cost is selected and push to the solver stack - /// instead. - /// - /// This implementation is built on top of HeuristicBase. - class Briggs : public HeuristicBase<Briggs> { - private: - - class LinkDegreeComparator { - public: - LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {} - bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr)) - return true; - return false; - } - private: - HeuristicSolverImpl<Briggs> *s; - }; - - class SpillCostComparator { - public: - SpillCostComparator(HeuristicSolverImpl<Briggs> &s) - : s(&s), g(&s.getGraph()) {} - bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr), - cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr); - if (cost1 < cost2) - return true; - return false; - } - - private: - HeuristicSolverImpl<Briggs> *s; - Graph *g; - }; - - typedef std::list<Graph::NodeItr> RNAllocableList; - typedef RNAllocableList::iterator RNAllocableListItr; - - typedef std::list<Graph::NodeItr> RNUnallocableList; - typedef RNUnallocableList::iterator RNUnallocableListItr; - - public: - - struct NodeData { - typedef std::vector<unsigned> UnsafeDegreesArray; - bool isHeuristic, isAllocable, isInitialized; - unsigned numDenied, numSafe; - UnsafeDegreesArray unsafeDegrees; - RNAllocableListItr rnaItr; - RNUnallocableListItr rnuItr; - - NodeData() - : isHeuristic(false), isAllocable(false), isInitialized(false), - numDenied(0), numSafe(0) { } - }; - - struct EdgeData { - typedef std::vector<unsigned> UnsafeArray; - unsigned worst, reverseWorst; - UnsafeArray unsafe, reverseUnsafe; - bool isUpToDate; - - EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {} - }; - - /// \brief Construct an instance of the Briggs heuristic. - /// @param solver A reference to the solver which is using this heuristic. - Briggs(HeuristicSolverImpl<Briggs> &solver) : - HeuristicBase<Briggs>(solver) {} - - /// \brief Determine whether a node should be reduced using optimal - /// reduction. - /// @param nItr Node iterator to be considered. - /// @return True if the given node should be optimally reduced, false - /// otherwise. - /// - /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one - /// exception. Nodes whose spill cost (element 0 of their cost vector) is - /// infinite are checked for allocability first. Allocable nodes may be - /// optimally reduced, but nodes whose allocability cannot be proven are - /// selected for heuristic reduction instead. - bool shouldOptimallyReduce(Graph::NodeItr nItr) { - if (getSolver().getSolverDegree(nItr) < 3) { - return true; - } - // else - return false; - } - - /// \brief Add a node to the heuristic reduce list. - /// @param nItr Node iterator to add to the heuristic reduce list. - void addToHeuristicReduceList(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - initializeNode(nItr); - nd.isHeuristic = true; - if (nd.isAllocable) { - nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); - } else { - nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr); - } - } - - /// \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. - /// - /// If the list of allocable nodes is non-empty a node is selected - /// from it and pushed to the stack. Otherwise if the non-allocable list - /// is non-empty a node is selected from it and pushed to the stack. - /// If both lists are empty the method simply returns false with no action - /// taken. - bool heuristicReduce() { - if (!rnAllocableList.empty()) { - RNAllocableListItr rnaItr = - min_element(rnAllocableList.begin(), rnAllocableList.end(), - LinkDegreeComparator(getSolver())); - Graph::NodeItr nItr = *rnaItr; - rnAllocableList.erase(rnaItr); - handleRemoveNode(nItr); - getSolver().pushToStack(nItr); - return true; - } else if (!rnUnallocableList.empty()) { - RNUnallocableListItr rnuItr = - min_element(rnUnallocableList.begin(), rnUnallocableList.end(), - SpillCostComparator(getSolver())); - Graph::NodeItr nItr = *rnuItr; - rnUnallocableList.erase(rnuItr); - handleRemoveNode(nItr); - getSolver().pushToStack(nItr); - return true; - } - // else - return false; - } - - /// \brief Prepare a change in the costs on the given edge. - /// @param eItr Edge iterator. - void preUpdateEdgeCosts(Graph::EdgeItr eItr) { - Graph &g = getGraph(); - Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), - n2Itr = g.getEdgeNode2(eItr); - NodeData &n1 = getHeuristicNodeData(n1Itr), - &n2 = getHeuristicNodeData(n2Itr); - - if (n1.isHeuristic) - subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr)); - if (n2.isHeuristic) - subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr)); - - EdgeData &ed = getHeuristicEdgeData(eItr); - ed.isUpToDate = false; - } - - /// \brief Handle the change in the costs on the given edge. - /// @param eItr Edge iterator. - void postUpdateEdgeCosts(Graph::EdgeItr eItr) { - // This is effectively the same as adding a new edge now, since - // we've factored out the costs of the old one. - handleAddEdge(eItr); - } - - /// \brief Handle the addition of a new edge into the PBQP graph. - /// @param eItr Edge iterator for the added edge. - /// - /// Updates allocability of any nodes connected by this edge which are - /// being managed by the heuristic. If allocability changes they are - /// moved to the appropriate list. - void handleAddEdge(Graph::EdgeItr eItr) { - Graph &g = getGraph(); - Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), - n2Itr = g.getEdgeNode2(eItr); - NodeData &n1 = getHeuristicNodeData(n1Itr), - &n2 = getHeuristicNodeData(n2Itr); - - // If neither node is managed by the heuristic there's nothing to be - // done. - if (!n1.isHeuristic && !n2.isHeuristic) - return; - - // Ok - we need to update at least one node. - computeEdgeContributions(eItr); - - // Update node 1 if it's managed by the heuristic. - if (n1.isHeuristic) { - bool n1WasAllocable = n1.isAllocable; - addEdgeContributions(eItr, n1Itr); - updateAllocability(n1Itr); - if (n1WasAllocable && !n1.isAllocable) { - rnAllocableList.erase(n1.rnaItr); - n1.rnuItr = - rnUnallocableList.insert(rnUnallocableList.end(), n1Itr); - } - } - - // Likewise for node 2. - if (n2.isHeuristic) { - bool n2WasAllocable = n2.isAllocable; - addEdgeContributions(eItr, n2Itr); - updateAllocability(n2Itr); - if (n2WasAllocable && !n2.isAllocable) { - rnAllocableList.erase(n2.rnaItr); - n2.rnuItr = - rnUnallocableList.insert(rnUnallocableList.end(), n2Itr); - } - } - } - - /// \brief Handle disconnection of an edge from a node. - /// @param eItr Edge iterator for edge being disconnected. - /// @param nItr Node iterator for the node being disconnected from. - /// - /// Updates allocability of the given node and, if appropriate, moves the - /// node to a new list. - void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - - // If the node is not managed by the heuristic there's nothing to be - // done. - if (!nd.isHeuristic) - return; - - EdgeData &ed = getHeuristicEdgeData(eItr); - (void)ed; - assert(ed.isUpToDate && "Edge data is not up to date."); - - // Update node. - bool ndWasAllocable = nd.isAllocable; - subtractEdgeContributions(eItr, nItr); - updateAllocability(nItr); - - // If the node has gone optimal... - if (shouldOptimallyReduce(nItr)) { - nd.isHeuristic = false; - addToOptimalReduceList(nItr); - if (ndWasAllocable) { - rnAllocableList.erase(nd.rnaItr); - } else { - rnUnallocableList.erase(nd.rnuItr); - } - } else { - // Node didn't go optimal, but we might have to move it - // from "unallocable" to "allocable". - if (!ndWasAllocable && nd.isAllocable) { - rnUnallocableList.erase(nd.rnuItr); - nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); - } - } - } - - private: - - NodeData& getHeuristicNodeData(Graph::NodeItr nItr) { - return getSolver().getHeuristicNodeData(nItr); - } - - EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { - return getSolver().getHeuristicEdgeData(eItr); - } - - // Work out what this edge will contribute to the allocability of the - // nodes connected to it. - void computeEdgeContributions(Graph::EdgeItr eItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); - - if (ed.isUpToDate) - return; // Edge data is already up to date. - - Matrix &eCosts = getGraph().getEdgeCosts(eItr); - - unsigned numRegs = eCosts.getRows() - 1, - numReverseRegs = eCosts.getCols() - 1; - - std::vector<unsigned> rowInfCounts(numRegs, 0), - colInfCounts(numReverseRegs, 0); - - ed.worst = 0; - ed.reverseWorst = 0; - ed.unsafe.clear(); - ed.unsafe.resize(numRegs, 0); - ed.reverseUnsafe.clear(); - ed.reverseUnsafe.resize(numReverseRegs, 0); - - for (unsigned i = 0; i < numRegs; ++i) { - for (unsigned j = 0; j < numReverseRegs; ++j) { - if (eCosts[i + 1][j + 1] == - std::numeric_limits<PBQPNum>::infinity()) { - ed.unsafe[i] = 1; - ed.reverseUnsafe[j] = 1; - ++rowInfCounts[i]; - ++colInfCounts[j]; - - if (colInfCounts[j] > ed.worst) { - ed.worst = colInfCounts[j]; - } - - if (rowInfCounts[i] > ed.reverseWorst) { - ed.reverseWorst = rowInfCounts[i]; - } - } - } - } - - ed.isUpToDate = true; - } - - // Add the contributions of the given edge to the given node's - // numDenied and safe members. No action is taken other than to update - // these member values. Once updated these numbers can be used by clients - // to update the node's allocability. - void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); - - assert(ed.isUpToDate && "Using out-of-date edge numbers."); - - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); - EdgeData::UnsafeArray &unsafe = - nIsNode1 ? ed.unsafe : ed.reverseUnsafe; - nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst; - - for (unsigned r = 0; r < numRegs; ++r) { - if (unsafe[r]) { - if (nd.unsafeDegrees[r]==0) { - --nd.numSafe; - } - ++nd.unsafeDegrees[r]; - } - } - } - - // Subtract the contributions of the given edge to the given node's - // numDenied and safe members. No action is taken other than to update - // these member values. Once updated these numbers can be used by clients - // to update the node's allocability. - void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); - - assert(ed.isUpToDate && "Using out-of-date edge numbers."); - - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); - EdgeData::UnsafeArray &unsafe = - nIsNode1 ? ed.unsafe : ed.reverseUnsafe; - nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst; - - for (unsigned r = 0; r < numRegs; ++r) { - if (unsafe[r]) { - if (nd.unsafeDegrees[r] == 1) { - ++nd.numSafe; - } - --nd.unsafeDegrees[r]; - } - } - } - - void updateAllocability(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; - } - - void initializeNode(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - - if (nd.isInitialized) - return; // Node data is already up to date. - - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - nd.numDenied = 0; - nd.numSafe = numRegs; - nd.unsafeDegrees.resize(numRegs, 0); - - typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; - - for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr), - aeEnd = getSolver().solverEdgesEnd(nItr); - aeItr != aeEnd; ++aeItr) { - - Graph::EdgeItr eItr = *aeItr; - computeEdgeContributions(eItr); - addEdgeContributions(eItr, nItr); - } - - updateAllocability(nItr); - nd.isInitialized = true; - } - - void handleRemoveNode(Graph::NodeItr xnItr) { - typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; - std::vector<Graph::EdgeItr> edgesToRemove; - for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr), - aeEnd = getSolver().solverEdgesEnd(xnItr); - aeItr != aeEnd; ++aeItr) { - Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr); - handleRemoveEdge(*aeItr, ynItr); - edgesToRemove.push_back(*aeItr); - } - while (!edgesToRemove.empty()) { - getSolver().removeSolverEdge(edgesToRemove.back()); - edgesToRemove.pop_back(); - } - } - - RNAllocableList rnAllocableList; - RNUnallocableList rnUnallocableList; - }; - - } -} - - -#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H diff --git a/contrib/llvm/lib/CodeGen/PBQP/Math.h b/contrib/llvm/lib/CodeGen/PBQP/Math.h deleted file mode 100644 index e7598bf..0000000 --- a/contrib/llvm/lib/CodeGen/PBQP/Math.h +++ /dev/null @@ -1,288 +0,0 @@ -//===------ Math.h - PBQP Vector and Matrix classes -------------*- 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_MATH_H -#define LLVM_CODEGEN_PBQP_MATH_H - -#include <cassert> -#include <algorithm> -#include <functional> - -namespace PBQP { - -typedef float PBQPNum; - -/// \brief PBQP Vector class. -class Vector { - public: - - /// \brief Construct a PBQP vector of the given size. - explicit Vector(unsigned length) : - length(length), data(new PBQPNum[length]) { - } - - /// \brief Construct a PBQP vector with initializer. - Vector(unsigned length, PBQPNum initVal) : - length(length), data(new PBQPNum[length]) { - std::fill(data, data + length, initVal); - } - - /// \brief Copy construct a PBQP vector. - Vector(const Vector &v) : - length(v.length), data(new PBQPNum[length]) { - std::copy(v.data, v.data + length, data); - } - - /// \brief Destroy this vector, return its memory. - ~Vector() { delete[] data; } - - /// \brief Assignment operator. - Vector& operator=(const Vector &v) { - delete[] data; - length = v.length; - data = new PBQPNum[length]; - std::copy(v.data, v.data + length, data); - return *this; - } - - /// \brief Return the length of the vector - unsigned getLength() const { - return length; - } - - /// \brief Element access. - PBQPNum& operator[](unsigned index) { - assert(index < length && "Vector element access out of bounds."); - return data[index]; - } - - /// \brief Const element access. - const PBQPNum& operator[](unsigned index) const { - assert(index < length && "Vector element access out of bounds."); - return data[index]; - } - - /// \brief Add another vector to this one. - Vector& operator+=(const Vector &v) { - assert(length == v.length && "Vector length mismatch."); - std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); - return *this; - } - - /// \brief Subtract another vector from this one. - Vector& operator-=(const Vector &v) { - assert(length == v.length && "Vector length mismatch."); - std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); - return *this; - } - - /// \brief Returns the index of the minimum value in this vector - unsigned minIndex() const { - return std::min_element(data, data + length) - data; - } - - private: - unsigned length; - PBQPNum *data; -}; - -/// \brief Output a textual representation of the given vector on the given -/// output stream. -template <typename OStream> -OStream& operator<<(OStream &os, const Vector &v) { - assert((v.getLength() != 0) && "Zero-length vector badness."); - - os << "[ " << v[0]; - for (unsigned i = 1; i < v.getLength(); ++i) { - os << ", " << v[i]; - } - os << " ]"; - - return os; -} - - -/// \brief PBQP Matrix class -class Matrix { - public: - - /// \brief Construct a PBQP Matrix with the given dimensions. - Matrix(unsigned rows, unsigned cols) : - rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { - } - - /// \brief Construct a PBQP Matrix with the given dimensions and initial - /// value. - Matrix(unsigned rows, unsigned cols, PBQPNum initVal) : - rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { - std::fill(data, data + (rows * cols), initVal); - } - - /// \brief Copy construct a PBQP matrix. - Matrix(const Matrix &m) : - rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) { - std::copy(m.data, m.data + (rows * cols), data); - } - - /// \brief Destroy this matrix, return its memory. - ~Matrix() { delete[] data; } - - /// \brief Assignment operator. - Matrix& operator=(const Matrix &m) { - delete[] data; - rows = m.rows; cols = m.cols; - data = new PBQPNum[rows * cols]; - std::copy(m.data, m.data + (rows * cols), data); - return *this; - } - - /// \brief Return the number of rows in this matrix. - unsigned getRows() const { return rows; } - - /// \brief Return the number of cols in this matrix. - unsigned getCols() const { return cols; } - - /// \brief Matrix element access. - PBQPNum* operator[](unsigned r) { - assert(r < rows && "Row out of bounds."); - return data + (r * cols); - } - - /// \brief Matrix element access. - const PBQPNum* operator[](unsigned r) const { - assert(r < rows && "Row out of bounds."); - return data + (r * cols); - } - - /// \brief Returns the given row as a vector. - Vector getRowAsVector(unsigned r) const { - Vector v(cols); - for (unsigned c = 0; c < cols; ++c) - v[c] = (*this)[r][c]; - return v; - } - - /// \brief Returns the given column as a vector. - Vector getColAsVector(unsigned c) const { - Vector v(rows); - for (unsigned r = 0; r < rows; ++r) - v[r] = (*this)[r][c]; - return v; - } - - /// \brief Reset the matrix to the given value. - Matrix& reset(PBQPNum val = 0) { - std::fill(data, data + (rows * cols), val); - return *this; - } - - /// \brief Set a single row of this matrix to the given value. - Matrix& setRow(unsigned r, PBQPNum val) { - assert(r < rows && "Row out of bounds."); - std::fill(data + (r * cols), data + ((r + 1) * cols), val); - return *this; - } - - /// \brief Set a single column of this matrix to the given value. - Matrix& setCol(unsigned c, PBQPNum val) { - assert(c < cols && "Column out of bounds."); - for (unsigned r = 0; r < rows; ++r) - (*this)[r][c] = val; - return *this; - } - - /// \brief Matrix transpose. - Matrix transpose() const { - Matrix m(cols, rows); - for (unsigned r = 0; r < rows; ++r) - for (unsigned c = 0; c < cols; ++c) - m[c][r] = (*this)[r][c]; - return m; - } - - /// \brief Returns the diagonal of the matrix as a vector. - /// - /// Matrix must be square. - Vector diagonalize() const { - assert(rows == cols && "Attempt to diagonalize non-square matrix."); - - Vector v(rows); - for (unsigned r = 0; r < rows; ++r) - v[r] = (*this)[r][r]; - return v; - } - - /// \brief Add the given matrix to this one. - Matrix& operator+=(const Matrix &m) { - assert(rows == m.rows && cols == m.cols && - "Matrix dimensions mismatch."); - std::transform(data, data + (rows * cols), m.data, data, - std::plus<PBQPNum>()); - return *this; - } - - /// \brief Returns the minimum of the given row - PBQPNum getRowMin(unsigned r) const { - assert(r < rows && "Row out of bounds"); - return *std::min_element(data + (r * cols), data + ((r + 1) * cols)); - } - - /// \brief Returns the minimum of the given column - PBQPNum getColMin(unsigned c) const { - PBQPNum minElem = (*this)[0][c]; - for (unsigned r = 1; r < rows; ++r) - if ((*this)[r][c] < minElem) minElem = (*this)[r][c]; - return minElem; - } - - /// \brief Subtracts the given scalar from the elements of the given row. - Matrix& subFromRow(unsigned r, PBQPNum val) { - assert(r < rows && "Row out of bounds"); - std::transform(data + (r * cols), data + ((r + 1) * cols), - data + (r * cols), - std::bind2nd(std::minus<PBQPNum>(), val)); - return *this; - } - - /// \brief Subtracts the given scalar from the elements of the given column. - Matrix& subFromCol(unsigned c, PBQPNum val) { - for (unsigned r = 0; r < rows; ++r) - (*this)[r][c] -= val; - return *this; - } - - /// \brief Returns true if this is a zero matrix. - bool isZero() const { - return find_if(data, data + (rows * cols), - std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) == - data + (rows * cols); - } - - private: - unsigned rows, cols; - PBQPNum *data; -}; - -/// \brief Output a textual representation of the given matrix on the given -/// output stream. -template <typename OStream> -OStream& operator<<(OStream &os, const Matrix &m) { - - assert((m.getRows() != 0) && "Zero-row matrix badness."); - - for (unsigned i = 0; i < m.getRows(); ++i) { - os << m.getRowAsVector(i); - } - - return os; -} - -} - -#endif // LLVM_CODEGEN_PBQP_MATH_H diff --git a/contrib/llvm/lib/CodeGen/PBQP/Solution.h b/contrib/llvm/lib/CodeGen/PBQP/Solution.h deleted file mode 100644 index 047fd04..0000000 --- a/contrib/llvm/lib/CodeGen/PBQP/Solution.h +++ /dev/null @@ -1,89 +0,0 @@ -//===-- Solution.h ------- PBQP Solution ------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// PBQP Solution class. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H -#define LLVM_CODEGEN_PBQP_SOLUTION_H - -#include "Math.h" -#include "Graph.h" - -#include <map> - -namespace PBQP { - - /// \brief Represents a solution to a PBQP problem. - /// - /// To get the selection for each node in the problem use the getSelection method. - class Solution { - private: - - typedef std::map<Graph::NodeItr, unsigned, NodeItrComparator> SelectionsMap; - SelectionsMap selections; - - unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; - - public: - - /// \brief Number of nodes for which selections have been made. - /// @return Number of nodes for which selections have been made. - unsigned numNodes() const { return selections.size(); } - - /// \brief Records a reduction via the R0 rule. Should be called from the - /// solver only. - void recordR0() { ++r0Reductions; } - - /// \brief Returns the number of R0 reductions applied to solve the problem. - unsigned numR0Reductions() const { return r0Reductions; } - - /// \brief Records a reduction via the R1 rule. Should be called from the - /// solver only. - void recordR1() { ++r1Reductions; } - - /// \brief Returns the number of R1 reductions applied to solve the problem. - unsigned numR1Reductions() const { return r1Reductions; } - - /// \brief Records a reduction via the R2 rule. Should be called from the - /// solver only. - void recordR2() { ++r2Reductions; } - - /// \brief Returns the number of R2 reductions applied to solve the problem. - unsigned numR2Reductions() const { return r2Reductions; } - - /// \brief Records a reduction via the RN rule. Should be called from the - /// solver only. - void recordRN() { ++ rNReductions; } - - /// \brief Returns the number of RN reductions applied to solve the problem. - unsigned numRNReductions() const { return rNReductions; } - - /// \brief Set the selection for a given node. - /// @param nItr Node iterator. - /// @param selection Selection for nItr. - void setSelection(Graph::NodeItr nItr, unsigned selection) { - selections[nItr] = selection; - } - - /// \brief Get a node's selection. - /// @param nItr Node iterator. - /// @return The selection for nItr; - unsigned getSelection(Graph::NodeItr nItr) const { - SelectionsMap::const_iterator sItr = selections.find(nItr); - assert(sItr != selections.end() && "No selection for node."); - return sItr->second; - } - - }; - -} - -#endif // LLVM_CODEGEN_PBQP_SOLUTION_H |
