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