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

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