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