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

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