Re-apply r202551, which introduced new PBQP solver.

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

11 files changed, 1536 insertions, 1928 deletions

diff --git a/include/llvm/CodeGen/PBQP/CostAllocator.h b/include/llvm/CodeGen/PBQP/CostAllocator.h
new file mode 100644
index 0000000000..164633453e
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/CostAllocator.h
@@ -0,0 +1,147 @@
+//===---------- CostAllocator.h - PBQP Cost Allocator -----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines classes conforming to the PBQP cost value manager concept.
+//
+// Cost value managers are memory managers for PBQP cost values (vectors and
+// matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
+// of edges on the largest function in SPEC2006).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_COSTALLOCATOR_H
+#define LLVM_COSTALLOCATOR_H
+
+#include <set>
+#include <type_traits>
+
+namespace PBQP {
+
+template <typename CostT,
+          typename CostKeyTComparator>
+class CostPool {
+public:
+
+  class PoolEntry {
+  public:
+    template <typename CostKeyT>
+    PoolEntry(CostPool &pool, CostKeyT cost)
+      : pool(pool), cost(std::move(cost)), refCount(0) {}
+    ~PoolEntry() { pool.removeEntry(this); }
+    void incRef() { ++refCount; }
+    bool decRef() { --refCount; return (refCount == 0); }
+    CostT& getCost() { return cost; }
+    const CostT& getCost() const { return cost; }
+  private:
+    CostPool &pool;
+    CostT cost;
+    std::size_t refCount;
+  };
+
+  class PoolRef {
+  public:
+    PoolRef(PoolEntry *entry) : entry(entry) {
+      this->entry->incRef();
+    }
+    PoolRef(const PoolRef &r) {
+      entry = r.entry;
+      entry->incRef();
+    }
+    PoolRef& operator=(const PoolRef &r) {
+      assert(entry != 0 && "entry should not be null.");
+      PoolEntry *temp = r.entry;
+      temp->incRef();
+      entry->decRef();
+      entry = temp;
+      return *this;
+    }
+
+    ~PoolRef() {
+      if (entry->decRef())
+        delete entry;
+    }
+    void reset(PoolEntry *entry) {
+      entry->incRef();
+      this->entry->decRef();
+      this->entry = entry;
+    }
+    CostT& operator*() { return entry->getCost(); }
+    const CostT& operator*() const { return entry->getCost(); }
+    CostT* operator->() { return &entry->getCost(); }
+    const CostT* operator->() const { return &entry->getCost(); }
+  private:
+    PoolEntry *entry;
+  };
+
+private:
+  class EntryComparator {
+  public:
+    template <typename CostKeyT>
+    typename std::enable_if<
+               !std::is_same<PoolEntry*,
+                             typename std::remove_const<CostKeyT>::type>::value,
+               bool>::type
+    operator()(const PoolEntry* a, const CostKeyT &b) {
+      return compare(a->getCost(), b);
+    }
+    bool operator()(const PoolEntry* a, const PoolEntry* b) {
+      return compare(a->getCost(), b->getCost());
+    }
+  private:
+    CostKeyTComparator compare;
+  };
+
+  typedef std::set<PoolEntry*, EntryComparator> EntrySet;
+
+  EntrySet entrySet;
+
+  void removeEntry(PoolEntry *p) { entrySet.erase(p); }
+
+public:
+
+  template <typename CostKeyT>
+  PoolRef getCost(CostKeyT costKey) {
+    typename EntrySet::iterator itr =
+      std::lower_bound(entrySet.begin(), entrySet.end(), costKey,
+                       EntryComparator());
+
+    if (itr != entrySet.end() && costKey == (*itr)->getCost())
+      return PoolRef(*itr);
+
+    PoolEntry *p = new PoolEntry(*this, std::move(costKey));
+    entrySet.insert(itr, p);
+    return PoolRef(p);
+  }
+};
+
+template <typename VectorT, typename VectorTComparator,
+          typename MatrixT, typename MatrixTComparator>
+class PoolCostAllocator {
+private:
+  typedef CostPool<VectorT, VectorTComparator> VectorCostPool;
+  typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
+public:
+  typedef VectorT Vector;
+  typedef MatrixT Matrix;
+  typedef typename VectorCostPool::PoolRef VectorPtr;
+  typedef typename MatrixCostPool::PoolRef MatrixPtr;
+
+  template <typename VectorKeyT>
+  VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
+
+  template <typename MatrixKeyT>
+  MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
+private:
+  VectorCostPool vectorPool;
+  MatrixCostPool matrixPool;
+};
+
+}
+
+#endif // LLVM_COSTALLOCATOR_H
diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h
index 0737143924..7ce95c7e73 100644
--- a/include/llvm/CodeGen/PBQP/Graph.h
+++ b/include/llvm/CodeGen/PBQP/Graph.h
@@ -15,414 +15,526 @@
 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
 #define LLVM_CODEGEN_PBQP_GRAPH_H
 
-#include "Math.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
+#include "llvm/Support/Compiler.h"
 #include <list>
 #include <map>
 #include <set>
 
 namespace PBQP {
 
-  /// PBQP Graph class.
-  /// Instances of this class describe PBQP problems.
-  class Graph {
+  class GraphBase {
   public:
-
     typedef unsigned NodeId;
     typedef unsigned EdgeId;
+  };
 
+  /// PBQP Graph class.
+  /// Instances of this class describe PBQP problems.
+  ///
+  template <typename SolverT>
+  class Graph : public GraphBase {
   private:
-
-    typedef std::set<NodeId> AdjEdgeList;
-
+    typedef typename SolverT::CostAllocator CostAllocator;
   public:
-
-    typedef AdjEdgeList::iterator AdjEdgeItr;
+    typedef typename SolverT::RawVector RawVector;
+    typedef typename SolverT::RawMatrix RawMatrix;
+    typedef typename SolverT::Vector Vector;
+    typedef typename SolverT::Matrix Matrix;
+    typedef typename CostAllocator::VectorPtr VectorPtr;
+    typedef typename CostAllocator::MatrixPtr MatrixPtr;
+    typedef typename SolverT::NodeMetadata NodeMetadata;
+    typedef typename SolverT::EdgeMetadata EdgeMetadata;
 
   private:
 
     class NodeEntry {
-    private:
-      Vector costs;
-      AdjEdgeList adjEdges;
-      void *data;
-      NodeEntry() : costs(0, 0) {}
     public:
-      NodeEntry(const Vector &costs) : costs(costs), data(0) {}
-      Vector& getCosts() { return costs; }
-      const Vector& getCosts() const { return costs; }
-      unsigned getDegree() const { return adjEdges.size(); }
-      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
-      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
-      AdjEdgeItr addEdge(EdgeId e) {
-        return adjEdges.insert(adjEdges.end(), e);
-      }
-      void removeEdge(AdjEdgeItr ae) {
-        adjEdges.erase(ae);
-      }
-      void setData(void *data) { this->data = data; }
-      void* getData() { return data; }
+      typedef std::set<NodeId> AdjEdgeList;
+      typedef AdjEdgeList::const_iterator AdjEdgeItr;
+      NodeEntry(VectorPtr Costs) : Costs(Costs) {}
+
+      VectorPtr Costs;
+      NodeMetadata Metadata;
+      AdjEdgeList AdjEdgeIds;
     };
 
     class EdgeEntry {
-    private:
-      NodeId node1, node2;
-      Matrix costs;
-      AdjEdgeItr node1AEItr, node2AEItr;
-      void *data;
-      EdgeEntry() : costs(0, 0, 0), data(0) {}
     public:
-      EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs)
-        : node1(node1), node2(node2), costs(costs) {}
-      NodeId getNode1() const { return node1; }
-      NodeId getNode2() const { return node2; }
-      Matrix& getCosts() { return costs; }
-      const Matrix& getCosts() const { return costs; }
-      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
-      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
-      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
-      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
-      void setData(void *data) { this->data = data; }
-      void *getData() { return data; }
+      EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
+        : Costs(Costs), N1Id(N1Id), N2Id(N2Id) {}
+      void invalidate() {
+        N1Id = N2Id = Graph::invalidNodeId();
+        Costs = nullptr;
+      }
+      NodeId getN1Id() const { return N1Id; }
+      NodeId getN2Id() const { return N2Id; }
+      MatrixPtr Costs;
+      EdgeMetadata Metadata;
+    private:
+      NodeId N1Id, N2Id;
     };
 
     // ----- MEMBERS -----
 
+    CostAllocator CostAlloc;
+    SolverT *Solver;
+
     typedef std::vector<NodeEntry> NodeVector;
     typedef std::vector<NodeId> FreeNodeVector;
-    NodeVector nodes;
-    FreeNodeVector freeNodes;
+    NodeVector Nodes;
+    FreeNodeVector FreeNodeIds;
 
     typedef std::vector<EdgeEntry> EdgeVector;
     typedef std::vector<EdgeId> FreeEdgeVector;
-    EdgeVector edges;
-    FreeEdgeVector freeEdges;
+    EdgeVector Edges;
+    FreeEdgeVector FreeEdgeIds;
 
     // ----- INTERNAL METHODS -----
 
-    NodeEntry& getNode(NodeId nId) { return nodes[nId]; }
-    const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; }
+    NodeEntry& getNode(NodeId NId) { return Nodes[NId]; }
+    const NodeEntry& getNode(NodeId NId) const { return Nodes[NId]; }
 
-    EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; }
-    const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; }
+    EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
+    const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
 
-    NodeId addConstructedNode(const NodeEntry &n) {
-      NodeId nodeId = 0;
-      if (!freeNodes.empty()) {
-        nodeId = freeNodes.back();
-        freeNodes.pop_back();
-        nodes[nodeId] = n;
+    NodeId addConstructedNode(const NodeEntry &N) {
+      NodeId NId = 0;
+      if (!FreeNodeIds.empty()) {
+        NId = FreeNodeIds.back();
+        FreeNodeIds.pop_back();
+        Nodes[NId] = std::move(N);
       } else {
-        nodeId = nodes.size();
-        nodes.push_back(n);
+        NId = Nodes.size();
+        Nodes.push_back(std::move(N));
       }
-      return nodeId;
+      return NId;
     }
 
-    EdgeId addConstructedEdge(const EdgeEntry &e) {
-      assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() &&
+    EdgeId addConstructedEdge(const EdgeEntry &E) {
+      assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
              "Attempt to add duplicate edge.");
-      EdgeId edgeId = 0;
-      if (!freeEdges.empty()) {
-        edgeId = freeEdges.back();
-        freeEdges.pop_back();
-        edges[edgeId] = e;
+      EdgeId EId = 0;
+      if (!FreeEdgeIds.empty()) {
+        EId = FreeEdgeIds.back();
+        FreeEdgeIds.pop_back();
+        Edges[EId] = std::move(E);
       } else {
-        edgeId = edges.size();
-        edges.push_back(e);
+        EId = Edges.size();
+        Edges.push_back(std::move(E));
       }
 
-      EdgeEntry &ne = getEdge(edgeId);
-      NodeEntry &n1 = getNode(ne.getNode1());
-      NodeEntry &n2 = getNode(ne.getNode2());
+      EdgeEntry &NE = getEdge(EId);
+      NodeEntry &N1 = getNode(NE.getN1Id());
+      NodeEntry &N2 = getNode(NE.getN2Id());
 
       // Sanity check on matrix dimensions:
-      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
-             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
+      assert((N1.Costs->getLength() == NE.Costs->getRows()) &&
+             (N2.Costs->getLength() == NE.Costs->getCols()) &&
              "Edge cost dimensions do not match node costs dimensions.");
 
-      ne.setNode1AEItr(n1.addEdge(edgeId));
-      ne.setNode2AEItr(n2.addEdge(edgeId));
-      return edgeId;
+      N1.AdjEdgeIds.insert(EId);
+      N2.AdjEdgeIds.insert(EId);
+      return EId;
     }
 
-    Graph(const Graph &other) {}
-    void operator=(const Graph &other) {}
+    Graph(const Graph &Other) {}
+    void operator=(const Graph &Other) {}
 
   public:
 
+    typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
+
     class NodeItr {
     public:
-      NodeItr(NodeId nodeId, const Graph &g)
-        : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) {
-        this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId
+      NodeItr(NodeId CurNId, const Graph &G)
+        : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
+        this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
       }
 
-      bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; }
-      bool operator!=(const NodeItr& n) const { return !(*this == n); }
-      NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; }
-      NodeId operator*() const { return nodeId; }
+      bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
+      bool operator!=(const NodeItr &O) const { return !(*this == O); }
+      NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
+      NodeId operator*() const { return CurNId; }
 
     private:
-      NodeId findNextInUse(NodeId n) const {
-        while (n < endNodeId &&
-               std::find(freeNodes.begin(), freeNodes.end(), n) !=
-                 freeNodes.end()) {
-          ++n;
+      NodeId findNextInUse(NodeId NId) const {
+        while (NId < EndNId &&
+               std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
+                 FreeNodeIds.end()) {
+          ++NId;
         }
-        return n;
+        return NId;
       }
 
-      NodeId nodeId, endNodeId;
-      const FreeNodeVector& freeNodes;
+      NodeId CurNId, EndNId;
+      const FreeNodeVector &FreeNodeIds;
     };
 
     class EdgeItr {
     public:
-      EdgeItr(EdgeId edgeId, const Graph &g)
-        : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) {
-        this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId
+      EdgeItr(EdgeId CurEId, const Graph &G)
+        : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
+        this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
       }
 
-      bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; }
-      bool operator!=(const EdgeItr& n) const { return !(*this == n); }
-      EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; }
-      EdgeId operator*() const { return edgeId; }
+      bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
+      bool operator!=(const EdgeItr &O) const { return !(*this == O); }
+      EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
+      EdgeId operator*() const { return CurEId; }
 
     private:
-      EdgeId findNextInUse(EdgeId n) const {
-        while (n < endEdgeId &&
-               std::find(freeEdges.begin(), freeEdges.end(), n) !=
-                 freeEdges.end()) {
-          ++n;
+      EdgeId findNextInUse(EdgeId EId) const {
+        while (EId < EndEId &&
+               std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) !=
+               FreeEdgeIds.end()) {
+          ++EId;
         }
-        return n;
+        return EId;
       }
 
-      EdgeId edgeId, endEdgeId;
-      const FreeEdgeVector& freeEdges;
+      EdgeId CurEId, EndEId;
+      const FreeEdgeVector &FreeEdgeIds;
+    };
+
+    class NodeIdSet {
+    public:
+      NodeIdSet(const Graph &G) : G(G) { }
+      NodeItr begin() const { return NodeItr(0, G); }
+      NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
+      bool empty() const { return G.Nodes.empty(); }
+      typename NodeVector::size_type size() const {
+        return G.Nodes.size() - G.FreeNodeIds.size();
+      }
+    private:
+      const Graph& G;
+    };
+
+    class EdgeIdSet {
+    public:
+      EdgeIdSet(const Graph &G) : G(G) { }
+      EdgeItr begin() const { return EdgeItr(0, G); }
+      EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
+      bool empty() const { return G.Edges.empty(); }
+      typename NodeVector::size_type size() const {
+        return G.Edges.size() - G.FreeEdgeIds.size();
+      }
+    private:
+      const Graph& G;
+    };
+
+    class AdjEdgeIdSet {
+    public:
+      AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
+      typename NodeEntry::AdjEdgeItr begin() const {
+        return NE.AdjEdgeIds.begin();
+      }
+      typename NodeEntry::AdjEdgeItr end() const {
+        return NE.AdjEdgeIds.end();
+      }
+      bool empty() const { return NE.AdjEdges.empty(); }
+      typename NodeEntry::AdjEdgeList::size_type size() const {
+        return NE.AdjEdgeIds.size();
+      }
+    private:
+      const NodeEntry &NE;
     };
 
     /// \brief Construct an empty PBQP graph.
