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