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 = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
 896         pdeq *q;
 897
 898         edge_t *edges;
 899         int i;
 900         int best_col;
 901
 902         memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
 903
 904         /* Collect all edges in the cloud on an obstack and sort the increasingly */
 905         obstack_init(&cloud->obst);
 906         for(i = 0; i < cloud->n_memb; ++i) {
 907                 co2_cloud_irn_t *ci = cloud->seq[i];
 908                 neighb_t *n;
 909
 910                 co_gs_foreach_neighb(ci->inh.aff, n) {
 911                         co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
 912                         if(ci->index < ni->index) {
 913                                 edge_t e;
 914                                 e.src   = ci;
 915                                 e.tgt   = ni;
 916                                 e.costs = n->costs;
 917                                 obstack_grow(&cloud->obst, &e, sizeof(e));
 918                                 n_edges++;
 919                         }
 920                 }
 921         }
 922         edges = obstack_finish(&cloud->obst);
 923         qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
 924
 925         /* Compute the maximum spanning tree using Kruskal/Union-Find */
 926         DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
 927         for(i = 0; i < n_edges; ++i) {
 928                 edge_t *e        = &edges[i];
 929                 co2_cloud_irn_t *rs = find_mst_root(e->src);
 930                 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
 931
 932                 /* if the union/find roots are different */
 933                 if(rs != rt) {
 934                         int si = e->src->index;
 935                         int ti = e->tgt->index;
 936
 937                         /* unify the sets */
 938                         rs->mst_parent = rt;
 939                         DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
 940
 941                         /* this edge is in the MST, so set it in the bitset. */
 942                         mst_edges[si * cloud->n_memb + ti] = e->costs;
 943                         mst_edges[ti * cloud->n_memb + si] = e->costs;
 944                 }
 945         }
 946         obstack_free(&cloud->obst, edges);
 947
 948         cloud->master->mst_parent = cloud->master;
 949         cloud->mst_root = cloud->master;
 950         q = new_pdeq1(cloud->master);
 951         while(!pdeq_empty(q)) {
 952                 co2_cloud_irn_t *ci = pdeq_getl(q);
 953                 int ofs    = ci->index * cloud->n_memb;
 954                 int end    = ofs + cloud->n_memb;
 955                 int i;
 956
 957                 ci->mst_n_childs = 0;
 958                 for(i = ofs; i < end; ++i) {
 959                         if(mst_edges[i] != 0) {
 960                                 int other = i - ofs;
 961                                 co2_cloud_irn_t *child = cloud->seq[i - ofs];
 962
 963                                 /* put the child to the worklist */
 964                                 pdeq_putr(q, child);
 965
 966                                 /* make ci the parent of the child and add the child to the children array of the parent */
 967                                 child->mst_parent = ci;
 968                                 child->mst_costs  = mst_edges[i];
 969                                 ci->mst_n_childs++;
 970                                 obstack_ptr_grow(&cloud->obst, child);
 971
 972                                 mst_edges[other * cloud->n_memb + ci->index] = 0;
 973                                 mst_edges[i] = 0;
 974                         }
 975                 }
 976
 977                 obstack_ptr_grow(&cloud->obst, NULL);
 978                 ci->mst_childs = obstack_finish(&cloud->obst);
 979         }
 980         del_pdeq(q);
 981         free(mst_edges);
 982
 983
 984         DBG((env->dbg, LEVEL_3, "mst:\n"));
 985         for(i = 0; i < cloud->n_memb; ++i) {
 986                 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
 987                 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
 988         }
 989
 990         for(i = 0; i < cloud->n_memb; ++i) {
 991                 co2_cloud_irn_t *ci = cloud->seq[i];
 992                 int n_childs = ci->mst_n_childs;
 993                 int j;
 994
 995                 ci->col_costs       = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
 996                 ci->tmp_coloring    = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
 997                 ci->fronts          = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
 998                 ci->color_badness   = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
 999                 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
1000                 memset(ci->col_costs,     0, n_regs * sizeof(ci->col_costs[0]));
1001                 memset(ci->tmp_coloring,  0, n_regs * sizeof(ci->tmp_coloring[0]));
1002                 memset(ci->fronts,        0, n_regs * n_childs * sizeof(ci->fronts[0]));
1003
1004                 for(j = 0; j < env->n_regs; j++)
1005                         ci->col_costs[j] = INT_MAX;
1006
1007         }
1008
1009         determine_color_badness(cloud->mst_root, 0);
1010         best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1011         unfix_subtree(cloud->mst_root);
1012         apply_coloring(cloud->mst_root, best_col, 0);
1013
1014         /* The coloring should represent the one with the best costs. */
1015         //materialize_coloring(&changed);
1016         DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1017                 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1018
1019         /* Fix all nodes in the cloud. */
1020         for(i = 0; i < cloud->n_memb; ++i)
1021                 cloud->seq[i]->inh.fixed = 1;
1022
1023         /* Free all space used while optimizing this cloud. */
1024         obstack_free(&cloud->obst, NULL);
1025 }
1026
1027 static int cloud_costs(co2_cloud_t *cloud)
1028 {
1029         int i, costs = 0;
1030         neighb_t *n;
1031
1032         for(i = 0; i < cloud->n_memb; ++i) {
1033                 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1034                 col_t col = get_col(cloud->env, ci->irn);
1035                 co_gs_foreach_neighb(ci->aff, n) {
1036                         col_t n_col = get_col(cloud->env, n->irn);
1037                         costs += col != n_col ? n->costs : 0;
1038                 }
1039         }
1040
1041         return costs / 2;
1042 }
1043
1044 static void process(co2_t *env)
1045 {
1046         affinity_node_t *a;
1047         co2_cloud_t *pos;
1048         co2_cloud_t **clouds;
1049         int n_clouds;
1050         int i;
1051         int init_costs  = 0;
1052         int all_costs   = 0;
1053         int final_costs = 0;
1054
1055         n_clouds = 0;
1056         co_gs_foreach_aff_node(env->co, a) {
1057                 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1058
1059                 if(!ci->cloud) {
1060                         new_cloud(env, a);
1061                         n_clouds++;
1062                 }
1063         }
1064
1065         i = 0;
1066         clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1067         list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1068                 clouds[i++] = pos;
1069         qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1070
1071         for(i = 0; i < n_clouds; ++i) {
1072                 init_costs  += cloud_costs(clouds[i]);
1073
1074                 /* Process the cloud. */
1075                 process_cloud(clouds[i]);
1076
1077                 all_costs   += clouds[i]->costs;
1078                 final_costs += cloud_costs(clouds[i]);
1079
1080                 /* Dump the IFG if the user demanded it. */
1081                 if (dump_flags & DUMP_CLOUD) {
1082                         char buf[256];
1083                         FILE *f;
1084
1085                         ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1086                         f = fopen(buf, "wt");
1087                         if(f != NULL) {
1088                                 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1089                                 fclose(f);
1090                         }
1091                 }
1092         }
1093
1094         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1095
1096         xfree(clouds);
1097 }
1098
1099 static void writeback_colors(co2_t *env)
1100 {
1101         const arch_env_t *aenv = env->co->aenv;
1102         co2_irn_t *irn;
1103
1104         for(irn = env->touched; irn; irn = irn->touched_next) {
1105                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1106                 arch_set_irn_register(aenv, (ir_node *) irn->irn, reg);
1107         }
1108 }
1109
1110
1111 /*
1112   ___ _____ ____   ____   ___ _____   ____                        _
1113  |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1114   | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1115   | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
1116  |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1117                                                            |_|            |___/
1118 */
1119
1120 static const char *get_dot_color_name(size_t col)
1121 {
1122         static const char *names[] = {
1123                 "blue",
1124                 "red",
1125                 "green",
1126                 "yellow",
1127                 "cyan",
1128                 "magenta",
1129                 "orange",
1130                 "chocolate",
1131                 "beige",
1132                 "navy",
1133                 "darkgreen",
1134                 "darkred",
1135                 "lightPink",
1136                 "chartreuse",
1137                 "lightskyblue",
1138                 "linen",
1139                 "pink",
1140                 "lightslateblue",
1141                 "mintcream",
1142                 "red",
1143                 "darkolivegreen",
1144                 "mediumblue",
1145                 "mistyrose",
1146                 "salmon",
1147                 "darkseagreen",
1148                 "mediumslateblue"
1149                 "moccasin",
1150                 "tomato",
1151                 "forestgreen",
1152                 "darkturquoise",
1153                 "palevioletred"
1154         };
1155
1156         return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1157 }
1158
1159 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1160 {
1161         const arch_register_req_t *req;
1162
1163         req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
1164         if(arch_register_req_is(req, limited))
1165                 return "diamond";
1166
1167         if(ci->fixed)
1168                 return "rectangle";
1169
1170         if(ci->tmp_fixed)
1171                 return "hexagon";
1172
1173         return "ellipse";
1174 }
1175
1176 static void ifg_dump_graph_attr(FILE *f, void *self)
1177 {
1178         (void) self;
1179         fprintf(f, "overlay=false");
1180 }
1181
1182 static int ifg_is_dump_node(void *self, ir_node *irn)
1183 {
1184         co2_t *env = self;
1185         return !arch_irn_is(env->co->aenv, irn, ignore);
1186 }
1187
1188 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1189 {
1190         co2_t *env    = self;
1191         co2_irn_t *ci = get_co2_irn(env, irn);
1192         int peri      = 1;
1193
1194         char buf[128] = "";
1195
1196         if(ci->aff) {
1197                 co2_cloud_irn_t *cci = (void *) ci;
1198                 if (cci->cloud && cci->cloud->mst_root == cci)
1199                         peri = 2;
1200
1201                 if(cci->cloud && cci->cloud->mst_root)
1202                         ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1203         }
1204
1205         ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1206                 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1207 }
1208
1209 static void ifg_dump_at_end(FILE *file, void *self)
1210 {
1211         co2_t *env = self;
1212         affinity_node_t *a;
1213
1214         co_gs_foreach_aff_node(env->co, a) {
1215                 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1216                 int idx = get_irn_idx(a->irn);
1217                 neighb_t *n;
1218
1219                 if(ai->mst_parent != ai)
1220                         fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1221
1222                 co_gs_foreach_neighb(a, n) {
1223                         int nidx = get_irn_idx(n->irn);
1224                         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1225
1226                         if(idx < nidx) {
1227                                 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1228                                 const char *arr = "arrowhead=dot arrowtail=dot";
1229
1230                                 if(ci->mst_parent == ai)
1231                                         arr = "arrowtail=normal";
1232                                 else if(ai->mst_parent == ci)
1233                                         arr = "arrowhead=normal";
1234
1235                                 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1236                         }
1237                 }
1238         }
1239 }
1240
1241
1242 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1243         ifg_is_dump_node,
1244         ifg_dump_graph_attr,
1245         ifg_dump_node_attr,
1246         NULL,
1247         NULL,
1248         ifg_dump_at_end
1249 };
1250
1251
1252 int co_solve_heuristic_new(copy_opt_t *co)
1253 {
1254         char  buf[256];
1255         co2_t env;
1256         FILE  *f;
1257
1258         phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1259         env.touched     = NULL;
1260         env.visited     = 0;
1261         env.co          = co;
1262         env.n_regs      = co->cls->n_regs;
1263         env.ignore_regs = bitset_alloca(co->cls->n_regs);
1264         arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1265         bitset_flip_all(env.ignore_regs);
1266         be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1267         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1268         INIT_LIST_HEAD(&env.cloud_head);
1269
1270         if(dump_flags & DUMP_BEFORE) {
1271                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1272                 f = fopen(buf, "wt");
1273                 if (f != NULL) {
1274                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1275                         fclose(f);
1276                 }
1277         }
1278
1279         process(&env);
1280
1281         if(dump_flags & DUMP_AFTER) {
1282                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1283                 f = fopen(buf, "wt");
1284                 if (f != NULL) {
1285                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1286                         fclose(f);
1287                 }
1288         }
1289
1290         writeback_colors(&env);
1291         phase_free(&env.ph);
1292         return 0;
1293 }