New PBQP solver.

* Fixed a reduction bug which occasionally led to infinite-cost (invalid)
  register allocation solutions despite the existence finite-cost solutions.
* Significantly reduced memory usage (>50% reduction).
* Simplified a lot of the solver code.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94514 91177308-0d34-0410-b5e6-96231b3b80d8

12 files changed, 1503 insertions, 2056 deletions

diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h
deleted file mode 100644
index 738dea0d37..0000000000
--- a/lib/CodeGen/PBQP/AnnotatedGraph.h
+++ /dev/null
@@ -1,184 +0,0 @@
-//===-- AnnotatedGraph.h - Annotated PBQP Graph -----------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Annotated PBQP Graph class. This class is used internally by the PBQP solver
-// to cache information to speed up reduction.
-//
-//===----------------------------------------------------------------------===//
-
-#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 PGraph::getNodeEntry(nodeItr).getNodeData();
-  }
-
-  const NodeData& getNodeData(const NodeIterator &nodeItr) const {
-    return PGraph::getNodeEntry(nodeItr).getNodeData();
-  }
-
-  EdgeData& getEdgeData(const EdgeIterator &edgeItr) {
-    return PGraph::getEdgeEntry(edgeItr).getEdgeData();
-  }
-
-  const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const {
-    return PGraph::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
deleted file mode 100644
index 35ec4f1b0b..0000000000
--- a/lib/CodeGen/PBQP/ExhaustiveSolver.h
+++ /dev/null
@@ -1,110 +0,0 @@
-//===-- ExhaustiveSolver.h - Brute Force PBQP Solver ------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Uses a trivial brute force algorithm to solve a PBQP problem.
-// PBQP is NP-HARD - This solver should only be used for debugging small
-// problems.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
-#define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
-
-#include "Solver.h"
-
-namespace PBQP {
-
-/// A brute force PBQP solver. This solver takes exponential time. It should
-/// only be used for debugging purposes. 
-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/Graph.h b/lib/CodeGen/PBQP/Graph.h
new file mode 100644
index 0000000000..40fc9197a9
--- /dev/null
+++ b/lib/CodeGen/PBQP/Graph.h
@@ -0,0 +1,357 @@
+//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// PBQP Graph class.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
+#define LLVM_CODEGEN_PBQP_GRAPH_H
+
+#include "Math.h"
+
+#include <list>
+#include <vector>
+
+namespace PBQP {
+
+  /// PBQP Graph class.
+  /// Instances of this class describe PBQP problems.
+  class Graph {
+  private:
+
+    // ----- TYPEDEFS -----
+    class NodeEntry;
+    class EdgeEntry;
+
+    typedef std::list<NodeEntry> NodeList;
+    typedef std::list<EdgeEntry> EdgeList;
+
+  public:
+
+    typedef NodeList::iterator NodeItr;
+    typedef EdgeList::iterator EdgeItr;
+
+  private:
+
+    typedef std::list<EdgeItr> AdjEdgeList;
+  
+  public:
+
+    typedef AdjEdgeList::iterator AdjEdgeItr;
+
+  private:
+
+    class NodeEntry {
+    private:
+      Vector costs;      
+      AdjEdgeList adjEdges;
+      unsigned degree;
+      void *data;
+    public:
+      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
+      Vector& getCosts() { return costs; }
+      unsigned getDegree() const { return degree; }
+      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
+      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
+      AdjEdgeItr addEdge(EdgeItr e) {
+        ++degree;
+        return adjEdges.insert(adjEdges.end(), e);
+      }
+      void removeEdge(AdjEdgeItr ae) {
+        --degree;
+        adjEdges.erase(ae);
+      }
+      void setData(void *data) { this->data = data; }
+      void* getData() { return data; }
+    };
+
+    class EdgeEntry {
+    private:
+      NodeItr node1, node2;
+      Matrix costs;
+      AdjEdgeItr node1AEItr, node2AEItr;
+      void *data;
+    public:
+      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
+        : node1(node1), node2(node2), costs(costs) {}
+      NodeItr getNode1() const { return node1; }
+      NodeItr getNode2() const { return node2; }
+      Matrix& getCosts() { return costs; }
+      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
+      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
+      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
+      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
+      void setData(void *data) { this->data = data; }
+      void *getData() { return data; }
+    };
+
+    // ----- MEMBERS -----
+
+    NodeList nodes;
+    unsigned numNodes;
+
+    EdgeList edges;
+    unsigned numEdges;
+
+    // ----- INTERNAL METHODS -----
+
+    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
+    const NodeEntry& getNode(NodeItr nItr) const { return *nItr; }
+    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
+    const EdgeEntry& getEdge(EdgeItr eItr) const { return *eItr; }
+
+    NodeItr addConstructedNode(const NodeEntry &n) {
+      ++numNodes;
+      return nodes.insert(nodes.end(), n);
+    }
+
+    EdgeItr addConstructedEdge(const EdgeEntry &e) {
+      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
+             "Attempt to add duplicate edge.");
+      ++numEdges;
+      EdgeItr edgeItr = edges.insert(edges.end(), e);
+      EdgeEntry &ne = getEdge(edgeItr);
+      NodeEntry &n1 = getNode(ne.getNode1());
+      NodeEntry &n2 = getNode(ne.getNode2());
+      // Sanity check on matrix dimensions:
+      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
+             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
+             "Edge cost dimensions do not match node costs dimensions.");
+      ne.setNode1AEItr(n1.addEdge(edgeItr));
+      ne.setNode2AEItr(n2.addEdge(edgeItr));
+      return edgeItr;
+    }
+
+  public:
+
+    Graph() : numNodes(0), numEdges(0) {}
+
+    /// \brief Add a node with the given costs.
+    /// @param costs Cost vector for the new node.
+    /// @return Node iterator for the added node.
+    NodeItr addNode(const Vector &costs) {
+      return addConstructedNode(NodeEntry(costs));
+    }
+
+    /// \brief Add an edge between the given nodes with the given costs.
+    /// @param n1Itr First node.
+    /// @param n2Itr Second node.
+    /// @return Edge iterator for the added edge.
+    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
+                    const Matrix &costs) {
+      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
+             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
+             "Matrix dimensions mismatch.");
+      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
+    }
+
+    /// \brief Get the number of nodes in the graph.
+    /// @return Number of nodes in the graph.
+    unsigned getNumNodes() const { return numNodes; }
+
+    /// \brief Get the number of edges in the graph.
+    /// @return Number of edges in the graph.
+    unsigned getNumEdges() const { return numEdges; }
+
+    /// \brief Get a node's cost vector.
+    /// @param nItr Node iterator.
+    /// @return Node cost vector.
+    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
+
+    /// \brief Set a node's data pointer.
+    /// @param nItr Node iterator.
+    /// @param data Pointer to node data.
+    ///
+    /// Typically used by a PBQP solver to attach data to aid in solution.
+    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
+
+    /// \brief Get the node's data pointer.
+    /// @param nItr Node iterator.
+    /// @return Pointer to node data.
+    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
+    
+    /// \brief Get an edge's cost matrix.
+    /// @param eItr Edge iterator.
+    /// @return Edge cost matrix.
+    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
+
+    /// \brief Set an edge's data pointer.
+    /// @param eItr Edge iterator.
+    /// @param data Pointer to edge data.
+    ///
+    /// Typically used by a PBQP solver to attach data to aid in solution.
+    void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
+
+    /// \brief Get an edge's data pointer.
+    /// @param eItr Edge iterator.
+    /// @return Pointer to edge data. 
+    void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
+
+    /// \brief Get a node's degree.
+    /// @param nItr Node iterator.
+    /// @return The degree of the node.
+    unsigned getNodeDegree(NodeItr nItr) const {
+      return getNode(nItr).getDegree();
+    }
+
+    /// \brief Begin iterator for node set.
+    NodeItr nodesBegin() { return nodes.begin(); }
+
+    /// \brief End iterator for node set.
+    NodeItr nodesEnd() { return nodes.end(); }
+
+    /// \brief Begin iterator for edge set.
+    EdgeItr edgesBegin() { return edges.begin(); }
+
+    /// \brief End iterator for edge set.
+    EdgeItr edgesEnd() { return edges.end(); }
+
+    /// \brief Get begin iterator for adjacent edge set.
+    /// @param nItr Node iterator.
+    /// @return Begin iterator for the set of edges connected to the given node.
+    AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
+      return getNode(nItr).edgesBegin();
+    }
+
+    /// \brief Get end iterator for adjacent edge set.
+    /// @param nItr Node iterator.
+    /// @return End iterator for the set of edges connected to the given node.
+    AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
+      return getNode(nItr).edgesEnd();
+    }
+
+    /// \brief Get the first node connected to this edge.
+    /// @param eItr Edge iterator.
+    /// @return The first node connected to the given edge. 
+    NodeItr getEdgeNode1(EdgeItr eItr) {
+      return getEdge(eItr).getNode1();
+    }
+
+    /// \brief Get the second node connected to this edge.
+    /// @param eItr Edge iterator.
+    /// @return The second node connected to the given edge. 
+    NodeItr getEdgeNode2(EdgeItr eItr) {
+      return getEdge(eItr).getNode2();
+    } 
+
+    /// \brief Get the "other" node connected to this edge.
+    /// @param eItr Edge iterator.
+    /// @param nItr Node iterator for the "given" node.
+    /// @return The iterator for the "other" node connected to this edge. 
+    NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
+      EdgeEntry &e = getEdge(eItr);
+      if (e.getNode1() == nItr) {
+        return e.getNode2();
+      } // else
+      return e.getNode1();
+    }
+
+    /// \brief Get the edge connecting two nodes.
+    /// @param n1Itr First node iterator.
+    /// @param n2Itr Second node iterator.
+    /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
+    ///         otherwise returns edgesEnd(). 
+    EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
+      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
+         aeItr != aeEnd; ++aeItr) {
+        if ((getEdgeNode1(*aeItr) == n2Itr) ||
+            (getEdgeNode2(*aeItr) == n2Itr)) {
+          return *aeItr;
+        }
+      }
+      return edges.end();
+    }
+
+    /// \brief Remove a node from the graph.
+    /// @param nItr Node iterator.
+    void removeNode(NodeItr nItr) {
+      NodeEntry &n = getNode(nItr);
+      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
+        EdgeItr eItr = *itr;
+        ++itr;
+        removeEdge(eItr); 
+      }
+      nodes.erase(nItr);
+      --numNodes;
+    }
+
+    /// \brief Remove an edge from the graph.
+    /// @param eItr Edge iterator.
+    void removeEdge(EdgeItr eItr) {
+      EdgeEntry &e = getEdge(eItr);
+      NodeEntry &n1 = getNode(e.getNode1());
+      NodeEntry &n2 = getNode(e.getNode2());
+      n1.removeEdge(e.getNode1AEItr());
+      n2.removeEdge(e.getNode2AEItr());
+      edges.erase(eItr);
+      --numEdges;
+    }
+
+    /// \brief Remove all nodes and edges from the graph.
+    void clear() {
+      nodes.clear();
+      edges.clear();
+      numNodes = numEdges = 0;
+    }
+
+    /// \brief Print a representation of this graph in DOT format.
+    /// @param os Output stream to print on.
+    template <typename OStream>
+    void printDot(OStream &os) {
+    
+      os << "graph {\n";
+
+      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+           nodeItr != nodeEnd; ++nodeItr) {
+
+        os << "  node" << nodeItr << " [ label=\""
+           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+      }
+
+      os << "  edge [ len=" << getNumNodes() << " ]\n";
+
+      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
+           edgeItr != edgeEnd; ++edgeItr) {
+
+        os << "  node" << getEdgeNode1(edgeItr)
+           << " -- node" << getEdgeNode2(edgeItr)
+           << " [ label=\"";
+
+        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+
+        for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
+          os << edgeCosts.getRowAsVector(i) << "\\n";
+        }
+        os << "\" ]\n";
+      }
+      os << "}\n";
+    }
+
+  };
+
+  class NodeItrComparator {
+  public:
+    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
+      return &*n1 < &*n2;
+    }
+  };
+
+  class EdgeItrCompartor {
+  public:
+    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
+      return &*e1 < &*e2;
+    }
+  };
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h
deleted file mode 100644
index becd98afdb..0000000000
--- a/lib/CodeGen/PBQP/GraphBase.h
+++ /dev/null
@@ -1,582 +0,0 @@
-//===-- GraphBase.h - Abstract Base PBQP Graph ------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Base class for PBQP Graphs.
-//
-//===----------------------------------------------------------------------===//
-
-
-#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());
-
-    // Sanity check on matrix dimensions.
-    assert((node1Entry.getCosts().getLength() == 
-            newEdgeEntry.getCosts().getRows()) && 
-           (node2Entry.getCosts().getLength() == 
-            newEdgeEntry.getCosts().getCols()) &&
-        "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 != adjEdgeEnd; ++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/HeuristicBase.h b/lib/CodeGen/PBQP/HeuristicBase.h
new file mode 100644
index 0000000000..3bb24e1cc3
--- /dev/null
+++ b/lib/CodeGen/PBQP/HeuristicBase.h
@@ -0,0 +1,242 @@
+//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H
+#define LLVM_CODEGEN_PBQP_HEURISTICBASE_H
+
+#include "HeuristicSolver.h"
+
+namespace PBQP {
+
+  /// \brief Abstract base class for heuristic implementations.
+  ///
+  /// This class provides a handy base for heuristic implementations with common
+  /// solver behaviour implemented for a number of methods.
+  ///
+  /// To implement your own heuristic using this class as a base you'll have to
+  /// implement, as a minimum, the following methods:
+  /// <ul>
+  ///   <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the
+  ///        heuristic reduction list.
+  ///   <li> void heuristicReduce() : Perform a single heuristic reduction.
+  ///   <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent)
+  ///        change to the cost matrix on the given edge (by R2).
+  ///   <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new 
+  ///        costs on the given edge.
+  ///   <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new
+  ///        edge into the PBQP graph (by R2).
+  ///   <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the
+  ///        disconnection of the given edge from the given node.
+  ///   <li> A constructor for your derived class : to pass back a reference to
+  ///        the solver which is using this heuristic.
+  /// </ul>
+  ///
+  /// These methods are implemented in this class for documentation purposes,
+  /// but will assert if called.
+  /// 
+  /// Note that this class uses the curiously recursive template idiom to
+  /// forward calls to the derived class. These methods need not be made
+  /// virtual, and indeed probably shouldn't for performance reasons.
+  ///
+  /// You'll also need to provide NodeData and EdgeData structs in your class.
+  /// These can be used to attach data relevant to your heuristic to each
+  /// node/edge in the PBQP graph.
+
+  template <typename HImpl>
+  class HeuristicBase {
+  private:
+
+    typedef std::list<Graph::NodeItr> OptimalList;
+
+    HeuristicSolverImpl<HImpl> &s;
+    Graph &g;
+    OptimalList optimalList;
+
+    // Return a reference to the derived heuristic.
+    HImpl& impl() { return static_cast<HImpl&>(*this); }
+
+    // Add the given node to the optimal reductions list. Keep an iterator to
+    // its location for fast removal. 
+    void addToOptimalReductionList(Graph::NodeItr nItr) {
+      optimalList.insert(optimalList.end(), nItr);
+    }
+
+  public:
+
+    /// \brief Construct an instance with a reference to the given solver.
+    /// @param solver The solver which is using this heuristic instance.
+    HeuristicBase(HeuristicSolverImpl<HImpl> &solver)
+      : s(solver), g(s.getGraph()) { }
+
+    /// \brief Get the solver which is using this heuristic instance.
+    /// @return The solver which is using this heuristic instance.
+    ///
+    /// You can use this method to get access to the solver in your derived
+    /// heuristic implementation.
+    HeuristicSolverImpl<HImpl>& getSolver() { return s; }
+
+    /// \brief Get the graph representing the problem to be solved.
+    /// @return The graph representing the problem to be solved.
+    Graph& getGraph() { return g; }
+
+    /// \brief Tell the solver to simplify the graph before the reduction phase.
+    /// @return Whether or not the solver should run a simplification phase
+    ///         prior to the main setup and reduction.
+    ///
+    /// HeuristicBase returns true from this method as it's a sensible default,
+    /// however you can over-ride it in your derived class if you want different
+    /// behaviour.
+    bool solverRunSimplify() const { return true; }
+
+    /// \brief Decide whether a node should be optimally or heuristically 
+    ///        reduced.
+    /// @return Whether or not the given node should be listed for optimal
+    ///         reduction (via R0, R1 or R2).
+    ///
+    /// HeuristicBase returns true for any node with degree less than 3. This is
+    /// sane and sensible for many situations, but not all. You can over-ride
+    /// this method in your derived class if you want a different selection
+    /// criteria. Note however that your criteria for selecting optimal nodes
+    /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
+    /// higher should not be selected under any circumstances.
+    bool shouldOptimallyReduce(Graph::NodeItr nItr) {
+      if (g.getNodeDegree(nItr) < 3)
+        return true;
+      // else
+      return false;
+    }
+
+    /// \brief Add the given node to the list of nodes to be optimally reduced.
+    /// @return nItr Node iterator to be added.
+    ///
+    /// You probably don't want to over-ride this, except perhaps to record
+    /// statistics before calling this implementation. HeuristicBase relies on
+    /// its behaviour.
+    void addToOptimalReduceList(Graph::NodeItr nItr) {
+      optimalList.push_back(nItr);
+    }
+
+    /// \brief Initialise the heuristic.
+    ///
+    /// HeuristicBase iterates over all nodes in the problem and adds them to
+    /// the appropriate list using addToOptimalReduceList or
+    /// addToHeuristicReduceList based on the result of shouldOptimallyReduce.
+    ///
+    /// This behaviour should be fine for most situations.
+    void setup() {
+      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
+           nItr != nEnd; ++nItr) {
+        if (impl().shouldOptimallyReduce(nItr)) {
+          addToOptimalReduceList(nItr);
+        } else {
+          impl().addToHeuristicReduceList(nItr);
+        }
+      }
+    }
+
+    /// \brief Optimally reduce one of the nodes in the optimal reduce list.
+    /// @return True if a reduction takes place, false if the optimal reduce
+    ///         list is empty.
+    ///
+    /// Selects a node from the optimal reduce list and removes it, applying
+    /// R0, R1 or R2 as appropriate based on the selected node's degree.
+    bool optimalReduce() {
+      if (optimalList.empty())
+        return false;
+
+      Graph::NodeItr nItr = optimalList.front();
+      optimalList.pop_front();
+
+      switch (s.getSolverDegree(nItr)) {
+        case 0: s.applyR0(nItr); break;
+        case 1: s.applyR1(nItr); break;
+        case 2: s.applyR2(nItr); break;
+        default: assert(false &&
+                        "Optimal reductions of degree > 2 nodes is invalid.");
+      }
+
+      return true;
+    }
+
+    /// \brief Perform the PBQP reduction process.
+    ///
+    /// Reduces the problem to the empty graph by repeated application of the
+    /// reduction rules R0, R1, R2 and RN.
+    /// R0, R1 or R2 are always applied if possible before RN is used.
+    void reduce() {
+      bool finished = false;
+
+      while (!finished) {
+        if (!optimalReduce())
+          if (!impl().heuristicReduce())
+            finished = true;
+      }
+    }
+
+    /// \brief Add a node to the heuristic reduce list.
+    /// @param nItr Node iterator to add to the heuristic reduce list.
+    void addToHeuristicList(Graph::NodeItr nItr) {
+      assert(false && "Must be implemented in derived class.");
+    }
+
+    /// \brief Heuristically reduce one of the nodes in the heuristic
+    ///        reduce list.
+    /// @return True if a reduction takes place, false if the heuristic reduce
+    ///         list is empty.
+    void heuristicReduce() {
+      assert(false && "Must be implemented in derived class.");
+    }
+
+    /// \brief Prepare a change in the costs on the given edge.
+    /// @param eItr Edge iterator.    
+    void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+      assert(false && "Must be implemented in derived class.");
+    }
+
+    /// \brief Handle the change in the costs on the given edge.
+    /// @param eItr Edge iterator.
+    void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
+      assert(false && "Must be implemented in derived class.");
+    }
+
+    /// \brief Handle the addition of a new edge into the PBQP graph.
+    /// @param eItr Edge iterator for the added edge.
+    void handleAddEdge(Graph::EdgeItr eItr) {
+      assert(false && "Must be implemented in derived class.");
+    }
+
+    /// \brief Handle disconnection of an edge from a node.
+    /// @param eItr Edge iterator for edge being disconnected.
+    /// @param nItr Node iterator for the node being disconnected from.
+    ///
+    /// Edges are frequently removed due to the removal of a node. This
+    /// method allows for the effect to be computed only for the remaining
+    /// node in the graph.
+    void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+      assert(false && "Must be implemented in derived class.");
+    }
+
+    /// \brief Clean up any structures used by HeuristicBase.
+    ///
+    /// At present this just performs a sanity check: that the optimal reduce
+    /// list is empty now that reduction has completed.
+    ///
+    /// If your derived class has more complex structures which need tearing
+    /// down you should over-ride this method but include a call back to this
+    /// implementation.
+    void cleanup() {
+      assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
+    }
+
+  };
+
+}
+
+
+#endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H
diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h
index f78a58a66c..5066685a19 100644
--- a/lib/CodeGen/PBQP/HeuristicSolver.h
+++ b/lib/CodeGen/PBQP/HeuristicSolver.h
@@ -1,4 +1,4 @@
-//===-- HeuristicSolver.h - Heuristic PBQP Solver ---------------*- C++ -*-===//
+//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -16,773 +16,577 @@
 #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
 #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
 
