New C++ PBQP solver. Currently about as fast (read _slow_) as the old C based solver, but I'll be working to improve that. The PBQP allocator has been updated to use the new solver.

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

13 files changed, 2850 insertions, 1785 deletions

diff --git a/lib/CodeGen/PBQP.cpp b/lib/CodeGen/PBQP.cpp
deleted file mode 100644
index 562300f..0000000
--- a/lib/CodeGen/PBQP.cpp
+++ /dev/null
@@ -1,1395 +0,0 @@
-//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Developed by:                   Bernhard Scholz
-//                             The University of Sydney
-//                         http://www.it.usyd.edu.au/~scholz
-//===----------------------------------------------------------------------===//
-
-#include "PBQP.h"
-#include "llvm/Config/alloca.h"
-#include <limits>
-#include <cassert>
-#include <cstring>
-
-namespace llvm {
-
-/**************************************************************************
- * Data Structures 
- **************************************************************************/
-
-/* edge of PBQP graph */
-typedef struct adjnode {
-  struct adjnode *prev,      /* doubly chained list */ 
-                 *succ, 
-                 *reverse;   /* reverse edge */
-  int adj;                   /* adj. node */
-  PBQPMatrix *costs;         /* cost matrix of edge */
-
-  bool tc_valid;              /* flag whether following fields are valid */
-  int *tc_safe_regs;          /* safe registers */
-  int tc_impact;              /* impact */ 
-} adjnode;
-
-/* bucket node */
-typedef struct bucketnode {
-  struct bucketnode *prev;   /* doubly chained list */
-  struct bucketnode *succ;   
-  int u;                     /* node */
-} bucketnode;
-
-/* data structure of partitioned boolean quadratic problem */
-struct pbqp {
-  int num_nodes;             /* number of nodes */
-  int max_deg;               /* maximal degree of a node */
-  bool solved;               /* flag that indicates whether PBQP has been solved yet */
-  bool optimal;              /* flag that indicates whether PBQP is optimal */
-  PBQPNum min;
-  bool changed;              /* flag whether graph has changed in simplification */
-
-                             /* node fields */
-  PBQPVector **node_costs;   /* cost vectors of nodes */
-  int *node_deg;             /* node degree of nodes */
-  int *solution;             /* solution for node */
-  adjnode **adj_list;        /* adj. list */
-  bucketnode **bucket_ptr;   /* bucket pointer of a node */
-
-                             /* node stack */
-  int *stack;                /* stack of nodes */
-  int stack_ptr;             /* stack pointer */
-
-                             /* bucket fields */
-  bucketnode **bucket_list;  /* bucket list */
-
-  int num_r0;                /* counters for number statistics */
-  int num_ri;
-  int num_rii;
-  int num_rn; 
-  int num_rn_special;      
-};
-
-bool isInf(PBQPNum n) { return n == std::numeric_limits<PBQPNum>::infinity(); } 
-
-/*****************************************************************************
- * allocation/de-allocation of pbqp problem 
- ****************************************************************************/
-
-/* allocate new partitioned boolean quadratic program problem */
-pbqp *alloc_pbqp(int num_nodes)
-{
-  pbqp *this_;
-  int u;
-  
-  assert(num_nodes > 0);
-  
-  /* allocate memory for pbqp data structure */   
-  this_ = (pbqp *)malloc(sizeof(pbqp));
-
-  /* Initialize pbqp fields */
-  this_->num_nodes = num_nodes;
-  this_->solved = false;
-  this_->optimal = true;
-  this_->min = 0.0;
-  this_->max_deg = 0;
-  this_->changed = false;
-  this_->num_r0 = 0;
-  this_->num_ri = 0;
-  this_->num_rii = 0;
-  this_->num_rn = 0;
-  this_->num_rn_special = 0;
-  
-  /* initialize/allocate stack fields of pbqp */ 
-  this_->stack = (int *) malloc(sizeof(int)*num_nodes);
-  this_->stack_ptr = 0;
-  
-  /* initialize/allocate node fields of pbqp */
-  this_->adj_list = (adjnode **) malloc(sizeof(adjnode *)*num_nodes);
-  this_->node_deg = (int *) malloc(sizeof(int)*num_nodes);
-  this_->solution = (int *) malloc(sizeof(int)*num_nodes);
-  this_->bucket_ptr = (bucketnode **) malloc(sizeof(bucketnode **)*num_nodes);
-  this_->node_costs = (PBQPVector**) malloc(sizeof(PBQPVector*) * num_nodes);
-  for(u=0;u<num_nodes;u++) {
-    this_->solution[u]=-1;
-    this_->adj_list[u]=NULL;
-    this_->node_deg[u]=0;
-    this_->bucket_ptr[u]=NULL;
-    this_->node_costs[u]=NULL;
-  }
-  
-  /* initialize bucket list */
-  this_->bucket_list = NULL;
-  
-  return this_;
-}
-
-/* free pbqp problem */
-void free_pbqp(pbqp *this_)
-{
-  int u;
-  int deg;
-  adjnode *adj_ptr,*adj_next;
-  bucketnode *bucket,*bucket_next;
-  
-  assert(this_ != NULL);
-  
-  /* free node cost fields */
-  for(u=0;u < this_->num_nodes;u++) {
-    delete this_->node_costs[u];
-  }
-  free(this_->node_costs);
-  
-  /* free bucket list */
-  for(deg=0;deg<=this_->max_deg;deg++) {
-    for(bucket=this_->bucket_list[deg];bucket!=NULL;bucket=bucket_next) {
-      this_->bucket_ptr[bucket->u] = NULL;
-      bucket_next = bucket-> succ;
-      free(bucket);
-    }
-  }
-  free(this_->bucket_list);
-  
-  /* free adj. list */
-  assert(this_->adj_list != NULL);
-  for(u=0;u < this_->num_nodes; u++) {
-    for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = adj_next) {
-      adj_next = adj_ptr -> succ;
-      if (u < adj_ptr->adj) {
-        assert(adj_ptr != NULL);
-        delete adj_ptr->costs;
-      }
-      if (adj_ptr -> tc_safe_regs != NULL) {
-           free(adj_ptr -> tc_safe_regs);
-      }
-      free(adj_ptr);
-    }
-  }
-  free(this_->adj_list);
-  
-  /* free other node fields */
-  free(this_->node_deg);
-  free(this_->solution);
-  free(this_->bucket_ptr);
-
-  /* free stack */
-  free(this_->stack);
-
-  /* free pbqp data structure itself */
-  free(this_);
-}
-
-
-/****************************************************************************
- * adj. node routines 
- ****************************************************************************/
-
-/* find data structure of adj. node of a given node */
-static
-adjnode *find_adjnode(pbqp *this_,int u,int v)
-{
-  adjnode *adj_ptr;
-  
-  assert (this_ != NULL);
-  assert (u >= 0 && u < this_->num_nodes);
-  assert (v >= 0 && v < this_->num_nodes);
-  assert(this_->adj_list != NULL);
-
-  for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-    if (adj_ptr->adj == v) {
-      return adj_ptr;
-    }
-  }
-  return NULL;
-}
-
-/* allocate a new data structure for adj. node */
-static
-adjnode *alloc_adjnode(pbqp *this_,int u, PBQPMatrix *costs)
-{
-  adjnode *p;
-
-  assert(this_ != NULL);
-  assert(costs != NULL);
-  assert(u >= 0 && u < this_->num_nodes);
-
-  p = (adjnode *)malloc(sizeof(adjnode));
-  assert(p != NULL);
-  
-  p->adj = u;
-  p->costs = costs;  
-
-  p->tc_valid= false;
-  p->tc_safe_regs = NULL;
-  p->tc_impact = 0;
-
-  return p;
-}
-
-/* insert adjacence node to adj. list */
-static
-void insert_adjnode(pbqp *this_, int u, adjnode *adj_ptr)
-{
-
-  assert(this_ != NULL);
-  assert(adj_ptr != NULL);
-  assert(u >= 0 && u < this_->num_nodes);
-
-  /* if adjacency list of node is not empty -> update
-     first node of the list */
-  if (this_ -> adj_list[u] != NULL) {
-    assert(this_->adj_list[u]->prev == NULL);
-    this_->adj_list[u] -> prev = adj_ptr;
-  }
-
-  /* update doubly chained list pointers of pointers */
-  adj_ptr -> succ = this_->adj_list[u];
-  adj_ptr -> prev = NULL;
-
-  /* update adjacency list pointer of node u */
-  this_->adj_list[u] = adj_ptr;
-}
-
-/* remove entry in an adj. list */
-static
-void remove_adjnode(pbqp *this_, int u, adjnode *adj_ptr)
-{
-  assert(this_!= NULL);
-  assert(u >= 0 && u <= this_->num_nodes);
-  assert(this_->adj_list != NULL);
-  assert(adj_ptr != NULL);
-  
-  if (adj_ptr -> prev == NULL) {
-    this_->adj_list[u] = adj_ptr -> succ;
-  } else {
-    adj_ptr -> prev -> succ = adj_ptr -> succ;
-  } 
-
-  if (adj_ptr -> succ != NULL) {
-    adj_ptr -> succ -> prev = adj_ptr -> prev;
-  }
-
-  if(adj_ptr->reverse != NULL) {
-    adjnode *rev = adj_ptr->reverse;
-    rev->reverse = NULL;
-  }
-
-  if (adj_ptr -> tc_safe_regs != NULL) {
-     free(adj_ptr -> tc_safe_regs);
-  }
-
-  free(adj_ptr);
-}
-
-/*****************************************************************************
- * node functions 
- ****************************************************************************/
-
-/* get degree of a node */
-static
-int get_deg(pbqp *this_,int u)
-{
-  adjnode *adj_ptr;
-  int deg = 0;
-  
-  assert(this_ != NULL);
-  assert(u >= 0 && u < this_->num_nodes);
-  assert(this_->adj_list != NULL);
-
-  for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-    deg ++;
-  }
-  return deg;
-}
-
-/* reinsert node */
-static
-void reinsert_node(pbqp *this_,int u)
-{
-  adjnode *adj_u,
-          *adj_v;
-
-  assert(this_!= NULL);
-  assert(u >= 0 && u <= this_->num_nodes);
-  assert(this_->adj_list != NULL);
-
-  for(adj_u = this_ -> adj_list[u]; adj_u != NULL; adj_u = adj_u -> succ) {
-    int v = adj_u -> adj;
-    adj_v = alloc_adjnode(this_,u,adj_u->costs);
-    insert_adjnode(this_,v,adj_v);
-  }
-}
-
-/* remove node */
-static
-void remove_node(pbqp *this_,int u)
-{
-  adjnode *adj_ptr;
-
-  assert(this_!= NULL);
-  assert(u >= 0 && u <= this_->num_nodes);
-  assert(this_->adj_list != NULL);
-
-  for(adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-    remove_adjnode(this_,adj_ptr->adj,adj_ptr -> reverse);
-  }
-}
-
-/*****************************************************************************
- * edge functions
- ****************************************************************************/
-
-/* insert edge to graph */
-/* (does not check whether edge exists in graph */
-static
-void insert_edge(pbqp *this_, int u, int v, PBQPMatrix *costs)
-{
-  adjnode *adj_u,
-          *adj_v;
-  
-  /* create adjanceny entry for u */
-  adj_u = alloc_adjnode(this_,v,costs);
-  insert_adjnode(this_,u,adj_u);
-
-
-  /* create adjanceny entry for v */
-  adj_v = alloc_adjnode(this_,u,costs);
-  insert_adjnode(this_,v,adj_v);
-  
-  /* create link for reverse edge */
-  adj_u -> reverse = adj_v;
-  adj_v -> reverse = adj_u;
-}
-
-/* delete edge */
-static
-void delete_edge(pbqp *this_,int u,int v)
-{
-  adjnode *adj_ptr;
-  adjnode *rev;
-  
-  assert(this_ != NULL);
-  assert( u >= 0 && u < this_->num_nodes);
-  assert( v >= 0 && v < this_->num_nodes);
-
-  adj_ptr=find_adjnode(this_,u,v);
-  assert(adj_ptr != NULL);
-  assert(adj_ptr->reverse != NULL);
-
-  delete adj_ptr -> costs;
- 
-  rev = adj_ptr->reverse; 
-  remove_adjnode(this_,u,adj_ptr);
-  remove_adjnode(this_,v,rev);
-} 
-
-/*****************************************************************************
- * cost functions 
- ****************************************************************************/
-
-/* Note: Since cost(u,v) = transpose(cost(v,u)), it would be necessary to store 
-   two matrices for both edges (u,v) and (v,u). However, we only store the 
-   matrix for the case u < v. For the other case we transpose the stored matrix
-   if required. 
-*/
-
-/* add costs to cost vector of a node */
-void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs)
-{
-  assert(this_ != NULL);
-  assert(costs != NULL);
-  assert(u >= 0 && u <= this_->num_nodes);
-  
-  if (!this_->node_costs[u]) {
-    this_->node_costs[u] = new PBQPVector(*costs);
-  } else {
-    *this_->node_costs[u] += *costs;
-  }
-}
-
-/* get cost matrix ptr */
-static
-PBQPMatrix *get_costmatrix_ptr(pbqp *this_, int u, int v)
-{
-  adjnode *adj_ptr;
-  PBQPMatrix *m = NULL;
-
-  assert (this_ != NULL);
-  assert (u >= 0 && u < this_->num_nodes);
-  assert (v >= 0 && v < this_->num_nodes); 
-
-  adj_ptr = find_adjnode(this_,u,v);
-
-  if (adj_ptr != NULL) {
-    m = adj_ptr -> costs;
-  } 
-
-  return m;
-}
-
-/* get cost matrix ptr */
-/* Note: only the pointer is returned for 
-   cost(u,v), if u < v.
-*/ 
-static
-PBQPMatrix *pbqp_get_costmatrix(pbqp *this_, int u, int v)
-{
-  adjnode *adj_ptr = find_adjnode(this_,u,v);
-  
-  if (adj_ptr != NULL) {
-    if ( u < v) {
-      return new PBQPMatrix(*adj_ptr->costs);
-    } else {
-      return new PBQPMatrix(adj_ptr->costs->transpose());
-    }
-  } else {
-    return NULL;
-  }  
-}
-
-/* add costs to cost matrix of an edge */
-void add_pbqp_edgecosts(pbqp *this_,int u,int v, PBQPMatrix *costs)
-{
-  PBQPMatrix *adj_costs;
-
-  assert(this_!= NULL);
-  assert(costs != NULL);
-  assert(u >= 0 && u <= this_->num_nodes);
-  assert(v >= 0 && v <= this_->num_nodes);
-  
-  /* does the edge u-v exists ? */
-  if (u == v) {
-    PBQPVector *diag = new PBQPVector(costs->diagonalize());
-    add_pbqp_nodecosts(this_,v,diag);
-    delete diag;
-  } else if ((adj_costs = get_costmatrix_ptr(this_,u,v))!=NULL) {
-    if ( u < v) {
-      *adj_costs += *costs;
-    } else {
-      *adj_costs += costs->transpose();
-    }
-  } else {
-    adj_costs = new PBQPMatrix((u < v) ? *costs : costs->transpose());
-    insert_edge(this_,u,v,adj_costs);
-  } 
-}
-
-/* remove bucket from bucket list */
-static
-void pbqp_remove_bucket(pbqp *this_, bucketnode *bucket)
-{
-  int u = bucket->u;
-  
-  assert(this_ != NULL);
-  assert(u >= 0 && u < this_->num_nodes);
-  assert(this_->bucket_list != NULL);
-  assert(this_->bucket_ptr[u] != NULL);
-  
-  /* update predecessor node in bucket list 
-     (if no preceeding bucket exists, then
-     the bucket_list pointer needs to be 
-     updated.)
-  */    
-  if (bucket->prev != NULL) {
-    bucket->prev-> succ = bucket->succ; 
-  } else {
-    this_->bucket_list[this_->node_deg[u]] = bucket -> succ;
-  }
-  
-  /* update successor node in bucket list */ 
-  if (bucket->succ != NULL) { 
-    bucket->succ-> prev = bucket->prev;
-  }
-}
-
-/**********************************************************************************
- * pop functions
- **********************************************************************************/
-
-/* pop node of given degree */
-static
-int pop_node(pbqp *this_,int deg)
-{
-  bucketnode *bucket;
-  int u;
-
-  assert(this_ != NULL);
-  assert(deg >= 0 && deg <= this_->max_deg);
-  assert(this_->bucket_list != NULL);
-   
-  /* get first bucket of bucket list */
-  bucket = this_->bucket_list[deg];
-  assert(bucket != NULL);
-
-  /* remove bucket */
-  pbqp_remove_bucket(this_,bucket);
-  u = bucket->u;
-  free(bucket);
-  return u;
-}
-
-/**********************************************************************************
- * reorder functions
- **********************************************************************************/
-
-/* add bucket to bucketlist */
-static
-void add_to_bucketlist(pbqp *this_,bucketnode *bucket, int deg)
-{
-  bucketnode *old_head;
-  
-  assert(bucket != NULL);
-  assert(this_ != NULL);
-  assert(deg >= 0 && deg <= this_->max_deg);
-  assert(this_->bucket_list != NULL);
-
-  /* store node degree (for re-ordering purposes)*/
-  this_->node_deg[bucket->u] = deg;
-  
-  /* put bucket to front of doubly chained list */
-  old_head = this_->bucket_list[deg];
-  bucket -> prev = NULL;
-  bucket -> succ = old_head;
-  this_ -> bucket_list[deg] = bucket;
-  if (bucket -> succ != NULL ) {
-    assert ( old_head -> prev == NULL);
-    old_head -> prev = bucket;
-  }
-}
-
-
-/* reorder node in bucket list according to 
-   current node degree */
-static
-void reorder_node(pbqp *this_, int u)
-{
-  int deg; 
-  
-  assert(this_ != NULL);
-  assert(u>= 0 && u < this_->num_nodes);
-  assert(this_->bucket_list != NULL);
-  assert(this_->bucket_ptr[u] != NULL);
-
-  /* get current node degree */
-  deg = get_deg(this_,u);
-  
-  /* remove bucket from old bucket list only
-     if degree of node has changed. */
-  if (deg != this_->node_deg[u]) {
-    pbqp_remove_bucket(this_,this_->bucket_ptr[u]);
-    add_to_bucketlist(this_,this_->bucket_ptr[u],deg);
-  } 
-}
-
-/* reorder adj. nodes of a node */
-static
-void reorder_adjnodes(pbqp *this_,int u)
-{
-  adjnode *adj_ptr;
-  
-  assert(this_!= NULL);
-  assert(u >= 0 && u <= this_->num_nodes);
-  assert(this_->adj_list != NULL);
-
-  for(adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-    reorder_node(this_,adj_ptr->adj);
-  }
-}
-
-/**********************************************************************************
- * creation functions
- **********************************************************************************/
-
-/* create new bucket entry */
-/* consistency of the bucket list is not checked! */
-static
-void create_bucket(pbqp *this_,int u,int deg)
-{
-  bucketnode *bucket;
-  
-  assert(this_ != NULL);
-  assert(u >= 0 && u < this_->num_nodes);
-  assert(this_->bucket_list != NULL);
-  
-  bucket = (bucketnode *)malloc(sizeof(bucketnode));
-  assert(bucket != NULL);
-
-  bucket -> u = u;
-  this_->bucket_ptr[u] = bucket;
-
-  add_to_bucketlist(this_,bucket,deg);
-}
-
-/* create bucket list */
-static
-void create_bucketlist(pbqp *this_)
-{
-  int u;
-  int max_deg;
-  int deg;
-
-  assert(this_ != NULL);
-  assert(this_->bucket_list == NULL);
-
-  /* determine max. degree of the nodes */
-  max_deg = 2;  /* at least of degree two! */
-  for(u=0;u<this_->num_nodes;u++) {
-    deg = this_->node_deg[u] = get_deg(this_,u);
-    if (deg > max_deg) {
-      max_deg = deg;
-    }
-  }
-  this_->max_deg = max_deg;
-  
-  /* allocate bucket list */
-  this_ -> bucket_list = (bucketnode **)malloc(sizeof(bucketnode *)*(max_deg + 1));
-  memset(this_->bucket_list,0,sizeof(bucketnode *)*(max_deg + 1));
-  assert(this_->bucket_list != NULL);
-  
-  /* insert nodes to the list */
-  for(u=0;u<this_->num_nodes;u++) {
-    create_bucket(this_,u,this_->node_deg[u]);  
-  }
-}
-
-/*****************************************************************************
- * PBQP simplification for trivial nodes
- ****************************************************************************/
-
-/* remove trivial node with cost vector length of one */
-static
-void disconnect_trivialnode(pbqp *this_,int u)
-{
-  int v;
-  adjnode *adj_ptr, 
-          *next;
-  PBQPMatrix *c_uv;
-  PBQPVector *c_v;
-  
-  assert(this_ != NULL);
-  assert(this_->node_costs != NULL);
-  assert(u >= 0 && u < this_ -> num_nodes);
-  assert(this_->node_costs[u]->getLength() == 1);
-  
-  /* add edge costs to node costs of adj. nodes */
-  for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = next){
-    next = adj_ptr -> succ;
-    v = adj_ptr -> adj;
-    assert(v >= 0 && v < this_ -> num_nodes);
-    
-    /* convert matrix to cost vector offset for adj. node */
-    c_uv = pbqp_get_costmatrix(this_,u,v);
-    c_v = new PBQPVector(c_uv->getRowAsVector(0));
-    *this_->node_costs[v] += *c_v;
-    
-    /* delete edge & free vec/mat */
-    delete c_v;
-    delete c_uv;
-    delete_edge(this_,u,v);
-  }   
-}
-
-/* find all trivial nodes and disconnect them */
-static   
-void eliminate_trivial_nodes(pbqp *this_)
-{
-   int u;
-   
-   assert(this_ != NULL);
-   assert(this_ -> node_costs != NULL);
-   
-   for(u=0;u < this_ -> num_nodes; u++) {
-     if (this_->node_costs[u]->getLength() == 1) {
-       disconnect_trivialnode(this_,u); 
-     }
-   }
-}
-
-/*****************************************************************************
- * Normal form for PBQP 
- ****************************************************************************/
-
-/* simplify a cost matrix. If the matrix
-   is independent, then simplify_matrix
-   returns true - otherwise false. In
-   vectors u and v the offset values of
-   the decomposition are stored. 
-*/
-
-static
-bool normalize_matrix(PBQPMatrix *m, PBQPVector *u, PBQPVector *v)
-{
-  assert( m != NULL);
-  assert( u != NULL);
-  assert( v != NULL);
-  assert( u->getLength() > 0);
-  assert( v->getLength() > 0);
-  
-  assert(m->getRows() == u->getLength());
-  assert(m->getCols() == v->getLength());
-
-  /* determine u vector */
-  for(unsigned r = 0; r < m->getRows(); ++r) {
-    PBQPNum min = m->getRowMin(r);
-    (*u)[r] += min;
-    if (!isInf(min)) {
-      m->subFromRow(r, min);
-    } else {
-      m->setRow(r, 0);
-    }
-  }
-  
-  /* determine v vector */
-  for(unsigned c = 0; c < m->getCols(); ++c) {
-    PBQPNum min = m->getColMin(c);
-    (*v)[c] += min;
-    if (!isInf(min)) {
-      m->subFromCol(c, min);
-    } else {
-      m->setCol(c, 0);
-    }
-  }
-  
-  /* determine whether matrix is 
-     independent or not. 
-    */
-  return m->isZero();
-}
-
-/* simplify single edge */
-static
-void simplify_edge(pbqp *this_,int u,int v)
-{
-  PBQPMatrix *costs;
-  bool is_zero; 
-  
-  assert (this_ != NULL);
-  assert (u >= 0 && u <this_->num_nodes);
-  assert (v >= 0 && v <this_->num_nodes);
-  assert (u != v);
-
-  /* swap u and v  if u > v in order to avoid un-necessary
-     tranpositions of the cost matrix */
-  
-  if (u > v) {
-    int swap = u;
-    u = v;
-    v = swap;
-  }
-  
-  /* get cost matrix and simplify it */  
-  costs = get_costmatrix_ptr(this_,u,v);
-  is_zero=normalize_matrix(costs,this_->node_costs[u],this_->node_costs[v]);
-
-  /* delete edge */
-  if(is_zero){
-    delete_edge(this_,u,v);
-    this_->changed = true;
-  }
-}
-
-/* normalize cost matrices and remove 
-   edges in PBQP if they ary independent, 
-   i.e. can be decomposed into two 
-   cost vectors.
-*/
-static
-void eliminate_independent_edges(pbqp *this_)
-{
-  int u,v;
-  adjnode *adj_ptr,*next;
-  
-  assert(this_ != NULL);
-  assert(this_ -> adj_list != NULL);
-
-  this_->changed = false;
-  for(u=0;u < this_->num_nodes;u++) {
-    for (adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = next) {
-      next = adj_ptr -> succ;
-      v = adj_ptr -> adj;
-      assert(v >= 0 && v < this_->num_nodes);
-      if (u < v) {
-        simplify_edge(this_,u,v);
-      } 
-    }
-  }
-}
-
-
-/*****************************************************************************
- * PBQP reduction rules 
- ****************************************************************************/
-
-/* RI reduction
-   This reduction rule is applied for nodes 
-   of degree one. */
-
-static
-void apply_RI(pbqp *this_,int x)
-{
-  int y;
-  unsigned xlen,
-           ylen;
-  PBQPMatrix *c_yx;
-  PBQPVector *c_x, *delta;
-  
-  assert(this_ != NULL);
-  assert(x >= 0 && x < this_->num_nodes);
-  assert(this_ -> adj_list[x] != NULL);
-  assert(this_ -> adj_list[x] -> succ == NULL);
-
-  /* get adjacence matrix */
-  y = this_ -> adj_list[x] -> adj;
-  assert(y >= 0 && y < this_->num_nodes);
-  
-  /* determine length of cost vectors for node x and y */
-  xlen = this_ -> node_costs[x]->getLength();
-  ylen = this_ -> node_costs[y]->getLength();
-
-  /* get cost vector c_x and matrix c_yx */
-  c_x = this_ -> node_costs[x];
-  c_yx = pbqp_get_costmatrix(this_,y,x); 
-  assert (c_yx != NULL);
-
-  
-  /* allocate delta vector */
-  delta = new PBQPVector(ylen);
-
-  /* compute delta vector */
-  for(unsigned i = 0; i < ylen; ++i) {
-    PBQPNum min =  (*c_yx)[i][0] + (*c_x)[0];
-    for(unsigned j = 1; j < xlen; ++j) {
-      PBQPNum c =  (*c_yx)[i][j] + (*c_x)[j];
-      if ( c < min )  
-         min = c;
-    }
-    (*delta)[i] = min; 
-  } 
-
-  /* add delta vector */
-  *this_ -> node_costs[y] += *delta;
-
-  /* delete node x */
-  remove_node(this_,x);
-
-  /* reorder adj. nodes of node x */
-  reorder_adjnodes(this_,x);
-
-  /* push node x on stack */
-  assert(this_ -> stack_ptr < this_ -> num_nodes);
-  this_->stack[this_ -> stack_ptr++] = x;
-
-  /* free vec/mat */
-  delete c_yx;
-  delete delta;
-
-  /* increment counter for number statistic */
-  this_->num_ri++;
-}
-
-/* RII reduction
-   This reduction rule is applied for nodes 
-   of degree two. */
-
-static
-void apply_RII(pbqp *this_,int x)
-{
-  int y,z; 
-  unsigned xlen,ylen,zlen;
-  adjnode *adj_yz;
-
-  PBQPMatrix *c_yx, *c_zx;
-  PBQPVector *cx;
-  PBQPMatrix *delta;
- 
-  assert(this_ != NULL);
-  assert(x >= 0 && x < this_->num_nodes);
-  assert(this_ -> adj_list[x] != NULL);
-  assert(this_ -> adj_list[x] -> succ != NULL);
-  assert(this_ -> adj_list[x] -> succ -> succ == NULL);
-
-  /* get adjacence matrix */
-  y = this_ -> adj_list[x] -> adj;
-  z = this_ -> adj_list[x] -> succ -> adj;
-  assert(y >= 0 && y < this_->num_nodes);
-  assert(z >= 0 && z < this_->num_nodes);
-  
-  /* determine length of cost vectors for node x and y */
-  xlen = this_ -> node_costs[x]->getLength();
-  ylen = this_ -> node_costs[y]->getLength();
-  zlen = this_ -> node_costs[z]->getLength();
-
-  /* get cost vector c_x and matrix c_yx */
-  cx = this_ -> node_costs[x];
-  c_yx = pbqp_get_costmatrix(this_,y,x); 
-  c_zx = pbqp_get_costmatrix(this_,z,x); 
-  assert(c_yx != NULL);
-  assert(c_zx != NULL);
-
-  /* Colour Heuristic */
-  if ( (adj_yz = find_adjnode(this_,y,z)) != NULL) {
-    adj_yz->tc_valid = false;
-    adj_yz->reverse->tc_valid = false; 
-  }
-
-  /* allocate delta matrix */
-  delta = new PBQPMatrix(ylen, zlen);
-
-  /* compute delta matrix */
-  for(unsigned i=0;i<ylen;i++) {
-    for(unsigned j=0;j<zlen;j++) {
-      PBQPNum min = (*c_yx)[i][0] + (*c_zx)[j][0] + (*cx)[0];
-      for(unsigned k=1;k<xlen;k++) {
-        PBQPNum c = (*c_yx)[i][k] + (*c_zx)[j][k] + (*cx)[k];
-        if ( c < min ) {
-          min = c;
-        }
-      }
-      (*delta)[i][j] = min;
-    }
-  }
-
-  /* add delta matrix */
-  add_pbqp_edgecosts(this_,y,z,delta);
-
-  /* delete node x */
-  remove_node(this_,x);
-
-  /* simplify cost matrix c_yz */
-  simplify_edge(this_,y,z);
-
-  /* reorder adj. nodes */
-  reorder_adjnodes(this_,x);
-
-  /* push node x on stack */
-  assert(this_ -> stack_ptr < this_ -> num_nodes);
-  this_->stack[this_ -> stack_ptr++] = x;
-
-  /* free vec/mat */
-  delete c_yx;
-  delete c_zx;
-  delete delta;
-
-  /* increment counter for number statistic */
-  this_->num_rii++;
-
-}
-
-/* RN reduction */
-static
-void apply_RN(pbqp *this_,int x)
-{
-  unsigned xlen;
-
-  assert(this_ != NULL);
-  assert(x >= 0 && x < this_->num_nodes);
-  assert(this_ -> node_costs[x] != NULL);
-
-  xlen = this_ -> node_costs[x] -> getLength();
-
-  /* after application of RN rule no optimality
-     can be guaranteed! */
-  this_ -> optimal = false;
-  
-  /* push node x on stack */
-  assert(this_ -> stack_ptr < this_ -> num_nodes);
-  this_->stack[this_ -> stack_ptr++] = x;
-
-  /* delete node x */ 
-  remove_node(this_,x);
-
-  /* reorder adj. nodes of node x */
-  reorder_adjnodes(this_,x);
-
-  /* increment counter for number statistic */
-  this_->num_rn++;
-}
-
-
-static
-void compute_tc_info(pbqp *this_, adjnode *p)
-{
-   adjnode *r;
-   PBQPMatrix *m;
-   int x,y;
-   PBQPVector *c_x, *c_y;
-   int *row_inf_counts;
-
-   assert(p->reverse != NULL);
-
-   /* set flags */ 
-   r = p->reverse;
-   p->tc_valid = true;
-   r->tc_valid = true;
-
-   /* get edge */
-   x = r->adj;
-   y = p->adj;
-
-   /* get cost vectors */
-   c_x = this_ -> node_costs[x];
-   c_y = this_ -> node_costs[y];
-
-   /* get cost matrix */
-   m = pbqp_get_costmatrix(this_, x, y);
-
-  
-   /* allocate allowed set for edge (x,y) and (y,x) */
-   if (p->tc_safe_regs == NULL) {
-     p->tc_safe_regs = (int *) malloc(sizeof(int) * c_x->getLength());
-   } 
-
-   if (r->tc_safe_regs == NULL ) {
-     r->tc_safe_regs = (int *) malloc(sizeof(int) * c_y->getLength());
-   }
-
-   p->tc_impact = r->tc_impact = 0;
-
-   row_inf_counts = (int *) alloca(sizeof(int) * c_x->getLength());
-
-   /* init arrays */
-   p->tc_safe_regs[0] = 0;
-   row_inf_counts[0] = 0;
-   for(unsigned i = 1; i < c_x->getLength(); ++i){
-     p->tc_safe_regs[i] = 1;
-     row_inf_counts[i] = 0;
-   }
-
-   r->tc_safe_regs[0] = 0;
-   for(unsigned j = 1; j < c_y->getLength(); ++j){
-     r->tc_safe_regs[j] = 1;
-   }
-
-   for(unsigned j = 0; j < c_y->getLength(); ++j) {
-      int col_inf_counts = 0;
-      for (unsigned i = 0; i < c_x->getLength(); ++i) {
-         if (isInf((*m)[i][j])) {
-              ++col_inf_counts;
-              ++row_inf_counts[i];
-         
-              p->tc_safe_regs[i] = 0;
-              r->tc_safe_regs[j] = 0;
-         }
-      }
-      if (col_inf_counts > p->tc_impact) {
-           p->tc_impact = col_inf_counts;
-      }
-   }
-
-   for(unsigned i = 0; i < c_x->getLength(); ++i){
-     if (row_inf_counts[i] > r->tc_impact)
-     {
-           r->tc_impact = row_inf_counts[i];
-     }
-   }
-           
-   delete m;
-}
-
-/* 
- * Checks whether node x can be locally coloured. 
- */
-static 
-int is_colorable(pbqp *this_,int x)
-{
-  adjnode *adj_ptr;
-  PBQPVector *c_x;
-  int result = 1;
-  int *allowed;
-  int num_allowed = 0;
-  unsigned total_impact = 0;
-
-  assert(this_ != NULL);
-  assert(x >= 0 && x < this_->num_nodes);
-  assert(this_ -> node_costs[x] != NULL);
-
-  c_x = this_ -> node_costs[x];
-
-  /* allocate allowed set */
-  allowed = (int *)malloc(sizeof(int) * c_x->getLength());
-  for(unsigned i = 0; i < c_x->getLength(); ++i){
-    if (!isInf((*c_x)[i]) && i > 0) {
-      allowed[i] = 1;
-      ++num_allowed;
-    } else { 
-      allowed[i] = 0;
-    }
-  }
-
-  /* determine local minimum */
-  for(adj_ptr=this_->adj_list[x] ;adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-      if (!adj_ptr -> tc_valid) { 
-          compute_tc_info(this_, adj_ptr);
-      }
-
-      total_impact += adj_ptr->tc_impact;
-
-      if (num_allowed > 0) {
-          for (unsigned i = 1; i < c_x->getLength(); ++i){
-            if (allowed[i]){
-              if (!adj_ptr->tc_safe_regs[i]){
-                allowed[i] = 0;
-                --num_allowed;
-                if (num_allowed == 0)
-                    break;
-              }
-            }
-          }
-      }
-      
-      if ( total_impact >= c_x->getLength() - 1 && num_allowed == 0 ) {
-         result = 0;
-         break;
-      }
-  }
-  free(allowed);
-
-  return result;
-}
-
-/* use briggs heuristic 
-  note: this_ is not a general heuristic. it only is useful for 
-  interference graphs.
- */
-int pop_colorablenode(pbqp *this_)
-{
-  int deg;
-  bucketnode *min_bucket=NULL;
-  PBQPNum min = std::numeric_limits<PBQPNum>::infinity();
- 
-  /* select node where the number of colors is less than the node degree */
-  for(deg=this_->max_deg;deg > 2;deg--) {
-    bucketnode *bucket;
-    for(bucket=this_->bucket_list[deg];bucket!= NULL;bucket = bucket -> succ) {
-      int u = bucket->u;
-      if (is_colorable(this_,u)) {
-        pbqp_remove_bucket(this_,bucket);
-        this_->num_rn_special++;
-        free(bucket);
-        return u; 
-      } 
-    }
-  }
-
-  /* select node with minimal ratio between average node costs and degree of node */
-  for(deg=this_->max_deg;deg >2; deg--) {
-    bucketnode *bucket;
-    for(bucket=this_->bucket_list[deg];bucket!= NULL;bucket = bucket -> succ) {
-      PBQPNum h;
-      int u;
- 
-      u = bucket->u;
-      assert(u>=0 && u < this_->num_nodes);
-      h = (*this_->node_costs[u])[0] / (PBQPNum) deg;
-      if (h < min) {
-        min_bucket = bucket;
-        min = h;
-      } 
-    }
-  }
-
-  /* return node and free bucket */
-  if (min_bucket != NULL) {
-    int u;
-
-    pbqp_remove_bucket(this_,min_bucket);
-    u = min_bucket->u;
-    free(min_bucket);
-    return u;
-  } else {
-    return -1;
-  }
-}
-
-
-/*****************************************************************************
- * PBQP graph parsing
- ****************************************************************************/
- 
-/* reduce pbqp problem (first phase) */
-static
-void reduce_pbqp(pbqp *this_)
-{
-  int u;
-
-  assert(this_ != NULL);
-  assert(this_->bucket_list != NULL);
-
-  for(;;){
-
-    if (this_->bucket_list[1] != NULL) {
-      u = pop_node(this_,1);
-      apply_RI(this_,u); 
-    } else if (this_->bucket_list[2] != NULL) {
-      u = pop_node(this_,2);
-      apply_RII(this_,u);
-    } else if ((u = pop_colorablenode(this_)) != -1) {
-      apply_RN(this_,u);
-    } else {
-      break;
-    }
-  } 
-}
-
-/*****************************************************************************
- * PBQP back propagation
- ****************************************************************************/
-
-/* determine solution of a reduced node. Either
-   RI or RII was applied for this_ node. */
-static
-void determine_solution(pbqp *this_,int x)
-{
-  PBQPVector *v = new PBQPVector(*this_ -> node_costs[x]);
-  adjnode *adj_ptr;
-
-  assert(this_ != NULL);
-  assert(x >= 0 && x < this_->num_nodes);
-  assert(this_ -> adj_list != NULL);
-  assert(this_ -> solution != NULL);
-
-  for(adj_ptr=this_->adj_list[x] ;adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-    int y = adj_ptr -> adj;
-    int y_sol = this_ -> solution[y];
-
-    PBQPMatrix *c_yx = pbqp_get_costmatrix(this_,y,x);
-    assert(y_sol >= 0 && y_sol < (int)this_->node_costs[y]->getLength());
-    (*v) += c_yx->getRowAsVector(y_sol);
-    delete c_yx;
-  }
-  this_ -> solution[x] = v->minIndex();
-
-  delete v;
-}
-
-/* back popagation phase of PBQP */
-static
-void back_propagate(pbqp *this_)
-{
-   int i;
-
-   assert(this_ != NULL);
-   assert(this_->stack != NULL);
-   assert(this_->stack_ptr < this_->num_nodes);
-
-   for(i=this_ -> stack_ptr-1;i>=0;i--) {
-      int x = this_ -> stack[i];
-      assert( x >= 0 && x < this_ -> num_nodes);
-      reinsert_node(this_,x);
-      determine_solution(this_,x);
-   }
-}
-
-/* solve trivial nodes of degree zero */
-static
-void determine_trivialsolution(pbqp *this_)
-{
-  int u;
-  PBQPNum delta;
-
-  assert( this_ != NULL);
-  assert( this_ -> bucket_list != NULL);
-
-  /* determine trivial solution */
-  while (this_->bucket_list[0] != NULL) {
-    u = pop_node(this_,0);
-
-    assert( u >= 0 && u < this_ -> num_nodes);
-
-    this_->solution[u] = this_->node_costs[u]->minIndex();
-    delta = (*this_->node_costs[u])[this_->solution[u]];
-    this_->min = this_->min + delta;
-
-    /* increment counter for number statistic */
-    this_->num_r0++;
-  }
-}
-
-/*****************************************************************************
- * debug facilities
- ****************************************************************************/
-static
-void check_pbqp(pbqp *this_)
-{
-  int u,v;
-  PBQPMatrix *costs;
-  adjnode *adj_ptr;
-  
-  assert( this_ != NULL);
-  
-  for(u=0;u< this_->num_nodes; u++) {
-    assert (this_ -> node_costs[u] != NULL);
-    for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
-      v = adj_ptr -> adj;
-      assert( v>= 0 && v < this_->num_nodes);
-      if (u < v ) {
-        costs = adj_ptr -> costs;
-        assert( costs->getRows() == this_->node_costs[u]->getLength() &&
-                costs->getCols() == this_->node_costs[v]->getLength());
-      }           
-    }
-  }
-}
-
-/*****************************************************************************
- * PBQP solve routines 
- ****************************************************************************/
-
-/* solve PBQP problem */
-void solve_pbqp(pbqp *this_)
-{
-  assert(this_ != NULL);
-  assert(!this_->solved); 
-  
-  /* check vector & matrix dimensions */
-  check_pbqp(this_);
-
-  /* simplify PBQP problem */  
-  
-  /* eliminate trivial nodes, i.e.
-     nodes with cost vectors of length one.  */
-  eliminate_trivial_nodes(this_); 
-
-  /* eliminate edges with independent 
-     cost matrices and normalize matrices */
-  eliminate_independent_edges(this_);
-  
-  /* create bucket list for graph parsing */
-  create_bucketlist(this_);
-  
-  /* reduce phase */
-  reduce_pbqp(this_);
-  
-  /* solve trivial nodes */
-  determine_trivialsolution(this_);
-
-  /* back propagation phase */
-  back_propagate(this_); 
-  
-  this_->solved = true;
-}
-
-/* get solution of a node */
-int get_pbqp_solution(pbqp *this_,int x)
-{
-  assert(this_ != NULL);
-  assert(this_->solution != NULL);
-  assert(this_ -> solved);
-  
-  return this_->solution[x];
-}
-
-/* is solution optimal? */
-bool is_pbqp_optimal(pbqp *this_)
-{
-  assert(this_ -> solved);
-  return this_->optimal;
-}
-
-} 
-
-/* end of pbqp.c */
diff --git a/lib/CodeGen/PBQP.h b/lib/CodeGen/PBQP.h
deleted file mode 100644
index 5fd2c06..0000000
--- a/lib/CodeGen/PBQP.h
+++ /dev/null
@@ -1,284 +0,0 @@
-//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Developed by:                   Bernhard Scholz
-//                             The University of Sydney
-//                         http://www.it.usyd.edu.au/~scholz
-//===----------------------------------------------------------------------===//
-
-// TODO:
-//
-//  * Default to null costs on vector initialisation?
-//  * C++-ify the rest of the solver.
-
-#ifndef LLVM_CODEGEN_PBQPSOLVER_H
-#define LLVM_CODEGEN_PBQPSOLVER_H
-
-#include <cassert>
-#include <algorithm>
-#include <functional>
-
-namespace llvm {
-
-//! \brief Floating point type to use in PBQP solver.
-typedef double PBQPNum;
-
-//! \brief PBQP Vector class.
-class PBQPVector {
-public:
-
-  //! \brief Construct a PBQP vector of the given size.
-  explicit PBQPVector(unsigned length) :
-    length(length), data(new PBQPNum[length]) {
-    std::fill(data, data + length, 0);
-  }
-
-  //! \brief Copy construct a PBQP vector.
-  PBQPVector(const PBQPVector &v) :
-    length(v.length), data(new PBQPNum[length]) {
-    std::copy(v.data, v.data + length, data);
-  }
-
-  ~PBQPVector() { delete[] data; }
-
-  //! \brief Assignment operator.
-  PBQPVector& operator=(const PBQPVector &v) {
-    delete[] data;
-    length = v.length;
-    data = new PBQPNum[length];
-    std::copy(v.data, v.data + length, data);
-    return *this;
-  }
-
-  //! \brief Return the length of the vector
-  unsigned getLength() const throw () {
-    return length;
-  }
-
-  //! \brief Element access.
-  PBQPNum& operator[](unsigned index) {
-    assert(index < length && "PBQPVector element access out of bounds.");
-    return data[index];
-  }
-
-  //! \brief Const element access.
-  const PBQPNum& operator[](unsigned index) const {
-    assert(index < length && "PBQPVector element access out of bounds.");
-    return data[index];
-  }
-
-  //! \brief Add another vector to this one.
-  PBQPVector& operator+=(const PBQPVector &v) {
-    assert(length == v.length && "PBQPVector length mismatch.");
-    std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 
-    return *this;
-  }
-
-  //! \brief Subtract another vector from this one.
-  PBQPVector& operator-=(const PBQPVector &v) {
-    assert(length == v.length && "PBQPVector 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 PBQP Matrix class
-class PBQPMatrix {
-public:
-
-  //! \brief Construct a PBQP Matrix with the given dimensions.
-  PBQPMatrix(unsigned rows, unsigned cols) :
-    rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
-    std::fill(data, data + (rows * cols), 0);
-  }
-
-  //! \brief Copy construct a PBQP matrix.
-  PBQPMatrix(const PBQPMatrix &m) :
-    rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
-    std::copy(m.data, m.data + (rows * cols), data);  
-  }
-
-  ~PBQPMatrix() { delete[] data; }
-
-  //! \brief Assignment operator.
-  PBQPMatrix& operator=(const PBQPMatrix &m) {
-    delete[] data;
-    rows = m.rows; cols = m.cols;
-    data = new PBQPNum[rows * cols];
-    std::copy(m.data, m.data + (rows * cols), data);
-    return *this;
-  }
-
-  //! \brief Return the number of rows in this matrix.
-  unsigned getRows() const throw () { return rows; }
-
-  //! \brief Return the number of cols in this matrix.
-  unsigned getCols() const throw () { return cols; }
-
-  //! \brief Matrix element access.
-  PBQPNum* operator[](unsigned r) {
-    assert(r < rows && "Row out of bounds.");
-    return data + (r * cols);
-  }
-
-  //! \brief Matrix element access.
-  const PBQPNum* operator[](unsigned r) const {
-    assert(r < rows && "Row out of bounds.");
-    return data + (r * cols);
-  }
-
-  //! \brief Returns the given row as a vector.
-  PBQPVector getRowAsVector(unsigned r) const {
-    PBQPVector v(cols);
-    for (unsigned c = 0; c < cols; ++c)
-      v[c] = (*this)[r][c];
-    return v; 
-  }
-
-  //! \brief Reset the matrix to the given value.
-  PBQPMatrix& 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.
-  PBQPMatrix& 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.
-  PBQPMatrix& 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.
-  PBQPMatrix transpose() const {
-    PBQPMatrix 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.
-  PBQPVector diagonalize() const {
-    assert(rows == cols && "Attempt to diagonalize non-square matrix.");
-
-    PBQPVector v(rows);
-    for (unsigned r = 0; r < rows; ++r)
-      v[r] = (*this)[r][r];
-    return v;
-  } 
-
-  //! \brief Add the given matrix to this one.
-  PBQPMatrix& operator+=(const PBQPMatrix &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.
-  PBQPMatrix& 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.
-  PBQPMatrix& 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;
-};
-
-#define EPS (1E-8)
-
-#ifndef PBQP_TYPE
-#define PBQP_TYPE
-struct pbqp;
-typedef struct pbqp pbqp;
-#endif
-
-/*****************
- * PBQP routines *
- *****************/
-
-/* allocate pbqp problem */
-pbqp *alloc_pbqp(int num);
-
-/* add node costs */
-void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs);
-
-/* add edge mat */
-void add_pbqp_edgecosts(pbqp *this_,int u,int v,PBQPMatrix *costs);
-
-/* solve PBQP problem */
-void solve_pbqp(pbqp *this_);
-
-/* get solution of a node */
-int get_pbqp_solution(pbqp *this_,int u);
-
-/* alloc PBQP */
-pbqp *alloc_pbqp(int num);
-
-/* free PBQP */
-void free_pbqp(pbqp *this_);
-
-/* is optimal */
-bool is_pbqp_optimal(pbqp *this_);
-
-}
-#endif
diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h
new file mode 100644
index 0000000..801b01e
--- /dev/null
+++ b/lib/CodeGen/PBQP/AnnotatedGraph.h
@@ -0,0 +1,170 @@
+#ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
+#define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
+
+#include "GraphBase.h"
+
+namespace PBQP {
+
+
+template <typename NodeData, typename EdgeData> class AnnotatedEdge;
+
+template <typename NodeData, typename EdgeData>
+class AnnotatedNode : public NodeBase<AnnotatedNode<NodeData, EdgeData>,
+                                      AnnotatedEdge<NodeData, EdgeData> > {
+private:
+
+  NodeData nodeData; 
+
+public:
+
+  AnnotatedNode(const Vector &costs, const NodeData &nodeData) :
+    NodeBase<AnnotatedNode<NodeData, EdgeData>,
+             AnnotatedEdge<NodeData, EdgeData> >(costs),
+             nodeData(nodeData) {}
+
+  NodeData& getNodeData() { return nodeData; }
+  const NodeData& getNodeData() const { return nodeData; }
+
+};
+
+template <typename NodeData, typename EdgeData>
+class AnnotatedEdge : public EdgeBase<AnnotatedNode<NodeData, EdgeData>,
+                                      AnnotatedEdge<NodeData, EdgeData> > {
+private:
+
+  typedef typename GraphBase<AnnotatedNode<NodeData, EdgeData>,
+                             AnnotatedEdge<NodeData, EdgeData> >::NodeIterator
+    NodeIterator;
+
+  EdgeData edgeData; 
+
+public:
+
+
+  AnnotatedEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+                const Matrix &costs, const EdgeData &edgeData) :
+    EdgeBase<AnnotatedNode<NodeData, EdgeData>,
+             AnnotatedEdge<NodeData, EdgeData> >(node1Itr, node2Itr, costs),
+    edgeData(edgeData) {}
+
+  EdgeData& getEdgeData() { return edgeData; }
+  const EdgeData& getEdgeData() const { return edgeData; }
+
+};
+
+template <typename NodeData, typename EdgeData>
+class AnnotatedGraph : public GraphBase<AnnotatedNode<NodeData, EdgeData>,
+                                        AnnotatedEdge<NodeData, EdgeData> > {
+private:
+
+  typedef GraphBase<AnnotatedNode<NodeData, EdgeData>,
+                    AnnotatedEdge<NodeData, EdgeData> > PGraph;
+
+  typedef AnnotatedNode<NodeData, EdgeData> NodeEntry;
+  typedef AnnotatedEdge<NodeData, EdgeData> EdgeEntry;
+
+
+  void copyFrom(const AnnotatedGraph &other) {
+    if (!other.areNodeIDsValid()) {
+      other.assignNodeIDs();
+    }
+    std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
+
+    for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
+         nItr != nEnd; ++nItr) {
+      newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
+    }
+
+    for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
+         eItr != eEnd; ++eItr) {
+
+      unsigned node1ID = other.getNodeID(other.getEdgeNode1(eItr)),
+               node2ID = other.getNodeID(other.getEdgeNode2(eItr));
+
+      addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
+              other.getEdgeCosts(eItr), other.getEdgeData(eItr));
+    }
+
+  }
+
+public:
+
+  typedef typename PGraph::NodeIterator NodeIterator;
+  typedef typename PGraph::ConstNodeIterator ConstNodeIterator;
+  typedef typename PGraph::EdgeIterator EdgeIterator;
+  typedef typename PGraph::ConstEdgeIterator ConstEdgeIterator;
+
+  AnnotatedGraph() {}
+
+  AnnotatedGraph(const AnnotatedGraph &other) {
+    copyFrom(other);
+  }
+
+  AnnotatedGraph& operator=(const AnnotatedGraph &other) {
+    PGraph::clear();
+    copyFrom(other);
+    return *this;
+  }
+
+  NodeIterator addNode(const Vector &costs, const NodeData &data) {
+    return PGraph::addConstructedNode(NodeEntry(costs, data));
+  }
+
+  EdgeIterator addEdge(const NodeIterator &node1Itr,
+                       const NodeIterator &node2Itr,
+                       const Matrix &costs, const EdgeData &data) {
+    return PGraph::addConstructedEdge(EdgeEntry(node1Itr, node2Itr,
+                                                costs, data));
+  }
+
+  NodeData& getNodeData(const NodeIterator &nodeItr) {
+    return getNodeEntry(nodeItr).getNodeData();
+  }
+
+  const NodeData& getNodeData(const NodeIterator &nodeItr) const {
+    return getNodeEntry(nodeItr).getNodeData();
+  }
+
+  EdgeData& getEdgeData(const EdgeIterator &edgeItr) {
+    return getEdgeEntry(edgeItr).getEdgeData();
+  }
+
+  const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const {
+    return getEdgeEntry(edgeItr).getEdgeData();
+  }
+
+  SimpleGraph toSimpleGraph() const {
+    SimpleGraph g;
+
+    if (!PGraph::areNodeIDsValid()) {
+      PGraph::assignNodeIDs();
+    }
+    std::vector<SimpleGraph::NodeIterator> newNodeItrs(PGraph::getNumNodes());
+
+    for (ConstNodeIterator nItr = PGraph::nodesBegin(), 
+         nEnd = PGraph::nodesEnd();
+         nItr != nEnd; ++nItr) {
+
+      newNodeItrs[getNodeID(nItr)] = g.addNode(getNodeCosts(nItr));
+    }
+
+    for (ConstEdgeIterator
+         eItr = PGraph::edgesBegin(), eEnd = PGraph::edgesEnd();
+         eItr != eEnd; ++eItr) {
+
+      unsigned node1ID = getNodeID(getEdgeNode1(eItr)),
+               node2ID = getNodeID(getEdgeNode2(eItr));
+
+        g.addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
+                  getEdgeCosts(eItr));
+    }
+
+    return g;
+  }
+
+};
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
diff --git a/lib/CodeGen/PBQP/ExhaustiveSolver.h b/lib/CodeGen/PBQP/ExhaustiveSolver.h
new file mode 100644
index 0000000..98f7140
--- /dev/null
+++ b/lib/CodeGen/PBQP/ExhaustiveSolver.h
@@ -0,0 +1,93 @@
+#ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
+#define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
+
+#include "Solver.h"
+
+namespace PBQP {
+
+class ExhaustiveSolverImpl {
+private:
+
+  const SimpleGraph &g;
+
+  PBQPNum getSolutionCost(const Solution &solution) const {
+    PBQPNum cost = 0.0;
+    
+    for (SimpleGraph::ConstNodeIterator
+         nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+      
+      unsigned nodeId = g.getNodeID(nodeItr);
+
+      cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
+    }
+
+    for (SimpleGraph::ConstEdgeIterator
+         edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
+         edgeItr != edgeEnd; ++edgeItr) {
+      
+      SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr),
+                                     n2 = g.getEdgeNode2Itr(edgeItr);
+      unsigned sol1 = solution.getSelection(g.getNodeID(n1)),
+               sol2 = solution.getSelection(g.getNodeID(n2));
+
+      cost += g.getEdgeCosts(edgeItr)[sol1][sol2];
+    }
+
+    return cost;
+  }
+
+public:
+
+  ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {}
+
+  Solution solve() const {
+    Solution current(g.getNumNodes(), true), optimal(current);
+
+    PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity();
+    bool finished = false;
+
+    while (!finished) {
+      PBQPNum currentCost = getSolutionCost(current);
+
+      if (currentCost < bestCost) {
+        optimal = current;
+        bestCost = currentCost;
+      }
+
+      // assume we're done.
+      finished = true;
+
+      for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+        if (current.getSelection(i) ==
+            (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) {
+          current.setSelection(i, 0);
+        }
+        else {
+          current.setSelection(i, current.getSelection(i) + 1);
+          finished = false;
+          break;
+        }
+      }
+
+    }
+
+    optimal.setSolutionCost(bestCost);
+
+    return optimal;
+  }
+
+};
+
+class ExhaustiveSolver : public Solver {
+public:
+  ~ExhaustiveSolver() {}
+  Solution solve(const SimpleGraph &g) const {
+    ExhaustiveSolverImpl solver(g);
+    return solver.solve();
+  }
+};
+
+}
+
+#endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP
diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h
new file mode 100644
index 0000000..bda5952
--- /dev/null
+++ b/lib/CodeGen/PBQP/GraphBase.h
@@ -0,0 +1,570 @@
+#ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
+#define LLVM_CODEGEN_PBQP_GRAPHBASE_H
+
+#include "PBQPMath.h"
+
+#include <list>
+#include <vector>
+
+namespace PBQP {
+
+// UGLY, but I'm not sure there's a good way around this: We need to be able to
+// look up a Node's "adjacent edge list" structure type before the Node type is
+// fully constructed.  We can enable this by pushing the choice of data type
+// out into this traits class.
+template <typename Graph>
+class NodeBaseTraits {
+  public:
+    typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
+    typedef typename AdjEdgeList::iterator AdjEdgeIterator;
+    typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
+};
+
+/// \brief Base for concrete graph classes. Provides a basic set of graph
+///        operations which are useful for PBQP solvers.
+template <typename NodeEntry, typename EdgeEntry>
+class GraphBase {
+private:
+
+  typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
+
+  typedef std::list<NodeEntry> NodeList;
+  typedef std::list<EdgeEntry> EdgeList;
+
+  NodeList nodeList;
+  unsigned nodeListSize;
+
+  EdgeList edgeList;
+  unsigned edgeListSize;
+
+  GraphBase(const ThisGraphT &other) { abort(); }
+  void operator=(const ThisGraphT &other) { abort(); } 
+  
+public:
+
+  /// \brief Iterates over the nodes of a graph.
+  typedef typename NodeList::iterator NodeIterator;
+  /// \brief Iterates over the nodes of a const graph.
+  typedef typename NodeList::const_iterator ConstNodeIterator;
+  /// \brief Iterates over the edges of a graph.
+  typedef typename EdgeList::iterator EdgeIterator;
+  /// \brief Iterates over the edges of a const graph.
+  typedef typename EdgeList::const_iterator ConstEdgeIterator;
+
+  /// \brief Iterates over the edges attached to a node.
+  typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
+    AdjEdgeIterator;
+
+  /// \brief Iterates over the edges attached to a node in a const graph.
+  typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
+    ConstAdjEdgeIterator;
+
+private:
+
+  typedef std::vector<NodeIterator> IDToNodeMap;
+
+  IDToNodeMap idToNodeMap;
+  bool nodeIDsValid;
+
+  void invalidateNodeIDs() {
+    if (nodeIDsValid) {
+      idToNodeMap.clear();
+      nodeIDsValid = false;
+    }
+  }
+
+  template <typename ItrT>
+  bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
+    for (ItrT t = begin; t != end; ++t) {
+      if (itr == t)
+        return true;
+    }
+
+    return false;
+  }
+
+protected:
+
+  GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
+  
+  NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
+  const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
+    return *nodeItr;
+  }
+
+  EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
+  const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
+    return *edgeItr;
+  }
+
+  NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
+    ++nodeListSize;
+
+    invalidateNodeIDs();
+
+    NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
+
+    return newNodeItr;
+  }
+
+  EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
+
+    assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
+          == edgeList.end()) && "Attempt to add duplicate edge.");
+
+    ++edgeListSize;
+
+    // Add the edge to the graph.
+    EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
+
+    // Get a reference to the version in the graph.
+    EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
+
+    // Node entries:
+    NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
+              &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
+
+    unsigned n1Len = node1Entry.getCosts().getLength(),
+             n2Len = node2Entry.getCosts().getLength(),
+             mRows = newEdgeEntry.getCosts().getRows(),
+             mCols = newEdgeEntry.getCosts().getCols();
+
+    // Sanity check on matrix dimensions.
+    assert((n1Len == mRows) && (n2Len == mCols) &&
+        "Matrix dimensions do not match cost vector dimensions.");
+
+    // Create links between nodes and edges.
+    newEdgeEntry.setNode1ThisEdgeItr(
+        node1Entry.addAdjEdge(edgeItr));
+    newEdgeEntry.setNode2ThisEdgeItr(
+        node2Entry.addAdjEdge(edgeItr));
+
+    return edgeItr;
+  }
+
+public:
+
+  /// \brief Returns the number of nodes in this graph.
+  unsigned getNumNodes() const { return nodeListSize; }
+
+  /// \brief Returns the number of edges in this graph.
+  unsigned getNumEdges() const { return edgeListSize; } 
+
+  /// \brief Return the cost vector for the given node.
+  Vector& getNodeCosts(const NodeIterator &nodeItr) {
+    return getNodeEntry(nodeItr).getCosts();
+  }
+
+  /// \brief Return the cost vector for the give node. 
+  const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
+    return getNodeEntry(nodeItr).getCosts();
+  }
+
+  /// \brief Return the degree of the given node.
+  unsigned getNodeDegree(const NodeIterator &nodeItr) const {
+    return getNodeEntry(nodeItr).getDegree();
+  }
+
+  /// \brief Assigns sequential IDs to the nodes, starting at 0, which
+  /// remain valid until the next addition or removal of a node.
+  void assignNodeIDs() {
+    unsigned curID = 0;
+    idToNodeMap.resize(getNumNodes());
+    for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr, ++curID) {
+      getNodeEntry(nodeItr).setID(curID);
+      idToNodeMap[curID] = nodeItr;
+    }
+    nodeIDsValid = true;
+  }
+
+  /// \brief Assigns sequential IDs to the nodes using the ordering of the
+  /// given vector.
+  void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
+    assert((getNumNodes() == nodeOrdering.size()) && 
+           "Wrong number of nodes in node ordering.");
+    idToNodeMap = nodeOrdering;
+    for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
+      getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
+    }
+    nodeIDsValid = true;
+  }
+
+  /// \brief Returns true if valid node IDs are assigned, false otherwise.
+  bool areNodeIDsValid() const { return nodeIDsValid; }
+
+  /// \brief Return the numeric ID of the given node.
+  ///
+  /// Calls to this method will result in an assertion failure if there have
+  /// been any node additions or removals since the last call to
+  /// assignNodeIDs().
+  unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
+    assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
+    return getNodeEntry(nodeItr).getID();
+  }
+
+  /// \brief Returns the iterator associated with the given node ID.
+  NodeIterator getNodeItr(unsigned nodeID) {
+    assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
+    return idToNodeMap[nodeID];
+  }
+
+  /// \brief Returns the iterator associated with the given node ID.
+  ConstNodeIterator getNodeItr(unsigned nodeID) const {
+    assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
+    return idToNodeMap[nodeID];
+  }
+
+  /// \brief Removes the given node (and all attached edges) from the graph.
+  void removeNode(const NodeIterator &nodeItr) {
+    assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
+           "Iterator does not belong to this graph!");
+
+    invalidateNodeIDs();
+    
+    NodeEntry &nodeEntry = getNodeEntry(nodeItr);
+
+    // We need to copy this out because it will be destroyed as the edges are
+    // removed.
+    typedef std::vector<EdgeIterator> AdjEdgeList;
+    typedef typename AdjEdgeList::iterator AdjEdgeListItr;
+
+    AdjEdgeList adjEdges;
+    adjEdges.reserve(nodeEntry.getDegree());
+    std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
+              std::back_inserter(adjEdges));
+
+    // Iterate over the copied out edges and remove them from the graph.
+    for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
+         itr != end; ++itr) {
+      removeEdge(*itr);
+    }
+
+    // Erase the node from the nodelist.
+    nodeList.erase(nodeItr);
+    --nodeListSize;
+  }
+
+  NodeIterator nodesBegin() { return nodeList.begin(); }
+  ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
+  NodeIterator nodesEnd() { return nodeList.end(); }
+  ConstNodeIterator nodesEnd() const { return nodeList.end(); }
+
+  AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
+    return getNodeEntry(nodeItr).adjEdgesBegin();
+  }
+
+  ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
+    return getNodeEntry(nodeItr).adjEdgesBegin();
+  }
+
+  AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
+    return getNodeEntry(nodeItr).adjEdgesEnd();
+  }
+  
+  ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
+    getNodeEntry(nodeItr).adjEdgesEnd();
+  }
+
+  EdgeIterator findEdge(const NodeIterator &node1Itr,
+                        const NodeIterator &node2Itr) {
+
+    for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
+         adjEdgeEnd = adjEdgesEnd(node1Itr);
+         adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+      if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
+          (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
+        return *adjEdgeItr;
+      }
+    }
+
+    return edgeList.end();
+  }
+
+  ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
+                             const ConstNodeIterator &node2Itr) const {
+
+    for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
+         adjEdgeEnd = adjEdgesEnd(node1Itr);
+         adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) {
+      if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
+          (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
+        return *adjEdgeItr;
+      }
+    }
+
+    return edgeList.end();
+  }
+
+  Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
+    return getEdgeEntry(edgeItr).getCosts();
+  }
+
+  const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
+    return getEdgeEntry(edgeItr).getCosts();
+  }
+
+  NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
+    return getEdgeEntry(edgeItr).getNode1Itr();
+  }
+
+  ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
+    return getEdgeEntry(edgeItr).getNode1Itr();
+  }
+
+  NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
+    return getEdgeEntry(edgeItr).getNode2Itr();
+  }
+
+  ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
+    return getEdgeEntry(edgeItr).getNode2Itr();
+  }
+
+  NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
+                                const NodeIterator &nodeItr) {
+
+    EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+    if (nodeItr == edgeEntry.getNode1Itr()) {
+      return edgeEntry.getNode2Itr();
+    }
+    //else
+    return edgeEntry.getNode1Itr();
+  }
+
+  ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
+                                     const ConstNodeIterator &nodeItr) const {
+
+    const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+    if (nodeItr == edgeEntry.getNode1Itr()) {
+      return edgeEntry.getNode2Itr();
+    }
+    //else
+    return edgeEntry.getNode1Itr();
+  }
+
+  void removeEdge(const EdgeIterator &edgeItr) {
+    assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
+           "Iterator does not belong to this graph!");
+
+    --edgeListSize;
+
+    // Get the edge entry.
+    EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+
+    // Get the nodes entry.
+    NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
+              &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
+
+    // Disconnect the edge from the nodes.
+    node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
+    node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
+
+    // Remove the edge from the graph.
+    edgeList.erase(edgeItr);
+  }
+
+  EdgeIterator edgesBegin() { return edgeList.begin(); }
+  ConstEdgeIterator edgesBegin() const { return edgeList.begin(); }
+  EdgeIterator edgesEnd() { return edgeList.end(); }
+  ConstEdgeIterator edgesEnd() const { return edgeList.end(); }
+
+  void clear() {
+    nodeList.clear();
+    nodeListSize = 0;
+    edgeList.clear();
+    edgeListSize = 0;
+    idToNodeMap.clear();
+  }
+
+  template <typename OStream>
+  void printDot(OStream &os) const {
+    
+    assert(areNodeIDsValid() &&
+           "Cannot print a .dot of a graph unless IDs have been assigned.");
+    
+    os << "graph {\n";
+
+    for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+
+      os << "  node" << getNodeID(nodeItr) << " [ label=\""
+         << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+    }
+
+    os << "  edge [ len=" << getNumNodes() << " ]\n";
+
+    for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
+         edgeItr != edgeEnd; ++edgeItr) {
+
+      os << "  node" << getNodeID(getEdgeNode1Itr(edgeItr))
+         << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
+         << " [ label=\"";
+
+      const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+
+      for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
+        os << edgeCosts.getRowAsVector(i) << "\\n";
+      }
+
+      os << "\" ]\n";
+    }
+
+    os << "}\n";
+  }
+
+  template <typename OStream>
+  void printDot(OStream &os) {
+    if (!areNodeIDsValid()) {
+      assignNodeIDs();
+    }
+
+    const_cast<const ThisGraphT*>(this)->printDot(os);
+  }
+
+  template <typename OStream>
+  void dumpTo(OStream &os) const {
+    typedef ConstNodeIterator ConstNodeID;
+    
+    assert(areNodeIDsValid() &&
+           "Cannot dump a graph unless IDs have been assigned.");
+
+    for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
+         nItr != nEnd; ++nItr) {
+      os << getNodeID(nItr) << "\n";
+    }
+
+    unsigned edgeNumber = 1;
+    for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
+         eItr != eEnd; ++eItr) {
+
+      os << edgeNumber++ << ": { "
+         << getNodeID(getEdgeNode1Itr(eItr)) << ", "
+         << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
+    }
+
+  }
+
+  template <typename OStream>
+  void dumpTo(OStream &os) {
+    if (!areNodeIDsValid()) {
+      assignNodeIDs();
+    }
+
+    const_cast<const ThisGraphT*>(this)->dumpTo(os);
+  }
+
+};
+
+/// \brief Provides a base from which to derive nodes for GraphBase.
+template <typename NodeImpl, typename EdgeImpl>
+class NodeBase {
+private:
+
+  typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
+  typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
+
+public:
+  typedef typename GraphBaseT::EdgeIterator EdgeIterator;
+
+private:
+  typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
+
+  unsigned degree, id;
+  Vector costs;
+  AdjEdgeList adjEdges;
+
+  void operator=(const NodeBase& other) {
+    assert(false && "Can't assign NodeEntrys.");
+  }
+
+public:
+
+  typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
+  typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
+    ConstAdjEdgeIterator;
+
+  NodeBase(const Vector &costs) : degree(0), costs(costs) {
+    assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
+  }
+
+  Vector& getCosts() { return costs; }
+  const Vector& getCosts() const { return costs; }
+
+  unsigned getDegree() const { return degree;  }
+
+  void setID(unsigned id) { this->id = id; }
+  unsigned getID() const { return id; }
+
+  AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
+    ++degree;
+    return adjEdges.insert(adjEdges.end(), edgeItr);
+  }
+
+  void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
+    --degree;
+    adjEdges.erase(adjEdgeItr);
+  }
+
+  AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); } 
+  ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); }
+  AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); }
+  ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); }
+
+};
+
+template <typename NodeImpl, typename EdgeImpl>
+class EdgeBase {
+public:
+  typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
+  typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
+
+  typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
+
+private:
+
+  NodeIterator node1Itr, node2Itr;
+  NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
+  Matrix costs;
+
+  void operator=(const EdgeBase &other) {
+    assert(false && "Can't assign EdgeEntrys.");
+  }
+
+public:
+
+  EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+           const Matrix &costs) :
+    node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
+
+    assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
+           "Can't have zero-dimensioned cost matrices");
+  }
+
+  Matrix& getCosts() { return costs; }
+  const Matrix& getCosts() const { return costs; }
+
+  const NodeIterator& getNode1Itr() const { return node1Itr; }
+  const NodeIterator& getNode2Itr() const { return node2Itr; }
+
+  void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
+    this->node1ThisEdgeItr = node1ThisEdgeItr;
+  }
+
+  const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
+    return node1ThisEdgeItr;
+  }
+
+  void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
+    this->node2ThisEdgeItr = node2ThisEdgeItr;
+  }
+
+  const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
+    return node2ThisEdgeItr;
+  }
+
+};
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP
diff --git a/lib/CodeGen/PBQP/GraphGenerator.h b/lib/CodeGen/PBQP/GraphGenerator.h
new file mode 100644
index 0000000..620e21e
--- /dev/null
+++ b/lib/CodeGen/PBQP/GraphGenerator.h
@@ -0,0 +1,195 @@
+#ifndef LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H
+#define LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H
+
+#include "PBQPMath.h"
+
+namespace PBQP {
+
+unsigned randRange(unsigned min, unsigned max) {
+  return min + (rand() % (max - min + 1));
+}
+
+class BasicNodeCostsGenerator {
+private:
+
+  unsigned maxDegree, minCost, maxCost;
+
+
+public:
+
+  BasicNodeCostsGenerator(unsigned maxDegree, unsigned minCost,
+                          unsigned maxCost) :
+    maxDegree(maxDegree), minCost(minCost), maxCost(maxCost) { }
+
+  Vector operator()() const {
+    Vector v(randRange(1, maxDegree));
+    for (unsigned i = 0; i < v.getLength(); ++i) {
+      v[i] = randRange(minCost, maxCost);
+    }
+    return v;
+  };
+
+};
+
+class FixedDegreeSpillCostGenerator {
+private:
+
+  unsigned degree, spillCostMin, spillCostMax;
+
+public:
+
+  FixedDegreeSpillCostGenerator(unsigned degree, unsigned spillCostMin,
+                                unsigned spillCostMax) :
+    degree(degree), spillCostMin(spillCostMin), spillCostMax(spillCostMax) { }
+
+  Vector operator()() const {
+    Vector v(degree, 0);
+    v[0] = randRange(spillCostMin, spillCostMax);
+    return v;
+  }
+
+};
+
+class BasicEdgeCostsGenerator {
+private:
+
+  unsigned minCost, maxCost;
+
+public:
+
+  BasicEdgeCostsGenerator(unsigned minCost, unsigned maxCost) :
+    minCost(minCost), maxCost(maxCost) {}
+
+  Matrix operator()(const SimpleGraph &g,
+                        const SimpleGraph::ConstNodeIterator &n1,
+                        const SimpleGraph::ConstNodeIterator &n2) const {
+
+    Matrix m(g.getNodeCosts(n1).getLength(),
+                 g.getNodeCosts(n2).getLength());
+
+    for (unsigned i = 0; i < m.getRows(); ++i) {
+      for (unsigned j = 0; j < m.getCols(); ++j) {
+        m[i][j] = randRange(minCost, maxCost);
+      }
+    }
+
+    return m;
+  }
+
+};
+
+class InterferenceCostsGenerator {
+public:
+
+  Matrix operator()(const SimpleGraph &g,
+                        const SimpleGraph::ConstNodeIterator &n1,
+                        const SimpleGraph::ConstNodeIterator &n2) const {
+
+    unsigned len = g.getNodeCosts(n1).getLength();
+
+    assert(len == g.getNodeCosts(n2).getLength());
+
+    Matrix m(len, len);
+
+    m[0][0] = 0;
+    for (unsigned i = 1; i < len; ++i) {
+      m[i][i] = std::numeric_limits<PBQPNum>::infinity();
+    }
+
+    return m;
+  }
+};
+
+class RingEdgeGenerator {
+public:
+
+  template <typename EdgeCostsGenerator>
+  void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) {
+
+    assert(g.areNodeIDsValid() && "Graph must have valid node IDs.");
+
+    if (g.getNumNodes() < 2)
+      return;
+
+    if (g.getNumNodes() == 2) {
+      SimpleGraph::NodeIterator n1 = g.getNodeItr(0),
+                                n2 = g.getNodeItr(1);
+      g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+      return;
+    }
+
+    // Else |V| > 2:
+    for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+      SimpleGraph::NodeIterator
+        n1 = g.getNodeItr(i),
+        n2 = g.getNodeItr((i + 1) % g.getNumNodes());
+      g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+    }
+  }
+
+};
+
+class FullyConnectedEdgeGenerator {
+public:
+    
+  template <typename EdgeCostsGenerator>
+  void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) {
+    assert(g.areNodeIDsValid() && "Graph must have valid node IDs.");
+    
+    for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+      for (unsigned j = i + 1; j < g.getNumNodes(); ++j) {
+        SimpleGraph::NodeIterator
+          n1 = g.getNodeItr(i),
+          n2 = g.getNodeItr(j);
+        g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+      }
+    }
+  }
+
+};
+
+class RandomEdgeGenerator {
+public:
+
+  template <typename EdgeCostsGenerator>
+  void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) {
+    
+    assert(g.areNodeIDsValid() && "Graph must have valid node IDs.");
+    
+    for (unsigned i = 0; i < g.getNumNodes(); ++i) {
+      for (unsigned j = i + 1; j < g.getNumNodes(); ++j) {
+        if (rand() % 2 == 0) {
+          SimpleGraph::NodeIterator
+            n1 = g.getNodeItr(i),
+            n2 = g.getNodeItr(j);
+          g.addEdge(n1, n2, edgeCostsGen(g, n1, n2));
+        }
+      }
+    }
+  }
+
+};
+
+template <typename NodeCostsGenerator,
+          typename EdgesGenerator,
+          typename EdgeCostsGenerator>
+SimpleGraph createRandomGraph(unsigned numNodes,
+                              NodeCostsGenerator nodeCostsGen,
+                              EdgesGenerator edgeGen,
+                              EdgeCostsGenerator edgeCostsGen) {
+
+  SimpleGraph g;
+  for (unsigned n = 0; n < numNodes; ++n) {
+    g.addNode(nodeCostsGen());
+  }
+
+  g.assignNodeIDs();
+
+  edgeGen(g, edgeCostsGen);
+
+  return g;
+}
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H
diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h
new file mode 100644
index 0000000..7088f36
--- /dev/null
+++ b/lib/CodeGen/PBQP/HeuristicSolver.h
@@ -0,0 +1,799 @@
+#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
+#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
+
+#include "Solver.h"
+#include "AnnotatedGraph.h"
+
+#include <limits>
+#include <iostream>
+
+namespace PBQP {
+
+/// \brief Important types for the HeuristicSolverImpl.
+/// 
+/// Declared seperately to allow access to heuristic classes before the solver
+/// is fully constructed.
+template <typename HeuristicNodeData, typename HeuristicEdgeData>
+class HSITypes {
+public:
+
+  class NodeData;
+  class EdgeData;
+
+  typedef AnnotatedGraph<NodeData, EdgeData> SolverGraph;
+  typedef typename SolverGraph::NodeIterator GraphNodeIterator;
+  typedef typename SolverGraph::EdgeIterator GraphEdgeIterator;
+  typedef typename SolverGraph::AdjEdgeIterator GraphAdjEdgeIterator;
+
+  typedef std::list<GraphNodeIterator> NodeList;
+  typedef typename NodeList::iterator NodeListIterator;
+
+  typedef std::vector<GraphNodeIterator> NodeStack;
+  typedef typename NodeStack::iterator NodeStackIterator;
+
+  class NodeData {
+    friend class EdgeData;
+
+  private:
+
+    typedef std::list<GraphEdgeIterator> LinksList;
+
+    unsigned numLinks;
+    LinksList links, solvedLinks;
+    NodeListIterator bucketItr;
+    HeuristicNodeData heuristicData;
+
+  public:
+
+    typedef typename LinksList::iterator AdjLinkIterator;
+
+  private:
+
+    AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) {
+      ++numLinks;
+      return links.insert(links.end(), edgeItr);
+    }
+
+    void delLink(const AdjLinkIterator &adjLinkItr) {
+      --numLinks;
+      links.erase(adjLinkItr);
+    }
+
+  public:
+
+    NodeData() : numLinks(0) {}
+
+    unsigned getLinkDegree() const { return numLinks; }
+
+    HeuristicNodeData& getHeuristicData() { return heuristicData; }
+    const HeuristicNodeData& getHeuristicData() const {
+      return heuristicData;
+    }
+
+    void setBucketItr(const NodeListIterator &bucketItr) {
+      this->bucketItr = bucketItr;
+    }
+
+    const NodeListIterator& getBucketItr() const {
+      return bucketItr;
+    }
+
+    AdjLinkIterator adjLinksBegin() {
+      return links.begin();
+    }
+
+    AdjLinkIterator adjLinksEnd() {
+      return links.end();
+    }
+
+    void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) {
+      solvedLinks.push_back(solvedLinkItr);
+    }
+
+    AdjLinkIterator solvedLinksBegin() {
+      return solvedLinks.begin();
+    }
+
+    AdjLinkIterator solvedLinksEnd() {
+      return solvedLinks.end();
+    }
+
+  };
+
+  class EdgeData {
+  private:
+
+    SolverGraph &g;
+    GraphNodeIterator node1Itr, node2Itr;
+    HeuristicEdgeData heuristicData;
+    typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr;
+
+  public:
+
+    EdgeData(SolverGraph &g) : g(g) {}
+
+    HeuristicEdgeData& getHeuristicData() { return heuristicData; }
+    const HeuristicEdgeData& getHeuristicData() const {
+      return heuristicData;
+    }
+
+    void setup(const GraphEdgeIterator &thisEdgeItr) {
+      node1Itr = g.getEdgeNode1Itr(thisEdgeItr);
+      node2Itr = g.getEdgeNode2Itr(thisEdgeItr);
+
+      node1ThisEdgeItr = g.getNodeData(node1Itr).addLink(thisEdgeItr);
+      node2ThisEdgeItr = g.getNodeData(node2Itr).addLink(thisEdgeItr);
+    }
+
+    void unlink() {
+      g.getNodeData(node1Itr).delLink(node1ThisEdgeItr);
+      g.getNodeData(node2Itr).delLink(node2ThisEdgeItr);
+    }
+
+  };
+
+};
+
+template <typename Heuristic>
+class HeuristicSolverImpl {
+public:
+  // Typedefs to make life easier:
+  typedef HSITypes<typename Heuristic::NodeData,
+                   typename Heuristic::EdgeData> HSIT;
+  typedef typename HSIT::SolverGraph SolverGraph;
+  typedef typename HSIT::NodeData NodeData;
+  typedef typename HSIT::EdgeData EdgeData;
+  typedef typename HSIT::GraphNodeIterator GraphNodeIterator;
+  typedef typename HSIT::GraphEdgeIterator GraphEdgeIterator;
+  typedef typename HSIT::GraphAdjEdgeIterator GraphAdjEdgeIterator;
+
+  typedef typename HSIT::NodeList NodeList;
+  typedef typename HSIT::NodeListIterator NodeListIterator;
+
+  typedef std::vector<GraphNodeIterator> NodeStack;
+  typedef typename NodeStack::iterator NodeStackIterator;
+
+  /*!
+   * \brief Constructor, which performs all the actual solver work.
+   */
+  HeuristicSolverImpl(const SimpleGraph &orig) :
+    solution(orig.getNumNodes(), true)
+  {
+    copyGraph(orig);
+    simplify();
+    setup();
+    computeSolution();
+    computeSolutionCost(orig);
+  }
+
+  /*!
+   * \brief Returns the graph for this solver.
+   */
+  SolverGraph& getGraph() { return g; }
+
+  /*!
+   * \brief Return the solution found by this solver.
+   */
+  const Solution& getSolution() const { return solution; }
+
+private:
+
+  /*!
+   * \brief Add the given node to the appropriate bucket for its link
+   * degree.
+   */
+  void addToBucket(const GraphNodeIterator &nodeItr) {
+    NodeData &nodeData = g.getNodeData(nodeItr);
+
+    switch (nodeData.getLinkDegree()) {
+      case 0: nodeData.setBucketItr(
+                r0Bucket.insert(r0Bucket.end(), nodeItr));
+              break;                                            
+      case 1: nodeData.setBucketItr(
+                r1Bucket.insert(r1Bucket.end(), nodeItr));
+              break;
+      case 2: nodeData.setBucketItr(
+                r2Bucket.insert(r2Bucket.end(), nodeItr));
+              break;
+      default: heuristic.addToRNBucket(nodeItr);
+               break;
+    }
+  }
+
+  /*!
+   * \brief Remove the given node from the appropriate bucket for its link
+   * degree.
+   */
+  void removeFromBucket(const GraphNodeIterator &nodeItr) {
+    NodeData &nodeData = g.getNodeData(nodeItr);
+
+    switch (nodeData.getLinkDegree()) {
+      case 0: r0Bucket.erase(nodeData.getBucketItr()); break;
+      case 1: r1Bucket.erase(nodeData.getBucketItr()); break;
+      case 2: r2Bucket.erase(nodeData.getBucketItr()); break;
+      default: heuristic.removeFromRNBucket(nodeItr); break;
+    }
+  }
+
+public:
+
+  /*!
+   * \brief Add a link.
+   */
+  void addLink(const GraphEdgeIterator &edgeItr) {
+    g.getEdgeData(edgeItr).setup(edgeItr);
+
+    if ((g.getNodeData(g.getEdgeNode1Itr(edgeItr)).getLinkDegree() > 2) ||
+        (g.getNodeData(g.getEdgeNode2Itr(edgeItr)).getLinkDegree() > 2)) {
+      heuristic.handleAddLink(edgeItr);
+    }
+  }
+
+  /*!
+   * \brief Remove link, update info for node.
+   *
+   * Only updates information for the given node, since usually the other
+   * is about to be removed.
+   */
+  void removeLink(const GraphEdgeIterator &edgeItr,
+                  const GraphNodeIterator &nodeItr) {
+
+    if (g.getNodeData(nodeItr).getLinkDegree() > 2) {
+      heuristic.handleRemoveLink(edgeItr, nodeItr);
+    }
+    g.getEdgeData(edgeItr).unlink();
+  }
+
+  /*!
+   * \brief Remove link, update info for both nodes. Useful for R2 only.
+   */
+  void removeLinkR2(const GraphEdgeIterator &edgeItr) {
+    GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr);
+
+    if (g.getNodeData(node1Itr).getLinkDegree() > 2) {
+      heuristic.handleRemoveLink(edgeItr, node1Itr);
+    }
+    removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr));
+  }
+
+  /*!
+   * \brief Removes all links connected to the given node.
+   */
+  void unlinkNode(const GraphNodeIterator &nodeItr) {
+    NodeData &nodeData = g.getNodeData(nodeItr);
+
+    typedef std::vector<GraphEdgeIterator> TempEdgeList;
+
+    TempEdgeList edgesToUnlink;
+    edgesToUnlink.reserve(nodeData.getLinkDegree());
+
+    // Copy adj edges into a temp vector. We want to destroy them during
+    // the unlink, and we can't do that while we're iterating over them.
+    std::copy(nodeData.adjLinksBegin(), nodeData.adjLinksEnd(),
+              std::back_inserter(edgesToUnlink));
+
+    for (typename TempEdgeList::iterator
+         edgeItr = edgesToUnlink.begin(), edgeEnd = edgesToUnlink.end();
+         edgeItr != edgeEnd; ++edgeItr) {
+
+      GraphNodeIterator otherNode = g.getEdgeOtherNode(*edgeItr, nodeItr);
+
+      removeFromBucket(otherNode);
+      removeLink(*edgeItr, otherNode);
+      addToBucket(otherNode);
+    }
+  }
+
+  /*!
+   * \brief Push the given node onto the stack to be solved with
+   * backpropagation.
+   */
+  void pushStack(const GraphNodeIterator &nodeItr) {
+    stack.push_back(nodeItr);
+  }
+
+  /*!
+   * \brief Set the solution of the given node.
+   */
+  void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) {
+    solution.setSelection(g.getNodeID(nodeItr), solIndex);
+
+    for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
+         adjEdgeEnd = g.adjEdgesEnd(nodeItr);
+         adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+      GraphEdgeIterator edgeItr(*adjEdgeItr);
+      GraphNodeIterator adjNodeItr(g.getEdgeOtherNode(edgeItr, nodeItr));
+      g.getNodeData(adjNodeItr).addSolvedLink(edgeItr);
+    }
+  }
+
+private:
+
+  SolverGraph g;
+  Heuristic heuristic;
+  Solution solution;
+
+  NodeList r0Bucket,
+           r1Bucket,
+           r2Bucket;
+
+  NodeStack stack;
+
+  // Copy the SimpleGraph into an annotated graph which we can use for reduction.
+  void copyGraph(const SimpleGraph &orig) {
+
+    assert((g.getNumEdges() == 0) && (g.getNumNodes() == 0) &&
+           "Graph should be empty prior to solver setup.");
+
+    assert(orig.areNodeIDsValid() &&
+           "Cannot copy from a graph with invalid node IDs.");
+
+    std::vector<GraphNodeIterator> newNodeItrs;
+
+    for (unsigned nodeID = 0; nodeID < orig.getNumNodes(); ++nodeID) {
+      newNodeItrs.push_back(
+        g.addNode(orig.getNodeCosts(orig.getNodeItr(nodeID)), NodeData()));
+    }
+
+    for (SimpleGraph::ConstEdgeIterator
+         origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd();
+         origEdgeItr != origEdgeEnd; ++origEdgeItr) {
+
+      unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)),
+               id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr));
+
+      g.addEdge(newNodeItrs[id1], newNodeItrs[id2],
+                orig.getEdgeCosts(origEdgeItr), EdgeData(g));
+    }
+
+    // Assign IDs to the new nodes using the ordering from the old graph,
+    // this will lead to nodes in the new graph getting the same ID as the
+    // corresponding node in the old graph.
+    g.assignNodeIDs(newNodeItrs);
+  }
+
+  // Simplify the annotated graph by eliminating independent edges and trivial
+  // nodes. 
+  void simplify() {
+    disconnectTrivialNodes();
+    eliminateIndependentEdges();
+  }
+
+  // Eliminate trivial nodes.
+  void disconnectTrivialNodes() {
+    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+
+      if (g.getNodeCosts(nodeItr).getLength() == 1) {
+
+        std::vector<GraphEdgeIterator> edgesToRemove;
+
+        for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
+             adjEdgeEnd = g.adjEdgesEnd(nodeItr);
+             adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+
+          GraphEdgeIterator edgeItr = *adjEdgeItr;
+
+          if (g.getEdgeNode1Itr(edgeItr) == nodeItr) {
+            GraphNodeIterator otherNodeItr = g.getEdgeNode2Itr(edgeItr);
+            g.getNodeCosts(otherNodeItr) +=
+              g.getEdgeCosts(edgeItr).getRowAsVector(0);
+          }
+          else {
+            GraphNodeIterator otherNodeItr = g.getEdgeNode1Itr(edgeItr);
+            g.getNodeCosts(otherNodeItr) +=
+              g.getEdgeCosts(edgeItr).getColAsVector(0);
+          }
+
+          edgesToRemove.push_back(edgeItr);
+        }
+
+        while (!edgesToRemove.empty()) {
+          g.removeEdge(edgesToRemove.back());
+          edgesToRemove.pop_back();
+        }
+      }
+    }
+  }
+
+  void eliminateIndependentEdges() {
+    std::vector<GraphEdgeIterator> edgesToProcess;
+
+    for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
+         edgeItr != edgeEnd; ++edgeItr) {
+      edgesToProcess.push_back(edgeItr);
+    }
+
+    while (!edgesToProcess.empty()) {
+      tryToEliminateEdge(edgesToProcess.back());
+      edgesToProcess.pop_back();
+    }
+  }
+
+  void tryToEliminateEdge(const GraphEdgeIterator &edgeItr) {
+    if (tryNormaliseEdgeMatrix(edgeItr)) {
+      g.removeEdge(edgeItr); 
+    }
+  }
+
+  bool tryNormaliseEdgeMatrix(const GraphEdgeIterator &edgeItr) {
+
+    Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
+    Vector &uCosts = g.getNodeCosts(g.getEdgeNode1Itr(edgeItr)),
+               &vCosts = g.getNodeCosts(g.getEdgeNode2Itr(edgeItr));
+
+    for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
+      PBQPNum rowMin = edgeCosts.getRowMin(r);
+      uCosts[r] += rowMin;
+      if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
+        edgeCosts.subFromRow(r, rowMin);
+      }
+      else {
+        edgeCosts.setRow(r, 0);
+      }
+    }
+
+    for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
+      PBQPNum colMin = edgeCosts.getColMin(c);
+      vCosts[c] += colMin;
+      if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
+        edgeCosts.subFromCol(c, colMin);
+      }
+      else {
+        edgeCosts.setCol(c, 0);
+      }
+    }
+
+    return edgeCosts.isZero();
+  }
+
+  void setup() {
+    setupLinks();
+    heuristic.initialise(*this);
+    setupBuckets();
+  }
+
+  void setupLinks() {
+    for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
+         edgeItr != edgeEnd; ++edgeItr) {
+      g.getEdgeData(edgeItr).setup(edgeItr);
+    }
+  }
+
+  void setupBuckets() {
+    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+      addToBucket(nodeItr);
+    }
+  }
+
+  void computeSolution() {
+    assert(g.areNodeIDsValid() &&
+           "Nodes cannot be added/removed during reduction.");
+
+    reduce();
+    computeTrivialSolutions();
+    backpropagate();
+  }
+
+  void printNode(const GraphNodeIterator &nodeItr) {
+
+    std::cerr << "Node " << g.getNodeID(nodeItr) << " (" << &*nodeItr << "):\n"
+              << "  costs = " << g.getNodeCosts(nodeItr) << "\n"
+              << "  link degree = " << g.getNodeData(nodeItr).getLinkDegree() << "\n"
+              << "  links = [ ";
+
+    for (typename HSIT::NodeData::AdjLinkIterator 
+         aeItr = g.getNodeData(nodeItr).adjLinksBegin(),
+         aeEnd = g.getNodeData(nodeItr).adjLinksEnd();
+         aeItr != aeEnd; ++aeItr) {
+      std::cerr << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr))
+                << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr))
+                << ") ";
+    }
+    std::cout << "]\n";
+  }
+
+  void dumpState() {
+
+    std::cerr << "\n";
+
+    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+      printNode(nodeItr);
+    }
+
+    NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket };
+
+    for (unsigned b = 0; b < 3; ++b) {
+      NodeList &bucket = *buckets[b];
+
+      std::cerr << "Bucket " << b << ": [ ";
+
+      for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end();
+           nItr != nEnd; ++nItr) {
+        std::cerr << g.getNodeID(*nItr) << " ";
+      }
+
+      std::cerr << "]\n";
+    }
+
+    std::cerr << "Stack: [ ";
+    for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end();
+         nsItr != nsEnd; ++nsItr) {
+      std::cerr << g.getNodeID(*nsItr) << " ";
+    }
+    std::cerr << "]\n";
+  }
+
+  void reduce() {
+    bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() &&
+      heuristic.rNBucketEmpty();
+
+    while (!reductionFinished) {
+
+      if (!r1Bucket.empty()) {
+        processR1();
+      }
+      else if (!r2Bucket.empty()) {
+        processR2();
+      }
+      else if (!heuristic.rNBucketEmpty()) {
+        solution.setProvedOptimal(false);
+        solution.incRNReductions();
+        heuristic.processRN();
+      } 
+      else reductionFinished = true;
+    }
+      
+  };
+
+  void processR1() {
+
+    // Remove the first node in the R0 bucket:
+    GraphNodeIterator xNodeItr = r1Bucket.front();
+    r1Bucket.pop_front();
+
+    solution.incR1Reductions();
+
+    //std::cerr << "Applying R1 to " << g.getNodeID(xNodeItr) << "\n";
+
+    assert((g.getNodeData(xNodeItr).getLinkDegree() == 1) &&
+           "Node in R1 bucket has degree != 1");
+
+    GraphEdgeIterator edgeItr = *g.getNodeData(xNodeItr).adjLinksBegin();
+
+    const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
+
+    const Vector &xCosts = g.getNodeCosts(xNodeItr);
+    unsigned xLen = xCosts.getLength();
+
+    // Duplicate a little code to avoid transposing matrices:
+    if (xNodeItr == g.getEdgeNode1Itr(edgeItr)) {
+      GraphNodeIterator yNodeItr = g.getEdgeNode2Itr(edgeItr);
+      Vector &yCosts = g.getNodeCosts(yNodeItr);
+      unsigned yLen = yCosts.getLength();
+
+      for (unsigned j = 0; j < yLen; ++j) {
+        PBQPNum min = edgeCosts[0][j] + xCosts[0];
+        for (unsigned i = 1; i < xLen; ++i) {
+          PBQPNum c = edgeCosts[i][j] + xCosts[i];
+          if (c < min)
+            min = c;
+        }
+        yCosts[j] += min;
+      }
+    }
+    else {
+      GraphNodeIterator yNodeItr = g.getEdgeNode1Itr(edgeItr);
+      Vector &yCosts = g.getNodeCosts(yNodeItr);
+      unsigned yLen = yCosts.getLength();
+
+      for (unsigned i = 0; i < yLen; ++i) {
+        PBQPNum min = edgeCosts[i][0] + xCosts[0];
+
+        for (unsigned j = 1; j < xLen; ++j) {
+          PBQPNum c = edgeCosts[i][j] + xCosts[j];
+          if (c < min)
+            min = c;
+        }
+        yCosts[i] += min;
+      }
+    }
+
+    unlinkNode(xNodeItr);
+    pushStack(xNodeItr);
+  }
+
+  void processR2() {
+
+    GraphNodeIterator xNodeItr = r2Bucket.front();
+    r2Bucket.pop_front();
+
+    solution.incR2Reductions();
+
+    // Unlink is unsafe here. At some point it may optimistically more a node
+    // to a lower-degree list when its degree will later rise, or vice versa,
+    // violating the assumption that node degrees monotonically decrease
+    // during the reduction phase. Instead we'll bucket shuffle manually.
+    pushStack(xNodeItr);
+
+    assert((g.getNodeData(xNodeItr).getLinkDegree() == 2) &&
+           "Node in R2 bucket has degree != 2");
+
+    const Vector &xCosts = g.getNodeCosts(xNodeItr);
+
+    typename NodeData::AdjLinkIterator tempItr =
+      g.getNodeData(xNodeItr).adjLinksBegin();
+
+    GraphEdgeIterator yxEdgeItr = *tempItr,
+                      zxEdgeItr = *(++tempItr);
+
+    GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr),
+                      zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr);
+
+    removeFromBucket(yNodeItr);
+    removeFromBucket(zNodeItr);
+
+    removeLink(yxEdgeItr, yNodeItr);
+    removeLink(zxEdgeItr, zNodeItr);
+
+    // Graph some of the costs:
+    bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr),
+         flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr);
+
+    const Matrix *yxCosts = flipEdge1 ?
+      new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) :
+      &g.getEdgeCosts(yxEdgeItr),
+                     *zxCosts = flipEdge2 ?
+      new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) :
+        &g.getEdgeCosts(zxEdgeItr);
+
+    unsigned xLen = xCosts.getLength(),
+             yLen = yxCosts->getRows(),
+             zLen = zxCosts->getRows();
+
+    // Compute delta:
+    Matrix delta(yLen, zLen);
+
+    for (unsigned i = 0; i < yLen; ++i) {
+      for (unsigned j = 0; j < zLen; ++j) {
+        PBQPNum min = (*yxCosts)[i][0] + (*zxCosts)[j][0] + xCosts[0];
+        for (unsigned k = 1; k < xLen; ++k) {
+          PBQPNum c = (*yxCosts)[i][k] + (*zxCosts)[j][k] + xCosts[k];
+          if (c < min) {
+            min = c;
+          }
+        }
+        delta[i][j] = min;
+      }
+    }
+
+    if (flipEdge1)
+      delete yxCosts;
+
+    if (flipEdge2)
+      delete zxCosts;
+
+    // Deal with the potentially induced yz edge.
+    GraphEdgeIterator yzEdgeItr = g.findEdge(yNodeItr, zNodeItr);
+    if (yzEdgeItr == g.edgesEnd()) {
+      yzEdgeItr = g.addEdge(yNodeItr, zNodeItr, delta, EdgeData(g));
+    }
+    else {
+      // There was an edge, but we're going to screw with it. Delete the old
+      // link, update the costs. We'll re-link it later.
+      removeLinkR2(yzEdgeItr);
+      g.getEdgeCosts(yzEdgeItr) +=
+        (yNodeItr == g.getEdgeNode1Itr(yzEdgeItr)) ?
+        delta : delta.transpose();
+    }
+
+    bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr);
+
+    // Nulled the edge, remove it entirely.
+    if (nullCostEdge) {
+      g.removeEdge(yzEdgeItr);
+    }
+    else {
+      // Edge remains - re-link it.
+      addLink(yzEdgeItr);
+    }
+
+    addToBucket(yNodeItr);
+    addToBucket(zNodeItr);
+    }
+
+  void computeTrivialSolutions() {
+
+    for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end();
+         r0Itr != r0End; ++r0Itr) {
+      GraphNodeIterator nodeItr = *r0Itr;
+
+      solution.incR0Reductions();
+      setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex());
+    }
+
+  }
+
+  void backpropagate() {
+    while (!stack.empty()) {
+      computeSolution(stack.back());
+      stack.pop_back();
+    }
+  }
+
+  void computeSolution(const GraphNodeIterator &nodeItr) {
+
+    NodeData &nodeData = g.getNodeData(nodeItr);
+
+    Vector v(g.getNodeCosts(nodeItr));
+
+    // Solve based on existing links.
+    for (typename NodeData::AdjLinkIterator
+         solvedLinkItr = nodeData.solvedLinksBegin(),
+         solvedLinkEnd = nodeData.solvedLinksEnd();
+         solvedLinkItr != solvedLinkEnd; ++solvedLinkItr) {
+
+      GraphEdgeIterator solvedEdgeItr(*solvedLinkItr);
+      Matrix &edgeCosts = g.getEdgeCosts(solvedEdgeItr);
+
+      if (nodeItr == g.getEdgeNode1Itr(solvedEdgeItr)) {
+        GraphNodeIterator adjNode(g.getEdgeNode2Itr(solvedEdgeItr));
+        unsigned adjSolution =
+          solution.getSelection(g.getNodeID(adjNode));
+        v += edgeCosts.getColAsVector(adjSolution);
+      }
+      else {
+        GraphNodeIterator adjNode(g.getEdgeNode1Itr(solvedEdgeItr));
+        unsigned adjSolution =
+          solution.getSelection(g.getNodeID(adjNode));
+        v += edgeCosts.getRowAsVector(adjSolution);
+      }
+
+    }
+
+    setSolution(nodeItr, v.minIndex());
+  }
+
+  void computeSolutionCost(const SimpleGraph &orig) {
+    PBQPNum cost = 0.0;
+
+    for (SimpleGraph::ConstNodeIterator
+         nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+
+      unsigned nodeId = orig.getNodeID(nodeItr);
+
+      cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
+    }
+
+    for (SimpleGraph::ConstEdgeIterator
+         edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd();
+         edgeItr != edgeEnd; ++edgeItr) {
+
+      SimpleGraph::ConstNodeIterator n1 = orig.getEdgeNode1Itr(edgeItr),
+                                     n2 = orig.getEdgeNode2Itr(edgeItr);
+      unsigned sol1 = solution.getSelection(orig.getNodeID(n1)),
+               sol2 = solution.getSelection(orig.getNodeID(n2));
+
+      cost += orig.getEdgeCosts(edgeItr)[sol1][sol2];
+    }
+
+    solution.setSolutionCost(cost);
+  }
+
+};
+
+template <typename Heuristic>
+class HeuristicSolver : public Solver {
+public:
+  Solution solve(const SimpleGraph &g) const {
+    HeuristicSolverImpl<Heuristic> solverImpl(g);
+    return solverImpl.getSolution();
+  }
+};
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h
new file mode 100644
index 0000000..fd37f5c
--- /dev/null
+++ b/lib/CodeGen/PBQP/Heuristics/Briggs.h
@@ -0,0 +1,385 @@
+#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
+#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
+
+#include "../HeuristicSolver.h"
+
+#include <set>
+
+namespace PBQP {
+namespace Heuristics {
+
+class Briggs {
+  public:
+
+    class NodeData;
+    class EdgeData;
+
+  private:
+
+    typedef HeuristicSolverImpl<Briggs> Solver;
+    typedef HSITypes<NodeData, EdgeData> HSIT;
+    typedef HSIT::SolverGraph SolverGraph;
+    typedef HSIT::GraphNodeIterator GraphNodeIterator;
+    typedef HSIT::GraphEdgeIterator GraphEdgeIterator;
+
+    class LinkDegreeComparator {
+      public:
+        LinkDegreeComparator() : g(0) {}
+        LinkDegreeComparator(SolverGraph *g) : g(g) {}
+
+        bool operator()(const GraphNodeIterator &node1Itr,
+                        const GraphNodeIterator &node2Itr) const {
+          assert((g != 0) && "Graph object not set, cannot access node data.");
+          unsigned n1Degree = g->getNodeData(node1Itr).getLinkDegree(),
+                   n2Degree = g->getNodeData(node2Itr).getLinkDegree();
+          if (n1Degree > n2Degree) {
+            return true;
+          }
+          else if (n1Degree < n2Degree) {
+            return false;
+          }
+          // else they're "equal" by degree, differentiate based on ID.
+          return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+        }
+
+      private:
+        SolverGraph *g;
+    };
+
+    class SpillPriorityComparator {
+      public:
+        SpillPriorityComparator() : g(0) {}
+        SpillPriorityComparator(SolverGraph *g) : g(g) {}
+
+        bool operator()(const GraphNodeIterator &node1Itr,
+                        const GraphNodeIterator &node2Itr) const {
+          assert((g != 0) && "Graph object not set, cannot access node data.");
+          PBQPNum cost1 =
+            g->getNodeCosts(node1Itr)[0] /
+            g->getNodeData(node1Itr).getLinkDegree(),
+            cost2 =
+              g->getNodeCosts(node2Itr)[0] /
+              g->getNodeData(node2Itr).getLinkDegree();
+
+          if (cost1 < cost2) {
+            return true;
+          }
+          else if (cost1 > cost2) {
+            return false;
+          }
+          // else they'er "equal" again, differentiate based on address again.
+          return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+        }
+
+      private:
+        SolverGraph *g;
+    };
+
+    typedef std::set<GraphNodeIterator, LinkDegreeComparator>
+      RNAllocableNodeList;
+    typedef RNAllocableNodeList::iterator RNAllocableNodeListIterator;
+
+    typedef std::set<GraphNodeIterator, SpillPriorityComparator>
+      RNUnallocableNodeList;
+    typedef RNUnallocableNodeList::iterator RNUnallocableNodeListIterator;
+
+  public:
+
+    class NodeData {
+      private:
+        RNAllocableNodeListIterator rNAllocableNodeListItr;
+        RNUnallocableNodeListIterator rNUnallocableNodeListItr;
+        unsigned numRegOptions, numDenied, numSafe;
+        std::vector<unsigned> unsafeDegrees;
+        bool allocable;
+
+        void addRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
+            const GraphEdgeIterator &edgeItr, bool add) {
+
+          //assume we're adding...
+          unsigned udTarget = 0, dir = 1;
+
+          if (!add) {
+            udTarget = 1;
+            dir = -1;
+          }
+
+          EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData();
+
+          EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd;
+
+          if (nodeItr == g.getEdgeNode1Itr(edgeItr)) {
+            numDenied += (dir * linkEdgeData.getWorstDegree());
+            edgeUnsafeBegin = linkEdgeData.unsafeBegin();
+            edgeUnsafeEnd = linkEdgeData.unsafeEnd();
+          }
+          else {
+            numDenied += (dir * linkEdgeData.getReverseWorstDegree());
+            edgeUnsafeBegin = linkEdgeData.reverseUnsafeBegin();
+            edgeUnsafeEnd = linkEdgeData.reverseUnsafeEnd();
+          }
+
+          assert((unsafeDegrees.size() ==
+                static_cast<unsigned>(
+                  std::distance(edgeUnsafeBegin, edgeUnsafeEnd)))
+              && "Unsafe array size mismatch.");
+
+          std::vector<unsigned>::iterator unsafeDegreesItr =
+            unsafeDegrees.begin();
+
+          for (EdgeData::ConstUnsafeIterator edgeUnsafeItr = edgeUnsafeBegin;
+              edgeUnsafeItr != edgeUnsafeEnd;
+              ++edgeUnsafeItr, ++unsafeDegreesItr) {
+
+            if ((*edgeUnsafeItr == 1) && (*unsafeDegreesItr == udTarget))  {
+              numSafe -= dir;
+            }
+            *unsafeDegreesItr += (dir * (*edgeUnsafeItr));
+          }
+
+          allocable = (numDenied < numRegOptions) || (numSafe > 0);
+        }
+
+      public:
+
+        void setup(SolverGraph &g, const GraphNodeIterator &nodeItr) {
+
+          numRegOptions = g.getNodeCosts(nodeItr).getLength() - 1;
+
+          numSafe = numRegOptions; // Optimistic, correct below.
+          numDenied = 0; // Also optimistic.
+          unsafeDegrees.resize(numRegOptions, 0);
+
+          HSIT::NodeData &nodeData = g.getNodeData(nodeItr);
+
+          for (HSIT::NodeData::AdjLinkIterator
+              adjLinkItr = nodeData.adjLinksBegin(),
+              adjLinkEnd = nodeData.adjLinksEnd();
+              adjLinkItr != adjLinkEnd; ++adjLinkItr) {
+
+            addRemoveLink(g, nodeItr, *adjLinkItr, true);
+          }
+        }
+
+        bool isAllocable() const { return allocable; }
+
+        void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
+            const GraphEdgeIterator &adjEdge) {
+          addRemoveLink(g, nodeItr, adjEdge, true);
+        }
+
+        void handleRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
+            const GraphEdgeIterator &adjEdge) {
+          addRemoveLink(g, nodeItr, adjEdge, false);
+        }
+
+        void setRNAllocableNodeListItr(
+            const RNAllocableNodeListIterator &rNAllocableNodeListItr) {
+
+          this->rNAllocableNodeListItr = rNAllocableNodeListItr;
+        }
+
+        RNAllocableNodeListIterator getRNAllocableNodeListItr() const {
+          return rNAllocableNodeListItr;
+        }
+
+        void setRNUnallocableNodeListItr(
+            const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) {
+
+          this->rNUnallocableNodeListItr = rNUnallocableNodeListItr;
+        }
+
+        RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const {
+          return rNUnallocableNodeListItr;
+        }
+
+
+    };
+
+    class EdgeData {
+      private:
+
+        typedef std::vector<unsigned> UnsafeArray;
+
+        unsigned worstDegree,
+                 reverseWorstDegree;
+        UnsafeArray unsafe, reverseUnsafe;
+
+      public:
+
+        EdgeData() : worstDegree(0), reverseWorstDegree(0) {}
+
+        typedef UnsafeArray::const_iterator ConstUnsafeIterator;
+
+        void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) {
+          const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
+          unsigned numRegs = edgeCosts.getRows() - 1,
+                   numReverseRegs = edgeCosts.getCols() - 1;
+
+          unsafe.resize(numRegs, 0);
+          reverseUnsafe.resize(numReverseRegs, 0);
+
+          std::vector<unsigned> rowInfCounts(numRegs, 0),
+                                colInfCounts(numReverseRegs, 0);
+
+          for (unsigned i = 0; i < numRegs; ++i) {
+            for (unsigned j = 0; j < numReverseRegs; ++j) {
+              if (edgeCosts[i + 1][j + 1] ==
+                  std::numeric_limits<PBQPNum>::infinity()) {
+                unsafe[i] = 1;
+                reverseUnsafe[j] = 1;
+                ++rowInfCounts[i];
+                ++colInfCounts[j];
+
+                if (colInfCounts[j] > worstDegree) {
+                  worstDegree = colInfCounts[j];
+                }
+
+                if (rowInfCounts[i] > reverseWorstDegree) {
+                  reverseWorstDegree = rowInfCounts[i];
+                }
+              }
+            }
+          }
+        }
+
+        unsigned getWorstDegree() const { return worstDegree; }
+        unsigned getReverseWorstDegree() const { return reverseWorstDegree; }
+        ConstUnsafeIterator unsafeBegin() const { return unsafe.begin(); }
+        ConstUnsafeIterator unsafeEnd() const { return unsafe.end(); }
+        ConstUnsafeIterator reverseUnsafeBegin() const {
+          return reverseUnsafe.begin();
+        }
+        ConstUnsafeIterator reverseUnsafeEnd() const {
+          return reverseUnsafe.end();
+        }
+    };
+
+  void initialise(Solver &solver) {
+    this->s = &solver;
+    g = &s->getGraph();
+    rNAllocableBucket = RNAllocableNodeList(LinkDegreeComparator(g));
+    rNUnallocableBucket =
+      RNUnallocableNodeList(SpillPriorityComparator(g));
+    
+    for (GraphEdgeIterator
+         edgeItr = g->edgesBegin(), edgeEnd = g->edgesEnd();
+         edgeItr != edgeEnd; ++edgeItr) {
+
+      g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
+    }
+
+    for (GraphNodeIterator
+         nodeItr = g->nodesBegin(), nodeEnd = g->nodesEnd();
+         nodeItr != nodeEnd; ++nodeItr) {
+
+      g->getNodeData(nodeItr).getHeuristicData().setup(*g, nodeItr);
+    }
+  }
+
+  void addToRNBucket(const GraphNodeIterator &nodeItr) {
+    NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
+
+    if (nodeData.isAllocable()) {
+      nodeData.setRNAllocableNodeListItr(
+        rNAllocableBucket.insert(rNAllocableBucket.begin(), nodeItr));
+    }
+    else {
+      nodeData.setRNUnallocableNodeListItr(
+        rNUnallocableBucket.insert(rNUnallocableBucket.begin(), nodeItr));
+    }
+  }
+
+  void removeFromRNBucket(const GraphNodeIterator &nodeItr) {
+    NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
+
+    if (nodeData.isAllocable()) {
+      rNAllocableBucket.erase(nodeData.getRNAllocableNodeListItr());
+    }
+    else {
+      rNUnallocableBucket.erase(nodeData.getRNUnallocableNodeListItr());
+    }
+  }
+
+  void handleAddLink(const GraphEdgeIterator &edgeItr) {
+    // We assume that if we got here this edge is attached to at least
+    // one high degree node.
+    g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
+
+    GraphNodeIterator n1Itr = g->getEdgeNode1Itr(edgeItr),
+                      n2Itr = g->getEdgeNode2Itr(edgeItr);
+   
+    HSIT::NodeData &n1Data = g->getNodeData(n1Itr),
+                   &n2Data = g->getNodeData(n2Itr);
+
+    if (n1Data.getLinkDegree() > 2) {
+      n1Data.getHeuristicData().handleAddLink(*g, n1Itr, edgeItr);
+    }
+    if (n2Data.getLinkDegree() > 2) {
+      n2Data.getHeuristicData().handleAddLink(*g, n2Itr, edgeItr);
+    }
+  }
+
+  void handleRemoveLink(const GraphEdgeIterator &edgeItr,
+                        const GraphNodeIterator &nodeItr) {
+    NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
+    nodeData.handleRemoveLink(*g, nodeItr, edgeItr);
+  }
+
+  void processRN() {
+
+   /* 
+    std::cerr << "processRN():\n"
+              << "  rNAllocable = [ ";
+    for (RNAllocableNodeListIterator nItr = rNAllocableBucket.begin(),
+                                     nEnd = rNAllocableBucket.end();
+         nItr != nEnd; ++nItr) {
+      std::cerr << g->getNodeID(*nItr) << " (" << g->getNodeData(*nItr).getLinkDegree() << ")    ";
+    }
+    std::cerr << "]\n"
+              << "  rNUnallocable = [ ";
+    for (RNUnallocableNodeListIterator nItr = rNUnallocableBucket.begin(),
+                                       nEnd = rNUnallocableBucket.end();
+         nItr != nEnd; ++nItr) {
+      float bCost = g->getNodeCosts(*nItr)[0] / g->getNodeData(*nItr).getLinkDegree();
+      std::cerr << g->getNodeID(*nItr) << " (" << bCost << ")   ";
+    }
+    std::cerr << "]\n";
+    */
+
+    if (!rNAllocableBucket.empty()) {
+      GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin();
+      //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n";
+      rNAllocableBucket.erase(rNAllocableBucket.begin());
+      s->pushStack(selectedNodeItr);
+      s->unlinkNode(selectedNodeItr);
+    }
+    else {
+      GraphNodeIterator selectedNodeItr = *rNUnallocableBucket.begin();
+      //std::cerr << "RN optimistically pushing " << g->getNodeID(selectedNodeItr) << "\n";
+      rNUnallocableBucket.erase(rNUnallocableBucket.begin());
+      s->pushStack(selectedNodeItr);
+      s->unlinkNode(selectedNodeItr);
+    }
+ 
+  }
+
+  bool rNBucketEmpty() const {
+    return (rNAllocableBucket.empty() && rNUnallocableBucket.empty());
+  }
+
+private:
+
+  Solver *s;
+  SolverGraph *g;
+  RNAllocableNodeList rNAllocableBucket;
+  RNUnallocableNodeList rNUnallocableBucket;
+};
+
+
+
+}
+}
+
+
+#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
diff --git a/lib/CodeGen/PBQP/PBQPMath.h b/lib/CodeGen/PBQP/PBQPMath.h
new file mode 100644
index 0000000..dc184fe
--- /dev/null
+++ b/lib/CodeGen/PBQP/PBQPMath.h
@@ -0,0 +1,279 @@
+#ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H 
+#define LLVM_CODEGEN_PBQP_PBQPMATH_H
+
+#include <cassert>
+#include <algorithm>
+#include <functional>
+
+namespace PBQP {
+
+typedef double PBQPNum;
+
+/// \brief PBQP Vector class.
+class Vector {
+  public:
+
+    /// \brief Construct a PBQP vector of the given size.
+    explicit Vector(unsigned length) :
+      length(length), data(new PBQPNum[length]) {
+      }
+
+    /// \brief Construct a PBQP vector with initializer.
+    Vector(unsigned length, PBQPNum initVal) :
+      length(length), data(new PBQPNum[length]) {
+        std::fill(data, data + length, initVal);
+      }
+
+    /// \brief Copy construct a PBQP vector.
+    Vector(const Vector &v) :
+      length(v.length), data(new PBQPNum[length]) {
+        std::copy(v.data, v.data + length, data);
+      }
+
+    /// \brief Destroy this vector, return its memory.
+    ~Vector() { delete[] data; }
+
+    /// \brief Assignment operator.
+    Vector& operator=(const Vector &v) {
+      delete[] data;
+      length = v.length;
+      data = new PBQPNum[length];
+      std::copy(v.data, v.data + length, data);
+      return *this;
+    }
+
+    /// \brief Return the length of the vector
+    unsigned getLength() const throw () {
+      return length;
+    }
+
+    /// \brief Element access.
+    PBQPNum& operator[](unsigned index) {
+      assert(index < length && "Vector element access out of bounds.");
+      return data[index];
+    }
+
+    /// \brief Const element access.
+    const PBQPNum& operator[](unsigned index) const {
+      assert(index < length && "Vector element access out of bounds.");
+      return data[index];
+    }
+
+    /// \brief Add another vector to this one.
+    Vector& operator+=(const Vector &v) {
+      assert(length == v.length && "Vector length mismatch.");
+      std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 
+      return *this;
+    }
+
+    /// \brief Subtract another vector from this one.
+    Vector& operator-=(const Vector &v) {
+      assert(length == v.length && "Vector length mismatch.");
+      std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 
+      return *this;
+    }
+
+    /// \brief Returns the index of the minimum value in this vector
+    unsigned minIndex() const {
+      return std::min_element(data, data + length) - data;
+    }
+
+  private:
+    unsigned length;
+    PBQPNum *data;
+};
+
+/// \brief Output a textual representation of the given vector on the given
+///        output stream.
+template <typename OStream>
+OStream& operator<<(OStream &os, const Vector &v) {
+  assert((v.getLength() != 0) && "Zero-length vector badness.");
+
+  os << "[ " << v[0];
+  for (unsigned i = 1; i < v.getLength(); ++i) {
+    os << ", " << v[i];
+  }
+  os << " ]";
+
+  return os;
+} 
+
+
+/// \brief PBQP Matrix class
+class Matrix {
+  public:
+
+    /// \brief Construct a PBQP Matrix with the given dimensions.
+    Matrix(unsigned rows, unsigned cols) :
+      rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
+    }
+
+    /// \brief Construct a PBQP Matrix with the given dimensions and initial
+    /// value.
+    Matrix(unsigned rows, unsigned cols, PBQPNum initVal) :
+      rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
+        std::fill(data, data + (rows * cols), initVal);
+    }
+
+    /// \brief Copy construct a PBQP matrix.
+    Matrix(const Matrix &m) :
+      rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
+        std::copy(m.data, m.data + (rows * cols), data);  
+    }
+
+    /// \brief Destroy this matrix, return its memory.
+    ~Matrix() { delete[] data; }
+
+    /// \brief Assignment operator.
+    Matrix& operator=(const Matrix &m) {
+      delete[] data;
+      rows = m.rows; cols = m.cols;
+      data = new PBQPNum[rows * cols];
+      std::copy(m.data, m.data + (rows * cols), data);
+      return *this;
+    }
+
+    /// \brief Return the number of rows in this matrix.
+    unsigned getRows() const throw () { return rows; }
+
+    /// \brief Return the number of cols in this matrix.
+    unsigned getCols() const throw () { return cols; }
+
+    /// \brief Matrix element access.
+    PBQPNum* operator[](unsigned r) {
+      assert(r < rows && "Row out of bounds.");
+      return data + (r * cols);
+    }
+
+    /// \brief Matrix element access.
+    const PBQPNum* operator[](unsigned r) const {
+      assert(r < rows && "Row out of bounds.");
+      return data + (r * cols);
+    }
+
+    /// \brief Returns the given row as a vector.
+    Vector getRowAsVector(unsigned r) const {
+      Vector v(cols);
+      for (unsigned c = 0; c < cols; ++c)
+        v[c] = (*this)[r][c];
+      return v; 
+    }
+
+    /// \brief Returns the given column as a vector.
+    Vector getColAsVector(unsigned c) const {
+      Vector v(rows);
+      for (unsigned r = 0; r < rows; ++r)
+        v[r] = (*this)[r][c];
+      return v;
+    }
+
+    /// \brief Reset the matrix to the given value.
+    Matrix& reset(PBQPNum val = 0) {
+      std::fill(data, data + (rows * cols), val);
+      return *this;
+    }
+
+    /// \brief Set a single row of this matrix to the given value.
+    Matrix& setRow(unsigned r, PBQPNum val) {
+      assert(r < rows && "Row out of bounds.");
+      std::fill(data + (r * cols), data + ((r + 1) * cols), val);
+      return *this;
+    }
+
+    /// \brief Set a single column of this matrix to the given value.
+    Matrix& setCol(unsigned c, PBQPNum val) {
+      assert(c < cols && "Column out of bounds.");
+      for (unsigned r = 0; r < rows; ++r)
+        (*this)[r][c] = val;
+      return *this;
+    }
+
+    /// \brief Matrix transpose.
+    Matrix transpose() const {
+      Matrix m(cols, rows);
+      for (unsigned r = 0; r < rows; ++r)
+        for (unsigned c = 0; c < cols; ++c)
+          m[c][r] = (*this)[r][c];
+      return m;
+    }
+
+    /// \brief Returns the diagonal of the matrix as a vector.
+    ///
+    /// Matrix must be square.
+    Vector diagonalize() const {
+      assert(rows == cols && "Attempt to diagonalize non-square matrix.");
+
+      Vector v(rows);
+      for (unsigned r = 0; r < rows; ++r)
+        v[r] = (*this)[r][r];
+      return v;
+    } 
+
+    /// \brief Add the given matrix to this one.
+    Matrix& operator+=(const Matrix &m) {
+      assert(rows == m.rows && cols == m.cols &&
+          "Matrix dimensions mismatch.");
+      std::transform(data, data + (rows * cols), m.data, data,
+          std::plus<PBQPNum>());
+      return *this;
+    }
+
+    /// \brief Returns the minimum of the given row
+    PBQPNum getRowMin(unsigned r) const {
+      assert(r < rows && "Row out of bounds");
+      return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
+    }
+
+    /// \brief Returns the minimum of the given column
+    PBQPNum getColMin(unsigned c) const {
+      PBQPNum minElem = (*this)[0][c];
+      for (unsigned r = 1; r < rows; ++r)
+        if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
+      return minElem;
+    }
+
+    /// \brief Subtracts the given scalar from the elements of the given row.
+    Matrix& subFromRow(unsigned r, PBQPNum val) {
+      assert(r < rows && "Row out of bounds");
+      std::transform(data + (r * cols), data + ((r + 1) * cols),
+          data + (r * cols),
+          std::bind2nd(std::minus<PBQPNum>(), val));
+      return *this;
+    }
+
+    /// \brief Subtracts the given scalar from the elements of the given column.
+    Matrix& subFromCol(unsigned c, PBQPNum val) {
+      for (unsigned r = 0; r < rows; ++r)
+        (*this)[r][c] -= val;
+      return *this;
+    }
+
+    /// \brief Returns true if this is a zero matrix.
+    bool isZero() const {
+      return find_if(data, data + (rows * cols),
+          std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
+        data + (rows * cols);
+    }
+
+  private:
+    unsigned rows, cols;
+    PBQPNum *data;
+};
+
+/// \brief Output a textual representation of the given matrix on the given
+///        output stream.
+template <typename OStream>
+OStream& operator<<(OStream &os, const Matrix &m) {
+
+  assert((m.getRows() != 0) && "Zero-row matrix badness.");
+
+  for (unsigned i = 0; i < m.getRows(); ++i) {
+    os << m.getRowAsVector(i);
+  }
+
+  return os;
+}
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_PBQPMATH_HPP
diff --git a/lib/CodeGen/PBQP/SimpleGraph.h b/lib/CodeGen/PBQP/SimpleGraph.h
new file mode 100644
index 0000000..595269c
--- /dev/null
+++ b/lib/CodeGen/PBQP/SimpleGraph.h
@@ -0,0 +1,86 @@
+#ifndef LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
+#define LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
+
+#include "GraphBase.h"
+
+namespace PBQP {
+
+class SimpleEdge;
+
+class SimpleNode : public NodeBase<SimpleNode, SimpleEdge> {
+public:
+  SimpleNode(const Vector &costs) :
+    NodeBase<SimpleNode, SimpleEdge>(costs) {}
+};
+
+class SimpleEdge : public EdgeBase<SimpleNode, SimpleEdge> {
+public:
+  SimpleEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+             const Matrix &costs) :
+    EdgeBase<SimpleNode, SimpleEdge>(node1Itr, node2Itr, costs) {}
+};
+
+class SimpleGraph : public GraphBase<SimpleNode, SimpleEdge> {
+private:
+
+  typedef GraphBase<SimpleNode, SimpleEdge> PGraph;
+
+  void copyFrom(const SimpleGraph &other) {
+    assert(other.areNodeIDsValid() &&
+           "Cannot copy from another graph unless IDs have been assigned.");
+   
+    std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
+
+    for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
+         nItr != nEnd; ++nItr) {
+      newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
+    }
+
+    for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
+         eItr != eEnd; ++eItr) {
+
+      unsigned node1ID = other.getNodeID(other.getEdgeNode1Itr(eItr)),
+               node2ID = other.getNodeID(other.getEdgeNode2Itr(eItr));
+
+      addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
+              other.getEdgeCosts(eItr));
+    }
+  }
+
+  void copyFrom(SimpleGraph &other) {
+    if (!other.areNodeIDsValid()) {
+      other.assignNodeIDs();
+    }
+    copyFrom(const_cast<const SimpleGraph&>(other));
+  }
+
+public:
+
+  SimpleGraph() {}
+
+
+  SimpleGraph(const SimpleGraph &other) : PGraph() {
+    copyFrom(other);
+  }
+
+  SimpleGraph& operator=(const SimpleGraph &other) {
+    clear();
+    copyFrom(other);
+    return *this;
+  }
+
+  NodeIterator addNode(const Vector &costs) {
+    return PGraph::addConstructedNode(SimpleNode(costs));
+  }
+
+  EdgeIterator addEdge(const NodeIterator &node1Itr,
+                       const NodeIterator &node2Itr,
+                       const Matrix &costs) {
+    return PGraph::addConstructedEdge(SimpleEdge(node1Itr, node2Itr, costs));
+  }
+
+};
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
diff --git a/lib/CodeGen/PBQP/Solution.h b/lib/CodeGen/PBQP/Solution.h
new file mode 100644
index 0000000..316c9de
--- /dev/null
+++ b/lib/CodeGen/PBQP/Solution.h
@@ -0,0 +1,74 @@
+#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H
+#define LLVM_CODEGEN_PBQP_SOLUTION_H
+
+#include "PBQPMath.h"
+
+namespace PBQP {
+
+class Solution {
+
+  friend class SolverImplementation;
+
+private:
+
+  std::vector<unsigned> selections;
+  PBQPNum solutionCost;
+  bool provedOptimal;
+  unsigned r0Reductions, r1Reductions,
+           r2Reductions, rNReductions;
+
+public:
+
+  Solution() :
+    solutionCost(0.0), provedOptimal(false),
+    r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
+
+  Solution(unsigned length, bool assumeOptimal) :
+    selections(length), solutionCost(0.0), provedOptimal(assumeOptimal),
+    r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
+
+  void setProvedOptimal(bool provedOptimal) {
+    this->provedOptimal = provedOptimal;
+  }
+
+  void setSelection(unsigned nodeID, unsigned selection) {
+    selections[nodeID] = selection;
+  }
+
+  void setSolutionCost(PBQPNum solutionCost) {
+    this->solutionCost = solutionCost;
+  }
+
+  void incR0Reductions() { ++r0Reductions; }
+  void incR1Reductions() { ++r1Reductions; }
+  void incR2Reductions() { ++r2Reductions; }
+  void incRNReductions() { ++rNReductions; }
+
+  unsigned numNodes() const { return selections.size(); }
+
+  unsigned getSelection(unsigned nodeID) const {
+    return selections[nodeID];
+  }
+
+  PBQPNum getCost() const { return solutionCost; }
+
+  bool isProvedOptimal() const { return provedOptimal; }
+
+  unsigned getR0Reductions() const { return r0Reductions; }
+  unsigned getR1Reductions() const { return r1Reductions; }
+  unsigned getR2Reductions() const { return r2Reductions; }
+  unsigned getRNReductions() const { return rNReductions; }
+
+  bool operator==(const Solution &other) const {
+    return (selections == other.selections);
+  }
+
+  bool operator!=(const Solution &other) const {
+    return !(*this == other);
+  }
+
+};
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_SOLUTION_H
diff --git a/lib/CodeGen/PBQP/Solver.h b/lib/CodeGen/PBQP/Solver.h
new file mode 100644
index 0000000..5b6a284
--- /dev/null
+++ b/lib/CodeGen/PBQP/Solver.h
@@ -0,0 +1,21 @@
+#ifndef LLVM_CODEGEN_PBQP_SOLVER_H
+#define LLVM_CODEGEN_PBQP_SOLVER_H
+
+#include "SimpleGraph.h"
+#include "Solution.h"
+
+namespace PBQP {
+
+/// \brief Interface for solver classes.
+class Solver {
+public:
+
+  virtual ~Solver() = 0;
+  virtual Solution solve(const SimpleGraph &orig) const = 0;
+};
+
+Solver::~Solver() {}
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_SOLVER_H
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index 862ce00..63c7d3d 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -31,7 +31,9 @@
 
 #define DEBUG_TYPE "regalloc"
 
-#include "PBQP.h"
+#include "PBQP/HeuristicSolver.h"
+#include "PBQP/SimpleGraph.h"
+#include "PBQP/Heuristics/Briggs.h"
 #include "VirtRegMap.h"
 #include "VirtRegRewriter.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
@@ -54,42 +56,41 @@
 using namespace llvm;
 
 static RegisterRegAlloc
-registerPBQPRepAlloc("pbqp", "PBQP register allocator",
-                     createPBQPRegisterAllocator);
+registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
+                      llvm::createPBQPRegisterAllocator);
 
 namespace {
 
-  //!
-  //! PBQP based allocators solve the register allocation problem by mapping
-  //! register allocation problems to Partitioned Boolean Quadratic
-  //! Programming problems.
+  ///
+  /// PBQP based allocators solve the register allocation problem by mapping
+  /// register allocation problems to Partitioned Boolean Quadratic
+  /// Programming problems.
   class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass {
   public:
 
     static char ID;
-
-    //! Construct a PBQP register allocator.
+    
+    /// Construct a PBQP register allocator.
     PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {}
 
-    //! Return the pass name.
+    /// Return the pass name.
     virtual const char* getPassName() const throw() {
       return "PBQP Register Allocator";
     }
 
-    //! PBQP analysis usage.
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesCFG();
-      AU.addRequired<LiveIntervals>();
-      AU.addRequiredTransitive<RegisterCoalescer>();
-      AU.addRequired<LiveStacks>();
-      AU.addPreserved<LiveStacks>();
-      AU.addRequired<MachineLoopInfo>();
-      AU.addPreserved<MachineLoopInfo>();
-      AU.addRequired<VirtRegMap>();
-      MachineFunctionPass::getAnalysisUsage(AU);
+    /// PBQP analysis usage.
+    virtual void getAnalysisUsage(AnalysisUsage &au) const {
+      au.addRequired<LiveIntervals>();
+      //au.addRequiredID(SplitCriticalEdgesID);
+      au.addRequired<LiveStacks>();
+      au.addPreserved<LiveStacks>();
+      au.addRequired<MachineLoopInfo>();
+      au.addPreserved<MachineLoopInfo>();
+      au.addRequired<VirtRegMap>();
+      MachineFunctionPass::getAnalysisUsage(au);
     }
 
-    //! Perform register allocation
+    /// Perform register allocation
     virtual bool runOnMachineFunction(MachineFunction &MF);
 
   private:
@@ -99,7 +100,7 @@ namespace {
     typedef std::vector<AllowedSet> AllowedSetMap;
     typedef std::set<unsigned> RegSet;
     typedef std::pair<unsigned, unsigned> RegPair;
-    typedef std::map<RegPair, PBQPNum> CoalesceMap;
+    typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
 
     typedef std::set<LiveInterval*> LiveIntervalSet;
 
@@ -121,60 +122,60 @@ namespace {
                     emptyVRegIntervals;
 
 
-    //! Builds a PBQP cost vector.
+    /// Builds a PBQP cost vector.
     template <typename RegContainer>
-    PBQPVector* buildCostVector(unsigned vReg,
-                                const RegContainer &allowed,
-                                const CoalesceMap &cealesces,
-                                PBQPNum spillCost) const;
-
-    //! \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.
+    PBQP::Vector buildCostVector(unsigned vReg,
+                                 const RegContainer &allowed,
+                                 const CoalesceMap &cealesces,
+                                 PBQP::PBQPNum spillCost) const;
+
+    /// \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>
-    PBQPMatrix* buildInterferenceMatrix(const RegContainer &allowed1,
-                                        const RegContainer &allowed2) const;
-
-    //!
-    //! 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.
+    PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
+                                          const RegContainer &allowed2) const;
+
+    ///
+    /// 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>
-    PBQPMatrix* buildCoalescingMatrix(const RegContainer &allowed1,
-                                      const RegContainer &allowed2,
-                                      PBQPNum cBenefit) const;
-
-    //! \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.
+    PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
+                                        const RegContainer &allowed2,
+                                        PBQP::PBQPNum cBenefit) const;
+
+    /// \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();
 
-    //! \brief Finds the initial set of vreg intervals to allocate.
+    /// \brief Finds the initial set of vreg intervals to allocate.
     void findVRegIntervalsToAlloc();
 
-    //! \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* constructPBQPProblem();
+    /// \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::SimpleGraph constructPBQPProblem();
 
-    //! \brief Adds a stack interval if the given live interval has been
-    //! spilled. Used to support stack slot coloring.
+    /// \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);
 
-    //! \brief Given a solved PBQP problem maps this solution back to a register
-    //! assignment.
-    bool mapPBQPToRegAlloc(pbqp *problem);
+    /// \brief Given a solved PBQP problem maps this solution back to a register
+    /// assignment.
+    bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
 
-    //! \brief Postprocessing before final spilling. Sets basic block "live in"
-    //! variables.
+    /// \brief Postprocessing before final spilling. Sets basic block "live in"
+    /// variables.
     void finalizeAlloc() const;
 
   };
@@ -184,17 +185,17 @@ namespace {
 
 
 template <typename RegContainer>
-PBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg,
-                                          const RegContainer &allowed,
-                                          const CoalesceMap &coalesces,
-                                          PBQPNum spillCost) const {
+PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg,
+                                           const RegContainer &allowed,
+                                           const CoalesceMap &coalesces,
+                                           PBQP::PBQPNum spillCost) const {
 
   typedef typename RegContainer::const_iterator AllowedItr;
 
   // Allocate vector. Additional element (0th) used for spill option
-  PBQPVector *v = new PBQPVector(allowed.size() + 1);
+  PBQP::Vector v(allowed.size() + 1, 0);
 
-  (*v)[0] = spillCost;
+  v[0] = spillCost;
 
   // Iterate over the allowed registers inserting coalesce benefits if there
   // are any.
@@ -212,14 +213,14 @@ PBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg,
       continue;
 
     // We have a coalesce - insert the benefit.
-    (*v)[ai + 1] = -cmItr->second;
+    v[ai + 1] = -cmItr->second;
   }
 
   return v;
 }
 
 template <typename RegContainer>
-PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
+PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix(
       const RegContainer &allowed1, const RegContainer &allowed2) const {
 
   typedef typename RegContainer::const_iterator RegContainerIterator;
@@ -232,7 +233,8 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
   // that the spill option (element 0,0) has zero cost, since we can allocate
   // both intervals to memory safely (the cost for each individual allocation
   // to memory is accounted for by the cost vectors for each live interval).
-  PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1);
+  PBQP::Matrix *m =
+    new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
 
   // Assume this is a zero matrix until proven otherwise.  Zero matrices occur
   // between interfering live ranges with non-overlapping register sets (e.g.
@@ -262,7 +264,7 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
 
       // If the row/column regs are identical or alias insert an infinity.
       if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) {
-        (*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity();
+        (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity();
         isZeroMatrix = false;
       }
 
@@ -284,9 +286,9 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
 }
 
 template <typename RegContainer>
-PBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix(
+PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix(
       const RegContainer &allowed1, const RegContainer &allowed2,
-      PBQPNum cBenefit) const {
+      PBQP::PBQPNum cBenefit) const {
 
   typedef typename RegContainer::const_iterator RegContainerIterator;
 
@@ -295,7 +297,8 @@ PBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix(
   // for the LiveIntervals which are (potentially) to be coalesced. The amount
   // -cBenefit will be placed in any element representing the same register
   // for both intervals.
-  PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1);
+  PBQP::Matrix *m =
+    new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
 
   // Reset costs to zero.
   m->reset(0);
@@ -497,10 +500,11 @@ void PBQPRegAlloc::findVRegIntervalsToAlloc() {
   }
 }
 
-pbqp* PBQPRegAlloc::constructPBQPProblem() {
+PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
 
   typedef std::vector<const LiveInterval*> LIVector;
   typedef std::vector<unsigned> RegVector;
+  typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector;
 
   // This will store the physical intervals for easy reference.
   LIVector physIntervals;
@@ -532,10 +536,11 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() {
   }
 
   // Get the set of potential coalesces.
-  CoalesceMap coalesces(findCoalesces());
+  CoalesceMap coalesces;//(findCoalesces());
 
   // Construct a PBQP solver for this problem
-  pbqp *solver = alloc_pbqp(vregIntervalsToAlloc.size());
+  PBQP::SimpleGraph problem;
+  NodeVector problemNodes(vregIntervalsToAlloc.size());
 
   // Resize allowedSets container appropriately.
   allowedSets.resize(vregIntervalsToAlloc.size());
@@ -596,13 +601,13 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() {
 
     // Set the spill cost to the interval weight, or epsilon if the
     // interval weight is zero
-    PBQPNum spillCost = (li->weight != 0.0) ?
-        li->weight : std::numeric_limits<PBQPNum>::min();
+    PBQP::PBQPNum spillCost = (li->weight != 0.0) ?
+        li->weight : std::numeric_limits<PBQP::PBQPNum>::min();
 
     // Build a cost vector for this interval.
-    add_pbqp_nodecosts(solver, node,
-                       buildCostVector(li->reg, allowedSets[node], coalesces,
-                                       spillCost));
+    problemNodes[node] =
+      problem.addNode(
+        buildCostVector(li->reg, allowedSets[node], coalesces, spillCost));
 
   }
 
@@ -618,7 +623,7 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() {
       CoalesceMap::const_iterator cmItr =
         coalesces.find(RegPair(li->reg, li2->reg));
 
-      PBQPMatrix *m = 0;
+      PBQP::Matrix *m = 0;
 
       if (cmItr != coalesces.end()) {
         m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
@@ -629,14 +634,29 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() {
       }
 
       if (m != 0) {
-        add_pbqp_edgecosts(solver, node1, node2, m);
+        problem.addEdge(problemNodes[node1],
+                        problemNodes[node2],
+                        *m);
+
         delete m;
       }
     }
   }
 
+  problem.assignNodeIDs();
+
+  assert(problem.getNumNodes() == allowedSets.size());
+  for (unsigned i = 0; i < allowedSets.size(); ++i) {
+    assert(problem.getNodeItr(i) == problemNodes[i]);
+  }
+/*
+  std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
+            << problem.getNumEdges() << " edges.\n";
+
+  problem.printDot(std::cerr);
+*/
   // We're done, PBQP problem constructed - return it.
-  return solver;
+  return problem;
 }
 
 void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
@@ -659,7 +679,9 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
   stackInterval.MergeRangesInAsValue(rhsInterval, vni);
 }
 
-bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) {
+bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
+
+  static unsigned round = 0;
 
   // Set to true if we have any spills
   bool anotherRoundNeeded = false;
@@ -667,10 +689,56 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) {
   // Clear the existing allocation.
   vrm->clearAllVirt();
 
+  CoalesceMap coalesces;//(findCoalesces());
+
+  for (unsigned i = 0; i < node2LI.size(); ++i) {
+    if (solution.getSelection(i) == 0) {
+      continue;
+    }
+
+    unsigned iSel = solution.getSelection(i);
+    unsigned iAlloc = allowedSets[i][iSel - 1];
+
+    for (unsigned j = i + 1; j < node2LI.size(); ++j) {
+
+      if (solution.getSelection(j) == 0) {
+        continue;
+      }
+
+      unsigned jSel = solution.getSelection(j);
+      unsigned jAlloc = allowedSets[j][jSel - 1];
+       
+      if ((iAlloc != jAlloc) && !tri->areAliases(iAlloc, jAlloc)) {
+        continue;
+      }
+
+      if (node2LI[i]->overlaps(*node2LI[j])) {
+        if (coalesces.find(RegPair(node2LI[i]->reg, node2LI[j]->reg)) == coalesces.end()) {
+          DEBUG(errs() <<  "In round " << ++round << ":\n"
+               << "Bogusness in " << mf->getFunction()->getName() << "!\n"
+               << "Live interval " << i << " (reg" << node2LI[i]->reg << ") and\n"
+               << "Live interval " << j << " (reg" << node2LI[j]->reg << ")\n"
+               << "  were allocated registers " << iAlloc << " (index " << iSel << ") and "
+               << jAlloc << "(index " << jSel 
+               << ") respectively in a graph of " << solution.numNodes() << " nodes.\n"
+               << "li[i]->empty() = " << node2LI[i]->empty() << "\n"
+               << "li[j]->empty() = " << node2LI[j]->empty() << "\n"
+               << "li[i]->overlaps(li[j]) = " << node2LI[i]->overlaps(*node2LI[j]) << "\n"
+                << "coalesce = " << (coalesces.find(RegPair(node2LI[i]->reg, node2LI[j]->reg)) != coalesces.end()) << "\n");
+             
+          DEBUG(errs() << "solution.getCost() = " << solution.getCost() << "\n");
+          exit(1);
+        }
+      }
+    }
+  }
+
+
   // Iterate over the nodes mapping the PBQP solution to a register assignment.
   for (unsigned node = 0; node < node2LI.size(); ++node) {
     unsigned virtReg = node2LI[node]->reg,
-             allocSelection = get_pbqp_solution(problem, node);
+             allocSelection = solution.getSelection(node);
+
 
     // If the PBQP solution is non-zero it's a physical register...
     if (allocSelection != 0) {
@@ -731,11 +799,12 @@ void PBQPRegAlloc::finalizeAlloc() const {
 
   // First allocate registers for the empty intervals.
   for (LiveIntervalSet::const_iterator
-         itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
+	 itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
          itr != end; ++itr) {
     LiveInterval *li = *itr;
 
     unsigned physReg = vrm->getRegAllocPref(li->reg);
+
     if (physReg == 0) {
       const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
       physReg = *liRC->allocation_order_begin(*mf);
@@ -766,8 +835,8 @@ void PBQPRegAlloc::finalizeAlloc() const {
       continue;
     }
 
-    // Ignore unallocated vregs:
     if (reg == 0) {
+      // Filter out zero regs - they're for intervals that were spilled.
       continue;
     }
 
@@ -806,8 +875,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
 
   vrm = &getAnalysis<VirtRegMap>();
 
-  DEBUG(errs() << "PBQP Register Allocating for " 
-        << mf->getFunction()->getName() << "\n");
+  DEBUG(errs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n");
 
   // Allocator main loop:
   //
@@ -832,15 +900,19 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
     unsigned round = 0;
 
     while (!pbqpAllocComplete) {
-      DOUT << "  PBQP Regalloc round " << round << ":\n";
-
-      pbqp *problem = constructPBQPProblem();
-
-      solve_pbqp(problem);
-
-      pbqpAllocComplete = mapPBQPToRegAlloc(problem);
-
-      free_pbqp(problem);
+      DEBUG(errs() << "  PBQP Regalloc round " << round << ":\n");
+
+      PBQP::SimpleGraph problem = constructPBQPProblem();
+      PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver;
+      problem.assignNodeIDs();
+      PBQP::Solution solution = solver.solve(problem);
+/*
+      std::cerr << "Solution:\n";
+      for (unsigned i = 0; i < solution.numNodes(); ++i) {
+        std::cerr << "  " << i << " -> " << solution.getSelection(i) << "\n";
+      }
+*/
+      pbqpAllocComplete = mapPBQPToRegAlloc(solution);
 
       ++round;
     }
@@ -855,7 +927,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
   node2LI.clear();
   allowedSets.clear();
 
-  DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n";
+  DEBUG(errs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
 
   // Run rewriter
   std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());