summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/lib/CodeGen/PBQP
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/CodeGen/PBQP')
-rw-r--r--contrib/llvm/lib/CodeGen/PBQP/Graph.h425
-rw-r--r--contrib/llvm/lib/CodeGen/PBQP/HeuristicBase.h242
-rw-r--r--contrib/llvm/lib/CodeGen/PBQP/HeuristicSolver.h607
-rw-r--r--contrib/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h465
-rw-r--r--contrib/llvm/lib/CodeGen/PBQP/Math.h288
-rw-r--r--contrib/llvm/lib/CodeGen/PBQP/Solution.h58
6 files changed, 2085 insertions, 0 deletions
diff --git a/contrib/llvm/lib/CodeGen/PBQP/Graph.h b/contrib/llvm/lib/CodeGen/PBQP/Graph.h
new file mode 100644
index 0000000..b2224cb
--- /dev/null
+++ b/contrib/llvm/lib/CodeGen/PBQP/Graph.h
@@ -0,0 +1,425 @@
+//===-------------------- 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
new file mode 100644
index 0000000..3bb24e1
--- /dev/null
+++ b/contrib/llvm/lib/CodeGen/PBQP/HeuristicBase.h
@@ -0,0 +1,242 @@
+//===-- 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())
+ 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
new file mode 100644
index 0000000..bd18b52
--- /dev/null
+++ b/contrib/llvm/lib/CodeGen/PBQP/HeuristicSolver.h
@@ -0,0 +1,607 @@
+//===-- 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);
+ }
+
+ /// \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);
+ }
+
+ /// \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);
+ }
+
+ 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
new file mode 100644
index 0000000..30d34d9
--- /dev/null
+++ b/contrib/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h
@@ -0,0 +1,465 @@
+//===-- 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 "llvm/Support/Compiler.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;
+ if (s->getSolverDegree(n1Itr) < s->getSolverDegree(n2Itr))
+ return false;
+ return (&*n1Itr < &*n2Itr);
+ }
+ 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;
+ if (cost1 > cost2)
+ return false;
+ return (&*n1Itr < &*n2Itr);
+ }
+
+ 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 ATTRIBUTE_UNUSED = getHeuristicEdgeData(eItr);
+
+ 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
new file mode 100644
index 0000000..e7598bf
--- /dev/null
+++ b/contrib/llvm/lib/CodeGen/PBQP/Math.h
@@ -0,0 +1,288 @@
+//===------ 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
new file mode 100644
index 0000000..294b537
--- /dev/null
+++ b/contrib/llvm/lib/CodeGen/PBQP/Solution.h
@@ -0,0 +1,58 @@
+//===-- 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;
+
+ 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 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
OpenPOWER on IntegriCloud