-#include "Solver.h"
-#include "AnnotatedGraph.h"
+#include "Graph.h"
+#include "Solution.h"
 #include "llvm/Support/raw_ostream.h"
+#include <vector>
 #include <limits>
 
 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;
-
+  /// \brief Heuristic PBQP solver implementation.
+  ///
+  /// This class should usually be created (and destroyed) indirectly via a call
+  /// to HeuristicSolver<HImpl>::solve(Graph&).
+  /// See the comments for HeuristicSolver.
+  ///
+  /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules,
+  /// backpropagation phase, and maintains the internal copy of the graph on
+  /// which the reduction is carried out (the original being kept to facilitate
+  /// backpropagation).
+  template <typename HImpl>
+  class HeuristicSolverImpl {
   private:
 
-    typedef std::list<GraphEdgeIterator> LinksList;
+    typedef typename HImpl::NodeData HeuristicNodeData;
+    typedef typename HImpl::EdgeData HeuristicEdgeData;
 
-    unsigned numLinks;
-    LinksList links, solvedLinks;
-    NodeListIterator bucketItr;
-    HeuristicNodeData heuristicData;
+    typedef std::list<Graph::EdgeItr> SolverEdges;
 
   public:
-
-    typedef typename LinksList::iterator AdjLinkIterator;
+  
+    /// \brief Iterator type for edges in the solver graph.
+    typedef SolverEdges::iterator SolverEdgeItr;
 
   private:
 
-    AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) {
-      ++numLinks;
-      return links.insert(links.end(), edgeItr);
-    }
+    class NodeData {
+    public:
+      NodeData() : solverDegree(0) {}
 
-    void delLink(const AdjLinkIterator &adjLinkItr) {
-      --numLinks;
-      links.erase(adjLinkItr);
-    }
+      HeuristicNodeData& getHeuristicData() { return hData; }
 
-  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;
-    }
+      SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
+        ++solverDegree;
+        return solverEdges.insert(solverEdges.end(), eItr);
+      }
 
