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

   1 /*
   2  * Copyright (C) 1995-2007 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       Simple copy minimization heuristics.
  23  * @author      Christian Wuerdig
  24  * @date        27.04.2007
  25  * @version     $Id$
  26  *
  27  * This is the C implementation of the mst algorithm
  28  * originally written in Java by Sebastian Hack.
  29  * (also known as "heur3" :)
  30  * Performs simple copy minimization.
  31  */
  32 #ifdef HAVE_CONFIG_H
  33 #include "config.h"
  34 #endif /* HAVE_CONFIG_H */
  35
  36 #include <float.h>
  37
  38 #include "array.h"
  39 #include "irnode_t.h"
  40 #include "bitset.h"
  41 #include "raw_bitset.h"
  42 #include "irphase_t.h"
  43 #include "pqueue.h"
  44 #include "pset_new.h"
  45 #include "xmalloc.h"
  46 #include "pdeq.h"
  47 #include "irprintf.h"
  48 #include "irbitset.h"
  49 #include "error.h"
  50
  51 #include "bearch.h"
  52 #include "beifg.h"
  53 #include "be_t.h"
  54 #include "becopyopt_t.h"
  55 #include "bemodule.h"
  56
  57 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  58
  59 #define COL_COST_INFEASIBLE       DBL_MAX
  60 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
  61 #define NEIGHBOUR_CONSTR_COSTS    64.0
  62
  63 #define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0))
  64 #define DBG_COL_COST(env, level, cost)   DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0))
  65
  66 static int last_chunk_id = 0;
  67
  68 typedef struct _col_cost_t {
  69         int    col;
  70         double cost;
  71 } col_cost_t;
  72
  73 /**
  74  * An affinity chunk.
  75  */
  76 typedef struct _aff_chunk_t {
  77         ir_node **n;
  78         bitset_t *nodes;                /**< A bitset containing all nodes inside this chunk. */
  79         bitset_t *interfere;            /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
  80         int      weight;                /**< Weight of this chunk */
  81         unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
  82         unsigned deleted           : 1; /**< Set if the was deleted. */
  83         int      id;                    /**< For debugging: An id of this chunk. */
  84 } aff_chunk_t;
  85
  86 /**
  87  * An affinity edge.
  88  */
  89 typedef struct _aff_edge_t {
  90         ir_node *src;                   /**< Source node. */
  91         ir_node *tgt;                   /**< Target node. */
  92         double  weight;                 /**< The weight of this edge. */
  93 } aff_edge_t;
  94
  95 /* main coalescing environment */
  96 typedef struct _co_mst_env_t {
  97         int              n_regs;         /**< number of regs in class */
  98         int              k;              /**< number of non-ignore registers in class */
  99         bitset_t         *ignore_regs;   /**< set containing all global ignore registers */
 100         ir_phase         ph;             /**< phase object holding data for nodes */
 101         pqueue           *chunks;        /**< priority queue for chunks */
 102         pset             *chunkset;      /**< set holding all chunks */
 103         be_ifg_t         *ifg;           /**< the interference graph */
 104         const arch_env_t *aenv;          /**< the arch environment */
 105         copy_opt_t       *co;            /**< the copy opt object */
 106 } co_mst_env_t;
 107
 108 /* stores coalescing related information for a node */
 109 typedef struct _co_mst_irn_t {
 110         ir_node     *irn;              /**< the irn this information belongs to */
 111         aff_chunk_t *chunk;            /**< the chunk this irn belongs to */
 112         bitset_t    *adm_colors;       /**< set of admissible colors for this irn */
 113         ir_node     **int_neighs;      /**< array of all interfering neighbours (cached for speed reasons) */
 114         int         n_neighs;          /**< length of the interfering neighbours array. */
 115         int         int_aff_neigh;     /**< number of interfering affinity neighbours */
 116         int         col;               /**< color currently assigned */
 117         int         init_col;          /**< the initial color */
 118         int         tmp_col;           /**< a temporary assigned color */
 119         unsigned    fixed     : 1;     /**< the color is fixed */
 120         unsigned    tmp_fixed : 1;     /**< the color is temporary fixed */
 121 } co_mst_irn_t;
 122
 123 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
 124
 125 typedef int decide_func_t(const co_mst_irn_t *node, int col);
 126
 127 #ifdef DEBUG_libfirm
 128
 129 /**
 130  * Write a chunk to stderr for debugging.
 131  */
 132 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
 133         int idx;
 134         if (c->weight_consistent)
 135                 ir_fprintf(stderr, " $%d ", c->weight);
 136         ir_fprintf(stderr, "{");
 137         bitset_foreach(c->nodes, idx) {
 138                 ir_node *n = get_idx_irn(env->co->irg, idx);
 139                 ir_fprintf(stderr, " %+F,", n);
 140         }
 141         ir_fprintf(stderr, "}");
 142 }
 143
 144 /**
 145  * Dump all admissible colors to stderr.
 146  */
 147 static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
 148         int idx;
 149         if (bitset_popcnt(node->adm_colors) < 1)
 150                 fprintf(stderr, "no admissible colors?!?");
 151         else {
 152                 bitset_foreach(node->adm_colors, idx)
 153                         fprintf(stderr, " %d", idx);
 154         }
 155 }
 156
 157 /**
 158  * Dump color-cost pairs to stderr.
 159  */
 160 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
 161         int i;
 162         for (i = 0; i < env->n_regs; ++i) {
 163                 if (cost[i].cost == COL_COST_INFEASIBLE)
 164                         fprintf(stderr, " (%d, INF)", cost[i].col);
 165                 else
 166                         fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
 167         }
 168 }
 169
 170 #endif /* DEBUG_libfirm */
 171
 172 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
 173         return node->tmp_fixed ? node->tmp_col : node->col;
 174 }
 175
 176 /**
 177  * @return 1 if node @p node has color @p col, 0 otherwise.
 178  */
 179 static int decider_has_color(const co_mst_irn_t *node, int col) {
 180         return get_mst_irn_col(node) == col;
 181 }
 182
 183 /**
 184  * @return 1 if node @p node has not color @p col, 0 otherwise.
 185  */
 186 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
 187         return get_mst_irn_col(node) != col;
 188 }
 189
 190 /**
 191  * Always returns true.
 192  */
 193 static int decider_always_yes(const co_mst_irn_t *node, int col) {
 194         return 1;
 195 }
 196
 197 /** compares two affinity edges by its weight */
 198 static int cmp_aff_edge(const void *a, const void *b) {
 199         const aff_edge_t *e1 = a;
 200         const aff_edge_t *e2 = b;
 201
 202         if (e2->weight == e1->weight) {
 203                 if (e2->src->node_idx == e1->src->node_idx)
 204                         return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
 205                 else
 206                         return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
 207         }
 208         /* sort in descending order */
 209         return QSORT_CMP(e2->weight, e1->weight);
 210 }
 211
 212 /** compares to color-cost pairs */
 213 static int cmp_col_cost(const void *a, const void *b) {
 214         const col_cost_t *c1 = a;
 215         const col_cost_t *c2 = b;
 216
 217         return c1->cost < c2->cost ? -1 : 1;
 218 }
 219
 220 /**
 221  * Creates a new affinity chunk
 222  */
 223 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
 224         aff_chunk_t *c = xmalloc(sizeof(*c));
 225         c->weight            = -1;
 226         c->weight_consistent = 0;
 227         c->n = NEW_ARR_F(ir_node *, 0);
 228         c->nodes             = bitset_irg_malloc(env->co->irg);
 229         c->interfere         = bitset_irg_malloc(env->co->irg);
 230         c->id                = last_chunk_id++;
 231         pset_insert(env->chunkset, c, c->id);
 232         return c;
 233 }
 234
 235 /**
 236  * Frees all memory allocated by an affinity chunk.
 237  */
 238 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 239         pset_remove(env->chunkset, c, c->id);
 240         bitset_free(c->nodes);
 241         bitset_free(c->interfere);
 242         DEL_ARR_F(c->n);
 243         c->deleted = 1;
 244         free(c);
 245 }
 246
 247 /**
 248  * Adds a node to an affinity chunk
 249  */
 250 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
 251         int i;
 252
 253         if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
 254                 return;
 255
 256         c->weight_consistent = 0;
 257         node->chunk          = c;
 258         bitset_set(c->nodes, get_irn_idx(node->irn));
 259
 260         ARR_APP1(ir_node *, c->n, node->irn);
 261
 262         for (i = node->n_neighs - 1; i >= 0; --i) {
 263                 ir_node *neigh = node->int_neighs[i];
 264                 bitset_set(c->interfere, get_irn_idx(neigh));
 265         }
 266 }
 267
 268 /**
 269  * In case there is no phase information for irn, initialize it.
 270  */
 271 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
 272         co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
 273         co_mst_env_t *env = ph->priv;
 274
 275         if (res != old) {
 276                 const arch_register_req_t *req;
 277                 void     *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
 278                 ir_node  *neigh;
 279                 unsigned len;
 280
 281                 res->irn           = irn;
 282                 res->chunk         = NULL;
 283                 res->fixed         = 0;
 284                 res->tmp_fixed     = 0;
 285                 res->tmp_col       = -1;
 286                 res->int_neighs    = NULL;
 287                 res->int_aff_neigh = 0;
 288                 res->col           = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
 289                 res->init_col      = res->col;
 290
 291                 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
 292
 293                 /* set admissible registers */
 294                 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
 295
 296                 /* Exclude colors not assignable to the irn */
 297                 req = arch_get_register_req(env->aenv, irn, -1);
 298                 if (arch_register_req_is(req, limited))
 299                         rbitset_copy_to_bitset(req->limited, res->adm_colors);
 300                 else
 301                         bitset_set_all(res->adm_colors);
 302
 303                 /* exclude global ignore registers as well */
 304                 bitset_andnot(res->adm_colors, env->ignore_regs);
 305
 306                 /* set the number of interfering affinity neighbours to -1, they are calculated later */
 307                 res->int_aff_neigh = -1;
 308
 309                 /* build list of interfering neighbours */
 310                 len = 0;
 311                 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
 312                         if (! arch_irn_is(env->aenv, neigh, ignore)) {
 313                                 obstack_ptr_grow(phase_obst(ph), neigh);
 314                                 ++len;
 315                         }
 316                 }
 317                 res->int_neighs = obstack_finish(phase_obst(ph));
 318                 res->n_neighs   = len;
 319         }
 320         return res;
 321 }
 322
 323 /**
 324  * Check if affinity chunk @p chunk interferes with node @p irn.
 325  */
 326 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
 327 #if 1
 328         if (bitset_is_set(chunk->interfere, get_irn_idx(irn)))
 329                 return 1;
 330 #else
 331         const co_mst_irn_t *node = get_co_mst_irn(env, irn);
 332         const ir_node      *neigh;
 333         int          i;
 334
 335         for (i = 0; i < node->n_neighs; ++i) {
 336                 neigh = node->int_neighs[i];
 337                 if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
 338                         return 1;
 339         }
 340 #endif
 341         return 0;
 342 }
 343
 344 /**
 345  * Check if there are interference edges from c1 to c2.
 346  * @param env   The global co_mst environment
 347  * @param c1    A chunk
 348  * @param c2    Another chunk
 349  * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
 350  */
 351 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
 352         int idx;
 353         bitset_t *tmp;
 354
 355         if (c1 == c2)
 356                 return 0;
 357 #if 1
 358         tmp = bitset_alloca(get_irg_last_idx(env->co->irg));
 359         tmp = bitset_copy(tmp, c1->interfere);
 360         tmp = bitset_and(tmp, c2->nodes);
 361         if (bitset_popcnt(tmp) > 0)
 362                 return 1;
 363 #else
 364         /* check if there is a node in c2 having an interfering neighbor in c1 */
 365         bitset_foreach(c2->nodes, idx) {
 366                 ir_node *n = get_idx_irn(env->co->irg, idx);
 367
 368                 if (aff_chunk_interferes(env, c1, n))
 369                         return 1;
 370         }
 371 #endif
 372         return 0;
 373 }
 374
 375 /**
 376  * Returns the affinity chunk of @p irn or creates a new
 377  * one with @p irn as element if there is none assigned.
 378  */
 379 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
 380         co_mst_irn_t *node = get_co_mst_irn(env, irn);
 381         return node->chunk;
 382 }
 383
 384 /**
 385  * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
 386  * are no interference edges from chunk(src) to chunk(tgt)).
 387  * @return 1 if successful, 0 if not possible
 388  */
 389 static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
 390         aff_chunk_t *c1 = get_aff_chunk(env, src);
 391         aff_chunk_t *c2 = get_aff_chunk(env, tgt);
 392
 393         DEBUG_ONLY(
 394                 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
 395                 if (c1) {
 396                         DBG_AFF_CHUNK(env, LEVEL_4, c1);
 397                 } else {
 398                         DB((dbg, LEVEL_4, "{%+F}", src));
 399                 }
 400                 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
 401                 if (c2) {
 402                         DBG_AFF_CHUNK(env, LEVEL_4, c2);
 403                 } else {
 404                         DB((dbg, LEVEL_4, "{%+F}", tgt));
 405                 }
 406                 DB((dbg, LEVEL_4, "\n"));
 407         )
 408
 409         if (c1 == NULL) {
 410                 if (c2 == NULL) {
 411                         /* no chunk exists */
 412                         co_mst_irn_t *mirn = get_co_mst_irn(env, src);
 413                         int i;
 414
 415                         for (i = mirn->n_neighs - 1; i >= 0; --i) {
 416                                 if (mirn->int_neighs[i] == tgt)
 417                                         break;
 418                         }
 419                         if (i < 0) {
 420                                 /* create one containing both nodes */
 421                                 c1 = new_aff_chunk(env);
 422                                 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
 423                                 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
 424                                 goto absorbed;
 425                         }
 426                 } else {
 427                         /* c2 already exists */
 428                         if (! aff_chunk_interferes(env, c2, src)) {
 429                                 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
 430                                 goto absorbed;
 431                         }
 432                 }
 433         } else if (c2 == NULL) {
 434                 /* c1 already exists */
 435                 if (! aff_chunk_interferes(env, c1, tgt)) {
 436                         aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
 437                         goto absorbed;
 438                 }
 439         } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
 440                 int idx;
 441
 442                 bitset_or(c1->nodes, c2->nodes);
 443                 bitset_or(c1->interfere, c2->interfere);
 444                 c1->weight_consistent = 0;
 445
 446 //              bitset_foreach(c2->nodes, idx) {
 447                 for (idx = 0; idx < ARR_LEN(c2->n); ++idx) {
 448                         int i;
 449 //                      ir_node      *n  = get_idx_irn(env->co->irg, idx);
 450                         ir_node      *n  = c2->n[idx];
 451                         co_mst_irn_t *mn = get_co_mst_irn(env, n);
 452                         mn->chunk = c1;
 453
 454                         for (i = 0; i < ARR_LEN(c1->n); ++i) {
 455                                 if (c1->n[i] == n)
 456                                         break;
 457                         }
 458                         if (i >= ARR_LEN(c1->n))
 459                                 ARR_APP1(ir_node *, c1->n, n);
 460                 }
 461
 462                 delete_aff_chunk(env, c2);
 463                 goto absorbed;
 464         }
 465         DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
 466         return 0;
 467
 468 absorbed:
 469         DB((dbg, LEVEL_4, " ... absorbed\n"));
 470         return 1;
 471 }
 472
 473 /**
 474  * Assures that the weight of the given chunk is consistent.
 475  */
 476 static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) {
 477         if (! c->weight_consistent) {
 478                 int w = 0;
 479                 int idx;
 480
 481 //              bitset_foreach(c->nodes, idx) {
 482 //                      ir_node               *n  = get_idx_irn(env->co->irg, idx);
 483                 for (idx = 0; idx < ARR_LEN(c->n); ++idx) {
 484                         ir_node *n = c->n[idx];
 485                         const affinity_node_t *an = get_affinity_info(env->co, n);
 486
 487                         if (an != NULL) {
 488                                 neighb_t *neigh;
 489                                 co_gs_foreach_neighb(an, neigh) {
 490                                         const ir_node      *m    = neigh->irn;
 491                                         const int          m_idx = get_irn_idx(m);
 492
 493                                         /* skip ignore nodes */
 494                                         if (arch_irn_is(env->aenv, m, ignore))
 495                                                 continue;
 496
 497                                         w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
 498                                 }
 499                         }
 500                 }
 501
 502                 c->weight            = w;
 503                 c->weight_consistent = 1;
 504         }
 505 }
 506
 507 /**
 508  * Count the number of interfering affinity neighbours
 509  */
 510 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
 511         const neighb_t     *neigh;
 512         ir_node            *irn  = an->irn;
 513         const co_mst_irn_t *node = get_co_mst_irn(env, irn);
 514         int                res   = 0;
 515
 516         co_gs_foreach_neighb(an, neigh) {
 517                 const ir_node *n = neigh->irn;
 518                 int           i;
 519
 520                 /* skip ignore nodes */
 521                 if (arch_irn_is(env->aenv, n, ignore))
 522                         continue;
 523
 524                 /* check if the affinity neighbour interfere */
 525                 for (i = 0; i < node->n_neighs; ++i) {
 526                         if (node->int_neighs[i] == n) {
 527                                 ++res;
 528                                 break;
 529                         }
 530                 }
 531         }
 532         return res;
 533 }
 534
 535
 536 /**
 537  * Build chunks of nodes connected by affinity edges.
 538  * We start at the heaviest affinity edge.
 539  * The chunks of the two edge-defining nodes will be
 540  * merged if there are no interference edges from one
 541  * chunk to the other.
 542  */
 543 static void build_affinity_chunks(co_mst_env_t *env) {
 544         void        *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
 545         aff_edge_t  *edges    = NEW_ARR_F(aff_edge_t, 0);
 546         ir_node     *n;
 547         int         i, len;
 548         aff_chunk_t *curr_chunk;
 549         pset_new_iterator_t iter;
 550
 551         /* at first we create the affinity edge objects */
 552         be_ifg_foreach_node(env->ifg, nodes_it, n) {
 553                 int             n_idx = get_irn_idx(n);
 554                 co_mst_irn_t    *n1;
 555                 affinity_node_t *an;
 556
 557                 /* skip ignore nodes */
 558                 if (arch_irn_is(env->aenv, n, ignore))
 559                         continue;
 560
 561                 n1 = get_co_mst_irn(env, n);
 562                 an = get_affinity_info(env->co, n);
 563
 564                 if (an != NULL) {
 565                         neighb_t *neigh;
 566
 567                         if (n1->int_aff_neigh < 0)
 568                                 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
 569                         co_gs_foreach_neighb(an, neigh) {
 570                                 ir_node *m    = neigh->irn;
 571                                 int     m_idx = get_irn_idx(m);
 572
 573                                 /* record the edge in only one direction */
 574                                 if (n_idx < m_idx) {
 575                                         co_mst_irn_t *n2;
 576                                         aff_edge_t   edge;
 577
 578                                         /* skip ignore nodes */
 579                                         if (arch_irn_is(env->aenv, m, ignore))
 580                                                 continue;
 581
 582                                         edge.src = n;
 583                                         edge.tgt = m;
 584
 585                                         n2 = get_co_mst_irn(env, m);
 586                                         if (n2->int_aff_neigh < 0) {
 587                                                 affinity_node_t *am = get_affinity_info(env->co, m);
 588                                                 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
 589                                         }
 590                                         edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
 591                                         ARR_APP1(aff_edge_t, edges, edge);
 592                                 }
 593                         }
 594                 }
 595         }
 596
 597         /* now: sort edges and build the affinity chunks */
 598         len = ARR_LEN(edges);
 599         qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
 600         for (i = 0; i < len; ++i) {
 601                 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
 602
 603                 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
 604         }
 605
 606         /* now insert all chunks into a priority queue */
 607         foreach_pset(env->chunkset, curr_chunk) {
 608                 aff_chunk_assure_weight(env, curr_chunk);
 609
 610                 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
 611                 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
 612                 DBG((dbg, LEVEL_1, "\n"));
 613
 614                 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
 615         }
 616         foreach_phase_irn(&env->ph, n) {
 617                 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
 618
 619                 if (mirn->chunk == NULL) {
 620                         /* no chunk is allocated so far, do it now */
 621                         aff_chunk_t *curr_chunk = new_aff_chunk(env);
 622                         aff_chunk_add_node(curr_chunk, mirn);
 623
 624                         aff_chunk_assure_weight(env, curr_chunk);
 625
 626                         DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
 627                         DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
 628                         DBG((dbg, LEVEL_1, "\n"));
 629
 630                         pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
 631                 }
 632         }
 633
 634         DEL_ARR_F(edges);
 635 }
 636
 637 /**
 638  * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
 639  */
 640 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
 641         aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
 642 {
 643         waitq *nodes = new_waitq();
 644
 645         DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col));
 646
 647         /* init queue and chunk */
 648         waitq_put(nodes, node);
 649         bitset_set(visited, get_irn_idx(node->irn));
 650         aff_chunk_add_node(chunk, node);
 651         DB((dbg, LEVEL_1, " %+F", node->irn));
 652
 653         /* as long as there are nodes in the queue */
 654         while (! waitq_empty(nodes)) {
 655                 co_mst_irn_t    *n  = waitq_get(nodes);
 656                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 657
 658                 /* check all affinity neighbors */
 659                 if (an != NULL) {
 660                         neighb_t *neigh;
 661                         co_gs_foreach_neighb(an, neigh) {
 662                                 ir_node      *m    = neigh->irn;
 663                                 int          m_idx = get_irn_idx(m);
 664                                 co_mst_irn_t *n2;
 665
 666                                 /* skip ignore nodes */
 667                                 if (arch_irn_is(env->aenv, m, ignore))
 668                                         continue;
 669
 670                                 n2 = get_co_mst_irn(env, m);
 671
 672                                 if (! bitset_is_set(visited, m_idx)       &&
 673                                         decider(n2, col)                      &&
 674                                         ! n2->fixed                           &&
 675                                         ! aff_chunk_interferes(env, chunk, m) &&
 676                                         bitset_is_set(orig_chunk->nodes, m_idx))
 677                                 {
 678                                         /*
 679                                                 following conditions are met:
 680                                                 - neighbour is not visited
 681                                                 - neighbour likes the color
 682                                                 - neighbour has not yet a fixed color
 683                                                 - the new chunk doesn't interfere with the neighbour
 684                                                 - neighbour belongs or belonged once to the original chunk
 685                                         */
 686                                         bitset_set(visited, m_idx);
 687                                         aff_chunk_add_node(chunk, n2);
 688                                         DB((dbg, LEVEL_1, " %+F", n2->irn));
 689                                         /* enqueue for further search */
 690                                         waitq_put(nodes, n2);
 691                                 }
 692                         }
 693                 }
 694         }
 695
 696         DB((dbg, LEVEL_1, "\n"));
 697
 698         del_waitq(nodes);
 699 }
 700
 701 /**
 702  * Fragment the given chunk into chunks having given color and not having given color.
 703  */
 704 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
 705         bitset_t    *visited = bitset_irg_malloc(env->co->irg);
 706         int         idx;
 707         aff_chunk_t *best = NULL;
 708
 709 //      bitset_foreach(c->nodes, idx) {
 710         for (idx = 0; idx < ARR_LEN(c->n); ++idx) {
 711                 ir_node       *irn;
 712                 co_mst_irn_t  *node;
 713                 aff_chunk_t   *tmp_chunk;
 714                 decide_func_t *decider;
 715                 int           check_for_best;
 716
 717                 irn  = c->n[idx];
 718                 if (bitset_is_set(visited, get_irn_idx(irn)))
 719                         continue;
 720
 721 //              irn  = get_idx_irn(env->co->irg, idx);
 722                 node = get_co_mst_irn(env, irn);
 723
 724                 if (get_mst_irn_col(node) == col) {
 725                         decider        = decider_has_color;
 726                         check_for_best = 1;
 727                         DBG((dbg, LEVEL_4, "\tcolor %d wanted", col));
 728                 }
 729                 else {
 730                         decider        = decider_hasnot_color;
 731                         check_for_best = 0;
 732                         DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col));
 733                 }
 734
 735                 /* create a new chunk starting at current node */
 736                 tmp_chunk = new_aff_chunk(env);
 737                 waitq_put(tmp, tmp_chunk);
 738                 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
 739                 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
 740
 741                 /* remember the local best */
 742                 aff_chunk_assure_weight(env, tmp_chunk);
 743                 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
 744                         best = tmp_chunk;
 745         }
 746
 747         assert(best && "No chunk found?");
 748         bitset_free(visited);
 749         return best;
 750 }
 751
 752 /**
 753  * Initializes an array of color-cost pairs.
 754  * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
 755  */
 756 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
 757         int i;
 758
 759         for (i = 0; i < env->n_regs; ++i) {
 760                 cost[i].col = i;
 761                 if (bitset_is_set(env->ignore_regs, i))
 762                         cost[i].cost = COL_COST_INFEASIBLE;
 763                 else
 764                         cost[i].cost = c;
 765         }
 766 }
 767
 768 /**
 769  * Initializes an array of color-cost pairs.
 770  * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
 771  */
 772 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
 773         assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
 774         col_cost_init(env, cost, COL_COST_INFEASIBLE);
 775         cost[col].col = 0;
 776         cost[0].col   = col;
 777         cost[0].cost  = 0.0;
 778 }
 779
 780 /**
 781  * Resets the temporary fixed color of all nodes within wait queue @p nodes.
 782  * ATTENTION: the queue is empty after calling this function!
 783  */
 784 static INLINE void reject_coloring(waitq *nodes) {
 785         DB((dbg, LEVEL_4, "\treject coloring for"));
 786         while (! waitq_empty(nodes)) {
 787                 co_mst_irn_t *n = waitq_get(nodes);
 788                 DB((dbg, LEVEL_4, " %+F", n->irn));
 789                 n->tmp_fixed = 0;
 790         }
 791         DB((dbg, LEVEL_4, "\n"));
 792 }
 793
 794 /**
 795  * Determines the costs for each color if it would be assigned to node @p node.
 796  */
 797 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
 798         affinity_node_t *an = get_affinity_info(env->co, node->irn);
 799         neighb_t        *aff_neigh;
 800         int             idx, i;
 801
 802         col_cost_init(env, costs, 0.0);
 803
 804         /* calculate (negative) costs for affinity neighbours */
 805         if (an != NULL) {
 806                 co_gs_foreach_neighb(an, aff_neigh) {
 807                         ir_node      *m = aff_neigh->irn;
 808                         co_mst_irn_t *neigh;
 809                         double       c;
 810
 811                         /* skip ignore nodes */
 812                         if (arch_irn_is(env->aenv, m, ignore))
 813                                 continue;
 814
 815                         neigh = get_co_mst_irn(env, m);
 816                         c     = (double)aff_neigh->costs;
 817
 818                         /* calculate costs for fixed affinity neighbours */
 819                         if (neigh->tmp_fixed || neigh->fixed) {
 820                                 int col = get_mst_irn_col(neigh);
 821                                 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
 822                         }
 823                 }
 824         }
 825
 826         /* calculate (positive) costs for interfering neighbours */
 827         for (i = 0; i < node->n_neighs; ++i) {
 828                 co_mst_irn_t *neigh;
 829                 int          col, col_cnt;
 830                 ir_node      *int_neigh;
 831
 832                 int_neigh = node->int_neighs[i];
 833
 834                 /* skip ignore nodes */
 835                 if (arch_irn_is(env->aenv, int_neigh, ignore))
 836                         continue;
 837
 838                 neigh   = get_co_mst_irn(env, int_neigh);
 839                 col     = get_mst_irn_col(neigh);
 840                 col_cnt = bitset_popcnt(neigh->adm_colors);
 841
 842                 if (neigh->tmp_fixed || neigh->fixed) {
 843                         /* colors of fixed interfering neighbours are infeasible */
 844                         costs[col].cost = COL_COST_INFEASIBLE;
 845                 }
 846                 else if (col_cnt < env->k) {
 847                         /* calculate costs for constrained interfering neighbours */
 848                         double ratio = 1.0 - ((double)col_cnt / (double)env->k);
 849
 850                         bitset_foreach_clear(neigh->adm_colors, idx) {
 851                                 /* check only explicitly forbidden colors (skip global forbidden ones) */
 852                                 if (! bitset_is_set(env->ignore_regs, idx)) {
 853                                         costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
 854                                 }
 855                         }
 856                 }
 857         }
 858
 859         /* set all not admissible colors to COL_COST_INFEASIBLE */
 860         bitset_foreach_clear(node->adm_colors, idx)
 861                 costs[idx].cost = COL_COST_INFEASIBLE;
 862 }
 863
 864 /* need forward declaration due to recursive call */
 865 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
 866
 867 /**
 868  * Tries to change node to a color but @p explude_col.
 869  * @return 1 if succeeded, 0 otherwise.
 870  */
 871 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
 872         int col = get_mst_irn_col(node);
 873         int res = 0;
 874
 875         /* neighbours has already a different color -> good, temporary fix it */
 876         if (col != exclude_col) {
 877                 node->tmp_fixed = 1;
 878                 node->tmp_col   = col;
 879                 waitq_put(changed_ones, node);
 880                 return 1;
 881         }
 882
 883         /* The node has the color it should not have _and_ has not been visited yet. */
 884         if (! (node->tmp_fixed || node->fixed)) {
 885                 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
 886
 887                 /* Get the costs for giving the node a specific color. */
 888                 determine_color_costs(env, node, costs);
 889
 890                 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
 891                 costs[exclude_col].cost = COL_COST_INFEASIBLE;
 892
 893                 /* sort the colors according costs, cheapest first. */
 894                 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
 895
 896                 /* Try recoloring the node using the color list. */
 897                 res = recolor_nodes(env, node, costs, changed_ones);
 898         }
 899
 900         return res;
 901 }
 902
 903 /**
 904  * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
 905  * ATTENTION: Expect @p costs already sorted by increasing costs.
 906  * @return 1 if coloring could be applied, 0 otherwise.
 907  */
 908 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
 909         int   i;
 910         waitq *local_changed = new_waitq();
 911         waitq *tmp           = new_waitq();
 912
 913         DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
 914         DBG_COL_COST(env, LEVEL_1, costs);
 915         DB((dbg, LEVEL_1, "\n"));
 916
 917         for (i = 0; i < env->n_regs; ++i) {
 918                 int tgt_col  = costs[i].col;
 919                 int neigh_ok = 1;
 920                 int j;
 921
 922                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 923                 if (costs[i].cost == COL_COST_INFEASIBLE) {
 924                         node->tmp_fixed = 0;
 925                         del_waitq(local_changed);
 926                         del_waitq(tmp);
 927                         return 0;
 928                 }
 929
 930                 /* Set the new color of the node and mark the node as temporarily fixed. */
 931                 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
 932                 node->tmp_fixed = 1;
 933                 node->tmp_col   = tgt_col;
 934                 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
 935
 936                 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
 937                 waitq_put(local_changed, node);
 938
 939                 /* try to color all interfering neighbours with current color forbidden */
 940                 for (j = 0; j < node->n_neighs; ++j) {
 941                         co_mst_irn_t *nn;
 942                         ir_node      *neigh;
 943
 944                         neigh = node->int_neighs[j];
 945
 946                         /* skip ignore nodes */
 947                         if (arch_irn_is(env->aenv, neigh, ignore))
 948                                 continue;
 949
 950                         nn = get_co_mst_irn(env, neigh);
 951                         DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_fixed: %d, tmp_col: %d, col: %d)\n",
 952                                 neigh, j, nn->fixed, nn->tmp_fixed, nn->tmp_col, nn->col));
 953
 954                         /*
 955                                 Try to change the color of the neighbor and record all nodes which
 956                                 get changed in the tmp list. Add this list to the "changed" list for
 957                                 that color. If we did not succeed to change the color of the neighbor,
 958                                 we bail out and try the next color.
 959                         */
 960                         if (get_mst_irn_col(nn) == tgt_col) {
 961                                 /* try to color neighbour with tgt_col forbidden */
 962                                 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
 963
 964                                 /* join lists of changed nodes */
 965                                 while (! waitq_empty(tmp))
 966                                         waitq_put(local_changed, waitq_get(tmp));
 967
 968                                 if (! neigh_ok)
 969                                         break;
 970                         }
 971                 }
 972
 973                 /*
 974                         We managed to assign the target color to all neighbors, so from the perspective
 975                         of the current node, every thing was ok and we can return safely.
 976                 */
 977                 if (neigh_ok) {
 978                         /* append the local_changed ones to global ones */
 979                         while (! waitq_empty(local_changed))
 980                                 waitq_put(changed_ones, waitq_get(local_changed));
 981                         del_waitq(local_changed);
 982                         del_waitq(tmp);
 983                         return 1;
 984                 }
 985                 else {
 986                         /* coloring of neighbours failed, so we try next color */
 987                         reject_coloring(local_changed);
 988                 }
 989         }
 990
 991         del_waitq(local_changed);
 992         del_waitq(tmp);
 993         return 0;
 994 }
 995
 996 /**
 997  * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
 998  * @return 1 if color @p col could be applied, 0 otherwise
 999  */