-    Graph() {}
+    Graph() : Solver(nullptr) { }
+
+    /// \brief Lock this graph to the given solver instance in preparation
+    /// for running the solver. This method will call solver.handleAddNode for
+    /// each node in the graph, and handleAddEdge for each edge, to give the
+    /// solver an opportunity to set up any requried metadata.
+    void setSolver(SolverT &S) {
+      assert(Solver == nullptr && "Solver already set. Call unsetSolver().");
+      Solver = &S;
+      for (auto NId : nodeIds())
+        Solver->handleAddNode(NId);
+      for (auto EId : edgeIds())
+        Solver->handleAddEdge(EId);
+    }
+
+    /// \brief Release from solver instance.
+    void unsetSolver() {
+      assert(Solver != nullptr && "Solver not set.");
+      Solver = nullptr;
+    }
 
     /// \brief Add a node with the given costs.
-    /// @param costs Cost vector for the new node.
+    /// @param Costs Cost vector for the new node.
     /// @return Node iterator for the added node.
-    NodeId addNode(const Vector &costs) {
-      return addConstructedNode(NodeEntry(costs));
+    template <typename OtherVectorT>
+    NodeId addNode(OtherVectorT Costs) {
+      // Get cost vector from the problem domain
+      VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
+      NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
+      if (Solver)
+        Solver->handleAddNode(NId);
+      return NId;
     }
 
     /// \brief Add an edge between the given nodes with the given costs.
-    /// @param n1Id First node.
-    /// @param n2Id Second node.
+    /// @param N1Id First node.
+    /// @param N2Id Second node.
     /// @return Edge iterator for the added edge.
-    EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) {
-      assert(getNodeCosts(n1Id).getLength() == costs.getRows() &&
-             getNodeCosts(n2Id).getLength() == costs.getCols() &&
+    template <typename OtherVectorT>
+    EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
+      assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
+             getNodeCosts(N2Id).getLength() == Costs.getCols() &&
              "Matrix dimensions mismatch.");
-      return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs));
+      // Get cost matrix from the problem domain.
+      MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
+      EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
+      if (Solver)
+        Solver->handleAddEdge(EId);
+      return EId;
     }
 
+    /// \brief Returns true if the graph is empty.
+    bool empty() const { return NodeIdSet(*this).empty(); }
+
+    NodeIdSet nodeIds() const { return NodeIdSet(*this); }
+    EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
+
+    AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
+
     /// \brief Get the number of nodes in the graph.
     /// @return Number of nodes in the graph.
-    unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); }
+    unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
 
     /// \brief Get the number of edges in the graph.
     /// @return Number of edges in the graph.
-    unsigned getNumEdges() const { return edges.size() - freeEdges.size(); }
+    unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
 
-    /// \brief Get a node's cost vector.
-    /// @param nId Node id.
+    /// \brief Set a node's cost vector.
+    /// @param NId Node to update.
+    /// @param Costs New costs to set.
     /// @return Node cost vector.
-    Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); }
+    template <typename OtherVectorT>
+    void setNodeCosts(NodeId NId, OtherVectorT Costs) {
+      VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
+      if (Solver)
+        Solver->handleSetNodeCosts(NId, *AllocatedCosts);
+      getNode(NId).Costs = AllocatedCosts;
+    }
 
     /// \brief Get a node's cost vector (const version).
-    /// @param nId Node id.
+    /// @param NId Node id.
     /// @return Node cost vector.
-    const Vector& getNodeCosts(NodeId nId) const {
-      return getNode(nId).getCosts();
+    const Vector& getNodeCosts(NodeId NId) const {
+      return *getNode(NId).Costs;
     }
 
-    /// \brief Set a node's data pointer.
-    /// @param nId Node id.
-    /// @param data Pointer to node data.
-    ///
-    /// Typically used by a PBQP solver to attach data to aid in solution.
-    void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); }
-
-    /// \brief Get the node's data pointer.
-    /// @param nId Node id.
-    /// @return Pointer to node data.
-    void* getNodeData(NodeId nId) { return getNode(nId).getData(); }
-
-    /// \brief Get an edge's cost matrix.
-    /// @param eId Edge id.
-    /// @return Edge cost matrix.
-    Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); }
-
-    /// \brief Get an edge's cost matrix (const version).
-    /// @param eId Edge id.
-    /// @return Edge cost matrix.
-    const Matrix& getEdgeCosts(EdgeId eId) const {
-      return getEdge(eId).getCosts();
+    NodeMetadata& getNodeMetadata(NodeId NId) {
+      return getNode(NId).Metadata;
     }
 
-    /// \brief Set an edge's data pointer.
-    /// @param eId Edge id.
-    /// @param data Pointer to edge data.
-    ///
-    /// Typically used by a PBQP solver to attach data to aid in solution.
-    void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); }
-
-    /// \brief Get an edge's data pointer.
-    /// @param eId Edge id.
-    /// @return Pointer to edge data.
-    void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); }
-
-    /// \brief Get a node's degree.
-    /// @param nId Node id.
-    /// @return The degree of the node.
-    unsigned getNodeDegree(NodeId nId) const {
-      return getNode(nId).getDegree();
+    const NodeMetadata& getNodeMetadata(NodeId NId) const {
+      return getNode(NId).Metadata;
     }
 
-    /// \brief Begin iterator for node set.
-    NodeItr nodesBegin() const { return NodeItr(0, *this);  }
-
-    /// \brief End iterator for node set.
-    NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); }
+    typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
+      return getNode(NId).AdjEdgeIds.size();
+    }
 
-    /// \brief Begin iterator for edge set.
-    EdgeItr edgesBegin() const { return EdgeItr(0, *this); }
+    /// \brief Set an edge's cost matrix.
+    /// @param EId Edge id.
+    /// @param Costs New cost matrix.
+    template <typename OtherMatrixT>
+    void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
+      MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
+      if (Solver)
+        Solver->handleSetEdgeCosts(EId, *AllocatedCosts);
+      getEdge(EId).Costs = AllocatedCosts;
+    }
 
-    /// \brief End iterator for edge set.
-    EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); }
+    /// \brief Get an edge's cost matrix (const version).
+    /// @param EId Edge id.
+    /// @return Edge cost matrix.
+    const Matrix& getEdgeCosts(EdgeId EId) const { return *getEdge(EId).Costs; }
 