-    const NodeListIterator& getBucketItr() const {
-      return bucketItr;
-    }
+      void removeSolverEdge(SolverEdgeItr seItr) {
+        --solverDegree;
+        solverEdges.erase(seItr);
+      }
 
-    AdjLinkIterator adjLinksBegin() {
-      return links.begin();
-    }
+      SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
+      SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
+      unsigned getSolverDegree() const { return solverDegree; }
+      void clearSolverEdges() {
+        solverDegree = 0;
+        solverEdges.clear(); 
+      }
+      
+    private:
+      HeuristicNodeData hData;
+      unsigned solverDegree;
+      SolverEdges solverEdges;
+    };
+ 
+    class EdgeData {
+    public:
+      HeuristicEdgeData& getHeuristicData() { return hData; }
+
+      void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
+        this->n1SolverEdgeItr = n1SolverEdgeItr;
+      }
 
-    AdjLinkIterator adjLinksEnd() {
-      return links.end();
-    }
+      SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
 
-    void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) {
-      solvedLinks.push_back(solvedLinkItr);
-    }
+      void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
+        this->n2SolverEdgeItr = n2SolverEdgeItr;
+      }
 
-    AdjLinkIterator solvedLinksBegin() {
-      return solvedLinks.begin();
-    }
+      SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
 
-    AdjLinkIterator solvedLinksEnd() {
-      return solvedLinks.end();
-    }
+    private:
 
-  };
+      HeuristicEdgeData hData;
+      SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
+    };
 
-  class EdgeData {
-  private:
+    Graph &g;
+    HImpl h;
+    Solution s;
+    std::vector<Graph::NodeItr> stack;
 
-    SolverGraph &g;
-    GraphNodeIterator node1Itr, node2Itr;
-    HeuristicEdgeData heuristicData;
-    typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr;
+    std::vector<NodeData> nodeData;
+    std::vector<EdgeData> edgeData;
 
   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);
