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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       More experiments on coalescing.
  23  * @author      Sebastian Hack
  24  * @date        14.04.2006
  25  * @version     $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include <libcore/lc_opts.h>
  32 #include <libcore/lc_opts_enum.h>
  33
  34 #include <stdlib.h>
  35 #include <limits.h>
  36
  37 #include "list.h"
  38 #include "pdeq.h"
  39 #include "bitset.h"
  40 #include "raw_bitset.h"
  41
  42 #include "debug.h"
  43 #include "bitfiddle.h"
  44
  45 #include "irphase_t.h"
  46 #include "irgraph_t.h"
  47 #include "irnode_t.h"
  48 #include "irprintf.h"
  49 #include "irtools.h"
  50
  51 #include "bemodule.h"
  52 #include "beabi.h"
  53 #include "benode_t.h"
  54 #include "becopyopt.h"
  55 #include "becopyopt_t.h"
  56 #include "bechordal_t.h"
  57 #include "beirg_t.h"
  58
  59 #define DUMP_BEFORE 1
  60 #define DUMP_AFTER  2
  61 #define DUMP_CLOUD  4
  62 #define DUMP_ALL    2 * DUMP_CLOUD - 1
  63
  64 static unsigned dump_flags      = 0;
  65 static int      subtree_iter    = 4;
  66 static int      max_depth       = 20;
  67 static double   constr_factor   = 0.9;
  68
  69 /* Options using libcore */
  70 static const lc_opt_enum_mask_items_t dump_items[] = {
  71         { "before",  DUMP_BEFORE },
  72         { "after",   DUMP_AFTER  },
  73         { "cloud",   DUMP_CLOUD  },
  74         { "all",     DUMP_ALL    },
  75         { NULL,      0 }
  76 };
  77
  78 static lc_opt_enum_mask_var_t dump_var = {
  79         &dump_flags, dump_items
  80 };
  81
  82 static const lc_opt_table_entry_t options[] = {
  83         LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                                         &dump_var),
  84         LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes",                           &subtree_iter),
  85         LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
  86         LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
  87         LC_OPT_ENT_NULL
  88 };
  89
  90 void be_init_copyheur2(void)
  91 {
  92         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
  93         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
  94         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
  95         lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
  96
  97         lc_opt_add_table(co2_grp, options);
  98 }
  99
 100 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
 101
 102 /*
 103   ____  _             _
 104  / ___|| |_ __ _ _ __| |_
 105  \___ \| __/ _` | '__| __|
 106   ___) | || (_| | |  | |_
 107  |____/ \__\__,_|_|   \__|
 108
 109 */
 110
 111 #define INFEASIBLE(cost) ((cost) == INT_MAX)
 112
 113 static be_ifg_dump_dot_cb_t ifg_dot_cb;
 114
 115 typedef unsigned col_t;
 116
 117 typedef struct _co2_irn_t       co2_irn_t;
 118 typedef struct _co2_cloud_t     co2_cloud_t;
 119 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
 120
 121 typedef struct {
 122         col_t col;
 123         int costs;
 124 } col_cost_pair_t;
 125
 126 typedef struct {
 127         ir_phase     ph;
 128         copy_opt_t *co;
 129         bitset_t   *ignore_regs;
 130         co2_irn_t  *touched;
 131         int         visited;
 132         int         n_regs;
 133         struct list_head cloud_head;
 134         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 135 } co2_t;
 136
 137 struct _co2_irn_t {
 138         ir_node         *irn;
 139         affinity_node_t *aff;
 140         co2_irn_t       *touched_next;
 141         col_t            tmp_col;
 142         col_t            orig_col;
 143         int                              last_color_change;
 144         bitset_t        *adm_cache;
 145         unsigned         fixed          : 1;
 146         unsigned         tmp_fixed      : 1;
 147         unsigned         is_constrained : 1;
 148         struct list_head changed_list;
 149 };
 150
 151 struct _co2_cloud_irn_t {
 152         struct _co2_irn_t  inh;
 153         co2_cloud_t       *cloud;
 154         int                visited;
 155         int                index;
 156         co2_cloud_irn_t   *mst_parent;
 157         int                mst_costs;
 158         int                mst_n_childs;
 159         co2_cloud_irn_t  **mst_childs;
 160         int               *col_costs;
 161         int                costs;
 162         int               *fronts;
 163         int               *color_badness;
 164         col_cost_pair_t   *tmp_coloring;
 165         struct list_head   cloud_list;
 166         struct list_head   mst_list;
 167 };
 168
 169 struct _co2_cloud_t {
 170         co2_t            *env;
 171         struct obstack    obst;
 172         int               costs;
 173         int               mst_costs;
 174         int               inevit;
 175         int               best_costs;
 176         int               n_memb;
 177         int               n_constr;
 178         int               max_degree;
 179         int                           ticks;
 180         double            freedom;
 181         co2_cloud_irn_t  *master;
 182         co2_cloud_irn_t  *mst_root;
 183         co2_cloud_irn_t **seq;
 184         struct list_head  members_head;
 185         struct list_head  list;
 186 };
 187
 188 typedef struct {
 189         co2_cloud_irn_t *src, *tgt;
 190         int costs;
 191 } edge_t;
 192
 193 #define FRONT_BASE(ci,col)  ((ci)->fronts + col * (ci)->mst_n_childs)
 194
 195 #define get_co2_irn(co2, irn)         ((co2_irn_t *)       phase_get_or_set_irn_data(&co2->ph, irn))
 196 #define get_co2_cloud_irn(co2, irn)   ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
 197
 198 static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data)
 199 {
 200         co2_t *env         = (co2_t *) ph;
 201         affinity_node_t *a = get_affinity_info(env->co, irn);
 202         size_t size        = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
 203         co2_irn_t *ci      = data ? data : phase_alloc(ph, size);
 204
 205         memset(ci, 0, size);
 206         INIT_LIST_HEAD(&ci->changed_list);
 207         ci->touched_next = env->touched;
 208         ci->orig_col     = get_irn_col(env->co, irn);
 209         env->touched     = ci;
 210         ci->irn          = irn;
 211         ci->aff          = a;
 212
 213         if(a) {
 214                 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
 215                 INIT_LIST_HEAD(&cci->cloud_list);
 216                 cci->mst_parent   = cci;
 217         }
 218
 219         return ci;
 220 }
 221
 222 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
 223
 224 static int cmp_clouds_gt(const void *a, const void *b)
 225 {
 226         const co2_cloud_t * const *p = a;
 227         const co2_cloud_t * const *q = b;
 228         double c = CLOUD_WEIGHT(*p);
 229         double d = CLOUD_WEIGHT(*q);
 230         return QSORT_CMP(d, c);
 231 }
 232
 233 /**
 234  * An order on color/costs pairs.
 235  * If the costs are equal, we use the color as a kind of normalization.
 236  */
 237 static int col_cost_pair_lt(const void *a, const void *b)
 238 {
 239         const col_cost_pair_t *p = a;
 240         const col_cost_pair_t *q = b;
 241         int c = p->costs;
 242         int d = q->costs;
 243         return QSORT_CMP(c, d);
 244 }
 245
 246 int cmp_edges(const void *a, const void *b)
 247 {
 248         const edge_t *p = a;
 249         const edge_t *q = b;
 250         return QSORT_CMP(q->costs, p->costs);
 251 }
 252
 253 static col_t get_col(co2_t *env, ir_node *irn)
 254 {
 255         co2_irn_t *ci = get_co2_irn(env, irn);
 256         return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
 257 }
 258
 259 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
 260 {
 261         co2_irn_t *ci = get_co2_irn(env, irn);
 262         return ci->fixed || ci->tmp_fixed;
 263 }
 264
 265 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
 266 {
 267         if(ci->adm_cache == NULL) {
 268                 const arch_register_req_t *req;
 269                 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
 270                 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
 271
 272                 if(arch_register_req_is(req, limited)) {
 273                         int i, n;
 274
 275                         n = env->n_regs;
 276                         for(i = 0; i < n; ++i) {
 277                                 if(rbitset_is_set(req->limited, i))
 278                                         bitset_set(ci->adm_cache, i);
 279                         }
 280                         ci->is_constrained = 1;
 281                 } else {
 282                         bitset_copy(ci->adm_cache, env->ignore_regs);
 283                         bitset_flip_all(ci->adm_cache);
 284                 }
 285         }
 286
 287         return ci->adm_cache;
 288 }
 289
 290 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
 291 {
 292         bitset_copy(bs, get_adm(env, ci));
 293         return bs;
 294 }
 295
 296 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
 297 {
 298         bitset_t *bs = get_adm(env, ci);
 299         return bitset_is_set(bs, col);
 300 }
 301
 302 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
 303 {
 304         if(!ci->adm_cache)
 305                 get_adm(env, ci);
 306         return ci->is_constrained;
 307 }
 308
 309 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
 310 {
 311         const arch_register_req_t *req;
 312
 313         req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
 314
 315         if (arch_register_req_is(req, limited)) {
 316                 unsigned n_regs   = env->co->cls->n_regs;
 317                 unsigned n_constr = 0;
 318                 unsigned i;
 319
 320                 n_constr = rbitset_popcnt(req->limited, n_regs);
 321                 for (i = 0; i < n_regs; ++i) {
 322                         if (rbitset_is_set(req->limited, i)) {
 323                                 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
 324                         }
 325                 }
 326         }
 327 }
 328
 329 /**
 330  * Determine costs which shall indicate how cheap/expensive it is to try
 331  * to assign a node some color.
 332  * The costs are computed for all colors. INT_MAX means that it is impossible
 333  * to give the node that specific color.
 334  *
 335  * @param env       The co2 this pointer.
 336  * @param irn       The node.
 337  * @param col_costs An array of colors x costs where the costs are written to.
 338  */
 339 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
 340 {
 341         ir_node *irn       = ci->irn;
 342         be_ifg_t *ifg      = env->co->cenv->ifg;
 343         int n_regs         = env->co->cls->n_regs;
 344         bitset_t *forb     = bitset_alloca(n_regs);
 345         affinity_node_t *a = ci->aff;
 346
 347         bitset_pos_t elm;
 348         ir_node *pos;
 349         void *it;
 350         int i;
 351
 352         /* Put all forbidden colors into the aux bitset. */
 353         admissible_colors(env, ci, forb);
 354         bitset_flip_all(forb);
 355
 356         for(i = 0; i < n_regs; ++i) {
 357                 col_costs[i].col   = i;
 358                 col_costs[i].costs = 0;
 359         }
 360
 361         if(a) {
 362                 neighb_t *n;
 363
 364                 co_gs_foreach_neighb(a, n) {
 365                         if(color_is_fix(env, n->irn)) {
 366                                 col_t col = get_col(env, n->irn);
 367                                 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
 368                         }
 369
 370                         incur_constraint_costs(env, n->irn, col_costs, -n->costs);
 371                 }
 372         }
 373
 374         it = be_ifg_neighbours_iter_alloca(ifg);
 375         be_ifg_foreach_neighbour(ifg, it, irn, pos) {
 376                 col_t col = get_col(env, pos);
 377                 if(color_is_fix(env, pos)) {
 378                         col_costs[col].costs  = INT_MAX;
 379                 }
 380                 else {
 381                         incur_constraint_costs(env, pos, col_costs, INT_MAX);
 382                         col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
 383                 }
 384         }
 385         be_ifg_neighbours_break(ifg, it);
 386
 387         /* Set the costs to infinity for each color which is not allowed at this node. */
 388         bitset_foreach(forb, elm) {
 389                 col_costs[elm].costs  = INT_MAX;
 390         }
 391
 392 }
 393
 394 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
 395 {
 396         int n_regs = env->co->cls->n_regs;
 397         int i;
 398
 399         for(i = 0; i < n_regs; ++i) {
 400                 seq[i].col   = i;
 401                 seq[i].costs = INT_MAX;
 402         }
 403
 404         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, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 429
 430 static int recolor(co2_t *env, 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                 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, 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, 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         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 ? -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         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, irn->irn, reg);
1107         }
1108 }
1109
1110
1111 /*
1112   ___ _____ ____   ____   ___ _____   ____                        _
1113  |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1114   | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1115   | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
1116  |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1117                                                            |_|            |___/
1118 */
1119
1120 static const char *get_dot_color_name(int 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         fprintf(f, "overlay=false");
1179 }
1180
1181 static int ifg_is_dump_node(void *self, ir_node *irn)
1182 {
1183         co2_t *env = self;
1184         return !arch_irn_is(env->co->aenv, irn, ignore);
1185 }
1186
1187 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1188 {
1189         co2_t *env    = self;
1190         co2_irn_t *ci = get_co2_irn(env, irn);
1191         int peri      = 1;
1192
1193         char buf[128] = "";
1194
1195         if(ci->aff) {
1196                 co2_cloud_irn_t *cci = (void *) ci;
1197                 if (cci->cloud && cci->cloud->mst_root == cci)
1198                         peri = 2;
1199
1200                 if(cci->cloud && cci->cloud->mst_root)
1201                         ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1202         }
1203
1204         ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1205                 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1206 }
1207
1208 static void ifg_dump_at_end(FILE *file, void *self)
1209 {
1210         co2_t *env = self;
1211         affinity_node_t *a;
1212
1213         co_gs_foreach_aff_node(env->co, a) {
1214                 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1215                 int idx = get_irn_idx(a->irn);
1216                 neighb_t *n;
1217
1218                 if(ai->mst_parent != ai)
1219                         fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1220
1221                 co_gs_foreach_neighb(a, n) {
1222                         int nidx = get_irn_idx(n->irn);
1223                         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1224
1225                         if(idx < nidx) {
1226                                 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1227                                 const char *arr = "arrowhead=dot arrowtail=dot";
1228
1229                                 if(ci->mst_parent == ai)
1230                                         arr = "arrowtail=normal";
1231                                 else if(ai->mst_parent == ci)
1232                                         arr = "arrowhead=normal";
1233
1234                                 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1235                         }
1236                 }
1237         }
1238 }
1239
1240
1241 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1242         ifg_is_dump_node,
1243         ifg_dump_graph_attr,
1244         ifg_dump_node_attr,
1245         NULL,
1246         NULL,
1247         ifg_dump_at_end
1248 };
1249
1250
1251 int co_solve_heuristic_new(copy_opt_t *co)
1252 {
1253         char  buf[256];
1254         co2_t env;
1255         FILE  *f;
1256
1257         phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1258         env.touched     = NULL;
1259         env.visited     = 0;
1260         env.co          = co;
1261         env.n_regs      = co->cls->n_regs;
1262         env.ignore_regs = bitset_alloca(co->cls->n_regs);
1263         arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1264         bitset_flip_all(env.ignore_regs);
1265         be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1266         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1267         INIT_LIST_HEAD(&env.cloud_head);
1268
1269         if(dump_flags & DUMP_BEFORE) {
1270                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1271                 f = fopen(buf, "wt");
1272                 if (f != NULL) {
1273                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1274                         fclose(f);
1275                 }
1276         }
1277
1278         process(&env);
1279
1280         if(dump_flags & DUMP_AFTER) {
1281                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1282                 f = fopen(buf, "wt");
1283                 if (f != NULL) {
1284                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1285                         fclose(f);
1286                 }
1287         }
1288
1289         writeback_colors(&env);
1290         phase_free(&env.ph);
1291         return 0;
1292 }