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

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