diff options
Diffstat (limited to 'lib/CodeGen')
| -rw-r--r-- | lib/CodeGen/LazyLiveness.cpp | 167 | ||||
| -rw-r--r-- | lib/CodeGen/PBQP.cpp | 1395 | ||||
| -rw-r--r-- | lib/CodeGen/PBQP.h | 284 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBigBlock.cpp | 892 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocSimple.cpp | 257 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp | 671 |
6 files changed, 0 insertions, 3666 deletions
diff --git a/lib/CodeGen/LazyLiveness.cpp b/lib/CodeGen/LazyLiveness.cpp deleted file mode 100644 index a951c99..0000000 --- a/lib/CodeGen/LazyLiveness.cpp +++ /dev/null @@ -1,167 +0,0 @@ -//===- LazyLiveness.cpp - Lazy, CFG-invariant liveness information --------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass implements a lazy liveness analysis as per "Fast Liveness Checking -// for SSA-form Programs," by Boissinot, et al. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "lazyliveness" -#include "llvm/CodeGen/LazyLiveness.h" -#include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/PostOrderIterator.h" -using namespace llvm; - -char LazyLiveness::ID = 0; -static RegisterPass<LazyLiveness> X("lazy-liveness", "Lazy Liveness Analysis"); - -void LazyLiveness::computeBackedgeChain(MachineFunction& mf, - MachineBasicBlock* MBB) { - SparseBitVector<128> tmp = rv[MBB]; - tmp.set(preorder[MBB]); - tmp &= backedge_source; - calculated.set(preorder[MBB]); - - for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) { - assert(rev_preorder.size() > *I && "Unknown block!"); - - MachineBasicBlock* SrcMBB = rev_preorder[*I]; - - for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin(), - SE = SrcMBB->succ_end(); SI != SE; ++SI) { - MachineBasicBlock* TgtMBB = *SI; - - if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) && - !rv[MBB].test(preorder[TgtMBB])) { - if (!calculated.test(preorder[TgtMBB])) - computeBackedgeChain(mf, TgtMBB); - - tv[MBB].set(preorder[TgtMBB]); - SparseBitVector<128> right = tv[TgtMBB]; - tv[MBB] |= right; - } - } - - tv[MBB].reset(preorder[MBB]); - } -} - -bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) { - rv.clear(); - tv.clear(); - backedges.clear(); - backedge_source.clear(); - backedge_target.clear(); - calculated.clear(); - preorder.clear(); - rev_preorder.clear(); - - rv.resize(mf.size()); - tv.resize(mf.size()); - preorder.resize(mf.size()); - rev_preorder.reserve(mf.size()); - - MRI = &mf.getRegInfo(); - MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); - - // Step 0: Compute preorder numbering for all MBBs. - unsigned num = 0; - for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT.getRootNode()), - DE = df_end(MDT.getRootNode()); DI != DE; ++DI) { - preorder[(*DI)->getBlock()] = num++; - rev_preorder.push_back((*DI)->getBlock()); - } - - // Step 1: Compute the transitive closure of the CFG, ignoring backedges. - for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), - POE = po_end(&*mf.begin()); POI != POE; ++POI) { - MachineBasicBlock* MBB = *POI; - SparseBitVector<128>& entry = rv[MBB]; - entry.set(preorder[MBB]); - - for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); SI != SE; ++SI) { - DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII = - rv.find(*SI); - - // Because we're iterating in postorder, any successor that does not yet - // have an rv entry must be on a backedge. - if (SII != rv.end()) { - entry |= SII->second; - } else { - backedges.insert(std::make_pair(MBB, *SI)); - backedge_source.set(preorder[MBB]); - backedge_target.set(preorder[*SI]); - } - } - } - - for (SparseBitVector<128>::iterator I = backedge_source.begin(); - I != backedge_source.end(); ++I) - computeBackedgeChain(mf, rev_preorder[*I]); - - for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), - POE = po_end(&*mf.begin()); POI != POE; ++POI) - if (!backedge_target.test(preorder[*POI])) - for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(), - SE = (*POI)->succ_end(); SI != SE; ++SI) - if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) { - SparseBitVector<128> right = tv[*SI]; - tv[*POI] |= right; - } - - for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), - POE = po_end(&*mf.begin()); POI != POE; ++POI) - tv[*POI].set(preorder[*POI]); - - return false; -} - -bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) { - MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); - - MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent(); - unsigned def = preorder[DefMBB]; - unsigned max_dom = 0; - for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]), - DE = df_end(MDT[DefMBB]); DI != DE; ++DI) { - if (preorder[DI->getBlock()] > max_dom) { - max_dom = preorder[(*DI)->getBlock()]; - } - } - - if (preorder[MBB] <= def || max_dom < preorder[MBB]) - return false; - - SparseBitVector<128>::iterator I = tv[MBB].begin(); - while (I != tv[MBB].end() && *I <= def) ++I; - while (I != tv[MBB].end() && *I < max_dom) { - for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg), - UE = MachineRegisterInfo::use_end(); UI != UE; ++UI) { - MachineBasicBlock* UseMBB = UI->getParent(); - if (rv[rev_preorder[*I]].test(preorder[UseMBB])) - return true; - - unsigned t_dom = 0; - for (df_iterator<MachineDomTreeNode*> DI = - df_begin(MDT[rev_preorder[*I]]), DE = df_end(MDT[rev_preorder[*I]]); - DI != DE; ++DI) - if (preorder[DI->getBlock()] > t_dom) { - max_dom = preorder[(*DI)->getBlock()]; - } - I = tv[MBB].begin(); - while (I != tv[MBB].end() && *I < t_dom) ++I; - } - } - - return false; -} diff --git a/lib/CodeGen/PBQP.cpp b/lib/CodeGen/PBQP.cpp deleted file mode 100644 index 562300f..0000000 --- a/lib/CodeGen/PBQP.cpp +++ /dev/null @@ -1,1395 +0,0 @@ -//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Developed by: Bernhard Scholz -// The University of Sydney -// http://www.it.usyd.edu.au/~scholz -//===----------------------------------------------------------------------===// - -#include "PBQP.h" -#include "llvm/Config/alloca.h" -#include <limits> -#include <cassert> -#include <cstring> - -namespace llvm { - -/************************************************************************** - * Data Structures - **************************************************************************/ - -/* edge of PBQP graph */ -typedef struct adjnode { - struct adjnode *prev, /* doubly chained list */ - *succ, - *reverse; /* reverse edge */ - int adj; /* adj. node */ - PBQPMatrix *costs; /* cost matrix of edge */ - - bool tc_valid; /* flag whether following fields are valid */ - int *tc_safe_regs; /* safe registers */ - int tc_impact; /* impact */ -} adjnode; - -/* bucket node */ -typedef struct bucketnode { - struct bucketnode *prev; /* doubly chained list */ - struct bucketnode *succ; - int u; /* node */ -} bucketnode; - -/* data structure of partitioned boolean quadratic problem */ -struct pbqp { - int num_nodes; /* number of nodes */ - int max_deg; /* maximal degree of a node */ - bool solved; /* flag that indicates whether PBQP has been solved yet */ - bool optimal; /* flag that indicates whether PBQP is optimal */ - PBQPNum min; - bool changed; /* flag whether graph has changed in simplification */ - - /* node fields */ - PBQPVector **node_costs; /* cost vectors of nodes */ - int *node_deg; /* node degree of nodes */ - int *solution; /* solution for node */ - adjnode **adj_list; /* adj. list */ - bucketnode **bucket_ptr; /* bucket pointer of a node */ - - /* node stack */ - int *stack; /* stack of nodes */ - int stack_ptr; /* stack pointer */ - - /* bucket fields */ - bucketnode **bucket_list; /* bucket list */ - - int num_r0; /* counters for number statistics */ - int num_ri; - int num_rii; - int num_rn; - int num_rn_special; -}; - -bool isInf(PBQPNum n) { return n == std::numeric_limits<PBQPNum>::infinity(); } - -/***************************************************************************** - * allocation/de-allocation of pbqp problem - ****************************************************************************/ - -/* allocate new partitioned boolean quadratic program problem */ -pbqp *alloc_pbqp(int num_nodes) -{ - pbqp *this_; - int u; - - assert(num_nodes > 0); - - /* allocate memory for pbqp data structure */ - this_ = (pbqp *)malloc(sizeof(pbqp)); - - /* Initialize pbqp fields */ - this_->num_nodes = num_nodes; - this_->solved = false; - this_->optimal = true; - this_->min = 0.0; - this_->max_deg = 0; - this_->changed = false; - this_->num_r0 = 0; - this_->num_ri = 0; - this_->num_rii = 0; - this_->num_rn = 0; - this_->num_rn_special = 0; - - /* initialize/allocate stack fields of pbqp */ - this_->stack = (int *) malloc(sizeof(int)*num_nodes); - this_->stack_ptr = 0; - - /* initialize/allocate node fields of pbqp */ - this_->adj_list = (adjnode **) malloc(sizeof(adjnode *)*num_nodes); - this_->node_deg = (int *) malloc(sizeof(int)*num_nodes); - this_->solution = (int *) malloc(sizeof(int)*num_nodes); - this_->bucket_ptr = (bucketnode **) malloc(sizeof(bucketnode **)*num_nodes); - this_->node_costs = (PBQPVector**) malloc(sizeof(PBQPVector*) * num_nodes); - for(u=0;u<num_nodes;u++) { - this_->solution[u]=-1; - this_->adj_list[u]=NULL; - this_->node_deg[u]=0; - this_->bucket_ptr[u]=NULL; - this_->node_costs[u]=NULL; - } - - /* initialize bucket list */ - this_->bucket_list = NULL; - - return this_; -} - -/* free pbqp problem */ -void free_pbqp(pbqp *this_) -{ - int u; - int deg; - adjnode *adj_ptr,*adj_next; - bucketnode *bucket,*bucket_next; - - assert(this_ != NULL); - - /* free node cost fields */ - for(u=0;u < this_->num_nodes;u++) { - delete this_->node_costs[u]; - } - free(this_->node_costs); - - /* free bucket list */ - for(deg=0;deg<=this_->max_deg;deg++) { - for(bucket=this_->bucket_list[deg];bucket!=NULL;bucket=bucket_next) { - this_->bucket_ptr[bucket->u] = NULL; - bucket_next = bucket-> succ; - free(bucket); - } - } - free(this_->bucket_list); - - /* free adj. list */ - assert(this_->adj_list != NULL); - for(u=0;u < this_->num_nodes; u++) { - for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = adj_next) { - adj_next = adj_ptr -> succ; - if (u < adj_ptr->adj) { - assert(adj_ptr != NULL); - delete adj_ptr->costs; - } - if (adj_ptr -> tc_safe_regs != NULL) { - free(adj_ptr -> tc_safe_regs); - } - free(adj_ptr); - } - } - free(this_->adj_list); - - /* free other node fields */ - free(this_->node_deg); - free(this_->solution); - free(this_->bucket_ptr); - - /* free stack */ - free(this_->stack); - - /* free pbqp data structure itself */ - free(this_); -} - - -/**************************************************************************** - * adj. node routines - ****************************************************************************/ - -/* find data structure of adj. node of a given node */ -static -adjnode *find_adjnode(pbqp *this_,int u,int v) -{ - adjnode *adj_ptr; - - assert (this_ != NULL); - assert (u >= 0 && u < this_->num_nodes); - assert (v >= 0 && v < this_->num_nodes); - assert(this_->adj_list != NULL); - - for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - if (adj_ptr->adj == v) { - return adj_ptr; - } - } - return NULL; -} - -/* allocate a new data structure for adj. node */ -static -adjnode *alloc_adjnode(pbqp *this_,int u, PBQPMatrix *costs) -{ - adjnode *p; - - assert(this_ != NULL); - assert(costs != NULL); - assert(u >= 0 && u < this_->num_nodes); - - p = (adjnode *)malloc(sizeof(adjnode)); - assert(p != NULL); - - p->adj = u; - p->costs = costs; - - p->tc_valid= false; - p->tc_safe_regs = NULL; - p->tc_impact = 0; - - return p; -} - -/* insert adjacence node to adj. list */ -static -void insert_adjnode(pbqp *this_, int u, adjnode *adj_ptr) -{ - - assert(this_ != NULL); - assert(adj_ptr != NULL); - assert(u >= 0 && u < this_->num_nodes); - - /* if adjacency list of node is not empty -> update - first node of the list */ - if (this_ -> adj_list[u] != NULL) { - assert(this_->adj_list[u]->prev == NULL); - this_->adj_list[u] -> prev = adj_ptr; - } - - /* update doubly chained list pointers of pointers */ - adj_ptr -> succ = this_->adj_list[u]; - adj_ptr -> prev = NULL; - - /* update adjacency list pointer of node u */ - this_->adj_list[u] = adj_ptr; -} - -/* remove entry in an adj. list */ -static -void remove_adjnode(pbqp *this_, int u, adjnode *adj_ptr) -{ - assert(this_!= NULL); - assert(u >= 0 && u <= this_->num_nodes); - assert(this_->adj_list != NULL); - assert(adj_ptr != NULL); - - if (adj_ptr -> prev == NULL) { - this_->adj_list[u] = adj_ptr -> succ; - } else { - adj_ptr -> prev -> succ = adj_ptr -> succ; - } - - if (adj_ptr -> succ != NULL) { - adj_ptr -> succ -> prev = adj_ptr -> prev; - } - - if(adj_ptr->reverse != NULL) { - adjnode *rev = adj_ptr->reverse; - rev->reverse = NULL; - } - - if (adj_ptr -> tc_safe_regs != NULL) { - free(adj_ptr -> tc_safe_regs); - } - - free(adj_ptr); -} - -/***************************************************************************** - * node functions - ****************************************************************************/ - -/* get degree of a node */ -static -int get_deg(pbqp *this_,int u) -{ - adjnode *adj_ptr; - int deg = 0; - - assert(this_ != NULL); - assert(u >= 0 && u < this_->num_nodes); - assert(this_->adj_list != NULL); - - for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - deg ++; - } - return deg; -} - -/* reinsert node */ -static -void reinsert_node(pbqp *this_,int u) -{ - adjnode *adj_u, - *adj_v; - - assert(this_!= NULL); - assert(u >= 0 && u <= this_->num_nodes); - assert(this_->adj_list != NULL); - - for(adj_u = this_ -> adj_list[u]; adj_u != NULL; adj_u = adj_u -> succ) { - int v = adj_u -> adj; - adj_v = alloc_adjnode(this_,u,adj_u->costs); - insert_adjnode(this_,v,adj_v); - } -} - -/* remove node */ -static -void remove_node(pbqp *this_,int u) -{ - adjnode *adj_ptr; - - assert(this_!= NULL); - assert(u >= 0 && u <= this_->num_nodes); - assert(this_->adj_list != NULL); - - for(adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - remove_adjnode(this_,adj_ptr->adj,adj_ptr -> reverse); - } -} - -/***************************************************************************** - * edge functions - ****************************************************************************/ - -/* insert edge to graph */ -/* (does not check whether edge exists in graph */ -static -void insert_edge(pbqp *this_, int u, int v, PBQPMatrix *costs) -{ - adjnode *adj_u, - *adj_v; - - /* create adjanceny entry for u */ - adj_u = alloc_adjnode(this_,v,costs); - insert_adjnode(this_,u,adj_u); - - - /* create adjanceny entry for v */ - adj_v = alloc_adjnode(this_,u,costs); - insert_adjnode(this_,v,adj_v); - - /* create link for reverse edge */ - adj_u -> reverse = adj_v; - adj_v -> reverse = adj_u; -} - -/* delete edge */ -static -void delete_edge(pbqp *this_,int u,int v) -{ - adjnode *adj_ptr; - adjnode *rev; - - assert(this_ != NULL); - assert( u >= 0 && u < this_->num_nodes); - assert( v >= 0 && v < this_->num_nodes); - - adj_ptr=find_adjnode(this_,u,v); - assert(adj_ptr != NULL); - assert(adj_ptr->reverse != NULL); - - delete adj_ptr -> costs; - - rev = adj_ptr->reverse; - remove_adjnode(this_,u,adj_ptr); - remove_adjnode(this_,v,rev); -} - -/***************************************************************************** - * cost functions - ****************************************************************************/ - -/* Note: Since cost(u,v) = transpose(cost(v,u)), it would be necessary to store - two matrices for both edges (u,v) and (v,u). However, we only store the - matrix for the case u < v. For the other case we transpose the stored matrix - if required. -*/ - -/* add costs to cost vector of a node */ -void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs) -{ - assert(this_ != NULL); - assert(costs != NULL); - assert(u >= 0 && u <= this_->num_nodes); - - if (!this_->node_costs[u]) { - this_->node_costs[u] = new PBQPVector(*costs); - } else { - *this_->node_costs[u] += *costs; - } -} - -/* get cost matrix ptr */ -static -PBQPMatrix *get_costmatrix_ptr(pbqp *this_, int u, int v) -{ - adjnode *adj_ptr; - PBQPMatrix *m = NULL; - - assert (this_ != NULL); - assert (u >= 0 && u < this_->num_nodes); - assert (v >= 0 && v < this_->num_nodes); - - adj_ptr = find_adjnode(this_,u,v); - - if (adj_ptr != NULL) { - m = adj_ptr -> costs; - } - - return m; -} - -/* get cost matrix ptr */ -/* Note: only the pointer is returned for - cost(u,v), if u < v. -*/ -static -PBQPMatrix *pbqp_get_costmatrix(pbqp *this_, int u, int v) -{ - adjnode *adj_ptr = find_adjnode(this_,u,v); - - if (adj_ptr != NULL) { - if ( u < v) { - return new PBQPMatrix(*adj_ptr->costs); - } else { - return new PBQPMatrix(adj_ptr->costs->transpose()); - } - } else { - return NULL; - } -} - -/* add costs to cost matrix of an edge */ -void add_pbqp_edgecosts(pbqp *this_,int u,int v, PBQPMatrix *costs) -{ - PBQPMatrix *adj_costs; - - assert(this_!= NULL); - assert(costs != NULL); - assert(u >= 0 && u <= this_->num_nodes); - assert(v >= 0 && v <= this_->num_nodes); - - /* does the edge u-v exists ? */ - if (u == v) { - PBQPVector *diag = new PBQPVector(costs->diagonalize()); - add_pbqp_nodecosts(this_,v,diag); - delete diag; - } else if ((adj_costs = get_costmatrix_ptr(this_,u,v))!=NULL) { - if ( u < v) { - *adj_costs += *costs; - } else { - *adj_costs += costs->transpose(); - } - } else { - adj_costs = new PBQPMatrix((u < v) ? *costs : costs->transpose()); - insert_edge(this_,u,v,adj_costs); - } -} - -/* remove bucket from bucket list */ -static -void pbqp_remove_bucket(pbqp *this_, bucketnode *bucket) -{ - int u = bucket->u; - - assert(this_ != NULL); - assert(u >= 0 && u < this_->num_nodes); - assert(this_->bucket_list != NULL); - assert(this_->bucket_ptr[u] != NULL); - - /* update predecessor node in bucket list - (if no preceeding bucket exists, then - the bucket_list pointer needs to be - updated.) - */ - if (bucket->prev != NULL) { - bucket->prev-> succ = bucket->succ; - } else { - this_->bucket_list[this_->node_deg[u]] = bucket -> succ; - } - - /* update successor node in bucket list */ - if (bucket->succ != NULL) { - bucket->succ-> prev = bucket->prev; - } -} - -/********************************************************************************** - * pop functions - **********************************************************************************/ - -/* pop node of given degree */ -static -int pop_node(pbqp *this_,int deg) -{ - bucketnode *bucket; - int u; - - assert(this_ != NULL); - assert(deg >= 0 && deg <= this_->max_deg); - assert(this_->bucket_list != NULL); - - /* get first bucket of bucket list */ - bucket = this_->bucket_list[deg]; - assert(bucket != NULL); - - /* remove bucket */ - pbqp_remove_bucket(this_,bucket); - u = bucket->u; - free(bucket); - return u; -} - -/********************************************************************************** - * reorder functions - **********************************************************************************/ - -/* add bucket to bucketlist */ -static -void add_to_bucketlist(pbqp *this_,bucketnode *bucket, int deg) -{ - bucketnode *old_head; - - assert(bucket != NULL); - assert(this_ != NULL); - assert(deg >= 0 && deg <= this_->max_deg); - assert(this_->bucket_list != NULL); - - /* store node degree (for re-ordering purposes)*/ - this_->node_deg[bucket->u] = deg; - - /* put bucket to front of doubly chained list */ - old_head = this_->bucket_list[deg]; - bucket -> prev = NULL; - bucket -> succ = old_head; - this_ -> bucket_list[deg] = bucket; - if (bucket -> succ != NULL ) { - assert ( old_head -> prev == NULL); - old_head -> prev = bucket; - } -} - - -/* reorder node in bucket list according to - current node degree */ -static -void reorder_node(pbqp *this_, int u) -{ - int deg; - - assert(this_ != NULL); - assert(u>= 0 && u < this_->num_nodes); - assert(this_->bucket_list != NULL); - assert(this_->bucket_ptr[u] != NULL); - - /* get current node degree */ - deg = get_deg(this_,u); - - /* remove bucket from old bucket list only - if degree of node has changed. */ - if (deg != this_->node_deg[u]) { - pbqp_remove_bucket(this_,this_->bucket_ptr[u]); - add_to_bucketlist(this_,this_->bucket_ptr[u],deg); - } -} - -/* reorder adj. nodes of a node */ -static -void reorder_adjnodes(pbqp *this_,int u) -{ - adjnode *adj_ptr; - - assert(this_!= NULL); - assert(u >= 0 && u <= this_->num_nodes); - assert(this_->adj_list != NULL); - - for(adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - reorder_node(this_,adj_ptr->adj); - } -} - -/********************************************************************************** - * creation functions - **********************************************************************************/ - -/* create new bucket entry */ -/* consistency of the bucket list is not checked! */ -static -void create_bucket(pbqp *this_,int u,int deg) -{ - bucketnode *bucket; - - assert(this_ != NULL); - assert(u >= 0 && u < this_->num_nodes); - assert(this_->bucket_list != NULL); - - bucket = (bucketnode *)malloc(sizeof(bucketnode)); - assert(bucket != NULL); - - bucket -> u = u; - this_->bucket_ptr[u] = bucket; - - add_to_bucketlist(this_,bucket,deg); -} - -/* create bucket list */ -static -void create_bucketlist(pbqp *this_) -{ - int u; - int max_deg; - int deg; - - assert(this_ != NULL); - assert(this_->bucket_list == NULL); - - /* determine max. degree of the nodes */ - max_deg = 2; /* at least of degree two! */ - for(u=0;u<this_->num_nodes;u++) { - deg = this_->node_deg[u] = get_deg(this_,u); - if (deg > max_deg) { - max_deg = deg; - } - } - this_->max_deg = max_deg; - - /* allocate bucket list */ - this_ -> bucket_list = (bucketnode **)malloc(sizeof(bucketnode *)*(max_deg + 1)); - memset(this_->bucket_list,0,sizeof(bucketnode *)*(max_deg + 1)); - assert(this_->bucket_list != NULL); - - /* insert nodes to the list */ - for(u=0;u<this_->num_nodes;u++) { - create_bucket(this_,u,this_->node_deg[u]); - } -} - -/***************************************************************************** - * PBQP simplification for trivial nodes - ****************************************************************************/ - -/* remove trivial node with cost vector length of one */ -static -void disconnect_trivialnode(pbqp *this_,int u) -{ - int v; - adjnode *adj_ptr, - *next; - PBQPMatrix *c_uv; - PBQPVector *c_v; - - assert(this_ != NULL); - assert(this_->node_costs != NULL); - assert(u >= 0 && u < this_ -> num_nodes); - assert(this_->node_costs[u]->getLength() == 1); - - /* add edge costs to node costs of adj. nodes */ - for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = next){ - next = adj_ptr -> succ; - v = adj_ptr -> adj; - assert(v >= 0 && v < this_ -> num_nodes); - - /* convert matrix to cost vector offset for adj. node */ - c_uv = pbqp_get_costmatrix(this_,u,v); - c_v = new PBQPVector(c_uv->getRowAsVector(0)); - *this_->node_costs[v] += *c_v; - - /* delete edge & free vec/mat */ - delete c_v; - delete c_uv; - delete_edge(this_,u,v); - } -} - -/* find all trivial nodes and disconnect them */ -static -void eliminate_trivial_nodes(pbqp *this_) -{ - int u; - - assert(this_ != NULL); - assert(this_ -> node_costs != NULL); - - for(u=0;u < this_ -> num_nodes; u++) { - if (this_->node_costs[u]->getLength() == 1) { - disconnect_trivialnode(this_,u); - } - } -} - -/***************************************************************************** - * Normal form for PBQP - ****************************************************************************/ - -/* simplify a cost matrix. If the matrix - is independent, then simplify_matrix - returns true - otherwise false. In - vectors u and v the offset values of - the decomposition are stored. -*/ - -static -bool normalize_matrix(PBQPMatrix *m, PBQPVector *u, PBQPVector *v) -{ - assert( m != NULL); - assert( u != NULL); - assert( v != NULL); - assert( u->getLength() > 0); - assert( v->getLength() > 0); - - assert(m->getRows() == u->getLength()); - assert(m->getCols() == v->getLength()); - - /* determine u vector */ - for(unsigned r = 0; r < m->getRows(); ++r) { - PBQPNum min = m->getRowMin(r); - (*u)[r] += min; - if (!isInf(min)) { - m->subFromRow(r, min); - } else { - m->setRow(r, 0); - } - } - - /* determine v vector */ - for(unsigned c = 0; c < m->getCols(); ++c) { - PBQPNum min = m->getColMin(c); - (*v)[c] += min; - if (!isInf(min)) { - m->subFromCol(c, min); - } else { - m->setCol(c, 0); - } - } - - /* determine whether matrix is - independent or not. - */ - return m->isZero(); -} - -/* simplify single edge */ -static -void simplify_edge(pbqp *this_,int u,int v) -{ - PBQPMatrix *costs; - bool is_zero; - - assert (this_ != NULL); - assert (u >= 0 && u <this_->num_nodes); - assert (v >= 0 && v <this_->num_nodes); - assert (u != v); - - /* swap u and v if u > v in order to avoid un-necessary - tranpositions of the cost matrix */ - - if (u > v) { - int swap = u; - u = v; - v = swap; - } - - /* get cost matrix and simplify it */ - costs = get_costmatrix_ptr(this_,u,v); - is_zero=normalize_matrix(costs,this_->node_costs[u],this_->node_costs[v]); - - /* delete edge */ - if(is_zero){ - delete_edge(this_,u,v); - this_->changed = true; - } -} - -/* normalize cost matrices and remove - edges in PBQP if they ary independent, - i.e. can be decomposed into two - cost vectors. -*/ -static -void eliminate_independent_edges(pbqp *this_) -{ - int u,v; - adjnode *adj_ptr,*next; - - assert(this_ != NULL); - assert(this_ -> adj_list != NULL); - - this_->changed = false; - for(u=0;u < this_->num_nodes;u++) { - for (adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = next) { - next = adj_ptr -> succ; - v = adj_ptr -> adj; - assert(v >= 0 && v < this_->num_nodes); - if (u < v) { - simplify_edge(this_,u,v); - } - } - } -} - - -/***************************************************************************** - * PBQP reduction rules - ****************************************************************************/ - -/* RI reduction - This reduction rule is applied for nodes - of degree one. */ - -static -void apply_RI(pbqp *this_,int x) -{ - int y; - unsigned xlen, - ylen; - PBQPMatrix *c_yx; - PBQPVector *c_x, *delta; - - assert(this_ != NULL); - assert(x >= 0 && x < this_->num_nodes); - assert(this_ -> adj_list[x] != NULL); - assert(this_ -> adj_list[x] -> succ == NULL); - - /* get adjacence matrix */ - y = this_ -> adj_list[x] -> adj; - assert(y >= 0 && y < this_->num_nodes); - - /* determine length of cost vectors for node x and y */ - xlen = this_ -> node_costs[x]->getLength(); - ylen = this_ -> node_costs[y]->getLength(); - - /* get cost vector c_x and matrix c_yx */ - c_x = this_ -> node_costs[x]; - c_yx = pbqp_get_costmatrix(this_,y,x); - assert (c_yx != NULL); - - - /* allocate delta vector */ - delta = new PBQPVector(ylen); - - /* compute delta vector */ - for(unsigned i = 0; i < ylen; ++i) { - PBQPNum min = (*c_yx)[i][0] + (*c_x)[0]; - for(unsigned j = 1; j < xlen; ++j) { - PBQPNum c = (*c_yx)[i][j] + (*c_x)[j]; - if ( c < min ) - min = c; - } - (*delta)[i] = min; - } - - /* add delta vector */ - *this_ -> node_costs[y] += *delta; - - /* delete node x */ - remove_node(this_,x); - - /* reorder adj. nodes of node x */ - reorder_adjnodes(this_,x); - - /* push node x on stack */ - assert(this_ -> stack_ptr < this_ -> num_nodes); - this_->stack[this_ -> stack_ptr++] = x; - - /* free vec/mat */ - delete c_yx; - delete delta; - - /* increment counter for number statistic */ - this_->num_ri++; -} - -/* RII reduction - This reduction rule is applied for nodes - of degree two. */ - -static -void apply_RII(pbqp *this_,int x) -{ - int y,z; - unsigned xlen,ylen,zlen; - adjnode *adj_yz; - - PBQPMatrix *c_yx, *c_zx; - PBQPVector *cx; - PBQPMatrix *delta; - - assert(this_ != NULL); - assert(x >= 0 && x < this_->num_nodes); - assert(this_ -> adj_list[x] != NULL); - assert(this_ -> adj_list[x] -> succ != NULL); - assert(this_ -> adj_list[x] -> succ -> succ == NULL); - - /* get adjacence matrix */ - y = this_ -> adj_list[x] -> adj; - z = this_ -> adj_list[x] -> succ -> adj; - assert(y >= 0 && y < this_->num_nodes); - assert(z >= 0 && z < this_->num_nodes); - - /* determine length of cost vectors for node x and y */ - xlen = this_ -> node_costs[x]->getLength(); - ylen = this_ -> node_costs[y]->getLength(); - zlen = this_ -> node_costs[z]->getLength(); - - /* get cost vector c_x and matrix c_yx */ - cx = this_ -> node_costs[x]; - c_yx = pbqp_get_costmatrix(this_,y,x); - c_zx = pbqp_get_costmatrix(this_,z,x); - assert(c_yx != NULL); - assert(c_zx != NULL); - - /* Colour Heuristic */ - if ( (adj_yz = find_adjnode(this_,y,z)) != NULL) { - adj_yz->tc_valid = false; - adj_yz->reverse->tc_valid = false; - } - - /* allocate delta matrix */ - delta = new PBQPMatrix(ylen, zlen); - - /* compute delta matrix */ - for(unsigned i=0;i<ylen;i++) { - for(unsigned j=0;j<zlen;j++) { - PBQPNum min = (*c_yx)[i][0] + (*c_zx)[j][0] + (*cx)[0]; - for(unsigned k=1;k<xlen;k++) { - PBQPNum c = (*c_yx)[i][k] + (*c_zx)[j][k] + (*cx)[k]; - if ( c < min ) { - min = c; - } - } - (*delta)[i][j] = min; - } - } - - /* add delta matrix */ - add_pbqp_edgecosts(this_,y,z,delta); - - /* delete node x */ - remove_node(this_,x); - - /* simplify cost matrix c_yz */ - simplify_edge(this_,y,z); - - /* reorder adj. nodes */ - reorder_adjnodes(this_,x); - - /* push node x on stack */ - assert(this_ -> stack_ptr < this_ -> num_nodes); - this_->stack[this_ -> stack_ptr++] = x; - - /* free vec/mat */ - delete c_yx; - delete c_zx; - delete delta; - - /* increment counter for number statistic */ - this_->num_rii++; - -} - -/* RN reduction */ -static -void apply_RN(pbqp *this_,int x) -{ - unsigned xlen; - - assert(this_ != NULL); - assert(x >= 0 && x < this_->num_nodes); - assert(this_ -> node_costs[x] != NULL); - - xlen = this_ -> node_costs[x] -> getLength(); - - /* after application of RN rule no optimality - can be guaranteed! */ - this_ -> optimal = false; - - /* push node x on stack */ - assert(this_ -> stack_ptr < this_ -> num_nodes); - this_->stack[this_ -> stack_ptr++] = x; - - /* delete node x */ - remove_node(this_,x); - - /* reorder adj. nodes of node x */ - reorder_adjnodes(this_,x); - - /* increment counter for number statistic */ - this_->num_rn++; -} - - -static -void compute_tc_info(pbqp *this_, adjnode *p) -{ - adjnode *r; - PBQPMatrix *m; - int x,y; - PBQPVector *c_x, *c_y; - int *row_inf_counts; - - assert(p->reverse != NULL); - - /* set flags */ - r = p->reverse; - p->tc_valid = true; - r->tc_valid = true; - - /* get edge */ - x = r->adj; - y = p->adj; - - /* get cost vectors */ - c_x = this_ -> node_costs[x]; - c_y = this_ -> node_costs[y]; - - /* get cost matrix */ - m = pbqp_get_costmatrix(this_, x, y); - - - /* allocate allowed set for edge (x,y) and (y,x) */ - if (p->tc_safe_regs == NULL) { - p->tc_safe_regs = (int *) malloc(sizeof(int) * c_x->getLength()); - } - - if (r->tc_safe_regs == NULL ) { - r->tc_safe_regs = (int *) malloc(sizeof(int) * c_y->getLength()); - } - - p->tc_impact = r->tc_impact = 0; - - row_inf_counts = (int *) alloca(sizeof(int) * c_x->getLength()); - - /* init arrays */ - p->tc_safe_regs[0] = 0; - row_inf_counts[0] = 0; - for(unsigned i = 1; i < c_x->getLength(); ++i){ - p->tc_safe_regs[i] = 1; - row_inf_counts[i] = 0; - } - - r->tc_safe_regs[0] = 0; - for(unsigned j = 1; j < c_y->getLength(); ++j){ - r->tc_safe_regs[j] = 1; - } - - for(unsigned j = 0; j < c_y->getLength(); ++j) { - int col_inf_counts = 0; - for (unsigned i = 0; i < c_x->getLength(); ++i) { - if (isInf((*m)[i][j])) { - ++col_inf_counts; - ++row_inf_counts[i]; - - p->tc_safe_regs[i] = 0; - r->tc_safe_regs[j] = 0; - } - } - if (col_inf_counts > p->tc_impact) { - p->tc_impact = col_inf_counts; - } - } - - for(unsigned i = 0; i < c_x->getLength(); ++i){ - if (row_inf_counts[i] > r->tc_impact) - { - r->tc_impact = row_inf_counts[i]; - } - } - - delete m; -} - -/* - * Checks whether node x can be locally coloured. - */ -static -int is_colorable(pbqp *this_,int x) -{ - adjnode *adj_ptr; - PBQPVector *c_x; - int result = 1; - int *allowed; - int num_allowed = 0; - unsigned total_impact = 0; - - assert(this_ != NULL); - assert(x >= 0 && x < this_->num_nodes); - assert(this_ -> node_costs[x] != NULL); - - c_x = this_ -> node_costs[x]; - - /* allocate allowed set */ - allowed = (int *)malloc(sizeof(int) * c_x->getLength()); - for(unsigned i = 0; i < c_x->getLength(); ++i){ - if (!isInf((*c_x)[i]) && i > 0) { - allowed[i] = 1; - ++num_allowed; - } else { - allowed[i] = 0; - } - } - - /* determine local minimum */ - for(adj_ptr=this_->adj_list[x] ;adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - if (!adj_ptr -> tc_valid) { - compute_tc_info(this_, adj_ptr); - } - - total_impact += adj_ptr->tc_impact; - - if (num_allowed > 0) { - for (unsigned i = 1; i < c_x->getLength(); ++i){ - if (allowed[i]){ - if (!adj_ptr->tc_safe_regs[i]){ - allowed[i] = 0; - --num_allowed; - if (num_allowed == 0) - break; - } - } - } - } - - if ( total_impact >= c_x->getLength() - 1 && num_allowed == 0 ) { - result = 0; - break; - } - } - free(allowed); - - return result; -} - -/* use briggs heuristic - note: this_ is not a general heuristic. it only is useful for - interference graphs. - */ -int pop_colorablenode(pbqp *this_) -{ - int deg; - bucketnode *min_bucket=NULL; - PBQPNum min = std::numeric_limits<PBQPNum>::infinity(); - - /* select node where the number of colors is less than the node degree */ - for(deg=this_->max_deg;deg > 2;deg--) { - bucketnode *bucket; - for(bucket=this_->bucket_list[deg];bucket!= NULL;bucket = bucket -> succ) { - int u = bucket->u; - if (is_colorable(this_,u)) { - pbqp_remove_bucket(this_,bucket); - this_->num_rn_special++; - free(bucket); - return u; - } - } - } - - /* select node with minimal ratio between average node costs and degree of node */ - for(deg=this_->max_deg;deg >2; deg--) { - bucketnode *bucket; - for(bucket=this_->bucket_list[deg];bucket!= NULL;bucket = bucket -> succ) { - PBQPNum h; - int u; - - u = bucket->u; - assert(u>=0 && u < this_->num_nodes); - h = (*this_->node_costs[u])[0] / (PBQPNum) deg; - if (h < min) { - min_bucket = bucket; - min = h; - } - } - } - - /* return node and free bucket */ - if (min_bucket != NULL) { - int u; - - pbqp_remove_bucket(this_,min_bucket); - u = min_bucket->u; - free(min_bucket); - return u; - } else { - return -1; - } -} - - -/***************************************************************************** - * PBQP graph parsing - ****************************************************************************/ - -/* reduce pbqp problem (first phase) */ -static -void reduce_pbqp(pbqp *this_) -{ - int u; - - assert(this_ != NULL); - assert(this_->bucket_list != NULL); - - for(;;){ - - if (this_->bucket_list[1] != NULL) { - u = pop_node(this_,1); - apply_RI(this_,u); - } else if (this_->bucket_list[2] != NULL) { - u = pop_node(this_,2); - apply_RII(this_,u); - } else if ((u = pop_colorablenode(this_)) != -1) { - apply_RN(this_,u); - } else { - break; - } - } -} - -/***************************************************************************** - * PBQP back propagation - ****************************************************************************/ - -/* determine solution of a reduced node. Either - RI or RII was applied for this_ node. */ -static -void determine_solution(pbqp *this_,int x) -{ - PBQPVector *v = new PBQPVector(*this_ -> node_costs[x]); - adjnode *adj_ptr; - - assert(this_ != NULL); - assert(x >= 0 && x < this_->num_nodes); - assert(this_ -> adj_list != NULL); - assert(this_ -> solution != NULL); - - for(adj_ptr=this_->adj_list[x] ;adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - int y = adj_ptr -> adj; - int y_sol = this_ -> solution[y]; - - PBQPMatrix *c_yx = pbqp_get_costmatrix(this_,y,x); - assert(y_sol >= 0 && y_sol < (int)this_->node_costs[y]->getLength()); - (*v) += c_yx->getRowAsVector(y_sol); - delete c_yx; - } - this_ -> solution[x] = v->minIndex(); - - delete v; -} - -/* back popagation phase of PBQP */ -static -void back_propagate(pbqp *this_) -{ - int i; - - assert(this_ != NULL); - assert(this_->stack != NULL); - assert(this_->stack_ptr < this_->num_nodes); - - for(i=this_ -> stack_ptr-1;i>=0;i--) { - int x = this_ -> stack[i]; - assert( x >= 0 && x < this_ -> num_nodes); - reinsert_node(this_,x); - determine_solution(this_,x); - } -} - -/* solve trivial nodes of degree zero */ -static -void determine_trivialsolution(pbqp *this_) -{ - int u; - PBQPNum delta; - - assert( this_ != NULL); - assert( this_ -> bucket_list != NULL); - - /* determine trivial solution */ - while (this_->bucket_list[0] != NULL) { - u = pop_node(this_,0); - - assert( u >= 0 && u < this_ -> num_nodes); - - this_->solution[u] = this_->node_costs[u]->minIndex(); - delta = (*this_->node_costs[u])[this_->solution[u]]; - this_->min = this_->min + delta; - - /* increment counter for number statistic */ - this_->num_r0++; - } -} - -/***************************************************************************** - * debug facilities - ****************************************************************************/ -static -void check_pbqp(pbqp *this_) -{ - int u,v; - PBQPMatrix *costs; - adjnode *adj_ptr; - - assert( this_ != NULL); - - for(u=0;u< this_->num_nodes; u++) { - assert (this_ -> node_costs[u] != NULL); - for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) { - v = adj_ptr -> adj; - assert( v>= 0 && v < this_->num_nodes); - if (u < v ) { - costs = adj_ptr -> costs; - assert( costs->getRows() == this_->node_costs[u]->getLength() && - costs->getCols() == this_->node_costs[v]->getLength()); - } - } - } -} - -/***************************************************************************** - * PBQP solve routines - ****************************************************************************/ - -/* solve PBQP problem */ -void solve_pbqp(pbqp *this_) -{ - assert(this_ != NULL); - assert(!this_->solved); - - /* check vector & matrix dimensions */ - check_pbqp(this_); - - /* simplify PBQP problem */ - - /* eliminate trivial nodes, i.e. - nodes with cost vectors of length one. */ - eliminate_trivial_nodes(this_); - - /* eliminate edges with independent - cost matrices and normalize matrices */ - eliminate_independent_edges(this_); - - /* create bucket list for graph parsing */ - create_bucketlist(this_); - - /* reduce phase */ - reduce_pbqp(this_); - - /* solve trivial nodes */ - determine_trivialsolution(this_); - - /* back propagation phase */ - back_propagate(this_); - - this_->solved = true; -} - -/* get solution of a node */ -int get_pbqp_solution(pbqp *this_,int x) -{ - assert(this_ != NULL); - assert(this_->solution != NULL); - assert(this_ -> solved); - - return this_->solution[x]; -} - -/* is solution optimal? */ -bool is_pbqp_optimal(pbqp *this_) -{ - assert(this_ -> solved); - return this_->optimal; -} - -} - -/* end of pbqp.c */ diff --git a/lib/CodeGen/PBQP.h b/lib/CodeGen/PBQP.h deleted file mode 100644 index 5fd2c06..0000000 --- a/lib/CodeGen/PBQP.h +++ /dev/null @@ -1,284 +0,0 @@ -//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Developed by: Bernhard Scholz -// The University of Sydney -// http://www.it.usyd.edu.au/~scholz -//===----------------------------------------------------------------------===// - -// TODO: -// -// * Default to null costs on vector initialisation? -// * C++-ify the rest of the solver. - -#ifndef LLVM_CODEGEN_PBQPSOLVER_H -#define LLVM_CODEGEN_PBQPSOLVER_H - -#include <cassert> -#include <algorithm> -#include <functional> - -namespace llvm { - -//! \brief Floating point type to use in PBQP solver. -typedef double PBQPNum; - -//! \brief PBQP Vector class. -class PBQPVector { -public: - - //! \brief Construct a PBQP vector of the given size. - explicit PBQPVector(unsigned length) : - length(length), data(new PBQPNum[length]) { - std::fill(data, data + length, 0); - } - - //! \brief Copy construct a PBQP vector. - PBQPVector(const PBQPVector &v) : - length(v.length), data(new PBQPNum[length]) { - std::copy(v.data, v.data + length, data); - } - - ~PBQPVector() { delete[] data; } - - //! \brief Assignment operator. - PBQPVector& operator=(const PBQPVector &v) { - delete[] data; - length = v.length; - data = new PBQPNum[length]; - std::copy(v.data, v.data + length, data); - return *this; - } - - //! \brief Return the length of the vector - unsigned getLength() const throw () { - return length; - } - - //! \brief Element access. - PBQPNum& operator[](unsigned index) { - assert(index < length && "PBQPVector element access out of bounds."); - return data[index]; - } - - //! \brief Const element access. - const PBQPNum& operator[](unsigned index) const { - assert(index < length && "PBQPVector element access out of bounds."); - return data[index]; - } - - //! \brief Add another vector to this one. - PBQPVector& operator+=(const PBQPVector &v) { - assert(length == v.length && "PBQPVector length mismatch."); - std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); - return *this; - } - - //! \brief Subtract another vector from this one. - PBQPVector& operator-=(const PBQPVector &v) { - assert(length == v.length && "PBQPVector length mismatch."); - std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); - return *this; - } - - //! \brief Returns the index of the minimum value in this vector - unsigned minIndex() const { - return std::min_element(data, data + length) - data; - } - -private: - unsigned length; - PBQPNum *data; -}; - - -//! \brief PBQP Matrix class -class PBQPMatrix { -public: - - //! \brief Construct a PBQP Matrix with the given dimensions. - PBQPMatrix(unsigned rows, unsigned cols) : - rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { - std::fill(data, data + (rows * cols), 0); - } - - //! \brief Copy construct a PBQP matrix. - PBQPMatrix(const PBQPMatrix &m) : - rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) { - std::copy(m.data, m.data + (rows * cols), data); - } - - ~PBQPMatrix() { delete[] data; } - - //! \brief Assignment operator. - PBQPMatrix& operator=(const PBQPMatrix &m) { - delete[] data; - rows = m.rows; cols = m.cols; - data = new PBQPNum[rows * cols]; - std::copy(m.data, m.data + (rows * cols), data); - return *this; - } - - //! \brief Return the number of rows in this matrix. - unsigned getRows() const throw () { return rows; } - - //! \brief Return the number of cols in this matrix. - unsigned getCols() const throw () { return cols; } - - //! \brief Matrix element access. - PBQPNum* operator[](unsigned r) { - assert(r < rows && "Row out of bounds."); - return data + (r * cols); - } - - //! \brief Matrix element access. - const PBQPNum* operator[](unsigned r) const { - assert(r < rows && "Row out of bounds."); - return data + (r * cols); - } - - //! \brief Returns the given row as a vector. - PBQPVector getRowAsVector(unsigned r) const { - PBQPVector v(cols); - for (unsigned c = 0; c < cols; ++c) - v[c] = (*this)[r][c]; - return v; - } - - //! \brief Reset the matrix to the given value. - PBQPMatrix& reset(PBQPNum val = 0) { - std::fill(data, data + (rows * cols), val); - return *this; - } - - //! \brief Set a single row of this matrix to the given value. - PBQPMatrix& setRow(unsigned r, PBQPNum val) { - assert(r < rows && "Row out of bounds."); - std::fill(data + (r * cols), data + ((r + 1) * cols), val); - return *this; - } - - //! \brief Set a single column of this matrix to the given value. - PBQPMatrix& setCol(unsigned c, PBQPNum val) { - assert(c < cols && "Column out of bounds."); - for (unsigned r = 0; r < rows; ++r) - (*this)[r][c] = val; - return *this; - } - - //! \brief Matrix transpose. - PBQPMatrix transpose() const { - PBQPMatrix m(cols, rows); - for (unsigned r = 0; r < rows; ++r) - for (unsigned c = 0; c < cols; ++c) - m[c][r] = (*this)[r][c]; - return m; - } - - //! \brief Returns the diagonal of the matrix as a vector. - //! - //! Matrix must be square. - PBQPVector diagonalize() const { - assert(rows == cols && "Attempt to diagonalize non-square matrix."); - - PBQPVector v(rows); - for (unsigned r = 0; r < rows; ++r) - v[r] = (*this)[r][r]; - return v; - } - - //! \brief Add the given matrix to this one. - PBQPMatrix& operator+=(const PBQPMatrix &m) { - assert(rows == m.rows && cols == m.cols && - "Matrix dimensions mismatch."); - std::transform(data, data + (rows * cols), m.data, data, - std::plus<PBQPNum>()); - return *this; - } - - //! \brief Returns the minimum of the given row - PBQPNum getRowMin(unsigned r) const { - assert(r < rows && "Row out of bounds"); - return *std::min_element(data + (r * cols), data + ((r + 1) * cols)); - } - - //! \brief Returns the minimum of the given column - PBQPNum getColMin(unsigned c) const { - PBQPNum minElem = (*this)[0][c]; - for (unsigned r = 1; r < rows; ++r) - if ((*this)[r][c] < minElem) minElem = (*this)[r][c]; - return minElem; - } - - //! \brief Subtracts the given scalar from the elements of the given row. - PBQPMatrix& subFromRow(unsigned r, PBQPNum val) { - assert(r < rows && "Row out of bounds"); - std::transform(data + (r * cols), data + ((r + 1) * cols), - data + (r * cols), - std::bind2nd(std::minus<PBQPNum>(), val)); - return *this; - } - - //! \brief Subtracts the given scalar from the elements of the given column. - PBQPMatrix& subFromCol(unsigned c, PBQPNum val) { - for (unsigned r = 0; r < rows; ++r) - (*this)[r][c] -= val; - return *this; - } - - //! \brief Returns true if this is a zero matrix. - bool isZero() const { - return find_if(data, data + (rows * cols), - std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) == - data + (rows * cols); - } - -private: - unsigned rows, cols; - PBQPNum *data; -}; - -#define EPS (1E-8) - -#ifndef PBQP_TYPE -#define PBQP_TYPE -struct pbqp; -typedef struct pbqp pbqp; -#endif - -/***************** - * PBQP routines * - *****************/ - -/* allocate pbqp problem */ -pbqp *alloc_pbqp(int num); - -/* add node costs */ -void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs); - -/* add edge mat */ -void add_pbqp_edgecosts(pbqp *this_,int u,int v,PBQPMatrix *costs); - -/* solve PBQP problem */ -void solve_pbqp(pbqp *this_); - -/* get solution of a node */ -int get_pbqp_solution(pbqp *this_,int u); - -/* alloc PBQP */ -pbqp *alloc_pbqp(int num); - -/* free PBQP */ -void free_pbqp(pbqp *this_); - -/* is optimal */ -bool is_pbqp_optimal(pbqp *this_); - -} -#endif diff --git a/lib/CodeGen/RegAllocBigBlock.cpp b/lib/CodeGen/RegAllocBigBlock.cpp deleted file mode 100644 index 91e4099..0000000 --- a/lib/CodeGen/RegAllocBigBlock.cpp +++ /dev/null @@ -1,892 +0,0 @@ -//===- RegAllocBigBlock.cpp - A register allocator for large basic blocks -===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the RABigBlock class -// -//===----------------------------------------------------------------------===// - -// This register allocator is derived from RegAllocLocal.cpp. Like it, this -// allocator works on one basic block at a time, oblivious to others. -// However, the algorithm used here is suited for long blocks of -// instructions - registers are spilled by greedily choosing those holding -// values that will not be needed for the longest amount of time. This works -// particularly well for blocks with 10 or more times as many instructions -// as machine registers, but can be used for general code. -// -//===----------------------------------------------------------------------===// -// -// TODO: - automagically invoke linearscan for (groups of) small BBs? -// - break ties when picking regs? (probably not worth it in a -// JIT context) -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "regalloc" -#include "llvm/BasicBlock.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/LiveVariables.h" -#include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Compiler.h" -#include "llvm/ADT/IndexedMap.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" -#include <algorithm> -using namespace llvm; - -STATISTIC(NumStores, "Number of stores added"); -STATISTIC(NumLoads , "Number of loads added"); -STATISTIC(NumFolded, "Number of loads/stores folded into instructions"); - -static RegisterRegAlloc - bigBlockRegAlloc("bigblock", "Big-block register allocator", - createBigBlockRegisterAllocator); - -namespace { -/// VRegKeyInfo - Defines magic values required to use VirtRegs as DenseMap -/// keys. - struct VRegKeyInfo { - static inline unsigned getEmptyKey() { return -1U; } - static inline unsigned getTombstoneKey() { return -2U; } - static bool isEqual(unsigned LHS, unsigned RHS) { return LHS == RHS; } - static unsigned getHashValue(const unsigned &Key) { return Key; } - }; - - -/// This register allocator is derived from RegAllocLocal.cpp. Like it, this -/// allocator works on one basic block at a time, oblivious to others. -/// However, the algorithm used here is suited for long blocks of -/// instructions - registers are spilled by greedily choosing those holding -/// values that will not be needed for the longest amount of time. This works -/// particularly well for blocks with 10 or more times as many instructions -/// as machine registers, but can be used for general code. -/// -/// TODO: - automagically invoke linearscan for (groups of) small BBs? -/// - break ties when picking regs? (probably not worth it in a -/// JIT context) -/// - class VISIBILITY_HIDDEN RABigBlock : public MachineFunctionPass { - public: - static char ID; - RABigBlock() : MachineFunctionPass(&ID) {} - private: - /// TM - For getting at TargetMachine info - /// - const TargetMachine *TM; - - /// MF - Our generic MachineFunction pointer - /// - MachineFunction *MF; - - /// RegInfo - For dealing with machine register info (aliases, folds - /// etc) - const TargetRegisterInfo *RegInfo; - - typedef SmallVector<unsigned, 2> VRegTimes; - - /// VRegReadTable - maps VRegs in a BB to the set of times they are read - /// - DenseMap<unsigned, VRegTimes*, VRegKeyInfo> VRegReadTable; - - /// VRegReadIdx - keeps track of the "current time" in terms of - /// positions in VRegReadTable - DenseMap<unsigned, unsigned , VRegKeyInfo> VRegReadIdx; - - /// StackSlotForVirtReg - Maps virtual regs to the frame index where these - /// values are spilled. - IndexedMap<unsigned, VirtReg2IndexFunctor> StackSlotForVirtReg; - - /// Virt2PhysRegMap - This map contains entries for each virtual register - /// that is currently available in a physical register. - IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap; - - /// PhysRegsUsed - This array is effectively a map, containing entries for - /// each physical register that currently has a value (ie, it is in - /// Virt2PhysRegMap). The value mapped to is the virtual register - /// corresponding to the physical register (the inverse of the - /// Virt2PhysRegMap), or 0. The value is set to 0 if this register is pinned - /// because it is used by a future instruction, and to -2 if it is not - /// allocatable. If the entry for a physical register is -1, then the - /// physical register is "not in the map". - /// - std::vector<int> PhysRegsUsed; - - /// VirtRegModified - This bitset contains information about which virtual - /// registers need to be spilled back to memory when their registers are - /// scavenged. If a virtual register has simply been rematerialized, there - /// is no reason to spill it to memory when we need the register back. - /// - std::vector<int> VirtRegModified; - - /// MBBLastInsnTime - the number of the the last instruction in MBB - /// - int MBBLastInsnTime; - - /// MBBCurTime - the number of the the instruction being currently processed - /// - int MBBCurTime; - - unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { - return Virt2PhysRegMap[VirtReg]; - } - - unsigned &getVirt2StackSlot(unsigned VirtReg) { - return StackSlotForVirtReg[VirtReg]; - } - - /// markVirtRegModified - Lets us flip bits in the VirtRegModified bitset - /// - void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - Reg -= TargetRegisterInfo::FirstVirtualRegister; - if (VirtRegModified.size() <= Reg) - VirtRegModified.resize(Reg+1); - VirtRegModified[Reg] = Val; - } - - /// isVirtRegModified - Lets us query the VirtRegModified bitset - /// - bool isVirtRegModified(unsigned Reg) const { - assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size() - && "Illegal virtual register!"); - return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; - } - - public: - /// getPassName - returns the BigBlock allocator's name - /// - virtual const char *getPassName() const { - return "BigBlock Register Allocator"; - } - - /// getAnalaysisUsage - declares the required analyses - /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredID(PHIEliminationID); - AU.addRequiredID(TwoAddressInstructionPassID); - MachineFunctionPass::getAnalysisUsage(AU); - } - - private: - /// runOnMachineFunction - Register allocate the whole function - /// - bool runOnMachineFunction(MachineFunction &Fn); - - /// AllocateBasicBlock - Register allocate the specified basic block. - /// - void AllocateBasicBlock(MachineBasicBlock &MBB); - - /// FillVRegReadTable - Fill out the table of vreg read times given a BB - /// - void FillVRegReadTable(MachineBasicBlock &MBB); - - /// areRegsEqual - This method returns true if the specified registers are - /// related to each other. To do this, it checks to see if they are equal - /// or if the first register is in the alias set of the second register. - /// - bool areRegsEqual(unsigned R1, unsigned R2) const { - if (R1 == R2) return true; - for (const unsigned *AliasSet = RegInfo->getAliasSet(R2); - *AliasSet; ++AliasSet) { - if (*AliasSet == R1) return true; - } - return false; - } - - /// getStackSpaceFor - This returns the frame index of the specified virtual - /// register on the stack, allocating space if necessary. - int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); - - /// removePhysReg - This method marks the specified physical register as no - /// longer being in use. - /// - void removePhysReg(unsigned PhysReg); - - /// spillVirtReg - This method spills the value specified by PhysReg into - /// the virtual register slot specified by VirtReg. It then updates the RA - /// data structures to indicate the fact that PhysReg is now available. - /// - void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, - unsigned VirtReg, unsigned PhysReg); - - /// spillPhysReg - This method spills the specified physical register into - /// the virtual register slot associated with it. If OnlyVirtRegs is set to - /// true, then the request is ignored if the physical register does not - /// contain a virtual register. - /// - void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, - unsigned PhysReg, bool OnlyVirtRegs = false); - - /// assignVirtToPhysReg - This method updates local state so that we know - /// that PhysReg is the proper container for VirtReg now. The physical - /// register must not be used for anything else when this is called. - /// - void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); - - /// isPhysRegAvailable - Return true if the specified physical register is - /// free and available for use. This also includes checking to see if - /// aliased registers are all free... - /// - bool isPhysRegAvailable(unsigned PhysReg) const; - - /// getFreeReg - Look to see if there is a free register available in the - /// specified register class. If not, return 0. - /// - unsigned getFreeReg(const TargetRegisterClass *RC); - - /// chooseReg - Pick a physical register to hold the specified - /// virtual register by choosing the one which will be read furthest - /// in the future. - /// - unsigned chooseReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned VirtReg); - - /// reloadVirtReg - This method transforms the specified specified virtual - /// register use to refer to a physical register. This method may do this - /// in one of several ways: if the register is available in a physical - /// register already, it uses that physical register. If the value is not - /// in a physical register, and if there are physical registers available, - /// it loads it into a register. If register pressure is high, and it is - /// possible, it tries to fold the load of the virtual register into the - /// instruction itself. It avoids doing this if register pressure is low to - /// improve the chance that subsequent instructions can use the reloaded - /// value. This method returns the modified instruction. - /// - MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned OpNum); - - }; - char RABigBlock::ID = 0; -} - -/// getStackSpaceFor - This allocates space for the specified virtual register -/// to be held on the stack. -int RABigBlock::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { - // Find the location Reg would belong... - int FrameIdx = getVirt2StackSlot(VirtReg); - - if (FrameIdx) - return FrameIdx - 1; // Already has space allocated? - - // Allocate a new stack object for this spill location... - FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), - RC->getAlignment()); - - // Assign the slot... - getVirt2StackSlot(VirtReg) = FrameIdx + 1; - return FrameIdx; -} - - -/// removePhysReg - This method marks the specified physical register as no -/// longer being in use. -/// -void RABigBlock::removePhysReg(unsigned PhysReg) { - PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used -} - - -/// spillVirtReg - This method spills the value specified by PhysReg into the -/// virtual register slot specified by VirtReg. It then updates the RA data -/// structures to indicate the fact that PhysReg is now available. -/// -void RABigBlock::spillVirtReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator I, - unsigned VirtReg, unsigned PhysReg) { - assert(VirtReg && "Spilling a physical register is illegal!" - " Must not have appropriate kill for the register or use exists beyond" - " the intended one."); - DOUT << " Spilling register " << RegInfo->getName(PhysReg) - << " containing %reg" << VirtReg; - - const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); - - if (!isVirtRegModified(VirtReg)) - DOUT << " which has not been modified, so no store necessary!"; - - // Otherwise, there is a virtual register corresponding to this physical - // register. We only need to spill it into its stack slot if it has been - // modified. - if (isVirtRegModified(VirtReg)) { - const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); - int FrameIndex = getStackSpaceFor(VirtReg, RC); - DOUT << " to stack slot #" << FrameIndex; - TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIndex, RC); - ++NumStores; // Update statistics - } - - getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available - - DOUT << "\n"; - removePhysReg(PhysReg); -} - - -/// spillPhysReg - This method spills the specified physical register into the -/// virtual register slot associated with it. If OnlyVirtRegs is set to true, -/// then the request is ignored if the physical register does not contain a -/// virtual register. -/// -void RABigBlock::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, - unsigned PhysReg, bool OnlyVirtRegs) { - if (PhysRegsUsed[PhysReg] != -1) { // Only spill it if it's used! - assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!"); - if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs) - spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg); - } else { - // If the selected register aliases any other registers, we must make - // sure that one of the aliases isn't alive. - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) - if (PhysRegsUsed[*AliasSet] != -1 && // Spill aliased register. - PhysRegsUsed[*AliasSet] != -2) // If allocatable. - if (PhysRegsUsed[*AliasSet]) - spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); - } -} - - -/// assignVirtToPhysReg - This method updates local state so that we know -/// that PhysReg is the proper container for VirtReg now. The physical -/// register must not be used for anything else when this is called. -/// -void RABigBlock::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { - assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!"); - // Update information to note the fact that this register was just used, and - // it holds VirtReg. - PhysRegsUsed[PhysReg] = VirtReg; - getVirt2PhysRegMapSlot(VirtReg) = PhysReg; -} - - -/// isPhysRegAvailable - Return true if the specified physical register is free -/// and available for use. This also includes checking to see if aliased -/// registers are all free... -/// -bool RABigBlock::isPhysRegAvailable(unsigned PhysReg) const { - if (PhysRegsUsed[PhysReg] != -1) return false; - - // If the selected register aliases any other allocated registers, it is - // not free! - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) - if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use? - return false; // Can't use this reg then. - return true; -} - - -/// getFreeReg - Look to see if there is a free register available in the -/// specified register class. If not, return 0. -/// -unsigned RABigBlock::getFreeReg(const TargetRegisterClass *RC) { - // Get iterators defining the range of registers that are valid to allocate in - // this class, which also specifies the preferred allocation order. - TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); - TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); - - for (; RI != RE; ++RI) - if (isPhysRegAvailable(*RI)) { // Is reg unused? - assert(*RI != 0 && "Cannot use register!"); - return *RI; // Found an unused register! - } - return 0; -} - - -/// chooseReg - Pick a physical register to hold the specified -/// virtual register by choosing the one whose value will be read -/// furthest in the future. -/// -unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, - unsigned VirtReg) { - const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); - // First check to see if we have a free register of the requested type... - unsigned PhysReg = getFreeReg(RC); - - // If we didn't find an unused register, find the one which will be - // read at the most distant point in time. - if (PhysReg == 0) { - unsigned delay=0, longest_delay=0; - VRegTimes* ReadTimes; - - unsigned curTime = MBBCurTime; - - // for all physical regs in the RC, - for(TargetRegisterClass::iterator pReg = RC->begin(); - pReg != RC->end(); ++pReg) { - // how long until they're read? - if(PhysRegsUsed[*pReg]>0) { // ignore non-allocatable regs - ReadTimes = VRegReadTable[PhysRegsUsed[*pReg]]; - if(ReadTimes && !ReadTimes->empty()) { - unsigned& pt = VRegReadIdx[PhysRegsUsed[*pReg]]; - while(pt < ReadTimes->size() && (*ReadTimes)[pt] < curTime) { - ++pt; - } - - if(pt < ReadTimes->size()) - delay = (*ReadTimes)[pt] - curTime; - else - delay = MBBLastInsnTime + 1 - curTime; - } else { - // This register is only defined, but never - // read in this MBB. Therefore the next read - // happens after the end of this MBB - delay = MBBLastInsnTime + 1 - curTime; - } - - - if(delay > longest_delay) { - longest_delay = delay; - PhysReg = *pReg; - } - } - } - - if(PhysReg == 0) { // ok, now we're desperate. We couldn't choose - // a register to spill by looking through the - // read timetable, so now we just spill the - // first allocatable register we find. - - // for all physical regs in the RC, - for(TargetRegisterClass::iterator pReg = RC->begin(); - pReg != RC->end(); ++pReg) { - // if we find a register we can spill - if(PhysRegsUsed[*pReg]>=-1) - PhysReg = *pReg; // choose it to be spilled - } - } - - assert(PhysReg && "couldn't choose a register to spill :( "); - // TODO: assert that RC->contains(PhysReg) / handle aliased registers? - - // since we needed to look in the table we need to spill this register. - spillPhysReg(MBB, I, PhysReg); - } - - // assign the vreg to our chosen physical register - assignVirtToPhysReg(VirtReg, PhysReg); - return PhysReg; // and return it -} - - -/// reloadVirtReg - This method transforms an instruction with a virtual -/// register use to one that references a physical register. It does this as -/// follows: -/// -/// 1) If the register is already in a physical register, it uses it. -/// 2) Otherwise, if there is a free physical register, it uses that. -/// 3) Otherwise, it calls chooseReg() to get the physical register -/// holding the most distantly needed value, generating a spill in -/// the process. -/// -/// This method returns the modified instruction. -MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned OpNum) { - unsigned VirtReg = MI->getOperand(OpNum).getReg(); - const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); - - // If the virtual register is already available in a physical register, - // just update the instruction and return. - if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) { - MI->getOperand(OpNum).setReg(PR); - return MI; - } - - // Otherwise, if we have free physical registers available to hold the - // value, use them. - const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); - unsigned PhysReg = getFreeReg(RC); - int FrameIndex = getStackSpaceFor(VirtReg, RC); - - if (PhysReg) { // we have a free register, so use it. - assignVirtToPhysReg(VirtReg, PhysReg); - } else { // no free registers available. - // try to fold the spill into the instruction - SmallVector<unsigned, 1> Ops; - Ops.push_back(OpNum); - if(MachineInstr* FMI = TII->foldMemoryOperand(*MF, MI, Ops, FrameIndex)) { - ++NumFolded; - FMI->copyKillDeadInfo(MI); - return MBB.insert(MBB.erase(MI), FMI); - } - - // determine which of the physical registers we'll kill off, since we - // couldn't fold. - PhysReg = chooseReg(MBB, MI, VirtReg); - } - - // this virtual register is now unmodified (since we just reloaded it) - markVirtRegModified(VirtReg, false); - - DOUT << " Reloading %reg" << VirtReg << " into " - << RegInfo->getName(PhysReg) << "\n"; - - // Add move instruction(s) - TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); - ++NumLoads; // Update statistics - - MF->getRegInfo().setPhysRegUsed(PhysReg); - MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register - return MI; -} - -/// Fill out the vreg read timetable. Since ReadTime increases -/// monotonically, the individual readtime sets will be sorted -/// in ascending order. -void RABigBlock::FillVRegReadTable(MachineBasicBlock &MBB) { - // loop over each instruction - MachineBasicBlock::iterator MII; - unsigned ReadTime; - - for(ReadTime=0, MII = MBB.begin(); MII != MBB.end(); ++ReadTime, ++MII) { - MachineInstr *MI = MII; - - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& MO = MI->getOperand(i); - // look for vreg reads.. - if (MO.isReg() && !MO.isDef() && MO.getReg() && - TargetRegisterInfo::isVirtualRegister(MO.getReg())) { - // ..and add them to the read table. - VRegTimes* &Times = VRegReadTable[MO.getReg()]; - if(!VRegReadTable[MO.getReg()]) { - Times = new VRegTimes; - VRegReadIdx[MO.getReg()] = 0; - } - Times->push_back(ReadTime); - } - } - - } - - MBBLastInsnTime = ReadTime; - - for(DenseMap<unsigned, VRegTimes*, VRegKeyInfo>::iterator Reads = VRegReadTable.begin(); - Reads != VRegReadTable.end(); ++Reads) { - if(Reads->second) { - DOUT << "Reads[" << Reads->first << "]=" << Reads->second->size() << "\n"; - } - } -} - -/// isReadModWriteImplicitKill - True if this is an implicit kill for a -/// read/mod/write register, i.e. update partial register. -static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() && - MO.isDef() && !MO.isDead()) - return true; - } - return false; -} - -/// isReadModWriteImplicitDef - True if this is an implicit def for a -/// read/mod/write register, i.e. update partial register. -static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() && - !MO.isDef() && MO.isKill()) - return true; - } - return false; -} - - -void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { - // loop over each instruction - MachineBasicBlock::iterator MII = MBB.begin(); - const TargetInstrInfo &TII = *TM->getInstrInfo(); - - DEBUG(const BasicBlock *LBB = MBB.getBasicBlock(); - if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName()); - - // If this is the first basic block in the machine function, add live-in - // registers as active. - if (&MBB == &*MF->begin()) { - for (MachineRegisterInfo::livein_iterator - I = MF->getRegInfo().livein_begin(), - E = MF->getRegInfo().livein_end(); I != E; ++I) { - unsigned Reg = I->first; - MF->getRegInfo().setPhysRegUsed(Reg); - PhysRegsUsed[Reg] = 0; // It is free and reserved now - for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->getRegInfo().setPhysRegUsed(*AliasSet); - } - } - } - } - - // Otherwise, sequentially allocate each instruction in the MBB. - MBBCurTime = -1; - while (MII != MBB.end()) { - MachineInstr *MI = MII++; - MBBCurTime++; - const TargetInstrDesc &TID = MI->getDesc(); - DEBUG(DOUT << "\nTime=" << MBBCurTime << " Starting RegAlloc of: " << *MI; - DOUT << " Regs have values: "; - for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) - DOUT << "[" << RegInfo->getName(i) - << ",%reg" << PhysRegsUsed[i] << "] "; - DOUT << "\n"); - - SmallVector<unsigned, 8> Kills; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (MO.isReg() && MO.isKill()) { - if (!MO.isImplicit()) - Kills.push_back(MO.getReg()); - else if (!isReadModWriteImplicitKill(MI, MO.getReg())) - // These are extra physical register kills when a sub-register - // is defined (def of a sub-register is a read/mod/write of the - // larger registers). Ignore. - Kills.push_back(MO.getReg()); - } - } - - // Get the used operands into registers. This has the potential to spill - // incoming values if we are out of registers. Note that we completely - // ignore physical register uses here. We assume that if an explicit - // physical register is referenced by the instruction, that it is guaranteed - // to be live-in, or the input is badly hosed. - // - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& MO = MI->getOperand(i); - // here we are looking for only used operands (never def&use) - if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && - TargetRegisterInfo::isVirtualRegister(MO.getReg())) - MI = reloadVirtReg(MBB, MI, i); - } - - // If this instruction is the last user of this register, kill the - // value, freeing the register being used, so it doesn't need to be - // spilled to memory. - // - for (unsigned i = 0, e = Kills.size(); i != e; ++i) { - unsigned VirtReg = Kills[i]; - unsigned PhysReg = VirtReg; - if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { - // If the virtual register was never materialized into a register, it - // might not be in the map, but it won't hurt to zero it out anyway. - unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); - PhysReg = PhysRegSlot; - PhysRegSlot = 0; - } else if (PhysRegsUsed[PhysReg] == -2) { - // Unallocatable register dead, ignore. - continue; - } else { - assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) && - "Silently clearing a virtual register?"); - } - - if (PhysReg) { - DOUT << " Last use of " << RegInfo->getName(PhysReg) - << "[%reg" << VirtReg <<"], removing it from live set\n"; - removePhysReg(PhysReg); - for (const unsigned *AliasSet = RegInfo->getSubRegisters(PhysReg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] != -2) { - DOUT << " Last use of " - << RegInfo->getName(*AliasSet) - << "[%reg" << VirtReg <<"], removing it from live set\n"; - removePhysReg(*AliasSet); - } - } - } - } - - // Loop over all of the operands of the instruction, spilling registers that - // are defined, and marking explicit destinations in the PhysRegsUsed map. - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (MO.isReg() && MO.isDef() && !MO.isImplicit() && MO.getReg() && - TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { - unsigned Reg = MO.getReg(); - if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. - // These are extra physical register defs when a sub-register - // is defined (def of a sub-register is a read/mod/write of the - // larger registers). Ignore. - if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; - - MF->getRegInfo().setPhysRegUsed(Reg); - spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg - PhysRegsUsed[Reg] = 0; // It is free and reserved now - for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->getRegInfo().setPhysRegUsed(*AliasSet); - } - } - } - } - - // Loop over the implicit defs, spilling them as well. - if (TID.getImplicitDefs()) { - for (const unsigned *ImplicitDefs = TID.getImplicitDefs(); - *ImplicitDefs; ++ImplicitDefs) { - unsigned Reg = *ImplicitDefs; - if (PhysRegsUsed[Reg] != -2) { - spillPhysReg(MBB, MI, Reg, true); - PhysRegsUsed[Reg] = 0; // It is free and reserved now - } - MF->getRegInfo().setPhysRegUsed(Reg); - for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->getRegInfo().setPhysRegUsed(*AliasSet); - } - } - } - } - - SmallVector<unsigned, 8> DeadDefs; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (MO.isReg() && MO.isDead()) - DeadDefs.push_back(MO.getReg()); - } - - // Okay, we have allocated all of the source operands and spilled any values - // that would be destroyed by defs of this instruction. Loop over the - // explicit defs and assign them to a register, spilling incoming values if - // we need to scavenge a register. - // - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (MO.isReg() && MO.isDef() && MO.getReg() && - TargetRegisterInfo::isVirtualRegister(MO.getReg())) { - unsigned DestVirtReg = MO.getReg(); - unsigned DestPhysReg; - - // If DestVirtReg already has a value, use it. - if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) - DestPhysReg = chooseReg(MBB, MI, DestVirtReg); - MF->getRegInfo().setPhysRegUsed(DestPhysReg); - markVirtRegModified(DestVirtReg); - MI->getOperand(i).setReg(DestPhysReg); // Assign the output register - } - } - - // If this instruction defines any registers that are immediately dead, - // kill them now. - // - for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) { - unsigned VirtReg = DeadDefs[i]; - unsigned PhysReg = VirtReg; - if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { - unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); - PhysReg = PhysRegSlot; - assert(PhysReg != 0); - PhysRegSlot = 0; - } else if (PhysRegsUsed[PhysReg] == -2) { - // Unallocatable register dead, ignore. - continue; - } - - if (PhysReg) { - DOUT << " Register " << RegInfo->getName(PhysReg) - << " [%reg" << VirtReg - << "] is never used, removing it from live set\n"; - removePhysReg(PhysReg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] != -2) { - DOUT << " Register " << RegInfo->getName(*AliasSet) - << " [%reg" << *AliasSet - << "] is never used, removing it from live set\n"; - removePhysReg(*AliasSet); - } - } - } - } - - // Finally, if this is a noop copy instruction, zap it. - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (TII.isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - SrcReg == DstReg) - MBB.erase(MI); - } - - MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); - - // Spill all physical registers holding virtual registers now. - for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) { - if (unsigned VirtReg = PhysRegsUsed[i]) - spillVirtReg(MBB, MI, VirtReg, i); - else - removePhysReg(i); - } -} - -/// runOnMachineFunction - Register allocate the whole function -/// -bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) { - DOUT << "Machine Function " << "\n"; - MF = &Fn; - TM = &Fn.getTarget(); - RegInfo = TM->getRegisterInfo(); - - PhysRegsUsed.assign(RegInfo->getNumRegs(), -1); - - // At various places we want to efficiently check to see whether a register - // is allocatable. To handle this, we mark all unallocatable registers as - // being pinned down, permanently. - { - BitVector Allocable = RegInfo->getAllocatableSet(Fn); - for (unsigned i = 0, e = Allocable.size(); i != e; ++i) - if (!Allocable[i]) - PhysRegsUsed[i] = -2; // Mark the reg unallocable. - } - - // initialize the virtual->physical register map to have a 'null' - // mapping for all virtual registers - Virt2PhysRegMap.grow(MF->getRegInfo().getLastVirtReg()); - StackSlotForVirtReg.grow(MF->getRegInfo().getLastVirtReg()); - VirtRegModified.resize(MF->getRegInfo().getLastVirtReg() - - TargetRegisterInfo::FirstVirtualRegister + 1, 0); - - // Loop over all of the basic blocks, eliminating virtual register references - for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); - MBB != MBBe; ++MBB) { - // fill out the read timetable - FillVRegReadTable(*MBB); - // use it to allocate the BB - AllocateBasicBlock(*MBB); - // clear it - VRegReadTable.clear(); - } - - StackSlotForVirtReg.clear(); - PhysRegsUsed.clear(); - VirtRegModified.clear(); - Virt2PhysRegMap.clear(); - return true; -} - -FunctionPass *llvm::createBigBlockRegisterAllocator() { - return new RABigBlock(); -} - diff --git a/lib/CodeGen/RegAllocSimple.cpp b/lib/CodeGen/RegAllocSimple.cpp deleted file mode 100644 index 447e54c..0000000 --- a/lib/CodeGen/RegAllocSimple.cpp +++ /dev/null @@ -1,257 +0,0 @@ -//===-- RegAllocSimple.cpp - A simple generic register allocator ----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements a simple register allocator. *Very* simple: It immediate -// spills every value right after it is computed, and it reloads all used -// operands from the spill area to temporary registers before each instruction. -// It does not keep values in registers across instructions. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "regalloc" -#include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Compiler.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" -#include <map> -using namespace llvm; - -STATISTIC(NumStores, "Number of stores added"); -STATISTIC(NumLoads , "Number of loads added"); - -namespace { - static RegisterRegAlloc - simpleRegAlloc("simple", "simple register allocator", - createSimpleRegisterAllocator); - - class VISIBILITY_HIDDEN RegAllocSimple : public MachineFunctionPass { - public: - static char ID; - RegAllocSimple() : MachineFunctionPass(&ID) {} - private: - MachineFunction *MF; - const TargetMachine *TM; - const TargetRegisterInfo *TRI; - const TargetInstrInfo *TII; - - // StackSlotForVirtReg - Maps SSA Regs => frame index on the stack where - // these values are spilled - std::map<unsigned, int> StackSlotForVirtReg; - - // RegsUsed - Keep track of what registers are currently in use. This is a - // bitset. - std::vector<bool> RegsUsed; - - // RegClassIdx - Maps RegClass => which index we can take a register - // from. Since this is a simple register allocator, when we need a register - // of a certain class, we just take the next available one. - std::map<const TargetRegisterClass*, unsigned> RegClassIdx; - - public: - virtual const char *getPassName() const { - return "Simple Register Allocator"; - } - - /// runOnMachineFunction - Register allocate the whole function - bool runOnMachineFunction(MachineFunction &Fn); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredID(PHIEliminationID); // Eliminate PHI nodes - MachineFunctionPass::getAnalysisUsage(AU); - } - private: - /// AllocateBasicBlock - Register allocate the specified basic block. - void AllocateBasicBlock(MachineBasicBlock &MBB); - - /// getStackSpaceFor - This returns the offset of the specified virtual - /// register on the stack, allocating space if necessary. - int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); - - /// Given a virtual register, return a compatible physical register that is - /// currently unused. - /// - /// Side effect: marks that register as being used until manually cleared - /// - unsigned getFreeReg(unsigned virtualReg); - - /// Moves value from memory into that register - unsigned reloadVirtReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator I, unsigned VirtReg); - - /// Saves reg value on the stack (maps virtual register to stack value) - void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, - unsigned VirtReg, unsigned PhysReg); - }; - char RegAllocSimple::ID = 0; -} - -/// getStackSpaceFor - This allocates space for the specified virtual -/// register to be held on the stack. -int RegAllocSimple::getStackSpaceFor(unsigned VirtReg, - const TargetRegisterClass *RC) { - // Find the location VirtReg would belong... - std::map<unsigned, int>::iterator I = StackSlotForVirtReg.find(VirtReg); - - if (I != StackSlotForVirtReg.end()) - return I->second; // Already has space allocated? - - // Allocate a new stack object for this spill location... - int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), - RC->getAlignment()); - - // Assign the slot... - StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx)); - - return FrameIdx; -} - -unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) { - const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtualReg); - TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); -#ifndef NDEBUG - TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); -#endif - - while (1) { - unsigned regIdx = RegClassIdx[RC]++; - assert(RI+regIdx != RE && "Not enough registers!"); - unsigned PhysReg = *(RI+regIdx); - - if (!RegsUsed[PhysReg]) { - MF->getRegInfo().setPhysRegUsed(PhysReg); - return PhysReg; - } - } -} - -unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator I, - unsigned VirtReg) { - const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(VirtReg); - int FrameIdx = getStackSpaceFor(VirtReg, RC); - unsigned PhysReg = getFreeReg(VirtReg); - - // Add move instruction(s) - ++NumLoads; - TII->loadRegFromStackSlot(MBB, I, PhysReg, FrameIdx, RC); - return PhysReg; -} - -void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator I, - unsigned VirtReg, unsigned PhysReg) { - const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(VirtReg); - - int FrameIdx = getStackSpaceFor(VirtReg, RC); - - // Add move instruction(s) - ++NumStores; - TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIdx, RC); -} - - -void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) { - // loop over each instruction - for (MachineBasicBlock::iterator MI = MBB.begin(); MI != MBB.end(); ++MI) { - // Made to combat the incorrect allocation of r2 = add r1, r1 - std::map<unsigned, unsigned> Virt2PhysRegMap; - - RegsUsed.resize(TRI->getNumRegs()); - - // This is a preliminary pass that will invalidate any registers that are - // used by the instruction (including implicit uses). - const TargetInstrDesc &Desc = MI->getDesc(); - const unsigned *Regs; - if (Desc.ImplicitUses) { - for (Regs = Desc.ImplicitUses; *Regs; ++Regs) - RegsUsed[*Regs] = true; - } - - if (Desc.ImplicitDefs) { - for (Regs = Desc.ImplicitDefs; *Regs; ++Regs) { - RegsUsed[*Regs] = true; - MF->getRegInfo().setPhysRegUsed(*Regs); - } - } - - // Loop over uses, move from memory into registers. - for (int i = MI->getNumOperands() - 1; i >= 0; --i) { - MachineOperand &MO = MI->getOperand(i); - - if (MO.isReg() && MO.getReg() && - TargetRegisterInfo::isVirtualRegister(MO.getReg())) { - unsigned virtualReg = (unsigned) MO.getReg(); - DOUT << "op: " << MO << "\n"; - DOUT << "\t inst[" << i << "]: "; - DEBUG(MI->print(*cerr.stream(), TM)); - - // make sure the same virtual register maps to the same physical - // register in any given instruction - unsigned physReg = Virt2PhysRegMap[virtualReg]; - if (physReg == 0) { - if (MO.isDef()) { - unsigned TiedOp; - if (!MI->isRegTiedToUseOperand(i, &TiedOp)) { - physReg = getFreeReg(virtualReg); - } else { - // must be same register number as the source operand that is - // tied to. This maps a = b + c into b = b + c, and saves b into - // a's spot. - assert(MI->getOperand(TiedOp).isReg() && - MI->getOperand(TiedOp).getReg() && - MI->getOperand(TiedOp).isUse() && - "Two address instruction invalid!"); - - physReg = MI->getOperand(TiedOp).getReg(); - } - spillVirtReg(MBB, next(MI), virtualReg, physReg); - } else { - physReg = reloadVirtReg(MBB, MI, virtualReg); - Virt2PhysRegMap[virtualReg] = physReg; - } - } - MO.setReg(physReg); - DOUT << "virt: " << virtualReg << ", phys: " << MO.getReg() << "\n"; - } - } - RegClassIdx.clear(); - RegsUsed.clear(); - } -} - - -/// runOnMachineFunction - Register allocate the whole function -/// -bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) { - DOUT << "Machine Function\n"; - MF = &Fn; - TM = &MF->getTarget(); - TRI = TM->getRegisterInfo(); - TII = TM->getInstrInfo(); - - // Loop over all of the basic blocks, eliminating virtual register references - for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); - MBB != MBBe; ++MBB) - AllocateBasicBlock(*MBB); - - StackSlotForVirtReg.clear(); - return true; -} - -FunctionPass *llvm::createSimpleRegisterAllocator() { - return new RegAllocSimple(); -} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp deleted file mode 100644 index 7926339..0000000 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp +++ /dev/null @@ -1,671 +0,0 @@ -//===---- ScheduleDAGEmit.cpp - Emit routines for the ScheduleDAG class ---===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This implements the Emit routines for the ScheduleDAG class, which creates -// MachineInstrs according to the computed schedule. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "pre-RA-sched" -#include "ScheduleDAGSDNodes.h" -#include "llvm/CodeGen/MachineConstantPool.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineInstrBuilder.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/MathExtras.h" -using namespace llvm; - -/// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an -/// implicit physical register output. -void ScheduleDAGSDNodes:: -EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, bool IsCloned, - unsigned SrcReg, DenseMap<SDValue, unsigned> &VRBaseMap) { - unsigned VRBase = 0; - if (TargetRegisterInfo::isVirtualRegister(SrcReg)) { - // Just use the input register directly! - SDValue Op(Node, ResNo); - if (IsClone) - VRBaseMap.erase(Op); - bool isNew = VRBaseMap.insert(std::make_pair(Op, SrcReg)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); - return; - } - - // If the node is only used by a CopyToReg and the dest reg is a vreg, use - // the CopyToReg'd destination register instead of creating a new vreg. - bool MatchReg = true; - const TargetRegisterClass *UseRC = NULL; - if (!IsClone && !IsCloned) - for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); - UI != E; ++UI) { - SDNode *User = *UI; - bool Match = true; - if (User->getOpcode() == ISD::CopyToReg && - User->getOperand(2).getNode() == Node && - User->getOperand(2).getResNo() == ResNo) { - unsigned DestReg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); - if (TargetRegisterInfo::isVirtualRegister(DestReg)) { - VRBase = DestReg; - Match = false; - } else if (DestReg != SrcReg) - Match = false; - } else { - for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) { - SDValue Op = User->getOperand(i); - if (Op.getNode() != Node || Op.getResNo() != ResNo) - continue; - MVT VT = Node->getValueType(Op.getResNo()); - if (VT == MVT::Other || VT == MVT::Flag) - continue; - Match = false; - if (User->isMachineOpcode()) { - const TargetInstrDesc &II = TII->get(User->getMachineOpcode()); - const TargetRegisterClass *RC = - getInstrOperandRegClass(TRI, II, i+II.getNumDefs()); - if (!UseRC) - UseRC = RC; - else if (RC) { - if (UseRC->hasSuperClass(RC)) - UseRC = RC; - else - assert((UseRC == RC || RC->hasSuperClass(UseRC)) && - "Multiple uses expecting different register classes!"); - } - } - } - } - MatchReg &= Match; - if (VRBase) - break; - } - - MVT VT = Node->getValueType(ResNo); - const TargetRegisterClass *SrcRC = 0, *DstRC = 0; - SrcRC = TRI->getPhysicalRegisterRegClass(SrcReg, VT); - - // Figure out the register class to create for the destreg. - if (VRBase) { - DstRC = MRI.getRegClass(VRBase); - } else if (UseRC) { - assert(UseRC->hasType(VT) && "Incompatible phys register def and uses!"); - DstRC = UseRC; - } else { - DstRC = TLI->getRegClassFor(VT); - } - - // If all uses are reading from the src physical register and copying the - // register is either impossible or very expensive, then don't create a copy. - if (MatchReg && SrcRC->getCopyCost() < 0) { - VRBase = SrcReg; - } else { - // Create the reg, emit the copy. - VRBase = MRI.createVirtualRegister(DstRC); - bool Emitted = TII->copyRegToReg(*BB, InsertPos, VRBase, SrcReg, - DstRC, SrcRC); - - assert(Emitted && "Unable to issue a copy instruction!\n"); - (void) Emitted; - } - - SDValue Op(Node, ResNo); - if (IsClone) - VRBaseMap.erase(Op); - bool isNew = VRBaseMap.insert(std::make_pair(Op, VRBase)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); -} - -/// getDstOfCopyToRegUse - If the only use of the specified result number of -/// node is a CopyToReg, return its destination register. Return 0 otherwise. -unsigned ScheduleDAGSDNodes::getDstOfOnlyCopyToRegUse(SDNode *Node, - unsigned ResNo) const { - if (!Node->hasOneUse()) - return 0; - - SDNode *User = *Node->use_begin(); - if (User->getOpcode() == ISD::CopyToReg && - User->getOperand(2).getNode() == Node && - User->getOperand(2).getResNo() == ResNo) { - unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); - if (TargetRegisterInfo::isVirtualRegister(Reg)) - return Reg; - } - return 0; -} - -void ScheduleDAGSDNodes::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, - const TargetInstrDesc &II, - bool IsClone, bool IsCloned, - DenseMap<SDValue, unsigned> &VRBaseMap) { - assert(Node->getMachineOpcode() != TargetInstrInfo::IMPLICIT_DEF && - "IMPLICIT_DEF should have been handled as a special case elsewhere!"); - - for (unsigned i = 0; i < II.getNumDefs(); ++i) { - // If the specific node value is only used by a CopyToReg and the dest reg - // is a vreg in the same register class, use the CopyToReg'd destination - // register instead of creating a new vreg. - unsigned VRBase = 0; - const TargetRegisterClass *RC = getInstrOperandRegClass(TRI, II, i); - - if (!IsClone && !IsCloned) - for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); - UI != E; ++UI) { - SDNode *User = *UI; - if (User->getOpcode() == ISD::CopyToReg && - User->getOperand(2).getNode() == Node && - User->getOperand(2).getResNo() == i) { - unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); - if (TargetRegisterInfo::isVirtualRegister(Reg)) { - const TargetRegisterClass *RegRC = MRI.getRegClass(Reg); - if (RegRC == RC) { - VRBase = Reg; - MI->addOperand(MachineOperand::CreateReg(Reg, true)); - break; - } - } - } - } - - // Create the result registers for this node and add the result regs to - // the machine instruction. - if (VRBase == 0) { - assert(RC && "Isn't a register operand!"); - VRBase = MRI.createVirtualRegister(RC); - MI->addOperand(MachineOperand::CreateReg(VRBase, true)); - } - - SDValue Op(Node, i); - if (IsClone) - VRBaseMap.erase(Op); - bool isNew = VRBaseMap.insert(std::make_pair(Op, VRBase)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); - } -} - -/// getVR - Return the virtual register corresponding to the specified result -/// of the specified node. -unsigned ScheduleDAGSDNodes::getVR(SDValue Op, - DenseMap<SDValue, unsigned> &VRBaseMap) { - if (Op.isMachineOpcode() && - Op.getMachineOpcode() == TargetInstrInfo::IMPLICIT_DEF) { - // Add an IMPLICIT_DEF instruction before every use. - unsigned VReg = getDstOfOnlyCopyToRegUse(Op.getNode(), Op.getResNo()); - // IMPLICIT_DEF can produce any type of result so its TargetInstrDesc - // does not include operand register class info. - if (!VReg) { - const TargetRegisterClass *RC = TLI->getRegClassFor(Op.getValueType()); - VReg = MRI.createVirtualRegister(RC); - } - BuildMI(BB, Op.getDebugLoc(), TII->get(TargetInstrInfo::IMPLICIT_DEF),VReg); - return VReg; - } - - DenseMap<SDValue, unsigned>::iterator I = VRBaseMap.find(Op); - assert(I != VRBaseMap.end() && "Node emitted out of order - late"); - return I->second; -} - - -/// AddRegisterOperand - Add the specified register as an operand to the -/// specified machine instr. Insert register copies if the register is -/// not in the required register class. -void -ScheduleDAGSDNodes::AddRegisterOperand(MachineInstr *MI, SDValue Op, - unsigned IIOpNum, - const TargetInstrDesc *II, - DenseMap<SDValue, unsigned> &VRBaseMap) { - assert(Op.getValueType() != MVT::Other && - Op.getValueType() != MVT::Flag && - "Chain and flag operands should occur at end of operand list!"); - // Get/emit the operand. - unsigned VReg = getVR(Op, VRBaseMap); - assert(TargetRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?"); - - const TargetInstrDesc &TID = MI->getDesc(); - bool isOptDef = IIOpNum < TID.getNumOperands() && - TID.OpInfo[IIOpNum].isOptionalDef(); - - // If the instruction requires a register in a different class, create - // a new virtual register and copy the value into it. - if (II) { - const TargetRegisterClass *SrcRC = - MRI.getRegClass(VReg); - const TargetRegisterClass *DstRC = - getInstrOperandRegClass(TRI, *II, IIOpNum); - assert((DstRC || (TID.isVariadic() && IIOpNum >= TID.getNumOperands())) && - "Don't have operand info for this instruction!"); - if (DstRC && SrcRC != DstRC && !SrcRC->hasSuperClass(DstRC)) { - unsigned NewVReg = MRI.createVirtualRegister(DstRC); - bool Emitted = TII->copyRegToReg(*BB, InsertPos, NewVReg, VReg, - DstRC, SrcRC); - assert(Emitted && "Unable to issue a copy instruction!\n"); - (void) Emitted; - VReg = NewVReg; - } - } - - MI->addOperand(MachineOperand::CreateReg(VReg, isOptDef)); -} - -/// AddOperand - Add the specified operand to the specified machine instr. II -/// specifies the instruction information for the node, and IIOpNum is the -/// operand number (in the II) that we are adding. IIOpNum and II are used for -/// assertions only. -void ScheduleDAGSDNodes::AddOperand(MachineInstr *MI, SDValue Op, - unsigned IIOpNum, - const TargetInstrDesc *II, - DenseMap<SDValue, unsigned> &VRBaseMap) { - if (Op.isMachineOpcode()) { - AddRegisterOperand(MI, Op, IIOpNum, II, VRBaseMap); - } else if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateImm(C->getZExtValue())); - } else if (ConstantFPSDNode *F = dyn_cast<ConstantFPSDNode>(Op)) { - const ConstantFP *CFP = F->getConstantFPValue(); - MI->addOperand(MachineOperand::CreateFPImm(CFP)); - } else if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateReg(R->getReg(), false)); - } else if (GlobalAddressSDNode *TGA = dyn_cast<GlobalAddressSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateGA(TGA->getGlobal(), TGA->getOffset(), - TGA->getTargetFlags())); - } else if (BasicBlockSDNode *BBNode = dyn_cast<BasicBlockSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateMBB(BBNode->getBasicBlock())); - } else if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateFI(FI->getIndex())); - } else if (JumpTableSDNode *JT = dyn_cast<JumpTableSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateJTI(JT->getIndex(), - JT->getTargetFlags())); - } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Op)) { - int Offset = CP->getOffset(); - unsigned Align = CP->getAlignment(); - const Type *Type = CP->getType(); - // MachineConstantPool wants an explicit alignment. - if (Align == 0) { - Align = TM.getTargetData()->getPrefTypeAlignment(Type); - if (Align == 0) { - // Alignment of vector types. FIXME! - Align = TM.getTargetData()->getTypeAllocSize(Type); - } - } - - unsigned Idx; - if (CP->isMachineConstantPoolEntry()) - Idx = ConstPool->getConstantPoolIndex(CP->getMachineCPVal(), Align); - else - Idx = ConstPool->getConstantPoolIndex(CP->getConstVal(), Align); - MI->addOperand(MachineOperand::CreateCPI(Idx, Offset, - CP->getTargetFlags())); - } else if (ExternalSymbolSDNode *ES = dyn_cast<ExternalSymbolSDNode>(Op)) { - MI->addOperand(MachineOperand::CreateES(ES->getSymbol(), 0, - ES->getTargetFlags())); - } else { - assert(Op.getValueType() != MVT::Other && - Op.getValueType() != MVT::Flag && - "Chain and flag operands should occur at end of operand list!"); - AddRegisterOperand(MI, Op, IIOpNum, II, VRBaseMap); - } -} - -/// getSuperRegisterRegClass - Returns the register class of a superreg A whose -/// "SubIdx"'th sub-register class is the specified register class and whose -/// type matches the specified type. -static const TargetRegisterClass* -getSuperRegisterRegClass(const TargetRegisterClass *TRC, - unsigned SubIdx, MVT VT) { - // Pick the register class of the superegister for this type - for (TargetRegisterInfo::regclass_iterator I = TRC->superregclasses_begin(), - E = TRC->superregclasses_end(); I != E; ++I) - if ((*I)->hasType(VT) && (*I)->getSubRegisterRegClass(SubIdx) == TRC) - return *I; - assert(false && "Couldn't find the register class"); - return 0; -} - -/// EmitSubregNode - Generate machine code for subreg nodes. -/// -void ScheduleDAGSDNodes::EmitSubregNode(SDNode *Node, - DenseMap<SDValue, unsigned> &VRBaseMap){ - unsigned VRBase = 0; - unsigned Opc = Node->getMachineOpcode(); - - // If the node is only used by a CopyToReg and the dest reg is a vreg, use - // the CopyToReg'd destination register instead of creating a new vreg. - for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); - UI != E; ++UI) { - SDNode *User = *UI; - if (User->getOpcode() == ISD::CopyToReg && - User->getOperand(2).getNode() == Node) { - unsigned DestReg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); - if (TargetRegisterInfo::isVirtualRegister(DestReg)) { - VRBase = DestReg; - break; - } - } - } - - if (Opc == TargetInstrInfo::EXTRACT_SUBREG) { - unsigned SubIdx = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue(); - - // Create the extract_subreg machine instruction. - MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(), - TII->get(TargetInstrInfo::EXTRACT_SUBREG)); - - // Figure out the register class to create for the destreg. - unsigned VReg = getVR(Node->getOperand(0), VRBaseMap); - const TargetRegisterClass *TRC = MRI.getRegClass(VReg); - const TargetRegisterClass *SRC = TRC->getSubRegisterRegClass(SubIdx); - assert(SRC && "Invalid subregister index in EXTRACT_SUBREG"); - - // Figure out the register class to create for the destreg. - // Note that if we're going to directly use an existing register, - // it must be precisely the required class, and not a subclass - // thereof. - if (VRBase == 0 || SRC != MRI.getRegClass(VRBase)) { - // Create the reg - assert(SRC && "Couldn't find source register class"); - VRBase = MRI.createVirtualRegister(SRC); - } - - // Add def, source, and subreg index - MI->addOperand(MachineOperand::CreateReg(VRBase, true)); - AddOperand(MI, Node->getOperand(0), 0, 0, VRBaseMap); - MI->addOperand(MachineOperand::CreateImm(SubIdx)); - BB->insert(InsertPos, MI); - } else if (Opc == TargetInstrInfo::INSERT_SUBREG || - Opc == TargetInstrInfo::SUBREG_TO_REG) { - SDValue N0 = Node->getOperand(0); - SDValue N1 = Node->getOperand(1); - SDValue N2 = Node->getOperand(2); - unsigned SubReg = getVR(N1, VRBaseMap); - unsigned SubIdx = cast<ConstantSDNode>(N2)->getZExtValue(); - const TargetRegisterClass *TRC = MRI.getRegClass(SubReg); - const TargetRegisterClass *SRC = - getSuperRegisterRegClass(TRC, SubIdx, - Node->getValueType(0)); - - // Figure out the register class to create for the destreg. - // Note that if we're going to directly use an existing register, - // it must be precisely the required class, and not a subclass - // thereof. - if (VRBase == 0 || SRC != MRI.getRegClass(VRBase)) { - // Create the reg - assert(SRC && "Couldn't find source register class"); - VRBase = MRI.createVirtualRegister(SRC); - } - - // Create the insert_subreg or subreg_to_reg machine instruction. - MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(), TII->get(Opc)); - MI->addOperand(MachineOperand::CreateReg(VRBase, true)); - - // If creating a subreg_to_reg, then the first input operand - // is an implicit value immediate, otherwise it's a register - if (Opc == TargetInstrInfo::SUBREG_TO_REG) { - const ConstantSDNode *SD = cast<ConstantSDNode>(N0); - MI->addOperand(MachineOperand::CreateImm(SD->getZExtValue())); - } else - AddOperand(MI, N0, 0, 0, VRBaseMap); - // Add the subregster being inserted - AddOperand(MI, N1, 0, 0, VRBaseMap); - MI->addOperand(MachineOperand::CreateImm(SubIdx)); - BB->insert(InsertPos, MI); - } else - assert(0 && "Node is not insert_subreg, extract_subreg, or subreg_to_reg"); - - SDValue Op(Node, 0); - bool isNew = VRBaseMap.insert(std::make_pair(Op, VRBase)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); -} - -/// EmitCopyToRegClassNode - Generate machine code for COPY_TO_REGCLASS nodes. -/// COPY_TO_REGCLASS is just a normal copy, except that the destination -/// register is constrained to be in a particular register class. -/// -void -ScheduleDAGSDNodes::EmitCopyToRegClassNode(SDNode *Node, - DenseMap<SDValue, unsigned> &VRBaseMap) { - unsigned VReg = getVR(Node->getOperand(0), VRBaseMap); - const TargetRegisterClass *SrcRC = MRI.getRegClass(VReg); - - unsigned DstRCIdx = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue(); - const TargetRegisterClass *DstRC = TRI->getRegClass(DstRCIdx); - - // Create the new VReg in the destination class and emit a copy. - unsigned NewVReg = MRI.createVirtualRegister(DstRC); - bool Emitted = TII->copyRegToReg(*BB, InsertPos, NewVReg, VReg, - DstRC, SrcRC); - assert(Emitted && - "Unable to issue a copy instruction for a COPY_TO_REGCLASS node!\n"); - (void) Emitted; - - SDValue Op(Node, 0); - bool isNew = VRBaseMap.insert(std::make_pair(Op, NewVReg)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); -} - -/// EmitNode - Generate machine code for an node and needed dependencies. -/// -void ScheduleDAGSDNodes::EmitNode(SDNode *Node, bool IsClone, bool IsCloned, - DenseMap<SDValue, unsigned> &VRBaseMap) { - // If machine instruction - if (Node->isMachineOpcode()) { - unsigned Opc = Node->getMachineOpcode(); - - // Handle subreg insert/extract specially - if (Opc == TargetInstrInfo::EXTRACT_SUBREG || - Opc == TargetInstrInfo::INSERT_SUBREG || - Opc == TargetInstrInfo::SUBREG_TO_REG) { - EmitSubregNode(Node, VRBaseMap); - return; - } - - // Handle COPY_TO_REGCLASS specially. - if (Opc == TargetInstrInfo::COPY_TO_REGCLASS) { - EmitCopyToRegClassNode(Node, VRBaseMap); - return; - } - - if (Opc == TargetInstrInfo::IMPLICIT_DEF) - // We want a unique VR for each IMPLICIT_DEF use. - return; - - const TargetInstrDesc &II = TII->get(Opc); - unsigned NumResults = CountResults(Node); - unsigned NodeOperands = CountOperands(Node); - unsigned MemOperandsEnd = ComputeMemOperandsEnd(Node); - bool HasPhysRegOuts = (NumResults > II.getNumDefs()) && - II.getImplicitDefs() != 0; -#ifndef NDEBUG - unsigned NumMIOperands = NodeOperands + NumResults; - assert((II.getNumOperands() == NumMIOperands || - HasPhysRegOuts || II.isVariadic()) && - "#operands for dag node doesn't match .td file!"); -#endif - - // Create the new machine instruction. - MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(), II); - - // Add result register values for things that are defined by this - // instruction. - if (NumResults) - CreateVirtualRegisters(Node, MI, II, IsClone, IsCloned, VRBaseMap); - - // Emit all of the actual operands of this instruction, adding them to the - // instruction as appropriate. - for (unsigned i = 0; i != NodeOperands; ++i) - AddOperand(MI, Node->getOperand(i), i+II.getNumDefs(), &II, VRBaseMap); - - // Emit all of the memory operands of this instruction - for (unsigned i = NodeOperands; i != MemOperandsEnd; ++i) - AddMemOperand(MI, cast<MemOperandSDNode>(Node->getOperand(i))->MO); - - if (II.usesCustomDAGSchedInsertionHook()) { - // Insert this instruction into the basic block using a target - // specific inserter which may returns a new basic block. - BB = TLI->EmitInstrWithCustomInserter(MI, BB); - InsertPos = BB->end(); - } else { - BB->insert(InsertPos, MI); - } - - // Additional results must be an physical register def. - if (HasPhysRegOuts) { - for (unsigned i = II.getNumDefs(); i < NumResults; ++i) { - unsigned Reg = II.getImplicitDefs()[i - II.getNumDefs()]; - if (Node->hasAnyUseOfValue(i)) - EmitCopyFromReg(Node, i, IsClone, IsCloned, Reg, VRBaseMap); - } - } - return; - } - - switch (Node->getOpcode()) { - default: -#ifndef NDEBUG - Node->dump(DAG); -#endif - assert(0 && "This target-independent node should have been selected!"); - break; - case ISD::EntryToken: - assert(0 && "EntryToken should have been excluded from the schedule!"); - break; - case ISD::TokenFactor: // fall thru - break; - case ISD::CopyToReg: { - unsigned SrcReg; - SDValue SrcVal = Node->getOperand(2); - if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(SrcVal)) - SrcReg = R->getReg(); - else - SrcReg = getVR(SrcVal, VRBaseMap); - - unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg(); - if (SrcReg == DestReg) // Coalesced away the copy? Ignore. - break; - - const TargetRegisterClass *SrcTRC = 0, *DstTRC = 0; - // Get the register classes of the src/dst. - if (TargetRegisterInfo::isVirtualRegister(SrcReg)) - SrcTRC = MRI.getRegClass(SrcReg); - else - SrcTRC = TRI->getPhysicalRegisterRegClass(SrcReg,SrcVal.getValueType()); - - if (TargetRegisterInfo::isVirtualRegister(DestReg)) - DstTRC = MRI.getRegClass(DestReg); - else - DstTRC = TRI->getPhysicalRegisterRegClass(DestReg, - Node->getOperand(1).getValueType()); - - bool Emitted = TII->copyRegToReg(*BB, InsertPos, DestReg, SrcReg, - DstTRC, SrcTRC); - assert(Emitted && "Unable to issue a copy instruction!\n"); - (void) Emitted; - break; - } - case ISD::CopyFromReg: { - unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg(); - EmitCopyFromReg(Node, 0, IsClone, IsCloned, SrcReg, VRBaseMap); - break; - } - case ISD::INLINEASM: { - unsigned NumOps = Node->getNumOperands(); - if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag) - --NumOps; // Ignore the flag operand. - - // Create the inline asm machine instruction. - MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(), - TII->get(TargetInstrInfo::INLINEASM)); - - // Add the asm string as an external symbol operand. - const char *AsmStr = - cast<ExternalSymbolSDNode>(Node->getOperand(1))->getSymbol(); - MI->addOperand(MachineOperand::CreateES(AsmStr)); - - // Add all of the operand registers to the instruction. - for (unsigned i = 2; i != NumOps;) { - unsigned Flags = - cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue(); - unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags); - - MI->addOperand(MachineOperand::CreateImm(Flags)); - ++i; // Skip the ID value. - - switch (Flags & 7) { - default: assert(0 && "Bad flags!"); - case 2: // Def of register. - for (; NumVals; --NumVals, ++i) { - unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); - MI->addOperand(MachineOperand::CreateReg(Reg, true)); - } - break; - case 6: // Def of earlyclobber register. - for (; NumVals; --NumVals, ++i) { - unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); - MI->addOperand(MachineOperand::CreateReg(Reg, true, false, false, - false, false, true)); - } - break; - case 1: // Use of register. - case 3: // Immediate. - case 4: // Addressing mode. - // The addressing mode has been selected, just add all of the - // operands to the machine instruction. - for (; NumVals; --NumVals, ++i) - AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap); - break; - } - } - BB->insert(InsertPos, MI); - break; - } - } -} - -/// EmitSchedule - Emit the machine code in scheduled order. -MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { - DenseMap<SDValue, unsigned> VRBaseMap; - DenseMap<SUnit*, unsigned> CopyVRBaseMap; - for (unsigned i = 0, e = Sequence.size(); i != e; i++) { - SUnit *SU = Sequence[i]; - if (!SU) { - // Null SUnit* is a noop. - EmitNoop(); - continue; - } - - // For pre-regalloc scheduling, create instructions corresponding to the - // SDNode and any flagged SDNodes and append them to the block. - if (!SU->getNode()) { - // Emit a copy. - EmitPhysRegCopy(SU, CopyVRBaseMap); - continue; - } - - SmallVector<SDNode *, 4> FlaggedNodes; - for (SDNode *N = SU->getNode()->getFlaggedNode(); N; - N = N->getFlaggedNode()) - FlaggedNodes.push_back(N); - while (!FlaggedNodes.empty()) { - EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned,VRBaseMap); - FlaggedNodes.pop_back(); - } - EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap); - } - - return BB; -} |
