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

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