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

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