+    /// \brief Construct a heuristic solver implementation to solve the given
+    ///        graph.
+    /// @param g The graph representing the problem instance to be solved.
+    HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}  
+
+    /// \brief Get the graph being solved by this solver.
+    /// @return The graph representing the problem instance being solved by this
+    ///         solver.
+    Graph& getGraph() { return g; }
+
+    /// \brief Get the heuristic data attached to the given node.
+    /// @param nItr Node iterator.
+    /// @return The heuristic data attached to the given node.
+    HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
+      return getSolverNodeData(nItr).getHeuristicData();
+    }
+
+    /// \brief Get the heuristic data attached to the given edge.
+    /// @param eItr Edge iterator.
+    /// @return The heuristic data attached to the given node.
+    HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
+      return getSolverEdgeData(eItr).getHeuristicData();
+    }
+
+    /// \brief Begin iterator for the set of edges adjacent to the given node in
+    ///        the solver graph.
+    /// @param nItr Node iterator.
+    /// @return Begin iterator for the set of edges adjacent to the given node
+    ///         in the solver graph. 
+    SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
+      return getSolverNodeData(nItr).solverEdgesBegin();
+    }
+
+    /// \brief End iterator for the set of edges adjacent to the given node in
+    ///        the solver graph.
+    /// @param nItr Node iterator.
+    /// @return End iterator for the set of edges adjacent to the given node in
+    ///         the solver graph. 
+    SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
+      return getSolverNodeData(nItr).solverEdgesEnd();
+    }
+
+    /// \brief Remove a node from the solver graph.
+    /// @param eItr Edge iterator for edge to be removed.
+    ///
+    /// Does <i>not</i> notify the heuristic of the removal. That should be
+    /// done manually if necessary.
+    void removeSolverEdge(Graph::EdgeItr eItr) {
+      EdgeData &eData = getSolverEdgeData(eItr);
+      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
+               &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
+
+      n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
+      n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
+    }
+
+    /// \brief Compute a solution to the PBQP problem instance with which this
+    ///        heuristic solver was constructed.
+    /// @return A solution to the PBQP problem.
+    ///
+    /// Performs the full PBQP heuristic solver algorithm, including setup,
+    /// calls to the heuristic (which will call back to the reduction rules in
+    /// this class), and cleanup.
+    Solution computeSolution() {
+      setup();
+      h.setup();
+      h.reduce();
+      backpropagate();
+      h.cleanup();
+      cleanup();
+      return s;
+    }
+
+    /// \brief Add to the end of the stack.
+    /// @param nItr Node iterator to add to the reduction stack.
+    void pushToStack(Graph::NodeItr nItr) {
+      getSolverNodeData(nItr).clearSolverEdges();
+      stack.push_back(nItr);
+    }
+
+    /// \brief Returns the solver degree of the given node.
+    /// @param nItr Node iterator for which degree is requested.
+    /// @return Node degree in the <i>solver</i> graph (not the original graph).
+    unsigned getSolverDegree(Graph::NodeItr nItr) {
+      return  getSolverNodeData(nItr).getSolverDegree();
+    }
+
+    /// \brief Set the solution of the given node.
+    /// @param nItr Node iterator to set solution for.
+    /// @param selection Selection for node.
+    void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
+      s.setSelection(nItr, selection);
+
+      for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
+                             aeEnd = g.adjEdgesEnd(nItr);
+           aeItr != aeEnd; ++aeItr) {
+        Graph::EdgeItr eItr(*aeItr);
+        Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
+        getSolverNodeData(anItr).addSolverEdge(eItr);
+      }
     }
-    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));
+    /// \brief Apply rule R0.
+    /// @param nItr Node iterator for node to apply R0 to.
+    ///
+    /// Node will be automatically pushed to the solver stack.
+    void applyR0(Graph::NodeItr nItr) {
+      assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
+             "R0 applied to node with degree != 0.");
 
-    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);
+      // Nothing to do. Just push the node onto the reduction stack.
+      pushToStack(nItr);
     }
-  }
-
-private:
-
-  SolverGraph g;
-  Heuristic heuristic;
-  Solution solution;
 
-  NodeList r0Bucket,
-           r1Bucket,
-           r2Bucket;
+    /// \brief Apply rule R1.
+    /// @param nItr Node iterator for node to apply R1 to.
+    ///
+    /// Node will be automatically pushed to the solver stack.
+    void applyR1(Graph::NodeItr xnItr) {
+      NodeData &nd = getSolverNodeData(xnItr);
+      assert(nd.getSolverDegree() == 1 &&
+             "R1 applied to node with degree != 1.");
 
-  NodeStack stack;
+      Graph::EdgeItr eItr = *nd.solverEdgesBegin();
 
-  // 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()));
+      const Matrix &eCosts = g.getEdgeCosts(eItr);
+      const Vector &xCosts = g.getNodeCosts(xnItr);
+      
+      // Duplicate a little to avoid transposing matrices.
+      if (xnItr == g.getEdgeNode1(eItr)) {
+        Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
+        Vector &yCosts = g.getNodeCosts(ynItr);
+        for (unsigned j = 0; j < yCosts.getLength(); ++j) {
+          PBQPNum min = eCosts[0][j] + xCosts[0];
+          for (unsigned i = 1; i < xCosts.getLength(); ++i) {
+            PBQPNum c = eCosts[i][j] + xCosts[i];
+            if (c < min)
+              min = c;
+          }
+          yCosts[j] += min;
+        }
+        h.handleRemoveEdge(eItr, ynItr);
+     } else {
+        Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
+        Vector &yCosts = g.getNodeCosts(ynItr);
+        for (unsigned i = 0; i < yCosts.getLength(); ++i) {
+          PBQPNum min = eCosts[i][0] + xCosts[0];
+          for (unsigned j = 1; j < xCosts.getLength(); ++j) {
+            PBQPNum c = eCosts[i][j] + xCosts[j];
+            if (c < min)
+              min = c;
+          }
+          yCosts[i] += min;
+        }
+        h.handleRemoveEdge(eItr, ynItr);
+      }
+      removeSolverEdge(eItr);
+      assert(nd.getSolverDegree() == 0 &&
+             "Degree 1 with edge removed should be 0.");
+      pushToStack(xnItr);
     }
 
-    for (SimpleGraph::ConstEdgeIterator
-         origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd();
-         origEdgeItr != origEdgeEnd; ++origEdgeItr) {
+    /// \brief Apply rule R2.
+    /// @param nItr Node iterator for node to apply R2 to.
+    ///
+    /// Node will be automatically pushed to the solver stack.
+    void applyR2(Graph::NodeItr xnItr) {
+      assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
+             "R2 applied to node with degree != 2.");
 
-      unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)),
-               id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr));
+      NodeData &nd = getSolverNodeData(xnItr);
+      const Vector &xCosts = g.getNodeCosts(xnItr);
 
-      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();
-  }
+      SolverEdgeItr aeItr = nd.solverEdgesBegin();
+      Graph::EdgeItr yxeItr = *aeItr,
+                     zxeItr = *(++aeItr);
 
-  // Eliminate trivial nodes.
-  void disconnectTrivialNodes() {
-    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
-         nodeItr != nodeEnd; ++nodeItr) {
+      Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
+                     znItr = g.getEdgeOtherNode(zxeItr, xnItr);
 
-      if (g.getNodeCosts(nodeItr).getLength() == 1) {
+      bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
+           flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
 
-        std::vector<GraphEdgeIterator> edgesToRemove;
+      const Matrix *yxeCosts = flipEdge1 ?
+        new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
+        &g.getEdgeCosts(yxeItr);
 
-        for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
-             adjEdgeEnd = g.adjEdgesEnd(nodeItr);
-             adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+      const Matrix *zxeCosts = flipEdge2 ?
+        new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
+        &g.getEdgeCosts(zxeItr);
 
-          GraphEdgeIterator edgeItr = *adjEdgeItr;
+      unsigned xLen = xCosts.getLength(),
+               yLen = yxeCosts->getRows(),
+               zLen = zxeCosts->getRows();
+               
+      Matrix delta(yLen, zLen);
 
-          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);
+      for (unsigned i = 0; i < yLen; ++i) {
+        for (unsigned j = 0; j < zLen; ++j) {
+          PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0];
+          for (unsigned k = 1; k < xLen; ++k) {
+            PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k];
+            if (c < min) {
+              min = c;
+            }
           }
-
-          edgesToRemove.push_back(edgeItr);
+          delta[i][j] = min;
         }
+      }
 
-        while (!edgesToRemove.empty()) {
-          g.removeEdge(edgesToRemove.back());
-          edgesToRemove.pop_back();
+      if (flipEdge1)
+        delete yxeCosts;
+
+      if (flipEdge2)
+        delete zxeCosts;
+
+      Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
+      bool addedEdge = false;
+
+      if (yzeItr == g.edgesEnd()) {
+        yzeItr = g.addEdge(ynItr, znItr, delta);
+        addedEdge = true;
+      } else {
+        Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
+        h.preUpdateEdgeCosts(yzeItr);
+        if (ynItr == g.getEdgeNode1(yzeItr)) {
+          yzeCosts += delta;
+        } else {
+          yzeCosts += delta.transpose();
         }
       }
-    }
-  }
-
-  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));
+      bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
 
-    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);
+      if (!addedEdge) {
+        // If we modified the edge costs let the heuristic know.
+        h.postUpdateEdgeCosts(yzeItr);
       }
-      else {
-        edgeCosts.setRow(r, 0);
+ 
+      if (nullCostEdge) {
+        // If this edge ended up null remove it.
+        if (!addedEdge) {
+          // We didn't just add it, so we need to notify the heuristic
+          // and remove it from the solver.
+          h.handleRemoveEdge(yzeItr, ynItr);
+          h.handleRemoveEdge(yzeItr, znItr);
+          removeSolverEdge(yzeItr);
+        }
+        g.removeEdge(yzeItr);
+      } else if (addedEdge) {
+        // If the edge was added, and non-null, finish setting it up, add it to
+        // the solver & notify heuristic.
+        edgeData.push_back(EdgeData());
+        g.setEdgeData(yzeItr, &edgeData.back());
+        addSolverEdge(yzeItr);
+        h.handleAddEdge(yzeItr);
       }
-    }
 