1000 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
1001         int col = get_mst_irn_col(node);
1002
1003         /* if node already has the target color -> good, temporary fix it */
1004         if (col == tgt_col) {
1005                 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1006                 if (! node->tmp_fixed) {
1007                         node->tmp_fixed = 1;
1008                         node->tmp_col   = tgt_col;
1009                         waitq_put(changed_ones, node);
1010                 }
1011                 return 1;
1012         }
1013
1014         /*
1015                 Node has not yet a fixed color and target color is admissible
1016                 -> try to recolor node and it's affinity neighbours
1017         */
1018         if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
1019                 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
1020                 int        res;
1021
1022                 col_cost_init_single(env, costs, tgt_col);
1023
1024                 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1025                 res = recolor_nodes(env, node, costs, changed_ones);
1026                 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1027
1028                 return res;
1029         }
1030
1031         DEBUG_ONLY(
1032                 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1033                         if (node->fixed || node->tmp_fixed)
1034                                 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1035                         else {
1036                                 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1037                                 dbg_admissible_colors(env, node);
1038                                 DB((dbg, LEVEL_4, ")\n"));
1039                         }
1040                 }
1041         )
1042
1043         return 0;
1044 }
1045
1046 /**
1047  * Tries to color an affinity chunk (or at least a part of it).
1048  * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1049  */
1050 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1051         aff_chunk_t *best_chunk   = NULL;
1052         int         best_color    = -1;
1053         int         best_node     = -1;
1054         waitq       *changed_ones = new_waitq();
1055         waitq       *tmp_chunks   = new_waitq();
1056         waitq       *best_starts  = NULL;
1057         bitset_t    *visited;
1058         int         col, idx;
1059
1060         DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1061         DBG_AFF_CHUNK(env, LEVEL_2, c);
1062         DB((dbg, LEVEL_2, "\n"));
1063
1064
1065         /* check which color is the "best" for the given chunk */
1066         for (col = 0; col < env->n_regs; ++col) {
1067                 int         one_good     = 0;
1068                 waitq       *good_starts = new_waitq();
1069                 aff_chunk_t *local_best;
1070
1071                 /* skip ignore colors */
1072                 if (bitset_is_set(env->ignore_regs, col))
1073                         continue;
1074
1075                 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
1076
1077                 /* try to bring all nodes of given chunk to the current color. */
1078 //              bitset_foreach(c->nodes, idx) {
1079 //                      ir_node      *irn  = get_idx_irn(env->co->irg, idx);
1080                 for (idx = 0; idx < ARR_LEN(c->n); ++idx) {
1081                         ir_node      *irn  = c->n[idx];
1082                         co_mst_irn_t *node = get_co_mst_irn(env, irn);
1083                         int          good  = 0;
1084
1085                         assert(! node->fixed && "Node must not have a fixed color.");
1086                         DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1087
1088                         good = change_node_color(env, node, col, changed_ones);
1089                         if (good)
1090                                 waitq_put(good_starts, node);
1091                         one_good |= good;
1092
1093                         DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
1094                 }
1095
1096                 /* try next color when failed */
1097                 if (! one_good)
1098                         continue;
1099
1100                 /* fragment the chunk according to the coloring */
1101                 local_best = fragment_chunk(env, col, c, tmp_chunks);
1102
1103                 /* search the best of the good list
1104                    and make it the new best if it is better than the current */
1105                 if (local_best) {
1106                         aff_chunk_assure_weight(env, local_best);
1107
1108                         DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1109                         DBG_AFF_CHUNK(env, LEVEL_4, local_best);
1110
1111                         if (! best_chunk || best_chunk->weight < local_best->weight) {
1112                                 best_chunk = local_best;
1113                                 best_color = col;
1114                                 if (best_starts)
1115                                         del_waitq(best_starts);
1116                                 best_starts = good_starts;
1117                                 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1118                         } else {
1119                                 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1120                                 del_waitq(good_starts);
1121                         }
1122                 }
1123
1124                 /* reject the coloring and bring the coloring to the initial state */
1125                 reject_coloring(changed_ones);
1126         }
1127
1128         /* free all intermediate created chunks except best one */
1129         while (! waitq_empty(tmp_chunks)) {
1130                 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1131                 if (tmp != best_chunk)
1132                         delete_aff_chunk(env, tmp);
1133         }
1134         del_waitq(tmp_chunks);
1135
1136         /* return if coloring failed */
1137         if (! best_chunk) {
1138                 del_waitq(changed_ones);
1139                 return;
1140         }
1141
1142         DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1143         DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1144         DB((dbg, LEVEL_2, "using color %d\n", best_color));
1145
1146         /* get the best fragment from the best list and color it */
1147 //      bitset_foreach(best_chunk->nodes, idx) {
1148 //              ir_node      *irn  = get_idx_irn(env->co->irg, idx);
1149         while (! waitq_empty(best_starts)) {
1150                 co_mst_irn_t *node = waitq_get(best_starts);
1151                 int          res;
1152
1153                 if (! bitset_is_set(best_chunk->nodes, get_irn_idx(node->irn)))
1154                         continue;
1155
1156                 res = change_node_color(env, node, best_color, changed_ones);
1157                 if (! res)
1158                         panic("Color manifesting failed for %+F, color %d in chunk %d\n", node->irn, best_color, best_chunk->id);
1159                 node->fixed = 1;
1160                 node->chunk = best_chunk;
1161         }
1162         for (idx = 0; idx < ARR_LEN(best_chunk->n); ++idx) {
1163                 ir_node *irn = best_chunk->n[idx];
1164                 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1165                 int          res;
1166
1167                 res = change_node_color(env, node, best_color, changed_ones);
1168                 if (! res)
1169                         panic("Color manifesting failed for %+F, color %d in chunk %d\n", irn, best_color, best_chunk->id);
1170                 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, irn, best_chunk->id));
1171                 node->fixed = 1;
1172                 node->chunk = best_chunk;
1173         }
1174
1175         /* materialize colors on changed nodes */
1176         while (! waitq_empty(changed_ones)) {
1177                 co_mst_irn_t *n = waitq_get(changed_ones);
1178                 n->tmp_fixed = 0;
1179                 n->col       = n->tmp_col;
1180         }
1181
1182         /* remove the nodes in best chunk from original chunk */
1183         bitset_andnot(c->nodes, best_chunk->nodes);
1184         {
1185         ir_node **tmp = NEW_ARR_F(ir_node *, 0);
1186         for (idx = 0; idx < ARR_LEN(c->n); ++idx) {
1187                 ir_node *irn = c->n[idx];
1188                 int j;
1189
1190                 for (j = 0; j < ARR_LEN(best_chunk->n); ++j) {
1191                         if (best_chunk->n[j] == irn)
1192                                 break;
1193                 }
1194                 if (j >= ARR_LEN(best_chunk->n))
1195                         ARR_APP1(ir_node *, tmp, irn);
1196         }
1197         DEL_ARR_F(c->n);
1198         c->n = tmp;
1199         }
1200
1201         /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1202 //      bitset_foreach(c->nodes, idx) {
1203 //              ir_node      *n  = get_idx_irn(env->co->irg, idx);
1204         for (idx = 0; idx < ARR_LEN(c->n); ++idx) {
1205                 ir_node *n = c->n[idx];
1206                 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1207                 nn->chunk = c;
1208         }
1209
1210         /* fragment the remaining chunk */
1211         visited = bitset_irg_malloc(env->co->irg);
1212         bitset_or(visited, best_chunk->nodes);
1213 //      bitset_foreach(c->nodes, idx) {
1214         for (idx = 0; idx < ARR_LEN(c->n); ++idx) {
1215                 ir_node *irn = c->n[idx];
1216                 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1217                         aff_chunk_t  *new_chunk = new_aff_chunk(env);
1218 //                      ir_node      *irn       = get_idx_irn(env->co->irg, idx);
1219                         co_mst_irn_t *node      = get_co_mst_irn(env, irn);
1220
1221                         expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1222                         aff_chunk_assure_weight(env, new_chunk);
1223                         pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1224                 }
1225         }
1226
1227         /* clear obsolete chunks and free some memory */
1228         delete_aff_chunk(env, best_chunk);
1229         bitset_free(visited);
1230         del_waitq(changed_ones);
1231 }
1232
1233 /**
1234  * Main driver for mst safe coalescing algorithm.
1235  */
1236 int co_solve_heuristic_mst(copy_opt_t *co) {
1237         unsigned     n_regs       = co->cls->n_regs;
1238         bitset_t     *ignore_regs = bitset_alloca(n_regs);
1239         unsigned     k;
1240         ir_node      *irn;
1241         co_mst_env_t mst_env;
1242
1243         /* init phase */
1244         phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1245
1246         k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1247         k = n_regs - k;
1248
1249         mst_env.n_regs      = n_regs;
1250         mst_env.k           = k;
1251         mst_env.chunks      = new_pqueue();
1252         mst_env.co          = co;
1253         mst_env.ignore_regs = ignore_regs;
1254         mst_env.ifg         = co->cenv->ifg;
1255         mst_env.aenv        = co->aenv;
1256         mst_env.chunkset    = pset_new_ptr(512);
1257
1258         DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1259
1260         /* build affinity chunks */
1261         build_affinity_chunks(&mst_env);
1262
1263         /* color chunks as long as there are some */
1264         while (! pqueue_empty(mst_env.chunks)) {
1265                 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1266
1267                 color_aff_chunk(&mst_env, chunk);
1268                 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1269                 delete_aff_chunk(&mst_env, chunk);
1270         }
1271
1272         /* apply coloring */
1273         foreach_phase_irn(&mst_env.ph, irn) {
1274                 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1275                 const arch_register_t *reg;
1276
1277                 if (arch_irn_is(mst_env.aenv, irn, ignore))
1278                         continue;
1279
1280                 assert(mirn->fixed && "Node should have fixed color");
1281
1282                 /* skip nodes where color hasn't changed */
1283                 if (mirn->init_col == mirn->col)
1284                         continue;
1285
1286                 reg = arch_register_for_index(co->cls, mirn->col);
1287                 arch_set_irn_register(co->aenv, irn, reg);
1288                 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1289         }
1290
1291         /* free allocated memory */
1292         del_pqueue(mst_env.chunks);
1293         phase_free(&mst_env.ph);
1294         del_pset(mst_env.chunkset);
1295
1296         return 0;
1297 }
1298
1299 void be_init_copyheur4(void) {
1300         FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1301 }
1302
1303 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);