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

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