-    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);
-      }
-    }
+      h.handleRemoveEdge(yxeItr, ynItr);
+      removeSolverEdge(yxeItr);
+      h.handleRemoveEdge(zxeItr, znItr);
+      removeSolverEdge(zxeItr);
 
-    return edgeCosts.isZero();
-  }
+      pushToStack(xnItr);
+    }
 
-  void setup() {
-    setupLinks();
-    heuristic.initialise(*this);
-    setupBuckets();
-  }
+  private:
 
-  void setupLinks() {
-    for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
-         edgeItr != edgeEnd; ++edgeItr) {
-      g.getEdgeData(edgeItr).setup(edgeItr);
+    NodeData& getSolverNodeData(Graph::NodeItr nItr) {
+      return *static_cast<NodeData*>(g.getNodeData(nItr));
     }
-  }
 
-  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) {
-    llvm::errs() << "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) {
-      llvm::errs() << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr))
-                   << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr))
-                   << ") ";
+    EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
+      return *static_cast<EdgeData*>(g.getEdgeData(eItr));
     }
-    llvm::errs() << "]\n";
-  }
 
-  void dumpState() {
-    llvm::errs() << "\n";
+    void addSolverEdge(Graph::EdgeItr eItr) {
+      EdgeData &eData = getSolverEdgeData(eItr);
+      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
+               &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
 
-    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
-         nodeItr != nodeEnd; ++nodeItr) {
-      printNode(nodeItr);
+      eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
+      eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
     }
 
-    NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket };
-
-    for (unsigned b = 0; b < 3; ++b) {
-      NodeList &bucket = *buckets[b];
-
-      llvm::errs() << "Bucket " << b << ": [ ";
-
-      for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end();
-           nItr != nEnd; ++nItr) {
-        llvm::errs() << g.getNodeID(*nItr) << " ";
+    void setup() {
+      if (h.solverRunSimplify()) {
+        simplify();
       }
 
-      llvm::errs() << "]\n";
-    }
-
-    llvm::errs() << "Stack: [ ";
-    for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end();
-         nsItr != nsEnd; ++nsItr) {
-      llvm::errs() << g.getNodeID(*nsItr) << " ";
-    }
-    llvm::errs() << "]\n";
-  }
-
-  void reduce() {
-    bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() &&
-      heuristic.rNBucketEmpty();
-
-    while (!reductionFinished) {
+      // Reserve space for the node and edge data.
+      nodeData.resize(g.getNumNodes());
+      edgeData.resize(g.getNumEdges());
 
-      if (!r1Bucket.empty()) {
-        processR1();
-      }
-      else if (!r2Bucket.empty()) {
-        processR2();
+      // Create node data objects.
+      unsigned ndIndex = 0;     
+      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
+	       nItr != nEnd; ++nItr, ++ndIndex) {
+        g.setNodeData(nItr, &nodeData[ndIndex]);
       }
-      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();
-
-    //llvm::errs() << "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;
+      // Create edge data objects.
+      unsigned edIndex = 0;
+      for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
+           eItr != eEnd; ++eItr, ++edIndex) {
+        g.setEdgeData(eItr, &edgeData[edIndex]);
+        addSolverEdge(eItr);
       }
     }
-    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;
-      }
+    void simplify() {
+      disconnectTrivialNodes();
+      eliminateIndependentEdges();
     }
 
-    unlinkNode(xNodeItr);
-    pushStack(xNodeItr);
-  }
-
-  void processR2() {
-
-    GraphNodeIterator xNodeItr = r2Bucket.front();
-    r2Bucket.pop_front();
+    // Eliminate trivial nodes.
+    void disconnectTrivialNodes() {
+      unsigned numDisconnected = 0;
 
-    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);
+      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
+           nItr != nEnd; ++nItr) {
 
-    GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr),
-                      zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr);
+        if (g.getNodeCosts(nItr).getLength() == 1) {
 
-    removeFromBucket(yNodeItr);
-    removeFromBucket(zNodeItr);
+          std::vector<Graph::EdgeItr> edgesToRemove;
 
-    removeLink(yxEdgeItr, yNodeItr);
-    removeLink(zxEdgeItr, zNodeItr);
+          for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
+                                 aeEnd = g.adjEdgesEnd(nItr);
+               aeItr != aeEnd; ++aeItr) {
 
-    // Graph some of the costs:
-    bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr),
-         flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr);
+            Graph::EdgeItr eItr = *aeItr;
 
-    const Matrix *yxCosts = flipEdge1 ?
-      new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) :
-      &g.getEdgeCosts(yxEdgeItr),
-                     *zxCosts = flipEdge2 ?
-      new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) :
-        &g.getEdgeCosts(zxEdgeItr);
+            if (g.getEdgeNode1(eItr) == nItr) {
+              Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
+              g.getNodeCosts(otherNodeItr) +=
+                g.getEdgeCosts(eItr).getRowAsVector(0);
+            }
+            else {
+              Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
+              g.getNodeCosts(otherNodeItr) +=
+                g.getEdgeCosts(eItr).getColAsVector(0);
+            }
 
-    unsigned xLen = xCosts.getLength(),
-             yLen = yxCosts->getRows(),
-             zLen = zxCosts->getRows();
+            edgesToRemove.push_back(eItr);
+          }
 
-    // Compute delta:
-    Matrix delta(yLen, zLen);
+          if (!edgesToRemove.empty())
+            ++numDisconnected;
 
-    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;
+          while (!edgesToRemove.empty()) {
+            g.removeEdge(edgesToRemove.back());
+            edgesToRemove.pop_back();
           }
         }
-        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();
-    }
+    void eliminateIndependentEdges() {
+      std::vector<Graph::EdgeItr> edgesToProcess;
+      unsigned numEliminated = 0;
 
-    bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr);
+      for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
+           eItr != eEnd; ++eItr) {
+        edgesToProcess.push_back(eItr);
+      }
 
-    // Nulled the edge, remove it entirely.
-    if (nullCostEdge) {
-      g.removeEdge(yzEdgeItr);
-    }
-    else {
-      // Edge remains - re-link it.
-      addLink(yzEdgeItr);
+      while (!edgesToProcess.empty()) {
+        if (tryToEliminateEdge(edgesToProcess.back()))
+          ++numEliminated;
+        edgesToProcess.pop_back();
+      }
     }
 
-    addToBucket(yNodeItr);
-    addToBucket(zNodeItr);
+    bool tryToEliminateEdge(Graph::EdgeItr eItr) {
+      if (tryNormaliseEdgeMatrix(eItr)) {
+        g.removeEdge(eItr);
+        return true; 
+      }
+      return false;
     }
 
-  void computeTrivialSolutions() {
+    bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
 
-    for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end();
-         r0Itr != r0End; ++r0Itr) {
-      GraphNodeIterator nodeItr = *r0Itr;
+      Matrix &edgeCosts = g.getEdgeCosts(eItr);
+      Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
+             &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
 
-      solution.incR0Reductions();
-      setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex());
-    }
+      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);
+        }
+      }
 
-  void backpropagate() {
-    while (!stack.empty()) {
-      computeSolution(stack.back());
-      stack.pop_back();
+      return edgeCosts.isZero();
     }
-  }
-
-  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);
+    void backpropagate() {
+      while (!stack.empty()) {
+        computeSolution(stack.back());
+        stack.pop_back();
       }
-
     }
 
-    setSolution(nodeItr, v.minIndex());
-  }
+    void computeSolution(Graph::NodeItr nItr) {
 
-  void computeSolutionCost(const SimpleGraph &orig) {
-    PBQPNum cost = 0.0;
+      NodeData &nodeData = getSolverNodeData(nItr);
 
-    for (SimpleGraph::ConstNodeIterator
-         nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd();
-         nodeItr != nodeEnd; ++nodeItr) {
+      Vector v(g.getNodeCosts(nItr));
 
-      unsigned nodeId = orig.getNodeID(nodeItr);
+      // Solve based on existing solved edges.
+      for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
+                         solvedEdgeEnd = nodeData.solverEdgesEnd();
+           solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
 
-      cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
-    }
+        Graph::EdgeItr eItr(*solvedEdgeItr);
+        Matrix &edgeCosts = g.getEdgeCosts(eItr);
 
-    for (SimpleGraph::ConstEdgeIterator
-         edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd();
-         edgeItr != edgeEnd; ++edgeItr) {
+        if (nItr == g.getEdgeNode1(eItr)) {
+          Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
+          unsigned adjSolution = s.getSelection(adjNode);
+          v += edgeCosts.getColAsVector(adjSolution);
+        }
+        else {
+          Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
+          unsigned adjSolution = s.getSelection(adjNode);
+          v += edgeCosts.getRowAsVector(adjSolution);
+        }
 
-      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];
+      setSolution(nItr, v.minIndex());
     }
 
-    solution.setSolutionCost(cost);
-  }
-
-};
+    void cleanup() {
+      h.cleanup();
+      nodeData.clear();
+      edgeData.clear();
+    }
+  };
 
