nsz Git - libfirm/blob - ir/be/becopyheur4.c

   1 /**
   2  * This is the C implementation of the trivial mst algo
   3  * originally written in Java by Sebastian Hack.
   4  * Performs simple copy minimzation.
   5  *
   6  * @author Christian Wuerdig
   7  * @date   27.04.2007
   8  * @id     $Id$
   9  */
  10
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif /* HAVE_CONFIG_H */
  14
  15 #include "array.h"
  16 #include "irnode.h"
  17 #include "bitset.h"
  18 #include "raw_bitset.h"
  19 #include "irphase_t.h"
  20
  21 #include "bearch.h"
  22 #include "beifg.h"
  23 #include "be_t.h"
  24
  25 typedef struct _aff_chunk_t {
  26         ir_node **nodes;
  27         int     weight;
  28 } aff_chunk_t;
  29
  30 typedef struct _aff_edge_t {
  31         ir_node *src;
  32         ir_node *tgt;
  33         double  weight;
  34 } aff_edge_t;
  35
  36 /* main coalescing environment*/
  37 typedef struct _co_mst_safe_env_t {
  38         int              n_regs;         /**< number of regs in class */
  39         int              k;              /**< number of non-ignore registers in class */
  40         bitset_t         *ignore_regs;   /**< set containing all global ignore registers */
  41         ir_phase         ph;             /**< phase object holding data for nodes */
  42         pqueue           *chunks;        /**< priority queue for chunks */
  43         be_ifg_t         *ifg;           /**< the interference graph */
  44         const arch_env_t *aenv;          /**< the arch environment */
  45 } co_mst_safe_env_t;
  46
  47 /* stores coalescing related information for a node */
  48 typedef struct _co_mst_safe_irn_t {
  49         ir_node     *irn;
  50         aff_chunk_t *chunk;
  51         bitset_t    *adm_colors;
  52         int         init_col;
  53         int         tmp_col;
  54         int         int_neigh;
  55         unsigned    fixed : 1;
  56 } co_mst_safe_irn_t;
  57
  58 #define get_co_mst_safe_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
  59
  60 /* compares two affinity edges */
  61 static int cmp_aff_edge(const void *a, const void *b) {
  62         const aff_edge_t * const *e1 = d1;
  63         const aff_edge_t * const *e2 = d2;
  64
  65         /* sort in descending order */
  66         return (*e1)->weight < (*e2)->weight ? 1 : -1;
  67 }
  68
  69 /**
  70  * In case there is no phase information for irn, initialize it.
  71  */
  72 static void *co_mst_safe_irn_init(ir_phase *ph, ir_node *irn, void *old) {
  73         co_mst_safe_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
  74         co_mst_safe_env_t *env = ph->priv;
  75
  76         if (res != old) {
  77                 void                      *neigh_it = be_ifg_neighbours_iter_alloca(env->ifg);
  78                 const arch_register_req_t *req;
  79                 ir_node                   *m;
  80
  81                 res->irn       = irn;
  82                 res->chunk     = NULL;
  83                 res->fixed     = 0;
  84                 res->tmp_col   = -1;
  85                 res->int_neigh = 0;
  86                 res->init_col  = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
  87
  88                 /* set admissible registers */
  89                 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
  90
  91                 /* Exclude colors not assignable to the irn */
  92                 req = arch_get_register_req(env->aenv, irn, -1);
  93                 if (arch_register_req_is(req, limited))
  94                         rbitset_copy_to_bitset(req->limited, res->adm_colors);
  95
  96                 /* exclude global ignore registers as well */
  97                 bitset_andnot(res->adm_colors, env->ignore_regs);
  98
  99                 /* calculate the number of interfering neigbours */
 100                 be_ifg_foreach_neighbour(env->ifg, neigh_it, irn, m) {
 101                         if (! arch_irn_is(env->aenv, m, ignore))
 102                                 res->int_neigh++;
 103                 }
 104
 105         }
 106
 107         return res;
 108 }
 109
 110 /**
 111  * Build chunks of nodes connected by affinity edges.
 112  * We start at the heaviest affinity edge.
 113  * The chunks of the two edge-defining nodes will be
 114  * merged if there are no interference edges from one
 115  * chunk to the other.
 116  */
 117 static void build_affinity_chunks(co_mst_safe_env_t *env) {
 118         void       *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
 119         aff_edge_t **edges   = NEW_ARR_F(aff_edge_t *, 0);
 120         int        i;
 121
 122         /* at first we create the affinity edge objects */
 123         be_ifg_foreach_node(env->ifg, nodes_it, n) {
 124                 int               n_idx = get_irn_idx(n);
 125                 co_mst_safe_irn_t *n1;
 126                 affinity_node_t   *an;
 127
 128                 if (arch_irn_is(env->aenv, n, ignore))
 129                         continue;
 130
 131                 n1 = get_co_mst_safe_irn(env, n);
 132                 an = get_affinity_info(co, n);
 133
 134                 if (an != NULL) {
 135                         neighb_t *neigh;
 136                         co_gs_foreach_neighb(an, neigh) {
 137                                 ir_node           *m    = neigh->irn;
 138                                 int               m_idx = get_irn_idx(m);
 139                                 co_mst_safe_irn_t *n2;
 140
 141                                 if (arch_irn_is(env->aenv, m, ignore))
 142                                         continue;
 143
 144                                 n2 = get_co_mst_safe_irn(env, m);
 145
 146                                 /* record the edge in only one direction and only to non-ignore nodes */
 147                                 if (n_idx < m_idx) {
 148                                         aff_edge_t *edge = phase_alloc(&env->ph, sizeof(*edge));
 149
 150                                         edge->src    = n;
 151                                         edge->tgt    = m;
 152                                         edge->weight = (double)neigh->cost / (double)(1 + n1->int_neigh + n2->int_neigh);
 153                                         ARR_APP1(aff_edge_t *, edges, edge);
 154                                 }
 155                         }
 156                 }
 157         }
 158
 159         /* now: sort edges and build the chunks */
 160         qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_aff_edge);
 161         for (i = 0; i < ARR_LEN(edges); ++i) {
 162
 163         }
 164
 165         DEL_ARR_F(edges);
 166 }
 167
 168 /**
 169  * Main driver for mst safe coalescing algorithm.
 170  */
 171 int co_solve_heuristic_mst_safe(copy_opt_t *co)
 172 {
 173         be_ifg_t *ifg         = co->cenv->ifg;
 174         unsigned n_regs       = co->cenv->cls->n_regs;
 175         bitset_t *ignore_regs = bitset_alloca(n_regs);
 176         unsigned k;
 177         co_mst_safe_env_t mst_env;
 178
 179         /* init phase */
 180         phase_init(&mst_env.ph, "co_mst_safe", co->irg, PHASE_DEFAULT_GROWTH, co_mst_safe_irn_init, &mst_env);
 181
 182         k = be_put_ignore_regs(co->cenv->birg, co->cenv->cls, ignore_regs);
 183         k = n_regs - k;
 184
 185         mst_env.n_regs = n_regs;
 186         mst_env.k      = k;
 187         mst_env.chunks = new_pqueue();
 188         mst_env.co     = co;
 189
 190         /* build affinity chunks */
 191         build_affinity_chunks(&mst_env);
 192
 193         /* color chunks as long as there are some */
 194         while (! pqueue_empty(mst_env.chunks)) {
 195                 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
 196                 color_aff_chunk(&mst_env, chunk);
 197         }
 198
 199         /* free allocated memory */
 200         del_pqueue(mst_env.chunks);
 201         phase_free(&mst_env.ph);
 202 }