New C++ PBQP solver. Currently about as fast (read _slow_) as the old C based solver, but I'll be working to improve that. The PBQP allocator has been updated to use the new solver.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78354 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h
new file mode 100644
index 0000000..801b01e
--- /dev/null
+++ b/lib/CodeGen/PBQP/AnnotatedGraph.h
@@ -0,0 +1,170 @@
+#ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
+#define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
+
+#include "GraphBase.h"
+
+namespace PBQP {
+
+
+template <typename NodeData, typename EdgeData> class AnnotatedEdge;
+
+template <typename NodeData, typename EdgeData>
+class AnnotatedNode : public NodeBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> > {
+private:
+
+ NodeData nodeData;
+
+public:
+
+ AnnotatedNode(const Vector &costs, const NodeData &nodeData) :
+ NodeBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> >(costs),
+ nodeData(nodeData) {}
+
+ NodeData& getNodeData() { return nodeData; }
+ const NodeData& getNodeData() const { return nodeData; }
+
+};
+
+template <typename NodeData, typename EdgeData>
+class AnnotatedEdge : public EdgeBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> > {
+private:
+
+ typedef typename GraphBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> >::NodeIterator
+ NodeIterator;
+
+ EdgeData edgeData;
+
+public:
+
+
+ AnnotatedEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+ const Matrix &costs, const EdgeData &edgeData) :
+ EdgeBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> >(node1Itr, node2Itr, costs),
+ edgeData(edgeData) {}
+
+ EdgeData& getEdgeData() { return edgeData; }
+ const EdgeData& getEdgeData() const { return edgeData; }
+
+};
+
+template <typename NodeData, typename EdgeData>
+class AnnotatedGraph : public GraphBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> > {
+private:
+
+ typedef GraphBase<AnnotatedNode<NodeData, EdgeData>,
+ AnnotatedEdge<NodeData, EdgeData> > PGraph;
+
+ typedef AnnotatedNode<NodeData, EdgeData> NodeEntry;
+ typedef AnnotatedEdge<NodeData, EdgeData> EdgeEntry;
+
+
+ void copyFrom(const AnnotatedGraph &other) {
+ if (!other.areNodeIDsValid()) {
+ other.assignNodeIDs();
+ }
+ std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
+
+ for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
+ nItr != nEnd; ++nItr) {
+ newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
+ }
+
+ for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
+ eItr != eEnd; ++eItr) {
+
+ unsigned node1ID = other.getNodeID(other.getEdgeNode1(eItr)),
+ node2ID = other.getNodeID(other.getEdgeNode2(eItr));
+
+ addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
+ other.getEdgeCosts(eItr), other.getEdgeData(eItr));
+ }
+
+ }
+
+public:
+
+ typedef typename PGraph::NodeIterator NodeIterator;
+ typedef typename PGraph::ConstNodeIterator ConstNodeIterator;
+ typedef typename PGraph::EdgeIterator EdgeIterator;
+ typedef typename PGraph::ConstEdgeIterator ConstEdgeIterator;
+
+ AnnotatedGraph() {}
+
+ AnnotatedGraph(const AnnotatedGraph &other) {
+ copyFrom(other);
+ }
+
+ AnnotatedGraph& operator=(const AnnotatedGraph &other) {
+ PGraph::clear();
+ copyFrom(other);
+ return *this;
+ }
+
+ NodeIterator addNode(const Vector &costs, const NodeData &data) {
+ return PGraph::addConstructedNode(NodeEntry(costs, data));
+ }
+
+ EdgeIterator addEdge(const NodeIterator &node1Itr,
+ const NodeIterator &node2Itr,
+ const Matrix &costs, const EdgeData &data) {
+ return PGraph::addConstructedEdge(EdgeEntry(node1Itr, node2Itr,
+ costs, data));
+ }
+
+ NodeData& getNodeData(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).getNodeData();
+ }
+
+ const NodeData& getNodeData(const NodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).getNodeData();
+ }
+
+ EdgeData& getEdgeData(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getEdgeData();
+ }
+
+ const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getEdgeData();
+ }
+
+ SimpleGraph toSimpleGraph() const {
+ SimpleGraph g;
+
+ if (!PGraph::areNodeIDsValid()) {
+ PGraph::assignNodeIDs();
+ }
+ std::vector<SimpleGraph::NodeIterator> newNodeItrs(PGraph::getNumNodes());
+
+ for (ConstNodeIterator nItr = PGraph::nodesBegin(),
+ nEnd = PGraph::nodesEnd();
+ nItr != nEnd; ++nItr) {
+
+ newNodeItrs[getNodeID(nItr)] = g.addNode(getNodeCosts(nItr));
+ }
+
+ for (ConstEdgeIterator
+ eItr = PGraph::edgesBegin(), eEnd = PGraph::edgesEnd();
+ eItr != eEnd; ++eItr) {
+
+ unsigned node1ID = getNodeID(getEdgeNode1(eItr)),
+ node2ID = getNodeID(getEdgeNode2(eItr));
+
+ g.addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
+ getEdgeCosts(eItr));
+ }
+
+ return g;
+ }
+
+};
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
diff --git a/lib/CodeGen/PBQP/ExhaustiveSolver.h b/lib/CodeGen/PBQP/ExhaustiveSolver.h
new file mode 100644
index 0000000..98f7140
--- /dev/null
+++ b/lib/CodeGen/PBQP/ExhaustiveSolver.h
@@ -0,0 +1,93 @@
+#ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
+#define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
+
+#include "Solver.h"
+
+namespace PBQP {
+
+class ExhaustiveSolverImpl {
+private:
+
+ const SimpleGraph &g;
+
+ PBQPNum getSolutionCost(const Solution &solution) const {
+ PBQPNum cost = 0.0;
+
+ for (SimpleGraph::ConstNodeIterator
+ nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ unsigned nodeId = g.getNodeID(nodeItr);
+
+ cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
+ }
+
+ for (SimpleGraph::ConstEdgeIterator
+ edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr),
+ n2 = g.getEdgeNode2Itr(edgeItr);
+ unsigned sol1 = solution.getSelection(g.getNodeID(n1)),
+ sol2 = solution.getSelection(g.getNodeID(n2));
+
+ cost += g.getEdgeCosts(edgeItr)[sol1][sol2];
+ }
+
+ return cost;
+ }
+
+public:
+
+ ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {}
+
+ Solution solve() const {
+ Solution current(g.getNumNodes(), true), optimal(current);
+
+ PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity();
+ bool finished = false;
+
+ while (!finished) {
+ PBQPNum currentCost = getSolutionCost(current);
+
+ if (currentCost < bestCost) {
+ optimal = current;
+ bestCost = currentCost;
+ }
+
+ // assume we're done.
+ finished = true;
+
+ for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+ if (current.getSelection(i) ==
+ (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) {
+ current.setSelection(i, 0);
+ }
+ else {
+ current.setSelection(i, current.getSelection(i) + 1);
+ finished = false;
+ break;
+ }
+ }
+
+ }
+
+ optimal.setSolutionCost(bestCost);
+
+ return optimal;
+ }
+
+};
+
+class ExhaustiveSolver : public Solver {
+public:
+ ~ExhaustiveSolver() {}
+ Solution solve(const SimpleGraph &g) const {
+ ExhaustiveSolverImpl solver(g);
+ return solver.solve();
+ }
+};
+
+}
+
+#endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP
diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h
new file mode 100644
index 0000000..bda5952
--- /dev/null
+++ b/lib/CodeGen/PBQP/GraphBase.h
@@ -0,0 +1,570 @@
+#ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
+#define LLVM_CODEGEN_PBQP_GRAPHBASE_H
+
+#include "PBQPMath.h"
+
+#include <list>
+#include <vector>
+
+namespace PBQP {
+
+// UGLY, but I'm not sure there's a good way around this: We need to be able to
+// look up a Node's "adjacent edge list" structure type before the Node type is
+// fully constructed. We can enable this by pushing the choice of data type
+// out into this traits class.
+template <typename Graph>
+class NodeBaseTraits {
+ public:
+ typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
+ typedef typename AdjEdgeList::iterator AdjEdgeIterator;
+ typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
+};
+
+/// \brief Base for concrete graph classes. Provides a basic set of graph
+/// operations which are useful for PBQP solvers.
+template <typename NodeEntry, typename EdgeEntry>
+class GraphBase {
+private:
+
+ typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
+
+ typedef std::list<NodeEntry> NodeList;
+ typedef std::list<EdgeEntry> EdgeList;
+
+ NodeList nodeList;
+ unsigned nodeListSize;
+
+ EdgeList edgeList;
+ unsigned edgeListSize;
+
+ GraphBase(const ThisGraphT &other) { abort(); }
+ void operator=(const ThisGraphT &other) { abort(); }
+
+public:
+
+ /// \brief Iterates over the nodes of a graph.
+ typedef typename NodeList::iterator NodeIterator;
+ /// \brief Iterates over the nodes of a const graph.
+ typedef typename NodeList::const_iterator ConstNodeIterator;
+ /// \brief Iterates over the edges of a graph.
+ typedef typename EdgeList::iterator EdgeIterator;
+ /// \brief Iterates over the edges of a const graph.
+ typedef typename EdgeList::const_iterator ConstEdgeIterator;
+
+ /// \brief Iterates over the edges attached to a node.
+ typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
+ AdjEdgeIterator;
+
+ /// \brief Iterates over the edges attached to a node in a const graph.
+ typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
+ ConstAdjEdgeIterator;
+
+private:
+
+ typedef std::vector<NodeIterator> IDToNodeMap;
+
+ IDToNodeMap idToNodeMap;
+ bool nodeIDsValid;
+
+ void invalidateNodeIDs() {
+ if (nodeIDsValid) {
+ idToNodeMap.clear();
+ nodeIDsValid = false;
+ }
+ }
+
+ template <typename ItrT>
+ bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
+ for (ItrT t = begin; t != end; ++t) {
+ if (itr == t)
+ return true;
+ }
+
+ return false;
+ }
+
+protected:
+
+ GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
+
+ NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
+ const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
+ return *nodeItr;
+ }
+
+ EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
+ const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
+ return *edgeItr;
+ }
+
+ NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
+ ++nodeListSize;
+
+ invalidateNodeIDs();
+
+ NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
+
+ return newNodeItr;
+ }
+
+ EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
+
+ assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
+ == edgeList.end()) && "Attempt to add duplicate edge.");
+
+ ++edgeListSize;
+
+ // Add the edge to the graph.
+ EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
+
+ // Get a reference to the version in the graph.
+ EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
+
+ // Node entries:
+ NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
+ &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
+
+ unsigned n1Len = node1Entry.getCosts().getLength(),
+ n2Len = node2Entry.getCosts().getLength(),
+ mRows = newEdgeEntry.getCosts().getRows(),
+ mCols = newEdgeEntry.getCosts().getCols();
+
+ // Sanity check on matrix dimensions.
+ assert((n1Len == mRows) && (n2Len == mCols) &&
+ "Matrix dimensions do not match cost vector dimensions.");
+
+ // Create links between nodes and edges.
+ newEdgeEntry.setNode1ThisEdgeItr(
+ node1Entry.addAdjEdge(edgeItr));
+ newEdgeEntry.setNode2ThisEdgeItr(
+ node2Entry.addAdjEdge(edgeItr));
+
+ return edgeItr;
+ }
+
+public:
+
+ /// \brief Returns the number of nodes in this graph.
+ unsigned getNumNodes() const { return nodeListSize; }
+
+ /// \brief Returns the number of edges in this graph.
+ unsigned getNumEdges() const { return edgeListSize; }
+
+ /// \brief Return the cost vector for the given node.
+ Vector& getNodeCosts(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).getCosts();
+ }
+
+ /// \brief Return the cost vector for the give node.
+ const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).getCosts();
+ }
+
+ /// \brief Return the degree of the given node.
+ unsigned getNodeDegree(const NodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).getDegree();
+ }
+
+ /// \brief Assigns sequential IDs to the nodes, starting at 0, which
+ /// remain valid until the next addition or removal of a node.
+ void assignNodeIDs() {
+ unsigned curID = 0;
+ idToNodeMap.resize(getNumNodes());
+ for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr, ++curID) {
+ getNodeEntry(nodeItr).setID(curID);
+ idToNodeMap[curID] = nodeItr;
+ }
+ nodeIDsValid = true;
+ }
+
+ /// \brief Assigns sequential IDs to the nodes using the ordering of the
+ /// given vector.
+ void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
+ assert((getNumNodes() == nodeOrdering.size()) &&
+ "Wrong number of nodes in node ordering.");
+ idToNodeMap = nodeOrdering;
+ for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
+ getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
+ }
+ nodeIDsValid = true;
+ }
+
+ /// \brief Returns true if valid node IDs are assigned, false otherwise.
+ bool areNodeIDsValid() const { return nodeIDsValid; }
+
+ /// \brief Return the numeric ID of the given node.
+ ///
+ /// Calls to this method will result in an assertion failure if there have
+ /// been any node additions or removals since the last call to
+ /// assignNodeIDs().
+ unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
+ assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
+ return getNodeEntry(nodeItr).getID();
+ }
+
+ /// \brief Returns the iterator associated with the given node ID.
+ NodeIterator getNodeItr(unsigned nodeID) {
+ assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
+ return idToNodeMap[nodeID];
+ }
+
+ /// \brief Returns the iterator associated with the given node ID.
+ ConstNodeIterator getNodeItr(unsigned nodeID) const {
+ assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
+ return idToNodeMap[nodeID];
+ }
+
+ /// \brief Removes the given node (and all attached edges) from the graph.
+ void removeNode(const NodeIterator &nodeItr) {
+ assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
+ "Iterator does not belong to this graph!");
+
+ invalidateNodeIDs();
+
+ NodeEntry &nodeEntry = getNodeEntry(nodeItr);
+
+ // We need to copy this out because it will be destroyed as the edges are
+ // removed.
+ typedef std::vector<EdgeIterator> AdjEdgeList;
+ typedef typename AdjEdgeList::iterator AdjEdgeListItr;
+
+ AdjEdgeList adjEdges;
+ adjEdges.reserve(nodeEntry.getDegree());
+ std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
+ std::back_inserter(adjEdges));
+
+ // Iterate over the copied out edges and remove them from the graph.
+ for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
+ itr != end; ++itr) {
+ removeEdge(*itr);
+ }
+
+ // Erase the node from the nodelist.
+ nodeList.erase(nodeItr);
+ --nodeListSize;
+ }
+
+ NodeIterator nodesBegin() { return nodeList.begin(); }
+ ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
+ NodeIterator nodesEnd() { return nodeList.end(); }
+ ConstNodeIterator nodesEnd() const { return nodeList.end(); }
+
+ AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).adjEdgesBegin();
+ }
+
+ ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).adjEdgesBegin();
+ }
+
+ AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).adjEdgesEnd();
+ }
+
+ ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
+ getNodeEntry(nodeItr).adjEdgesEnd();
+ }
+
+ EdgeIterator findEdge(const NodeIterator &node1Itr,
+ const NodeIterator &node2Itr) {
+
+ for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
+ adjEdgeEnd = adjEdgesEnd(node1Itr);
+ adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+ if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
+ (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
+ return *adjEdgeItr;
+ }
+ }
+
+ return edgeList.end();
+ }
+
+ ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
+ const ConstNodeIterator &node2Itr) const {
+
+ for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
+ adjEdgeEnd = adjEdgesEnd(node1Itr);
+ adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) {
+ if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
+ (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
+ return *adjEdgeItr;
+ }
+ }
+
+ return edgeList.end();
+ }
+
+ Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getCosts();
+ }
+
+ const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getCosts();
+ }
+
+ NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getNode1Itr();
+ }
+
+ ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getNode1Itr();
+ }
+
+ NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getNode2Itr();
+ }
+
+ ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getNode2Itr();
+ }
+
+ NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
+ const NodeIterator &nodeItr) {
+
+ EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+ if (nodeItr == edgeEntry.getNode1Itr()) {
+ return edgeEntry.getNode2Itr();
+ }
+ //else
+ return edgeEntry.getNode1Itr();
+ }
+
+ ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
+ const ConstNodeIterator &nodeItr) const {
+
+ const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+ if (nodeItr == edgeEntry.getNode1Itr()) {
+ return edgeEntry.getNode2Itr();
+ }
+ //else
+ return edgeEntry.getNode1Itr();
+ }
+
+ void removeEdge(const EdgeIterator &edgeItr) {
+ assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
+ "Iterator does not belong to this graph!");
+
+ --edgeListSize;
+
+ // Get the edge entry.
+ EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+
+ // Get the nodes entry.
+ NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
+ &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
+
+ // Disconnect the edge from the nodes.
+ node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
+ node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
+
+ // Remove the edge from the graph.
+ edgeList.erase(edgeItr);
+ }
+
+ EdgeIterator edgesBegin() { return edgeList.begin(); }
+ ConstEdgeIterator edgesBegin() const { return edgeList.begin(); }
+ EdgeIterator edgesEnd() { return edgeList.end(); }
+ ConstEdgeIterator edgesEnd() const { return edgeList.end(); }
+
+ void clear() {
+ nodeList.clear();
+ nodeListSize = 0;
+ edgeList.clear();
+ edgeListSize = 0;
+ idToNodeMap.clear();
+ }
+
+ template <typename OStream>
+ void printDot(OStream &os) const {
+
+ assert(areNodeIDsValid() &&
+ "Cannot print a .dot of a graph unless IDs have been assigned.");
+
+ os << "graph {\n";
+
+ for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ os << " node" << getNodeID(nodeItr) << " [ label=\""
+ << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+ }
+
+ os << " edge [ len=" << getNumNodes() << " ]\n";
+
+ for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ os << " node" << getNodeID(getEdgeNode1Itr(edgeItr))
+ << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
+ << " [ label=\"";
+
+ const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+
+ for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
+ os << edgeCosts.getRowAsVector(i) << "\\n";
+ }
+
+ os << "\" ]\n";
+ }
+
+ os << "}\n";
+ }
+
+ template <typename OStream>
+ void printDot(OStream &os) {
+ if (!areNodeIDsValid()) {
+ assignNodeIDs();
+ }
+
+ const_cast<const ThisGraphT*>(this)->printDot(os);
+ }
+
+ template <typename OStream>
+ void dumpTo(OStream &os) const {
+ typedef ConstNodeIterator ConstNodeID;
+
+ assert(areNodeIDsValid() &&
+ "Cannot dump a graph unless IDs have been assigned.");
+
+ for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
+ nItr != nEnd; ++nItr) {
+ os << getNodeID(nItr) << "\n";
+ }
+
+ unsigned edgeNumber = 1;
+ for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
+ eItr != eEnd; ++eItr) {
+
+ os << edgeNumber++ << ": { "
+ << getNodeID(getEdgeNode1Itr(eItr)) << ", "
+ << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
+ }
+
+ }
+
+ template <typename OStream>
+ void dumpTo(OStream &os) {
+ if (!areNodeIDsValid()) {
+ assignNodeIDs();
+ }
+
+ const_cast<const ThisGraphT*>(this)->dumpTo(os);
+ }
+
+};
+
+/// \brief Provides a base from which to derive nodes for GraphBase.
+template <typename NodeImpl, typename EdgeImpl>
+class NodeBase {
+private:
+
+ typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
+ typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
+
+public:
+ typedef typename GraphBaseT::EdgeIterator EdgeIterator;
+
+private:
+ typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
+
+ unsigned degree, id;
+ Vector costs;
+ AdjEdgeList adjEdges;
+
+ void operator=(const NodeBase& other) {
+ assert(false && "Can't assign NodeEntrys.");
+ }
+
+public:
+
+ typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
+ typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
+ ConstAdjEdgeIterator;
+
+ NodeBase(const Vector &costs) : degree(0), costs(costs) {
+ assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
+ }
+
+ Vector& getCosts() { return costs; }
+ const Vector& getCosts() const { return costs; }
+
+ unsigned getDegree() const { return degree; }
+
+ void setID(unsigned id) { this->id = id; }
+ unsigned getID() const { return id; }
+
+ AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
+ ++degree;
+ return adjEdges.insert(adjEdges.end(), edgeItr);
+ }
+
+ void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
+ --degree;
+ adjEdges.erase(adjEdgeItr);
+ }
+
+ AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); }
+ ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); }
+ AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); }
+ ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); }
+
+};
+
+template <typename NodeImpl, typename EdgeImpl>
+class EdgeBase {
+public:
+ typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
+ typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
+
+ typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
+
+private:
+
+ NodeIterator node1Itr, node2Itr;
+ NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
+ Matrix costs;
+
+ void operator=(const EdgeBase &other) {
+ assert(false && "Can't assign EdgeEntrys.");
+ }
+
+public:
+
+ EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+ const Matrix &costs) :
+ node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
+
+ assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
+ "Can't have zero-dimensioned cost matrices");
+ }
+
+ Matrix& getCosts() { return costs; }
+ const Matrix& getCosts() const { return costs; }
+
+ const NodeIterator& getNode1Itr() const { return node1Itr; }
+ const NodeIterator& getNode2Itr() const { return node2Itr; }
+
+ void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
+ this->node1ThisEdgeItr = node1ThisEdgeItr;
+ }
+
+ const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
+ return node1ThisEdgeItr;
+ }
+
+ void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
+ this->node2ThisEdgeItr = node2ThisEdgeItr;
+ }
+
+ const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
+ return node2ThisEdgeItr;
+ }
+
+};
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP
diff --git a/lib/CodeGen/PBQP/GraphGenerator.h b/lib/CodeGen/PBQP/GraphGenerator.h
new file mode 100644
index 0000000..620e21e
--- /dev/null
+++ b/lib/CodeGen/PBQP/GraphGenerator.h
@@ -0,0 +1,195 @@
+#ifndef LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H
+#define LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H
+
+#include "PBQPMath.h"
+
+namespace PBQP {
+
+unsigned randRange(unsigned min, unsigned max) {
+ return min + (rand() % (max - min + 1));
+}
+
+class BasicNodeCostsGenerator {
+private:
+
+ unsigned maxDegree, minCost, maxCost;
+
+
+public:
+
+ BasicNodeCostsGenerator(unsigned maxDegree, unsigned minCost,
+ unsigned maxCost) :
+ maxDegree(maxDegree), minCost(minCost), maxCost(maxCost) { }
+
+ Vector operator()() const {
+ Vector v(randRange(1, maxDegree));
+ for (unsigned i = 0; i < v.getLength(); ++i) {
+ v[i] = randRange(minCost, maxCost);
+ }
+ return v;
+ };
+
+};
+
+class FixedDegreeSpillCostGenerator {
+private:
+
+ unsigned degree, spillCostMin, spillCostMax;
+
+public:
+
+ FixedDegreeSpillCostGenerator(unsigned degree, unsigned spillCostMin,
+ unsigned spillCostMax) :
+ degree(degree), spillCostMin(spillCostMin), spillCostMax(spillCostMax) { }
+
+ Vector operator()() const {
+ Vector v(degree, 0);
+ v[0] = randRange(spillCostMin, spillCostMax);
+ return v;
+ }
+
+};
+
+class BasicEdgeCostsGenerator {
+private:
+
+ unsigned minCost, maxCost;
+
+public:
+
+ BasicEdgeCostsGenerator(unsigned minCost, unsigned maxCost) :
+ minCost(minCost), maxCost(maxCost) {}
+
+ Matrix operator()(const SimpleGraph &g,
+ const SimpleGraph::ConstNodeIterator &n1,
+ const SimpleGraph::ConstNodeIterator &n2) const {
+
+ Matrix m(g.getNodeCosts(n1).getLength(),
+ g.getNodeCosts(n2).getLength());
+
+ for (unsigned i = 0; i < m.getRows(); ++i) {
+ for (unsigned j = 0; j < m.getCols(); ++j) {
+ m[i][j] = randRange(minCost, maxCost);
+ }
+ }
+
+ return m;
+ }
+
+};
+
+class InterferenceCostsGenerator {
+public:
+
+ Matrix operator()(const SimpleGraph &g,
+ const SimpleGraph::ConstNodeIterator &n1,
+ const SimpleGraph::ConstNodeIterator &n2) const {
+
+ unsigned len = g.getNodeCosts(n1).getLength();
+
+ assert(len == g.getNodeCosts(n2).getLength());
+
+ Matrix m(len, len);
+
+ m[0][0] = 0;
+ for (unsigned i = 1; i < len; ++i) {
+ m[i][i] = std::numeric_limits<PBQPNum>::infinity();
+ }
+
+ return m;
+ }
+};
+
+class RingEdgeGenerator {
+public:
+
+ template <typename EdgeCostsGenerator>
+ void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) {
+
+ assert(g.areNodeIDsValid() && "Graph must have valid node IDs.");
+
+ if (g.getNumNodes() < 2)
+ return;
+
+ if (g.getNumNodes() == 2) {
+ SimpleGraph::NodeIterator n1 = g.getNodeItr(0),
+ n2 = g.getNodeItr(1);
+ g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+ return;
+ }
+
+ // Else |V| > 2:
+ for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+ SimpleGraph::NodeIterator
+ n1 = g.getNodeItr(i),
+ n2 = g.getNodeItr((i + 1) % g.getNumNodes());
+ g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+ }
+ }
+
+};
+
+class FullyConnectedEdgeGenerator {
+public:
+
+ template <typename EdgeCostsGenerator>
+ void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) {
+ assert(g.areNodeIDsValid() && "Graph must have valid node IDs.");
+
+ for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+ for (unsigned j = i + 1; j < g.getNumNodes(); ++j) {
+ SimpleGraph::NodeIterator
+ n1 = g.getNodeItr(i),
+ n2 = g.getNodeItr(j);
+ g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+ }
+ }
+ }
+
+};
+
+class RandomEdgeGenerator {
+public:
+
+ template <typename EdgeCostsGenerator>
+ void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) {
+
+ assert(g.areNodeIDsValid() && "Graph must have valid node IDs.");
+
+ for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+ for (unsigned j = i + 1; j < g.getNumNodes(); ++j) {
+ if (rand() % 2 == 0) {
+ SimpleGraph::NodeIterator
+ n1 = g.getNodeItr(i),
+ n2 = g.getNodeItr(j);
+ g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+ }
+ }
+ }
+ }
+
+};
+
+template <typename NodeCostsGenerator,
+ typename EdgesGenerator,
+ typename EdgeCostsGenerator>
+SimpleGraph createRandomGraph(unsigned numNodes,
+ NodeCostsGenerator nodeCostsGen,
+ EdgesGenerator edgeGen,
+ EdgeCostsGenerator edgeCostsGen) {
+
+ SimpleGraph g;
+ for (unsigned n = 0; n < numNodes; ++n) {
+ g.addNode(nodeCostsGen());
+ }
+
+ g.assignNodeIDs();
+
+ edgeGen(g, edgeCostsGen);
+
+ return g;
+}
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H
diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h
new file mode 100644
index 0000000..7088f36
--- /dev/null
+++ b/lib/CodeGen/PBQP/HeuristicSolver.h
@@ -0,0 +1,799 @@
+#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
+#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
+
+#include "Solver.h"
+#include "AnnotatedGraph.h"
+
+#include <limits>
+#include <iostream>
+
+namespace PBQP {
+
+/// \brief Important types for the HeuristicSolverImpl.
+///
+/// Declared seperately to allow access to heuristic classes before the solver
+/// is fully constructed.
+template <typename HeuristicNodeData, typename HeuristicEdgeData>
+class HSITypes {
+public:
+
+ class NodeData;
+ class EdgeData;
+
+ typedef AnnotatedGraph<NodeData, EdgeData> SolverGraph;
+ typedef typename SolverGraph::NodeIterator GraphNodeIterator;
+ typedef typename SolverGraph::EdgeIterator GraphEdgeIterator;
+ typedef typename SolverGraph::AdjEdgeIterator GraphAdjEdgeIterator;
+
+ typedef std::list<GraphNodeIterator> NodeList;
+ typedef typename NodeList::iterator NodeListIterator;
+
+ typedef std::vector<GraphNodeIterator> NodeStack;
+ typedef typename NodeStack::iterator NodeStackIterator;
+
+ class NodeData {
+ friend class EdgeData;
+
+ private:
+
+ typedef std::list<GraphEdgeIterator> LinksList;
+
+ unsigned numLinks;
+ LinksList links, solvedLinks;
+ NodeListIterator bucketItr;
+ HeuristicNodeData heuristicData;
+
+ public:
+
+ typedef typename LinksList::iterator AdjLinkIterator;
+
+ private:
+
+ AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) {
+ ++numLinks;
+ return links.insert(links.end(), edgeItr);
+ }
+
+ void delLink(const AdjLinkIterator &adjLinkItr) {
+ --numLinks;
+ links.erase(adjLinkItr);
+ }
+
+ public:
+
+ NodeData() : numLinks(0) {}
+
+ unsigned getLinkDegree() const { return numLinks; }
+
+ HeuristicNodeData& getHeuristicData() { return heuristicData; }
+ const HeuristicNodeData& getHeuristicData() const {
+ return heuristicData;
+ }
+
+ void setBucketItr(const NodeListIterator &bucketItr) {
+ this->bucketItr = bucketItr;
+ }
+
+ const NodeListIterator& getBucketItr() const {
+ return bucketItr;
+ }
+
+ AdjLinkIterator adjLinksBegin() {
+ return links.begin();
+ }
+
+ AdjLinkIterator adjLinksEnd() {
+ return links.end();
+ }
+
+ void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) {
+ solvedLinks.push_back(solvedLinkItr);
+ }
+
+ AdjLinkIterator solvedLinksBegin() {
+ return solvedLinks.begin();
+ }
+
+ AdjLinkIterator solvedLinksEnd() {
+ return solvedLinks.end();
+ }
+
+ };
+
+ class EdgeData {
+ private:
+
+ SolverGraph &g;
+ GraphNodeIterator node1Itr, node2Itr;
+ HeuristicEdgeData heuristicData;
+ typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr;
+
+ public:
+
+ EdgeData(SolverGraph &g) : g(g) {}
+
+ HeuristicEdgeData& getHeuristicData() { return heuristicData; }
+ const HeuristicEdgeData& getHeuristicData() const {
+ return heuristicData;
+ }
+
+ void setup(const GraphEdgeIterator &thisEdgeItr) {
+ node1Itr = g.getEdgeNode1Itr(thisEdgeItr);
+ node2Itr = g.getEdgeNode2Itr(thisEdgeItr);
+
+ node1ThisEdgeItr = g.getNodeData(node1Itr).addLink(thisEdgeItr);
+ node2ThisEdgeItr = g.getNodeData(node2Itr).addLink(thisEdgeItr);
+ }
+
+ void unlink() {
+ g.getNodeData(node1Itr).delLink(node1ThisEdgeItr);
+ g.getNodeData(node2Itr).delLink(node2ThisEdgeItr);
+ }
+
+ };
+
+};
+
+template <typename Heuristic>
+class HeuristicSolverImpl {
+public:
+ // Typedefs to make life easier:
+ typedef HSITypes<typename Heuristic::NodeData,
+ typename Heuristic::EdgeData> HSIT;
+ typedef typename HSIT::SolverGraph SolverGraph;
+ typedef typename HSIT::NodeData NodeData;
+ typedef typename HSIT::EdgeData EdgeData;
+ typedef typename HSIT::GraphNodeIterator GraphNodeIterator;
+ typedef typename HSIT::GraphEdgeIterator GraphEdgeIterator;
+ typedef typename HSIT::GraphAdjEdgeIterator GraphAdjEdgeIterator;
+
+ typedef typename HSIT::NodeList NodeList;
+ typedef typename HSIT::NodeListIterator NodeListIterator;
+
+ typedef std::vector<GraphNodeIterator> NodeStack;
+ typedef typename NodeStack::iterator NodeStackIterator;
+
+ /*!
+ * \brief Constructor, which performs all the actual solver work.
+ */
+ HeuristicSolverImpl(const SimpleGraph &orig) :
+ solution(orig.getNumNodes(), true)
+ {
+ copyGraph(orig);
+ simplify();
+ setup();
+ computeSolution();
+ computeSolutionCost(orig);
+ }
+
+ /*!
+ * \brief Returns the graph for this solver.
+ */
+ SolverGraph& getGraph() { return g; }
+
+ /*!
+ * \brief Return the solution found by this solver.
+ */
+ const Solution& getSolution() const { return solution; }
+
+private:
+
+ /*!
+ * \brief Add the given node to the appropriate bucket for its link
+ * degree.
+ */
+ void addToBucket(const GraphNodeIterator &nodeItr) {
+ NodeData &nodeData = g.getNodeData(nodeItr);
+
+ switch (nodeData.getLinkDegree()) {
+ case 0: nodeData.setBucketItr(
+ r0Bucket.insert(r0Bucket.end(), nodeItr));
+ break;
+ case 1: nodeData.setBucketItr(
+ r1Bucket.insert(r1Bucket.end(), nodeItr));
+ break;
+ case 2: nodeData.setBucketItr(
+ r2Bucket.insert(r2Bucket.end(), nodeItr));
+ break;
+ default: heuristic.addToRNBucket(nodeItr);
+ break;
+ }
+ }
+
+ /*!
+ * \brief Remove the given node from the appropriate bucket for its link
+ * degree.
+ */
+ void removeFromBucket(const GraphNodeIterator &nodeItr) {
+ NodeData &nodeData = g.getNodeData(nodeItr);
+
+ switch (nodeData.getLinkDegree()) {
+ case 0: r0Bucket.erase(nodeData.getBucketItr()); break;
+ case 1: r1Bucket.erase(nodeData.getBucketItr()); break;
+ case 2: r2Bucket.erase(nodeData.getBucketItr()); break;
+ default: heuristic.removeFromRNBucket(nodeItr); break;
+ }
+ }
+
+public:
+
+ /*!
+ * \brief Add a link.
+ */
+ void addLink(const GraphEdgeIterator &edgeItr) {
+ g.getEdgeData(edgeItr).setup(edgeItr);
+
+ if ((g.getNodeData(g.getEdgeNode1Itr(edgeItr)).getLinkDegree() > 2) ||
+ (g.getNodeData(g.getEdgeNode2Itr(edgeItr)).getLinkDegree() > 2)) {
+ heuristic.handleAddLink(edgeItr);
+ }
+ }
+
+ /*!
+ * \brief Remove link, update info for node.
+ *
+ * Only updates information for the given node, since usually the other
+ * is about to be removed.
+ */
+ void removeLink(const GraphEdgeIterator &edgeItr,
+ const GraphNodeIterator &nodeItr) {
+
+ if (g.getNodeData(nodeItr).getLinkDegree() > 2) {
+ heuristic.handleRemoveLink(edgeItr, nodeItr);
+ }
+ g.getEdgeData(edgeItr).unlink();
+ }
+
+ /*!
+ * \brief Remove link, update info for both nodes. Useful for R2 only.
+ */
+ void removeLinkR2(const GraphEdgeIterator &edgeItr) {
+ GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr);
+
+ if (g.getNodeData(node1Itr).getLinkDegree() > 2) {
+ heuristic.handleRemoveLink(edgeItr, node1Itr);
+ }
+ removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr));
+ }
+
+ /*!
+ * \brief Removes all links connected to the given node.
+ */
+ void unlinkNode(const GraphNodeIterator &nodeItr) {
+ NodeData &nodeData = g.getNodeData(nodeItr);
+
+ typedef std::vector<GraphEdgeIterator> TempEdgeList;
+
+ TempEdgeList edgesToUnlink;
+ edgesToUnlink.reserve(nodeData.getLinkDegree());
+
+ // Copy adj edges into a temp vector. We want to destroy them during
+ // the unlink, and we can't do that while we're iterating over them.
+ std::copy(nodeData.adjLinksBegin(), nodeData.adjLinksEnd(),
+ std::back_inserter(edgesToUnlink));
+
+ for (typename TempEdgeList::iterator
+ edgeItr = edgesToUnlink.begin(), edgeEnd = edgesToUnlink.end();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ GraphNodeIterator otherNode = g.getEdgeOtherNode(*edgeItr, nodeItr);
+
+ removeFromBucket(otherNode);
+ removeLink(*edgeItr, otherNode);
+ addToBucket(otherNode);
+ }
+ }
+
+ /*!
+ * \brief Push the given node onto the stack to be solved with
+ * backpropagation.
+ */
+ void pushStack(const GraphNodeIterator &nodeItr) {
+ stack.push_back(nodeItr);
+ }
+
+ /*!
+ * \brief Set the solution of the given node.
+ */
+ void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) {
+ solution.setSelection(g.getNodeID(nodeItr), solIndex);
+
+ for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
+ adjEdgeEnd = g.adjEdgesEnd(nodeItr);
+ adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+ GraphEdgeIterator edgeItr(*adjEdgeItr);
+ GraphNodeIterator adjNodeItr(g.getEdgeOtherNode(edgeItr, nodeItr));
+ g.getNodeData(adjNodeItr).addSolvedLink(edgeItr);
+ }
+ }
+
+private:
+
+ SolverGraph g;
+ Heuristic heuristic;
+ Solution solution;
+
+ NodeList r0Bucket,
+ r1Bucket,
+ r2Bucket;
+
+ NodeStack stack;
+
+ // Copy the SimpleGraph into an annotated graph which we can use for reduction.
+ void copyGraph(const SimpleGraph &orig) {
+
+ assert((g.getNumEdges() == 0) && (g.getNumNodes() == 0) &&
+ "Graph should be empty prior to solver setup.");
+
+ assert(orig.areNodeIDsValid() &&
+ "Cannot copy from a graph with invalid node IDs.");
+
+ std::vector<GraphNodeIterator> newNodeItrs;
+
+ for (unsigned nodeID = 0; nodeID < orig.getNumNodes(); ++nodeID) {
+ newNodeItrs.push_back(
+ g.addNode(orig.getNodeCosts(orig.getNodeItr(nodeID)), NodeData()));
+ }
+
+ for (SimpleGraph::ConstEdgeIterator
+ origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd();
+ origEdgeItr != origEdgeEnd; ++origEdgeItr) {
+
+ unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)),
+ id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr));
+
+ g.addEdge(newNodeItrs[id1], newNodeItrs[id2],
+ orig.getEdgeCosts(origEdgeItr), EdgeData(g));
+ }
+
+ // Assign IDs to the new nodes using the ordering from the old graph,
+ // this will lead to nodes in the new graph getting the same ID as the
+ // corresponding node in the old graph.
+ g.assignNodeIDs(newNodeItrs);
+ }
+
+ // Simplify the annotated graph by eliminating independent edges and trivial
+ // nodes.
+ void simplify() {
+ disconnectTrivialNodes();
+ eliminateIndependentEdges();
+ }
+
+ // Eliminate trivial nodes.
+ void disconnectTrivialNodes() {
+ for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ if (g.getNodeCosts(nodeItr).getLength() == 1) {
+
+ std::vector<GraphEdgeIterator> edgesToRemove;
+
+ for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
+ adjEdgeEnd = g.adjEdgesEnd(nodeItr);
+ adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+
+ GraphEdgeIterator edgeItr = *adjEdgeItr;
+
+ if (g.getEdgeNode1Itr(edgeItr) == nodeItr) {
+ GraphNodeIterator otherNodeItr = g.getEdgeNode2Itr(edgeItr);
+ g.getNodeCosts(otherNodeItr) +=
+ g.getEdgeCosts(edgeItr).getRowAsVector(0);
+ }
+ else {
+ GraphNodeIterator otherNodeItr = g.getEdgeNode1Itr(edgeItr);
+ g.getNodeCosts(otherNodeItr) +=
+ g.getEdgeCosts(edgeItr).getColAsVector(0);
+ }
+
+ edgesToRemove.push_back(edgeItr);
+ }
+
+ while (!edgesToRemove.empty()) {
+ g.removeEdge(edgesToRemove.back());
+ edgesToRemove.pop_back();
+ }
+ }
+ }
+ }
+
+ void eliminateIndependentEdges() {
+ std::vector<GraphEdgeIterator> edgesToProcess;
+
+ for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+ edgesToProcess.push_back(edgeItr);
+ }
+
+ while (!edgesToProcess.empty()) {
+ tryToEliminateEdge(edgesToProcess.back());
+ edgesToProcess.pop_back();
+ }
+ }
+
+ void tryToEliminateEdge(const GraphEdgeIterator &edgeItr) {
+ if (tryNormaliseEdgeMatrix(edgeItr)) {
+ g.removeEdge(edgeItr);
+ }
+ }
+
+ bool tryNormaliseEdgeMatrix(const GraphEdgeIterator &edgeItr) {
+
+ Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
+ Vector &uCosts = g.getNodeCosts(g.getEdgeNode1Itr(edgeItr)),
+ &vCosts = g.getNodeCosts(g.getEdgeNode2Itr(edgeItr));
+
+ for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
+ PBQPNum rowMin = edgeCosts.getRowMin(r);
+ uCosts[r] += rowMin;
+ if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
+ edgeCosts.subFromRow(r, rowMin);
+ }
+ else {
+ edgeCosts.setRow(r, 0);
+ }
+ }
+
+ for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
+ PBQPNum colMin = edgeCosts.getColMin(c);
+ vCosts[c] += colMin;
+ if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
+ edgeCosts.subFromCol(c, colMin);
+ }
+ else {
+ edgeCosts.setCol(c, 0);
+ }
+ }
+
+ return edgeCosts.isZero();
+ }
+
+ void setup() {
+ setupLinks();
+ heuristic.initialise(*this);
+ setupBuckets();
+ }
+
+ void setupLinks() {
+ for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+ g.getEdgeData(edgeItr).setup(edgeItr);
+ }
+ }
+
+ void setupBuckets() {
+ for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+ addToBucket(nodeItr);
+ }
+ }
+
+ void computeSolution() {
+ assert(g.areNodeIDsValid() &&
+ "Nodes cannot be added/removed during reduction.");
+
+ reduce();
+ computeTrivialSolutions();
+ backpropagate();
+ }
+
+ void printNode(const GraphNodeIterator &nodeItr) {
+
+ std::cerr << "Node " << g.getNodeID(nodeItr) << " (" << &*nodeItr << "):\n"
+ << " costs = " << g.getNodeCosts(nodeItr) << "\n"
+ << " link degree = " << g.getNodeData(nodeItr).getLinkDegree() << "\n"
+ << " links = [ ";
+
+ for (typename HSIT::NodeData::AdjLinkIterator
+ aeItr = g.getNodeData(nodeItr).adjLinksBegin(),
+ aeEnd = g.getNodeData(nodeItr).adjLinksEnd();
+ aeItr != aeEnd; ++aeItr) {
+ std::cerr << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr))
+ << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr))
+ << ") ";
+ }
+ std::cout << "]\n";
+ }
+
+ void dumpState() {
+
+ std::cerr << "\n";
+
+ for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+ printNode(nodeItr);
+ }
+
+ NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket };
+
+ for (unsigned b = 0; b < 3; ++b) {
+ NodeList &bucket = *buckets[b];
+
+ std::cerr << "Bucket " << b << ": [ ";
+
+ for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end();
+ nItr != nEnd; ++nItr) {
+ std::cerr << g.getNodeID(*nItr) << " ";
+ }
+
+ std::cerr << "]\n";
+ }
+
+ std::cerr << "Stack: [ ";
+ for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end();
+ nsItr != nsEnd; ++nsItr) {
+ std::cerr << g.getNodeID(*nsItr) << " ";
+ }
+ std::cerr << "]\n";
+ }
+
+ void reduce() {
+ bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() &&
+ heuristic.rNBucketEmpty();
+
+ while (!reductionFinished) {
+
+ if (!r1Bucket.empty()) {
+ processR1();
+ }
+ else if (!r2Bucket.empty()) {
+ processR2();
+ }
+ else if (!heuristic.rNBucketEmpty()) {
+ solution.setProvedOptimal(false);
+ solution.incRNReductions();
+ heuristic.processRN();
+ }
+ else reductionFinished = true;
+ }
+
+ };
+
+ void processR1() {
+
+ // Remove the first node in the R0 bucket:
+ GraphNodeIterator xNodeItr = r1Bucket.front();
+ r1Bucket.pop_front();
+
+ solution.incR1Reductions();
+
+ //std::cerr << "Applying R1 to " << g.getNodeID(xNodeItr) << "\n";
+
+ assert((g.getNodeData(xNodeItr).getLinkDegree() == 1) &&
+ "Node in R1 bucket has degree != 1");
+
+ GraphEdgeIterator edgeItr = *g.getNodeData(xNodeItr).adjLinksBegin();
+
+ const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
+
+ const Vector &xCosts = g.getNodeCosts(xNodeItr);
+ unsigned xLen = xCosts.getLength();
+
+ // Duplicate a little code to avoid transposing matrices:
+ if (xNodeItr == g.getEdgeNode1Itr(edgeItr)) {
+ GraphNodeIterator yNodeItr = g.getEdgeNode2Itr(edgeItr);
+ Vector &yCosts = g.getNodeCosts(yNodeItr);
+ unsigned yLen = yCosts.getLength();
+
+ for (unsigned j = 0; j < yLen; ++j) {
+ PBQPNum min = edgeCosts[0][j] + xCosts[0];
+ for (unsigned i = 1; i < xLen; ++i) {
+ PBQPNum c = edgeCosts[i][j] + xCosts[i];
+ if (c < min)
+ min = c;
+ }
+ yCosts[j] += min;
+ }
+ }
+ else {
+ GraphNodeIterator yNodeItr = g.getEdgeNode1Itr(edgeItr);
+ Vector &yCosts = g.getNodeCosts(yNodeItr);
+ unsigned yLen = yCosts.getLength();
+
+ for (unsigned i = 0; i < yLen; ++i) {
+ PBQPNum min = edgeCosts[i][0] + xCosts[0];
+
+ for (unsigned j = 1; j < xLen; ++j) {
+ PBQPNum c = edgeCosts[i][j] + xCosts[j];
+ if (c < min)
+ min = c;
+ }
+ yCosts[i] += min;
+ }
+ }
+
+ unlinkNode(xNodeItr);
+ pushStack(xNodeItr);
+ }
+
+ void processR2() {
+
+ GraphNodeIterator xNodeItr = r2Bucket.front();
+ r2Bucket.pop_front();
+
+ solution.incR2Reductions();
+
+ // Unlink is unsafe here. At some point it may optimistically more a node
+ // to a lower-degree list when its degree will later rise, or vice versa,
+ // violating the assumption that node degrees monotonically decrease
+ // during the reduction phase. Instead we'll bucket shuffle manually.
+ pushStack(xNodeItr);
+
+ assert((g.getNodeData(xNodeItr).getLinkDegree() == 2) &&
+ "Node in R2 bucket has degree != 2");
+
+ const Vector &xCosts = g.getNodeCosts(xNodeItr);
+
+ typename NodeData::AdjLinkIterator tempItr =
+ g.getNodeData(xNodeItr).adjLinksBegin();
+
+ GraphEdgeIterator yxEdgeItr = *tempItr,
+ zxEdgeItr = *(++tempItr);
+
+ GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr),
+ zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr);
+
+ removeFromBucket(yNodeItr);
+ removeFromBucket(zNodeItr);
+
+ removeLink(yxEdgeItr, yNodeItr);
+ removeLink(zxEdgeItr, zNodeItr);
+
+ // Graph some of the costs:
+ bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr),
+ flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr);
+
+ const Matrix *yxCosts = flipEdge1 ?
+ new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) :
+ &g.getEdgeCosts(yxEdgeItr),
+ *zxCosts = flipEdge2 ?
+ new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) :
+ &g.getEdgeCosts(zxEdgeItr);
+
+ unsigned xLen = xCosts.getLength(),
+ yLen = yxCosts->getRows(),
+ zLen = zxCosts->getRows();
+
+ // Compute delta:
+ Matrix delta(yLen, zLen);
+
+ for (unsigned i = 0; i < yLen; ++i) {
+ for (unsigned j = 0; j < zLen; ++j) {
+ PBQPNum min = (*yxCosts)[i][0] + (*zxCosts)[j][0] + xCosts[0];
+ for (unsigned k = 1; k < xLen; ++k) {
+ PBQPNum c = (*yxCosts)[i][k] + (*zxCosts)[j][k] + xCosts[k];
+ if (c < min) {
+ min = c;
+ }
+ }
+ delta[i][j] = min;
+ }
+ }
+
+ if (flipEdge1)
+ delete yxCosts;
+
+ if (flipEdge2)
+ delete zxCosts;
+
+ // Deal with the potentially induced yz edge.
+ GraphEdgeIterator yzEdgeItr = g.findEdge(yNodeItr, zNodeItr);
+ if (yzEdgeItr == g.edgesEnd()) {
+ yzEdgeItr = g.addEdge(yNodeItr, zNodeItr, delta, EdgeData(g));
+ }
+ else {
+ // There was an edge, but we're going to screw with it. Delete the old
+ // link, update the costs. We'll re-link it later.
+ removeLinkR2(yzEdgeItr);
+ g.getEdgeCosts(yzEdgeItr) +=
+ (yNodeItr == g.getEdgeNode1Itr(yzEdgeItr)) ?
+ delta : delta.transpose();
+ }
+
+ bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr);
+
+ // Nulled the edge, remove it entirely.
+ if (nullCostEdge) {
+ g.removeEdge(yzEdgeItr);
+ }
+ else {
+ // Edge remains - re-link it.
+ addLink(yzEdgeItr);
+ }
+
+ addToBucket(yNodeItr);
+ addToBucket(zNodeItr);
+ }
+
+ void computeTrivialSolutions() {
+
+ for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end();
+ r0Itr != r0End; ++r0Itr) {
+ GraphNodeIterator nodeItr = *r0Itr;
+
+ solution.incR0Reductions();
+ setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex());
+ }
+
+ }
+
+ void backpropagate() {
+ while (!stack.empty()) {
+ computeSolution(stack.back());
+ stack.pop_back();
+ }
+ }
+
+ void computeSolution(const GraphNodeIterator &nodeItr) {
+
+ NodeData &nodeData = g.getNodeData(nodeItr);
+
+ Vector v(g.getNodeCosts(nodeItr));
+
+ // Solve based on existing links.
+ for (typename NodeData::AdjLinkIterator
+ solvedLinkItr = nodeData.solvedLinksBegin(),
+ solvedLinkEnd = nodeData.solvedLinksEnd();
+ solvedLinkItr != solvedLinkEnd; ++solvedLinkItr) {
+
+ GraphEdgeIterator solvedEdgeItr(*solvedLinkItr);
+ Matrix &edgeCosts = g.getEdgeCosts(solvedEdgeItr);
+
+ if (nodeItr == g.getEdgeNode1Itr(solvedEdgeItr)) {
+ GraphNodeIterator adjNode(g.getEdgeNode2Itr(solvedEdgeItr));
+ unsigned adjSolution =
+ solution.getSelection(g.getNodeID(adjNode));
+ v += edgeCosts.getColAsVector(adjSolution);
+ }
+ else {
+ GraphNodeIterator adjNode(g.getEdgeNode1Itr(solvedEdgeItr));
+ unsigned adjSolution =
+ solution.getSelection(g.getNodeID(adjNode));
+ v += edgeCosts.getRowAsVector(adjSolution);
+ }
+
+ }
+
+ setSolution(nodeItr, v.minIndex());
+ }
+
+ void computeSolutionCost(const SimpleGraph &orig) {
+ PBQPNum cost = 0.0;
+
+ for (SimpleGraph::ConstNodeIterator
+ nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ unsigned nodeId = orig.getNodeID(nodeItr);
+
+ cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
+ }
+
+ for (SimpleGraph::ConstEdgeIterator
+ edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ SimpleGraph::ConstNodeIterator n1 = orig.getEdgeNode1Itr(edgeItr),
+ n2 = orig.getEdgeNode2Itr(edgeItr);
+ unsigned sol1 = solution.getSelection(orig.getNodeID(n1)),
+ sol2 = solution.getSelection(orig.getNodeID(n2));
+
+ cost += orig.getEdgeCosts(edgeItr)[sol1][sol2];
+ }
+
+ solution.setSolutionCost(cost);
+ }
+
+};
+
+template <typename Heuristic>
+class HeuristicSolver : public Solver {
+public:
+ Solution solve(const SimpleGraph &g) const {
+ HeuristicSolverImpl<Heuristic> solverImpl(g);
+ return solverImpl.getSolution();
+ }
+};
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h
new file mode 100644
index 0000000..fd37f5c
--- /dev/null
+++ b/lib/CodeGen/PBQP/Heuristics/Briggs.h
@@ -0,0 +1,385 @@
+#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
+#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
+
+#include "../HeuristicSolver.h"
+
+#include <set>
+
+namespace PBQP {
+namespace Heuristics {
+
+class Briggs {
+ public:
+
+ class NodeData;
+ class EdgeData;
+
+ private:
+
+ typedef HeuristicSolverImpl<Briggs> Solver;
+ typedef HSITypes<NodeData, EdgeData> HSIT;
+ typedef HSIT::SolverGraph SolverGraph;
+ typedef HSIT::GraphNodeIterator GraphNodeIterator;
+ typedef HSIT::GraphEdgeIterator GraphEdgeIterator;
+
+ class LinkDegreeComparator {
+ public:
+ LinkDegreeComparator() : g(0) {}
+ LinkDegreeComparator(SolverGraph *g) : g(g) {}
+
+ bool operator()(const GraphNodeIterator &node1Itr,
+ const GraphNodeIterator &node2Itr) const {
+ assert((g != 0) && "Graph object not set, cannot access node data.");
+ unsigned n1Degree = g->getNodeData(node1Itr).getLinkDegree(),
+ n2Degree = g->getNodeData(node2Itr).getLinkDegree();
+ if (n1Degree > n2Degree) {
+ return true;
+ }
+ else if (n1Degree < n2Degree) {
+ return false;
+ }
+ // else they're "equal" by degree, differentiate based on ID.
+ return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+ }
+
+ private:
+ SolverGraph *g;
+ };
+
+ class SpillPriorityComparator {
+ public:
+ SpillPriorityComparator() : g(0) {}
+ SpillPriorityComparator(SolverGraph *g) : g(g) {}
+
+ bool operator()(const GraphNodeIterator &node1Itr,
+ const GraphNodeIterator &node2Itr) const {
+ assert((g != 0) && "Graph object not set, cannot access node data.");
+ PBQPNum cost1 =
+ g->getNodeCosts(node1Itr)[0] /
+ g->getNodeData(node1Itr).getLinkDegree(),
+ cost2 =
+ g->getNodeCosts(node2Itr)[0] /
+ g->getNodeData(node2Itr).getLinkDegree();
+
+ if (cost1 < cost2) {
+ return true;
+ }
+ else if (cost1 > cost2) {
+ return false;
+ }
+ // else they'er "equal" again, differentiate based on address again.
+ return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+ }
+
+ private:
+ SolverGraph *g;
+ };
+
+ typedef std::set<GraphNodeIterator, LinkDegreeComparator>
+ RNAllocableNodeList;
+ typedef RNAllocableNodeList::iterator RNAllocableNodeListIterator;
+
+ typedef std::set<GraphNodeIterator, SpillPriorityComparator>
+ RNUnallocableNodeList;
+ typedef RNUnallocableNodeList::iterator RNUnallocableNodeListIterator;
+
+ public:
+
+ class NodeData {
+ private:
+ RNAllocableNodeListIterator rNAllocableNodeListItr;
+ RNUnallocableNodeListIterator rNUnallocableNodeListItr;
+ unsigned numRegOptions, numDenied, numSafe;
+ std::vector<unsigned> unsafeDegrees;
+ bool allocable;
+
+ void addRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
+ const GraphEdgeIterator &edgeItr, bool add) {
+
+ //assume we're adding...
+ unsigned udTarget = 0, dir = 1;
+
+ if (!add) {
+ udTarget = 1;
+ dir = -1;
+ }
+
+ EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData();
+
+ EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd;
+
+ if (nodeItr == g.getEdgeNode1Itr(edgeItr)) {
+ numDenied += (dir * linkEdgeData.getWorstDegree());
+ edgeUnsafeBegin = linkEdgeData.unsafeBegin();
+ edgeUnsafeEnd = linkEdgeData.unsafeEnd();
+ }
+ else {
+ numDenied += (dir * linkEdgeData.getReverseWorstDegree());
+ edgeUnsafeBegin = linkEdgeData.reverseUnsafeBegin();
+ edgeUnsafeEnd = linkEdgeData.reverseUnsafeEnd();
+ }
+
+ assert((unsafeDegrees.size() ==
+ static_cast<unsigned>(
+ std::distance(edgeUnsafeBegin, edgeUnsafeEnd)))
+ && "Unsafe array size mismatch.");
+
+ std::vector<unsigned>::iterator unsafeDegreesItr =
+ unsafeDegrees.begin();
+
+ for (EdgeData::ConstUnsafeIterator edgeUnsafeItr = edgeUnsafeBegin;
+ edgeUnsafeItr != edgeUnsafeEnd;
+ ++edgeUnsafeItr, ++unsafeDegreesItr) {
+
+ if ((*edgeUnsafeItr == 1) && (*unsafeDegreesItr == udTarget)) {
+ numSafe -= dir;
+ }
+ *unsafeDegreesItr += (dir * (*edgeUnsafeItr));
+ }
+
+ allocable = (numDenied < numRegOptions) || (numSafe > 0);
+ }
+
+ public:
+
+ void setup(SolverGraph &g, const GraphNodeIterator &nodeItr) {
+
+ numRegOptions = g.getNodeCosts(nodeItr).getLength() - 1;
+
+ numSafe = numRegOptions; // Optimistic, correct below.
+ numDenied = 0; // Also optimistic.
+ unsafeDegrees.resize(numRegOptions, 0);
+
+ HSIT::NodeData &nodeData = g.getNodeData(nodeItr);
+
+ for (HSIT::NodeData::AdjLinkIterator
+ adjLinkItr = nodeData.adjLinksBegin(),
+ adjLinkEnd = nodeData.adjLinksEnd();
+ adjLinkItr != adjLinkEnd; ++adjLinkItr) {
+
+ addRemoveLink(g, nodeItr, *adjLinkItr, true);
+ }
+ }
+
+ bool isAllocable() const { return allocable; }
+
+ void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
+ const GraphEdgeIterator &adjEdge) {
+ addRemoveLink(g, nodeItr, adjEdge, true);
+ }
+
+ void handleRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
+ const GraphEdgeIterator &adjEdge) {
+ addRemoveLink(g, nodeItr, adjEdge, false);
+ }
+
+ void setRNAllocableNodeListItr(
+ const RNAllocableNodeListIterator &rNAllocableNodeListItr) {
+
+ this->rNAllocableNodeListItr = rNAllocableNodeListItr;
+ }
+
+ RNAllocableNodeListIterator getRNAllocableNodeListItr() const {
+ return rNAllocableNodeListItr;
+ }
+
+ void setRNUnallocableNodeListItr(
+ const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) {
+
+ this->rNUnallocableNodeListItr = rNUnallocableNodeListItr;
+ }
+
+ RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const {
+ return rNUnallocableNodeListItr;
+ }
+
+
+ };
+
+ class EdgeData {
+ private:
+
+ typedef std::vector<unsigned> UnsafeArray;
+
+ unsigned worstDegree,
+ reverseWorstDegree;
+ UnsafeArray unsafe, reverseUnsafe;
+
+ public:
+
+ EdgeData() : worstDegree(0), reverseWorstDegree(0) {}
+
+ typedef UnsafeArray::const_iterator ConstUnsafeIterator;
+
+ void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) {
+ const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
+ unsigned numRegs = edgeCosts.getRows() - 1,
+ numReverseRegs = edgeCosts.getCols() - 1;
+
+ unsafe.resize(numRegs, 0);
+ reverseUnsafe.resize(numReverseRegs, 0);
+
+ std::vector<unsigned> rowInfCounts(numRegs, 0),
+ colInfCounts(numReverseRegs, 0);
+
+ for (unsigned i = 0; i < numRegs; ++i) {
+ for (unsigned j = 0; j < numReverseRegs; ++j) {
+ if (edgeCosts[i + 1][j + 1] ==
+ std::numeric_limits<PBQPNum>::infinity()) {
+ unsafe[i] = 1;
+ reverseUnsafe[j] = 1;
+ ++rowInfCounts[i];
+ ++colInfCounts[j];
+
+ if (colInfCounts[j] > worstDegree) {
+ worstDegree = colInfCounts[j];
+ }
+
+ if (rowInfCounts[i] > reverseWorstDegree) {
+ reverseWorstDegree = rowInfCounts[i];
+ }
+ }
+ }
+ }
+ }
+
+ unsigned getWorstDegree() const { return worstDegree; }
+ unsigned getReverseWorstDegree() const { return reverseWorstDegree; }
+ ConstUnsafeIterator unsafeBegin() const { return unsafe.begin(); }
+ ConstUnsafeIterator unsafeEnd() const { return unsafe.end(); }
+ ConstUnsafeIterator reverseUnsafeBegin() const {
+ return reverseUnsafe.begin();
+ }
+ ConstUnsafeIterator reverseUnsafeEnd() const {
+ return reverseUnsafe.end();
+ }
+ };
+
+ void initialise(Solver &solver) {
+ this->s = &solver;
+ g = &s->getGraph();
+ rNAllocableBucket = RNAllocableNodeList(LinkDegreeComparator(g));
+ rNUnallocableBucket =
+ RNUnallocableNodeList(SpillPriorityComparator(g));
+
+ for (GraphEdgeIterator
+ edgeItr = g->edgesBegin(), edgeEnd = g->edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
+ }
+
+ for (GraphNodeIterator
+ nodeItr = g->nodesBegin(), nodeEnd = g->nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ g->getNodeData(nodeItr).getHeuristicData().setup(*g, nodeItr);
+ }
+ }
+
+ void addToRNBucket(const GraphNodeIterator &nodeItr) {
+ NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
+
+ if (nodeData.isAllocable()) {
+ nodeData.setRNAllocableNodeListItr(
+ rNAllocableBucket.insert(rNAllocableBucket.begin(), nodeItr));
+ }
+ else {
+ nodeData.setRNUnallocableNodeListItr(
+ rNUnallocableBucket.insert(rNUnallocableBucket.begin(), nodeItr));
+ }
+ }
+
+ void removeFromRNBucket(const GraphNodeIterator &nodeItr) {
+ NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
+
+ if (nodeData.isAllocable()) {
+ rNAllocableBucket.erase(nodeData.getRNAllocableNodeListItr());
+ }
+ else {
+ rNUnallocableBucket.erase(nodeData.getRNUnallocableNodeListItr());
+ }
+ }
+
+ void handleAddLink(const GraphEdgeIterator &edgeItr) {
+ // We assume that if we got here this edge is attached to at least
+ // one high degree node.
+ g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
+
+ GraphNodeIterator n1Itr = g->getEdgeNode1Itr(edgeItr),
+ n2Itr = g->getEdgeNode2Itr(edgeItr);
+
+ HSIT::NodeData &n1Data = g->getNodeData(n1Itr),
+ &n2Data = g->getNodeData(n2Itr);
+
+ if (n1Data.getLinkDegree() > 2) {
+ n1Data.getHeuristicData().handleAddLink(*g, n1Itr, edgeItr);
+ }
+ if (n2Data.getLinkDegree() > 2) {
+ n2Data.getHeuristicData().handleAddLink(*g, n2Itr, edgeItr);
+ }
+ }
+
+ void handleRemoveLink(const GraphEdgeIterator &edgeItr,
+ const GraphNodeIterator &nodeItr) {
+ NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
+ nodeData.handleRemoveLink(*g, nodeItr, edgeItr);
+ }
+
+ void processRN() {
+
+ /*
+ std::cerr << "processRN():\n"
+ << " rNAllocable = [ ";
+ for (RNAllocableNodeListIterator nItr = rNAllocableBucket.begin(),
+ nEnd = rNAllocableBucket.end();
+ nItr != nEnd; ++nItr) {
+ std::cerr << g->getNodeID(*nItr) << " (" << g->getNodeData(*nItr).getLinkDegree() << ") ";
+ }
+ std::cerr << "]\n"
+ << " rNUnallocable = [ ";
+ for (RNUnallocableNodeListIterator nItr = rNUnallocableBucket.begin(),
+ nEnd = rNUnallocableBucket.end();
+ nItr != nEnd; ++nItr) {
+ float bCost = g->getNodeCosts(*nItr)[0] / g->getNodeData(*nItr).getLinkDegree();
+ std::cerr << g->getNodeID(*nItr) << " (" << bCost << ") ";
+ }
+ std::cerr << "]\n";
+ */
+
+ if (!rNAllocableBucket.empty()) {
+ GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin();
+ //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n";
+ rNAllocableBucket.erase(rNAllocableBucket.begin());
+ s->pushStack(selectedNodeItr);
+ s->unlinkNode(selectedNodeItr);
+ }
+ else {
+ GraphNodeIterator selectedNodeItr = *rNUnallocableBucket.begin();
+ //std::cerr << "RN optimistically pushing " << g->getNodeID(selectedNodeItr) << "\n";
+ rNUnallocableBucket.erase(rNUnallocableBucket.begin());
+ s->pushStack(selectedNodeItr);
+ s->unlinkNode(selectedNodeItr);
+ }
+
+ }
+
+ bool rNBucketEmpty() const {
+ return (rNAllocableBucket.empty() && rNUnallocableBucket.empty());
+ }
+
+private:
+
+ Solver *s;
+ SolverGraph *g;
+ RNAllocableNodeList rNAllocableBucket;
+ RNUnallocableNodeList rNUnallocableBucket;
+};
+
+
+
+}
+}
+
+
+#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
diff --git a/lib/CodeGen/PBQP/PBQPMath.h b/lib/CodeGen/PBQP/PBQPMath.h
new file mode 100644
index 0000000..dc184fe
--- /dev/null
+++ b/lib/CodeGen/PBQP/PBQPMath.h
@@ -0,0 +1,279 @@
+#ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H
+#define LLVM_CODEGEN_PBQP_PBQPMATH_H
+
+#include <cassert>
+#include <algorithm>
+#include <functional>
+
+namespace PBQP {
+
+typedef double 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 throw () {
+ 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 throw () { return rows; }
+
+ /// \brief Return the number of cols in this matrix.
+ unsigned getCols() const throw () { 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_PBQPMATH_HPP
diff --git a/lib/CodeGen/PBQP/SimpleGraph.h b/lib/CodeGen/PBQP/SimpleGraph.h
new file mode 100644
index 0000000..595269c
--- /dev/null
+++ b/lib/CodeGen/PBQP/SimpleGraph.h
@@ -0,0 +1,86 @@
+#ifndef LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
+#define LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
+
+#include "GraphBase.h"
+
+namespace PBQP {
+
+class SimpleEdge;
+
+class SimpleNode : public NodeBase<SimpleNode, SimpleEdge> {
+public:
+ SimpleNode(const Vector &costs) :
+ NodeBase<SimpleNode, SimpleEdge>(costs) {}
+};
+
+class SimpleEdge : public EdgeBase<SimpleNode, SimpleEdge> {
+public:
+ SimpleEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+ const Matrix &costs) :
+ EdgeBase<SimpleNode, SimpleEdge>(node1Itr, node2Itr, costs) {}
+};
+
+class SimpleGraph : public GraphBase<SimpleNode, SimpleEdge> {
+private:
+
+ typedef GraphBase<SimpleNode, SimpleEdge> PGraph;
+
+ void copyFrom(const SimpleGraph &other) {
+ assert(other.areNodeIDsValid() &&
+ "Cannot copy from another graph unless IDs have been assigned.");
+
+ std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
+
+ for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
+ nItr != nEnd; ++nItr) {
+ newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
+ }
+
+ for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
+ eItr != eEnd; ++eItr) {
+
+ unsigned node1ID = other.getNodeID(other.getEdgeNode1Itr(eItr)),
+ node2ID = other.getNodeID(other.getEdgeNode2Itr(eItr));
+
+ addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
+ other.getEdgeCosts(eItr));
+ }
+ }
+
+ void copyFrom(SimpleGraph &other) {
+ if (!other.areNodeIDsValid()) {
+ other.assignNodeIDs();
+ }
+ copyFrom(const_cast<const SimpleGraph&>(other));
+ }
+
+public:
+
+ SimpleGraph() {}
+
+
+ SimpleGraph(const SimpleGraph &other) : PGraph() {
+ copyFrom(other);
+ }
+
+ SimpleGraph& operator=(const SimpleGraph &other) {
+ clear();
+ copyFrom(other);
+ return *this;
+ }
+
+ NodeIterator addNode(const Vector &costs) {
+ return PGraph::addConstructedNode(SimpleNode(costs));
+ }
+
+ EdgeIterator addEdge(const NodeIterator &node1Itr,
+ const NodeIterator &node2Itr,
+ const Matrix &costs) {
+ return PGraph::addConstructedEdge(SimpleEdge(node1Itr, node2Itr, costs));
+ }
+
+};
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
diff --git a/lib/CodeGen/PBQP/Solution.h b/lib/CodeGen/PBQP/Solution.h
new file mode 100644
index 0000000..316c9de
--- /dev/null
+++ b/lib/CodeGen/PBQP/Solution.h
@@ -0,0 +1,74 @@
+#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H
+#define LLVM_CODEGEN_PBQP_SOLUTION_H
+
+#include "PBQPMath.h"
+
+namespace PBQP {
+
+class Solution {
+
+ friend class SolverImplementation;
+
+private:
+
+ std::vector<unsigned> selections;
+ PBQPNum solutionCost;
+ bool provedOptimal;
+ unsigned r0Reductions, r1Reductions,
+ r2Reductions, rNReductions;
+
+public:
+
+ Solution() :
+ solutionCost(0.0), provedOptimal(false),
+ r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
+
+ Solution(unsigned length, bool assumeOptimal) :
+ selections(length), solutionCost(0.0), provedOptimal(assumeOptimal),
+ r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
+
+ void setProvedOptimal(bool provedOptimal) {
+ this->provedOptimal = provedOptimal;
+ }
+
+ void setSelection(unsigned nodeID, unsigned selection) {
+ selections[nodeID] = selection;
+ }
+
+ void setSolutionCost(PBQPNum solutionCost) {
+ this->solutionCost = solutionCost;
+ }
+
+ void incR0Reductions() { ++r0Reductions; }
+ void incR1Reductions() { ++r1Reductions; }
+ void incR2Reductions() { ++r2Reductions; }
+ void incRNReductions() { ++rNReductions; }
+
+ unsigned numNodes() const { return selections.size(); }
+
+ unsigned getSelection(unsigned nodeID) const {
+ return selections[nodeID];
+ }
+
+ PBQPNum getCost() const { return solutionCost; }
+
+ bool isProvedOptimal() const { return provedOptimal; }
+
+ unsigned getR0Reductions() const { return r0Reductions; }
+ unsigned getR1Reductions() const { return r1Reductions; }
+ unsigned getR2Reductions() const { return r2Reductions; }
+ unsigned getRNReductions() const { return rNReductions; }
+
+ bool operator==(const Solution &other) const {
+ return (selections == other.selections);
+ }
+
+ bool operator!=(const Solution &other) const {
+ return !(*this == other);
+ }
+
+};
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_SOLUTION_H
diff --git a/lib/CodeGen/PBQP/Solver.h b/lib/CodeGen/PBQP/Solver.h
new file mode 100644
index 0000000..5b6a284
--- /dev/null
+++ b/lib/CodeGen/PBQP/Solver.h
@@ -0,0 +1,21 @@
+#ifndef LLVM_CODEGEN_PBQP_SOLVER_H
+#define LLVM_CODEGEN_PBQP_SOLVER_H
+
+#include "SimpleGraph.h"
+#include "Solution.h"
+
+namespace PBQP {
+
+/// \brief Interface for solver classes.
+class Solver {
+public:
+
+ virtual ~Solver() = 0;
+ virtual Solution solve(const SimpleGraph &orig) const = 0;
+};
+
+Solver::~Solver() {}
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_SOLVER_H