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

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