-template <typename Heuristic>
-class HeuristicSolver : public Solver {
-public:
-  Solution solve(const SimpleGraph &g) const {
-    HeuristicSolverImpl<Heuristic> solverImpl(g);
-    return solverImpl.getSolution();
-  }
-};
+  /// \brief PBQP heuristic solver class.
+  ///
+  /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
+  /// by calling
+  /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
+  ///
+  /// The choice of heuristic for the H parameter will affect both the solver
+  /// speed and solution quality. The heuristic should be chosen based on the
+  /// nature of the problem being solved.
+  /// Currently the only solver included with LLVM is the Briggs heuristic for
+  /// register allocation.
+  template <typename HImpl>
+  class HeuristicSolver {
+  public:
+    static Solution solve(Graph &g) {
+      HeuristicSolverImpl<HImpl> hs(g);
+      return hs.computeSolution();
+    }
+  };
 
 }
 
diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h
index 1228f6533c..65f22cbc04 100644
--- a/lib/CodeGen/PBQP/Heuristics/Briggs.h
+++ b/lib/CodeGen/PBQP/Heuristics/Briggs.h
@@ -19,364 +19,452 @@
 #define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
 
 #include "../HeuristicSolver.h"
+#include "../HeuristicBase.h"
 
 #include <set>
+#include <limits>
 
 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 {
+  namespace Heuristics {
+
+    /// \brief PBQP Heuristic which applies an allocability test based on
+    ///        Briggs.
+    /// 
+    /// This heuristic assumes that the elements of cost vectors in the PBQP
+    /// problem represent storage options, with the first being the spill
+    /// option and subsequent elements representing legal registers for the
+    /// corresponding node. Edge cost matrices are likewise assumed to represent
+    /// register constraints.
+    /// If one or more nodes can be proven allocable by this heuristic (by
+    /// inspection of their constraint matrices) then the allocable node of
+    /// highest degree is selected for the next reduction and pushed to the
+    /// solver stack. If no nodes can be proven allocable then the node with
+    /// the lowest estimated spill cost is selected and push to the solver stack
+    /// instead.
+    /// 
+    /// This implementation is built on top of HeuristicBase.       
+    class Briggs : public HeuristicBase<Briggs> {
+    private:
+
+      class LinkDegreeComparator {
       public:
-        LinkDegreeComparator() : 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) {
+        LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
+        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
+          if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
             return true;
-          }
-          else if (n1Degree < n2Degree) {
+          if (s->getSolverDegree(n1Itr) < s->getSolverDegree(n2Itr))
             return false;
-          }
-          // else they're "equal" by degree, differentiate based on ID.
-          return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+          return (&*n1Itr < &*n2Itr);
         }
-
       private:
-        SolverGraph *g;
-    };
+        HeuristicSolverImpl<Briggs> *s;
+      };
 
-    class SpillPriorityComparator {
+      class SpillCostComparator {
       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) {
+        SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
+          : s(&s), g(&s.getGraph()) {}
+        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
+          PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr),
+                  cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr);
+          if (cost1 < cost2)
             return true;
-          }
-          else if (cost1 > cost2) {
+          if (cost1 > cost2)
             return false;
-          }
-          // else they'er "equal" again, differentiate based on address again.
-          return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+          return (&*n1Itr < &*n2Itr);
         }
 
       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) {
+        HeuristicSolverImpl<Briggs> *s;
+        Graph *g;
+      };
 
-          //assume we're adding...
-          unsigned udTarget = 0, dir = 1;
+      typedef std::list<Graph::NodeItr> RNAllocableList;
+      typedef RNAllocableList::iterator RNAllocableListItr;
 
-          if (!add) {
-            udTarget = 1;
-            dir = ~0;
-          }
+      typedef std::list<Graph::NodeItr> RNUnallocableList;  
+      typedef RNUnallocableList::iterator RNUnallocableListItr;
 
-          EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData();
+    public:
 
-          EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd;
+      struct NodeData {
+        typedef std::vector<unsigned> UnsafeDegreesArray;
+        bool isHeuristic, isAllocable, isInitialized;
+        unsigned numDenied, numSafe;
+        UnsafeDegreesArray unsafeDegrees;
+        RNAllocableListItr rnaItr;
+        RNUnallocableListItr rnuItr;
 
-          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();
-          }
+        NodeData()
+          : isHeuristic(false), isAllocable(false), isInitialized(false),
+            numDenied(0), numSafe(0) { }
+      };
 
-          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));
+      struct EdgeData {
+        typedef std::vector<unsigned> UnsafeArray;
+        unsigned worst, reverseWorst;
+        UnsafeArray unsafe, reverseUnsafe;
+        bool isUpToDate;
+
+        EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
+      };
+
+      /// \brief Construct an instance of the Briggs heuristic.
+      /// @param solver A reference to the solver which is using this heuristic.
+      Briggs(HeuristicSolverImpl<Briggs> &solver) :
+        HeuristicBase<Briggs>(solver) {}
+
+      /// \brief Determine whether a node should be reduced using optimal
+      ///        reduction.
+      /// @param nItr Node iterator to be considered.
+      /// @return True if the given node should be optimally reduced, false
+      ///         otherwise.
+      ///
+      /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one
+      /// exception. Nodes whose spill cost (element 0 of their cost vector) is
+      /// infinite are checked for allocability first. Allocable nodes may be
+      /// optimally reduced, but nodes whose allocability cannot be proven are
+      /// selected for heuristic reduction instead.
+      bool shouldOptimallyReduce(Graph::NodeItr nItr) {
+        if (getSolver().getSolverDegree(nItr) < 3) {
+          if (getGraph().getNodeCosts(nItr)[0] !=
+                std::numeric_limits<PBQPNum>::infinity()) {
+            return true;
           }
-
-          allocable = (numDenied < numRegOptions) || (numSafe > 0);
+          // Otherwise we have an infinite spill cost node.
+          initializeNode(nItr);
+          NodeData &nd = getHeuristicNodeData(nItr);
+          return nd.isAllocable;
         }
-
-      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);
-          }
+        // else
+        return false;
+      }
+
+      /// \brief Add a node to the heuristic reduce list.
+      /// @param nItr Node iterator to add to the heuristic reduce list.
+      void addToHeuristicReduceList(Graph::NodeItr nItr) {
+        NodeData &nd = getHeuristicNodeData(nItr);
+        initializeNode(nItr);
+        nd.isHeuristic = true;
+        if (nd.isAllocable) {
+          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+        } else {
+          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
         }
-
-        bool isAllocable() const { return allocable; }
-
-        void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
-            const GraphEdgeIterator &adjEdge) {
-          addRemoveLink(g, nodeItr, adjEdge, true);
+      }
+
+      /// \brief Heuristically reduce one of the nodes in the heuristic
+      ///        reduce list.
+      /// @return True if a reduction takes place, false if the heuristic reduce
+      ///         list is empty.
+      ///
+      /// If the list of allocable nodes is non-empty a node is selected
+      /// from it and pushed to the stack. Otherwise if the non-allocable list
+      /// is non-empty a node is selected from it and pushed to the stack.
+      /// If both lists are empty the method simply returns false with no action
+      /// taken.
+      bool heuristicReduce() {
+        if (!rnAllocableList.empty()) {
+          RNAllocableListItr rnaItr =
+            min_element(rnAllocableList.begin(), rnAllocableList.end(),
+                        LinkDegreeComparator(getSolver()));
+          Graph::NodeItr nItr = *rnaItr;
+          rnAllocableList.erase(rnaItr);
+          handleRemoveNode(nItr);
+          getSolver().pushToStack(nItr);
+          return true;
+        } else if (!rnUnallocableList.empty()) {
+          RNUnallocableListItr rnuItr =
+            min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
+                        SpillCostComparator(getSolver()));
+          Graph::NodeItr nItr = *rnuItr;
+          rnUnallocableList.erase(rnuItr);
+          handleRemoveNode(nItr);
+          getSolver().pushToStack(nItr);
+          return true;
         }