-    /// \brief Get begin iterator for adjacent edge set.
-    /// @param nId Node id.
-    /// @return Begin iterator for the set of edges connected to the given node.
-    AdjEdgeItr adjEdgesBegin(NodeId nId) {
-      return getNode(nId).edgesBegin();
+    EdgeMetadata& getEdgeMetadata(EdgeId NId) {
+      return getEdge(NId).Metadata;
     }
 
-    /// \brief Get end iterator for adjacent edge set.
-    /// @param nId Node id.
-    /// @return End iterator for the set of edges connected to the given node.
-    AdjEdgeItr adjEdgesEnd(NodeId nId) {
-      return getNode(nId).edgesEnd();
+    const EdgeMetadata& getEdgeMetadata(EdgeId NId) const {
+      return getEdge(NId).Metadata;
     }
 
     /// \brief Get the first node connected to this edge.
-    /// @param eId Edge id.
+    /// @param EId Edge id.
     /// @return The first node connected to the given edge.
-    NodeId getEdgeNode1(EdgeId eId) {
-      return getEdge(eId).getNode1();
+    NodeId getEdgeNode1Id(EdgeId EId) {
+      return getEdge(EId).getN1Id();
     }
 
     /// \brief Get the second node connected to this edge.
-    /// @param eId Edge id.
+    /// @param EId Edge id.
     /// @return The second node connected to the given edge.
-    NodeId getEdgeNode2(EdgeId eId) {
-      return getEdge(eId).getNode2();
+    NodeId getEdgeNode2Id(EdgeId EId) {
+      return getEdge(EId).getN2Id();
     }
 
     /// \brief Get the "other" node connected to this edge.
-    /// @param eId Edge id.
-    /// @param nId Node id for the "given" node.
+    /// @param EId Edge id.
+    /// @param NId Node id for the "given" node.
     /// @return The iterator for the "other" node connected to this edge.
-    NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) {
-      EdgeEntry &e = getEdge(eId);
-      if (e.getNode1() == nId) {
-        return e.getNode2();
+    NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
+      EdgeEntry &E = getEdge(EId);
+      if (E.getN1Id() == NId) {
+        return E.getN2Id();
       } // else
-      return e.getNode1();
+      return E.getN1Id();
+    }
+
+    /// \brief Returns a value representing an invalid (non-existant) node.
+    static NodeId invalidNodeId() {
+      return std::numeric_limits<NodeId>::max();
     }
 
-    EdgeId invalidEdgeId() const {
+    /// \brief Returns a value representing an invalid (non-existant) edge.
+    static EdgeId invalidEdgeId() {
       return std::numeric_limits<EdgeId>::max();
     }
 
     /// \brief Get the edge connecting two nodes.
-    /// @param n1Id First node id.
-    /// @param n2Id Second node id.
-    /// @return An id for edge (n1Id, n2Id) if such an edge exists,
+    /// @param N1Id First node id.
+    /// @param N2Id Second node id.
+    /// @return An id for edge (N1Id, N2Id) if such an edge exists,
     ///         otherwise returns an invalid edge id.
-    EdgeId findEdge(NodeId n1Id, NodeId n2Id) {
-      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id);
-         aeItr != aeEnd; ++aeItr) {
-        if ((getEdgeNode1(*aeItr) == n2Id) ||
-            (getEdgeNode2(*aeItr) == n2Id)) {
-          return *aeItr;
+    EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
+      for (auto AEId : adjEdgeIds(N1Id)) {
+        if ((getEdgeNode1Id(AEId) == N2Id) ||
+            (getEdgeNode2Id(AEId) == N2Id)) {
+          return AEId;
         }
       }
       return invalidEdgeId();
     }
 
     /// \brief Remove a node from the graph.
-    /// @param nId Node id.
-    void removeNode(NodeId nId) {
-      NodeEntry &n = getNode(nId);
-      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) {
-        EdgeId eId = *itr;
-        removeEdge(eId);
+    /// @param NId Node id.
+    void removeNode(NodeId NId) {
+      if (Solver)
+        Solver->handleRemoveNode(NId);
+      NodeEntry &N = getNode(NId);
+      // TODO: Can this be for-each'd?
+      for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
+                      AEEnd = N.adjEdgesEnd();
+           AEItr != AEEnd;) {
+        EdgeId EId = *AEItr;
+        ++AEItr;
+        removeEdge(EId);
       }
-      freeNodes.push_back(nId);
+      FreeNodeIds.push_back(NId);
+    }
+
+    /// \brief Disconnect an edge from the given node.
+    ///
+    /// Removes the given edge from the adjacency list of the given node.
+    /// This operation leaves the edge in an 'asymmetric' state: It will no
+    /// longer appear in an iteration over the given node's (NId's) edges, but
+    /// will appear in an iteration over the 'other', unnamed node's edges.
+    ///
+    /// This does not correspond to any normal graph operation, but exists to
+    /// support efficient PBQP graph-reduction based solvers. It is used to
+    /// 'effectively' remove the unnamed node from the graph while the solver
+    /// is performing the reduction. The solver will later call reconnectNode
+    /// to restore the edge in the named node's adjacency list.
+    ///
+    /// Since the degree of a node is the number of connected edges,
+    /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
+    /// drop by 1.
+    ///
+    /// A disconnected edge WILL still appear in an iteration over the graph
+    /// edges.
+    ///
+    /// A disconnected edge should not be removed from the graph, it should be
+    /// reconnected first.
+    ///
+    /// A disconnected edge can be reconnected by calling the reconnectEdge
+    /// method.
+    void disconnectEdge(EdgeId EId, NodeId NId) {
+      if (Solver)
+        Solver->handleDisconnectEdge(EId, NId);
+      NodeEntry &N = getNode(NId);
+      N.AdjEdgeIds.erase(EId);
+    }
+
+    /// \brief Convenience method to disconnect all neighbours from the given
+    ///        node.
+    void disconnectAllNeighborsFromNode(NodeId NId) {
+      for (auto AEId : adjEdgeIds(NId))
+        disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
+    }
+
+    /// \brief Re-attach an edge to its nodes.
+    ///
+    /// Adds an edge that had been previously disconnected back into the
+    /// adjacency set of the nodes that the edge connects.
+    void reconnectEdge(EdgeId EId, NodeId NId) {
+      NodeEntry &N = getNode(NId);
+      N.addAdjEdge(EId);
+      if (Solver)
+        Solver->handleReconnectEdge(EId, NId);
     }
 
     /// \brief Remove an edge from the graph.
-    /// @param eId Edge id.
-    void removeEdge(EdgeId eId) {
-      EdgeEntry &e = getEdge(eId);
-      NodeEntry &n1 = getNode(e.getNode1());
-      NodeEntry &n2 = getNode(e.getNode2());
-      n1.removeEdge(e.getNode1AEItr());
-      n2.removeEdge(e.getNode2AEItr());
-      freeEdges.push_back(eId);
+    /// @param EId Edge id.
+    void removeEdge(EdgeId EId) {
+      if (Solver)
+        Solver->handleRemoveEdge(EId);
+      EdgeEntry &E = getEdge(EId);
+      NodeEntry &N1 = getNode(E.getNode1());
+      NodeEntry &N2 = getNode(E.getNode2());
+      N1.removeEdge(EId);
+      N2.removeEdge(EId);
+      FreeEdgeIds.push_back(EId);
+      Edges[EId].invalidate();
     }
 
     /// \brief Remove all nodes and edges from the graph.
     void clear() {
-      nodes.clear();
-      freeNodes.clear();
-      edges.clear();
-      freeEdges.clear();
+      Nodes.clear();
+      FreeNodeIds.clear();
+      Edges.clear();
+      FreeEdgeIds.clear();
     }
 
     /// \brief Dump a graph to an output stream.
     template <typename OStream>
-    void dump(OStream &os) {
-      os << getNumNodes() << " " << getNumEdges() << "\n";
-
-      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
-           nodeItr != nodeEnd; ++nodeItr) {
-        const Vector& v = getNodeCosts(*nodeItr);
-        os << "\n" << v.getLength() << "\n";
-        assert(v.getLength() != 0 && "Empty vector in graph.");
-        os << v[0];
-        for (unsigned i = 1; i < v.getLength(); ++i) {
-          os << " " << v[i];
+    void dump(OStream &OS) {
+      OS << nodeIds().size() << " " << edgeIds().size() << "\n";
+
+      for (auto NId : nodeIds()) {
+        const Vector& V = getNodeCosts(NId);
+        OS << "\n" << V.getLength() << "\n";
+        assert(V.getLength() != 0 && "Empty vector in graph.");
+        OS << V[0];
+        for (unsigned i = 1; i < V.getLength(); ++i) {
+          OS << " " << V[i];
         }
-        os << "\n";
+        OS << "\n";
       }
 
-      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
-           edgeItr != edgeEnd; ++edgeItr) {
-        NodeId n1 = getEdgeNode1(*edgeItr);
-        NodeId n2 = getEdgeNode2(*edgeItr);
-        assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
-        const Matrix& m = getEdgeCosts(*edgeItr);
-        os << "\n" << n1 << " " << n2 << "\n"
-           << m.getRows() << " " << m.getCols() << "\n";
-        assert(m.getRows() != 0 && "No rows in matrix.");
-        assert(m.getCols() != 0 && "No cols in matrix.");
-        for (unsigned i = 0; i < m.getRows(); ++i) {
-          os << m[i][0];
-          for (unsigned j = 1; j < m.getCols(); ++j) {
-            os << " " << m[i][j];
+      for (auto EId : edgeIds()) {
+        NodeId N1Id = getEdgeNode1Id(EId);
+        NodeId N2Id = getEdgeNode2Id(EId);
+        assert(N1Id != N2Id && "PBQP graphs shound not have self-edges.");
+        const Matrix& M = getEdgeCosts(EId);
+        OS << "\n" << N1Id << " " << N2Id << "\n"
+           << M.getRows() << " " << M.getCols() << "\n";
+        assert(M.getRows() != 0 && "No rows in matrix.");
+        assert(M.getCols() != 0 && "No cols in matrix.");
+        for (unsigned i = 0; i < M.getRows(); ++i) {
+          OS << M[i][0];
+          for (unsigned j = 1; j < M.getCols(); ++j) {
+            OS << " " << M[i][j];
           }
-          os << "\n";
+          OS << "\n";
         }
       }
     }
@@ -430,49 +542,27 @@ namespace PBQP {
     /// \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";
+    void printDot(OStream &OS) {
+      OS << "graph {\n";
+      for (auto NId : nodeIds()) {
+        OS << "  node" << NId << " [ label=\""
+           << NId << ": " << getNodeCosts(NId) << "\" ]\n";
       }
-
-      os << "  edge [ len=" << getNumNodes() << " ]\n";
-
-      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
-           edgeItr != edgeEnd; ++edgeItr) {
-
-        os << "  node" << getEdgeNode1(*edgeItr)
-           << " -- node" << getEdgeNode2(*edgeItr)
+      OS << "  edge [ len=" << nodeIds().size() << " ]\n";
+      for (auto EId : edgeIds()) {
+        OS << "  node" << getEdgeNode1Id(EId)
+           << " -- node" << getEdgeNode2Id(EId)
            << " [ label=\"";
-
-        const Matrix &edgeCosts = getEdgeCosts(*edgeItr);
-
-        for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
-          os << edgeCosts.getRowAsVector(i) << "\\n";
+        const Matrix &EdgeCosts = getEdgeCosts(EId);
+        for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
+          OS << EdgeCosts.getRowAsVector(i) << "\\n";
         }
-        os << "\" ]\n";
+        OS << "\" ]\n";
       }
-      os << "}\n";
+      OS << "}\n";
     }
-
   };
 
-//  void Graph::copyFrom(const Graph &other) {
-//     std::map<Graph::ConstNodeItr, Graph::NodeItr,
-//              NodeItrComparator> nodeMap;
-
-//      for (Graph::ConstNodeItr nItr = other.nodesBegin(),
-//                              nEnd = other.nodesEnd();
-//          nItr != nEnd; ++nItr) {
-//       nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
-//     }
-//  }
-
 }
 
 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h
deleted file mode 100644
index 8bcbb9ed1d..0000000000
--- a/include/llvm/CodeGen/PBQP/HeuristicBase.h
+++ /dev/null
@@ -1,247 +0,0 @@
-//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H
-#define LLVM_CODEGEN_PBQP_HEURISTICBASE_H
-
-#include "HeuristicSolver.h"
-
-namespace PBQP {
-
-  /// \brief Abstract base class for heuristic implementations.
-  ///
-  /// This class provides a handy base for heuristic implementations with common
-  /// solver behaviour implemented for a number of methods.
-  ///
-  /// To implement your own heuristic using this class as a base you'll have to
-  /// implement, as a minimum, the following methods:
-  /// <ul>
-  ///   <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the
-  ///        heuristic reduction list.
-  ///   <li> void heuristicReduce() : Perform a single heuristic reduction.
-  ///   <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent)
-  ///        change to the cost matrix on the given edge (by R2).
-  ///   <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new
-  ///        costs on the given edge.
-  ///   <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new
-  ///        edge into the PBQP graph (by R2).
-  ///   <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the
-  ///        disconnection of the given edge from the given node.
-  ///   <li> A constructor for your derived class : to pass back a reference to
-  ///        the solver which is using this heuristic.
-  /// </ul>
-  ///
-  /// These methods are implemented in this class for documentation purposes,
-  /// but will assert if called.
-  ///
-  /// Note that this class uses the curiously recursive template idiom to
-  /// forward calls to the derived class. These methods need not be made
-  /// virtual, and indeed probably shouldn't for performance reasons.
-  ///
-  /// You'll also need to provide NodeData and EdgeData structs in your class.
-  /// These can be used to attach data relevant to your heuristic to each
-  /// node/edge in the PBQP graph.
-
-  template <typename HImpl>
-  class HeuristicBase {
-  private:
-
-    typedef std::list<Graph::NodeId> 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::NodeId nId) {
-      optimalList.insert(optimalList.end(), nId);
-    }
-
-  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::NodeId nId) {
-      if (g.getNodeDegree(nId) < 3)
-        return true;
-      // else
-      return false;
-    }
-
-    /// \brief Add the given node to the list of nodes to be optimally reduced.
-    /// @param nId Node id 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::NodeId nId) {
-      optimalList.push_back(nId);
-    }
-
-    /// \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::NodeId nId = optimalList.front();
-      optimalList.pop_front();
-
-      switch (s.getSolverDegree(nId)) {
-        case 0: s.applyR0(nId); break;
-        case 1: s.applyR1(nId); break;
-        case 2: s.applyR2(nId); break;
-        default: llvm_unreachable(
-                        "Optimal reductions of degree > 2 nodes is invalid.");
-      }
-
-      return true;
-    }
-
-    /// \brief Perform the PBQP reduction process.
-    ///
-    /// Reduces the problem to the empty graph by repeated application of the
-    /// reduction rules R0, R1, R2 and RN.
-    /// R0, R1 or R2 are always applied if possible before RN is used.
-    void reduce() {
-      bool finished = false;
-
-      while (!finished) {
-        if (!optimalReduce()) {
-          if (impl().heuristicReduce()) {
-            getSolver().recordRN();
-          } else {
-            finished = true;
-          }
-        }
-      }
-    }
-
-    /// \brief Add a node to the heuristic reduce list.
-    /// @param nId Node id to add to the heuristic reduce list.
-    void addToHeuristicList(Graph::NodeId nId) {
-      llvm_unreachable("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.
-    bool heuristicReduce() {
-      llvm_unreachable("Must be implemented in derived class.");
-      return false;
-    }
-
-    /// \brief Prepare a change in the costs on the given edge.
-    /// @param eId Edge id.
-    void preUpdateEdgeCosts(Graph::EdgeId eId) {
-      llvm_unreachable("Must be implemented in derived class.");
-    }
-
-    /// \brief Handle the change in the costs on the given edge.
-    /// @param eId Edge id.
-    void postUpdateEdgeCostts(Graph::EdgeId eId) {
-      llvm_unreachable("Must be implemented in derived class.");
-    }
-
-    /// \brief Handle the addition of a new edge into the PBQP graph.
-    /// @param eId Edge id for the added edge.
-    void handleAddEdge(Graph::EdgeId eId) {
-      llvm_unreachable("Must be implemented in derived class.");
-    }
-
-    /// \brief Handle disconnection of an edge from a node.
-    /// @param eId Edge id for edge being disconnected.
-    /// @param nId Node id 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::EdgeId eId, Graph::NodeId nId) {
-      llvm_unreachable("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/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
deleted file mode 100644
index e26ca02fff..0000000000
--- a/include/llvm/CodeGen/PBQP/HeuristicSolver.h
+++ /dev/null
@@ -1,618 +0,0 @@
-//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Heuristic PBQP solver. This solver is able to perform optimal reductions for
-// nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is
-// used to select a node for reduction.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
-#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
-
-#include "Graph.h"
-#include "Solution.h"
-#include <limits>
-#include <vector>
-
-namespace PBQP {
-
-  /// \brief Heuristic PBQP solver implementation.
-  ///
-  /// This class should usually be created (and destroyed) indirectly via a call
-  /// to HeuristicSolver<HImpl>::solve(Graph&).
-  /// See the comments for HeuristicSolver.
-  ///
-  /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules,
-  /// backpropagation phase, and maintains the internal copy of the graph on
-  /// which the reduction is carried out (the original being kept to facilitate
-  /// backpropagation).
-  template <typename HImpl>
-  class HeuristicSolverImpl {
-  private:
-
-    typedef typename HImpl::NodeData HeuristicNodeData;
-    typedef typename HImpl::EdgeData HeuristicEdgeData;
-
-    typedef std::list<Graph::EdgeId> SolverEdges;
-
-  public:
-
-    /// \brief Iterator type for edges in the solver graph.
-    typedef SolverEdges::iterator SolverEdgeItr;
-
-  private:
-
-    class NodeData {
-    public:
-      NodeData() : solverDegree(0) {}
-
-      HeuristicNodeData& getHeuristicData() { return hData; }
-
-      SolverEdgeItr addSolverEdge(Graph::EdgeId eId) {
-        ++solverDegree;
-        return solverEdges.insert(solverEdges.end(), eId);
-      }
-
-      void removeSolverEdge(SolverEdgeItr seItr) {
-        --solverDegree;
-        solverEdges.erase(seItr);
-      }
-
-      SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
-      SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
-      unsigned getSolverDegree() const { return solverDegree; }
-      void clearSolverEdges() {
-        solverDegree = 0;
-        solverEdges.clear();
-      }
-
-    private:
-      HeuristicNodeData hData;
-      unsigned solverDegree;
-      SolverEdges solverEdges;
-    };
-
-    class EdgeData {
-    public:
-      HeuristicEdgeData& getHeuristicData() { return hData; }
-
-      void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
-        this->n1SolverEdgeItr = n1SolverEdgeItr;
-      }
-
-      SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
-
-      void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
-        this->n2SolverEdgeItr = n2SolverEdgeItr;
-      }
-
-      SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
-
-    private:
-
-      HeuristicEdgeData hData;
-      SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
-    };
-
-    Graph &g;
-    HImpl h;
-    Solution s;
-    std::vector<Graph::NodeId> stack;
-
-    typedef std::list<NodeData> NodeDataList;
-    NodeDataList nodeDataList;
-
-    typedef std::list<EdgeData> EdgeDataList;
-    EdgeDataList edgeDataList;
-
-  public:
-
-    /// \brief Construct a heuristic solver implementation to solve the given
-    ///        graph.
-    /// @param g The graph representing the problem instance to be solved.
-    HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}
-
-    /// \brief Get the graph being solved by this solver.
-    /// @return The graph representing the problem instance being solved by this
-    ///         solver.
-    Graph& getGraph() { return g; }
-
-    /// \brief Get the heuristic data attached to the given node.
-    /// @param nId Node id.
-    /// @return The heuristic data attached to the given node.
-    HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) {
-      return getSolverNodeData(nId).getHeuristicData();
-    }
-
-    /// \brief Get the heuristic data attached to the given edge.
-    /// @param eId Edge id.
-    /// @return The heuristic data attached to the given node.
-    HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
-      return getSolverEdgeData(eId).getHeuristicData();
-    }
-
-    /// \brief Begin iterator for the set of edges adjacent to the given node in
-    ///        the solver graph.
-    /// @param nId Node id.
-    /// @return Begin iterator for the set of edges adjacent to the given node
-    ///         in the solver graph.
-    SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) {
-      return getSolverNodeData(nId).solverEdgesBegin();
-    }
-
-    /// \brief End iterator for the set of edges adjacent to the given node in
-    ///        the solver graph.
-    /// @param nId Node id.
-    /// @return End iterator for the set of edges adjacent to the given node in
-    ///         the solver graph.
-    SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) {
-      return getSolverNodeData(nId).solverEdgesEnd();
-    }
-
-    /// \brief Remove a node from the solver graph.
-    /// @param eId Edge id 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::EdgeId eId) {
-      EdgeData &eData = getSolverEdgeData(eId);
-      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)),
-               &n2Data = getSolverNodeData(g.getEdgeNode2(eId));
-
-      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 nId Node id to add to the reduction stack.
-    void pushToStack(Graph::NodeId nId) {
-      getSolverNodeData(nId).clearSolverEdges();
-      stack.push_back(nId);
-    }
-
-    /// \brief Returns the solver degree of the given node.
-    /// @param nId Node id for which degree is requested.
-    /// @return Node degree in the <i>solver</i> graph (not the original graph).
-    unsigned getSolverDegree(Graph::NodeId nId) {
-      return  getSolverNodeData(nId).getSolverDegree();
-    }
-
-    /// \brief Set the solution of the given node.
-    /// @param nId Node id to set solution for.
-    /// @param selection Selection for node.
-    void setSolution(const Graph::NodeId &nId, unsigned selection) {
-      s.setSelection(nId, selection);
-
-      for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId),
-                             aeEnd = g.adjEdgesEnd(nId);
-           aeItr != aeEnd; ++aeItr) {
-        Graph::EdgeId eId(*aeItr);
-        Graph::NodeId anId(g.getEdgeOtherNode(eId, nId));
-        getSolverNodeData(anId).addSolverEdge(eId);
-      }
-    }
-
-    /// \brief Apply rule R0.
-    /// @param nId Node id for node to apply R0 to.
-    ///
-    /// Node will be automatically pushed to the solver stack.
-    void applyR0(Graph::NodeId nId) {
-      assert(getSolverNodeData(nId).getSolverDegree() == 0 &&
-             "R0 applied to node with degree != 0.");
-
-      // Nothing to do. Just push the node onto the reduction stack.
-      pushToStack(nId);
-
-      s.recordR0();
-    }
-
-    /// \brief Apply rule R1.
-    /// @param xnId Node id for node to apply R1 to.
-    ///
-    /// Node will be automatically pushed to the solver stack.
-    void applyR1(Graph::NodeId xnId) {
-      NodeData &nd = getSolverNodeData(xnId);
-      assert(nd.getSolverDegree() == 1 &&
-             "R1 applied to node with degree != 1.");
-
-      Graph::EdgeId eId = *nd.solverEdgesBegin();
-
-      const Matrix &eCosts = g.getEdgeCosts(eId);
-      const Vector &xCosts = g.getNodeCosts(xnId);
-
-      // Duplicate a little to avoid transposing matrices.
-      if (xnId == g.getEdgeNode1(eId)) {
-        Graph::NodeId ynId = g.getEdgeNode2(eId);
-        Vector &yCosts = g.getNodeCosts(ynId);
-        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(eId, ynId);
-     } else {
-        Graph::NodeId ynId = g.getEdgeNode1(eId);
-        Vector &yCosts = g.getNodeCosts(ynId);
-        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(eId, ynId);
-      }
-      removeSolverEdge(eId);
-      assert(nd.getSolverDegree() == 0 &&
-             "Degree 1 with edge removed should be 0.");
-      pushToStack(xnId);
-      s.recordR1();
-    }
-
-    /// \brief Apply rule R2.
-    /// @param xnId Node id for node to apply R2 to.
-    ///
-    /// Node will be automatically pushed to the solver stack.
-    void applyR2(Graph::NodeId xnId) {
-      assert(getSolverNodeData(xnId).getSolverDegree() == 2 &&
-             "R2 applied to node with degree != 2.");
-
-      NodeData &nd = getSolverNodeData(xnId);
-      const Vector &xCosts = g.getNodeCosts(xnId);
-
-      SolverEdgeItr aeItr = nd.solverEdgesBegin();
-      Graph::EdgeId yxeId = *aeItr,
-                    zxeId = *(++aeItr);
-
-      Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId),
-                    znId = g.getEdgeOtherNode(zxeId, xnId);
-
-      bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId),
-           flipEdge2 = (g.getEdgeNode1(zxeId) == xnId);
-
-      const Matrix *yxeCosts = flipEdge1 ?
-        new Matrix(g.getEdgeCosts(yxeId).transpose()) :
-        &g.getEdgeCosts(yxeId);
-
-      const Matrix *zxeCosts = flipEdge2 ?
-        new Matrix(g.getEdgeCosts(zxeId).transpose()) :
-        &g.getEdgeCosts(zxeId);
-
-      unsigned xLen = xCosts.getLength(),
-               yLen = yxeCosts->getRows(),
-               zLen = zxeCosts->getRows();
-
-      Matrix delta(yLen, zLen);
-
-      for (unsigned i = 0; i < yLen; ++i) {
-        for (unsigned j = 0; j < zLen; ++j) {
-          PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0];
-          for (unsigned k = 1; k < xLen; ++k) {
-            PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k];
-            if (c < min) {
-              min = c;
-            }
-          }
-          delta[i][j] = min;
-        }
-      }
-
-      if (flipEdge1)
-        delete yxeCosts;
-
-      if (flipEdge2)
-        delete zxeCosts;
-
-      Graph::EdgeId yzeId = g.findEdge(ynId, znId);
-      bool addedEdge = false;
-
-      if (yzeId == g.invalidEdgeId()) {
-        yzeId = g.addEdge(ynId, znId, delta);
-        addedEdge = true;
-      } else {
-        Matrix &yzeCosts = g.getEdgeCosts(yzeId);
-        h.preUpdateEdgeCosts(yzeId);
-        if (ynId == g.getEdgeNode1(yzeId)) {
-          yzeCosts += delta;
-        } else {
-          yzeCosts += delta.transpose();
-        }
-      }
-
-      bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId);
-
-      if (!addedEdge) {
-        // If we modified the edge costs let the heuristic know.
-        h.postUpdateEdgeCosts(yzeId);
-      }
-
-      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(yzeId, ynId);
-          h.handleRemoveEdge(yzeId, znId);
-          removeSolverEdge(yzeId);
-        }
-        g.removeEdge(yzeId);
-      } else if (addedEdge) {
-        // If the edge was added, and non-null, finish setting it up, add it to
-        // the solver & notify heuristic.
-        edgeDataList.push_back(EdgeData());
-        g.setEdgeData(yzeId, &edgeDataList.back());
-        addSolverEdge(yzeId);
-        h.handleAddEdge(yzeId);
-      }
-
-      h.handleRemoveEdge(yxeId, ynId);
-      removeSolverEdge(yxeId);
-      h.handleRemoveEdge(zxeId, znId);
-      removeSolverEdge(zxeId);
-
-      pushToStack(xnId);
-      s.recordR2();
-    }
-
-    /// \brief Record an application of the RN rule.
-    ///
-    /// For use by the HeuristicBase.
-    void recordRN() { s.recordRN(); }
-
-  private:
-
-    NodeData& getSolverNodeData(Graph::NodeId nId) {
-      return *static_cast<NodeData*>(g.getNodeData(nId));
-    }
-
-    EdgeData& getSolverEdgeData(Graph::EdgeId eId) {
-      return *static_cast<EdgeData*>(g.getEdgeData(eId));
-    }
-
-    void addSolverEdge(Graph::EdgeId eId) {
-      EdgeData &eData = getSolverEdgeData(eId);
-      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)),
-               &n2Data = getSolverNodeData(g.getEdgeNode2(eId));
-
-      eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId));
-      eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId));
-    }
-
-    void setup() {
-      if (h.solverRunSimplify()) {
-        simplify();
-      }
-
-      // Create node data objects.
-      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
-           nItr != nEnd; ++nItr) {
-        nodeDataList.push_back(NodeData());
-        g.setNodeData(*nItr, &nodeDataList.back());
-      }
-
-      // Create edge data objects.
-      for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
-           eItr != eEnd; ++eItr) {
-        edgeDataList.push_back(EdgeData());
-        g.setEdgeData(*eItr, &edgeDataList.back());
-        addSolverEdge(*eItr);
-      }
-    }
-
-    void simplify() {
-      disconnectTrivialNodes();
-      eliminateIndependentEdges();
-    }
-
-    // Eliminate trivial nodes.
-    void disconnectTrivialNodes() {
-      unsigned numDisconnected = 0;
-
-      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
-           nItr != nEnd; ++nItr) {
-
-        Graph::NodeId nId = *nItr;
-
-        if (g.getNodeCosts(nId).getLength() == 1) {
-
-          std::vector<Graph::EdgeId> edgesToRemove;
-
-          for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId),
-                                 aeEnd = g.adjEdgesEnd(nId);
-               aeItr != aeEnd; ++aeItr) {
-
-            Graph::EdgeId eId = *aeItr;
-
-            if (g.getEdgeNode1(eId) == nId) {
-              Graph::NodeId otherNodeId = g.getEdgeNode2(eId);
-              g.getNodeCosts(otherNodeId) +=
-                g.getEdgeCosts(eId).getRowAsVector(0);
-            }
-            else {
-              Graph::NodeId otherNodeId = g.getEdgeNode1(eId);
-              g.getNodeCosts(otherNodeId) +=
-                g.getEdgeCosts(eId).getColAsVector(0);
-            }
-
-            edgesToRemove.push_back(eId);
-          }
-
-          if (!edgesToRemove.empty())
-            ++numDisconnected;
-
-          while (!edgesToRemove.empty()) {
-            g.removeEdge(edgesToRemove.back());
-            edgesToRemove.pop_back();
-          }
-        }
-      }
-    }
-
-    void eliminateIndependentEdges() {
-      std::vector<Graph::EdgeId> edgesToProcess;
-      unsigned numEliminated = 0;
-
-      for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
-           eItr != eEnd; ++eItr) {
-        edgesToProcess.push_back(*eItr);
-      }
-
-      while (!edgesToProcess.empty()) {
-        if (tryToEliminateEdge(edgesToProcess.back()))
-          ++numEliminated;
-        edgesToProcess.pop_back();
-      }
-    }
-
-    bool tryToEliminateEdge(Graph::EdgeId eId) {
-      if (tryNormaliseEdgeMatrix(eId)) {
-        g.removeEdge(eId);
-        return true;
-      }
-      return false;
-    }
-
-    bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) {
-
-      const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity();
-
-      Matrix &edgeCosts = g.getEdgeCosts(eId);
-      Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)),
-             &vCosts = g.getNodeCosts(g.getEdgeNode2(eId));
-
-      for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
-        PBQPNum rowMin = infinity;
-
-        for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
-          if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin)
-            rowMin = edgeCosts[r][c];
-        }
-
-        uCosts[r] += rowMin;
-
-        if (rowMin != infinity) {
-          edgeCosts.subFromRow(r, rowMin);
-        }
-        else {
-          edgeCosts.setRow(r, 0);
-        }
-      }
-
-      for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
-        PBQPNum colMin = infinity;
-
-        for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
-          if (uCosts[r] != infinity && edgeCosts[r][c] < colMin)
-            colMin = edgeCosts[r][c];
-        }
-
-        vCosts[c] += colMin;
-
-        if (colMin != infinity) {
-          edgeCosts.subFromCol(c, colMin);
-        }
-        else {
-          edgeCosts.setCol(c, 0);
-        }
-      }
-
-      return edgeCosts.isZero();
-    }
-
-    void backpropagate() {
-      while (!stack.empty()) {
-        computeSolution(stack.back());
-        stack.pop_back();
-      }
-    }
-
-    void computeSolution(Graph::NodeId nId) {
-
-      NodeData &nodeData = getSolverNodeData(nId);
-
-      Vector v(g.getNodeCosts(nId));
-
-      // Solve based on existing solved edges.
-      for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
-                         solvedEdgeEnd = nodeData.solverEdgesEnd();
-           solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
-
-        Graph::EdgeId eId(*solvedEdgeItr);
-        Matrix &edgeCosts = g.getEdgeCosts(eId);
-
-        if (nId == g.getEdgeNode1(eId)) {
-          Graph::NodeId adjNode(g.getEdgeNode2(eId));
-          unsigned adjSolution = s.getSelection(adjNode);
-          v += edgeCosts.getColAsVector(adjSolution);
-        }
-        else {
-          Graph::NodeId adjNode(g.getEdgeNode1(eId));
-          unsigned adjSolution = s.getSelection(adjNode);
-          v += edgeCosts.getRowAsVector(adjSolution);
-        }
-
-      }
-
-      setSolution(nId, v.minIndex());
-    }
-
-    void cleanup() {
-      h.cleanup();
-      nodeDataList.clear();
-      edgeDataList.clear();
-    }
-  };
-
-  /// \brief PBQP heuristic solver class.
-  ///
-  /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
-  /// by calling
-  /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
-  ///
-  /// The choice of heuristic for the H parameter will affect both the solver
-  /// speed and solution quality. The heuristic should be chosen based on the
-  /// nature of the problem being solved.
-  /// Currently the only solver included with LLVM is the Briggs heuristic for
-  /// register allocation.
-  template <typename HImpl>
-  class HeuristicSolver {
-  public:
-    static Solution solve(Graph &g) {
-      HeuristicSolverImpl<HImpl> hs(g);
-      return hs.computeSolution();
-    }
-  };
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
deleted file mode 100644
index c355c2c2f8..0000000000
--- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
+++ /dev/null
@@ -1,468 +0,0 @@
-//===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This class implements the Briggs test for "allocability" of nodes in a
-// PBQP graph representing a register allocation problem. Nodes which can be
-// proven allocable (by a safe and relatively accurate test) are removed from
-// the PBQP graph first. If no provably allocable node is present in the graph
-// then the node with the minimal spill-cost to degree ratio is removed.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
-#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
-
-#include "../HeuristicBase.h"
-#include "../HeuristicSolver.h"
-#include <limits>
-
-namespace PBQP {
-  namespace Heuristics {
-
-    /// \brief PBQP Heuristic which applies an allocability test based on
-    ///        Briggs.
-    ///
-    /// This heuristic assumes that the elements of cost vectors in the PBQP
-    /// problem represent storage options, with the first being the spill
-    /// option and subsequent elements representing legal registers for the
-    /// corresponding node. Edge cost matrices are likewise assumed to represent
-    /// register constraints.
-    /// If one or more nodes can be proven allocable by this heuristic (by
-    /// inspection of their constraint matrices) then the allocable node of
-    /// highest degree is selected for the next reduction and pushed to the
-    /// solver stack. If no nodes can be proven allocable then the node with
-    /// the lowest estimated spill cost is selected and push to the solver stack
-    /// instead.
-    ///
-    /// This implementation is built on top of HeuristicBase.
-    class Briggs : public HeuristicBase<Briggs> {
-    private:
-
-      class LinkDegreeComparator {
-      public:
-        LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
-        bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
-          if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id))
-            return true;
-          return false;
-        }
-      private:
-        HeuristicSolverImpl<Briggs> *s;
-      };
-
-      class SpillCostComparator {
-      public:
-        SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
-          : s(&s), g(&s.getGraph()) {}
-        bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
-          const PBQP::Vector &cv1 = g->getNodeCosts(n1Id);
-          const PBQP::Vector &cv2 = g->getNodeCosts(n2Id);
-
-          PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id);
-          PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id);
-
-          if (cost1 < cost2)
-            return true;
-          return false;
-        }
-
-      private:
-        HeuristicSolverImpl<Briggs> *s;
-        Graph *g;
-      };
-
-      typedef std::list<Graph::NodeId> RNAllocableList;
-      typedef RNAllocableList::iterator RNAllocableListItr;
-
-      typedef std::list<Graph::NodeId> RNUnallocableList;
-      typedef RNUnallocableList::iterator RNUnallocableListItr;
-
-    public:
-
-      struct NodeData {
-        typedef std::vector<unsigned> UnsafeDegreesArray;
-        bool isHeuristic, isAllocable, isInitialized;
-        unsigned numDenied, numSafe;
-        UnsafeDegreesArray unsafeDegrees;
-        RNAllocableListItr rnaItr;
-        RNUnallocableListItr rnuItr;
-
-        NodeData()
-          : isHeuristic(false), isAllocable(false), isInitialized(false),
-            numDenied(0), numSafe(0) { }
-      };
-
-      struct EdgeData {
-        typedef std::vector<unsigned> UnsafeArray;
-        unsigned worst, reverseWorst;
-        UnsafeArray unsafe, reverseUnsafe;
-        bool isUpToDate;
-
-        EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
-      };
-
-      /// \brief Construct an instance of the Briggs heuristic.
-      /// @param solver A reference to the solver which is using this heuristic.
-      Briggs(HeuristicSolverImpl<Briggs> &solver) :
-        HeuristicBase<Briggs>(solver) {}
-
-      /// \brief Determine whether a node should be reduced using optimal
-      ///        reduction.
-      /// @param nId Node id 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::NodeId nId) {
-        if (getSolver().getSolverDegree(nId) < 3) {
-          return true;
-        }
-        // else
-        return false;
-      }
-
-      /// \brief Add a node to the heuristic reduce list.
-      /// @param nId Node id to add to the heuristic reduce list.
-      void addToHeuristicReduceList(Graph::NodeId nId) {
-        NodeData &nd = getHeuristicNodeData(nId);
-        initializeNode(nId);
-        nd.isHeuristic = true;
-        if (nd.isAllocable) {
-          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
-        } else {
-          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId);
-        }
-      }
-
-      /// \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::NodeId nId = *rnaItr;
-          rnAllocableList.erase(rnaItr);
-          handleRemoveNode(nId);
-          getSolver().pushToStack(nId);
-          return true;
-        } else if (!rnUnallocableList.empty()) {
-          RNUnallocableListItr rnuItr =
-            min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
-                        SpillCostComparator(getSolver()));
-          Graph::NodeId nId = *rnuItr;
-          rnUnallocableList.erase(rnuItr);
-          handleRemoveNode(nId);
-          getSolver().pushToStack(nId);
-          return true;
-        }
-        // else
-        return false;
-      }
-
-      /// \brief Prepare a change in the costs on the given edge.
-      /// @param eId Edge id.
-      void preUpdateEdgeCosts(Graph::EdgeId eId) {
-        Graph &g = getGraph();
-        Graph::NodeId n1Id = g.getEdgeNode1(eId),
-                      n2Id = g.getEdgeNode2(eId);
-        NodeData &n1 = getHeuristicNodeData(n1Id),
-                 &n2 = getHeuristicNodeData(n2Id);
-
-        if (n1.isHeuristic)
-          subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId));
-        if (n2.isHeuristic)
-          subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId));
-
-        EdgeData &ed = getHeuristicEdgeData(eId);
-        ed.isUpToDate = false;
-      }
-
-      /// \brief Handle the change in the costs on the given edge.
-      /// @param eId Edge id.
-      void postUpdateEdgeCosts(Graph::EdgeId eId) {
-        // This is effectively the same as adding a new edge now, since
-        // we've factored out the costs of the old one.
-        handleAddEdge(eId);
-      }
-
-      /// \brief Handle the addition of a new edge into the PBQP graph.
-      /// @param eId Edge id 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::EdgeId eId) {
-        Graph &g = getGraph();
-        Graph::NodeId n1Id = g.getEdgeNode1(eId),
-                      n2Id = g.getEdgeNode2(eId);
-        NodeData &n1 = getHeuristicNodeData(n1Id),
-                 &n2 = getHeuristicNodeData(n2Id);
-
-        // 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(eId);
-
-        // Update node 1 if it's managed by the heuristic.
-        if (n1.isHeuristic) {
-          bool n1WasAllocable = n1.isAllocable;
-          addEdgeContributions(eId, n1Id);
-          updateAllocability(n1Id);
-          if (n1WasAllocable && !n1.isAllocable) {
-            rnAllocableList.erase(n1.rnaItr);
-            n1.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n1Id);
-          }
-        }
-
-        // Likewise for node 2.
-        if (n2.isHeuristic) {
-          bool n2WasAllocable = n2.isAllocable;
-          addEdgeContributions(eId, n2Id);
-          updateAllocability(n2Id);
-          if (n2WasAllocable && !n2.isAllocable) {
-            rnAllocableList.erase(n2.rnaItr);
-            n2.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n2Id);
-          }
-        }
-      }
-
-      /// \brief Handle disconnection of an edge from a node.
-      /// @param eId Edge id for edge being disconnected.
-      /// @param nId Node id 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::EdgeId eId, Graph::NodeId nId) {
-        NodeData &nd =getHeuristicNodeData(nId);
-
-        // If the node is not managed by the heuristic there's nothing to be
-        // done.
-        if (!nd.isHeuristic)
-          return;
-
-        EdgeData &ed = getHeuristicEdgeData(eId);
-        (void)ed;
-        assert(ed.isUpToDate && "Edge data is not up to date.");
-
-        // Update node.
-        bool ndWasAllocable = nd.isAllocable;
-        subtractEdgeContributions(eId, nId);
-        updateAllocability(nId);
-
-        // If the node has gone optimal...
-        if (shouldOptimallyReduce(nId)) {
-          nd.isHeuristic = false;
-          addToOptimalReduceList(nId);
-          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(), nId);
-          }
-        }
-      }
-
-    private:
-
-      NodeData& getHeuristicNodeData(Graph::NodeId nId) {
-        return getSolver().getHeuristicNodeData(nId);
-      }
-
-      EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
-        return getSolver().getHeuristicEdgeData(eId);
-      }
-
-      // Work out what this edge will contribute to the allocability of the
-      // nodes connected to it.
-      void computeEdgeContributions(Graph::EdgeId eId) {
-        EdgeData &ed = getHeuristicEdgeData(eId);
-
-        if (ed.isUpToDate)
-          return; // Edge data is already up to date.
-
-        Matrix &eCosts = getGraph().getEdgeCosts(eId);
-
-        unsigned numRegs = eCosts.getRows() - 1,
-                 numReverseRegs = eCosts.getCols() - 1;
-
-        std::vector<unsigned> rowInfCounts(numRegs, 0),
-                              colInfCounts(numReverseRegs, 0);
-
-        ed.worst = 0;
-        ed.reverseWorst = 0;
-        ed.unsafe.clear();
-        ed.unsafe.resize(numRegs, 0);
-        ed.reverseUnsafe.clear();
-        ed.reverseUnsafe.resize(numReverseRegs, 0);
-
-        for (unsigned i = 0; i < numRegs; ++i) {
-          for (unsigned j = 0; j < numReverseRegs; ++j) {
-            if (eCosts[i + 1][j + 1] ==
-                  std::numeric_limits<PBQPNum>::infinity()) {
-              ed.unsafe[i] = 1;
-              ed.reverseUnsafe[j] = 1;
-              ++rowInfCounts[i];
-              ++colInfCounts[j];
-
-              if (colInfCounts[j] > ed.worst) {
-                ed.worst = colInfCounts[j];
-              }
-
-              if (rowInfCounts[i] > ed.reverseWorst) {
-                ed.reverseWorst = rowInfCounts[i];
-              }
-            }
-          }
-        }
-
-        ed.isUpToDate = true;
-      }
-
-      // Add the contributions of the given edge to the given node's
-      // numDenied and safe members. No action is taken other than to update
-      // these member values. Once updated these numbers can be used by clients
-      // to update the node's allocability.
-      void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
-        EdgeData &ed = getHeuristicEdgeData(eId);
-
-        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
-
-        NodeData &nd = getHeuristicNodeData(nId);
-        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
-
-        bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
-        EdgeData::UnsafeArray &unsafe =
-          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
-        nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
-
-        for (unsigned r = 0; r < numRegs; ++r) {
-          if (unsafe[r]) {
-            if (nd.unsafeDegrees[r]==0) {
-              --nd.numSafe;
-            }
-            ++nd.unsafeDegrees[r];
-          }
-        }
-      }
-
-      // Subtract the contributions of the given edge to the given node's
-      // numDenied and safe members. No action is taken other than to update
-      // these member values. Once updated these numbers can be used by clients
-      // to update the node's allocability.
-      void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
-        EdgeData &ed = getHeuristicEdgeData(eId);
-
-        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
-
-        NodeData &nd = getHeuristicNodeData(nId);
-        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
-
-        bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
-        EdgeData::UnsafeArray &unsafe =
-          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
-        nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
-
-        for (unsigned r = 0; r < numRegs; ++r) {
-          if (unsafe[r]) {
-            if (nd.unsafeDegrees[r] == 1) {
-              ++nd.numSafe;
-            }
-            --nd.unsafeDegrees[r];
-          }
-        }
-      }
-
-      void updateAllocability(Graph::NodeId nId) {
-        NodeData &nd = getHeuristicNodeData(nId);
-        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
-        nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
-      }
-
-      void initializeNode(Graph::NodeId nId) {
-        NodeData &nd = getHeuristicNodeData(nId);
-
-        if (nd.isInitialized)
-          return; // Node data is already up to date.
-
-        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
-
-        nd.numDenied = 0;
-        const Vector& nCosts = getGraph().getNodeCosts(nId);
-        for (unsigned i = 1; i < nCosts.getLength(); ++i) {
-          if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity())
-            ++nd.numDenied;
-        }
-
-        nd.numSafe = numRegs;
-        nd.unsafeDegrees.resize(numRegs, 0);
-
-        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
-
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId),
-                           aeEnd = getSolver().solverEdgesEnd(nId);
-             aeItr != aeEnd; ++aeItr) {
-
-          Graph::EdgeId eId = *aeItr;
-          computeEdgeContributions(eId);
-          addEdgeContributions(eId, nId);
-        }
-
-        updateAllocability(nId);
-        nd.isInitialized = true;
-      }
-
-      void handleRemoveNode(Graph::NodeId xnId) {
-        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
-        std::vector<Graph::EdgeId> edgesToRemove;
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId),
-                           aeEnd = getSolver().solverEdgesEnd(xnId);
-             aeItr != aeEnd; ++aeItr) {
-          Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId);
-          handleRemoveEdge(*aeItr, ynId);
-          edgesToRemove.push_back(*aeItr);
-        }
-        while (!edgesToRemove.empty()) {
-          getSolver().removeSolverEdge(edgesToRemove.back());
-          edgesToRemove.pop_back();
-        }
-      }
-
-      RNAllocableList rnAllocableList;
-      RNUnallocableList rnUnallocableList;
-    };
-
-  }
-}
-
-
-#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
diff --git a/include/llvm/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h
index 08f8b981ae..69a9d83cc0 100644
--- a/include/llvm/CodeGen/PBQP/Math.h
+++ b/include/llvm/CodeGen/PBQP/Math.h
@@ -20,268 +20,418 @@ typedef float PBQPNum;
 
 /// \brief PBQP Vector class.
 class Vector {
-  public:
-
-    /// \brief Construct a PBQP vector of the given size.
-    explicit Vector(unsigned length) :
-      length(length), data(new PBQPNum[length]) {
-      }
-
-    /// \brief Construct a PBQP vector with initializer.
-    Vector(unsigned length, PBQPNum initVal) :
-      length(length), data(new PBQPNum[length]) {
-        std::fill(data, data + length, initVal);
-      }
-
-    /// \brief Copy construct a PBQP vector.
-    Vector(const Vector &v) :
-      length(v.length), data(new PBQPNum[length]) {
-        std::copy(v.data, v.data + length, data);
-      }
-
-    /// \brief Destroy this vector, return its memory.
-    ~Vector() { delete[] data; }
-
-    /// \brief Assignment operator.
-    Vector& operator=(const Vector &v) {
-      delete[] data;
-      length = v.length;
-      data = new PBQPNum[length];
-      std::copy(v.data, v.data + length, data);
-      return *this;
-    }
-
-    /// \brief Return the length of the vector
-    unsigned getLength() const {
-      return length;
-    }
-
-    /// \brief Element access.
-    PBQPNum& operator[](unsigned index) {
-      assert(index < length && "Vector element access out of bounds.");
-      return data[index];
-    }
-
-    /// \brief Const element access.
-    const PBQPNum& operator[](unsigned index) const {
-      assert(index < length && "Vector element access out of bounds.");
-      return data[index];
-    }
-
-    /// \brief Add another vector to this one.
-    Vector& operator+=(const Vector &v) {
-      assert(length == v.length && "Vector length mismatch.");
-      std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 
-      return *this;
-    }
-
-    /// \brief Subtract another vector from this one.
-    Vector& operator-=(const Vector &v) {
-      assert(length == v.length && "Vector length mismatch.");
-      std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 
-      return *this;
-    }
-
-    /// \brief Returns the index of the minimum value in this vector
-    unsigned minIndex() const {
-      return std::min_element(data, data + length) - data;
-    }
-
-  private:
-    unsigned length;
-    PBQPNum *data;
+  friend class VectorComparator;
+public:
+
+  /// \brief Construct a PBQP vector of the given size.
+  explicit Vector(unsigned Length)
+    : Length(Length), Data(new PBQPNum[Length]) {
+    // llvm::dbgs() << "Constructing PBQP::Vector "
+    //              << this << " (length " << Length << ")\n";
+  }
+
+  /// \brief Construct a PBQP vector with initializer.
+  Vector(unsigned Length, PBQPNum InitVal)
+    : Length(Length), Data(new PBQPNum[Length]) {
+    // llvm::dbgs() << "Constructing PBQP::Vector "
+    //              << this << " (length " << Length << ", fill "
+    //              << InitVal << ")\n";
+    std::fill(Data, Data + Length, InitVal);
+  }
+
+  /// \brief Copy construct a PBQP vector.
+  Vector(const Vector &V)
+    : Length(V.Length), Data(new PBQPNum[Length]) {
+    // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this
+    //              << " from PBQP::Vector " << &V << "\n";
+    std::copy(V.Data, V.Data + Length, Data);
+  }
+
+  /// \brief Move construct a PBQP vector.
+  Vector(Vector &&V)
+    : Length(V.Length), Data(V.Data) {
+    V.Length = 0;
+    V.Data = nullptr;
+  }
+
+  /// \brief Destroy this vector, return its memory.
+  ~Vector() {
+    // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
+    delete[] Data;
+  }
+
+  /// \brief Copy-assignment operator.
+  Vector& operator=(const Vector &V) {
+    // llvm::dbgs() << "Assigning to PBQP::Vector " << this
+    //              << " from PBQP::Vector " << &V << "\n";
+    delete[] Data;
+    Length = V.Length;
+    Data = new PBQPNum[Length];
+    std::copy(V.Data, V.Data + Length, Data);
+    return *this;
+  }
+
+  /// \brief Move-assignment operator.
+  Vector& operator=(Vector &&V) {
+    delete[] Data;
+    Length = V.Length;
+    Data = V.Data;
+    V.Length = 0;
+    V.Data = nullptr;
+    return *this;
+  }
+
+  /// \brief Comparison operator.
+  bool operator==(const Vector &V) const {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    if (Length != V.Length)
+      return false;
+    return std::equal(Data, Data + Length, V.Data);
+  }
+
+  /// \brief Return the length of the vector
+  unsigned getLength() const {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    return Length;
+  }
+
+  /// \brief Element access.
+  PBQPNum& operator[](unsigned Index) {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    assert(Index < Length && "Vector element access out of bounds.");
+    return Data[Index];
+  }
+
+  /// \brief Const element access.
+  const PBQPNum& operator[](unsigned Index) const {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    assert(Index < Length && "Vector element access out of bounds.");
+    return Data[Index];
+  }
+
+  /// \brief Add another vector to this one.
+  Vector& operator+=(const Vector &V) {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    assert(Length == V.Length && "Vector length mismatch.");
+    std::transform(Data, Data + Length, V.Data, Data, std::plus<PBQPNum>());
+    return *this;
+  }
+
+  /// \brief Subtract another vector from this one.
+  Vector& operator-=(const Vector &V) {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    assert(Length == V.Length && "Vector length mismatch.");
+    std::transform(Data, Data + Length, V.Data, Data, std::minus<PBQPNum>());
+    return *this;
+  }
+
+  /// \brief Returns the index of the minimum value in this vector
+  unsigned minIndex() const {
+    assert(Length != 0 && Data != nullptr && "Invalid vector");
+    return std::min_element(Data, Data + Length) - Data;
+  }
+
+private:
+  unsigned Length;
+  PBQPNum *Data;
+};
+
+class VectorComparator {
+public:
+  bool operator()(const Vector &A, const Vector &B) {
+    if (A.Length < B.Length)
+      return true;
+    if (B.Length < A.Length)
+      return false;
+    char *AData = reinterpret_cast<char*>(A.Data);
+    char *BData = reinterpret_cast<char*>(B.Data);
+    return std::lexicographical_compare(AData,
+                                        AData + A.Length * sizeof(PBQPNum),
+                                        BData,
+                                        BData + A.Length * sizeof(PBQPNum));
+  }
 };
 
 /// \brief Output a textual representation of the given vector on the given
 ///        output stream.
 template <typename OStream>
