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

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