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

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