diff --git a/lib/CodeGen/PBQP/Graph.h b/lib/CodeGen/PBQP/Graph.h
deleted file mode 100644
index b2224cb..0000000
--- a/lib/CodeGen/PBQP/Graph.h
+++ /dev/null
@@ -1,425 +0,0 @@
-//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// PBQP Graph class.
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
-#define LLVM_CODEGEN_PBQP_GRAPH_H
-
-#include "Math.h"
-
-#include <list>
-#include <vector>
-#include <map>
-
-namespace PBQP {
-
-  /// PBQP Graph class.
-  /// Instances of this class describe PBQP problems.
-  class Graph {
-  private:
-
-    // ----- TYPEDEFS -----
-    class NodeEntry;
-    class EdgeEntry;
-
-    typedef std::list<NodeEntry> NodeList;
-    typedef std::list<EdgeEntry> EdgeList;
-
-  public:
-
-    typedef NodeList::iterator NodeItr;
-    typedef NodeList::const_iterator ConstNodeItr;
-
-    typedef EdgeList::iterator EdgeItr;
-    typedef EdgeList::const_iterator ConstEdgeItr;
-
-  private:
-
-    typedef std::list<EdgeItr> AdjEdgeList;
-  
-  public:
-
-    typedef AdjEdgeList::iterator AdjEdgeItr;
-
-  private:
-
-    class NodeEntry {
-    private:
-      Vector costs;      
-      AdjEdgeList adjEdges;
-      unsigned degree;
-      void *data;
-    public:
-      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
-      Vector& getCosts() { return costs; }
-      const Vector& getCosts() const { return costs; }
-      unsigned getDegree() const { return degree; }
-      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
-      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
-      AdjEdgeItr addEdge(EdgeItr e) {
-        ++degree;
-        return adjEdges.insert(adjEdges.end(), e);
-      }
-      void removeEdge(AdjEdgeItr ae) {
-        --degree;
-        adjEdges.erase(ae);
-      }
-      void setData(void *data) { this->data = data; }
-      void* getData() { return data; }
-    };
-
-    class EdgeEntry {
-    private:
-      NodeItr node1, node2;
-      Matrix costs;
-      AdjEdgeItr node1AEItr, node2AEItr;
-      void *data;
-    public:
-      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
-        : node1(node1), node2(node2), costs(costs) {}
-      NodeItr getNode1() const { return node1; }
-      NodeItr getNode2() const { return node2; }
-      Matrix& getCosts() { return costs; }
-      const Matrix& getCosts() const { return costs; }
-      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
-      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
-      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
-      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
-      void setData(void *data) { this->data = data; }
-      void *getData() { return data; }
-    };
-
-    // ----- MEMBERS -----
-
-    NodeList nodes;
-    unsigned numNodes;
-
-    EdgeList edges;
-    unsigned numEdges;
-
-    // ----- INTERNAL METHODS -----
-
-    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
-    const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
-
-    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
-    const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
-
-    NodeItr addConstructedNode(const NodeEntry &n) {
-      ++numNodes;
-      return nodes.insert(nodes.end(), n);
-    }
-
-    EdgeItr addConstructedEdge(const EdgeEntry &e) {
-      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
-             "Attempt to add duplicate edge.");
-      ++numEdges;
-      EdgeItr edgeItr = edges.insert(edges.end(), e);
-      EdgeEntry &ne = getEdge(edgeItr);
-      NodeEntry &n1 = getNode(ne.getNode1());
-      NodeEntry &n2 = getNode(ne.getNode2());
-      // Sanity check on matrix dimensions:
-      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
-             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
-             "Edge cost dimensions do not match node costs dimensions.");
-      ne.setNode1AEItr(n1.addEdge(edgeItr));
-      ne.setNode2AEItr(n2.addEdge(edgeItr));
-      return edgeItr;
-    }
-
-    inline void copyFrom(const Graph &other);
-  public:
-
-    /// \brief Construct an empty PBQP graph.
-    Graph() : numNodes(0), numEdges(0) {}
-
-    /// \brief Copy construct this graph from "other". Note: Does not copy node
-    ///        and edge data, only graph structure and costs.
-    /// @param other Source graph to copy from.
-    Graph(const Graph &other) : numNodes(0), numEdges(0) {
-      copyFrom(other);
-    }
-
-    /// \brief Make this graph a copy of "other". Note: Does not copy node and
-    ///        edge data, only graph structure and costs.
-    /// @param other The graph to copy from.
-    /// @return A reference to this graph.
-    ///
-    /// This will clear the current graph, erasing any nodes and edges added,
-    /// before copying from other.
-    Graph& operator=(const Graph &other) {
-      clear();      
-      copyFrom(other);
-      return *this;
-    }
-
-    /// \brief Add a node with the given costs.
-    /// @param costs Cost vector for the new node.
-    /// @return Node iterator for the added node.
-    NodeItr addNode(const Vector &costs) {
-      return addConstructedNode(NodeEntry(costs));
-    }
-
-    /// \brief Add an edge between the given nodes with the given costs.
-    /// @param n1Itr First node.
-    /// @param n2Itr Second node.
-    /// @return Edge iterator for the added edge.
-    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
-                    const Matrix &costs) {
-      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
-             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
-             "Matrix dimensions mismatch.");
-      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
-    }
-
-    /// \brief Get the number of nodes in the graph.
-    /// @return Number of nodes in the graph.
-    unsigned getNumNodes() const { return numNodes; }
-
-    /// \brief Get the number of edges in the graph.
-    /// @return Number of edges in the graph.
-    unsigned getNumEdges() const { return numEdges; }
-
-    /// \brief Get a node's cost vector.
-    /// @param nItr Node iterator.
-    /// @return Node cost vector.
-    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
-
-    /// \brief Get a node's cost vector (const version).
-    /// @param nItr Node iterator.
-    /// @return Node cost vector.
-    const Vector& getNodeCosts(ConstNodeItr nItr) const {
-      return getNode(nItr).getCosts();
-    }
-
-    /// \brief Set a node's data pointer.
-    /// @param nItr Node iterator.
-    /// @param data Pointer to node data.
-    ///
-    /// Typically used by a PBQP solver to attach data to aid in solution.
-    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
-
-    /// \brief Get the node's data pointer.
-    /// @param nItr Node iterator.
-    /// @return Pointer to node data.
-    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
-    
-    /// \brief Get an edge's cost matrix.
-    /// @param eItr Edge iterator.
-    /// @return Edge cost matrix.
-    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
-
-    /// \brief Get an edge's cost matrix (const version).
-    /// @param eItr Edge iterator.
-    /// @return Edge cost matrix.
-    const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
-      return getEdge(eItr).getCosts();
-    }
-
-    /// \brief Set an edge's data pointer.
-    /// @param eItr Edge iterator.
-    /// @param data Pointer to edge data.
-    ///
-    /// Typically used by a PBQP solver to attach data to aid in solution.
-    void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
-
-    /// \brief Get an edge's data pointer.
-    /// @param eItr Edge iterator.
-    /// @return Pointer to edge data. 
-    void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
-
-    /// \brief Get a node's degree.
-    /// @param nItr Node iterator.
-    /// @return The degree of the node.
-    unsigned getNodeDegree(NodeItr nItr) const {
-      return getNode(nItr).getDegree();
-    }
-
-    /// \brief Begin iterator for node set.
-    NodeItr nodesBegin() { return nodes.begin(); }
-
-    /// \brief Begin const iterator for node set.
-    ConstNodeItr nodesBegin() const { return nodes.begin(); }
-
-    /// \brief End iterator for node set.
-    NodeItr nodesEnd() { return nodes.end(); }
-
-    /// \brief End const iterator for node set.
-    ConstNodeItr nodesEnd() const { return nodes.end(); }
-
-    /// \brief Begin iterator for edge set.
-    EdgeItr edgesBegin() { return edges.begin(); }
-
-    /// \brief End iterator for edge set.
-    EdgeItr edgesEnd() { return edges.end(); }
-
-    /// \brief Get begin iterator for adjacent edge set.
-    /// @param nItr Node iterator.
-    /// @return Begin iterator for the set of edges connected to the given node.
-    AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
-      return getNode(nItr).edgesBegin();
-    }
-
-    /// \brief Get end iterator for adjacent edge set.
-    /// @param nItr Node iterator.
-    /// @return End iterator for the set of edges connected to the given node.
-    AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
-      return getNode(nItr).edgesEnd();
-    }
-
-    /// \brief Get the first node connected to this edge.
-    /// @param eItr Edge iterator.
-    /// @return The first node connected to the given edge. 
-    NodeItr getEdgeNode1(EdgeItr eItr) {
-      return getEdge(eItr).getNode1();
-    }
-
-    /// \brief Get the second node connected to this edge.
-    /// @param eItr Edge iterator.
-    /// @return The second node connected to the given edge. 
-    NodeItr getEdgeNode2(EdgeItr eItr) {
-      return getEdge(eItr).getNode2();
-    } 
-
-    /// \brief Get the "other" node connected to this edge.
-    /// @param eItr Edge iterator.
-    /// @param nItr Node iterator for the "given" node.
-    /// @return The iterator for the "other" node connected to this edge. 
-    NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
-      EdgeEntry &e = getEdge(eItr);
-      if (e.getNode1() == nItr) {
-        return e.getNode2();
-      } // else
-      return e.getNode1();
-    }
-
-    /// \brief Get the edge connecting two nodes.
-    /// @param n1Itr First node iterator.
-    /// @param n2Itr Second node iterator.
-    /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
-    ///         otherwise returns edgesEnd(). 
-    EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
-      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
-         aeItr != aeEnd; ++aeItr) {
-        if ((getEdgeNode1(*aeItr) == n2Itr) ||
-            (getEdgeNode2(*aeItr) == n2Itr)) {
-          return *aeItr;
-        }
-      }
-      return edges.end();
-    }
-
-    /// \brief Remove a node from the graph.
-    /// @param nItr Node iterator.
-    void removeNode(NodeItr nItr) {
-      NodeEntry &n = getNode(nItr);
-      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
-        EdgeItr eItr = *itr;
-        ++itr;
-        removeEdge(eItr); 
-      }
-      nodes.erase(nItr);
-      --numNodes;
-    }
-
-    /// \brief Remove an edge from the graph.
-    /// @param eItr Edge iterator.
-    void removeEdge(EdgeItr eItr) {
-      EdgeEntry &e = getEdge(eItr);
-      NodeEntry &n1 = getNode(e.getNode1());
-      NodeEntry &n2 = getNode(e.getNode2());
-      n1.removeEdge(e.getNode1AEItr());
-      n2.removeEdge(e.getNode2AEItr());
-      edges.erase(eItr);
-      --numEdges;
-    }
-
-    /// \brief Remove all nodes and edges from the graph.
-    void clear() {
-      nodes.clear();
-      edges.clear();
-      numNodes = numEdges = 0;
-    }
-
-    /// \brief Print a representation of this graph in DOT format.
-    /// @param os Output stream to print on.
-    template <typename OStream>
-    void printDot(OStream &os) {
-    
-      os << "graph {\n";
-
-      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
-           nodeItr != nodeEnd; ++nodeItr) {
-
-        os << "  node" << nodeItr << " [ label=\""
-           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
-      }
-
-      os << "  edge [ len=" << getNumNodes() << " ]\n";
-
-      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
-           edgeItr != edgeEnd; ++edgeItr) {
-
-        os << "  node" << getEdgeNode1(edgeItr)
-           << " -- node" << getEdgeNode2(edgeItr)
-           << " [ label=\"";
-
-        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
-
-        for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
-          os << edgeCosts.getRowAsVector(i) << "\\n";
-        }
-        os << "\" ]\n";
-      }
-      os << "}\n";
-    }
-
-  };
-
-  class NodeItrComparator {
-  public:
-    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
-      return &*n1 < &*n2;
-    }
-
-    bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
-      return &*n1 < &*n2;
-    }
-  };
-
-  class EdgeItrCompartor {
-  public:
-    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
-      return &*e1 < &*e2;
-    }
-
-    bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
-      return &*e1 < &*e2;
-    }
-  };
-
-  void Graph::copyFrom(const Graph &other) {
-    std::map<Graph::ConstNodeItr, Graph::NodeItr,
-             NodeItrComparator> nodeMap;
-
-     for (Graph::ConstNodeItr nItr = other.nodesBegin(),
-                             nEnd = other.nodesEnd();
-         nItr != nEnd; ++nItr) {
-      nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
-    }
-      
-  }
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
diff --git a/lib/CodeGen/PBQP/HeuristicBase.h b/lib/CodeGen/PBQP/HeuristicBase.h
deleted file mode 100644
index 791c227..0000000
--- a/lib/CodeGen/PBQP/HeuristicBase.h
+++ /dev/null
@@ -1,246 +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::NodeItr> OptimalList;
-
-    HeuristicSolverImpl<HImpl> &s;
-    Graph &g;
-    OptimalList optimalList;
-
-    // Return a reference to the derived heuristic.
-    HImpl& impl() { return static_cast<HImpl&>(*this); }
-
-    // Add the given node to the optimal reductions list. Keep an iterator to
-    // its location for fast removal. 
-    void addToOptimalReductionList(Graph::NodeItr nItr) {
-      optimalList.insert(optimalList.end(), nItr);
-    }
-
-  public:
-
-    /// \brief Construct an instance with a reference to the given solver.
-    /// @param solver The solver which is using this heuristic instance.
-    HeuristicBase(HeuristicSolverImpl<HImpl> &solver)
-      : s(solver), g(s.getGraph()) { }
-
-    /// \brief Get the solver which is using this heuristic instance.
-    /// @return The solver which is using this heuristic instance.
-    ///
-    /// You can use this method to get access to the solver in your derived
-    /// heuristic implementation.
-    HeuristicSolverImpl<HImpl>& getSolver() { return s; }
-
-    /// \brief Get the graph representing the problem to be solved.
-    /// @return The graph representing the problem to be solved.
-    Graph& getGraph() { return g; }
-
-    /// \brief Tell the solver to simplify the graph before the reduction phase.
-    /// @return Whether or not the solver should run a simplification phase
-    ///         prior to the main setup and reduction.
-    ///
-    /// HeuristicBase returns true from this method as it's a sensible default,
-    /// however you can over-ride it in your derived class if you want different
-    /// behaviour.
-    bool solverRunSimplify() const { return true; }
-
-    /// \brief Decide whether a node should be optimally or heuristically 
-    ///        reduced.
-    /// @return Whether or not the given node should be listed for optimal
-    ///         reduction (via R0, R1 or R2).
-    ///
-    /// HeuristicBase returns true for any node with degree less than 3. This is
-    /// sane and sensible for many situations, but not all. You can over-ride
-    /// this method in your derived class if you want a different selection
-    /// criteria. Note however that your criteria for selecting optimal nodes
-    /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
-    /// higher should not be selected under any circumstances.
-    bool shouldOptimallyReduce(Graph::NodeItr nItr) {
-      if (g.getNodeDegree(nItr) < 3)
-        return true;
-      // else
-      return false;
-    }
-
-    /// \brief Add the given node to the list of nodes to be optimally reduced.
-    /// @return nItr Node iterator to be added.
-    ///
-    /// You probably don't want to over-ride this, except perhaps to record
-    /// statistics before calling this implementation. HeuristicBase relies on
-    /// its behaviour.
-    void addToOptimalReduceList(Graph::NodeItr nItr) {
-      optimalList.push_back(nItr);
-    }
-
-    /// \brief Initialise the heuristic.
-    ///
-    /// HeuristicBase iterates over all nodes in the problem and adds them to
-    /// the appropriate list using addToOptimalReduceList or
-    /// addToHeuristicReduceList based on the result of shouldOptimallyReduce.
-    ///
-    /// This behaviour should be fine for most situations.
-    void setup() {
-      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
-           nItr != nEnd; ++nItr) {
-        if (impl().shouldOptimallyReduce(nItr)) {
-          addToOptimalReduceList(nItr);
-        } else {
-          impl().addToHeuristicReduceList(nItr);
-        }
-      }
-    }
-
-    /// \brief Optimally reduce one of the nodes in the optimal reduce list.
-    /// @return True if a reduction takes place, false if the optimal reduce
-    ///         list is empty.
-    ///
-    /// Selects a node from the optimal reduce list and removes it, applying
-    /// R0, R1 or R2 as appropriate based on the selected node's degree.
-    bool optimalReduce() {
-      if (optimalList.empty())
-        return false;
-
-      Graph::NodeItr nItr = optimalList.front();
-      optimalList.pop_front();
-
-      switch (s.getSolverDegree(nItr)) {
-        case 0: s.applyR0(nItr); break;
-        case 1: s.applyR1(nItr); break;
-        case 2: s.applyR2(nItr); break;
-        default: assert(false &&
-                        "Optimal reductions of degree > 2 nodes is invalid.");
-      }
-
-      return true;
-    }
-
-    /// \brief Perform the PBQP reduction process.
-    ///
-    /// Reduces the problem to the empty graph by repeated application of the
-    /// reduction rules R0, R1, R2 and RN.
-    /// R0, R1 or R2 are always applied if possible before RN is used.
-    void reduce() {
-      bool finished = false;
-
-      while (!finished) {
-        if (!optimalReduce()) {
-          if (impl().heuristicReduce()) {
-            getSolver().recordRN();
-          } else {
-            finished = true;
-          }
-        }
-      }
-    }
-
-    /// \brief Add a node to the heuristic reduce list.
-    /// @param nItr Node iterator to add to the heuristic reduce list.
-    void addToHeuristicList(Graph::NodeItr nItr) {
-      assert(false && "Must be implemented in derived class.");
-    }
-
-    /// \brief Heuristically reduce one of the nodes in the heuristic
-    ///        reduce list.
-    /// @return True if a reduction takes place, false if the heuristic reduce
-    ///         list is empty.
-    void heuristicReduce() {
-      assert(false && "Must be implemented in derived class.");
-    }
-
-    /// \brief Prepare a change in the costs on the given edge.
-    /// @param eItr Edge iterator.    
-    void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
-      assert(false && "Must be implemented in derived class.");
-    }
-
-    /// \brief Handle the change in the costs on the given edge.
-    /// @param eItr Edge iterator.
-    void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
-      assert(false && "Must be implemented in derived class.");
-    }
-
-    /// \brief Handle the addition of a new edge into the PBQP graph.
-    /// @param eItr Edge iterator for the added edge.
-    void handleAddEdge(Graph::EdgeItr eItr) {
-      assert(false && "Must be implemented in derived class.");
-    }
-
-    /// \brief Handle disconnection of an edge from a node.
-    /// @param eItr Edge iterator for edge being disconnected.
-    /// @param nItr Node iterator for the node being disconnected from.
-    ///
-    /// Edges are frequently removed due to the removal of a node. This
-    /// method allows for the effect to be computed only for the remaining
-    /// node in the graph.
-    void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-      assert(false && "Must be implemented in derived class.");
-    }
-
-    /// \brief Clean up any structures used by HeuristicBase.
-    ///
-    /// At present this just performs a sanity check: that the optimal reduce
-    /// list is empty now that reduction has completed.
-    ///
-    /// If your derived class has more complex structures which need tearing
-    /// down you should over-ride this method but include a call back to this
-    /// implementation.
-    void cleanup() {
-      assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
-    }
-
-  };
-
-}
-
-
-#endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H
diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h
deleted file mode 100644
index 35514f9..0000000
--- a/lib/CodeGen/PBQP/HeuristicSolver.h
+++ /dev/null
@@ -1,616 +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 <vector>
-#include <limits>
-
-namespace PBQP {
-
-  /// \brief Heuristic PBQP solver implementation.
-  ///
-  /// This class should usually be created (and destroyed) indirectly via a call
-  /// to HeuristicSolver<HImpl>::solve(Graph&).
-  /// See the comments for HeuristicSolver.
-  ///
-  /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules,
-  /// backpropagation phase, and maintains the internal copy of the graph on
-  /// which the reduction is carried out (the original being kept to facilitate
-  /// backpropagation).
-  template <typename HImpl>
-  class HeuristicSolverImpl {
-  private:
-
-    typedef typename HImpl::NodeData HeuristicNodeData;
-    typedef typename HImpl::EdgeData HeuristicEdgeData;
-
-    typedef std::list<Graph::EdgeItr> SolverEdges;
-
-  public:
-  
-    /// \brief Iterator type for edges in the solver graph.
-    typedef SolverEdges::iterator SolverEdgeItr;
-
-  private:
-
-    class NodeData {
-    public:
-      NodeData() : solverDegree(0) {}
-
-      HeuristicNodeData& getHeuristicData() { return hData; }
-
-      SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
-        ++solverDegree;
-        return solverEdges.insert(solverEdges.end(), eItr);
-      }
-
-      void removeSolverEdge(SolverEdgeItr seItr) {
-        --solverDegree;
-        solverEdges.erase(seItr);
-      }
-
-      SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
-      SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
-      unsigned getSolverDegree() const { return solverDegree; }
-      void clearSolverEdges() {
-        solverDegree = 0;
-        solverEdges.clear(); 
-      }
-      
-    private:
-      HeuristicNodeData hData;
-      unsigned solverDegree;
-      SolverEdges solverEdges;
-    };
- 
-    class EdgeData {
-    public:
-      HeuristicEdgeData& getHeuristicData() { return hData; }
-
-      void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
-        this->n1SolverEdgeItr = n1SolverEdgeItr;
-      }
-
-      SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
-
-      void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
-        this->n2SolverEdgeItr = n2SolverEdgeItr;
-      }
-
-      SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
-
-    private:
-
-      HeuristicEdgeData hData;
-      SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
-    };
-
-    Graph &g;
-    HImpl h;
-    Solution s;
-    std::vector<Graph::NodeItr> stack;
-
-    typedef std::list<NodeData> NodeDataList;
-    NodeDataList nodeDataList;
-
-    typedef std::list<EdgeData> EdgeDataList;
-    EdgeDataList edgeDataList;
-
-  public:
-
-    /// \brief Construct a heuristic solver implementation to solve the given
-    ///        graph.
-    /// @param g The graph representing the problem instance to be solved.
-    HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}  
-
-    /// \brief Get the graph being solved by this solver.
-    /// @return The graph representing the problem instance being solved by this
-    ///         solver.
-    Graph& getGraph() { return g; }
-
-    /// \brief Get the heuristic data attached to the given node.
-    /// @param nItr Node iterator.
-    /// @return The heuristic data attached to the given node.
-    HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
-      return getSolverNodeData(nItr).getHeuristicData();
-    }
-
-    /// \brief Get the heuristic data attached to the given edge.
-    /// @param eItr Edge iterator.
-    /// @return The heuristic data attached to the given node.
-    HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
-      return getSolverEdgeData(eItr).getHeuristicData();
-    }
-
-    /// \brief Begin iterator for the set of edges adjacent to the given node in
-    ///        the solver graph.
-    /// @param nItr Node iterator.
-    /// @return Begin iterator for the set of edges adjacent to the given node
-    ///         in the solver graph. 
-    SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
-      return getSolverNodeData(nItr).solverEdgesBegin();
-    }
-
-    /// \brief End iterator for the set of edges adjacent to the given node in
-    ///        the solver graph.
-    /// @param nItr Node iterator.
-    /// @return End iterator for the set of edges adjacent to the given node in
-    ///         the solver graph. 
-    SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
-      return getSolverNodeData(nItr).solverEdgesEnd();
-    }
-
-    /// \brief Remove a node from the solver graph.
-    /// @param eItr Edge iterator for edge to be removed.
-    ///
-    /// Does <i>not</i> notify the heuristic of the removal. That should be
-    /// done manually if necessary.
-    void removeSolverEdge(Graph::EdgeItr eItr) {
-      EdgeData &eData = getSolverEdgeData(eItr);
-      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
-               &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
-
-      n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
-      n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
-    }
-
-    /// \brief Compute a solution to the PBQP problem instance with which this
-    ///        heuristic solver was constructed.
-    /// @return A solution to the PBQP problem.
-    ///
-    /// Performs the full PBQP heuristic solver algorithm, including setup,
-    /// calls to the heuristic (which will call back to the reduction rules in
-    /// this class), and cleanup.
-    Solution computeSolution() {
-      setup();
-      h.setup();
-      h.reduce();
-      backpropagate();
-      h.cleanup();
-      cleanup();
-      return s;
-    }
-
-    /// \brief Add to the end of the stack.
-    /// @param nItr Node iterator to add to the reduction stack.
-    void pushToStack(Graph::NodeItr nItr) {
-      getSolverNodeData(nItr).clearSolverEdges();
-      stack.push_back(nItr);
-    }
-
-    /// \brief Returns the solver degree of the given node.
-    /// @param nItr Node iterator for which degree is requested.
-    /// @return Node degree in the <i>solver</i> graph (not the original graph).
-    unsigned getSolverDegree(Graph::NodeItr nItr) {
-      return  getSolverNodeData(nItr).getSolverDegree();
-    }
-
-    /// \brief Set the solution of the given node.
-    /// @param nItr Node iterator to set solution for.
-    /// @param selection Selection for node.
-    void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
-      s.setSelection(nItr, selection);
-
-      for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
-                             aeEnd = g.adjEdgesEnd(nItr);
-           aeItr != aeEnd; ++aeItr) {
-        Graph::EdgeItr eItr(*aeItr);
-        Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
-        getSolverNodeData(anItr).addSolverEdge(eItr);
-      }
-    }
-
-    /// \brief Apply rule R0.
-    /// @param nItr Node iterator for node to apply R0 to.
-    ///
-    /// Node will be automatically pushed to the solver stack.
-    void applyR0(Graph::NodeItr nItr) {
-      assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
-             "R0 applied to node with degree != 0.");
-
-      // Nothing to do. Just push the node onto the reduction stack.
-      pushToStack(nItr);
-
-      s.recordR0();
-    }
-
-    /// \brief Apply rule R1.
-    /// @param xnItr Node iterator for node to apply R1 to.
-    ///
-    /// Node will be automatically pushed to the solver stack.
-    void applyR1(Graph::NodeItr xnItr) {
-      NodeData &nd = getSolverNodeData(xnItr);
-      assert(nd.getSolverDegree() == 1 &&
-             "R1 applied to node with degree != 1.");
-
-      Graph::EdgeItr eItr = *nd.solverEdgesBegin();
-
-      const Matrix &eCosts = g.getEdgeCosts(eItr);
-      const Vector &xCosts = g.getNodeCosts(xnItr);
-      
-      // Duplicate a little to avoid transposing matrices.
-      if (xnItr == g.getEdgeNode1(eItr)) {
-        Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
-        Vector &yCosts = g.getNodeCosts(ynItr);
-        for (unsigned j = 0; j < yCosts.getLength(); ++j) {
-          PBQPNum min = eCosts[0][j] + xCosts[0];
-          for (unsigned i = 1; i < xCosts.getLength(); ++i) {
-            PBQPNum c = eCosts[i][j] + xCosts[i];
-            if (c < min)
-              min = c;
-          }
-          yCosts[j] += min;
-        }
-        h.handleRemoveEdge(eItr, ynItr);
-     } else {
-        Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
-        Vector &yCosts = g.getNodeCosts(ynItr);
-        for (unsigned i = 0; i < yCosts.getLength(); ++i) {
-          PBQPNum min = eCosts[i][0] + xCosts[0];
-          for (unsigned j = 1; j < xCosts.getLength(); ++j) {
-            PBQPNum c = eCosts[i][j] + xCosts[j];
-            if (c < min)
-              min = c;
-          }
-          yCosts[i] += min;
-        }
-        h.handleRemoveEdge(eItr, ynItr);
-      }
-      removeSolverEdge(eItr);
-      assert(nd.getSolverDegree() == 0 &&
-             "Degree 1 with edge removed should be 0.");
-      pushToStack(xnItr);
-      s.recordR1();
-    }
-
-    /// \brief Apply rule R2.
-    /// @param xnItr Node iterator for node to apply R2 to.
-    ///
-    /// Node will be automatically pushed to the solver stack.
-    void applyR2(Graph::NodeItr xnItr) {
-      assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
-             "R2 applied to node with degree != 2.");
-
-      NodeData &nd = getSolverNodeData(xnItr);
-      const Vector &xCosts = g.getNodeCosts(xnItr);
-
-      SolverEdgeItr aeItr = nd.solverEdgesBegin();
-      Graph::EdgeItr yxeItr = *aeItr,
-                     zxeItr = *(++aeItr);
-
-      Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
-                     znItr = g.getEdgeOtherNode(zxeItr, xnItr);
-
-      bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
-           flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
-
-      const Matrix *yxeCosts = flipEdge1 ?
-        new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
-        &g.getEdgeCosts(yxeItr);
-
-      const Matrix *zxeCosts = flipEdge2 ?
-        new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
-        &g.getEdgeCosts(zxeItr);
-
-      unsigned xLen = xCosts.getLength(),
-               yLen = yxeCosts->getRows(),
-               zLen = zxeCosts->getRows();
-               
-      Matrix delta(yLen, zLen);
-
-      for (unsigned i = 0; i < yLen; ++i) {
-        for (unsigned j = 0; j < zLen; ++j) {
-          PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0];
-          for (unsigned k = 1; k < xLen; ++k) {
-            PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k];
-            if (c < min) {
-              min = c;
-            }
-          }
-          delta[i][j] = min;
-        }
-      }
-
-      if (flipEdge1)
-        delete yxeCosts;
-
-      if (flipEdge2)
-        delete zxeCosts;
-
-      Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
-      bool addedEdge = false;
-
-      if (yzeItr == g.edgesEnd()) {
-        yzeItr = g.addEdge(ynItr, znItr, delta);
-        addedEdge = true;
-      } else {
-        Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
-        h.preUpdateEdgeCosts(yzeItr);
-        if (ynItr == g.getEdgeNode1(yzeItr)) {
-          yzeCosts += delta;
-        } else {
-          yzeCosts += delta.transpose();
-        }
-      }
-
-      bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
-
-      if (!addedEdge) {
-        // If we modified the edge costs let the heuristic know.
-        h.postUpdateEdgeCosts(yzeItr);
-      }
- 
-      if (nullCostEdge) {
-        // If this edge ended up null remove it.
-        if (!addedEdge) {
-          // We didn't just add it, so we need to notify the heuristic
-          // and remove it from the solver.
-          h.handleRemoveEdge(yzeItr, ynItr);
-          h.handleRemoveEdge(yzeItr, znItr);
-          removeSolverEdge(yzeItr);
-        }
-        g.removeEdge(yzeItr);
-      } else if (addedEdge) {
-        // If the edge was added, and non-null, finish setting it up, add it to
-        // the solver & notify heuristic.
-        edgeDataList.push_back(EdgeData());
-        g.setEdgeData(yzeItr, &edgeDataList.back());
-        addSolverEdge(yzeItr);
-        h.handleAddEdge(yzeItr);
-      }
-
-      h.handleRemoveEdge(yxeItr, ynItr);
-      removeSolverEdge(yxeItr);
-      h.handleRemoveEdge(zxeItr, znItr);
-      removeSolverEdge(zxeItr);
-
-      pushToStack(xnItr);
-      s.recordR2();
-    }
-
-    /// \brief Record an application of the RN rule.
-    ///
-    /// For use by the HeuristicBase.
-    void recordRN() { s.recordRN(); } 
-
-  private:
-
-    NodeData& getSolverNodeData(Graph::NodeItr nItr) {
-      return *static_cast<NodeData*>(g.getNodeData(nItr));
-    }
-
-    EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
-      return *static_cast<EdgeData*>(g.getEdgeData(eItr));
-    }
-
-    void addSolverEdge(Graph::EdgeItr eItr) {
-      EdgeData &eData = getSolverEdgeData(eItr);
-      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
-               &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
-
-      eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
-      eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
-    }
-
-    void setup() {
-      if (h.solverRunSimplify()) {
-        simplify();
-      }
-
-      // Create node data objects.
-      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
-           nItr != nEnd; ++nItr) {
-        nodeDataList.push_back(NodeData());
-        g.setNodeData(nItr, &nodeDataList.back());
-      }
-
-      // Create edge data objects.
-      for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
-           eItr != eEnd; ++eItr) {
-        edgeDataList.push_back(EdgeData());
-        g.setEdgeData(eItr, &edgeDataList.back());
-        addSolverEdge(eItr);
-      }
-    }
-
-    void simplify() {
-      disconnectTrivialNodes();
-      eliminateIndependentEdges();
-    }
-
-    // Eliminate trivial nodes.
-    void disconnectTrivialNodes() {
-      unsigned numDisconnected = 0;
-
-      for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
-           nItr != nEnd; ++nItr) {
-
-        if (g.getNodeCosts(nItr).getLength() == 1) {
-
-          std::vector<Graph::EdgeItr> edgesToRemove;
-
-          for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
-                                 aeEnd = g.adjEdgesEnd(nItr);
-               aeItr != aeEnd; ++aeItr) {
-
-            Graph::EdgeItr eItr = *aeItr;
-
-            if (g.getEdgeNode1(eItr) == nItr) {
-              Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
-              g.getNodeCosts(otherNodeItr) +=
-                g.getEdgeCosts(eItr).getRowAsVector(0);
-            }
-            else {
-              Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
-              g.getNodeCosts(otherNodeItr) +=
-                g.getEdgeCosts(eItr).getColAsVector(0);
-            }
-
-            edgesToRemove.push_back(eItr);
-          }
-
-          if (!edgesToRemove.empty())
-            ++numDisconnected;
-
-          while (!edgesToRemove.empty()) {
-            g.removeEdge(edgesToRemove.back());
-            edgesToRemove.pop_back();
-          }
-        }
-      }
-    }
-
-    void eliminateIndependentEdges() {
-      std::vector<Graph::EdgeItr> edgesToProcess;
-      unsigned numEliminated = 0;
-
-      for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
-           eItr != eEnd; ++eItr) {
-        edgesToProcess.push_back(eItr);
-      }
-
-      while (!edgesToProcess.empty()) {
-        if (tryToEliminateEdge(edgesToProcess.back()))
-          ++numEliminated;
-        edgesToProcess.pop_back();
-      }
-    }
-
-    bool tryToEliminateEdge(Graph::EdgeItr eItr) {
-      if (tryNormaliseEdgeMatrix(eItr)) {
-        g.removeEdge(eItr);
-        return true; 
-      }
-      return false;
-    }
-
-    bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
-
-      const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity();
-
-      Matrix &edgeCosts = g.getEdgeCosts(eItr);
-      Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
-             &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
-
-      for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
-        PBQPNum rowMin = infinity;
-
-        for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
-          if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin)
-            rowMin = edgeCosts[r][c];
-        }
-
-        uCosts[r] += rowMin;
-
-        if (rowMin != infinity) {
-          edgeCosts.subFromRow(r, rowMin);
-        }
-        else {
-          edgeCosts.setRow(r, 0);
-        }
-      }
-
-      for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
-        PBQPNum colMin = infinity;
-
-        for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
-          if (uCosts[r] != infinity && edgeCosts[r][c] < colMin)
-            colMin = edgeCosts[r][c];
-        }
-
-        vCosts[c] += colMin;
-
-        if (colMin != infinity) {
-          edgeCosts.subFromCol(c, colMin);
-        }
-        else {
-          edgeCosts.setCol(c, 0);
-        }
-      }
-
-      return edgeCosts.isZero();
-    }
-
-    void backpropagate() {
-      while (!stack.empty()) {
-        computeSolution(stack.back());
-        stack.pop_back();
-      }
-    }
-
-    void computeSolution(Graph::NodeItr nItr) {
-
-      NodeData &nodeData = getSolverNodeData(nItr);
-
-      Vector v(g.getNodeCosts(nItr));
-
-      // Solve based on existing solved edges.
-      for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
-                         solvedEdgeEnd = nodeData.solverEdgesEnd();
-           solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
-
-        Graph::EdgeItr eItr(*solvedEdgeItr);
-        Matrix &edgeCosts = g.getEdgeCosts(eItr);
-
-        if (nItr == g.getEdgeNode1(eItr)) {
-          Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
-          unsigned adjSolution = s.getSelection(adjNode);
-          v += edgeCosts.getColAsVector(adjSolution);
-        }
-        else {
-          Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
-          unsigned adjSolution = s.getSelection(adjNode);
-          v += edgeCosts.getRowAsVector(adjSolution);
-        }
-
-      }
-
-      setSolution(nItr, v.minIndex());
-    }
-
-    void cleanup() {
-      h.cleanup();
-      nodeDataList.clear();
-      edgeDataList.clear();
-    }
-  };
-
-  /// \brief PBQP heuristic solver class.
-  ///
-  /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
-  /// by calling
-  /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
-  ///
-  /// The choice of heuristic for the H parameter will affect both the solver
-  /// speed and solution quality. The heuristic should be chosen based on the
-  /// nature of the problem being solved.
-  /// Currently the only solver included with LLVM is the Briggs heuristic for
-  /// register allocation.
-  template <typename HImpl>
-  class HeuristicSolver {
-  public:
-    static Solution solve(Graph &g) {
-      HeuristicSolverImpl<HImpl> hs(g);
-      return hs.computeSolution();
-    }
-  };
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h
deleted file mode 100644
index 18eaf7c..0000000
--- a/lib/CodeGen/PBQP/Heuristics/Briggs.h
+++ /dev/null
@@ -1,460 +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 "../HeuristicSolver.h"
-#include "../HeuristicBase.h"
-
-#include <set>
-#include <limits>
-
-namespace PBQP {
-  namespace Heuristics {
-
-    /// \brief PBQP Heuristic which applies an allocability test based on
-    ///        Briggs.
-    /// 
-    /// This heuristic assumes that the elements of cost vectors in the PBQP
-    /// problem represent storage options, with the first being the spill
-    /// option and subsequent elements representing legal registers for the
-    /// corresponding node. Edge cost matrices are likewise assumed to represent
-    /// register constraints.
-    /// If one or more nodes can be proven allocable by this heuristic (by
-    /// inspection of their constraint matrices) then the allocable node of
-    /// highest degree is selected for the next reduction and pushed to the
-    /// solver stack. If no nodes can be proven allocable then the node with
-    /// the lowest estimated spill cost is selected and push to the solver stack
-    /// instead.
-    /// 
-    /// This implementation is built on top of HeuristicBase.       
-    class Briggs : public HeuristicBase<Briggs> {
-    private:
-
-      class LinkDegreeComparator {
-      public:
-        LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
-        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
-            return true;
-          return false;
-        }
-      private:
-        HeuristicSolverImpl<Briggs> *s;
-      };
-
-      class SpillCostComparator {
-      public:
-        SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
-          : s(&s), g(&s.getGraph()) {}
-        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr),
-                  cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr);
-          if (cost1 < cost2)
-            return true;
-          return false;
-        }
-
-      private:
-        HeuristicSolverImpl<Briggs> *s;
-        Graph *g;
-      };
-
-      typedef std::list<Graph::NodeItr> RNAllocableList;
-      typedef RNAllocableList::iterator RNAllocableListItr;
-
-      typedef std::list<Graph::NodeItr> RNUnallocableList;  
-      typedef RNUnallocableList::iterator RNUnallocableListItr;
-
-    public:
-
-      struct NodeData {
-        typedef std::vector<unsigned> UnsafeDegreesArray;
-        bool isHeuristic, isAllocable, isInitialized;
-        unsigned numDenied, numSafe;
-        UnsafeDegreesArray unsafeDegrees;
-        RNAllocableListItr rnaItr;
-        RNUnallocableListItr rnuItr;
-
-        NodeData()
-          : isHeuristic(false), isAllocable(false), isInitialized(false),
-            numDenied(0), numSafe(0) { }
-      };
-
-      struct EdgeData {
-        typedef std::vector<unsigned> UnsafeArray;
-        unsigned worst, reverseWorst;
-        UnsafeArray unsafe, reverseUnsafe;
-        bool isUpToDate;
-
-        EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
-      };
-
-      /// \brief Construct an instance of the Briggs heuristic.
-      /// @param solver A reference to the solver which is using this heuristic.
-      Briggs(HeuristicSolverImpl<Briggs> &solver) :
-        HeuristicBase<Briggs>(solver) {}
-
-      /// \brief Determine whether a node should be reduced using optimal
-      ///        reduction.
-      /// @param nItr Node iterator to be considered.
-      /// @return True if the given node should be optimally reduced, false
-      ///         otherwise.
-      ///
-      /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one
-      /// exception. Nodes whose spill cost (element 0 of their cost vector) is
-      /// infinite are checked for allocability first. Allocable nodes may be
-      /// optimally reduced, but nodes whose allocability cannot be proven are
-      /// selected for heuristic reduction instead.
-      bool shouldOptimallyReduce(Graph::NodeItr nItr) {
-        if (getSolver().getSolverDegree(nItr) < 3) {
-          return true;
-        }
-        // else
-        return false;
-      }
-
-      /// \brief Add a node to the heuristic reduce list.
-      /// @param nItr Node iterator to add to the heuristic reduce list.
-      void addToHeuristicReduceList(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-        initializeNode(nItr);
-        nd.isHeuristic = true;
-        if (nd.isAllocable) {
-          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
-        } else {
-          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
-        }
-      }
-
-      /// \brief Heuristically reduce one of the nodes in the heuristic
-      ///        reduce list.
-      /// @return True if a reduction takes place, false if the heuristic reduce
-      ///         list is empty.
-      ///
-      /// If the list of allocable nodes is non-empty a node is selected
-      /// from it and pushed to the stack. Otherwise if the non-allocable list
-      /// is non-empty a node is selected from it and pushed to the stack.
-      /// If both lists are empty the method simply returns false with no action
-      /// taken.
-      bool heuristicReduce() {
-        if (!rnAllocableList.empty()) {
-          RNAllocableListItr rnaItr =
-            min_element(rnAllocableList.begin(), rnAllocableList.end(),
-                        LinkDegreeComparator(getSolver()));
-          Graph::NodeItr nItr = *rnaItr;
-          rnAllocableList.erase(rnaItr);
-          handleRemoveNode(nItr);
-          getSolver().pushToStack(nItr);
-          return true;
-        } else if (!rnUnallocableList.empty()) {
-          RNUnallocableListItr rnuItr =
-            min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
-                        SpillCostComparator(getSolver()));
-          Graph::NodeItr nItr = *rnuItr;
-          rnUnallocableList.erase(rnuItr);
-          handleRemoveNode(nItr);
-          getSolver().pushToStack(nItr);
-          return true;
-        }
-        // else
-        return false;
-      }
-
-      /// \brief Prepare a change in the costs on the given edge.
-      /// @param eItr Edge iterator.    
-      void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
-        Graph &g = getGraph();
-        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
-                       n2Itr = g.getEdgeNode2(eItr);
-        NodeData &n1 = getHeuristicNodeData(n1Itr),
-                 &n2 = getHeuristicNodeData(n2Itr);
-
-        if (n1.isHeuristic)
-          subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
-        if (n2.isHeuristic)
-          subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
-
-        EdgeData &ed = getHeuristicEdgeData(eItr);
-        ed.isUpToDate = false;
-      }
-
-      /// \brief Handle the change in the costs on the given edge.
-      /// @param eItr Edge iterator.
-      void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
-        // This is effectively the same as adding a new edge now, since
-        // we've factored out the costs of the old one.
-        handleAddEdge(eItr);
-      }
-
-      /// \brief Handle the addition of a new edge into the PBQP graph.
-      /// @param eItr Edge iterator for the added edge.
-      ///
-      /// Updates allocability of any nodes connected by this edge which are
-      /// being managed by the heuristic. If allocability changes they are
-      /// moved to the appropriate list.
-      void handleAddEdge(Graph::EdgeItr eItr) {
-        Graph &g = getGraph();
-        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
-                       n2Itr = g.getEdgeNode2(eItr);
-        NodeData &n1 = getHeuristicNodeData(n1Itr),
-                 &n2 = getHeuristicNodeData(n2Itr);
-
-        // If neither node is managed by the heuristic there's nothing to be
-        // done.
-        if (!n1.isHeuristic && !n2.isHeuristic)
-          return;
-
-        // Ok - we need to update at least one node.
-        computeEdgeContributions(eItr);
-
-        // Update node 1 if it's managed by the heuristic.
-        if (n1.isHeuristic) {
-          bool n1WasAllocable = n1.isAllocable;
-          addEdgeContributions(eItr, n1Itr);
-          updateAllocability(n1Itr);
-          if (n1WasAllocable && !n1.isAllocable) {
-            rnAllocableList.erase(n1.rnaItr);
-            n1.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
-          }
-        }
-
-        // Likewise for node 2.
-        if (n2.isHeuristic) {
-          bool n2WasAllocable = n2.isAllocable;
-          addEdgeContributions(eItr, n2Itr);
-          updateAllocability(n2Itr);
-          if (n2WasAllocable && !n2.isAllocable) {
-            rnAllocableList.erase(n2.rnaItr);
-            n2.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
-          }
-        }
-      }
-
-      /// \brief Handle disconnection of an edge from a node.
-      /// @param eItr Edge iterator for edge being disconnected.
-      /// @param nItr Node iterator for the node being disconnected from.
-      ///
-      /// Updates allocability of the given node and, if appropriate, moves the
-      /// node to a new list.
-      void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-
-        // If the node is not managed by the heuristic there's nothing to be
-        // done.
-        if (!nd.isHeuristic)
-          return;
-
-        EdgeData &ed = getHeuristicEdgeData(eItr);
-        (void)ed;
-        assert(ed.isUpToDate && "Edge data is not up to date.");
-
-        // Update node.
-        bool ndWasAllocable = nd.isAllocable;
-        subtractEdgeContributions(eItr, nItr);
-        updateAllocability(nItr);
-
-        // If the node has gone optimal...
-        if (shouldOptimallyReduce(nItr)) {
-          nd.isHeuristic = false;
-          addToOptimalReduceList(nItr);
-          if (ndWasAllocable) {
-            rnAllocableList.erase(nd.rnaItr);
-          } else {
-            rnUnallocableList.erase(nd.rnuItr);
-          }
-        } else {
-          // Node didn't go optimal, but we might have to move it
-          // from "unallocable" to "allocable".
-          if (!ndWasAllocable && nd.isAllocable) {
-            rnUnallocableList.erase(nd.rnuItr);
-            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
-          }
-        }
-      }
-
-    private:
-
-      NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
-        return getSolver().getHeuristicNodeData(nItr);
-      }
-
-      EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
-        return getSolver().getHeuristicEdgeData(eItr);
-      }
-
-      // Work out what this edge will contribute to the allocability of the
-      // nodes connected to it.
-      void computeEdgeContributions(Graph::EdgeItr eItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
-
-        if (ed.isUpToDate)
-          return; // Edge data is already up to date.
-
-        Matrix &eCosts = getGraph().getEdgeCosts(eItr);
-
-        unsigned numRegs = eCosts.getRows() - 1,
-                 numReverseRegs = eCosts.getCols() - 1;
-
-        std::vector<unsigned> rowInfCounts(numRegs, 0),
-                              colInfCounts(numReverseRegs, 0);        
-
-        ed.worst = 0;
-        ed.reverseWorst = 0;
-        ed.unsafe.clear();
-        ed.unsafe.resize(numRegs, 0);
-        ed.reverseUnsafe.clear();
-        ed.reverseUnsafe.resize(numReverseRegs, 0);
-
-        for (unsigned i = 0; i < numRegs; ++i) {
-          for (unsigned j = 0; j < numReverseRegs; ++j) {
-            if (eCosts[i + 1][j + 1] ==
-                  std::numeric_limits<PBQPNum>::infinity()) {
-              ed.unsafe[i] = 1;
-              ed.reverseUnsafe[j] = 1;
-              ++rowInfCounts[i];
-              ++colInfCounts[j];
-
-              if (colInfCounts[j] > ed.worst) {
-                ed.worst = colInfCounts[j];
-              }
-
-              if (rowInfCounts[i] > ed.reverseWorst) {
-                ed.reverseWorst = rowInfCounts[i];
-              }
-            }
-          }
-        }
-
-        ed.isUpToDate = true;
-      }
-
-      // Add the contributions of the given edge to the given node's 
-      // numDenied and safe members. No action is taken other than to update
-      // these member values. Once updated these numbers can be used by clients
-      // to update the node's allocability.
-      void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
-
-        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
-
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-        
-        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
-        EdgeData::UnsafeArray &unsafe =
-          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
-        nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
-
-        for (unsigned r = 0; r < numRegs; ++r) {
-          if (unsafe[r]) {
-            if (nd.unsafeDegrees[r]==0) {
-              --nd.numSafe;
-            }
-            ++nd.unsafeDegrees[r];
-          }
-        }
-      }
-
-      // Subtract the contributions of the given edge to the given node's 
-      // numDenied and safe members. No action is taken other than to update
-      // these member values. Once updated these numbers can be used by clients
-      // to update the node's allocability.
-      void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
-
-        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
-
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-        
-        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
-        EdgeData::UnsafeArray &unsafe =
-          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
-        nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
-
-        for (unsigned r = 0; r < numRegs; ++r) {
-          if (unsafe[r]) { 
-            if (nd.unsafeDegrees[r] == 1) {
-              ++nd.numSafe;
-            }
-            --nd.unsafeDegrees[r];
-          }
-        }
-      }
-
-      void updateAllocability(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-        nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
-      }
-
-      void initializeNode(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-
-        if (nd.isInitialized)
-          return; // Node data is already up to date.
-
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-
-        nd.numDenied = 0;
-        nd.numSafe = numRegs;
-        nd.unsafeDegrees.resize(numRegs, 0);
-
-        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
-
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
-                           aeEnd = getSolver().solverEdgesEnd(nItr);
-             aeItr != aeEnd; ++aeItr) {
-          
-          Graph::EdgeItr eItr = *aeItr;
-          computeEdgeContributions(eItr);
-          addEdgeContributions(eItr, nItr);
-        }
-
-        updateAllocability(nItr);
-        nd.isInitialized = true;
-      }
-
-      void handleRemoveNode(Graph::NodeItr xnItr) {
-        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
-        std::vector<Graph::EdgeItr> edgesToRemove;
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
-                           aeEnd = getSolver().solverEdgesEnd(xnItr);
-             aeItr != aeEnd; ++aeItr) {
-          Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
-          handleRemoveEdge(*aeItr, ynItr);
-          edgesToRemove.push_back(*aeItr);
-        }
-        while (!edgesToRemove.empty()) {
-          getSolver().removeSolverEdge(edgesToRemove.back());
-          edgesToRemove.pop_back();
-        }
-      }
-
-      RNAllocableList rnAllocableList;
-      RNUnallocableList rnUnallocableList;
-    };
-
-  }
-}
-
-
-#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
diff --git a/lib/CodeGen/PBQP/Math.h b/lib/CodeGen/PBQP/Math.h
deleted file mode 100644
index e7598bf..0000000
--- a/lib/CodeGen/PBQP/Math.h
+++ /dev/null
@@ -1,288 +0,0 @@
-//===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_MATH_H 
-#define LLVM_CODEGEN_PBQP_MATH_H
-
-#include <cassert>
-#include <algorithm>
-#include <functional>
-
-namespace PBQP {
-
-typedef float PBQPNum;
-
-/// \brief PBQP Vector class.
-class Vector {
-  public:
-
-    /// \brief Construct a PBQP vector of the given size.
-    explicit Vector(unsigned length) :
-      length(length), data(new PBQPNum[length]) {
-      }
-
-    /// \brief Construct a PBQP vector with initializer.
-    Vector(unsigned length, PBQPNum initVal) :
-      length(length), data(new PBQPNum[length]) {
-        std::fill(data, data + length, initVal);
-      }
-
-    /// \brief Copy construct a PBQP vector.
-    Vector(const Vector &v) :
-      length(v.length), data(new PBQPNum[length]) {
-        std::copy(v.data, v.data + length, data);
-      }
-
-    /// \brief Destroy this vector, return its memory.
-    ~Vector() { delete[] data; }
-
-    /// \brief Assignment operator.
-    Vector& operator=(const Vector &v) {
-      delete[] data;
-      length = v.length;
-      data = new PBQPNum[length];
-      std::copy(v.data, v.data + length, data);
-      return *this;
-    }
-
-    /// \brief Return the length of the vector
-    unsigned getLength() const {
-      return length;
-    }
-
-    /// \brief Element access.
-    PBQPNum& operator[](unsigned index) {
-      assert(index < length && "Vector element access out of bounds.");
-      return data[index];
-    }
-
-    /// \brief Const element access.
-    const PBQPNum& operator[](unsigned index) const {
-      assert(index < length && "Vector element access out of bounds.");
-      return data[index];
-    }
-
-    /// \brief Add another vector to this one.
-    Vector& operator+=(const Vector &v) {
-      assert(length == v.length && "Vector length mismatch.");
-      std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 
-      return *this;
-    }
-
-    /// \brief Subtract another vector from this one.
-    Vector& operator-=(const Vector &v) {
-      assert(length == v.length && "Vector length mismatch.");
-      std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 
-      return *this;
-    }
-
-    /// \brief Returns the index of the minimum value in this vector
-    unsigned minIndex() const {
-      return std::min_element(data, data + length) - data;
-    }
-
-  private:
-    unsigned length;
-    PBQPNum *data;
-};
-
-/// \brief Output a textual representation of the given vector on the given
-///        output stream.
-template <typename OStream>
-OStream& operator<<(OStream &os, const Vector &v) {
-  assert((v.getLength() != 0) && "Zero-length vector badness.");
-
-  os << "[ " << v[0];
-  for (unsigned i = 1; i < v.getLength(); ++i) {
-    os << ", " << v[i];
-  }
-  os << " ]";
-
-  return os;
-} 
-
-
-/// \brief PBQP Matrix class
-class Matrix {
-  public:
-
-    /// \brief Construct a PBQP Matrix with the given dimensions.
-    Matrix(unsigned rows, unsigned cols) :
-      rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
-    }
-
-    /// \brief Construct a PBQP Matrix with the given dimensions and initial
-    /// value.
-    Matrix(unsigned rows, unsigned cols, PBQPNum initVal) :
-      rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
-        std::fill(data, data + (rows * cols), initVal);
-    }
-
-    /// \brief Copy construct a PBQP matrix.
-    Matrix(const Matrix &m) :
-      rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
-        std::copy(m.data, m.data + (rows * cols), data);  
-    }
-
-    /// \brief Destroy this matrix, return its memory.
-    ~Matrix() { delete[] data; }
-
-    /// \brief Assignment operator.
-    Matrix& operator=(const Matrix &m) {
-      delete[] data;
-      rows = m.rows; cols = m.cols;
-      data = new PBQPNum[rows * cols];
-      std::copy(m.data, m.data + (rows * cols), data);
-      return *this;
-    }
-
-    /// \brief Return the number of rows in this matrix.
-    unsigned getRows() const { return rows; }
-
-    /// \brief Return the number of cols in this matrix.
-    unsigned getCols() const { return cols; }
-
-    /// \brief Matrix element access.
-    PBQPNum* operator[](unsigned r) {
-      assert(r < rows && "Row out of bounds.");
-      return data + (r * cols);
-    }
-
-    /// \brief Matrix element access.
-    const PBQPNum* operator[](unsigned r) const {
-      assert(r < rows && "Row out of bounds.");
-      return data + (r * cols);
-    }
-
-    /// \brief Returns the given row as a vector.
-    Vector getRowAsVector(unsigned r) const {
-      Vector v(cols);
-      for (unsigned c = 0; c < cols; ++c)
-        v[c] = (*this)[r][c];
-      return v; 
-    }
-
-    /// \brief Returns the given column as a vector.
-    Vector getColAsVector(unsigned c) const {
-      Vector v(rows);
-      for (unsigned r = 0; r < rows; ++r)
-        v[r] = (*this)[r][c];
-      return v;
-    }
-
-    /// \brief Reset the matrix to the given value.
-    Matrix& reset(PBQPNum val = 0) {
-      std::fill(data, data + (rows * cols), val);
-      return *this;
-    }
-
-    /// \brief Set a single row of this matrix to the given value.
-    Matrix& setRow(unsigned r, PBQPNum val) {
-      assert(r < rows && "Row out of bounds.");
-      std::fill(data + (r * cols), data + ((r + 1) * cols), val);
-      return *this;
-    }
-
-    /// \brief Set a single column of this matrix to the given value.
-    Matrix& setCol(unsigned c, PBQPNum val) {
-      assert(c < cols && "Column out of bounds.");
-      for (unsigned r = 0; r < rows; ++r)
-        (*this)[r][c] = val;
-      return *this;
-    }
-
-    /// \brief Matrix transpose.
-    Matrix transpose() const {
-      Matrix m(cols, rows);
-      for (unsigned r = 0; r < rows; ++r)
-        for (unsigned c = 0; c < cols; ++c)
-          m[c][r] = (*this)[r][c];
-      return m;
-    }
-
-    /// \brief Returns the diagonal of the matrix as a vector.
-    ///
-    /// Matrix must be square.
-    Vector diagonalize() const {
-      assert(rows == cols && "Attempt to diagonalize non-square matrix.");
-
-      Vector v(rows);
-      for (unsigned r = 0; r < rows; ++r)
-        v[r] = (*this)[r][r];
-      return v;
-    } 
-
-    /// \brief Add the given matrix to this one.
-    Matrix& operator+=(const Matrix &m) {
-      assert(rows == m.rows && cols == m.cols &&
-          "Matrix dimensions mismatch.");
-      std::transform(data, data + (rows * cols), m.data, data,
-          std::plus<PBQPNum>());
-      return *this;
-    }
-
-    /// \brief Returns the minimum of the given row
-    PBQPNum getRowMin(unsigned r) const {
-      assert(r < rows && "Row out of bounds");
-      return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
-    }
-
-    /// \brief Returns the minimum of the given column
-    PBQPNum getColMin(unsigned c) const {
-      PBQPNum minElem = (*this)[0][c];
-      for (unsigned r = 1; r < rows; ++r)
-        if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
-      return minElem;
-    }
-
-    /// \brief Subtracts the given scalar from the elements of the given row.
-    Matrix& subFromRow(unsigned r, PBQPNum val) {
-      assert(r < rows && "Row out of bounds");
-      std::transform(data + (r * cols), data + ((r + 1) * cols),
-          data + (r * cols),
-          std::bind2nd(std::minus<PBQPNum>(), val));
-      return *this;
-    }
-
-    /// \brief Subtracts the given scalar from the elements of the given column.
-    Matrix& subFromCol(unsigned c, PBQPNum val) {
-      for (unsigned r = 0; r < rows; ++r)
-        (*this)[r][c] -= val;
-      return *this;
-    }
-
-    /// \brief Returns true if this is a zero matrix.
-    bool isZero() const {
-      return find_if(data, data + (rows * cols),
-          std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
-        data + (rows * cols);
-    }
-
-  private:
-    unsigned rows, cols;
-    PBQPNum *data;
-};
-
-/// \brief Output a textual representation of the given matrix on the given
-///        output stream.
-template <typename OStream>
-OStream& operator<<(OStream &os, const Matrix &m) {
-
-  assert((m.getRows() != 0) && "Zero-row matrix badness.");
-
-  for (unsigned i = 0; i < m.getRows(); ++i) {
-    os << m.getRowAsVector(i);
-  }
-
-  return os;
-}
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_MATH_H
diff --git a/lib/CodeGen/PBQP/Solution.h b/lib/CodeGen/PBQP/Solution.h
deleted file mode 100644
index 9c40ed7..0000000
--- a/lib/CodeGen/PBQP/Solution.h
+++ /dev/null
@@ -1,93 +0,0 @@
-//===-- Solution.h ------- PBQP Solution ------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// PBQP Solution class.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H
-#define LLVM_CODEGEN_PBQP_SOLUTION_H
-
-#include "Math.h"
-#include "Graph.h"
-
-#include <map>
-
-namespace PBQP {
-
-  /// \brief Represents a solution to a PBQP problem.
-  ///
-  /// To get the selection for each node in the problem use the getSelection method.
-  class Solution {
-  private:
-
-    typedef std::map<Graph::NodeItr, unsigned, NodeItrComparator> SelectionsMap;
-    SelectionsMap selections;
-
-    unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions;
-
-  public:
-
-    /// \brief Initialise an empty solution.
-    Solution()
-      : r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
-
-    /// \brief Number of nodes for which selections have been made.
-    /// @return Number of nodes for which selections have been made.
-    unsigned numNodes() const { return selections.size(); }
-
-    /// \brief Records a reduction via the R0 rule. Should be called from the
-    ///        solver only.
-    void recordR0() { ++r0Reductions; }
-
-    /// \brief Returns the number of R0 reductions applied to solve the problem.
-    unsigned numR0Reductions() const { return r0Reductions; }
-
-    /// \brief Records a reduction via the R1 rule. Should be called from the
-    ///        solver only.
-    void recordR1() { ++r1Reductions; }
-
-    /// \brief Returns the number of R1 reductions applied to solve the problem.
-    unsigned numR1Reductions() const { return r1Reductions; }
-
-    /// \brief Records a reduction via the R2 rule. Should be called from the
-    ///        solver only.
-    void recordR2() { ++r2Reductions; }
-
-    /// \brief Returns the number of R2 reductions applied to solve the problem.
-    unsigned numR2Reductions() const { return r2Reductions; }
-
-    /// \brief Records a reduction via the RN rule. Should be called from the
-    ///        solver only.
-    void recordRN() { ++ rNReductions; }
-
-    /// \brief Returns the number of RN reductions applied to solve the problem.
-    unsigned numRNReductions() const { return rNReductions; }
-
-    /// \brief Set the selection for a given node.
-    /// @param nItr Node iterator.
-    /// @param selection Selection for nItr.
-    void setSelection(Graph::NodeItr nItr, unsigned selection) {
-      selections[nItr] = selection;
-    }
-
-    /// \brief Get a node's selection.
-    /// @param nItr Node iterator.
-    /// @return The selection for nItr;
-    unsigned getSelection(Graph::NodeItr nItr) const {
-      SelectionsMap::const_iterator sItr = selections.find(nItr);
-      assert(sItr != selections.end() && "No selection for node.");
-      return sItr->second;
-    }
-
-  };
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_SOLUTION_H
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index 61f337b..6b2e5c0 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -31,9 +31,6 @@
 
 #define DEBUG_TYPE "regalloc"
 
-#include "PBQP/HeuristicSolver.h"
-#include "PBQP/Graph.h"
-#include "PBQP/Heuristics/Briggs.h"
 #include "RenderMachineFunction.h"
 #include "Splitter.h"
 #include "VirtRegMap.h"
@@ -41,9 +38,13 @@
 #include "llvm/CodeGen/CalcSpillWeights.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/RegAllocPBQP.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
+#include "llvm/CodeGen/PBQP/Graph.h"
+#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/RegisterCoalescer.h"
 #include "llvm/Support/Debug.h"
@@ -51,12 +52,14 @@
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include <limits>
-#include <map>
 #include <memory>
 #include <set>
 #include <vector>
 
-using namespace llvm;
+namespace llvm {
+
+using namespace PBQP;
+  using namespace PBQP::Heuristics;
 
 static RegisterRegAlloc
 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
@@ -68,156 +71,212 @@
                 cl::init(false), cl::Hidden);
 
 static cl::opt<bool>
+pbqpBuilder("pbqp-builder",
+                cl::desc("Use new builder system."),
+                cl::init(false), cl::Hidden);
+
+
+static cl::opt<bool>
 pbqpPreSplitting("pbqp-pre-splitting",
                  cl::desc("Pre-splite before PBQP register allocation."),
                  cl::init(false), cl::Hidden);
 
-namespace {
+char RegAllocPBQP::ID = 0;
 
-  ///
-  /// PBQP based allocators solve the register allocation problem by mapping
-  /// register allocation problems to Partitioned Boolean Quadratic
-  /// Programming problems.
-  class PBQPRegAlloc : public MachineFunctionPass {
-  public:
+unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
+  Node2VReg::const_iterator vregItr = node2VReg.find(node);
+  assert(vregItr != node2VReg.end() && "No vreg for node.");
+  return vregItr->second;
+}
 
-    static char ID;
+PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
+  VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
+  assert(nodeItr != vreg2Node.end() && "No node for vreg.");
+  return nodeItr->second;
+  
+}
 
-    /// Construct a PBQP register allocator.
-    PBQPRegAlloc() : MachineFunctionPass(ID) {}
+const PBQPRAProblem::AllowedSet&
+  PBQPRAProblem::getAllowedSet(unsigned vreg) const {
+  AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg);
+  assert(allowedSetItr != allowedSets.end() && "No pregs for vreg.");
+  const AllowedSet &allowedSet = allowedSetItr->second;
+  return allowedSet;
+}
 
