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