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