-    /// Return the pass name.
-    virtual const char* getPassName() const {
-      return "PBQP Register Allocator";
+unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const {
+  assert(isPRegOption(vreg, option) && "Not a preg option.");
+
+  const AllowedSet& allowedSet = getAllowedSet(vreg);
+  assert(option <= allowedSet.size() && "Option outside allowed set.");
+  return allowedSet[option - 1];
+}
+
+std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(
+                                             MachineFunction *mf,
+                                             const LiveIntervals *lis,
+                                             const RegSet &vregs) {
+
+  typedef std::vector<const LiveInterval*> LIVector;
+
+  MachineRegisterInfo *mri = &mf->getRegInfo();
+  const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();  
+
+  std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
+  PBQP::Graph &g = p->getGraph();
+  RegSet pregs;
+
+  // Collect the set of preg intervals, record that they're used in the MF.
+  for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end();
+       itr != end; ++itr) {
+    if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
+      pregs.insert(itr->first);
+      mri->setPhysRegUsed(itr->first);
     }
+  }
 
-    /// PBQP analysis usage.
-    virtual void getAnalysisUsage(AnalysisUsage &au) const {
-      au.addRequired<SlotIndexes>();
-      au.addPreserved<SlotIndexes>();
-      au.addRequired<LiveIntervals>();
-      //au.addRequiredID(SplitCriticalEdgesID);
-      au.addRequired<RegisterCoalescer>();
-      au.addRequired<CalculateSpillWeights>();
-      au.addRequired<LiveStacks>();
-      au.addPreserved<LiveStacks>();
-      au.addRequired<MachineLoopInfo>();
-      au.addPreserved<MachineLoopInfo>();
-      if (pbqpPreSplitting)
-        au.addRequired<LoopSplitter>();
-      au.addRequired<VirtRegMap>();
-      au.addRequired<RenderMachineFunction>();
-      MachineFunctionPass::getAnalysisUsage(au);
-    }
+  BitVector reservedRegs = tri->getReservedRegs(*mf);
 
