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