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

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