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

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