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

   1
   2 /**
   3  * More experiments on coalescing.
   4  * @author Sebastian Hack
   5  * @date   14.04.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
  27 #include "irphase_t.h"
  28 #include "irgraph_t.h"
  29 #include "irnode_t.h"
  30 #include "irprintf.h"
  31 #include "irtools.h"
  32
  33 #include "beabi.h"
  34 #include "benode_t.h"
  35 #include "becopyopt.h"
  36 #include "becopyopt_t.h"
  37 #include "bechordal_t.h"
  38
  39 #define DUMP_BEFORE 1
  40 #define DUMP_AFTER  2
  41 #define DUMP_CLOUD  4
  42 #define DUMP_ALL    2 * DUMP_CLOUD - 1
  43
  44 static int    dump_flags      = 0;
  45 static double stop_percentage = 1.0;
  46
  47 /* Options using libcore */
  48 #ifdef WITH_LIBCORE
  49
  50 static const lc_opt_enum_mask_items_t dump_items[] = {
  51         { "before",  DUMP_BEFORE },
  52     { "after",   DUMP_AFTER  },
  53     { "cloud",   DUMP_CLOUD  },
  54         { "all",     DUMP_ALL    },
  55         { NULL,      0 }
  56 };
  57
  58 static lc_opt_enum_mask_var_t dump_var = {
  59         &dump_flags, dump_items
  60 };
  61
  62 static const lc_opt_table_entry_t options[] = {
  63         LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud",                     &dump_var),
  64         LC_OPT_ENT_DBL      ("stop", "stop optimizing cloud at given percentage of total cloud costs", &stop_percentage),
  65         { NULL }
  66 };
  67
  68 void be_co2_register_options(lc_opt_entry_t *grp)
  69 {
  70         lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
  71         lc_opt_add_table(co2_grp, options);
  72 }
  73 #endif
  74
  75 /*
  76   ____  _             _
  77  / ___|| |_ __ _ _ __| |_
  78  \___ \| __/ _` | '__| __|
  79   ___) | || (_| | |  | |_
  80  |____/ \__\__,_|_|   \__|
  81
  82 */
  83
  84 #define INFEASIBLE(cost) ((cost) == INT_MAX)
  85
  86 static be_ifg_dump_dot_cb_t ifg_dot_cb;
  87
  88 typedef unsigned col_t;
  89
  90 typedef struct _co2_irn_t       co2_irn_t;
  91 typedef struct _co2_cloud_t     co2_cloud_t;
  92 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
  93
  94 typedef struct {
  95         col_t col;
  96         int costs;
  97 } col_cost_pair_t;
  98
  99 typedef struct {
 100         phase_t     ph;
 101         copy_opt_t *co;
 102         bitset_t   *ignore_regs;
 103         co2_irn_t  *touched;
 104         int         visited;
 105         int         n_regs;
 106         struct list_head cloud_head;
 107         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 108 } co2_t;
 109
 110 struct _co2_irn_t {
 111         ir_node         *irn;
 112         affinity_node_t *aff;
 113         co2_irn_t       *touched_next;
 114         col_t            tmp_col;
 115         col_t            orig_col;
 116         int                              last_color_change;
 117         bitset_t        *adm_cache;
 118         unsigned         fixed     : 1;
 119         unsigned         tmp_fixed : 1;
 120         struct list_head changed_list;
 121 };
 122
 123 struct _co2_cloud_irn_t {
 124         struct _co2_irn_t  inh;
 125         co2_cloud_t       *cloud;
 126         int                visited;
 127         int                index;
 128         co2_cloud_irn_t   *mst_parent;
 129         int                mst_costs;
 130         int                mst_n_childs;
 131         co2_cloud_irn_t  **mst_childs;
 132         int               *col_costs;
 133         int                costs;
 134         int               *fronts;
 135         int               *color_badness;
 136         col_cost_pair_t   *tmp_coloring;
 137         struct list_head   cloud_list;
 138         struct list_head   mst_list;
 139 };
 140
 141 struct _co2_cloud_t {
 142         co2_t            *env;
 143         struct obstack    obst;
 144         int               costs;
 145         int               mst_costs;
 146         int               inevit;
 147         int               best_costs;
 148         int               n_memb;
 149         int               max_degree;
 150         int                           ticks;
 151         co2_cloud_irn_t  *master;
 152         co2_cloud_irn_t  *mst_root;
 153         co2_cloud_irn_t **seq;
 154         struct list_head  members_head;
 155         struct list_head  list;
 156 };
 157
 158 #define FRONT_BASE(ci,col)  ((ci)->fronts + col * (ci)->mst_n_childs)
 159
 160 #define get_co2_irn(co2, irn)         ((co2_irn_t *)       phase_get_or_set_irn_data(&co2->ph, irn))
 161 #define get_co2_cloud_irn(co2, irn)   ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
 162
 163 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
 164 {
 165         co2_t *env         = (co2_t *) ph;
 166         affinity_node_t *a = get_affinity_info(env->co, irn);
 167         size_t size        = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
 168         co2_irn_t *ci      = data ? data : phase_alloc(ph, size);
 169
 170         memset(ci, 0, size);
 171         INIT_LIST_HEAD(&ci->changed_list);
 172         ci->touched_next = env->touched;
 173         ci->orig_col     = get_irn_col(env->co, irn);
 174         env->touched     = ci;
 175         ci->irn          = irn;
 176         ci->aff          = a;
 177
 178         if(a) {
 179                 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
 180                 INIT_LIST_HEAD(&cci->cloud_list);
 181                 cci->mst_parent   = cci;
 182         }
 183
 184         return ci;
 185 }
 186
 187
 188 static int cmp_clouds_gt(const void *a, const void *b)
 189 {
 190         const co2_cloud_t **p = a;
 191         const co2_cloud_t **q = b;
 192         int c = (*p)->costs;
 193         int d = (*q)->costs;
 194         return QSORT_CMP(d, c);
 195 }
 196
 197 /**
 198  * An order on color/costs pairs.
 199  * If the costs are equal, we use the color as a kind of normalization.
 200  */
 201 static int col_cost_pair_lt(const void *a, const void *b)
 202 {
 203         const col_cost_pair_t *p = a;
 204         const col_cost_pair_t *q = b;
 205         int c = p->costs;
 206         int d = q->costs;
 207         return QSORT_CMP(c, d);
 208 }
 209
 210 static col_t get_col(co2_t *env, ir_node *irn)
 211 {
 212         co2_irn_t *ci = get_co2_irn(env, irn);
 213         return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
 214 }
 215
 216 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
 217 {
 218         co2_irn_t *ci = get_co2_irn(env, irn);
 219         return ci->fixed || ci->tmp_fixed;
 220 }
 221
 222 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
 223 {
 224         if(!ci->adm_cache) {
 225                 arch_register_req_t req;
 226                 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
 227                 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
 228                 if(arch_register_req_is(&req, limited))
 229                         req.limited(req.limited_env, ci->adm_cache);
 230                 else {
 231                         bitset_copy(ci->adm_cache, env->ignore_regs);
 232                         bitset_flip_all(ci->adm_cache);
 233                 }
 234         }
 235
 236         return ci->adm_cache;
 237 }
 238
 239 static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
 240 {
 241         bitset_copy(bs, get_adm(env, ci));
 242         return bs;
 243 }
 244
 245 static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
 246 {
 247         bitset_t *bs = get_adm(env, ci);
 248         return bitset_is_set(bs, col);
 249 }
 250
 251 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
 252 {
 253         bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
 254         arch_register_req_t req;
 255
 256         arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
 257
 258         if(arch_register_req_is(&req, limited)) {
 259                 bitset_pos_t elm;
 260                 int n_constr;
 261
 262                 req.limited(req.limited_env, aux);
 263                 n_constr = bitset_popcnt(aux);
 264                 bitset_foreach(aux, elm) {
 265                         col_costs[elm].costs  = add_saturated(col_costs[elm].costs, costs / n_constr);
 266                 }
 267         }
 268 }
 269
 270 /**
 271  * Determine costs which shall indicate how cheap/expensive it is to try
 272  * to assign a node some color.
 273  * The costs are computed for all colors. INT_MAX means that it is impossible
 274  * to give the node that specific color.
 275  *
 276  * @param env       The co2 this pointer.
 277  * @param irn       The node.
 278  * @param col_costs An array of colors x costs where the costs are written to.
 279  */
 280 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
 281 {
 282         ir_node *irn       = ci->irn;
 283         be_ifg_t *ifg      = env->co->cenv->ifg;
 284         int n_regs         = env->co->cls->n_regs;
 285         bitset_t *forb     = bitset_alloca(n_regs);
 286         affinity_node_t *a = ci->aff;
 287
 288         bitset_pos_t elm;
 289         ir_node *pos;
 290         void *it;
 291         int i;
 292
 293         /* Put all forbidden colors into the aux bitset. */
 294         admissible_colors(env, ci, forb);
 295         bitset_flip_all(forb);
 296
 297         for(i = 0; i < n_regs; ++i) {
 298                 col_costs[i].col   = i;
 299                 col_costs[i].costs = 0;
 300         }
 301
 302         if(a) {
 303                 neighb_t *n;
 304
 305                 co_gs_foreach_neighb(a, n) {
 306                         if(color_is_fix(env, n->irn)) {
 307                                 col_t col = get_col(env, n->irn);
 308                                 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
 309                         }
 310
 311                         incur_constraint_costs(env, n->irn, col_costs, -n->costs);
 312                 }
 313         }
 314
 315         it = be_ifg_neighbours_iter_alloca(ifg);
 316         be_ifg_foreach_neighbour(ifg, it, irn, pos) {
 317                 col_t col = get_col(env, pos);
 318                 if(color_is_fix(env, pos)) {
 319                         col_costs[col].costs  = INT_MAX;
 320                 }
 321                 else {
 322                         incur_constraint_costs(env, pos, col_costs, INT_MAX);
 323                         col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
 324                 }
 325         }
 326
 327         /* Set the costs to infinity for each color which is not allowed at this node. */
 328         bitset_foreach(forb, elm) {
 329                 col_costs[elm].costs  = INT_MAX;
 330         }
 331
 332 }
 333
 334 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
 335 {
 336         int n_regs = env->co->cls->n_regs;
 337         int i;
 338
 339         for(i = 0; i < n_regs; ++i) {
 340                 seq[i].col   = i;
 341                 seq[i].costs = INT_MAX;
 342         }
 343
 344         assert(is_color_admissible(env, ci, col));
 345         seq[col].col = 0;
 346         seq[0].col   = col;
 347         seq[0].costs = 0;
 348 }
 349
 350 static void reject_coloring(struct list_head *h)
 351 {
 352         co2_irn_t *pos;
 353
 354         list_for_each_entry(co2_irn_t, pos, h, changed_list)
 355                 pos->tmp_fixed = 0;
 356 }
 357
 358 static void materialize_coloring(struct list_head *h)
 359 {
 360         co2_irn_t *pos;
 361
 362         list_for_each_entry(co2_irn_t, pos, h, changed_list) {
 363                 pos->orig_col  = pos->tmp_col;
 364                 pos->tmp_fixed = 0;
 365         }
 366 }
 367
 368 typedef struct {
 369         co2_irn_t *ci;
 370         col_t col;
 371 } col_entry_t;
 372
 373 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
 374 {
 375         co2_irn_t *pos;
 376         col_entry_t ent;
 377
 378         list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
 379                 ent.ci  = pos;
 380                 ent.col = pos->tmp_col;
 381                 pos->tmp_col = 0;
 382                 obstack_grow(obst, &ent, sizeof(ent));
 383         }
 384         memset(&ent, 0, sizeof(ent));
 385         obstack_grow(obst, &ent, sizeof(ent));
 386         return obstack_finish(obst);
 387 }
 388
 389 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 390 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
 391
 392 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
 393 {
 394         int n_regs         = env->co->cls->n_regs;
 395         be_ifg_t *ifg      = env->co->cenv->ifg;
 396         co2_irn_t *ci      = get_co2_irn(env, irn);
 397         int res            = 0;
 398         int n_aff          = 0;
 399
 400         int i;
 401
 402         for(i = 0; i < n_regs; ++i) {
 403                 col_t tgt_col  = col_list[i].col;
 404                 unsigned costs = col_list[i].costs;
 405                 int neigh_ok   = 1;
 406
 407                 struct list_head changed;
 408                 ir_node *n;
 409                 void *it;
 410
 411                 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
 412
 413                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 414                 if(INFEASIBLE(costs)) {
 415                         DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
 416                         ci->tmp_fixed = 0;
 417                         return 0;
 418                 }
 419
 420                 /* Set the new color of the node and mark the node as temporarily fixed. */
 421                 ci->tmp_col     = tgt_col;
 422                 ci->tmp_fixed   = 1;
 423
 424                 /*
 425                 If that color has costs > 0, there's at least one neighbor having that color,
 426                 so we will try to change the neighbors' colors, too.
 427                 */
 428                 INIT_LIST_HEAD(&changed);
 429                 list_add(&ci->changed_list, &changed);
 430
 431                 it = be_ifg_neighbours_iter_alloca(ifg);
 432                 be_ifg_foreach_neighbour(ifg, it, irn, n) {
 433
 434                         /* try to re-color the neighbor if it has the target color. */
 435                         if(get_col(env, n) == tgt_col) {
 436                                 struct list_head tmp;
 437
 438                                 /*
 439                                 Try to change the color of the neighbor and record all nodes which
 440                                 get changed in the tmp list. Add this list to the "changed" list for
 441                                 that color. If we did not succeed to change the color of the neighbor,
 442                                 we bail out and try the next color.
 443                                 */
 444                                 INIT_LIST_HEAD(&tmp);
 445                                 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
 446                                 list_splice(&tmp, &changed);
 447                                 if(!neigh_ok)
 448                                         break;
 449                         }
 450                 }
 451
 452                 /*
 453                 We managed to assign the target color to all neighbors, so from the perspective
 454                 of the current node, every thing was ok and we can return safely.
 455                 */
 456                 if(neigh_ok) {
 457                         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
 458                         list_splice(&changed, parent_changed);
 459                         res = 1;
 460                         break;
 461                 }
 462
 463                 /*
 464                 If not, that color did not succeed and we unfix all nodes we touched
 465                 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
 466                 */
 467                 else
 468                         reject_coloring(&changed);
 469         }
 470
 471         return res;
 472 }
 473
 474 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
 475 {
 476         co2_irn_t *ci = get_co2_irn(env, irn);
 477         int res       = 0;
 478         col_t col     = get_col(env, irn);
 479
 480         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
 481
 482         /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
 483         if(col != not_col) {
 484                 if(!ci->tmp_fixed) {
 485                         ci->tmp_col     = col;
 486                         ci->tmp_fixed   = 1;
 487                 }
 488
 489                 list_add(&ci->changed_list, parent_changed);
 490                 return 1;
 491         }
 492
 493         /* The node has the color it should not have _and_ has not been visited yet. */
 494         if(!color_is_fix(env, irn)) {
 495                 int n_regs            = env->co->cls->n_regs;
 496                 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
 497
 498                 /* Get the costs for giving the node a specific color. */
 499                 determine_color_costs(env, ci, csts);
 500
 501                 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
 502                 csts[not_col].costs = INT_MAX;
 503
 504                 /* sort the colors according costs, cheapest first. */
 505                 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
 506
 507                 /* Try recoloring the node using the color list. */
 508                 res = recolor(env, irn, csts, parent_changed, depth);
 509         }
 510
 511         /* If we came here, everything went ok. */
 512         return res;
 513 }
 514
 515 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
 516 {
 517         co2_irn_t *ci = get_co2_irn(env, irn);
 518         col_t col     = get_col(env, irn);
 519         int res       = 0;
 520
 521         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
 522
 523         /* the node has the wanted color. That's fine, mark it as visited and return. */
 524         if(col == tgt_col) {
 525                 if(!ci->tmp_fixed) {
 526                         ci->tmp_col     = col;
 527                         ci->tmp_fixed   = 1;
 528                         list_add(&ci->changed_list, parent_changed);
 529                 }
 530
 531                 res = 1;
 532                 goto end;
 533         }
 534
 535         if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
 536                 int n_regs           = env->co->cls->n_regs;
 537                 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
 538
 539                 /* Get the costs for giving the node a specific color. */
 540                 single_color_cost(env, ci, tgt_col, seq);
 541
 542                 /* Try recoloring the node using the color list. */
 543                 res = recolor(env, irn, seq, parent_changed, depth);
 544
 545         }
 546
 547 end:
 548         DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
 549         return res;
 550 }
 551
 552 static void front_inval_color(co2_cloud_irn_t *ci, col_t col)
 553 {
 554         int *base = FRONT_BASE(ci, col);
 555         memset(base, -1, ci->mst_n_childs * sizeof(base[0]));
 556 }
 557
 558 typedef struct {
 559         co2_cloud_irn_t *src, *tgt;
 560         int costs;
 561 } edge_t;
 562
 563 int cmp_edges(const void *a, const void *b)
 564 {
 565         const edge_t *p = a;
 566         const edge_t *q = b;
 567         return QSORT_CMP(p->costs, q->costs);
 568 }
 569
 570 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
 571 {
 572         while(ci->mst_parent != ci->mst_parent)
 573                 ci = ci->mst_parent;
 574         return ci;
 575 }
 576
 577
 578 static int cmp_parent(const void *a, const void *b)
 579 {
 580         const co2_cloud_irn_t *p = a;
 581         const co2_cloud_irn_t *q = b;
 582         return QSORT_CMP(q->mst_costs, p->mst_costs);
 583 }
 584
 585 static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col)
 586 {
 587         int n_regs = ci->cloud->env->n_regs;
 588         int i, j;
 589
 590         for(i = 0; i < ci->mst_n_childs; ++i) {
 591                 co2_cloud_irn_t *c = ci->mst_childs[i];
 592                 for(j = 0; j < n_regs; ++j) {
 593                         int costs = c->col_costs[j];
 594                         if(INFEASIBLE(costs))
 595                                 c->tmp_coloring[j].costs = INT_MAX;
 596                         else {
 597                                 int add = j != (int) col ? c->mst_costs : 0;
 598                                 c->tmp_coloring[j].costs = add + costs;
 599                         }
 600                         c->tmp_coloring[j].col = j;
 601                 }
 602                 qsort(c->tmp_coloring, n_regs, sizeof(c->tmp_coloring[0]), col_cost_pair_lt);
 603         }
 604 }
 605
 606 static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq)
 607 {
 608         int n_regs    = ci->cloud->env->n_regs;
 609         bitset_t *adm = bitset_alloca(n_regs);
 610         int i, j;
 611
 612         // TODO: Prefer some colors depending on the neighbors, etc.
 613
 614         admissible_colors(ci->cloud->env, &ci->inh, adm);
 615         for(i = 0; i < n_regs; ++i) {
 616                 seq[i].col   = i;
 617
 618                 if (!bitset_is_set(adm, i))
 619                         seq[i].costs = INT_MAX;
 620                 else {
 621                         seq[i].costs = 0;
 622                         for(j = 0; j < ci->mst_n_childs; ++j) {
 623                                 co2_cloud_irn_t *child = ci->mst_childs[j];
 624                                 if (!INFEASIBLE(child->col_costs[i]))
 625                                         seq[i].costs -= ci->mst_childs[j]->col_costs[i];
 626                         }
 627                 }
 628         }
 629
 630         qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
 631 }
 632
 633 static int push_front(co2_cloud_irn_t *ci, int *front)
 634 {
 635         co2_t *env   = ci->cloud->env;
 636         int n_regs   = env->n_regs;
 637         int min_diff = INT_MAX;
 638         int min_chld = -1;
 639         int i;
 640
 641         for(i = 0; i < ci->mst_n_childs; ++i) {
 642                 co2_cloud_irn_t *child = ci->mst_childs[i];
 643                 int idx = front[i];
 644
 645
 646                 if(idx + 1 < n_regs) {
 647                         int diff = child->tmp_coloring[idx].costs - child->tmp_coloring[idx + 1].costs;
 648                         if(diff < min_diff) {
 649                                 min_diff = diff;
 650                                 min_chld = i;
 651                         }
 652                 }
 653         }
 654
 655         if(min_chld >= 0) {
 656                 co2_cloud_irn_t *child = ci->mst_childs[min_chld];
 657                 DBG((env->dbg, LEVEL_3, "\tsmallest diff with child %+F on index %d is %d\n", child->inh.irn, front[min_chld], min_diff));
 658                 front[min_chld] += 1;
 659         }
 660
 661         return min_chld;
 662 }
 663
 664 static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
 665 {
 666         int n_childs = ci->mst_n_childs;
 667         /*
 668                 select the front for the given color.
 669                 The front will determine the colors of the children.
 670         */
 671         int *front = FRONT_BASE(ci, col);
 672         int i, ok = 1;
 673
 674         ok = change_color_single(ci->cloud->env, ci->inh.irn, col, changed, 0);
 675         for(i = 0; i < n_childs && ok; ++i) {
 676                 co2_cloud_irn_t *child = ci->mst_childs[i];
 677                 col_t col              = front[i];
 678
 679                 ok = color_subtree(child, col, changed, depth + 1);
 680         }
 681
 682         return ok;
 683 }
 684
 685 static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth)
 686 {
 687         co2_t *env = ci->cloud->env;
 688         struct list_head changed;
 689         int i, ok = 1;
 690
 691         INIT_LIST_HEAD(&changed);
 692         *initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1);
 693
 694         for (i = 0; i < ci->mst_n_childs && ok; ++i) {
 695                 co2_cloud_irn_t *child = ci->mst_childs[i];
 696                 col_t tgt_col = child->tmp_coloring[front[i]].col;
 697
 698                 ok = color_subtree(child, tgt_col, &changed, depth + 1);
 699         }
 700
 701         reject_coloring(&changed);
 702
 703         return ok;
 704 }
 705
 706 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
 707 {
 708         int *front = FRONT_BASE(ci, col);
 709         int cost   = 0;
 710         int i;
 711
 712         for(i = 0; i < ci->mst_n_childs; ++i) {
 713                 co2_cloud_irn_t *chld = ci->mst_childs[i];
 714                 col_t chld_col        = front[i];
 715
 716                 cost += examine_subtree_coloring(chld, chld_col);
 717                 cost += col != chld_col ? chld->mst_costs : 0;
 718         }
 719
 720         return cost;
 721 }
 722
 723 static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth)
 724 {
 725         co2_t *env           = ci->cloud->env;
 726         int n_regs           = env->n_regs;
 727         col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
 728         int *front           = alloca(ci->mst_n_childs * sizeof(front[0]));
 729         int best_col         = -1;
 730         int best_cost        = INT_MAX;
 731
 732
 733         int i;
 734
 735         DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn));
 736
 737         for (i = 0; i < ci->mst_n_childs; ++i)
 738                 cloud_mst_build_colorings(ci->mst_childs[i], depth + 1);
 739
 740         for (i = 0; i < n_regs; ++i)
 741                 ci->col_costs[i] = INT_MAX;
 742
 743         /* Sort the children according to the cost of the affinity edge they have to the current node. */
 744         // qsort(child, ci->mst_n_childs, sizeof(childs[0]), cmp_parent);
 745
 746         determine_start_colors(ci, seq);
 747         // qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
 748
 749         for(i = 0; i < n_regs; ++i) {
 750                 col_t col = seq[i].col;
 751                 int costs = seq[i].costs;
 752                 int done  = 0;
 753
 754                 if(INFEASIBLE(costs))
 755                         break;
 756
 757                 /*
 758                         Judge, if it is worthwhile trying this color.
 759                         If another color was so good that we cannot get any better, bail out here.
 760                         Perhaps???
 761                 */
 762
 763                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
 764
 765                 /* This sorts the tmp_coloring array in the children according to the costs of the current color. */
 766                 fill_tmp_coloring(ci, col);
 767
 768                 /* Initialize the front. It gives the indexes into the color tmp_coloring array. */
 769                 memset(front, 0, ci->mst_n_childs * sizeof(front));
 770
 771                 /*
 772                         As long as we have color configurations to try.
 773                         We try the best ones first and get worse over and over.
 774                 */
 775                 while (!done) {
 776                         int j, try_push;
 777
 778                         if (try_coloring(ci, col, front, &try_push, depth + 1)) {
 779                                 int *res_front = FRONT_BASE(ci, col);
 780                                 int costs;
 781
 782                                 for(j = 0; j < ci->mst_n_childs; ++j) {
 783                                         co2_cloud_irn_t *child = ci->mst_childs[j];
 784                                         col_t col              = child->tmp_coloring[front[j]].col;
 785                                         res_front[j] = col;
 786                                 }
 787
 788                                 costs = examine_subtree_coloring(ci, col);
 789                                 ci->col_costs[col] = costs;
 790                                 done = 1;
 791
 792                                 /* Set the current best color. */
 793                                 if(costs < best_cost) {
 794                                         best_cost = costs;
 795                                         best_col  = col;
 796                                 }
 797                         }
 798
 799                         DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", depth, done ? "ok" : "failed"));
 800
 801                         /* Worsen the configuration, if that one didn't succeed. */
 802                         if (!done)
 803                                 done = try_push ? push_front(ci, front) < 0 : 1;
 804                 }
 805         }
 806
 807         DBG((env->dbg, LEVEL_2, "%2{firm:indent} %+F\n", depth, ci->inh.irn));
 808         for(i = 0; i < n_regs; ++i)
 809                 DBG((env->dbg, LEVEL_2, "%2{firm:indent}  color %d costs %d\n", depth, i, ci->col_costs[i]));
 810
 811         return best_col;
 812 }
 813
 814
 815 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
 816 {
 817         co2_t *env     = ci->cloud->env;
 818         int n_regs     = env->n_regs;
 819         be_ifg_t *ifg  = env->co->cenv->ifg;
 820         co2_irn_t *ir  = &ci->inh;
 821         bitset_t *bs   = bitset_alloca(n_regs);
 822
 823         bitset_pos_t elm;
 824         ir_node *irn;
 825         int i, j;
 826         void *it;
 827
 828         admissible_colors(env, &ci->inh, bs);
 829         bitset_flip_all(bs);
 830         bitset_foreach(bs, elm)
 831                 ci->color_badness[elm] = n_regs * ci->costs;
 832
 833         /* Use constrained/fixed interfering neighbors to influence the color badness */
 834         it = be_ifg_neighbours_iter_alloca(ifg);
 835         be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
 836                 co2_irn_t *ni = get_co2_irn(env, irn);
 837                 int n_adm;
 838
 839                 admissible_colors(env, ni, bs);
 840                 n_adm = bitset_popcnt(bs);
 841                 bitset_foreach(bs, elm)
 842                         ci->color_badness[elm] += n_regs - n_adm;
 843
 844                 if(ni->fixed) {
 845                         col_t c = get_col(env, ni->irn);
 846                         ci->color_badness[c] += n_regs * ci->costs;
 847                 }
 848         }
 849
 850         /* Collect the color badness for the whole subtree */
 851         for(i = 0; i < ci->mst_n_childs; ++i) {
 852                 co2_cloud_irn_t *child = ci->mst_childs[i];
 853                 determine_color_badness(child, depth + 1);
 854
 855                 for(j = 0; j < n_regs; ++j)
 856                         ci->color_badness[j] += child->color_badness[j];
 857         }
 858
 859         for(j = 0; j < n_regs; ++j)
 860                 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
 861 }
 862
 863 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth);
 864
 865
 866 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, struct list_head *parent_changed, int depth)
 867 {
 868         co2_t *env           = ci->cloud->env;
 869         col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
 870         int is_root          = ci->mst_parent == ci;
 871         col_t parent_col     = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
 872         int min_badness      = INT_MAX;
 873         int best_col_costs   = INT_MAX;
 874         int best_col         = -1;
 875
 876         struct list_head changed;
 877         int ok, i, j;
 878
 879         for(i = 0; i < env->n_regs; ++i) {
 880                 int badness = ci->color_badness[i];
 881
 882                 seq[i].col   = i;
 883                 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? ci->color_badness[i] : INT_MAX;
 884
 885                 min_badness = MIN(min_badness, badness);
 886         }
 887
 888         /* If we are not the root and the parent's color is allowed for this node give it top prio. */
 889         if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
 890                 seq[parent_col].costs = min_badness - 1;
 891
 892         qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
 893
 894         INIT_LIST_HEAD(&changed);
 895         for(i = 0; i < env->n_regs; ++i) {
 896                 col_t col    = seq[i].col;
 897                 int costs    = seq[i].costs;
 898                 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
 899
 900                 int subtree_costs, sum_costs;
 901
 902                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
 903                 INIT_LIST_HEAD(&changed);
 904                 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
 905
 906                 for(j = 0; ok && j < ci->mst_n_childs; ++j) {
 907                         ok = coalesce_top_down(ci->mst_childs[j], j, &changed, depth + 1) >= 0;
 908                 }
 909
 910                 /* If the subtree could not be colored, we have to try another color. */
 911                 if (!ok) {
 912                         reject_coloring(&changed);
 913                         continue;
 914                 }
 915
 916                 subtree_costs      = examine_subtree_coloring(ci, col);
 917                 sum_costs          = subtree_costs + add_cost;
 918                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
 919
 920                 if(sum_costs < best_col_costs) {
 921                         best_col           = col;
 922                         best_col_costs     = sum_costs;
 923                         ci->col_costs[col] = subtree_costs;
 924                 }
 925
 926                 reject_coloring(&changed);
 927
 928                 if(sum_costs == 0)
 929                         break;
 930
 931                 /* If we are at the root and we achieved an acceptable amount of optimization, we finish. */
 932 #if 0
 933                 if(is_root && (ci->cloud->mst_costs * stop_percentage < ci->cloud->mst_costs - sum_costs)) {
 934                         assert(best_col != -1);
 935                         break;
 936                 }
 937 #endif
 938         }
 939
 940         if(!is_root) {
 941                 int *front = FRONT_BASE(ci->mst_parent, parent_col);
 942                 front[child_nr] = best_col;
 943         }
 944
 945         if(best_col >= 0) {
 946                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}applying best color %d for %+F\n", depth, best_col, ci->inh.irn));
 947                 apply_coloring(ci, best_col, parent_changed, depth);
 948         }
 949
 950         return best_col;
 951 }
 952
 953 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
 954 {
 955         be_ifg_t *ifg       = env->co->cenv->ifg;
 956         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
 957         int costs           = 0;
 958         neighb_t *n;
 959
 960         if(ci->visited >= env->visited)
 961                 return;
 962
 963         /* mark the node as visited and add it to the cloud. */
 964         ci->visited = env->visited;
 965         ci->cloud   = cloud;
 966         list_add(&ci->cloud_list, &cloud->members_head);
 967
 968         DB((env->dbg, LEVEL_3, "\t%+F\n", ci->inh.irn));
 969
 970         /* determine the nodes costs */
 971         co_gs_foreach_neighb(a, n) {
 972                 costs += n->costs;
 973                 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
 974                 if(be_ifg_connected(ifg, a->irn, n->irn))
 975                         cloud->inevit += n->costs;
 976         }
 977
 978         /* add the node's cost to the total costs of the cloud. */
 979         ci->costs          = costs;
 980         cloud->costs      += costs;
 981         cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
 982         cloud->n_memb++;
 983
 984         /* If this is the heaviest node in the cloud, set it as the cloud's master. */
 985         if(costs >= curr_costs) {
 986                 curr_costs    = costs;
 987                 cloud->master = ci;
 988         }
 989
 990         /* add all the neighbors of the node to the cloud. */
 991         co_gs_foreach_neighb(a, n) {
 992                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 993                 assert(an);
 994                 populate_cloud(env, cloud, an, curr_costs);
 995         }
 996 }
 997
 998 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
 999 {
1000         co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
1001         co2_cloud_irn_t *ci;
1002         int i;
1003
1004         DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
1005         memset(cloud, 0, sizeof(cloud[0]));
1006         INIT_LIST_HEAD(&cloud->members_head);
1007         INIT_LIST_HEAD(&cloud->list);
1008         list_add(&cloud->list, &env->cloud_head);
1009         cloud->best_costs = INT_MAX;
1010         cloud->env = env;
1011         env->visited++;
1012         populate_cloud(env, cloud, a, 0);
1013
1014         /* Allocate space for the best colors array, where the best coloring is saved. */
1015         // cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
1016
1017         /* Also allocate space for the node sequence and compute that sequence. */
1018         cloud->seq    = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
1019
1020         i = 0;
1021         list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
1022                 ci->index       = i;
1023                 cloud->seq[i++] = ci;
1024         }
1025         DBG((env->dbg, LEVEL_2, "cloud cost %d\n", cloud->costs));
1026
1027         return cloud;
1028 }
1029
1030 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
1031 {
1032         ir_node *irn = ci->inh.irn;
1033         int *front   = FRONT_BASE(ci, col);
1034         int i, ok;
1035
1036         DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
1037         ok = change_color_single(ci->cloud->env, irn, col, changed, depth);
1038         assert(ok && "Color changing may not fail while committing the coloring");
1039
1040         for(i = 0; i < ci->mst_n_childs; ++i) {
1041                 apply_coloring(ci->mst_childs[i], front[i], changed, depth + 1);
1042         }
1043 }
1044
1045 static void process_cloud(co2_cloud_t *cloud)
1046 {
1047         co2_t *env  = cloud->env;
1048         int n_edges = 0;
1049
1050         struct list_head changed;
1051         edge_t *edges;
1052         int i;
1053         int best_col;
1054
1055         /* Collect all edges in the cloud on an obstack and sort the increasingly */
1056         obstack_init(&cloud->obst);
1057         for(i = 0; i < cloud->n_memb; ++i) {
1058                 co2_cloud_irn_t *ci = cloud->seq[i];
1059                 neighb_t *n;
1060
1061                 co_gs_foreach_neighb(ci->inh.aff, n) {
1062                         co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
1063                         if(ci->index < ni->index) {
1064                                 edge_t e;
1065                                 e.src   = ci;
1066                                 e.tgt   = ni;
1067                                 e.costs = n->costs;
1068                                 obstack_grow(&cloud->obst, &e, sizeof(e));
1069                                 n_edges++;
1070                         }
1071                 }
1072         }
1073         edges = obstack_finish(&cloud->obst);
1074         qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
1075
1076         /* Compute the maximum spanning tree using Kruskal/Union-Find */
1077         DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
1078         for(i = 0; i < n_edges; ++i) {
1079                 edge_t *e        = &edges[i];
1080                 co2_cloud_irn_t *p_src = find_mst_root(e->src);
1081                 co2_cloud_irn_t *p_tgt = find_mst_root(e->tgt);
1082
1083                 if(p_src != p_tgt) {
1084
1085                         /*
1086                                 Bring the more costly nodes near to the root of the MST.
1087                                 Thus, tgt shall always be the more expensive node.
1088                         */
1089                         if(p_src->costs > p_tgt->costs) {
1090                                 void *tmp = p_src;
1091                                 p_src = p_tgt;
1092                                 p_tgt = tmp;
1093                         }
1094
1095                         p_tgt->mst_n_childs++;
1096                         p_src->mst_parent = p_tgt;
1097                         p_src->mst_costs  = e->costs;
1098
1099                         DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", p_src->inh.irn, p_tgt->inh.irn, e->costs));
1100                 }
1101         }
1102         obstack_free(&cloud->obst, edges);
1103
1104         for(i = 0; i < cloud->n_memb; ++i) {
1105                 co2_cloud_irn_t *ci = cloud->seq[i];
1106                 int j;
1107
1108                 ci->mst_childs      = obstack_alloc(&cloud->obst, ci->mst_n_childs * sizeof(ci->mst_childs));
1109                 ci->col_costs       = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->col_costs[0]));
1110                 ci->tmp_coloring    = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->tmp_coloring[0]));
1111                 ci->fronts          = obstack_alloc(&cloud->obst, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
1112                 ci->color_badness   = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->fronts[0]));
1113                 memset(ci->color_badness, 0, env->n_regs * sizeof(ci->color_badness[0]));
1114                 memset(ci->col_costs, 0, env->n_regs * sizeof(ci->col_costs[0]));
1115                 memset(ci->tmp_coloring, 0, env->n_regs * sizeof(ci->tmp_coloring[0]));
1116                 memset(ci->fronts, 0, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
1117
1118                 for(j = 0; j < env->n_regs; j++)
1119                         ci->col_costs[j] = INT_MAX;
1120
1121                 ci->mst_n_childs    = 0;
1122         }
1123
1124         /* build the child arrays in the nodes */
1125         for(i = 0; i < cloud->n_memb; ++i) {
1126                 co2_cloud_irn_t *ci = cloud->seq[i];
1127                 if(ci->mst_parent != ci)
1128                         ci->mst_parent->mst_childs[ci->mst_parent->mst_n_childs++] = ci;
1129                 else {
1130                         cloud->mst_root  = ci;
1131                         cloud->mst_costs = 0;
1132                 }
1133         }
1134
1135         /* Compute the "best" colorings. */
1136         // best_col = cloud_mst_build_colorings(cloud->mst_root, 0);
1137
1138         determine_color_badness(cloud->mst_root, 0);
1139         INIT_LIST_HEAD(&changed);
1140         best_col = coalesce_top_down(cloud->mst_root, -1, &changed, 0);
1141
1142         /* The coloring should represent the one with the best costs. */
1143         materialize_coloring(&changed);
1144         DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1145                 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1146
1147         /* Fix all nodes in the cloud. */
1148         for(i = 0; i < cloud->n_memb; ++i)
1149                 cloud->seq[i]->inh.fixed = 1;
1150
1151         /* Free all space used while optimizing this cloud. */
1152         obstack_free(&cloud->obst, NULL);
1153 }
1154
1155 static int cloud_costs(co2_cloud_t *cloud)
1156 {
1157         int i, costs = 0;
1158         neighb_t *n;
1159
1160         for(i = 0; i < cloud->n_memb; ++i) {
1161                 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1162                 col_t col = get_col(cloud->env, ci->irn);
1163                 co_gs_foreach_neighb(ci->aff, n) {
1164                         col_t n_col = get_col(cloud->env, n->irn);
1165                         costs += col != n_col ? n->costs : 0;
1166                 }
1167         }
1168
1169         return costs / 2;
1170 }
1171
1172 static void process(co2_t *env)
1173 {
1174         affinity_node_t *a;
1175         co2_cloud_t *pos;
1176         co2_cloud_t **clouds;
1177         int n_clouds;
1178         int i;
1179         int init_costs  = 0;
1180         int all_costs   = 0;
1181         int final_costs = 0;
1182
1183         n_clouds = 0;
1184         co_gs_foreach_aff_node(env->co, a) {
1185                 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1186
1187                 if(!ci->cloud) {
1188                         co2_cloud_t *cloud = new_cloud(env, a);
1189                         n_clouds++;
1190                 }
1191         }
1192
1193         i = 0;
1194         clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1195         list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1196                 clouds[i++] = pos;
1197         qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1198
1199         for(i = 0; i < n_clouds; ++i) {
1200                 init_costs  += cloud_costs(clouds[i]);
1201                 process_cloud(clouds[i]);
1202                 all_costs   += clouds[i]->costs;
1203                 final_costs += cloud_costs(clouds[i]);
1204
1205                 /* Dump the IFG if the user demanded it. */
1206                 if (dump_flags & DUMP_CLOUD) {
1207                         char buf[256];
1208                         FILE *f;
1209
1210                         ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1211                         if(f = fopen(buf, "wt")) {
1212                                 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1213                                 fclose(f);
1214                         }
1215                 }
1216         }
1217
1218         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1219
1220         xfree(clouds);
1221 }
1222
1223 static void writeback_colors(co2_t *env)
1224 {
1225         const arch_env_t *aenv = env->co->aenv;
1226         co2_irn_t *irn;
1227
1228         for(irn = env->touched; irn; irn = irn->touched_next) {
1229                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1230                 arch_set_irn_register(aenv, irn->irn, reg);
1231         }
1232 }
1233
1234
1235 /*
1236   ___ _____ ____   ____   ___ _____   ____                        _
1237  |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1238   | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1239   | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
1240  |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1241                                                            |_|            |___/
1242 */
1243
1244 static const char *get_dot_color_name(int col)
1245 {
1246         static const char *names[] = {
1247                 "blue",
1248                 "red",
1249                 "green",
1250                 "yellow",
1251                 "cyan",
1252                 "magenta",
1253                 "orange",
1254                 "chocolate",
1255                 "beige",
1256                 "navy",
1257                 "darkgreen",
1258                 "darkred",
1259                 "lightPink",
1260                 "chartreuse",
1261                 "lightskyblue",
1262                 "linen",
1263                 "pink",
1264                 "lightslateblue",
1265                 "mintcream",
1266                 "red",
1267                 "darkolivegreen",
1268                 "mediumblue",
1269                 "mistyrose",
1270                 "salmon",
1271                 "darkseagreen",
1272                 "mediumslateblue"
1273                 "moccasin",
1274                 "tomato",
1275                 "forestgreen",
1276                 "darkturquoise",
1277                 "palevioletred"
1278         };
1279
1280         return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1281 }
1282
1283 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1284 {
1285         arch_register_req_t req;
1286
1287         arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1288         if(arch_register_req_is(&req, limited))
1289                 return "diamond";
1290
1291         if(ci->fixed)
1292                 return "rectangle";
1293
1294         if(ci->tmp_fixed)
1295                 return "hexagon";
1296
1297         return "ellipse";
1298 }
1299
1300 static void ifg_dump_graph_attr(FILE *f, void *self)
1301 {
1302         fprintf(f, "overlay=false");
1303 }
1304
1305 static int ifg_is_dump_node(void *self, ir_node *irn)
1306 {
1307         co2_t *env = self;
1308         return !arch_irn_is(env->co->aenv, irn, ignore);
1309 }
1310
1311 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1312 {
1313         co2_t *env    = self;
1314         co2_irn_t *ci = get_co2_irn(env, irn);
1315         int peri      = 1;
1316
1317         if(ci->aff) {
1318                 co2_cloud_irn_t *cci = (void *) ci;
1319                 if (cci->cloud && cci->cloud->mst_root == cci)
1320                         peri = 2;
1321         }
1322
1323         ir_fprintf(f, "label=\"%+F\" style=filled peripheries=%d color=%s shape=%s", irn, peri,
1324                 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1325 }
1326
1327 static void ifg_dump_at_end(FILE *file, void *self)
1328 {
1329         co2_t *env = self;
1330         affinity_node_t *a;
1331
1332         co_gs_foreach_aff_node(env->co, a) {
1333                 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1334                 int idx = get_irn_idx(a->irn);
1335                 neighb_t *n;
1336
1337                 co_gs_foreach_neighb(a, n) {
1338                         int nidx = get_irn_idx(n->irn);
1339                         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1340
1341                         if(idx < nidx) {
1342                                 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1343                                 const char *arr = "arrowhead=dot arrowtail=dot";
1344
1345                                 if(ci->mst_parent == ai)
1346                                         arr = "arrowtail=normal";
1347                                 else if(ai->mst_parent == ci)
1348                                         arr = "arrowhead=normal";
1349
1350                                 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1351                         }
1352                 }
1353         }
1354 }
1355
1356
1357 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1358         ifg_is_dump_node,
1359         ifg_dump_graph_attr,
1360         ifg_dump_node_attr,
1361         NULL,
1362         NULL,
1363         ifg_dump_at_end
1364 };
1365
1366
1367 void co_solve_heuristic_new(copy_opt_t *co)
1368 {
1369         co2_t env;
1370         FILE *f;
1371
1372         phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1373         env.touched     = NULL;
1374         env.visited     = 0;
1375         env.co          = co;
1376         env.n_regs      = co->cls->n_regs;
1377         env.ignore_regs = bitset_alloca(co->cls->n_regs);
1378         arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1379         bitset_flip_all(env.ignore_regs);
1380         be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1381         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1382         INIT_LIST_HEAD(&env.cloud_head);
1383
1384         if(dump_flags & DUMP_BEFORE) {
1385                 if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) {
1386                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1387                         fclose(f);
1388                 }
1389         }
1390
1391         process(&env);
1392
1393         if(dump_flags & DUMP_AFTER) {
1394                 if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) {
1395                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1396                         fclose(f);
1397                 }
1398         }
1399
1400         writeback_colors(&env);
1401         phase_free(&env.ph);
1402 }