-OStream& operator<<(OStream &os, const Vector &v) {
-  assert((v.getLength() != 0) && "Zero-length vector badness.");
+OStream& operator<<(OStream &OS, const Vector &V) {
+  assert((V.getLength() != 0) && "Zero-length vector badness.");
 
-  os << "[ " << v[0];
-  for (unsigned i = 1; i < v.getLength(); ++i) {
-    os << ", " << v[i];
-  }
-  os << " ]";
+  OS << "[ " << V[0];
+  for (unsigned i = 1; i < V.getLength(); ++i)
+    OS << ", " << V[i];
+  OS << " ]";
 
-  return os;
-} 
+  return OS;
+}
 
 
 /// \brief PBQP Matrix class
 class Matrix {
-  public:
-
-    /// \brief Construct a PBQP Matrix with the given dimensions.
-    Matrix(unsigned rows, unsigned cols) :
-      rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
-    }
-
-    /// \brief Construct a PBQP Matrix with the given dimensions and initial
-    /// value.
-    Matrix(unsigned rows, unsigned cols, PBQPNum initVal) :
-      rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
-        std::fill(data, data + (rows * cols), initVal);
-    }
-
-    /// \brief Copy construct a PBQP matrix.
-    Matrix(const Matrix &m) :
-      rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
-        std::copy(m.data, m.data + (rows * cols), data);  
-    }
-
-    /// \brief Destroy this matrix, return its memory.
-    ~Matrix() { delete[] data; }
-
-    /// \brief Assignment operator.
-    Matrix& operator=(const Matrix &m) {
-      delete[] data;
-      rows = m.rows; cols = m.cols;
-      data = new PBQPNum[rows * cols];
-      std::copy(m.data, m.data + (rows * cols), data);
-      return *this;
-    }
-
-    /// \brief Return the number of rows in this matrix.
-    unsigned getRows() const { return rows; }
-
-    /// \brief Return the number of cols in this matrix.
-    unsigned getCols() const { return cols; }
-
-    /// \brief Matrix element access.
-    PBQPNum* operator[](unsigned r) {
-      assert(r < rows && "Row out of bounds.");
-      return data + (r * cols);
-    }
-
-    /// \brief Matrix element access.
-    const PBQPNum* operator[](unsigned r) const {
-      assert(r < rows && "Row out of bounds.");
-      return data + (r * cols);
-    }
-
-    /// \brief Returns the given row as a vector.
-    Vector getRowAsVector(unsigned r) const {
-      Vector v(cols);
-      for (unsigned c = 0; c < cols; ++c)
-        v[c] = (*this)[r][c];
-      return v; 
-    }
-
-    /// \brief Returns the given column as a vector.
-    Vector getColAsVector(unsigned c) const {
-      Vector v(rows);
-      for (unsigned r = 0; r < rows; ++r)
-        v[r] = (*this)[r][c];
-      return v;
-    }
-
-    /// \brief Reset the matrix to the given value.
-    Matrix& reset(PBQPNum val = 0) {
-      std::fill(data, data + (rows * cols), val);
-      return *this;
-    }
-
-    /// \brief Set a single row of this matrix to the given value.
-    Matrix& setRow(unsigned r, PBQPNum val) {
-      assert(r < rows && "Row out of bounds.");
-      std::fill(data + (r * cols), data + ((r + 1) * cols), val);
-      return *this;
-    }
-
-    /// \brief Set a single column of this matrix to the given value.
-    Matrix& setCol(unsigned c, PBQPNum val) {
-      assert(c < cols && "Column out of bounds.");
-      for (unsigned r = 0; r < rows; ++r)
-        (*this)[r][c] = val;
-      return *this;
-    }
-
-    /// \brief Matrix transpose.
-    Matrix transpose() const {
-      Matrix m(cols, rows);
-      for (unsigned r = 0; r < rows; ++r)
-        for (unsigned c = 0; c < cols; ++c)
-          m[c][r] = (*this)[r][c];
-      return m;
-    }
-
-    /// \brief Returns the diagonal of the matrix as a vector.
-    ///
-    /// Matrix must be square.
-    Vector diagonalize() const {
-      assert(rows == cols && "Attempt to diagonalize non-square matrix.");
-
-      Vector v(rows);
-      for (unsigned r = 0; r < rows; ++r)
-        v[r] = (*this)[r][r];
-      return v;
-    } 
-
-    /// \brief Add the given matrix to this one.
-    Matrix& operator+=(const Matrix &m) {
-      assert(rows == m.rows && cols == m.cols &&
-          "Matrix dimensions mismatch.");
-      std::transform(data, data + (rows * cols), m.data, data,
-          std::plus<PBQPNum>());
-      return *this;
-    }
-
-    /// \brief Returns the minimum of the given row
-    PBQPNum getRowMin(unsigned r) const {
-      assert(r < rows && "Row out of bounds");
-      return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
-    }
-
-    /// \brief Returns the minimum of the given column
-    PBQPNum getColMin(unsigned c) const {
-      PBQPNum minElem = (*this)[0][c];
-      for (unsigned r = 1; r < rows; ++r)
-        if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
-      return minElem;
-    }
-
-    /// \brief Subtracts the given scalar from the elements of the given row.
-    Matrix& subFromRow(unsigned r, PBQPNum val) {
-      assert(r < rows && "Row out of bounds");
-      std::transform(data + (r * cols), data + ((r + 1) * cols),
-          data + (r * cols),
-          std::bind2nd(std::minus<PBQPNum>(), val));
-      return *this;
-    }
-
-    /// \brief Subtracts the given scalar from the elements of the given column.
-    Matrix& subFromCol(unsigned c, PBQPNum val) {
-      for (unsigned r = 0; r < rows; ++r)
-        (*this)[r][c] -= val;
-      return *this;
-    }
-
-    /// \brief Returns true if this is a zero matrix.
-    bool isZero() const {
-      return find_if(data, data + (rows * cols),
-          std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
-        data + (rows * cols);
-    }
-
-  private:
-    unsigned rows, cols;
-    PBQPNum *data;
+private:
+  friend class MatrixComparator;
+public:
+
+  /// \brief Construct a PBQP Matrix with the given dimensions.
+  Matrix(unsigned Rows, unsigned Cols) :
+    Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
+  }
+
+  /// \brief Construct a PBQP Matrix with the given dimensions and initial
+  /// value.
+  Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
+    : Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
+    std::fill(Data, Data + (Rows * Cols), InitVal);
+  }
+
+  /// \brief Copy construct a PBQP matrix.
+  Matrix(const Matrix &M)
+    : Rows(M.Rows), Cols(M.Cols), Data(new PBQPNum[Rows * Cols]) {
+    std::copy(M.Data, M.Data + (Rows * Cols), Data);
+  }
+
+  /// \brief Move construct a PBQP matrix.
+  Matrix(Matrix &&M)
+    : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
+    M.Rows = M.Cols = 0;
+    M.Data = nullptr;
+  }
+
+  /// \brief Destroy this matrix, return its memory.
+  ~Matrix() { delete[] Data; }
+
+  /// \brief Copy-assignment operator.
+  Matrix& operator=(const Matrix &M) {
+    delete[] Data;
+    Rows = M.Rows; Cols = M.Cols;
+    Data = new PBQPNum[Rows * Cols];
+    std::copy(M.Data, M.Data + (Rows * Cols), Data);
+    return *this;
+  }
+
+  /// \brief Move-assignment operator.
+  Matrix& operator=(Matrix &&M) {
+    delete[] Data;
+    Rows = M.Rows;
+    Cols = M.Cols;
+    Data = M.Data;
+    M.Rows = M.Cols = 0;
+    M.Data = nullptr;
+    return *this;
+  }
+
+  /// \brief Comparison operator.
+  bool operator==(const Matrix &M) const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    if (Rows != M.Rows || Cols != M.Cols)
+      return false;
+    return std::equal(Data, Data + (Rows * Cols), M.Data);
+  }
+
+  /// \brief Return the number of rows in this matrix.
+  unsigned getRows() const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    return Rows;
+  }
+
+  /// \brief Return the number of cols in this matrix.
+  unsigned getCols() const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    return Cols;
+  }
+
+  /// \brief Matrix element access.
+  PBQPNum* operator[](unsigned R) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds.");
+    return Data + (R * Cols);
+  }
+
+  /// \brief Matrix element access.
+  const PBQPNum* operator[](unsigned R) const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds.");
+    return Data + (R * Cols);
+  }
+
+  /// \brief Returns the given row as a vector.
+  Vector getRowAsVector(unsigned R) const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    Vector V(Cols);
+    for (unsigned C = 0; C < Cols; ++C)
+      V[C] = (*this)[R][C];
+    return V;
+  }
+
+  /// \brief Returns the given column as a vector.
+  Vector getColAsVector(unsigned C) const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    Vector V(Rows);
+    for (unsigned R = 0; R < Rows; ++R)
+      V[R] = (*this)[R][C];
+    return V;
+  }
+
+  /// \brief Reset the matrix to the given value.
+  Matrix& reset(PBQPNum Val = 0) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    std::fill(Data, Data + (Rows * Cols), Val);
+    return *this;
+  }
+
+  /// \brief Set a single row of this matrix to the given value.
+  Matrix& setRow(unsigned R, PBQPNum Val) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds.");
+    std::fill(Data + (R * Cols), Data + ((R + 1) * Cols), Val);
+    return *this;
+  }
+
+  /// \brief Set a single column of this matrix to the given value.
+  Matrix& setCol(unsigned C, PBQPNum Val) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(C < Cols && "Column out of bounds.");
+    for (unsigned R = 0; R < Rows; ++R)
+      (*this)[R][C] = Val;
+    return *this;
+  }
+
+  /// \brief Matrix transpose.
+  Matrix transpose() const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    Matrix M(Cols, Rows);
+    for (unsigned r = 0; r < Rows; ++r)
+      for (unsigned c = 0; c < Cols; ++c)
+        M[c][r] = (*this)[r][c];
+    return M;
+  }
+
+  /// \brief Returns the diagonal of the matrix as a vector.
+  ///
+  /// Matrix must be square.
+  Vector diagonalize() const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(Rows == Cols && "Attempt to diagonalize non-square matrix.");
+    Vector V(Rows);
+    for (unsigned r = 0; r < Rows; ++r)
+      V[r] = (*this)[r][r];
+    return V;
+  }
+
+  /// \brief Add the given matrix to this one.
+  Matrix& operator+=(const Matrix &M) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(Rows == M.Rows && Cols == M.Cols &&
+           "Matrix dimensions mismatch.");
+    std::transform(Data, Data + (Rows * Cols), M.Data, Data,
+                   std::plus<PBQPNum>());
+    return *this;
+  }
+
+  Matrix operator+(const Matrix &M) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    Matrix Tmp(*this);
+    Tmp += M;
+    return Tmp;
+  }
+
+  /// \brief Returns the minimum of the given row
+  PBQPNum getRowMin(unsigned R) const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds");
+    return *std::min_element(Data + (R * Cols), Data + ((R + 1) * Cols));
+  }
+
+  /// \brief Returns the minimum of the given column
+  PBQPNum getColMin(unsigned C) const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    PBQPNum MinElem = (*this)[0][C];
+    for (unsigned R = 1; R < Rows; ++R)
+      if ((*this)[R][C] < MinElem)
+        MinElem = (*this)[R][C];
+    return MinElem;
+  }
+
+  /// \brief Subtracts the given scalar from the elements of the given row.
+  Matrix& subFromRow(unsigned R, PBQPNum Val) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds");
+    std::transform(Data + (R * Cols), Data + ((R + 1) * Cols),
+                   Data + (R * Cols),
+                   std::bind2nd(std::minus<PBQPNum>(), Val));
+    return *this;
+  }
+
+  /// \brief Subtracts the given scalar from the elements of the given column.
+  Matrix& subFromCol(unsigned C, PBQPNum Val) {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    for (unsigned R = 0; R < Rows; ++R)
+      (*this)[R][C] -= Val;
+    return *this;
+  }
+
+  /// \brief Returns true if this is a zero matrix.
+  bool isZero() const {
+    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
+    return find_if(Data, Data + (Rows * Cols),
+                   std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
+      Data + (Rows * Cols);
+  }
+
+private:
+  unsigned Rows, Cols;
+  PBQPNum *Data;
+};
+
+class MatrixComparator {
+public:
+  bool operator()(const Matrix &A, const Matrix &B) {
+    if (A.Rows < B.Rows)
+      return true;
+    if (B.Rows < A.Rows)
+      return false;
+    if (A.Cols < B.Cols)
+      return true;
+    if (B.Cols < A.Cols)
+      return false;
+    char *AData = reinterpret_cast<char*>(A.Data);
+    char *BData = reinterpret_cast<char*>(B.Data);
+    return std::lexicographical_compare(
+             AData, AData + (A.Rows * A.Cols * sizeof(PBQPNum)),
+             BData, BData + (A.Rows * A.Cols * sizeof(PBQPNum)));
+  }
 };
 
 /// \brief Output a textual representation of the given matrix on the given
 ///        output stream.
 template <typename OStream>
