diff options
author | Evan Cheng <evan.cheng@apple.com> | 2008-10-02 18:29:27 +0000 |
---|---|---|
committer | Evan Cheng <evan.cheng@apple.com> | 2008-10-02 18:29:27 +0000 |
commit | b1290a6cc40f7caa0351450ce7021a0d48b5f2c0 (patch) | |
tree | f85f3dbefa75c38e754239c3c69b962202759e76 /lib/CodeGen | |
parent | 208ca6aa14e42057069cd779bb1ca53170a38713 (diff) | |
download | external_llvm-b1290a6cc40f7caa0351450ce7021a0d48b5f2c0.zip external_llvm-b1290a6cc40f7caa0351450ce7021a0d48b5f2c0.tar.gz external_llvm-b1290a6cc40f7caa0351450ce7021a0d48b5f2c0.tar.bz2 |
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
Diffstat (limited to 'lib/CodeGen')
-rw-r--r-- | lib/CodeGen/PBQP.cpp | 1395 | ||||
-rw-r--r-- | lib/CodeGen/PBQP.h | 284 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocPBQP.cpp | 529 |
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 |