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

   1 /**
   2  * More experiments on coalescing.
   3  * @author Sebastian Hack
   4  * @date   25.07.2006
   5  */
   6 #ifdef HAVE_CONFIG_H
   7 #include <config.h>
   8 #endif
   9
  10 #include <libcore/lc_opts.h>
  11 #include <libcore/lc_opts_enum.h>
  12
  13 #include <stdlib.h>
  14 #include <limits.h>
  15
  16 #include "list.h"
  17 #include "pdeq.h"
  18 #include "bitset.h"
  19
  20 #include "debug.h"
  21 #include "bitfiddle.h"
  22 #include "bitset.h"
  23 #include "raw_bitset.h"
  24
  25 #include "irphase_t.h"
  26 #include "irgraph_t.h"
  27 #include "irnode_t.h"
  28 #include "irprintf.h"
  29 #include "irtools.h"
  30
  31 #include "bemodule.h"
  32 #include "beabi.h"
  33 #include "benode_t.h"
  34 #include "becopyopt.h"
  35 #include "becopyopt_t.h"
  36 #include "bechordal_t.h"
  37 #include "bejavacoal.h"
  38
  39 #include <stdlib.h>
  40 #include <stdio.h>
  41
  42 #define DUMP_BEFORE 1
  43 #define DUMP_AFTER  2
  44 #define DUMP_ALL    2 * DUMP_AFTER - 1
  45
  46 static unsigned dump_flags = 0;
  47 static int      dbg_level  = 0;
  48
  49 static const lc_opt_enum_mask_items_t dump_items[] = {
  50         { "before",  DUMP_BEFORE },
  51         { "after",   DUMP_AFTER  },
  52         { "all",     DUMP_ALL    },
  53         { NULL,      0 }
  54 };
  55
  56 static lc_opt_enum_mask_var_t dump_var = {
  57         &dump_flags, dump_items
  58 };
  59
  60 static const lc_opt_table_entry_t options[] = {
  61         LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                              &dump_var),
  62         LC_OPT_ENT_INT      ("dbg",  "debug level for the Java coalescer",          &dbg_level),
  63         { NULL }
  64 };
  65
  66 void be_init_copyheur3(void)
  67 {
  68         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
  69         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
  70         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
  71         lc_opt_entry_t *co3_grp = lc_opt_get_grp(chordal_grp, "co3");
  72
  73         lc_opt_add_table(co3_grp, options);
  74 }
  75
  76 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur3);
  77
  78 static void set_admissible_regs(be_java_coal_t *coal, copy_opt_t *co, ir_node *irn, int t_idx, int *col_map)
  79 {
  80         const arch_register_req_t *req;
  81
  82         req = arch_get_register_req(co->aenv, irn, BE_OUT_POS(0));
  83
  84         // ir_printf("%+F\n", irn);
  85         if(arch_register_req_is(req, limited)) {
  86                 unsigned i;
  87                 unsigned n_regs = co->cls->n_regs;
  88
  89                 for(i = 0; i < n_regs; ++i) {
  90                         if(!rbitset_is_set(req->limited, i) && col_map[i] >= 0) {
  91                                 be_java_coal_forbid_color(coal, t_idx, col_map[i]);
  92                         }
  93                 }
  94         }
  95 }
  96
  97 int co_solve_heuristic_java(copy_opt_t *co)
  98 {
  99         be_ifg_t *ifg   = co->cenv->ifg;
 100         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 101         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 102         bitset_t *nodes = bitset_malloc(get_irg_last_idx(co->irg));
 103         unsigned n_regs = co->cenv->cls->n_regs;
 104
 105         char dbg[256];
 106         unsigned i, j, curr_idx;
 107         int *col_map;
 108         int *inv_col_map;
 109
 110         int *node_map;
 111         int *inv_node_map;
 112
 113         be_java_coal_t *coal;
 114         ir_node *n, *m;
 115
 116         col_map     = alloca(n_regs * sizeof(col_map[0]));
 117         inv_col_map = alloca(n_regs * sizeof(inv_col_map[0]));
 118
 119         memset(inv_col_map, -1, sizeof(inv_col_map[0]) * n_regs);
 120
 121         for(i = 0, j = 0; i < n_regs; ++i) {
 122                 const arch_register_t *reg = &co->cls->regs[i];
 123                 col_map[i] = -1;
 124                 if(!arch_register_type_is(reg, ignore)) {
 125                         col_map[i] = j;
 126                         inv_col_map[j] = i;
 127                         ++j;
 128                 }
 129         }
 130
 131         node_map     = malloc((get_irg_last_idx(co->irg) + 1) * sizeof(node_map[0]));
 132         inv_node_map = malloc((get_irg_last_idx(co->irg) + 1) * sizeof(inv_node_map[0]));
 133
 134         curr_idx = 0;
 135         be_ifg_foreach_node(ifg, nodes_it, n) {
 136                 if(!arch_irn_is(co->aenv, n, ignore)) {
 137                         int idx = get_irn_idx(n);
 138                         bitset_set(nodes, idx);
 139                         node_map[idx] = curr_idx;
 140                         inv_node_map[curr_idx] = idx;
 141                         curr_idx++;
 142                 }
 143         }
 144
 145         if(curr_idx == 0) {
 146                 free(node_map);
 147                 free(inv_node_map);
 148                 bitset_free(nodes);
 149                 return 0;
 150         }
 151
 152         coal = be_java_coal_init("test", curr_idx, j, dbg_level);
 153
 154         /* Check, if all neighbours are indeed connected to the node. */
 155         be_ifg_foreach_node(ifg, nodes_it, n) {
 156                 int n_idx = get_irn_idx(n);
 157                 int t_idx = node_map[n_idx];
 158
 159                 if(bitset_is_set(nodes, n_idx)) {
 160                         affinity_node_t *an = get_affinity_info(co, n);
 161
 162                         ir_snprintf(dbg, sizeof(dbg), "%+F", n);
 163                         be_java_coal_set_debug(coal, t_idx, dbg);
 164                         be_java_coal_set_color(coal, t_idx, col_map[arch_get_irn_register(co->aenv, n)->index]);
 165                         set_admissible_regs(coal, co, n, t_idx, col_map);
 166                         be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 167                                 int m_idx = get_irn_idx(m);
 168                                 int s_idx = node_map[m_idx];
 169
 170                                 if(n_idx < m_idx && bitset_is_set(nodes, m_idx)) {
 171                                         be_java_coal_add_int_edge(coal, s_idx, t_idx);
 172                                 }
 173                         }
 174
 175                         if(an != NULL) {
 176                                 neighb_t *neigh;
 177                                 co_gs_foreach_neighb(an, neigh) {
 178                                         int m_idx = get_irn_idx(neigh->irn);
 179                                         int s_idx = node_map[m_idx];
 180
 181                                         if(n_idx < m_idx && bitset_is_set(nodes, m_idx)) {
 182                                                 be_java_coal_add_aff_edge(coal, s_idx, t_idx, neigh->costs);
 183                                         }
 184                                 }
 185                         }
 186                 }
 187         }
 188
 189         if(dump_flags & DUMP_BEFORE) {
 190                 char fn[512];
 191                 ir_snprintf(fn, sizeof(fn), "%F-%s-before.dot", co->cenv->irg, co->cenv->cls->name);
 192                 be_java_coal_dump(coal, fn);
 193         }
 194
 195         be_java_coal_coalesce(coal);
 196
 197         be_ifg_foreach_node(ifg, nodes_it, n) {
 198                 unsigned idx = get_irn_idx(n);
 199                 if(bitset_is_set(nodes, idx)) {
 200                         unsigned t_idx             = node_map[idx];
 201                         unsigned col               = inv_col_map[be_java_coal_get_color(coal, t_idx)];
 202                         const arch_register_t *reg;
 203
 204                         assert(col < n_regs);
 205                         reg     = &co->cls->regs[col];
 206                         arch_set_irn_register(co->aenv, n, reg);
 207                 }
 208         }
 209
 210         if(dump_flags & DUMP_AFTER) {
 211                 char fn[512];
 212                 ir_snprintf(fn, sizeof(fn), "%F-%s-after.dot", co->cenv->irg, co->cenv->cls->name);
 213                 be_java_coal_dump(coal, fn);
 214         }
 215
 216         be_java_coal_destroy(coal);
 217         bitset_free(nodes);
 218         return 0;
 219 }