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

10 files changed, 2672 insertions, 0 deletions

diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h
new file mode 100644
index 0000000000..801b01e333
--- /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 0000000000..98f7140ff0
--- /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 0000000000..bda5952e22
--- /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 0000000000..620e21e276
--- /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 0000000000..7088f36456
--- /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 0000000000..fd37f5cbb3
--- /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 0000000000..dc184fed14
--- /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 0000000000..595269c327
--- /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 0000000000..316c9de5bd
--- /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 0000000000..5b6a284957
--- /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