A Partitioned Boolean Quadratic Programming (PBQP) based register allocator.

Contributed by Lang Hames.


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

3 files changed, 2208 insertions, 0 deletions

diff --git a/lib/CodeGen/PBQP.cpp b/lib/CodeGen/PBQP.cpp
new file mode 100644
index 0000000..ade9e7c
--- /dev/null
+++ b/lib/CodeGen/PBQP.cpp
@@ -0,0 +1,1395 @@
+//===---------------- 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 Univesity of Sydney
+//                         http://www.it.usyd.edu.au/~scholz
+//===----------------------------------------------------------------------===//
+
+
+#include <limits>
+#include <cassert>
+
+#include "PBQP.h"
+
+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
new file mode 100644
index 0000000..e31ccc4
--- /dev/null
+++ b/lib/CodeGen/PBQP.h
@@ -0,0 +1,284 @@
+//===---------------- 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 Univesity 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/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
new file mode 100644
index 0000000..ee82f63
--- /dev/null
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -0,0 +1,529 @@
+//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// 
+// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
+// register allocator for LLVM. This allocator works by constructing a PBQP
+// problem representing the register allocation problem under consideration,
+// solving this using a PBQP solver, and mapping the solution back to a
+// register assignment. If any variables are selected for spilling then spill
+// code is inserted and the process repeated. 
+//
+// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
+// for register allocation. For more information on PBQP for register
+// allocation see the following papers: 
+//
+//   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
+//   PBQP. In Proceedings of the 7th Joint Modular Languages Conference
+//   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
+//
+//   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
+//   architectures. In Proceedings of the Joint Conference on Languages,
+//   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
+//   NY, USA, 139-148.
+// 
+// Author: Lang Hames
+// Email: lhames@gmail.com
+//
+//===----------------------------------------------------------------------===//
+
+// TODO:
+// 
+// * Use of std::set in constructPBQPProblem destroys allocation order preference.
+// Switch to an order preserving container.
+// 
+// * Coalescing support.
+
+#define DEBUG_TYPE "regalloc"
+
+#include "PBQP.h"
+#include "VirtRegMap.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Support/Debug.h"
+#include <memory>
+#include <map>
+#include <set>
+#include <vector>
+#include <limits>
+
+using namespace llvm;
+
+static RegisterRegAlloc
+registerPBQPRepAlloc("pbqp", "  PBQP register allocator",
+                     createPBQPRegisterAllocator);
+
+
+namespace {
+
+  //!
+  //! 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.
+    PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {}
+
+    //! Return the pass name.
+    virtual const char* getPassName() const throw() {
+      return "PBQP Register Allocator";
+    }
+
+    //! PBQP analysis usage.
+    virtual void getAnalysisUsage(AnalysisUsage &au) const {
+      au.addRequired<LiveIntervals>();
+      au.addRequired<MachineLoopInfo>();
+      MachineFunctionPass::getAnalysisUsage(au);
+    }
+
+    //! Perform register allocation
+    virtual bool runOnMachineFunction(MachineFunction &MF);
+
+  private:
+    typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
+    typedef std::vector<const LiveInterval*> Node2LIMap;
+    typedef std::vector<unsigned> AllowedSet;
+    typedef std::vector<AllowedSet> AllowedSetMap;
+    typedef std::set<unsigned> IgnoreSet;
+
+    MachineFunction *mf;
+    const TargetMachine *tm;
+    const TargetRegisterInfo *tri;
+    const TargetInstrInfo *tii;
+    const MachineLoopInfo *loopInfo;
+    MachineRegisterInfo *mri;
+
+    LiveIntervals *li;
+    VirtRegMap *vrm;
+
+    LI2NodeMap li2Node;
+    Node2LIMap node2LI;
+    AllowedSetMap allowedSets;
+    IgnoreSet ignoreSet;
+
+    //! Builds a PBQP cost vector.
+    template <typename Container>
+    PBQPVector* buildCostVector(const Container &allowed,
+                                PBQPNum spillCost) const;
+
+    //! \brief Builds a PBQP interfernce 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 Container>
+    PBQPMatrix* buildInterferenceMatrix(const Container &allowed1,
+                                        const Container &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 Container>
+    PBQPMatrix* buildCoalescingMatrix(const Container &allowed1,
+                                      const Container &allowed2,
+                                      PBQPNum cBenefit) const;
+
+    //! \brief Helper functior for constructInitialPBQPProblem().
+    //!
+    //! This function iterates over the Function we are about to allocate for
+    //! and computes spill costs.
+    void calcSpillCosts();
+
+    //! \brief Scans the MachineFunction being allocated to find coalescing
+    //  opportunities.
+    void findCoalescingOpportunities();
+
+    //! \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 Given a solved PBQP problem maps this solution back to a register
+    //! assignment.
+    bool mapPBQPToRegAlloc(pbqp *problem); 
+
+  };
+
+  char PBQPRegAlloc::ID = 0;
+}
+
+
+template <typename Container>
+PBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed,
+                                          PBQPNum spillCost) const {
+
+  // Allocate vector. Additional element (0th) used for spill option
+  PBQPVector *v = new PBQPVector(allowed.size() + 1);
+
+  (*v)[0] = spillCost;
+
+  return v;
+}
+
+template <typename Container>
+PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
+      const Container &allowed1, const Container &allowed2) const {
+
+  typedef typename Container::const_iterator ContainerIterator;
+
+  // Construct a PBQP matrix representing the cost of allocation options. The
+  // rows and columns correspond to the allocation options for the two live
+  // intervals.  Elements will be infinite where corresponding registers alias,
+  // since we cannot allocate aliasing registers to interfering live intervals.
+  // All other elements (non-aliasing combinations) will have zero cost. Note
+  // 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);
+ 
+  // Assume this is a zero matrix until proven otherwise.  Zero matrices occur
+  // between interfering live ranges with non-overlapping register sets (e.g.
+  // non-overlapping reg classes, or disjoint sets of allowed regs within the
+  // same class). The term "overlapping" is used advisedly: sets which do not
+  // intersect, but contain registers which alias, will have non-zero matrices.
+  // We optimize zero matrices away to improve solver speed.
+  bool isZeroMatrix = true;
+
+
+  // Row index. Starts at 1, since the 0th row is for the spill option, which
+  // is always zero.
+  unsigned ri = 1; 
+
+  // Iterate over allowed sets, insert infinities where required. 
+  for (ContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
+       a1Itr != a1End; ++a1Itr) {
+
+    // Column index, starts at 1 as for row index.
+    unsigned ci = 1;
+    unsigned reg1 = *a1Itr;
+
+    for (ContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
+         a2Itr != a2End; ++a2Itr) {
+
+      unsigned reg2 = *a2Itr;
+
+      // 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();
+        isZeroMatrix = false;
+      }
+
+      ++ci;
+    }
+
+    ++ri;
+  }
+
+  // If this turns out to be a zero matrix...
+  if (isZeroMatrix) {
+    // free it and return null.
+    delete m;
+    return 0;
+  }
+
+  // ...otherwise return the cost matrix.
+  return m;
+}
+
+void PBQPRegAlloc::calcSpillCosts() {
+
+  // Calculate the spill cost for each live interval by iterating over the
+  // function counting loads and stores, with loop depth taken into account.
+  for (MachineFunction::const_iterator bbItr = mf->begin(), bbEnd = mf->end();
+       bbItr != bbEnd; ++bbItr) {
+
+    const MachineBasicBlock *mbb = &*bbItr;
+    float loopDepth = loopInfo->getLoopDepth(mbb);
+
+    for (MachineBasicBlock::const_iterator
+         iItr = mbb->begin(), iEnd = mbb->end(); iItr != iEnd; ++iItr) {
+
+      const MachineInstr *instr = &*iItr;
+
+      for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) {
+
+        const MachineOperand &mo = instr->getOperand(opNo);
+
+        // We're not interested in non-registers...
+        if (!mo.isRegister())
+          continue;
+ 
+        unsigned moReg = mo.getReg();
+
+        // ...Or invalid registers...
+        if (moReg == 0)
+          continue;
+
+        // ...Or physical registers...
+        if (TargetRegisterInfo::isPhysicalRegister(moReg)) 
+          continue;
+
+        assert ((mo.isUse() || mo.isDef()) &&
+                "Not a use, not a def, what is it?");
+
+	//... Just the virtual registers. We treat loads and stores as equal.
+	li->getInterval(moReg).weight += powf(10.0f, loopDepth);
+      }
+
+    }
+
+  }
+
+}
+
+pbqp* PBQPRegAlloc::constructPBQPProblem() {
+
+  typedef std::vector<const LiveInterval*> LIVector;
+  typedef std::set<unsigned> RegSet;
+
+  // These will store the physical & virtual intervals, respectively.
+  LIVector physIntervals, virtIntervals;
+
+  // Start by clearing the old node <-> live interval mappings & allowed sets
+  li2Node.clear();
+  node2LI.clear();
+  allowedSets.clear();
+
+  // Iterate over intervals classifying them as physical or virtual, and
+  // constructing live interval <-> node number mappings.
+  for (LiveIntervals::iterator itr = li->begin(), end = li->end();
+       itr != end; ++itr) {
+
+    if (itr->second->getNumValNums() != 0) {
+      DOUT << "Live range has " << itr->second->getNumValNums() << ": " << itr->second << "\n";
+    }
+
+    if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
+      physIntervals.push_back(itr->second);
+      mri->setPhysRegUsed(itr->second->reg);
+    }
+    else {
+
+      // If we've allocated this virtual register interval a stack slot on a
+      // previous round then it's not an allocation candidate
+      if (ignoreSet.find(itr->first) != ignoreSet.end())
+        continue;
+
+      li2Node[itr->second] = node2LI.size();
+      node2LI.push_back(itr->second);
+      virtIntervals.push_back(itr->second);
+    }
+  }
+
+  // Early out if there's no regs to allocate for.
+  if (virtIntervals.empty())
+    return 0;
+
+  // Construct a PBQP solver for this problem
+  pbqp *solver = alloc_pbqp(virtIntervals.size());
+
+  // Resize allowedSets container appropriately.
+  allowedSets.resize(virtIntervals.size());
+
+  // Iterate over virtual register intervals to compute allowed sets...
+  for (unsigned node = 0; node < node2LI.size(); ++node) {
+
+    // Grab pointers to the interval and its register class.
+    const LiveInterval *li = node2LI[node];
+    const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
+    
+    // Start by assuming all allocable registers in the class are allowed...
+    RegSet liAllowed(liRC->allocation_order_begin(*mf),
+                     liRC->allocation_order_end(*mf));
+
+    // If this range is non-empty then eliminate the physical registers which
+    // overlap with this range, along with all their aliases.
+    if (!li->empty()) {
+      for (LIVector::iterator pItr = physIntervals.begin(),
+           pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
+
+        if (li->overlaps(**pItr)) {
+
+          unsigned pReg = (*pItr)->reg;
+
+          // Remove the overlapping reg...
+          liAllowed.erase(pReg);
+
+          const unsigned *aliasItr = tri->getAliasSet(pReg);
+
+          if (aliasItr != 0) {
+            // ...and its aliases.
+            for (; *aliasItr != 0; ++aliasItr) {
+              liAllowed.erase(*aliasItr);
+            }
+
+          }
+        
+        }
+
+      }
+
+    }
+
+    // Copy the allowed set into a member vector for use when constructing cost
+    // vectors & matrices, and mapping PBQP solutions back to assignments.
+    allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
+
+    // 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();
+
+    // Build a cost vector for this interval.
+    add_pbqp_nodecosts(solver, node,
+                       buildCostVector(allowedSets[node], spillCost));
+
+  }
+
+  // Now add the cost matrices...
+  for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
+      
+    const LiveInterval *li = node2LI[node1];
+
+    if (li->empty())
+      continue;
+ 
+    // Test for live range overlaps and insert interference matrices.
+    for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
+      const LiveInterval *li2 = node2LI[node2];
+
+      if (li2->empty())
+        continue;
+
+      if (li->overlaps(*li2)) {
+        PBQPMatrix *m =
+          buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
+
+        if (m != 0) {
+          add_pbqp_edgecosts(solver, node1, node2, m);
+          delete m;
+        }
+      }
+    }
+  }
+
+  // We're done, PBQP problem constructed - return it.
+  return solver; 
+}
+
+bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) {
+  
+  // Set to true if we have any spills
+  bool anotherRoundNeeded = false;
+
+  // Clear the existing allocation.
+  vrm->clearAllVirt();
+  
+  // Iterate over the nodes mapping the PBQP solution to a register assignment.
+  for (unsigned node = 0; node < node2LI.size(); ++node) {
+    unsigned symReg = node2LI[node]->reg,
+             allocSelection = get_pbqp_solution(problem, node);
+
+    // If the PBQP solution is non-zero it's a physical register...
+    if (allocSelection != 0) {
+      // Get the physical reg, subtracting 1 to account for the spill option.
+      unsigned physReg = allowedSets[node][allocSelection - 1];
+
+      // Add to the virt reg map and update the used phys regs.
+      vrm->assignVirt2Phys(symReg, physReg);
+      mri->setPhysRegUsed(physReg);
+    }
+    // ...Otherwise it's a spill.
+    else {
+
+      // Make sure we ignore this virtual reg on the next round
+      // of allocation
+      ignoreSet.insert(node2LI[node]->reg);
+
+      float SSWeight;
+
+      // Insert spill ranges for this live range
+      SmallVector<LiveInterval*, 8> spillIs;
+      std::vector<LiveInterval*> newSpills =
+        li->addIntervalsForSpills(*node2LI[node], spillIs, loopInfo, *vrm,
+                                  SSWeight);
+
+      // We need another round if spill intervals were added.
+      anotherRoundNeeded |= !newSpills.empty();
+    }
+  }
+
+  return !anotherRoundNeeded;
+}
+
+bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
+  
+  mf = &MF;
+  tm = &mf->getTarget();
+  tri = tm->getRegisterInfo();
+  mri = &mf->getRegInfo();
+
+  li = &getAnalysis<LiveIntervals>();
+  loopInfo = &getAnalysis<MachineLoopInfo>();
+
+  std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf));
+  vrm = vrmAutoPtr.get();
+
+  // Allocator main loop:
+  // 
+  // * Map current regalloc problem to a PBQP problem
+  // * Solve the PBQP problem
+  // * Map the solution back to a register allocation
+  // * Spill if necessary
+  // 
+  // This process is continued till no more spills are generated.
+
+  bool regallocComplete = false;
+  
+  // Calculate spill costs for intervals
+  calcSpillCosts();
+
+  while (!regallocComplete) {
+    pbqp *problem = constructPBQPProblem();
+   
+    // Fast out if there's no problem to solve.
+    if (problem == 0)
+      return true;
+ 
+    solve_pbqp(problem);
+   
+    regallocComplete = mapPBQPToRegAlloc(problem);
+
+    free_pbqp(problem); 
+  }
+
+  ignoreSet.clear();
+
+  std::auto_ptr<Spiller> spiller(createSpiller());
+
+  spiller->runOnMachineFunction(*mf, *vrm);
+    
+  return true; 
+}
+
+FunctionPass* llvm::createPBQPRegisterAllocator() {
+  return new PBQPRegAlloc();
+}
+
+
+#undef DEBUG_TYPE