-    /// Perform register allocation
-    virtual bool runOnMachineFunction(MachineFunction &MF);
+  // Iterate over vregs. 
+  for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
+       vregItr != vregEnd; ++vregItr) {
+    unsigned vreg = *vregItr;
+    const TargetRegisterClass *trc = mri->getRegClass(vreg);
+    const LiveInterval *vregLI = &lis->getInterval(vreg);
 
-  private:
-
-    class LIOrdering {
-    public:
-      bool operator()(const LiveInterval *li1, const LiveInterval *li2) const {
-        return li1->reg < li2->reg;
+    // Compute an initial allowed set for the current vreg.
+    typedef std::vector<unsigned> VRAllowed;
+    VRAllowed vrAllowed;
+    for (TargetRegisterClass::iterator aoItr = trc->allocation_order_begin(*mf),
+                                       aoEnd = trc->allocation_order_end(*mf);
+         aoItr != aoEnd; ++aoItr) {
+      unsigned preg = *aoItr;
+      if (!reservedRegs.test(preg)) {
+        vrAllowed.push_back(preg);
       }
-    };
+    }
 
-    typedef std::map<const LiveInterval*, unsigned, LIOrdering> LI2NodeMap;
-    typedef std::vector<const LiveInterval*> Node2LIMap;
-    typedef std::vector<unsigned> AllowedSet;
-    typedef std::vector<AllowedSet> AllowedSetMap;
-    typedef std::set<unsigned> RegSet;
-    typedef std::pair<unsigned, unsigned> RegPair;
-    typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
+    // Remove any physical registers which overlap.
+    for (RegSet::const_iterator pregItr = pregs.begin(),
+                                pregEnd = pregs.end();
+         pregItr != pregEnd; ++pregItr) {
+      unsigned preg = *pregItr;
+      const LiveInterval *pregLI = &lis->getInterval(preg);
 
-    typedef std::set<LiveInterval*, LIOrdering> LiveIntervalSet;
+      if (pregLI->empty())
+        continue;
 
-    typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
+      if (!vregLI->overlaps(*pregLI))
+        continue;
 
-    MachineFunction *mf;
-    const TargetMachine *tm;
-    const TargetRegisterInfo *tri;
-    const TargetInstrInfo *tii;
-    const MachineLoopInfo *loopInfo;
-    MachineRegisterInfo *mri;
-    RenderMachineFunction *rmf;
+      // Remove the register from the allowed set.
+      VRAllowed::iterator eraseItr =
+        std::find(vrAllowed.begin(), vrAllowed.end(), preg);
 
-    LiveIntervals *lis;
-    LiveStacks *lss;
-    VirtRegMap *vrm;
+      if (eraseItr != vrAllowed.end()) {
+        vrAllowed.erase(eraseItr);
+      }
 
-    LI2NodeMap li2Node;
-    Node2LIMap node2LI;
-    AllowedSetMap allowedSets;
-    LiveIntervalSet vregIntervalsToAlloc,
-                    emptyVRegIntervals;
-    NodeVector problemNodes;
+      // Also remove any aliases.
+      const unsigned *aliasItr = tri->getAliasSet(preg);
+      if (aliasItr != 0) {
+        for (; *aliasItr != 0; ++aliasItr) {
+          VRAllowed::iterator eraseItr =
+            std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr);
 
+          if (eraseItr != vrAllowed.end()) {
+            vrAllowed.erase(eraseItr);
+          }
+        }
+      }
+    }
 
-    /// Builds a PBQP cost vector.
-    template <typename RegContainer>
-    PBQP::Vector buildCostVector(unsigned vReg,
-                                 const RegContainer &allowed,
-                                 const CoalesceMap &cealesces,
-                                 PBQP::PBQPNum spillCost) const;
+    // Construct the node.
+    PBQP::Graph::NodeItr node = 
+      g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
 
-    /// \brief Builds a PBQP interference matrix.
-    ///
-    /// @return Either a pointer to a non-zero PBQP matrix representing the
-    ///         allocation option costs, or a null pointer for a zero matrix.
-    ///
-    /// Expects allowed sets for two interfering LiveIntervals. These allowed
-    /// sets should contain only allocable registers from the LiveInterval's
-    /// register class, with any interfering pre-colored registers removed.
-    template <typename RegContainer>
-    PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
-                                          const RegContainer &allowed2) const;
+    // Record the mapping and allowed set in the problem.
+    p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
 