-OStream& operator<<(OStream &os, const Matrix &m) {
-
-  assert((m.getRows() != 0) && "Zero-row matrix badness.");
+OStream& operator<<(OStream &OS, const Matrix &M) {
+  assert((M.getRows() != 0) && "Zero-row matrix badness.");
+  for (unsigned i = 0; i < M.getRows(); ++i)
+    OS << M.getRowAsVector(i);
+  return OS;
+}
 
-  for (unsigned i = 0; i < m.getRows(); ++i) {
-    os << m.getRowAsVector(i);
-  }
+template <typename Metadata>
+class MDVector : public Vector {
+public:
+  MDVector(const Vector &v) : Vector(v), md(*this) { }
+  MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
+  const Metadata& getMetadata() const { return md; }
+private:
+  Metadata md;
+};
 
-  return os;
-}
+template <typename Metadata>
+class MDMatrix : public Matrix {
+public:
+  MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
+  MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
+  const Metadata& getMetadata() const { return md; }
+private:
+  Metadata md;
+};
 
 }
 
diff --git a/include/llvm/CodeGen/PBQP/ReductionRules.h b/include/llvm/CodeGen/PBQP/ReductionRules.h
new file mode 100644
index 0000000000..a259c85327
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/ReductionRules.h
@@ -0,0 +1,194 @@
+//===----------- ReductionRules.h - Reduction Rules -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Reduction Rules.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_REDUCTIONRULES_H
+#define LLVM_REDUCTIONRULES_H
+
+#include "Graph.h"
+#include "Math.h"
+#include "Solution.h"
+
+namespace PBQP {
+
+  /// \brief Reduce a node of degree one.
+  ///
+  /// Propagate costs from the given node, which must be of degree one, to its
+  /// neighbor. Notify the problem domain.
+  template <typename GraphT>
+  void applyR1(GraphT &G, typename GraphT::NodeId NId) {
+    typedef typename GraphT::NodeId NodeId;
+    typedef typename GraphT::EdgeId EdgeId;
+    typedef typename GraphT::Vector Vector;
+    typedef typename GraphT::Matrix Matrix;
+    typedef typename GraphT::RawVector RawVector;
+
+    assert(G.getNodeDegree(NId) == 1 &&
+           "R1 applied to node with degree != 1.");
+
+    EdgeId EId = *G.adjEdgeIds(NId).begin();
+    NodeId MId = G.getEdgeOtherNodeId(EId, NId);
+
+    const Matrix &ECosts = G.getEdgeCosts(EId);
+    const Vector &XCosts = G.getNodeCosts(NId);
+    RawVector YCosts = G.getNodeCosts(MId);
+
+    // Duplicate a little to avoid transposing matrices.
+    if (NId == G.getEdgeNode1Id(EId)) {
+      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;
+      }
+    } else {
+      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;
+      }
+    }
+    G.setNodeCosts(MId, YCosts);
+    G.disconnectEdge(EId, MId);
+  }
+
+  template <typename GraphT>
+  void applyR2(GraphT &G, typename GraphT::NodeId NId) {
+    typedef typename GraphT::NodeId NodeId;
+    typedef typename GraphT::EdgeId EdgeId;
+    typedef typename GraphT::Vector Vector;
+    typedef typename GraphT::Matrix Matrix;
+    typedef typename GraphT::RawMatrix RawMatrix;
+
+    assert(G.getNodeDegree(NId) == 2 &&
+           "R2 applied to node with degree != 2.");
+
+    const Vector &XCosts = G.getNodeCosts(NId);
+
+    typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
+    EdgeId YXEId = *AEItr,
+           ZXEId = *(++AEItr);
+
+    NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
+           ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
+
+    bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
+         FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
+
+    const Matrix *YXECosts = FlipEdge1 ?
+      new Matrix(G.getEdgeCosts(YXEId).transpose()) :
+      &G.getEdgeCosts(YXEId);
+
+    const Matrix *ZXECosts = FlipEdge2 ?
+      new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
+      &G.getEdgeCosts(ZXEId);
+
+    unsigned XLen = XCosts.getLength(),
+      YLen = YXECosts->getRows(),
+      ZLen = ZXECosts->getRows();
+
+    RawMatrix Delta(YLen, ZLen);
+
+    for (unsigned i = 0; i < YLen; ++i) {
+      for (unsigned j = 0; j < ZLen; ++j) {
+        PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
+        for (unsigned k = 1; k < XLen; ++k) {
+          PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
+          if (C < Min) {
+            Min = C;
+          }
+        }
+        Delta[i][j] = Min;
+      }
+    }
+
+    if (FlipEdge1)
+      delete YXECosts;
+
+    if (FlipEdge2)
+      delete ZXECosts;
+
+    EdgeId YZEId = G.findEdge(YNId, ZNId);
+    bool AddedEdge = false;
+
+    if (YZEId == G.invalidEdgeId()) {
+      YZEId = G.addEdge(YNId, ZNId, Delta);
+      AddedEdge = true;
+    } else {
+      const Matrix &YZECosts = G.getEdgeCosts(YZEId);
+      if (YNId == G.getEdgeNode1Id(YZEId)) {
+        G.setEdgeCosts(YZEId, Delta + YZECosts);
+      } else {
+        G.setEdgeCosts(YZEId, Delta.transpose() + YZECosts);
+      }
+    }
+
+    G.disconnectEdge(YXEId, YNId);
+    G.disconnectEdge(ZXEId, ZNId);
+
+    // TODO: Try to normalize newly added/modified edge.
+  }
+
+
+  // \brief Find a solution to a fully reduced graph by backpropagation.
+  //
+  // Given a graph and a reduction order, pop each node from the reduction
+  // order and greedily compute a minimum solution based on the node costs, and
+  // the dependent costs due to previously solved nodes.
+  //
+  // Note - This does not return the graph to its original (pre-reduction)
+  //        state: the existing solvers destructively alter the node and edge
+  //        costs. Given that, the backpropagate function doesn't attempt to
+  //        replace the edges either, but leaves the graph in its reduced
+  //        state.
+  template <typename GraphT, typename StackT>
+  Solution backpropagate(GraphT& G, StackT stack) {
+    typedef GraphBase::NodeId NodeId;
+    typedef GraphBase::EdgeId EdgeId;
+    typedef typename GraphT::Matrix Matrix;
+    typedef typename GraphT::RawVector RawVector;
+
+    Solution s;
+
+    while (!stack.empty()) {
+      NodeId NId = stack.back();
+      stack.pop_back();
+
+      RawVector v = G.getNodeCosts(NId);
+
+      for (auto EId : G.adjEdgeIds(NId)) {
+        const Matrix& edgeCosts = G.getEdgeCosts(EId);
+        if (NId == G.getEdgeNode1Id(EId)) {
+          NodeId mId = G.getEdgeNode2Id(EId);
+          v += edgeCosts.getColAsVector(s.getSelection(mId));
+        } else {
+          NodeId mId = G.getEdgeNode1Id(EId);
+          v += edgeCosts.getRowAsVector(s.getSelection(mId));
+        }
+      }
+
+      s.setSelection(NId, v.minIndex());
+    }
+
+    return s;
+  }
+
+}
+
+#endif // LLVM_REDUCTIONRULES_H
diff --git a/include/llvm/CodeGen/PBQP/RegAllocSolver.h b/include/llvm/CodeGen/PBQP/RegAllocSolver.h
new file mode 100644
index 0000000000..80eba31b8c
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/RegAllocSolver.h
@@ -0,0 +1,359 @@
+//===-- RegAllocSolver.h - Heuristic PBQP Solver for reg alloc --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Heuristic PBQP solver for register allocation problems. This solver uses a
+// graph reduction approach. Nodes of degree 0, 1 and 2 are eliminated with
+// optimality-preserving rules (see ReductionRules.h). When no low-degree (<3)
+// nodes are present, a heuristic derived from Brigg's graph coloring approach
+// is used.
+// 
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H
+#define LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H
+
+#include "CostAllocator.h"
+#include "Graph.h"
+#include "ReductionRules.h"
+#include "Solution.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <limits>
+#include <vector>
+
+namespace PBQP {
+
+  namespace RegAlloc {
+
+    /// \brief Metadata to speed allocatability test.
+    ///
+    /// Keeps track of the number of infinities in each row and column.
+    class MatrixMetadata {
+    private:
+      MatrixMetadata(const MatrixMetadata&);
+      void operator=(const MatrixMetadata&);
+    public:
+      MatrixMetadata(const PBQP::Matrix& m)
+        : worstRow(0), worstCol(0),
+          unsafeRows(new bool[m.getRows() - 1]()),
+          unsafeCols(new bool[m.getCols() - 1]()) {
+
+        unsigned* colCounts = new unsigned[m.getCols() - 1]();
+
+        for (unsigned i = 1; i < m.getRows(); ++i) {
+          unsigned rowCount = 0;
+          for (unsigned j = 1; j < m.getCols(); ++j) {
+            if (m[i][j] == std::numeric_limits<PBQP::PBQPNum>::infinity()) {
+              ++rowCount;
+              ++colCounts[j - 1];
+              unsafeRows[i - 1] = true;
+              unsafeCols[j - 1] = true;
+            }
+          }
+          worstRow = std::max(worstRow, rowCount);
+        }
+        unsigned worstColCountForCurRow =
+          *std::max_element(colCounts, colCounts + m.getCols() - 1);
+        worstCol = std::max(worstCol, worstColCountForCurRow);
+        delete[] colCounts;
+      }
+
+      ~MatrixMetadata() {
+        delete[] unsafeRows;
+        delete[] unsafeCols;
+      }
+
+      unsigned getWorstRow() const { return worstRow; }
+      unsigned getWorstCol() const { return worstCol; }
+      const bool* getUnsafeRows() const { return unsafeRows; }
+      const bool* getUnsafeCols() const { return unsafeCols; }
+
+    private:
+      unsigned worstRow, worstCol;
+      bool* unsafeRows;
+      bool* unsafeCols;
+    };
+
+    class NodeMetadata {
+    public:
+      typedef enum { Unprocessed,
+                     OptimallyReducible,
+                     ConservativelyAllocatable,
+                     NotProvablyAllocatable } ReductionState;
+
+      NodeMetadata() : rs(Unprocessed), deniedOpts(0), optUnsafeEdges(0) {}
+      ~NodeMetadata() { delete[] optUnsafeEdges; }
+
+      void setup(const Vector& costs) {
+        numOpts = costs.getLength() - 1;
+        optUnsafeEdges = new unsigned[numOpts]();
+      }
+
+      ReductionState getReductionState() const { return rs; }
+      void setReductionState(ReductionState rs) { this->rs = rs; }
+
+      void handleAddEdge(const MatrixMetadata& md, bool transpose) {
+        deniedOpts += transpose ? md.getWorstCol() : md.getWorstRow();
+        const bool* unsafeOpts =
+          transpose ? md.getUnsafeCols() : md.getUnsafeRows();
+        for (unsigned i = 0; i < numOpts; ++i)
+          optUnsafeEdges[i] += unsafeOpts[i];
+      }
+
+      void handleRemoveEdge(const MatrixMetadata& md, bool transpose) {
+        deniedOpts -= transpose ? md.getWorstCol() : md.getWorstRow();
+        const bool* unsafeOpts =
+          transpose ? md.getUnsafeCols() : md.getUnsafeRows();
+        for (unsigned i = 0; i < numOpts; ++i)
+          optUnsafeEdges[i] -= unsafeOpts[i];
+      }
+
+      bool isConservativelyAllocatable() const {
+        return (deniedOpts < numOpts) ||
+               (std::find(optUnsafeEdges, optUnsafeEdges + numOpts, 0) !=
+                  optUnsafeEdges + numOpts);
+      }
+
+    private:
+      ReductionState rs;
+      unsigned numOpts;
+      unsigned deniedOpts;
+      unsigned* optUnsafeEdges;
+    };
+
+    class RegAllocSolverImpl {
+    private:
+      typedef PBQP::MDMatrix<MatrixMetadata> RAMatrix;
+    public:
+      typedef PBQP::Vector RawVector;
+      typedef PBQP::Matrix RawMatrix;
+      typedef PBQP::Vector Vector;
+      typedef RAMatrix     Matrix;
+      typedef PBQP::PoolCostAllocator<
+                Vector, PBQP::VectorComparator,
+                Matrix, PBQP::MatrixComparator> CostAllocator;
+
+      typedef PBQP::GraphBase::NodeId NodeId;
+      typedef PBQP::GraphBase::EdgeId EdgeId;
+
+      typedef RegAlloc::NodeMetadata NodeMetadata;
+
+      struct EdgeMetadata { };
+
+      typedef PBQP::Graph<RegAllocSolverImpl> Graph;
+
+      RegAllocSolverImpl(Graph &G) : G(G) {}
+
+      Solution solve() {
+        G.setSolver(*this);
+        Solution S;
+        setup();
+        S = backpropagate(G, reduce());
+        G.unsetSolver();
+        return S;
+      }
+
+      void handleAddNode(NodeId NId) {
+        G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
+      }
+      void handleRemoveNode(NodeId NId) {}
+      void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
+
+      void handleAddEdge(EdgeId EId) {
+        handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
+        handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
+      }
+
+      void handleRemoveEdge(EdgeId EId) {
+        handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
+        handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
+      }
+
+      void handleDisconnectEdge(EdgeId EId, NodeId NId) {
+        NodeMetadata& nMd = G.getNodeMetadata(NId);
+        const MatrixMetadata& mMd = G.getEdgeCosts(EId).getMetadata();
+        nMd.handleRemoveEdge(mMd, NId == G.getEdgeNode2Id(EId));
+        if (G.getNodeDegree(NId) == 3) {
+          // This node is becoming optimally reducible.
+          moveToOptimallyReducibleNodes(NId);
+        } else if (nMd.getReductionState() ==
+                     NodeMetadata::NotProvablyAllocatable &&
+                   nMd.isConservativelyAllocatable()) {
+          // This node just became conservatively allocatable.
+          moveToConservativelyAllocatableNodes(NId);
+        }
+      }
+
+      void handleReconnectEdge(EdgeId EId, NodeId NId) {
+        NodeMetadata& nMd = G.getNodeMetadata(NId);
+        const MatrixMetadata& mMd = G.getEdgeCosts(EId).getMetadata();
+        nMd.handleAddEdge(mMd, NId == G.getEdgeNode2Id(EId));
+      }
+
+      void handleSetEdgeCosts(EdgeId EId, const Matrix& NewCosts) {
+        handleRemoveEdge(EId);
+
+        NodeId n1Id = G.getEdgeNode1Id(EId);
+        NodeId n2Id = G.getEdgeNode2Id(EId);
+        NodeMetadata& n1Md = G.getNodeMetadata(n1Id);
+        NodeMetadata& n2Md = G.getNodeMetadata(n2Id);
+        const MatrixMetadata& mMd = NewCosts.getMetadata();
+        n1Md.handleAddEdge(mMd, n1Id != G.getEdgeNode1Id(EId));
+        n2Md.handleAddEdge(mMd, n2Id != G.getEdgeNode1Id(EId));
+      }
+
+    private:
+
+      void removeFromCurrentSet(NodeId NId) {
+        switch (G.getNodeMetadata(NId).getReductionState()) {
+          case NodeMetadata::Unprocessed: break;
+          case NodeMetadata::OptimallyReducible:
+            assert(OptimallyReducibleNodes.find(NId) !=
+                     OptimallyReducibleNodes.end() &&
+                   "Node not in optimally reducible set.");
+            OptimallyReducibleNodes.erase(NId);
+            break;
+          case NodeMetadata::ConservativelyAllocatable:
+            assert(ConservativelyAllocatableNodes.find(NId) !=
+                     ConservativelyAllocatableNodes.end() &&
+                   "Node not in conservatively allocatable set.");
+            ConservativelyAllocatableNodes.erase(NId);
+            break;
+          case NodeMetadata::NotProvablyAllocatable:
+            assert(NotProvablyAllocatableNodes.find(NId) !=
+                     NotProvablyAllocatableNodes.end() &&
+                   "Node not in not-provably-allocatable set.");
+            NotProvablyAllocatableNodes.erase(NId);
+            break;
+        }
+      }
+
+      void moveToOptimallyReducibleNodes(NodeId NId) {
+        removeFromCurrentSet(NId);
+        OptimallyReducibleNodes.insert(NId);
+        G.getNodeMetadata(NId).setReductionState(
+          NodeMetadata::OptimallyReducible);
+      }
+
+      void moveToConservativelyAllocatableNodes(NodeId NId) {
+        removeFromCurrentSet(NId);
+        ConservativelyAllocatableNodes.insert(NId);
+        G.getNodeMetadata(NId).setReductionState(
+          NodeMetadata::ConservativelyAllocatable);
+      }
+
+      void moveToNotProvablyAllocatableNodes(NodeId NId) {
+        removeFromCurrentSet(NId);
+        NotProvablyAllocatableNodes.insert(NId);
+        G.getNodeMetadata(NId).setReductionState(
+          NodeMetadata::NotProvablyAllocatable);
+      }
+
+      void setup() {
+        // Set up worklists.
+        for (auto NId : G.nodeIds()) {
+          if (G.getNodeDegree(NId) < 3)
+            moveToOptimallyReducibleNodes(NId);
+          else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
+            moveToConservativelyAllocatableNodes(NId);
+          else
+            moveToNotProvablyAllocatableNodes(NId);
+        }
+      }
+
+      // Compute a reduction order for the graph by iteratively applying PBQP
+      // reduction rules. Locally optimal rules are applied whenever possible (R0,
+      // R1, R2). If no locally-optimal rules apply then any conservatively
+      // allocatable node is reduced. Finally, if no conservatively allocatable
+      // node exists then the node with the lowest spill-cost:degree ratio is
+      // selected.
+      std::vector<GraphBase::NodeId> reduce() {
+        assert(!G.empty() && "Cannot reduce empty graph.");
+
+        typedef GraphBase::NodeId NodeId;
+        std::vector<NodeId> NodeStack;
+
+        // Consume worklists.
+        while (true) {
+          if (!OptimallyReducibleNodes.empty()) {
+            NodeSet::iterator nItr = OptimallyReducibleNodes.begin();
+            NodeId NId = *nItr;
+            OptimallyReducibleNodes.erase(nItr);
+            NodeStack.push_back(NId);
+            switch (G.getNodeDegree(NId)) {
+              case 0:
+                break;
+              case 1:
+                applyR1(G, NId);
+                break;
+              case 2:
+                applyR2(G, NId);
+                break;
+              default: llvm_unreachable("Not an optimally reducible node.");
+            }
+          } else if (!ConservativelyAllocatableNodes.empty()) {
+            // Conservatively allocatable nodes will never spill. For now just
+            // take the first node in the set and push it on the stack. When we
+            // start optimizing more heavily for register preferencing, it may
+            // would be better to push nodes with lower 'expected' or worst-case
+            // register costs first (since early nodes are the most
+            // constrained).
+            NodeSet::iterator nItr = ConservativelyAllocatableNodes.begin();
+            NodeId NId = *nItr;
+            ConservativelyAllocatableNodes.erase(nItr);
+            NodeStack.push_back(NId);
+            G.disconnectAllNeighborsFromNode(NId);
+
+          } else if (!NotProvablyAllocatableNodes.empty()) {
+            NodeSet::iterator nItr =
+              std::min_element(NotProvablyAllocatableNodes.begin(),
+                               NotProvablyAllocatableNodes.end(),
+                               SpillCostComparator(G));
+            NodeId NId = *nItr;
+            NotProvablyAllocatableNodes.erase(nItr);
+            NodeStack.push_back(NId);
+            G.disconnectAllNeighborsFromNode(NId);
+          } else
+            break;
+        }
+
+        return NodeStack;
+      }
+
+      class SpillCostComparator {
+      public:
+        SpillCostComparator(const Graph& G) : G(G) {}
+        bool operator()(NodeId N1Id, NodeId N2Id) {
+          PBQPNum N1SC = G.getNodeCosts(N1Id)[0] / G.getNodeDegree(N1Id);
+          PBQPNum N2SC = G.getNodeCosts(N2Id)[0] / G.getNodeDegree(N2Id);
+          return N1SC < N2SC;
+        }
+      private:
+        const Graph& G;
+      };
+
+      Graph& G;
+      typedef std::set<NodeId> NodeSet;
+      NodeSet OptimallyReducibleNodes;
+      NodeSet ConservativelyAllocatableNodes;
+      NodeSet NotProvablyAllocatableNodes;
+    };
+
+    typedef Graph<RegAllocSolverImpl> Graph;
+
+    Solution solve(Graph& G) {
+      if (G.empty())
+        return Solution();
+      RegAllocSolverImpl RegAllocSolver(G);
+      return RegAllocSolver.solve();
+    }
+
+  }
+}
+
+#endif // LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H
diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h
index 091805d00f..3556e60f39 100644
--- a/include/llvm/CodeGen/PBQP/Solution.h
+++ b/include/llvm/CodeGen/PBQP/Solution.h
@@ -26,7 +26,7 @@ namespace PBQP {
   class Solution {
   private:
 
-    typedef std::map<Graph::NodeId, unsigned> SelectionsMap;
+    typedef std::map<GraphBase::NodeId, unsigned> SelectionsMap;
     SelectionsMap selections;
 
     unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions;
@@ -72,14 +72,14 @@ namespace PBQP {
     /// \brief Set the selection for a given node.
     /// @param nodeId Node id.
     /// @param selection Selection for nodeId.
-    void setSelection(Graph::NodeId nodeId, unsigned selection) {
+    void setSelection(GraphBase::NodeId nodeId, unsigned selection) {
       selections[nodeId] = selection;
     }
 
     /// \brief Get a node's selection.
     /// @param nodeId Node id.
     /// @return The selection for nodeId;
-    unsigned getSelection(Graph::NodeId nodeId) const {
+    unsigned getSelection(GraphBase::NodeId nodeId) const {
       SelectionsMap::const_iterator sItr = selections.find(nodeId);
       assert(sItr != selections.end() && "No selection for node.");
       return sItr->second;
diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index 7472e5a62d..40539dcab2 100644
--- a/include/llvm/CodeGen/RegAllocPBQP.h
+++ b/include/llvm/CodeGen/RegAllocPBQP.h
@@ -17,9 +17,9 @@
 #define LLVM_CODEGEN_REGALLOCPBQP_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/PBQP/Graph.h"
-#include "llvm/CodeGen/PBQP/Solution.h"
+#include "llvm/CodeGen/PBQP/RegAllocSolver.h"
 #include <map>
 #include <set>
 
@@ -31,28 +31,29 @@ namespace llvm {
   class TargetRegisterInfo;
   template<class T> class OwningPtr;
 
+  typedef PBQP::RegAlloc::Graph PBQPRAGraph;
+
   /// This class wraps up a PBQP instance representing a register allocation
   /// problem, plus the structures necessary to map back from the PBQP solution
   /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map,
   /// and the PBQP option <--> storage location map).
-
   class PBQPRAProblem {
   public:
 
     typedef SmallVector<unsigned, 16> AllowedSet;
 
-    PBQP::Graph& getGraph() { return graph; }
+    PBQPRAGraph& getGraph() { return graph; }
 
-    const PBQP::Graph& getGraph() const { return graph; }
+    const PBQPRAGraph& getGraph() const { return graph; }
 
     /// Record the mapping between the given virtual register and PBQP node,
     /// and the set of allowed pregs for the vreg.
     ///
     /// If you are extending
     /// PBQPBuilder you are unlikely to need this: Nodes and options for all
-    /// vregs will already have been set up for you by the base class. 
+    /// vregs will already have been set up for you by the base class.
     template <typename AllowedRegsItr>
-    void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId,
+    void recordVReg(unsigned vreg, PBQPRAGraph::NodeId nodeId,
                     AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
       assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node.");
       assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
@@ -64,10 +65,10 @@ namespace llvm {
     }
 
     /// Get the virtual register corresponding to the given PBQP node.
-    unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const;
+    unsigned getVRegForNode(PBQPRAGraph::NodeId nodeId) const;
 
     /// Get the PBQP node corresponding to the given virtual register.
-    PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const;
+    PBQPRAGraph::NodeId getNodeForVReg(unsigned vreg) const;
 
     /// Returns true if the given PBQP option represents a physical register,
     /// false otherwise.
@@ -92,16 +93,16 @@ namespace llvm {
 
   private:
 
-    typedef std::map<PBQP::Graph::NodeId, unsigned>  Node2VReg;
-    typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node;
+    typedef std::map<PBQPRAGraph::NodeId, unsigned>  Node2VReg;
+    typedef DenseMap<unsigned, PBQPRAGraph::NodeId> VReg2Node;
     typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
 
-    PBQP::Graph graph;
+    PBQPRAGraph graph;
     Node2VReg node2VReg;
     VReg2Node vreg2Node;
 
     AllowedSetMap allowedSets;
-    
+
   };
 
   /// Builds PBQP instances to represent register allocation problems. Includes
@@ -114,7 +115,7 @@ namespace llvm {
   public:
 
     typedef std::set<unsigned> RegSet;
- 
+
     /// Default constructor.
     PBQPBuilder() {}
 
@@ -139,12 +140,12 @@ namespace llvm {
   /// Extended builder which adds coalescing constraints to a problem.
   class PBQPBuilderWithCoalescing : public PBQPBuilder {
   public:
- 
+
     /// Build a PBQP instance to represent the register allocation problem for
     /// the given MachineFunction.
     virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
                                  const MachineBlockFrequencyInfo *mbfi,
-                                 const RegSet &vregs);   
+                                 const RegSet &vregs);
 
   private:
 
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index 3d2451e796..83dbcecab0 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -45,9 +45,6 @@
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/PBQP/Graph.h"
-#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
-#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/IR/Module.h"
@@ -157,13 +154,13 @@ char RegAllocPBQP::ID = 0;
 
 } // End anonymous namespace.
 
-unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::NodeId node) const {
+unsigned PBQPRAProblem::getVRegForNode(PBQPRAGraph::NodeId node) const {
   Node2VReg::const_iterator vregItr = node2VReg.find(node);
   assert(vregItr != node2VReg.end() && "No vreg for node.");
   return vregItr->second;
 }
 
-PBQP::Graph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
+PBQPRAGraph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
   VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
   assert(nodeItr != vreg2Node.end() && "No node for vreg.");
   return nodeItr->second;
@@ -195,7 +192,7 @@ PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis,
   const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
 
   OwningPtr<PBQPRAProblem> p(new PBQPRAProblem());
-  PBQP::Graph &g = p->getGraph();
+  PBQPRAGraph &g = p->getGraph();
   RegSet pregs;
 
   // Collect the set of preg intervals, record that they're used in the MF.
@@ -245,17 +242,19 @@ PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis,
       vrAllowed.push_back(preg);
     }
 
-    // Construct the node.
-    PBQP::Graph::NodeId node =
-      g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
-
-    // Record the mapping and allowed set in the problem.
-    p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
+    PBQP::Vector nodeCosts(vrAllowed.size() + 1, 0);
 
     PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
         vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
 
-    addSpillCosts(g.getNodeCosts(node), spillCost);
+    addSpillCosts(nodeCosts, spillCost);
+
+    // Construct the node.
+    PBQPRAGraph::NodeId nId = g.addNode(std::move(nodeCosts));
+
+    // Record the mapping and allowed set in the problem.
+    p->recordVReg(vreg, nId, vrAllowed.begin(), vrAllowed.end());
+
   }
 
   for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end();
@@ -272,11 +271,11 @@ PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis,
 
       assert(!l2.empty() && "Empty interval in vreg set?");
       if (l1.overlaps(l2)) {
-        PBQP::Graph::EdgeId edge =
-          g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
-                    PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
+        PBQP::Matrix edgeCosts(vr1Allowed.size()+1, vr2Allowed.size()+1, 0);
+        addInterferenceCosts(edgeCosts, vr1Allowed, vr2Allowed, tri);
 
-        addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
+        g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
+                  std::move(edgeCosts));
       }
     }
   }
@@ -316,7 +315,7 @@ PBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf,
                                                 const RegSet &vregs) {
 
   OwningPtr<PBQPRAProblem> p(PBQPBuilder::build(mf, lis, mbfi, vregs));
-  PBQP::Graph &g = p->getGraph();
+  PBQPRAGraph &g = p->getGraph();
 
   const TargetMachine &tm = mf->getTarget();
   CoalescerPair cp(*tm.getRegisterInfo());
@@ -362,28 +361,32 @@ PBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf,
         }
         if (pregOpt < allowed.size()) {
           ++pregOpt; // +1 to account for spill option.
-          PBQP::Graph::NodeId node = p->getNodeForVReg(src);
-          addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit);
+          PBQPRAGraph::NodeId node = p->getNodeForVReg(src);
+          llvm::dbgs() << "Reading node costs for node " << node << "\n";
+          llvm::dbgs() << "Source node: " << &g.getNodeCosts(node) << "\n";
+          PBQP::Vector newCosts(g.getNodeCosts(node));
+          addPhysRegCoalesce(newCosts, pregOpt, cBenefit);
+          g.setNodeCosts(node, newCosts);
         }
       } else {
         const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst);
         const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src);
