Added a separate class (PBQPBuilder) for PBQP Problem construction. This class can be extended to support custom constraints.

For now the allocator still uses the old (internal) construction mechanism by default. This will be phased out soon assuming 
no issues with the builder system come up.

To invoke the new construction mechanism just pass '-regalloc=pbqp -pbqp-builder' to llc. To provide custom constraints a
Target just needs to extend PBQPBuilder and pass an instance of their derived builder to the RegAllocPBQP constructor.



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

6 files changed, 2129 insertions, 0 deletions

diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h
new file mode 100644
index 0000000000..b2224cb051
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/Graph.h
@@ -0,0 +1,425 @@
+//===-------------------- 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/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h
new file mode 100644
index 0000000000..791c227f0d
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h
@@ -0,0 +1,246 @@
+//===-- 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/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
new file mode 100644
index 0000000000..35514f9674
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
@@ -0,0 +1,616 @@
+//===-- 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/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
new file mode 100644
index 0000000000..18eaf7c0da
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
@@ -0,0 +1,460 @@
+//===-- 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/include/llvm/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h
new file mode 100644
index 0000000000..e7598bf3e3
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/Math.h
@@ -0,0 +1,288 @@
+//===------ 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/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h
new file mode 100644
index 0000000000..57d9b95fc3
--- /dev/null
+++ b/include/llvm/CodeGen/PBQP/Solution.h
@@ -0,0 +1,94 @@
+//===-- 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::ConstNodeItr, 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::ConstNodeItr 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