-    ///
-    /// Expects allowed sets for two potentially coalescable LiveIntervals,
-    /// and an estimated benefit due to coalescing. The allowed sets should
-    /// contain only allocable registers from the LiveInterval's register
-    /// classes, with any interfering pre-colored registers removed.
-    template <typename RegContainer>
-    PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
-                                        const RegContainer &allowed2,
-                                        PBQP::PBQPNum cBenefit) const;
+    PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
+        vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
 
-    /// \brief Finds coalescing opportunities and returns them as a map.
-    ///
-    /// Any entries in the map are guaranteed coalescable, even if their
-    /// corresponding live intervals overlap.
-    CoalesceMap findCoalesces();
+    addSpillCosts(g.getNodeCosts(node), spillCost);
+  }
 
-    /// \brief Finds the initial set of vreg intervals to allocate.
-    void findVRegIntervalsToAlloc();
+  for (RegSet::iterator vr1Itr = vregs.begin(), vrEnd = vregs.end();
+         vr1Itr != vrEnd; ++vr1Itr) {
+    unsigned vr1 = *vr1Itr;
+    const LiveInterval &l1 = lis->getInterval(vr1);
+    const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1);
 
-    /// \brief Constructs a PBQP problem representation of the register
-    /// allocation problem for this function.
-    ///
-    /// @return a PBQP solver object for the register allocation problem.
-    PBQP::Graph constructPBQPProblem();
+    for (RegSet::iterator vr2Itr = llvm::next(vr1Itr);
+         vr2Itr != vrEnd; ++vr2Itr) {
+      unsigned vr2 = *vr2Itr;
+      const LiveInterval &l2 = lis->getInterval(vr2);
+      const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2);
 
-    /// \brief Adds a stack interval if the given live interval has been
-    /// spilled. Used to support stack slot coloring.
-    void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
+      assert(!l2.empty() && "Empty interval in vreg set?");
+      if (l1.overlaps(l2)) {
+        PBQP::Graph::EdgeItr edge =
+          g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
+                    PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
 
-    /// \brief Given a solved PBQP problem maps this solution back to a register
-    /// assignment.
-    bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
+        addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
+      }
+    }
+  }
 
-    /// \brief Postprocessing before final spilling. Sets basic block "live in"
-    /// variables.
-    void finalizeAlloc() const;
+  return p;
+}
 
-  };
+void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
+                                PBQP::PBQPNum spillCost) {
+  costVec[0] = spillCost;
+}
 
-  char PBQPRegAlloc::ID = 0;
+void PBQPBuilder::addInterferenceCosts(PBQP::Matrix &costMat,
+                                       const PBQPRAProblem::AllowedSet &vr1Allowed,
+                                       const PBQPRAProblem::AllowedSet &vr2Allowed,
+                                       const TargetRegisterInfo *tri) {
+  assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch.");
+  assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch.");
+
+  for (unsigned i = 0; i < vr1Allowed.size(); ++i) {
+    unsigned preg1 = vr1Allowed[i];
+
+    for (unsigned j = 0; j < vr2Allowed.size(); ++j) {
+      unsigned preg2 = vr2Allowed[j];
+
+      if (tri->regsOverlap(preg1, preg2)) {
+        costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
+      }
+    }
+  }
 }
 
 
+
+void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
+  au.addRequired<SlotIndexes>();
+  au.addPreserved<SlotIndexes>();
+  au.addRequired<LiveIntervals>();
+  //au.addRequiredID(SplitCriticalEdgesID);
+  au.addRequired<RegisterCoalescer>();
+  au.addRequired<CalculateSpillWeights>();
+  au.addRequired<LiveStacks>();
+  au.addPreserved<LiveStacks>();
+  au.addRequired<MachineLoopInfo>();
+  au.addPreserved<MachineLoopInfo>();
+  if (pbqpPreSplitting)
+    au.addRequired<LoopSplitter>();
+  au.addRequired<VirtRegMap>();
+  au.addRequired<RenderMachineFunction>();
+  MachineFunctionPass::getAnalysisUsage(au);
+}
+
 template <typename RegContainer>
-PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg,
+PBQP::Vector RegAllocPBQP::buildCostVector(unsigned vReg,
                                            const RegContainer &allowed,
                                            const CoalesceMap &coalesces,
                                            PBQP::PBQPNum spillCost) const {
@@ -252,7 +311,7 @@
 }
 
 template <typename RegContainer>
-PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix(
+PBQP::Matrix* RegAllocPBQP::buildInterferenceMatrix(
       const RegContainer &allowed1, const RegContainer &allowed2) const {
 
   typedef typename RegContainer::const_iterator RegContainerIterator;
@@ -318,7 +377,7 @@
 }
 
 template <typename RegContainer>
-PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix(
+PBQP::Matrix* RegAllocPBQP::buildCoalescingMatrix(
       const RegContainer &allowed1, const RegContainer &allowed2,
       PBQP::PBQPNum cBenefit) const {
 
@@ -379,7 +438,7 @@
   return m;
 }
 
-PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
+RegAllocPBQP::CoalesceMap RegAllocPBQP::findCoalesces() {
 
   typedef MachineFunction::const_iterator MFIterator;
   typedef MachineBasicBlock::const_iterator MBBIterator;
@@ -516,7 +575,7 @@
   return coalescesFound;
 }
 
-void PBQPRegAlloc::findVRegIntervalsToAlloc() {
+void RegAllocPBQP::findVRegIntervalsToAlloc() {
 
   // Iterate over all live ranges.
   for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
@@ -532,15 +591,15 @@
     // Empty intervals we allocate in a simple post-processing stage in
     // finalizeAlloc.
     if (!li->empty()) {
-      vregIntervalsToAlloc.insert(li);
+      vregsToAlloc.insert(li->reg);
     }
     else {
-      emptyVRegIntervals.insert(li);
+      emptyIntervalVRegs.insert(li->reg);
     }
   }
 }
 
-PBQP::Graph PBQPRegAlloc::constructPBQPProblem() {
+PBQP::Graph RegAllocPBQP::constructPBQPProblem() {
 
   typedef std::vector<const LiveInterval*> LIVector;
   typedef std::vector<unsigned> RegVector;
@@ -565,10 +624,10 @@
 
   // Iterate over vreg intervals, construct live interval <-> node number
   //  mappings.
-  for (LiveIntervalSet::const_iterator
-       itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end();
+  for (RegSet::const_iterator itr = vregsToAlloc.begin(),
+                              end = vregsToAlloc.end();
        itr != end; ++itr) {
-    const LiveInterval *li = *itr;
+    const LiveInterval *li = &lis->getInterval(*itr);
 
     li2Node[li] = node2LI.size();
     node2LI.push_back(li);
@@ -583,10 +642,10 @@
 
   // Construct a PBQP solver for this problem
   PBQP::Graph problem;
-  problemNodes.resize(vregIntervalsToAlloc.size());
+  problemNodes.resize(vregsToAlloc.size());
 
   // Resize allowedSets container appropriately.
-  allowedSets.resize(vregIntervalsToAlloc.size());
+  allowedSets.resize(vregsToAlloc.size());
 
   BitVector ReservedRegs = tri->getReservedRegs(*mf);
 
@@ -617,8 +676,10 @@
 
       // If we get here then the live intervals overlap, but we're still ok
       // if they're coalescable.
-      if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end())
+      if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) {
+        DEBUG(dbgs() << "CoalescingOverride: (" << li->reg << ", " << pReg << ")\n");
         continue;
+      }
 
       // If we get here then we have a genuine exclusion.
 
@@ -703,7 +764,7 @@
   return problem;
 }
 
-void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
+void RegAllocPBQP::addStackInterval(const LiveInterval *spilled,
                                     MachineRegisterInfo* mri) {
   int stackSlot = vrm->getStackSlot(spilled->reg);
 
@@ -724,7 +785,7 @@
   stackInterval.MergeRangesInAsValue(rhsInterval, vni);
 }
 
-bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
+bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
 
   // Set to true if we have any spills
   bool anotherRoundNeeded = false;
@@ -744,7 +805,7 @@
       unsigned physReg = allowedSets[node][allocSelection - 1];
 
       DEBUG(dbgs() << "VREG " << virtReg << " -> "
-                   << tri->getName(physReg) << "\n");
+            << tri->getName(physReg) << " (Option: " << allocSelection << ")\n");
 
       assert(physReg != 0);
 
@@ -756,7 +817,7 @@
 
       // Make sure we ignore this virtual reg on the next round
       // of allocation
-      vregIntervalsToAlloc.erase(&lis->getInterval(virtReg));
+      vregsToAlloc.erase(virtReg);
 
       // Insert spill ranges for this live range
       const LiveInterval *spillInterval = node2LI[node];
@@ -769,7 +830,7 @@
       rmf->rememberSpills(spillInterval, newSpills);
 
       (void) oldSpillWeight;
-      DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: "
+      DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Option: 0, Cost: "
                    << oldSpillWeight << ", New vregs: ");
 
       // Copy any newly inserted live intervals into the list of regs to
@@ -782,7 +843,7 @@
 
         DEBUG(dbgs() << (*itr)->reg << " ");
 
-        vregIntervalsToAlloc.insert(*itr);
+        vregsToAlloc.insert((*itr)->reg);
       }
 
       DEBUG(dbgs() << ")\n");
