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 double 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         ir_node const *max_node   = NULL;
 741         int            max_weight = 0;
 742         size_t         i;
 743
 744         for (i = ARR_LEN(chunk->n); i != 0;) {
 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); i != 0;)
 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 its 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 its 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         i;
1187         size_t      idx;
1188         size_t      len;
1189         size_t      nidx;
1190         size_t      pos;
1191         struct list_head changed;
1192
1193         DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id));
1194         DBG_AFF_CHUNK(env, LEVEL_2, c);
1195         DB((dbg, LEVEL_2, "\n"));
1196
1197         stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id);
1198
1199         ++env->chunk_visited;
1200
1201         /* compute color preference */
1202         for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) {
1203                 const ir_node *n = c->interfere[pos];
1204                 co_mst_irn_t *node = get_co_mst_irn(env, n);
1205                 aff_chunk_t *chunk = node->chunk;
1206
1207                 if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
1208                         assert(!chunk->deleted);
1209                         chunk->visited = env->chunk_visited;
1210                         ++n_int_chunks;
1211
1212                         aff_chunk_assure_weight(env, chunk);
1213                         for (i = 0; i < env->n_regs; ++i)
1214                                 order[i].cost += chunk->color_affinity[i].cost;
1215                 }
1216         }
1217
1218         for (i = 0; i < env->n_regs; ++i) {
1219                 real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
1220                 order[i].col  = i;
1221                 order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
1222         }
1223
1224         qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
1225
1226         DBG_COL_COST(env, LEVEL_2, order);
1227         DB((dbg, LEVEL_2, "\n"));
1228
1229         /* check which color is the "best" for the given chunk.
1230          * if we found a color which was ok for all nodes, we take it
1231          * and do not look further. (see did_all flag usage below.)
1232          * If we have many colors which fit all nodes it is hard to decide
1233          * which one to take anyway.
1234          * TODO Sebastian: Perhaps we should at all nodes and figure out
1235          * a suitable color using costs as done above (determine_color_costs).
1236          */
1237         for (i = 0; i < env->k; ++i) {
1238                 int         col = order[i].col;
1239                 waitq       *good_starts = new_waitq();
1240                 aff_chunk_t *local_best;
1241                 int          n_succeeded;
1242
1243                 /* skip ignore colors */
1244                 if (!bitset_is_set(env->allocatable_regs, col))
1245                         continue;
1246
1247                 DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
1248
1249                 n_succeeded = 0;
1250
1251                 /* try to bring all nodes of given chunk to the current color. */
1252                 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1253                         const ir_node   *irn  = c->n[idx];
1254                         co_mst_irn_t    *node = get_co_mst_irn(env, irn);
1255                         int              good;
1256
1257                         assert(! node->fixed && "Node must not have a fixed color.");
1258                         DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1259
1260                         /*
1261                                 The order of the colored nodes is important, so we record the successfully
1262                                 colored ones in the order they appeared.
1263                         */
1264                         INIT_LIST_HEAD(&changed);
1265                         stat_ev_tim_push();
1266                         good = change_node_color(env, node, col, &changed);
1267                         stat_ev_tim_pop("heur4_recolor");
1268                         if (good) {
1269                                 waitq_put(good_starts, node);
1270                                 materialize_coloring(&changed);
1271                                 node->fixed = 1;
1272                         }
1273
1274                         else
1275                                 reject_coloring(&changed);
1276
1277                         n_succeeded += good;
1278                         DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
1279                 }
1280
1281                 /* unfix all nodes */
1282                 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1283                         co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]);
1284                         node->fixed = 0;
1285                 }
1286
1287                 /* try next color when failed */
1288                 if (n_succeeded == 0)
1289                         continue;
1290
1291                 /* fragment the chunk according to the coloring */
1292                 local_best = fragment_chunk(env, col, c, tmp_chunks);
1293
1294                 /* search the best of the good list
1295                    and make it the new best if it is better than the current */
1296                 if (local_best) {
1297                         aff_chunk_assure_weight(env, local_best);
1298
1299                         DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col));
1300                         DBG_AFF_CHUNK(env, LEVEL_3, local_best);
1301
1302                         if (! best_chunk || best_chunk->weight < local_best->weight) {
1303                                 best_chunk = local_best;
1304                                 best_color = col;
1305                                 if (best_starts)
1306                                         del_waitq(best_starts);
1307                                 best_starts = good_starts;
1308                                 DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color));
1309                         } else {
1310                                 DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
1311                                 del_waitq(good_starts);
1312                         }
1313                 }
1314                 else {
1315                         del_waitq(good_starts);
1316                 }
1317
1318                 /* if all nodes were recolored, bail out */
1319                 if (n_succeeded == n_nodes)
1320                         break;
1321         }
1322
1323         stat_ev_int("heur4_colors_tried", i);
1324
1325         /* free all intermediate created chunks except best one */
1326         while (! waitq_empty(tmp_chunks)) {
1327                 aff_chunk_t *tmp = (aff_chunk_t*)waitq_get(tmp_chunks);
1328                 if (tmp != best_chunk)
1329                         delete_aff_chunk(tmp);
1330         }
1331         del_waitq(tmp_chunks);
1332
1333         /* return if coloring failed */
1334         if (! best_chunk) {
1335                 if (best_starts)
1336                         del_waitq(best_starts);
1337                 return;
1338         }
1339
1340         DB((dbg, LEVEL_2, "\tbest chunk #%u ", best_chunk->id));
1341         DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1342         DB((dbg, LEVEL_2, "using color %d\n", best_color));
1343
1344         for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1345                 const ir_node *irn  = best_chunk->n[idx];
1346                 co_mst_irn_t  *node = get_co_mst_irn(env, irn);
1347                 int res;
1348
1349                 /* bring the node to the color. */
1350                 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%u\n", best_color, node->irn, best_chunk->id));
1351                 INIT_LIST_HEAD(&changed);
1352                 stat_ev_tim_push();
1353                 res = change_node_color(env, node, best_color, &changed);
1354                 stat_ev_tim_pop("heur4_recolor");
1355                 if (res) {
1356                         materialize_coloring(&changed);
1357                         node->fixed = 1;
1358                 }
1359                 assert(list_empty(&changed));
1360         }
1361
1362         /* remove the nodes in best chunk from original chunk */
1363         len = ARR_LEN(best_chunk->n);
1364         for (idx = 0; idx < len; ++idx) {
1365                 const ir_node *irn = best_chunk->n[idx];
1366                 int pos = nodes_bsearch(c->n, irn);
1367
1368                 if (pos > 0)
1369                         c->n[pos] = NULL;
1370         }
1371         len = ARR_LEN(c->n);
1372         for (idx = nidx = 0; idx < len; ++idx) {
1373                 const ir_node *irn = c->n[idx];
1374
1375                 if (irn != NULL) {
1376                         c->n[nidx++] = irn;
1377                 }
1378         }
1379         ARR_SHRINKLEN(c->n, nidx);
1380
1381
1382         /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1383         for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1384                 const ir_node *n  = c->n[idx];
1385                 co_mst_irn_t  *nn = get_co_mst_irn(env, n);
1386                 nn->chunk = c;
1387         }
1388
1389         /* fragment the remaining chunk */
1390         visited = bitset_irg_malloc(env->co->irg);
1391         for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx)
1392                 bitset_set(visited, get_irn_idx(best_chunk->n[idx]));
1393
1394         for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1395                 const ir_node *irn = c->n[idx];
1396                 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1397                         aff_chunk_t  *new_chunk = new_aff_chunk(env);
1398                         co_mst_irn_t *node      = get_co_mst_irn(env, irn);
1399
1400                         expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1401                         aff_chunk_assure_weight(env, new_chunk);
1402                         pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1403                 }
1404         }
1405
1406         for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1407                 const ir_node *n  = best_chunk->n[idx];
1408                 co_mst_irn_t  *nn = get_co_mst_irn(env, n);
1409                 nn->chunk = NULL;
1410         }
1411
1412         /* clear obsolete chunks and free some memory */
1413         delete_aff_chunk(best_chunk);
1414         bitset_free(visited);
1415         if (best_starts)
1416                 del_waitq(best_starts);
1417
1418         stat_ev_ctx_pop("heur4_color_chunk");
1419 }
1420
1421 /**
1422  * Main driver for mst safe coalescing algorithm.
1423  */
1424 static int co_solve_heuristic_mst(copy_opt_t *co)
1425 {
1426         unsigned     n_regs            = co->cls->n_regs;
1427         bitset_t     *allocatable_regs = bitset_alloca(n_regs);
1428         unsigned     i, j;
1429         size_t       k;
1430         ir_node      *irn;
1431         co_mst_env_t mst_env;
1432
1433         last_chunk_id = 0;
1434
1435         stat_ev_tim_push();
1436
1437         /* init phase */
1438         phase_init(&mst_env.ph, co->irg, co_mst_irn_init);
1439         phase_set_private(&mst_env.ph, &mst_env);
1440
1441         be_put_allocatable_regs(co->cenv->irg, co->cls, allocatable_regs);
1442         k = bitset_popcount(allocatable_regs);
1443
1444         mst_env.n_regs           = n_regs;
1445         mst_env.k                = k;
1446         mst_env.chunks           = new_pqueue();
1447         mst_env.co               = co;
1448         mst_env.allocatable_regs = allocatable_regs;
1449         mst_env.ifg              = co->cenv->ifg;
1450         INIT_LIST_HEAD(&mst_env.chunklist);
1451         mst_env.chunk_visited    = 0;
1452         mst_env.single_cols      = (col_cost_t**)phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs);
1453
1454         for (i = 0; i < n_regs; ++i) {
1455                 col_cost_t *vec = (col_cost_t*)phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs);
1456
1457                 mst_env.single_cols[i] = vec;
1458                 for (j = 0; j < n_regs; ++j) {
1459                         vec[j].col  = j;
1460                         vec[j].cost = REAL(0.0);
1461                 }
1462                 vec[i].col  = 0;
1463                 vec[0].col  = i;
1464                 vec[0].cost = REAL(1.0);
1465         }
1466
1467         DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1468
1469         /* build affinity chunks */
1470         stat_ev_tim_push();
1471         build_affinity_chunks(&mst_env);
1472         stat_ev_tim_pop("heur4_initial_chunk");
1473
1474         /* color chunks as long as there are some */
1475         while (! pqueue_empty(mst_env.chunks)) {
1476                 aff_chunk_t *chunk = (aff_chunk_t*)pqueue_pop_front(mst_env.chunks);
1477
1478                 color_aff_chunk(&mst_env, chunk);
1479                 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id));
1480                 delete_aff_chunk(chunk);
1481         }
1482
1483         /* apply coloring */
1484         foreach_phase_irn(&mst_env.ph, irn) {
1485                 co_mst_irn_t          *mirn;
1486                 const arch_register_t *reg;
1487
1488                 if (arch_irn_is_ignore(irn))
1489                         continue;
1490
1491                 mirn = get_co_mst_irn(&mst_env, irn);
1492                 // assert(mirn->fixed && "Node should have fixed color");
1493
1494                 /* skip nodes where color hasn't changed */
1495                 if (mirn->init_col == mirn->col)
1496                         continue;
1497
1498                 reg = arch_register_for_index(co->cls, mirn->col);
1499                 arch_set_irn_register(irn, reg);
1500                 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1501         }
1502
1503         /* free allocated memory */
1504         del_pqueue(mst_env.chunks);
1505         phase_deinit(&mst_env.ph);
1506
1507         stat_ev_tim_pop("heur4_total");
1508
1509         return 0;
1510 }
1511
1512 static const lc_opt_table_entry_t options[] = {
1513         LC_OPT_ENT_INT      ("limit", "limit recoloring",  &recolor_limit),
1514         LC_OPT_ENT_DBL      ("di",    "dislike influence", &dislike_influence),
1515         LC_OPT_LAST
1516 };
1517
1518 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4)
1519 void be_init_copyheur4(void)
1520 {
1521         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1522         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1523         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1524         lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1525         lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1526
1527         static co_algo_info copyheur = {
1528                 co_solve_heuristic_mst, 0
1529         };
1530
1531         lc_opt_add_table(heur4_grp, options);
1532         be_register_copyopt("heur4", &copyheur);
1533
1534         FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1535 }