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

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