@@ -795,15 +856,75 @@
   return !anotherRoundNeeded;
 }
 
-void PBQPRegAlloc::finalizeAlloc() const {
+bool RegAllocPBQP::mapPBQPToRegAlloc2(const PBQPRAProblem &problem,
+                                      const PBQP::Solution &solution) {
+  // Set to true if we have any spills
+  bool anotherRoundNeeded = false;
+
+  // Clear the existing allocation.
+  vrm->clearAllVirt();
+
+  const PBQP::Graph &g = problem.getGraph();
+  // Iterate over the nodes mapping the PBQP solution to a register
+  // assignment.
+  for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(),
+                                 nodeEnd = g.nodesEnd();
+       node != nodeEnd; ++node) {
+    unsigned vreg = problem.getVRegForNode(node);
+    unsigned alloc = solution.getSelection(node);
+
+    if (problem.isPRegOption(vreg, alloc)) {
+      unsigned preg = problem.getPRegForOption(vreg, alloc);    
+      DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n");
+      assert(preg != 0 && "Invalid preg selected.");
+      vrm->assignVirt2Phys(vreg, preg);      
+    } else if (problem.isSpillOption(vreg, alloc)) {
+      vregsToAlloc.erase(vreg);
+      const LiveInterval* spillInterval = &lis->getInterval(vreg);
+      double oldWeight = spillInterval->weight;
+      SmallVector<LiveInterval*, 8> spillIs;
+      rmf->rememberUseDefs(spillInterval);
+      std::vector<LiveInterval*> newSpills =
+        lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
+      addStackInterval(spillInterval, mri);
+      rmf->rememberSpills(spillInterval, newSpills);
+
+      (void) oldWeight;
+      DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: "
+                   << oldWeight << ", New vregs: ");
+
+      // Copy any newly inserted live intervals into the list of regs to
+      // allocate.
+      for (std::vector<LiveInterval*>::const_iterator
+           itr = newSpills.begin(), end = newSpills.end();
+           itr != end; ++itr) {
+        assert(!(*itr)->empty() && "Empty spill range.");
+        DEBUG(dbgs() << (*itr)->reg << " ");
+        vregsToAlloc.insert((*itr)->reg);
+      }
+
+      DEBUG(dbgs() << ")\n");
+
+      // We need another round if spill intervals were added.
+      anotherRoundNeeded |= !newSpills.empty();
+    } else {
+      assert(false && "Unknown allocation option.");
+    }
+  }
+
+  return !anotherRoundNeeded;
+}
+
+
+void RegAllocPBQP::finalizeAlloc() const {
   typedef LiveIntervals::iterator LIIterator;
   typedef LiveInterval::Ranges::const_iterator LRIterator;
 
   // First allocate registers for the empty intervals.
-  for (LiveIntervalSet::const_iterator
-         itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
+  for (RegSet::const_iterator
+         itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end();
          itr != end; ++itr) {
-    LiveInterval *li = *itr;
+    LiveInterval *li = &lis->getInterval(*itr);
 
     unsigned physReg = vrm->getRegAllocPref(li->reg);
 
@@ -863,7 +984,7 @@
 
 }
 
-bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
+bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
 
   mf = &MF;
   tm = &mf->getTarget();
@@ -894,21 +1015,36 @@
   findVRegIntervalsToAlloc();
 
   // If there are non-empty intervals allocate them using pbqp.
-  if (!vregIntervalsToAlloc.empty()) {
+  if (!vregsToAlloc.empty()) {
 
     bool pbqpAllocComplete = false;
     unsigned round = 0;
 
-    while (!pbqpAllocComplete) {
-      DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
+    if (!pbqpBuilder) {
+      while (!pbqpAllocComplete) {
+        DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
 
-      PBQP::Graph problem = constructPBQPProblem();
-      PBQP::Solution solution =
-        PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
+        PBQP::Graph problem = constructPBQPProblem();
+        PBQP::Solution solution =
+          PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
 
-      pbqpAllocComplete = mapPBQPToRegAlloc(solution);
+        pbqpAllocComplete = mapPBQPToRegAlloc(solution);
 
-      ++round;
+        ++round;
+      }
+    } else {
+      while (!pbqpAllocComplete) {
+        DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
+
+        std::auto_ptr<PBQPRAProblem> problem =
+          builder->build(mf, lis, vregsToAlloc);
+        PBQP::Solution solution =
+          HeuristicSolver<Briggs>::solve(problem->getGraph());
+
+        pbqpAllocComplete = mapPBQPToRegAlloc2(*problem, solution);
+
+        ++round;
+      }
     }
   }
 
@@ -917,8 +1053,8 @@
 
   rmf->renderMachineFunction("After PBQP register allocation.", vrm);
 
-  vregIntervalsToAlloc.clear();
-  emptyVRegIntervals.clear();
+  vregsToAlloc.clear();
+  emptyIntervalVRegs.clear();
   li2Node.clear();
   node2LI.clear();
   allowedSets.clear();
@@ -934,9 +1070,10 @@
   return true;
 }
 
-FunctionPass* llvm::createPBQPRegisterAllocator() {
-  return new PBQPRegAlloc();
+FunctionPass* createPBQPRegisterAllocator() {
+  return new RegAllocPBQP(std::auto_ptr<PBQPBuilder>(new PBQPBuilder()));
 }
 
+}
 
 #undef DEBUG_TYPE