-        PBQP::Graph::NodeId node1 = p->getNodeForVReg(dst);
-        PBQP::Graph::NodeId node2 = p->getNodeForVReg(src);
-        PBQP::Graph::EdgeId edge = g.findEdge(node1, node2);
+        PBQPRAGraph::NodeId node1 = p->getNodeForVReg(dst);
+        PBQPRAGraph::NodeId node2 = p->getNodeForVReg(src);
+        PBQPRAGraph::EdgeId edge = g.findEdge(node1, node2);
         if (edge == g.invalidEdgeId()) {
-          edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
-                                                      allowed2->size() + 1,
-                                                      0));
+          PBQP::Matrix costs(allowed1->size() + 1, allowed2->size() + 1, 0);
+          addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit);
+          g.addEdge(node1, node2, costs);
         } else {
-          if (g.getEdgeNode1(edge) == node2) {
+          if (g.getEdgeNode1Id(edge) == node2) {
             std::swap(node1, node2);
             std::swap(allowed1, allowed2);
           }
+          PBQP::Matrix costs(g.getEdgeCosts(edge));
+          addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit);
+          g.setEdgeCosts(edge, costs);
         }
-
-        addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2,
-                           cBenefit);
       }
     }
   }
@@ -471,14 +474,12 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem,
   // Clear the existing allocation.
   vrm->clearAllVirt();
 
-  const PBQP::Graph &g = problem.getGraph();
+  const PBQPRAGraph &g = problem.getGraph();
   // Iterate over the nodes mapping the PBQP solution to a register
   // assignment.
-  for (PBQP::Graph::NodeItr nodeItr = g.nodesBegin(),
-                            nodeEnd = g.nodesEnd();
-       nodeItr != nodeEnd; ++nodeItr) {
-    unsigned vreg = problem.getVRegForNode(*nodeItr);
-    unsigned alloc = solution.getSelection(*nodeItr);
+  for (auto NId : g.nodeIds()) {
+    unsigned vreg = problem.getVRegForNode(NId);
+    unsigned alloc = solution.getSelection(NId);
 
     if (problem.isPRegOption(vreg, alloc)) {
       unsigned preg = problem.getPRegForOption(vreg, alloc);
@@ -603,8 +604,7 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
 #endif
 
       PBQP::Solution solution =
-        PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(
-          problem->getGraph());
+        PBQP::RegAlloc::solve(problem->getGraph());
 
       pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution);