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