-
-        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;
+        // else
+        return false;
+      }
+
+      /// \brief Prepare a change in the costs on the given edge.
+      /// @param eItr Edge iterator.    
+      void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+        Graph &g = getGraph();
+        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
+                       n2Itr = g.getEdgeNode2(eItr);
+        NodeData &n1 = getHeuristicNodeData(n1Itr),
+                 &n2 = getHeuristicNodeData(n2Itr);
+
+        if (n1.isHeuristic)
+          subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
+        if (n2.isHeuristic)
+          subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
+
+        EdgeData &ed = getHeuristicEdgeData(eItr);
+        ed.isUpToDate = false;
+      }
+
+      /// \brief Handle the change in the costs on the given edge.
+      /// @param eItr Edge iterator.
+      void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
+        // This is effectively the same as adding a new edge now, since
+        // we've factored out the costs of the old one.
+        handleAddEdge(eItr);
+      }
+
+      /// \brief Handle the addition of a new edge into the PBQP graph.
+      /// @param eItr Edge iterator for the added edge.
+      ///
+      /// Updates allocability of any nodes connected by this edge which are
+      /// being managed by the heuristic. If allocability changes they are
+      /// moved to the appropriate list.
+      void handleAddEdge(Graph::EdgeItr eItr) {
+        Graph &g = getGraph();
+        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
+                       n2Itr = g.getEdgeNode2(eItr);
+        NodeData &n1 = getHeuristicNodeData(n1Itr),
+                 &n2 = getHeuristicNodeData(n2Itr);
+
+        // If neither node is managed by the heuristic there's nothing to be
+        // done.
+        if (!n1.isHeuristic && !n2.isHeuristic)
+          return;
+
+        // Ok - we need to update at least one node.
+        computeEdgeContributions(eItr);
+
+        // Update node 1 if it's managed by the heuristic.
+        if (n1.isHeuristic) {
+          bool n1WasAllocable = n1.isAllocable;
+          addEdgeContributions(eItr, n1Itr);
+          updateAllocability(n1Itr);
+          if (n1WasAllocable && !n1.isAllocable) {
+            rnAllocableList.erase(n1.rnaItr);
+            n1.rnuItr =
+              rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
+          }
         }
 
-        void setRNUnallocableNodeListItr(
-            const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) {
-
-          this->rNUnallocableNodeListItr = rNUnallocableNodeListItr;
+        // Likewise for node 2.
+        if (n2.isHeuristic) {
+          bool n2WasAllocable = n2.isAllocable;
+          addEdgeContributions(eItr, n2Itr);
+          updateAllocability(n2Itr);
+          if (n2WasAllocable && !n2.isAllocable) {
+            rnAllocableList.erase(n2.rnaItr);
+            n2.rnuItr =
+              rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
+          }
         }
-
-        RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const {
-          return rNUnallocableNodeListItr;
+      }
+
+      /// \brief Handle disconnection of an edge from a node.
+      /// @param eItr Edge iterator for edge being disconnected.
+      /// @param nItr Node iterator for the node being disconnected from.
+      ///
+      /// Updates allocability of the given node and, if appropriate, moves the
+      /// node to a new list.
+      void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+        NodeData &nd = getHeuristicNodeData(nItr);
+
+        // If the node is not managed by the heuristic there's nothing to be
+        // done.
+        if (!nd.isHeuristic)
+          return;
+
+        EdgeData &ed = getHeuristicEdgeData(eItr);
+
+        assert(ed.isUpToDate && "Edge data is not up to date.");
+
+        // Update node.
+        bool ndWasAllocable = nd.isAllocable;
+        subtractEdgeContributions(eItr, nItr);
+        updateAllocability(nItr);
+
+        // If the node has gone optimal...
+        if (shouldOptimallyReduce(nItr)) {
+          nd.isHeuristic = false;
+          addToOptimalReduceList(nItr);
+          if (ndWasAllocable) {
+            rnAllocableList.erase(nd.rnaItr);
+          } else {
+            rnUnallocableList.erase(nd.rnuItr);
+          }
+        } else {
+          // Node didn't go optimal, but we might have to move it
+          // from "unallocable" to "allocable".
+          if (!ndWasAllocable && nd.isAllocable) {
+            rnUnallocableList.erase(nd.rnuItr);
+            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+          }
         }
+      }
 
+    private:
 
-    };
+      NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
+        return getSolver().getHeuristicNodeData(nItr);
+      }
 
-    class EdgeData {
-      private:
+      EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
+        return getSolver().getHeuristicEdgeData(eItr);
+      }
 
-        typedef std::vector<unsigned> UnsafeArray;
+      // Work out what this edge will contribute to the allocability of the
+      // nodes connected to it.
+      void computeEdgeContributions(Graph::EdgeItr eItr) {
+        EdgeData &ed = getHeuristicEdgeData(eItr);
 
-        unsigned worstDegree,
-                 reverseWorstDegree;
-        UnsafeArray unsafe, reverseUnsafe;
+        if (ed.isUpToDate)
+          return; // Edge data is already up to date.
 
-      public:
+        Matrix &eCosts = getGraph().getEdgeCosts(eItr);
 
-        EdgeData() : worstDegree(0), reverseWorstDegree(0) {}
+        unsigned numRegs = eCosts.getRows() - 1,
+                 numReverseRegs = eCosts.getCols() - 1;
 
-        typedef UnsafeArray::const_iterator ConstUnsafeIterator;
+        std::vector<unsigned> rowInfCounts(numRegs, 0),
+                              colInfCounts(numReverseRegs, 0);        
 
-        void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) {
-          const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
-          unsigned numRegs = edgeCosts.getRows() - 1,
-                   numReverseRegs = edgeCosts.getCols() - 1;
+        ed.worst = 0;
+        ed.reverseWorst = 0;
+        ed.unsafe.clear();
+        ed.unsafe.resize(numRegs, 0);
+        ed.reverseUnsafe.clear();
+        ed.reverseUnsafe.resize(numReverseRegs, 0);
 
-          unsafe.resize(numRegs, 0);
-          reverseUnsafe.resize(numReverseRegs, 0);
+        for (unsigned i = 0; i < numRegs; ++i) {
+          for (unsigned j = 0; j < numReverseRegs; ++j) {
+            if (eCosts[i + 1][j + 1] ==
+                  std::numeric_limits<PBQPNum>::infinity()) {
+              ed.unsafe[i] = 1;
+              ed.reverseUnsafe[j] = 1;
+              ++rowInfCounts[i];
+              ++colInfCounts[j];
 
-          std::vector<unsigned> rowInfCounts(numRegs, 0),
-                                colInfCounts(numReverseRegs, 0);
+              if (colInfCounts[j] > ed.worst) {
+                ed.worst = colInfCounts[j];
+              }
 
-          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];
-                }
+              if (rowInfCounts[i] > ed.reverseWorst) {
+                ed.reverseWorst = 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();
+        ed.isUpToDate = true;
+      }
+
+      // Add the contributions of the given edge to the given node's 
+      // numDenied and safe members. No action is taken other than to update
+      // these member values. Once updated these numbers can be used by clients
+      // to update the node's allocability.
+      void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+        EdgeData &ed = getHeuristicEdgeData(eItr);
+
+        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
+
+        NodeData &nd = getHeuristicNodeData(nItr);
+        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        
+        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+        EdgeData::UnsafeArray &unsafe =
+          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
+        nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
+
+        for (unsigned r = 0; r < numRegs; ++r) {
+          if (unsafe[r]) {
+            if (nd.unsafeDegrees[r]==0) {
+              --nd.numSafe;
+            }
+            ++nd.unsafeDegrees[r];
+          }
         }
-        ConstUnsafeIterator reverseUnsafeEnd() const {
-          return reverseUnsafe.end();
+      }
+
+      // Subtract the contributions of the given edge to the given node's 
+      // numDenied and safe members. No action is taken other than to update
+      // these member values. Once updated these numbers can be used by clients
+      // to update the node's allocability.
+      void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+        EdgeData &ed = getHeuristicEdgeData(eItr);
+
+        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
+
+        NodeData &nd = getHeuristicNodeData(nItr);
+        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        
+        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+        EdgeData::UnsafeArray &unsafe =
+          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
+        nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
+
+        for (unsigned r = 0; r < numRegs; ++r) {
+          if (unsafe[r]) { 
+            if (nd.unsafeDegrees[r] == 1) {
+              ++nd.numSafe;
+            }
+            --nd.unsafeDegrees[r];
+          }
         }
-    };
-
-  void 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 updateAllocability(Graph::NodeItr nItr) {
+        NodeData &nd = getHeuristicNodeData(nItr);
+        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
+      }
 
-  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 initializeNode(Graph::NodeItr nItr) {
+        NodeData &nd = getHeuristicNodeData(nItr);
 
-  void handleRemoveLink(const GraphEdgeIterator &edgeItr,
-                        const GraphNodeIterator &nodeItr) {
-    NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
-    nodeData.handleRemoveLink(*g, nodeItr, edgeItr);
-  }
+        if (nd.isInitialized)
+          return; // Node data is already up to date.
 
-  void processRN() {
-    
-    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);
-    }
- 
-  }
+        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
 
-  bool rNBucketEmpty() const {
-    return (rNAllocableBucket.empty() && rNUnallocableBucket.empty());
-  }
+        nd.numDenied = 0;
+        nd.numSafe = numRegs;
+        nd.unsafeDegrees.resize(numRegs, 0);
 
-private:
+        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
 
-  Solver *s;
-  SolverGraph *g;
-  RNAllocableNodeList rNAllocableBucket;
-  RNUnallocableNodeList rNUnallocableBucket;
-};
+        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
+                           aeEnd = getSolver().solverEdgesEnd(nItr);
+             aeItr != aeEnd; ++aeItr) {
+          
+          Graph::EdgeItr eItr = *aeItr;
+          computeEdgeContributions(eItr);
+          addEdgeContributions(eItr, nItr);
+        }
 
+        updateAllocability(nItr);
+        nd.isInitialized = true;
+      }
+
+      void handleRemoveNode(Graph::NodeItr xnItr) {
+        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
+        std::vector<Graph::EdgeItr> edgesToRemove;
+        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
+                           aeEnd = getSolver().solverEdgesEnd(xnItr);
+             aeItr != aeEnd; ++aeItr) {
+          Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
+          handleRemoveEdge(*aeItr, ynItr);
+          edgesToRemove.push_back(*aeItr);
+        }
+        while (!edgesToRemove.empty()) {
+          getSolver().removeSolverEdge(edgesToRemove.back());
+          edgesToRemove.pop_back();
+        }
+      }
 
