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

   1 /*
   2  * Copyright (C) 1995-2007 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       becopyheur4.c
  22  * @brief      Simple copy minimization heuristics.
  23  * @author     27.04.2007
  24  * @version    $Id$
  25  * @license
  26  *
  27  * Copyrigth (C) 1995-2007 University of Karlsruhe.  All right reserved.
  28  *
  29  * This file is part of libFirm.
  30  *
  31  * This file may be distributed and/or modified under the terms of the
  32  * GNU General Public License version 2 as published by the Free Software
  33  * Foundation and appearing in the file LICENSE.GPL included in the
  34  * packaging of this file.
  35  *
  36  * Licensees holding valid libFirm Professional Edition licenses may use
  37  * this file in accordance with the libFirm Commercial License.
  38  * Agreement provided with the Software.
  39  *
  40  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  41  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  42  * PURPOSE.
  43  *
  44  * @summary
  45  *
  46  * This is the C implementation of the mst algorithm
  47  * originally written in Java by Sebastian Hack.
  48  * (also known as "heur3" :)
  49  * Performs simple copy minimization.
  50  */
  51
  52 #ifdef HAVE_CONFIG_H
  53 #include "config.h"
  54 #endif /* HAVE_CONFIG_H */
  55
  56 #include <float.h>
  57
  58 #include "array.h"
  59 #include "irnode_t.h"
  60 #include "bitset.h"
  61 #include "raw_bitset.h"
  62 #include "irphase_t.h"
  63 #include "pqueue.h"
  64 #include "pset_new.h"
  65 #include "xmalloc.h"
  66 #include "pdeq.h"
  67 #include "irprintf.h"
  68
  69 #include "bearch.h"
  70 #include "beifg.h"
  71 #include "be_t.h"
  72 #include "becopyopt_t.h"
  73 #include "irbitset.h"
  74
  75 #define COL_COST_INFEASIBLE       DBL_MAX
  76 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
  77 #define NEIGHBOUR_CONSTR_COSTS    64.0
  78
  79 #define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(if (firm_dbg_get_mask((env)->dbg) & (level)) dbg_aff_chunk((env), (chunk));)
  80 #define DBG_COL_COST(env, level, cost)   DEBUG_ONLY(if (firm_dbg_get_mask((env)->dbg) & (level)) dbg_col_cost((env), (cost));)
  81
  82 static int last_chunk_id = 0;
  83
  84 typedef struct _col_cost_t {
  85         int    col;
  86         double cost;
  87 } col_cost_t;
  88
  89 typedef struct _aff_chunk_t {
  90         bitset_t *nodes;
  91         int      weight;
  92         unsigned weight_consistent : 1;
  93         int      id;
  94 } aff_chunk_t;
  95
  96 typedef struct _aff_edge_t {
  97         ir_node *src;
  98         ir_node *tgt;
  99         double  weight;
 100 } aff_edge_t;
 101
 102 /* main coalescing environment*/
 103 typedef struct _co_mst_env_t {
 104         int              n_regs;         /**< number of regs in class */
 105         int              k;              /**< number of non-ignore registers in class */
 106         bitset_t         *ignore_regs;   /**< set containing all global ignore registers */
 107         ir_phase         ph;             /**< phase object holding data for nodes */
 108         pqueue           *chunks;        /**< priority queue for chunks */
 109         pset_new_t       chunkset;       /**< set holding all chunks */
 110         be_ifg_t         *ifg;           /**< the interference graph */
 111         const arch_env_t *aenv;          /**< the arch environment */
 112         copy_opt_t       *co;            /**< the copy opt object */
 113         DEBUG_ONLY(firm_dbg_module_t *dbg);
 114 } co_mst_env_t;
 115
 116 /* stores coalescing related information for a node */
 117 typedef struct _co_mst_irn_t {
 118         ir_node     *irn;              /**< the irn this information belongs to */
 119         aff_chunk_t *chunk;            /**< the chunk this irn belongs to */
 120         bitset_t    *adm_colors;       /**< set of admissible colors for this irn */
 121         ir_node     **int_neighs;      /**< ARR_D of all interfering neighbours (cached for speed reasons) */
 122         int         int_aff_neigh;     /**< number of interfering affinity neighbours */
 123         int         col;               /**< color currently assigned */
 124         int         init_col;          /**< the initial color */
 125         int         tmp_col;           /**< a temporary assigned color */
 126         unsigned    fixed     : 1;     /**< the color is fixed */
 127         unsigned    tmp_fixed : 1;     /**< the color is temporary fixed */
 128 } co_mst_irn_t;
 129
 130 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
 131
 132 typedef int decide_func_t(co_mst_irn_t *node, int col);
 133
 134 #ifdef DEBUG_libfirm
 135
 136 /**
 137  * Write a chunk to stderr for debugging.
 138  */
 139 static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 140         int idx;
 141         if (c->weight_consistent)
 142                 ir_fprintf(stderr, " $%d ", c->weight);
 143         ir_fprintf(stderr, "{");
 144         bitset_foreach(c->nodes, idx) {
 145                 ir_node *n = get_idx_irn(env->co->irg, idx);
 146                 ir_fprintf(stderr, " %+F,", n);
 147         }
 148         ir_fprintf(stderr, "}");
 149 }
 150
 151 /**
 152  * Dump all admissible colors to stderr.
 153  */
 154 static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) {
 155         int idx;
 156         if (bitset_popcnt(node->adm_colors) < 1)
 157                 fprintf(stderr, "no admissible colors?!?");
 158         else {
 159                 bitset_foreach(node->adm_colors, idx)
 160                         fprintf(stderr, " %d", idx);
 161         }
 162 }
 163
 164 /**
 165  * Dump color-cost pairs to stderr.
 166  */
 167 static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) {
 168         int i;
 169         for (i = 0; i < env->n_regs; ++i) {
 170                 if (cost[i].cost == COL_COST_INFEASIBLE)
 171                         fprintf(stderr, " (%d, INF)", cost[i].col);
 172                 else
 173                         fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
 174         }
 175 }
 176
 177 #endif /* DEBUG_libfirm */
 178
 179 static INLINE int get_mst_irn_col(co_mst_irn_t *node) {
 180         return node->tmp_fixed ? node->tmp_col : node->col;
 181 }
 182
 183 /**
 184  * @return 1 if node @p node has color @p col, 0 otherwise.
 185  */
 186 static int decider_has_color(co_mst_irn_t *node, int col) {
 187         return get_mst_irn_col(node) == col;
 188 }
 189
 190 /**
 191  * @return 1 if node @p node has not color @p col, 0 otherwise.
 192  */
 193 static int decider_hasnot_color(co_mst_irn_t *node, int col) {
 194         return get_mst_irn_col(node) != col;
 195 }
 196
 197 /**
 198  * Always returns true.
 199  */
 200 static int decider_always_yes(co_mst_irn_t *node, int col) {
 201         return 1;
 202 }
 203
 204 /* > compares two affinity edges by its weight */
 205 static int cmp_aff_edge(const void *a, const void *b) {
 206         const aff_edge_t *e1 = a;
 207         const aff_edge_t *e2 = b;
 208
 209         if (e2->weight == e1->weight) {
 210                 if (e2->src->node_idx == e1->src->node_idx)
 211                         return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
 212                 else
 213                         return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
 214         }
 215         /* sort in descending order */
 216         return QSORT_CMP(e2->weight, e1->weight);
 217 }
 218
 219 /* compares to color-cost pairs */
 220 static int cmp_col_cost(const void *a, const void *b) {
 221         const col_cost_t *c1 = a;
 222         const col_cost_t *c2 = b;
 223
 224         return c1->cost < c2->cost ? -1 : 1;
 225 }
 226
 227 /**
 228  * Creates a new affinity chunk
 229  */
 230 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
 231         aff_chunk_t *c = xmalloc(sizeof(*c));
 232         c->weight            = -1;
 233         c->weight_consistent = 0;
 234         c->nodes             = bitset_irg_malloc(env->co->irg);
 235         c->id                = last_chunk_id++;
 236         pset_new_insert(&env->chunkset, c);
 237         return c;
 238 }
 239
 240 /**
 241  * Frees all memory allocated by an affinity chunk.
 242  */
 243 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 244         pset_new_remove(&env->chunkset, c);
 245         bitset_free(c->nodes);
 246         free(c);
 247 }
 248
 249 /**
 250  * Adds a node to an affinity chunk
 251  */
 252 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
 253         c->weight_consistent = 0;
 254         node->chunk          = c;
 255         bitset_set(c->nodes, get_irn_idx(node->irn));
 256 }
 257
 258 /**
 259  * In case there is no phase information for irn, initialize it.
 260  */
 261 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
 262         co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
 263         co_mst_env_t *env = ph->priv;
 264
 265         if (res != old) {
 266                 const arch_register_req_t *req;
 267                 void     *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
 268                 ir_node  *neigh;
 269                 unsigned len;
 270
 271                 res->irn           = irn;
 272                 res->chunk         = new_aff_chunk(env);
 273                 res->fixed         = 0;
 274                 res->tmp_fixed     = 0;
 275                 res->tmp_col       = -1;
 276                 res->int_neighs    = NULL;
 277                 res->int_aff_neigh = 0;
 278                 res->col           = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
 279                 res->init_col      = res->col;
 280
 281                 /* add note to new chunk */
 282                 aff_chunk_add_node(res->chunk, res);
 283
 284                 DB((env->dbg, LEVEL_4, "Creating phase info for %+F, chunk %d\n", irn, res->chunk->id));
 285
 286                 /* set admissible registers */
 287                 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
 288
 289                 /* Exclude colors not assignable to the irn */
 290                 req = arch_get_register_req(env->aenv, irn, -1);
 291                 if (arch_register_req_is(req, limited))
 292                         rbitset_copy_to_bitset(req->limited, res->adm_colors);
 293                 else
 294                         bitset_set_all(res->adm_colors);
 295
 296                 /* exclude global ignore registers as well */
 297                 bitset_andnot(res->adm_colors, env->ignore_regs);
 298
 299                 /* set the number of interfering affinity neighbours to -1, they are calculated later */
 300                 res->int_aff_neigh = -1;
 301
 302                 /* build list of interfering neighbours */
 303                 len = 0;
 304                 /* count them first as an obstack array cannot be extended */
 305                 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
 306                         len++;
 307                 res->int_neighs = NEW_ARR_D(ir_node *, phase_obst(ph), len);
 308                 len = 0;
 309                 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
 310                         res->int_neighs[len++] = neigh;
 311         }
 312         return res;
 313 }
 314
 315 /**
 316  * Check if affinity chunk @p chunk interferes with node @p irn.
 317  */
 318 static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) {
 319         co_mst_irn_t *node = get_co_mst_irn(env, irn);
 320         ir_node      *neigh;
 321         int          i;
 322
 323         for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
 324                 neigh = node->int_neighs[i];
 325                 if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
 326                         return 1;
 327         }
 328
 329         return 0;
 330 }
 331
 332 /**
 333  * Check if there are interference edges from c1 to c2.
 334  * @param env   The global co_mst environment
 335  * @param c1    A chunk
 336  * @param c2    Another chunk
 337  * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
 338  */
 339 static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
 340         int idx;
 341
 342         if (c1 == c2)
 343                 return 0;
 344
 345         /* check if there is a node in c2 having an interfering neighbor in c1 */
 346         bitset_foreach(c2->nodes, idx) {
 347                 ir_node *n = get_idx_irn(env->co->irg, idx);
 348
 349                 if (aff_chunk_interferes(env, c1, n))
 350                         return 1;
 351         }
 352
 353         return 0;
 354 }
 355
 356 /**
 357  * Let c1 absorb the nodes of c2 (only possible when there
 358  * are no interference edges from c1 to c2).
 359  * @return 1 if successful, 0 if not possible
 360  */
 361 static int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
 362         DB((env->dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1->id));
 363         DBG_AFF_CHUNK(env, LEVEL_4, c1);
 364         DB((env->dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2->id));
 365         DBG_AFF_CHUNK(env, LEVEL_4, c2);
 366         DB((env->dbg, LEVEL_4, "\n"));
 367
 368         if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
 369                 int idx;
 370
 371                 bitset_or(c1->nodes, c2->nodes);
 372                 c1->weight_consistent = 0;
 373
 374                 bitset_foreach(c2->nodes, idx) {
 375                         ir_node      *n  = get_idx_irn(env->co->irg, idx);
 376                         co_mst_irn_t *mn = get_co_mst_irn(env, n);
 377                         mn->chunk = c1;
 378                 }
 379
 380                 DB((env->dbg, LEVEL_4, " ... absorbed, c2 deleted\n"));
 381                 delete_aff_chunk(env, c2);
 382                 return 1;
 383         }
 384         DB((env->dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
 385         return 0;
 386 }
 387
 388 /**
 389  * Returns the affinity chunk of @p irn or creates a new
 390  * one with @p irn as element if there is none assigned.
 391  */
 392 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
 393         co_mst_irn_t *node = get_co_mst_irn(env, irn);
 394         assert(node->chunk && "Node should have a chunk.");
 395         return node->chunk;
 396 }
 397
 398 /**
 399  * Assures that the weight of the given chunk is consistent.
 400  */
 401 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
 402         if (! c->weight_consistent) {
 403                 int w = 0;
 404                 int idx;
 405
 406                 bitset_foreach(c->nodes, idx) {
 407                         ir_node         *n  = get_idx_irn(env->co->irg, idx);
 408                         affinity_node_t *an = get_affinity_info(env->co, n);
 409
 410                         if (an != NULL) {
 411                                 neighb_t *neigh;
 412                                 co_gs_foreach_neighb(an, neigh) {
 413                                         ir_node      *m    = neigh->irn;
 414                                         int          m_idx = get_irn_idx(m);
 415
 416                                         /* skip ignore nodes */
 417                                         if (arch_irn_is(env->aenv, m, ignore))
 418                                                 continue;
 419
 420                                         w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
 421                                 }
 422                         }
 423                 }
 424
 425                 c->weight            = w;
 426                 c->weight_consistent = 1;
 427         }
 428 }
 429
 430 /**
 431  * Count the number of interfering affinity neighbours
 432  */
 433 static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) {
 434         neighb_t     *neigh;
 435         ir_node      *irn  = an->irn;
 436         co_mst_irn_t *node = get_co_mst_irn(env, irn);
 437         int          res   = 0;
 438
 439         co_gs_foreach_neighb(an, neigh) {
 440                 ir_node *n = neigh->irn;
 441                 int     i;
 442
 443                 /* skip ignore nodes */
 444                 if (arch_irn_is(env->aenv, n, ignore))
 445                         continue;
 446
 447                 /* check if the affinity neighbour interfere */
 448                 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
 449                         if (node->int_neighs[i] == n) {
 450                                 ++res;
 451                                 break;
 452                         }
 453                 }
 454         }
 455         return res;
 456 }
 457
 458
 459 /**
 460  * Build chunks of nodes connected by affinity edges.
 461  * We start at the heaviest affinity edge.
 462  * The chunks of the two edge-defining nodes will be
 463  * merged if there are no interference edges from one
 464  * chunk to the other.
 465  */
 466 static void build_affinity_chunks(co_mst_env_t *env) {
 467         void        *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
 468         aff_edge_t  *edges    = NEW_ARR_F(aff_edge_t, 0);
 469         ir_node     *n;
 470         int         i, len;
 471         aff_chunk_t *curr_chunk;
 472         pset_new_iterator_t iter;
 473
 474         /* at first we create the affinity edge objects */
 475         be_ifg_foreach_node(env->ifg, nodes_it, n) {
 476                 int             n_idx = get_irn_idx(n);
 477                 co_mst_irn_t    *n1;
 478                 affinity_node_t *an;
 479
 480                 /* skip ignore nodes */
 481                 if (arch_irn_is(env->aenv, n, ignore))
 482                         continue;
 483
 484                 n1 = get_co_mst_irn(env, n);
 485                 an = get_affinity_info(env->co, n);
 486
 487                 if (an != NULL) {
 488                         neighb_t *neigh;
 489
 490                         if (n1->int_aff_neigh < 0)
 491                                 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
 492                         co_gs_foreach_neighb(an, neigh) {
 493                                 ir_node *m    = neigh->irn;
 494                                 int     m_idx = get_irn_idx(m);
 495
 496                                 /* record the edge in only one direction */
 497                                 if (n_idx < m_idx) {
 498                                         co_mst_irn_t *n2;
 499                                         aff_edge_t   edge;
 500
 501                                         /* skip ignore nodes */
 502                                         if (arch_irn_is(env->aenv, m, ignore))
 503                                                 continue;
 504
 505                                         edge.src = n;
 506                                         edge.tgt = m;
 507
 508                                         n2 = get_co_mst_irn(env, m);
 509                                         if (n2->int_aff_neigh < 0) {
 510                                                 affinity_node_t *am = get_affinity_info(env->co, m);
 511                                                 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
 512                                         }
 513                                         edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
 514                                         ARR_APP1(aff_edge_t, edges, edge);
 515                                 }
 516                         }
 517                 }
 518         }
 519
 520         /* now: sort edges and build the affinity chunks */
 521         len = ARR_LEN(edges);
 522         qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
 523         for (i = 0; i < len; ++i) {
 524                 aff_chunk_t *c1 = get_aff_chunk(env, edges[i].src);
 525                 aff_chunk_t *c2 = get_aff_chunk(env, edges[i].tgt);
 526
 527                 DBG((env->dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
 528
 529                 (void)aff_chunk_absorb(env, c1, c2);
 530         }
 531
 532         /* now insert all chunks into a priority queue */
 533         foreach_pset_new(&env->chunkset, curr_chunk, iter) {
 534                 aff_chunk_assure_weight(env, curr_chunk);
 535
 536                 DBG((env->dbg, LEVEL_1, "entry #%d", curr_chunk->id));
 537                 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
 538                 DBG((env->dbg, LEVEL_1, "\n"));
 539
 540
 541                 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
 542         }
 543
 544         DEL_ARR_F(edges);
 545 }
 546
 547 /**
 548  * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
 549  */
 550 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
 551         aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
 552 {
 553         waitq *nodes = new_waitq();
 554
 555         DBG((env->dbg, LEVEL_1, "\nExpanding new chunk (id %d) from %+F:", chunk->id, node->irn));
 556
 557         /* init queue and chunk */
 558         waitq_put(nodes, node);
 559         bitset_set(visited, get_irn_idx(node->irn));
 560         aff_chunk_add_node(chunk, node);
 561         DB((env->dbg, LEVEL_1, " %+F", node->irn));
 562
 563         /* as long as there are nodes in the queue */
 564         while (! waitq_empty(nodes)) {
 565                 co_mst_irn_t    *n  = waitq_get(nodes);
 566                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 567
 568                 /* check all affinity neighbors */
 569                 if (an != NULL) {
 570                         neighb_t *neigh;
 571                         co_gs_foreach_neighb(an, neigh) {
 572                                 ir_node      *m    = neigh->irn;
 573                                 int          m_idx = get_irn_idx(m);
 574                                 co_mst_irn_t *n2;
 575
 576                                 /* skip ignore nodes */
 577                                 if (arch_irn_is(env->aenv, m, ignore))
 578                                         continue;
 579
 580                                 n2 = get_co_mst_irn(env, m);
 581
 582                                 if (! bitset_is_set(visited, m_idx)       &&
 583                                         decider(n2, col)                      &&
 584                                         ! n2->fixed                           &&
 585                                         ! aff_chunk_interferes(env, chunk, m) &&
 586                                         bitset_is_set(orig_chunk->nodes, m_idx))
 587                                 {
 588                                         /*
 589                                                 following conditions are met:
 590                                                 - neighbour is not visited
 591                                                 - neighbour likes the color
 592                                                 - neighbour has not yet a fixed color
 593                                                 - the new chunk doesn't interfere with the neighbour
 594                                                 - neighbour belongs or belonged once to the original chunk
 595                                         */
 596                                         bitset_set(visited, m_idx);
 597                                         aff_chunk_add_node(chunk, n2);
 598                                         DB((env->dbg, LEVEL_1, " %+F", n2->irn));
 599                                         /* enqueue for further search */
 600                                         waitq_put(nodes, n2);
 601                                 }
 602                         }
 603                 }
 604         }
 605
 606         DB((env->dbg, LEVEL_1, "\n"));
 607
 608         del_waitq(nodes);
 609 }
 610
 611 /**
 612  * Fragment the given chunk into chunks having given color and not having given color.
 613  */
 614 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
 615         bitset_t    *visited = bitset_irg_malloc(env->co->irg);
 616         int         idx;
 617         aff_chunk_t *best = NULL;
 618
 619         bitset_foreach(c->nodes, idx) {
 620                 ir_node       *irn;
 621                 co_mst_irn_t  *node;
 622                 aff_chunk_t   *tmp_chunk;
 623                 decide_func_t *decider;
 624                 int           check_for_best;
 625
 626                 if (bitset_is_set(visited, idx))
 627                         continue;
 628
 629                 irn  = get_idx_irn(env->co->irg, idx);
 630                 node = get_co_mst_irn(env, irn);
 631
 632                 if (get_mst_irn_col(node) == col) {
 633                         decider        = decider_has_color;
 634                         check_for_best = 1;
 635                 }
 636                 else {
 637                         decider        = decider_hasnot_color;
 638                         check_for_best = 0;
 639                 }
 640
 641                 /* create a new chunk starting at current node */
 642                 tmp_chunk = new_aff_chunk(env);
 643                 waitq_put(tmp, tmp_chunk);
 644                 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
 645                 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
 646
 647                 /* remember the local best */
 648                 aff_chunk_assure_weight(env, tmp_chunk);
 649                 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
 650                         best = tmp_chunk;
 651         }
 652
 653         assert(best && "No chunk found?");
 654         bitset_free(visited);
 655         return best;
 656 }
 657
 658 /**
 659  * Initializes an array of color-cost pairs.
 660  * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
 661  */
 662 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
 663         int i;
 664
 665         for (i = 0; i < env->n_regs; ++i) {
 666                 cost[i].col = i;
 667                 if (bitset_is_set(env->ignore_regs, i))
 668                         cost[i].cost = COL_COST_INFEASIBLE;
 669                 else
 670                         cost[i].cost = c;
 671         }
 672 }
 673
 674 /**
 675  * Initializes an array of color-cost pairs.
 676  * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
 677  */
 678 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
 679         assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
 680         col_cost_init(env, cost, COL_COST_INFEASIBLE);
 681         cost[col].col = 0;
 682         cost[0].col   = col;
 683         cost[0].cost  = 0.0;
 684 }
 685
 686 /**
 687  * Resets the temporary fixed color of all nodes within wait queue @p nodes.
 688  * ATTENTION: the queue is empty after calling this function!
 689  */
 690 static INLINE void reject_coloring(waitq *nodes) {
 691         while (! waitq_empty(nodes)) {
 692                 co_mst_irn_t *n = waitq_get(nodes);
 693                 n->tmp_fixed = 0;
 694         }
 695 }
 696
 697 /**
 698  * Determines the costs for each color if it would be assigned to node @p node.
 699  */
 700 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
 701         affinity_node_t *an = get_affinity_info(env->co, node->irn);
 702         neighb_t        *aff_neigh;
 703         int             idx, i;
 704
 705         col_cost_init(env, costs, 0.0);
 706
 707         /* calculate (negative) costs for affinity neighbours */
 708         if (an != NULL) {
 709                 co_gs_foreach_neighb(an, aff_neigh) {
 710                         ir_node      *m = aff_neigh->irn;
 711                         co_mst_irn_t *neigh;
 712                         double       c;
 713
 714                         /* skip ignore nodes */
 715                         if (arch_irn_is(env->aenv, m, ignore))
 716                                 continue;
 717
 718                         neigh = get_co_mst_irn(env, m);
 719                         c     = (double)aff_neigh->costs;
 720
 721                         /* calculate costs for fixed affinity neighbours */
 722                         if (neigh->tmp_fixed || neigh->fixed) {
 723                                 int col = get_mst_irn_col(neigh);
 724                                 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
 725                         }
 726                 }
 727         }
 728
 729         /* calculate (positive) costs for interfering neighbours */
 730         for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
 731                 co_mst_irn_t *neigh;
 732                 int          col, col_cnt;
 733                 ir_node      *int_neigh;
 734
 735                 int_neigh = node->int_neighs[i];
 736
 737                 /* skip ignore nodes */
 738                 if (arch_irn_is(env->aenv, int_neigh, ignore))
 739                         continue;
 740
 741                 neigh   = get_co_mst_irn(env, int_neigh);
 742                 col     = get_mst_irn_col(neigh);
 743                 col_cnt = bitset_popcnt(neigh->adm_colors);
 744
 745                 if (neigh->tmp_fixed || neigh->fixed) {
 746                         /* colors of fixed interfering neighbours are infeasible */
 747                         costs[col].cost = COL_COST_INFEASIBLE;
 748                 }
 749                 else if (col_cnt < env->k) {
 750                         /* calculate costs for constrained interfering neighbours */
 751                         double ratio = 1.0 - ((double)col_cnt / (double)env->k);
 752
 753                         bitset_foreach_clear(neigh->adm_colors, idx) {
 754                                 /* check only explicitly forbidden colors (skip global forbidden ones) */
 755                                 if (! bitset_is_set(env->ignore_regs, idx)) {
 756                                         costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
 757                                 }
 758                         }
 759                 }
 760         }
 761
 762         /* set all not admissible colors to COL_COST_INFEASIBLE */
 763         bitset_foreach_clear(node->adm_colors, idx)
 764                 costs[idx].cost = COL_COST_INFEASIBLE;
 765 }
 766
 767 /* need forward declaration due to recursive call */
 768 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
 769
 770 /**
 771  * Tries to change node to a color but @p explude_col.
 772  * @return 1 if succeeded, 0 otherwise.
 773  */
 774 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
 775         int col = get_mst_irn_col(node);
 776         int res = 0;
 777
 778         /* neighbours has already a different color -> good, temporary fix it */
 779         if (col != exclude_col) {
 780                 node->tmp_fixed = 1;
 781                 node->tmp_col   = col;
 782                 waitq_put(changed_ones, node);
 783                 return 1;
 784         }
 785
 786         /* The node has the color it should not have _and_ has not been visited yet. */
 787         if (! (node->tmp_fixed || node->fixed)) {
 788                 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
 789
 790                 /* Get the costs for giving the node a specific color. */
 791                 determine_color_costs(env, node, costs);
 792
 793                 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
 794                 costs[exclude_col].cost = COL_COST_INFEASIBLE;
 795
 796                 /* sort the colors according costs, cheapest first. */
 797                 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
 798
 799                 /* Try recoloring the node using the color list. */
 800                 res = recolor_nodes(env, node, costs, changed_ones);
 801         }
 802
 803         return res;
 804 }
 805
 806 /**
 807  * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
 808  * ATTENTION: Expect @p costs already sorted by increasing costs.
 809  * @return 1 if coloring could be applied, 0 otherwise.
 810  */
 811 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
 812         int   i;
 813         waitq *local_changed = new_waitq();
 814         waitq *tmp           = new_waitq();
 815
 816         DBG((env->dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
 817         DBG_COL_COST(env, LEVEL_1, costs);
 818         DB((env->dbg, LEVEL_1, "\n"));
 819
 820         for (i = 0; i < env->n_regs; ++i) {
 821                 int tgt_col  = costs[i].col;
 822                 int neigh_ok = 1;
 823                 int j;
 824
 825                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 826                 if (costs[i].cost == COL_COST_INFEASIBLE) {
 827                         node->tmp_fixed = 0;
 828                         del_waitq(local_changed);
 829                         del_waitq(tmp);
 830                         return 0;
 831                 }
 832
 833                 /* Set the new color of the node and mark the node as temporarily fixed. */
 834                 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
 835                 node->tmp_fixed = 1;
 836                 node->tmp_col   = tgt_col;
 837
 838                 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
 839                 waitq_put(local_changed, node);
 840
 841                 /* try to color all interfering neighbours with current color forbidden */
 842                 for (j = 0; j < ARR_LEN(node->int_neighs); ++j) {
 843                         co_mst_irn_t *nn;
 844                         ir_node      *neigh;
 845
 846                         neigh = node->int_neighs[j];
 847
 848                         /* skip ignore nodes */
 849                         if (arch_irn_is(env->aenv, neigh, ignore))
 850                                 continue;
 851
 852                         nn = get_co_mst_irn(env, neigh);
 853
 854                         /*
 855                                 Try to change the color of the neighbor and record all nodes which
 856                                 get changed in the tmp list. Add this list to the "changed" list for
 857                                 that color. If we did not succeed to change the color of the neighbor,
 858                                 we bail out and try the next color.
 859                         */
 860                         if (get_mst_irn_col(nn) == tgt_col) {
 861                                 /* try to color neighbour with tgt_col forbidden */
 862                                 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
 863
 864                                 /* join lists of changed nodes */
 865                                 while (! waitq_empty(tmp))
 866                                         waitq_put(local_changed, waitq_get(tmp));
 867
 868                                 if (! neigh_ok)
 869                                         break;
 870                         }
 871                 }
 872
 873                 /*
 874                         We managed to assign the target color to all neighbors, so from the perspective
 875                         of the current node, every thing was ok and we can return safely.
 876                 */
 877                 if (neigh_ok) {
 878                         /* append the local_changed ones to global ones */
 879                         while (! waitq_empty(local_changed))
 880                                 waitq_put(changed_ones, waitq_get(local_changed));
 881                         del_waitq(local_changed);
 882                         del_waitq(tmp);
 883                         return 1;
 884                 }
 885                 else {
 886                         /* coloring of neighbours failed, so we try next color */
 887                         reject_coloring(local_changed);
 888                 }
 889         }
 890
 891         del_waitq(local_changed);
 892         del_waitq(tmp);
 893         return 0;
 894 }
 895
 896 /**
 897  * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
 898  * @return 1 if color @p col could be applied, 0 otherwise
 899  */
 900 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
 901         int col = get_mst_irn_col(node);
 902
 903         /* if node already has the target color -> good, temporary fix it */
 904         if (col == tgt_col) {
 905                 DBG((env->dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
 906                 if (! node->tmp_fixed) {
 907                         node->tmp_fixed = 1;
 908                         node->tmp_col   = tgt_col;
 909                         waitq_put(changed_ones, node);
 910                 }
 911                 return 1;
 912         }
 913
 914         /*
 915                 Node has not yet a fixed color and target color is admissible
 916                 -> try to recolor node and it's affinity neighbours
 917         */
 918         if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
 919                 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
 920                 int        res;
 921
 922                 col_cost_init_single(env, costs, tgt_col);
 923
 924                 DBG((env->dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
 925                 res = recolor_nodes(env, node, costs, changed_ones);
 926                 DBG((env->dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
 927
 928                 return res;
 929         }
 930
 931         DEBUG_ONLY(
 932                 if (firm_dbg_get_mask(env->dbg) & LEVEL_4) {
 933                         if (node->fixed || node->tmp_fixed)
 934                                 DB((env->dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
 935                         else {
 936                                 DB((env->dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
 937                                 dbg_admissible_colors(env, node);
 938                                 DB((env->dbg, LEVEL_4, ")\n"));
 939                         }
 940                 }
 941         )
 942
 943         return 0;
 944 }
 945
 946 /**
 947  * Tries to color an affinity chunk (or at least a part of it).
 948  * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
 949  */
 950 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 951         aff_chunk_t *best_chunk   = NULL;
 952         int         best_color    = -1;
 953         waitq       *changed_ones = new_waitq();
 954         waitq       *tmp_chunks   = new_waitq();
 955         bitset_t    *visited;
 956         int         col, idx;
 957
 958         DB((env->dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
 959         DBG_AFF_CHUNK(env, LEVEL_2, c);
 960         DB((env->dbg, LEVEL_2, "\n"));
 961
 962
 963         /* check which color is the "best" for the given chunk */
 964         for (col = 0; col < env->k; ++col) {
 965                 int         one_good = 0;
 966                 aff_chunk_t *local_best;
 967
 968                 DB((env->dbg, LEVEL_3, "\ttrying color %d\n", col));
 969
 970                 /* try to bring all nodes of given chunk to the current color. */
 971                 bitset_foreach(c->nodes, idx) {
 972                         ir_node      *irn  = get_idx_irn(env->co->irg, idx);
 973                         co_mst_irn_t *node = get_co_mst_irn(env, irn);
 974
 975                         assert(! node->fixed && "Node must not have a fixed color.");
 976
 977                         DB((env->dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
 978                         one_good |= change_node_color(env, node, col, changed_ones);
 979                         DB((env->dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
 980                 }
 981
 982                 /* try next color when failed */
 983                 if (! one_good)
 984                         continue;
 985
 986                 /* fragment the chunk according to the coloring */
 987                 local_best = fragment_chunk(env, col, c, tmp_chunks);
 988
 989                 /* search the best of the good list
 990                    and make it the new best if it is better than the current */
 991                 if (local_best) {
 992                         aff_chunk_assure_weight(env, local_best);
 993
 994                         DB((env->dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
 995                         DBG_AFF_CHUNK(env, LEVEL_4, local_best);
 996
 997                         if (! best_chunk || best_chunk->weight < local_best->weight) {
 998                                 best_chunk = local_best;
 999                                 best_color = col;
1000                                 DB((env->dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1001                         } else {
1002                                 DB((env->dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1003                         }
1004                 }
1005
1006                 /* reject the coloring and bring the coloring to the initial state */
1007                 reject_coloring(changed_ones);
1008         }
1009
1010         /* free all intermediate created chunks except best one */
1011         while (! waitq_empty(tmp_chunks)) {
1012                 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1013                 if (tmp != best_chunk)
1014                         delete_aff_chunk(env, tmp);
1015         }
1016         del_waitq(tmp_chunks);
1017
1018         /* return if coloring failed */
1019         if (! best_chunk) {
1020                 delete_aff_chunk(env, c);
1021                 del_waitq(changed_ones);
1022                 return;
1023         }
1024
1025         DB((env->dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1026         DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1027         DB((env->dbg, LEVEL_2, "using color %d\n", best_color));
1028
1029         /* get the best fragment from the best list and color it */
1030         bitset_foreach(best_chunk->nodes, idx) {
1031                 ir_node      *irn  = get_idx_irn(env->co->irg, idx);
1032                 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1033                 int          res;
1034
1035                 res = change_node_color(env, node, best_color, changed_ones);
1036                 assert(res && "color manifesting failed");
1037                 node->fixed = 1;
1038                 node->chunk = best_chunk;
1039         }
1040
1041         /* materialize colors on changed nodes */
1042         while (! waitq_empty(changed_ones)) {
1043                 co_mst_irn_t *n = waitq_get(changed_ones);
1044                 n->tmp_fixed = 0;
1045                 n->col       = n->tmp_col;
1046         }
1047
1048         /* remove the nodes in best chunk from original chunk */
1049         bitset_andnot(c->nodes, best_chunk->nodes);
1050
1051         /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1052         bitset_foreach(c->nodes, idx) {
1053                 ir_node      *n  = get_idx_irn(env->co->irg, idx);
1054                 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1055                 nn->chunk = c;
1056         }
1057
1058         /* fragment the remaining chunk */
1059         visited = bitset_irg_malloc(env->co->irg);
1060         bitset_or(visited, best_chunk->nodes);
1061         bitset_foreach(c->nodes, idx) {
1062                 if (! bitset_is_set(visited, idx)) {
1063                         aff_chunk_t  *new_chunk = new_aff_chunk(env);
1064                         ir_node      *irn       = get_idx_irn(env->co->irg, idx);
1065                         co_mst_irn_t *node      = get_co_mst_irn(env, irn);
1066
1067                         expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1068                         aff_chunk_assure_weight(env, new_chunk);
1069                         pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1070                 }
1071         }
1072
1073         /* clear obsolete chunks and free some memory */
1074         delete_aff_chunk(env, best_chunk);
1075         bitset_free(visited);
1076         del_waitq(changed_ones);
1077 }
1078
1079 /**
1080  * Main driver for mst safe coalescing algorithm.
1081  */
1082 int co_solve_heuristic_mst(copy_opt_t *co)
1083 {
1084         unsigned     n_regs       = co->cls->n_regs;
1085         bitset_t     *ignore_regs = bitset_alloca(n_regs);
1086         unsigned     k;
1087         ir_node      *irn;
1088         co_mst_env_t mst_env;
1089
1090         /* init phase */
1091         phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1092
1093         k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1094         k = n_regs - k;
1095
1096         FIRM_DBG_REGISTER(mst_env.dbg, "firm.be.co.heur4");
1097         mst_env.n_regs      = n_regs;
1098         mst_env.k           = k;
1099         mst_env.chunks      = new_pqueue();
1100         mst_env.co          = co;
1101         mst_env.ignore_regs = ignore_regs;
1102         mst_env.ifg         = co->cenv->ifg;
1103         mst_env.aenv        = co->aenv;
1104         pset_new_init(&mst_env.chunkset);
1105
1106         DBG((mst_env.dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1107
1108         /* build affinity chunks */
1109         build_affinity_chunks(&mst_env);
1110
1111         /* color chunks as long as there are some */
1112         while (! pqueue_empty(mst_env.chunks)) {
1113                 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1114
1115                 color_aff_chunk(&mst_env, chunk);
1116                 DB((mst_env.dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1117                 delete_aff_chunk(&mst_env, chunk);
1118         }
1119
1120         /* apply coloring */
1121         foreach_phase_irn(&mst_env.ph, irn) {
1122                 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1123                 const arch_register_t *reg;
1124
1125                 if (arch_irn_is(mst_env.aenv, irn, ignore))
1126                         continue;
1127
1128                 assert(mirn->fixed && "Node should have fixed color");
1129
1130                 /* skip nodes where color hasn't changed */
1131                 if (mirn->init_col == mirn->col)
1132                         continue;
1133
1134                 reg = arch_register_for_index(co->cls, mirn->col);
1135                 arch_set_irn_register(co->aenv, irn, reg);
1136                 DB((mst_env.dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1137         }
1138
1139         /* free allocated memory */
1140         del_pqueue(mst_env.chunks);
1141         phase_free(&mst_env.ph);
1142         pset_new_destroy(&mst_env.chunkset);
1143
1144         return 0;
1145 }