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