+      RNAllocableList rnAllocableList;
+      RNUnallocableList rnUnallocableList;
+    };
 
-}
+  }
 }
 
 
diff --git a/lib/CodeGen/PBQP/PBQPMath.h b/lib/CodeGen/PBQP/Math.h
index 20737a298c..e7598bf3e3 100644
--- a/lib/CodeGen/PBQP/PBQPMath.h
+++ b/lib/CodeGen/PBQP/Math.h
@@ -1,4 +1,4 @@
-//===-- PBQPMath.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
+//===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,8 +7,8 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H 
-#define LLVM_CODEGEN_PBQP_PBQPMATH_H
+#ifndef LLVM_CODEGEN_PBQP_MATH_H 
+#define LLVM_CODEGEN_PBQP_MATH_H
 
 #include <cassert>
 #include <algorithm>
@@ -16,7 +16,7 @@
 
 namespace PBQP {
 
-typedef double PBQPNum;
+typedef float PBQPNum;
 
 /// \brief PBQP Vector class.
 class Vector {
@@ -285,4 +285,4 @@ OStream& operator<<(OStream &os, const Matrix &m) {
 
 }
 
-#endif // LLVM_CODEGEN_PBQP_PBQPMATH_HPP
+#endif // LLVM_CODEGEN_PBQP_MATH_H
diff --git a/lib/CodeGen/PBQP/SimpleGraph.h b/lib/CodeGen/PBQP/SimpleGraph.h
deleted file mode 100644
index 13e63ceb48..0000000000
--- a/lib/CodeGen/PBQP/SimpleGraph.h
+++ /dev/null
@@ -1,100 +0,0 @@
-//===-- SimpleGraph.h - Simple PBQP Graph -----------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Simple PBQP graph class representing a PBQP problem. Graphs of this type
-// can be passed to a PBQPSolver instance to solve the PBQP problem.
-//
-//===----------------------------------------------------------------------===//
-
-#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
index aee684d33e..294b5370af 100644
--- a/lib/CodeGen/PBQP/Solution.h
+++ b/lib/CodeGen/PBQP/Solution.h
@@ -7,81 +7,51 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// Annotated PBQP Graph class. This class is used internally by the PBQP solver
-// to cache information to speed up reduction.
+// PBQP Solution class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_PBQP_SOLUTION_H
 #define LLVM_CODEGEN_PBQP_SOLUTION_H
 
-#include "PBQPMath.h"
+#include "Math.h"
+#include "Graph.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;
-  }
+#include <map>
 
-  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);
-  }
+namespace PBQP {
 
-};
+  /// \brief Represents a solution to a PBQP problem.
+  ///
+  /// To get the selection for each node in the problem use the getSelection method.
+  class Solution {
+  private:
+    typedef std::map<Graph::NodeItr, unsigned, NodeItrComparator> SelectionsMap;
+    SelectionsMap selections;
+
+  public:
+
+    /// \brief Number of nodes for which selections have been made.
+    /// @return Number of nodes for which selections have been made.
+    unsigned numNodes() const { return selections.size(); }
+
+    /// \brief Set the selection for a given node.
+    /// @param nItr Node iterator.
+    /// @param selection Selection for nItr.
+    void setSelection(Graph::NodeItr nItr, unsigned selection) {
+      selections[nItr] = selection;
+    }
+
+    /// \brief Get a node's selection.
+    /// @param nItr Node iterator.
+    /// @return The selection for nItr;
+    unsigned getSelection(Graph::NodeItr nItr) const {
+      SelectionsMap::const_iterator sItr = selections.find(nItr);
+      assert(sItr != selections.end() && "No selection for node.");
+      return sItr->second;
+    }
+
+  };
 
 }
 
diff --git a/lib/CodeGen/PBQP/Solver.h b/lib/CodeGen/PBQP/Solver.h
deleted file mode 100644
index a445de81bc..0000000000
--- a/lib/CodeGen/PBQP/Solver.h
+++ /dev/null
@@ -1,31 +0,0 @@
-//===-- Solver.h ------- PBQP solver interface ------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_PBQP_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
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index fc59653f82..74e155fd3f 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -32,7 +32,7 @@
 #define DEBUG_TYPE "regalloc"
 
 #include "PBQP/HeuristicSolver.h"
-#include "PBQP/SimpleGraph.h"
+#include "PBQP/Graph.h"
 #include "PBQP/Heuristics/Briggs.h"
 #include "VirtRegMap.h"
 #include "VirtRegRewriter.h"
@@ -58,12 +58,12 @@ using namespace llvm;
 
 static RegisterRegAlloc
 registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
-                      llvm::createPBQPRegisterAllocator);
+                       llvm::createPBQPRegisterAllocator);
 
 static cl::opt<bool>
 pbqpCoalescing("pbqp-coalescing",
-               cl::desc("Attempt coalescing during PBQP register allocation."),
-               cl::init(false), cl::Hidden);
+                cl::desc("Attempt coalescing during PBQP register allocation."),
+                cl::init(false), cl::Hidden);
 
 namespace {
 
@@ -114,6 +114,8 @@ namespace {
 
     typedef std::set<LiveInterval*> LiveIntervalSet;
 
+    typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
+
     MachineFunction *mf;
     const TargetMachine *tm;
     const TargetRegisterInfo *tri;
@@ -130,6 +132,7 @@ namespace {
     AllowedSetMap allowedSets;
     LiveIntervalSet vregIntervalsToAlloc,
                     emptyVRegIntervals;
+    NodeVector problemNodes;
 
 
     /// Builds a PBQP cost vector.
@@ -174,7 +177,7 @@ namespace {
     /// allocation problem for this function.
     ///
     /// @return a PBQP solver object for the register allocation problem.
-    PBQP::SimpleGraph constructPBQPProblem();
+    PBQP::Graph constructPBQPProblem();
 
     /// \brief Adds a stack interval if the given live interval has been
     /// spilled. Used to support stack slot coloring.
@@ -510,11 +513,10 @@ void PBQPRegAlloc::findVRegIntervalsToAlloc() {
   }
 }
 
-PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
+PBQP::Graph PBQPRegAlloc::constructPBQPProblem() {
 
   typedef std::vector<const LiveInterval*> LIVector;
   typedef std::vector<unsigned> RegVector;
-  typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector;
 
   // This will store the physical intervals for easy reference.
   LIVector physIntervals;
@@ -553,8 +555,8 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
   }
 
   // Construct a PBQP solver for this problem
-  PBQP::SimpleGraph problem;
-  NodeVector problemNodes(vregIntervalsToAlloc.size());
+  PBQP::Graph problem;
+  problemNodes.resize(vregIntervalsToAlloc.size());
 
   // Resize allowedSets container appropriately.
   allowedSets.resize(vregIntervalsToAlloc.size());
@@ -657,12 +659,7 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
     }
   }
 
-  problem.assignNodeIDs();
-
   assert(problem.getNumNodes() == allowedSets.size());
-  for (unsigned i = 0; i < allowedSets.size(); ++i) {
-    assert(problem.getNodeItr(i) == problemNodes[i]);
-  }
 /*
   std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
             << problem.getNumEdges() << " edges.\n";
@@ -696,10 +693,6 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
 
 bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
 
-  // Assert that this is a valid solution to the regalloc problem.
-  assert(solution.getCost() != std::numeric_limits<PBQP::PBQPNum>::infinity() &&
-         "Invalid (infinite cost) solution for PBQP problem.");
-
   // Set to true if we have any spills
   bool anotherRoundNeeded = false;
 
@@ -709,7 +702,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
   // Iterate over the nodes mapping the PBQP solution to a register assignment.
   for (unsigned node = 0; node < node2LI.size(); ++node) {
     unsigned virtReg = node2LI[node]->reg,
-             allocSelection = solution.getSelection(node);
+             allocSelection = solution.getSelection(problemNodes[node]);
 
 
     // If the PBQP solution is non-zero it's a physical register...
@@ -849,7 +842,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
 
   vrm = &getAnalysis<VirtRegMap>();
 
-  DEBUG(dbgs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n");
+  DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
 
   // Allocator main loop:
   //
@@ -876,10 +869,9 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
     while (!pbqpAllocComplete) {
       DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
 
-      PBQP::SimpleGraph problem = constructPBQPProblem();
-      PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver;
-      problem.assignNodeIDs();
-      PBQP::Solution solution = solver.solve(problem);
+      PBQP::Graph problem = constructPBQPProblem();
+      PBQP::Solution solution =
+        PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
 
       pbqpAllocComplete = mapPBQPToRegAlloc(solution);
 
@@ -895,6 +887,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
   li2Node.clear();
   node2LI.clear();
   allowedSets.clear();
+  problemNodes.clear();
 
   DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");