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

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