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

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