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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       More experiments on coalescing.
   9  * @author      Sebastian Hack
  10  * @date        14.04.2006
  11  */
  12 #include "config.h"
  13
  14 #include "lc_opts.h"
  15 #include "lc_opts_enum.h"
  16
  17 #include <stdlib.h>
  18 #include <limits.h>
  19
  20 #include "beintlive_t.h"
  21 #include "beirg.h"
  22 #include "list.h"
  23 #include "pdeq.h"
  24 #include "bitset.h"
  25 #include "raw_bitset.h"
  26
  27 #include "debug.h"
  28 #include "bitfiddle.h"
  29
  30 #include "irgraph_t.h"
  31 #include "irnode_t.h"
  32 #include "irprintf.h"
  33 #include "util.h"
  34 #include "irtools.h"
  35 #include "irnodemap.h"
  36 #include "be_t.h"
  37 #include "bemodule.h"
  38 #include "beabi.h"
  39 #include "benode.h"
  40 #include "becopyopt.h"
  41 #include "becopyopt_t.h"
  42 #include "bechordal_t.h"
  43
  44 #define DUMP_BEFORE 1
  45 #define DUMP_AFTER  2
  46 #define DUMP_CLOUD  4
  47 #define DUMP_ALL    2 * DUMP_CLOUD - 1
  48
  49 static unsigned dump_flags      = 0;
  50 static int      subtree_iter    = 4;
  51 static int      max_depth       = 20;
  52 static double   constr_factor   = 0.9;
  53
  54 static const lc_opt_enum_mask_items_t dump_items[] = {
  55         { "before",  DUMP_BEFORE },
  56         { "after",   DUMP_AFTER  },
  57         { "cloud",   DUMP_CLOUD  },
  58         { "all",     DUMP_ALL    },
  59         { NULL,      0 }
  60 };
  61
  62 static lc_opt_enum_mask_var_t dump_var = {
  63         &dump_flags, dump_items
  64 };
  65
  66 static const lc_opt_table_entry_t options[] = {
  67         LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                                         &dump_var),
  68         LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes",                           &subtree_iter),
  69         LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
  70         LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
  71         LC_OPT_LAST
  72 };
  73
  74 /*
  75   ____  _             _
  76  / ___|| |_ __ _ _ __| |_
  77  \___ \| __/ _` | '__| __|
  78   ___) | || (_| | |  | |_
  79  |____/ \__\__,_|_|   \__|
  80
  81 */
  82
  83 #define INFEASIBLE(cost) ((cost) == INT_MAX)
  84
  85 typedef unsigned col_t;
  86
  87 typedef struct co2_irn_t       co2_irn_t;
  88 typedef struct co2_cloud_t     co2_cloud_t;
  89 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
  90
  91 typedef struct {
  92         col_t col;
  93         int costs;
  94 } col_cost_pair_t;
  95
  96 typedef struct {
  97         ir_nodemap     map;
  98         struct obstack obst;
  99         copy_opt_t *co;
 100         bitset_t   *allocatable_regs;
 101         co2_irn_t  *touched;
 102         int         visited;
 103         int         n_regs;
 104         struct list_head cloud_head;
 105         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 106 } co2_t;
 107
 108 struct co2_irn_t {
 109         const ir_node   *irn;
 110         affinity_node_t *aff;
 111         co2_irn_t       *touched_next;
 112         col_t            tmp_col;
 113         col_t            orig_col;
 114         bitset_t        *adm_cache;
 115         unsigned         fixed          : 1;
 116         unsigned         tmp_fixed      : 1;
 117         struct list_head changed_list;
 118 };
 119
 120 struct co2_cloud_irn_t {
 121         struct co2_irn_t   inh;
 122         co2_cloud_t       *cloud;
 123         int                visited;
 124         int                index;
 125         co2_cloud_irn_t   *mst_parent;
 126         int                mst_costs;
 127         int                mst_n_childs;
 128         co2_cloud_irn_t  **mst_childs;
 129         int               *col_costs;
 130         int                costs;
 131         int               *fronts;
 132         int               *color_badness;
 133         col_cost_pair_t   *tmp_coloring;
 134         struct list_head   cloud_list;
 135         struct list_head   mst_list;
 136 };
 137
 138 struct co2_cloud_t {
 139         co2_t            *env;
 140         struct obstack    obst;
 141         int               costs;
 142         int               mst_costs;
 143         int               inevit;
 144         int               best_costs;
 145         int               n_memb;
 146         int               ticks;
 147         double            freedom;
 148         co2_cloud_irn_t  *master;
 149         co2_cloud_irn_t  *mst_root;
 150         co2_cloud_irn_t **seq;
 151         struct list_head  members_head;
 152         struct list_head  list;
 153 };
 154
 155 typedef struct {
 156         co2_cloud_irn_t *src, *tgt;
 157         int costs;
 158 } edge_t;
 159
 160 #define FRONT_BASE(ci,col)  ((ci)->fronts + col * (ci)->mst_n_childs)
 161
 162 static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
 163 {
 164         co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
 165         if (ci == NULL) {
 166                 ci = OALLOCZ(&env->obst, co2_irn_t);
 167
 168                 INIT_LIST_HEAD(&ci->changed_list);
 169                 ci->touched_next = env->touched;
 170                 ci->orig_col     = get_irn_col(node);
 171                 env->touched     = ci;
 172                 ci->irn          = node;
 173                 ci->aff          = NULL;
 174
 175                 ir_nodemap_insert(&env->map, node, ci);
 176         }
 177         return ci;
 178 }
 179
 180 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
 181 {
 182         co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
 183         if (ci == NULL) {
 184                 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
 185
 186                 INIT_LIST_HEAD(&ci->inh.changed_list);
 187                 ci->inh.touched_next = env->touched;
 188                 ci->inh.orig_col     = get_irn_col(node);
 189                 env->touched         = &ci->inh;
 190                 ci->inh.irn          = node;
 191                 ci->inh.aff          = get_affinity_info(env->co, node);
 192
 193                 INIT_LIST_HEAD(&ci->cloud_list);
 194                 ci->mst_parent = ci;
 195
 196                 ir_nodemap_insert(&env->map, node, ci);
 197         }
 198         return ci;
 199 }
 200
 201 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
 202
 203 static int cmp_clouds_gt(const void *a, const void *b)
 204 {
 205         const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
 206         const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
 207         double c = CLOUD_WEIGHT(*p);
 208         double d = CLOUD_WEIGHT(*q);
 209         return QSORT_CMP(d, c);
 210 }
 211
 212 /**
 213  * An order on color/costs pairs.
 214  * If the costs are equal, we use the color as a kind of normalization.
 215  */
 216 static int col_cost_pair_lt(const void *a, const void *b)
 217 {
 218         const col_cost_pair_t *p = (const col_cost_pair_t*)a;
 219         const col_cost_pair_t *q = (const col_cost_pair_t*)b;
 220         int c = p->costs;
 221         int d = q->costs;
 222         return QSORT_CMP(c, d);
 223 }
 224
 225 static int cmp_edges(const void *a, const void *b)
 226 {
 227         const edge_t *p = (const edge_t*)a;
 228         const edge_t *q = (const edge_t*)b;
 229         return QSORT_CMP(q->costs, p->costs);
 230 }
 231
 232 static col_t get_col(co2_t *env, const ir_node *irn)
 233 {
 234         co2_irn_t *ci = get_co2_irn(env, irn);
 235         return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
 236 }
 237
 238 static inline int color_is_fix(co2_t *env, const ir_node *irn)
 239 {
 240         co2_irn_t *ci = get_co2_irn(env, irn);
 241         return ci->fixed || ci->tmp_fixed;
 242 }
 243
 244 static inline bitset_t const *admissible_colors(co2_t *const env, co2_irn_t *const ci)
 245 {
 246         if (ci->adm_cache == NULL) {
 247                 const arch_register_req_t *req;
 248                 ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
 249                 req = arch_get_irn_register_req(ci->irn);
 250
 251                 if (arch_register_req_is(req, limited)) {
 252                         rbitset_copy_to_bitset(req->limited, ci->adm_cache);
 253                 } else {
 254                         bitset_copy(ci->adm_cache, env->allocatable_regs);
 255                 }
 256         }
 257
 258         return ci->adm_cache;
 259 }
 260
 261 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
 262 {
 263         bitset_t const *const bs = admissible_colors(env, ci);
 264         return bitset_is_set(bs, col);
 265 }
 266
 267 static void incur_constraint_costs(ir_node const *const irn, col_cost_pair_t *const col_costs, int const costs)
 268 {
 269         const arch_register_req_t *req = arch_get_irn_register_req(irn);
 270
 271         if (arch_register_req_is(req, limited)) {
 272                 unsigned const n_regs   = req->cls->n_regs;
 273                 unsigned const n_constr = rbitset_popcount(req->limited, n_regs);
 274                 for (unsigned i = 0; i < n_regs; ++i) {
 275                         if (rbitset_is_set(req->limited, i)) {
 276                                 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
 277                         }
 278                 }
 279         }
 280 }
 281
 282 /**
 283  * Determine costs which shall indicate how cheap/expensive it is to try
 284  * to assign a node some color.
 285  * The costs are computed for all colors. INT_MAX means that it is impossible
 286  * to give the node that specific color.
 287  *
 288  * @param env       The co2 this pointer.
 289  * @param irn       The node.
 290  * @param col_costs An array of colors x costs where the costs are written to.
 291  */
 292 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
 293 {
 294         const ir_node *irn = ci->irn;
 295         be_ifg_t *ifg      = env->co->cenv->ifg;
 296         int n_regs         = env->co->cls->n_regs;
 297         affinity_node_t *a = ci->aff;
 298
 299         neighbours_iter_t it;
 300         int i;
 301
 302         for (i = 0; i < n_regs; ++i) {
 303                 col_costs[i].col   = i;
 304                 col_costs[i].costs = 0;
 305         }
 306
 307         if (a) {
 308                 co_gs_foreach_neighb(a, n) {
 309                         if (color_is_fix(env, n->irn)) {
 310                                 col_t col = get_col(env, n->irn);
 311                                 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
 312                         }
 313
 314                         incur_constraint_costs(n->irn, col_costs, -n->costs);
 315                 }
 316         }
 317
 318         be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
 319                 col_t col = get_col(env, pos);
 320                 if (color_is_fix(env, pos)) {
 321                         col_costs[col].costs  = INT_MAX;
 322                 }
 323                 else {
 324                         incur_constraint_costs(pos, col_costs, INT_MAX);
 325                         col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
 326                 }
 327         }
 328         be_ifg_neighbours_break(&it);
 329
 330         /* Set the costs to infinity for each color which is not allowed at this node. */
 331         bitset_t const *const admissible = admissible_colors(env, ci);
 332         bitset_foreach_clear(admissible, elm) {
 333                 col_costs[elm].costs  = INT_MAX;
 334         }
 335 }
 336
 337 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
 338 {
 339         int n_regs = env->co->cls->n_regs;
 340         int i;
 341
 342         for (i = 0; i < n_regs; ++i) {
 343                 seq[i].col   = i;
 344                 seq[i].costs = INT_MAX;
 345         }
 346
 347         (void) ci;
 348         assert(is_color_admissible(env, ci, col));
 349         seq[col].col = 0;
 350         seq[0].col   = col;
 351         seq[0].costs = 0;
 352 }
 353
 354 static void reject_coloring(struct list_head *h)
 355 {
 356         list_for_each_entry(co2_irn_t, pos, h, changed_list)
 357                 pos->tmp_fixed = 0;
 358 }
 359
 360 static void materialize_coloring(struct list_head *h)
 361 {
 362         list_for_each_entry(co2_irn_t, pos, h, changed_list) {
 363                 pos->orig_col  = pos->tmp_col;
 364                 pos->tmp_fixed = 0;
 365         }
 366 }
 367
 368 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 369
 370 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
 371 {
 372         int n_regs         = env->co->cls->n_regs;
 373         be_ifg_t *ifg      = env->co->cenv->ifg;
 374         co2_irn_t *ci      = get_co2_irn(env, irn);
 375         int res            = 0;
 376
 377         int i;
 378
 379         if (depth >= max_depth)
 380           return 0;
 381
 382         for (i = 0; i < n_regs; ++i) {
 383                 col_t tgt_col  = col_list[i].col;
 384                 unsigned costs = col_list[i].costs;
 385                 int neigh_ok   = 1;
 386
 387                 struct list_head changed;
 388                 neighbours_iter_t it;
 389
 390                 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
 391
 392                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 393                 if (INFEASIBLE(costs)) {
 394                         DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
 395                         ci->tmp_fixed = 0;
 396                         return 0;
 397                 }
 398
 399                 /* Set the new color of the node and mark the node as temporarily fixed. */
 400                 ci->tmp_col     = tgt_col;
 401                 ci->tmp_fixed   = 1;
 402
 403                 /*
 404                 If that color has costs > 0, there's at least one neighbor having that color,
 405                 so we will try to change the neighbors' colors, too.
 406                 */
 407                 INIT_LIST_HEAD(&changed);
 408                 list_add(&ci->changed_list, &changed);
 409
 410                 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
 411
 412                         /* try to re-color the neighbor if it has the target color. */
 413                         if (get_col(env, n) == tgt_col) {
 414                                 struct list_head tmp;
 415
 416                                 /*
 417                                 Try to change the color of the neighbor and record all nodes which
 418                                 get changed in the tmp list. Add this list to the "changed" list for
 419                                 that color. If we did not succeed to change the color of the neighbor,
 420                                 we bail out and try the next color.
 421                                 */
 422                                 INIT_LIST_HEAD(&tmp);
 423                                 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
 424                                 list_splice(&tmp, &changed);
 425                                 if (!neigh_ok)
 426                                         break;
 427                         }
 428                 }
 429                 be_ifg_neighbours_break(&it);
 430
 431                 /*
 432                 We managed to assign the target color to all neighbors, so from the perspective
 433                 of the current node, every thing was ok and we can return safely.
 434                 */
 435                 if (neigh_ok) {
 436                         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
 437                         list_splice(&changed, parent_changed);
 438                         res = 1;
 439                         break;
 440                 }
 441
 442                 /*
 443                 If not, that color did not succeed and we unfix all nodes we touched
 444                 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
 445                 */
 446                 else
 447                         reject_coloring(&changed);
 448         }
 449
 450         return res;
 451 }
 452
 453 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
 454 {
 455         co2_irn_t *ci = get_co2_irn(env, irn);
 456         int res       = 0;
 457         col_t col     = get_col(env, irn);
 458
 459         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
 460
 461         /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
 462         if (col != not_col) {
 463                 if (!ci->tmp_fixed) {
 464                         ci->tmp_col     = col;
 465                         ci->tmp_fixed   = 1;
 466                 }
 467
 468                 list_add(&ci->changed_list, parent_changed);
 469                 return 1;
 470         }
 471
 472         /* The node has the color it should not have _and_ has not been visited yet. */
 473         if (!color_is_fix(env, irn)) {
 474                 int n_regs            = env->co->cls->n_regs;
 475                 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
 476
 477                 /* Get the costs for giving the node a specific color. */
 478                 determine_color_costs(env, ci, csts);
 479
 480                 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
 481                 csts[not_col].costs = INT_MAX;
 482
 483                 /* sort the colors according costs, cheapest first. */
 484                 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
 485
 486                 /* Try recoloring the node using the color list. */
 487                 res = recolor(env, irn, csts, parent_changed, depth);
 488         }
 489
 490         /* If we came here, everything went ok. */
 491         return res;
 492 }
 493
 494 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
 495 {
 496         co2_irn_t *ci = get_co2_irn(env, irn);
 497         col_t col     = get_col(env, irn);
 498         int res       = 0;
 499
 500         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
 501
 502         /* the node has the wanted color. That's fine, mark it as visited and return. */
 503         if (col == tgt_col) {
 504                 if (!ci->tmp_fixed) {
 505                         ci->tmp_col     = col;
 506                         ci->tmp_fixed   = 1;
 507                         list_add(&ci->changed_list, parent_changed);
 508                 }
 509
 510                 res = 1;
 511                 goto end;
 512         }
 513
 514         if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
 515                 int n_regs           = env->co->cls->n_regs;
 516                 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
 517
 518                 /* Get the costs for giving the node a specific color. */
 519                 single_color_cost(env, ci, tgt_col, seq);
 520
 521                 /* Try recoloring the node using the color list. */
 522                 res = recolor(env, irn, seq, parent_changed, depth);
 523
 524         }
 525
 526 end:
 527         DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
 528         return res;
 529 }
 530
 531 /**
 532  * Examine the costs of the current coloring concerning a MST subtree.
 533  * @param ci  The subtree root.
 534  * @param col The color of @p ci.
 535  * @return    The best coloring for that subtree under the assumption that @p ci has color @p col.
 536  */
 537 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
 538 {
 539         int *front = FRONT_BASE(ci, col);
 540         int cost   = 0;
 541         int i;
 542
 543         for (i = 0; i < ci->mst_n_childs; ++i) {
 544                 co2_cloud_irn_t *chld = ci->mst_childs[i];
 545                 col_t chld_col        = front[i];
 546
 547                 cost += examine_subtree_coloring(chld, chld_col);
 548                 cost += col != chld_col ? chld->mst_costs : 0;
 549         }
 550
 551         return cost;
 552 }
 553
 554 /**
 555  * Determine color badnesses of a node.
 556  * Badness means that it is unlikely that the node in question can
 557  * obtain a color. The higher the badness, the more unlikely it is that
 558  * the node can be assigned that color.
 559  * @param ci      The node.
 560  * @param badness An integer array as long as there are registers.
 561  * @note          The array <code>badness</code> is not cleared.
 562  */
 563 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
 564 {
 565         co2_t *env     = ci->cloud->env;
 566         co2_irn_t *ir  = &ci->inh;
 567         be_ifg_t *ifg  = env->co->cenv->ifg;
 568
 569         neighbours_iter_t it;
 570
 571         {
 572                 bitset_t const *const bs = admissible_colors(env, &ci->inh);
 573                 bitset_foreach_clear(bs, elm)
 574                         badness[elm] = ci->costs;
 575         }
 576
 577         /* Use constrained/fixed interfering neighbors to influence the color badness */
 578         be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
 579                 co2_irn_t *ni = get_co2_irn(env, irn);
 580
 581                 bitset_t const *const bs = admissible_colors(env, ni);
 582                 if (bitset_popcount(bs) == 1) {
 583                         size_t c = bitset_next_set(bs, 0);
 584                         badness[c] += ci->costs;
 585                 }
 586
 587                 else if (ni->fixed) {
 588                         col_t c = get_col(env, ni->irn);
 589                         badness[c] += ci->costs;
 590                 }
 591         }
 592         be_ifg_neighbours_break(&it);
 593 }
 594
 595 /**
 596  * Determine the badness of a MST subtree.
 597  * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
 598  * @see node_color_badness() for a definition of badness.
 599  * @param ci    The root of the subtree.
 600  * @param depth Depth for debugging purposes.
 601  */
 602 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
 603 {
 604         co2_t *env     = ci->cloud->env;
 605         int i, j;
 606
 607         node_color_badness(ci, ci->color_badness);
 608
 609         /* Collect the color badness for the whole subtree */
 610         for (i = 0; i < ci->mst_n_childs; ++i) {
 611                 co2_cloud_irn_t *child = ci->mst_childs[i];
 612                 determine_color_badness(child, depth + 1);
 613
 614                 for (j = 0; j < env->n_regs; ++j)
 615                         ci->color_badness[j] += child->color_badness[j];
 616         }
 617
 618         for (j = 0; j < env->n_regs; ++j)
 619                 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
 620 }
 621
 622 /**
 623  * Unfix all nodes in a MST subtree.
 624  */
 625 static void unfix_subtree(co2_cloud_irn_t *ci)
 626 {
 627         int i;
 628
 629         ci->inh.fixed = 0;
 630         for (i = 0; i < ci->mst_n_childs; ++i)
 631                 unfix_subtree(ci->mst_childs[i]);
 632 }
 633
 634 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 635 {
 636         co2_t *env           = ci->cloud->env;
 637         col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
 638         int is_root          = ci->mst_parent == ci;
 639         col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
 640         int min_badness      = INT_MAX;
 641         int best_col_costs   = INT_MAX;
 642         int best_col         = -1;
 643         int n_regs           = env->n_regs;
 644         int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
 645
 646         struct list_head changed;
 647         int ok, i, j;
 648
 649         for (i = 0; i < n_regs; ++i) {
 650                 int badness = ci->color_badness[i];
 651
 652                 seq[i].col   = i;
 653                 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
 654
 655                 min_badness = MIN(min_badness, badness);
 656         }
 657
 658         /* If we are not the root and the parent's color is allowed for this node give it top prio. */
 659         if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
 660                 seq[parent_col].costs = min_badness - 1;
 661
 662         /* Sort the colors. The will be processed in that ordering. */
 663         qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
 664
 665         DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
 666         INIT_LIST_HEAD(&changed);
 667         for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
 668                 col_t col    = seq[i].col;
 669                 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
 670
 671                 int subtree_costs, sum_costs;
 672
 673                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
 674
 675                 unfix_subtree(ci);
 676                 INIT_LIST_HEAD(&changed);
 677                 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
 678                 if (ok) {
 679                         materialize_coloring(&changed);
 680                         ci->inh.fixed = 1;
 681                 }
 682
 683                 else
 684                         continue;
 685
 686                 for (j = 0; j < ci->mst_n_childs; ++j) {
 687                         co2_cloud_irn_t *child = ci->mst_childs[j];
 688                         ok = coalesce_top_down(child, j, depth + 1) >= 0;
 689                         if (ok)
 690                                 child->inh.fixed = 1;
 691                         else
 692                                 break;
 693                 }
 694
 695                 /* If the subtree could not be colored, we have to try another color. */
 696                 if (!ok)
 697                         continue;
 698
 699                 subtree_costs      = examine_subtree_coloring(ci, col);
 700                 sum_costs          = subtree_costs + add_cost;
 701                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
 702
 703                 if (sum_costs < best_col_costs) {
 704                         best_col           = col;
 705                         best_col_costs     = sum_costs;
 706                         ci->col_costs[col] = subtree_costs;
 707                 }
 708
 709                 if (sum_costs == 0)
 710                         break;
 711         }
 712
 713         if (!is_root) {
 714                 int *front = FRONT_BASE(ci->mst_parent, parent_col);
 715                 front[child_nr] = best_col;
 716         }
 717
 718         return best_col;
 719 }
 720
 721 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
 722 {
 723         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
 724         int costs           = 0;
 725
 726         if (ci->cloud)
 727                 return;
 728
 729         /* mark the node as visited and add it to the cloud. */
 730         ci->cloud   = cloud;
 731         list_add(&ci->cloud_list, &cloud->members_head);
 732
 733         DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
 734
 735         /* determine the nodes costs */
 736         be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
 737         co_gs_foreach_neighb(a, n) {
 738                 costs += n->costs;
 739                 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
 740                 if (be_values_interfere(lv, a->irn, n->irn))
 741                         cloud->inevit += n->costs;
 742         }
 743
 744         /* add the node's cost to the total costs of the cloud. */
 745         ci->costs        = costs;
 746         cloud->costs    += costs;
 747         cloud->freedom  += bitset_popcount(admissible_colors(env, &ci->inh));
 748         cloud->n_memb   += 1;
 749
 750         /* If this is the heaviest node in the cloud, set it as the cloud's master. */
 751         if (costs >= curr_costs) {
 752                 curr_costs    = costs;
 753                 cloud->master = ci;
 754         }
 755
 756         /* add all the neighbors of the node to the cloud. */
 757         co_gs_foreach_neighb(a, n) {
 758                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 759                 assert(an);
 760                 populate_cloud(env, cloud, an, curr_costs);
 761         }
 762 }
 763
 764 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
 765 {
 766         co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
 767         int i;
 768
 769         DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
 770         memset(cloud, 0, sizeof(cloud[0]));
 771         INIT_LIST_HEAD(&cloud->members_head);
 772         INIT_LIST_HEAD(&cloud->list);
 773         list_add(&cloud->list, &env->cloud_head);
 774         cloud->best_costs = INT_MAX;
 775         cloud->env = env;
 776         env->visited++;
 777         populate_cloud(env, cloud, a, 0);
 778         cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
 779
 780         /* Also allocate space for the node sequence and compute that sequence. */
 781         cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
 782
 783         i = 0;
 784         list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
 785                 ci->index       = i;
 786                 cloud->seq[i++] = ci;
 787         }
 788         DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
 789
 790         return cloud;
 791 }
 792
 793 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
 794 {
 795         const ir_node *irn = ci->inh.irn;
 796         int *front   = FRONT_BASE(ci, col);
 797         int i;
 798         struct list_head changed;
 799
 800         INIT_LIST_HEAD(&changed);
 801
 802         DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
 803         change_color_single(ci->cloud->env, irn, col, &changed, depth);
 804         materialize_coloring(&changed);
 805
 806         for (i = 0; i < ci->mst_n_childs; ++i) {
 807                 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
 808         }
 809 }
 810
 811 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
 812 {
 813         while (ci != ci->mst_parent)
 814                 ci = ci->mst_parent;
 815         return ci;
 816 }
 817
 818
 819 static void process_cloud(co2_cloud_t *cloud)
 820 {
 821         co2_t *env  = cloud->env;
 822         int n_regs  = env->n_regs;
 823         int n_edges = 0;
 824         int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
 825         pdeq *q;
 826
 827         edge_t *edges;
 828         int i;
 829         int best_col;
 830
 831         /* Collect all edges in the cloud on an obstack and sort the increasingly */
 832         obstack_init(&cloud->obst);
 833         for (i = 0; i < cloud->n_memb; ++i) {
 834                 co2_cloud_irn_t *ci = cloud->seq[i];
 835
 836                 co_gs_foreach_neighb(ci->inh.aff, n) {
 837                         co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
 838                         if (ci->index < ni->index) {
 839                                 edge_t e;
 840                                 e.src   = ci;
 841                                 e.tgt   = ni;
 842                                 e.costs = n->costs;
 843                                 obstack_grow(&cloud->obst, &e, sizeof(e));
 844                                 n_edges++;
 845                         }
 846                 }
 847         }
 848         edges = (edge_t*)obstack_finish(&cloud->obst);
 849         qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
 850
 851         /* Compute the maximum spanning tree using Kruskal/Union-Find */
 852         DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
 853         for (i = 0; i < n_edges; ++i) {
 854                 edge_t *e        = &edges[i];
 855                 co2_cloud_irn_t *rs = find_mst_root(e->src);
 856                 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
 857
 858                 /* if the union/find roots are different */
 859                 if (rs != rt) {
 860                         int si = e->src->index;
 861                         int ti = e->tgt->index;
 862
 863                         /* unify the sets */
 864                         rs->mst_parent = rt;
 865                         DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
 866
 867                         /* this edge is in the MST, so set it in the bitset. */
 868                         mst_edges[si * cloud->n_memb + ti] = e->costs;
 869                         mst_edges[ti * cloud->n_memb + si] = e->costs;
 870                 }
 871         }
 872         obstack_free(&cloud->obst, edges);
 873
 874         cloud->master->mst_parent = cloud->master;
 875         cloud->mst_root = cloud->master;
 876         q = new_pdeq1(cloud->master);
 877         while (!pdeq_empty(q)) {
 878                 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
 879                 int ofs    = ci->index * cloud->n_memb;
 880                 int end    = ofs + cloud->n_memb;
 881                 int i;
 882
 883                 ci->mst_n_childs = 0;
 884                 for (i = ofs; i < end; ++i) {
 885                         if (mst_edges[i] != 0) {
 886                                 int other = i - ofs;
 887                                 co2_cloud_irn_t *child = cloud->seq[i - ofs];
 888
 889                                 /* put the child to the worklist */
 890                                 pdeq_putr(q, child);
 891
 892                                 /* make ci the parent of the child and add the child to the children array of the parent */
 893                                 child->mst_parent = ci;
 894                                 child->mst_costs  = mst_edges[i];
 895                                 ci->mst_n_childs++;
 896                                 obstack_ptr_grow(&cloud->obst, child);
 897
 898                                 mst_edges[other * cloud->n_memb + ci->index] = 0;
 899                                 mst_edges[i] = 0;
 900                         }
 901                 }
 902
 903                 obstack_ptr_grow(&cloud->obst, NULL);
 904                 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
 905         }
 906         del_pdeq(q);
 907         free(mst_edges);
 908
 909
 910         DBG((env->dbg, LEVEL_3, "mst:\n"));
 911         for (i = 0; i < cloud->n_memb; ++i) {
 912                 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
 913                 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
 914         }
 915
 916         for (i = 0; i < cloud->n_memb; ++i) {
 917                 co2_cloud_irn_t *ci = cloud->seq[i];
 918                 int n_childs = ci->mst_n_childs;
 919                 int j;
 920
 921                 ci->col_costs       = OALLOCNZ(&cloud->obst, int,             n_regs);
 922                 ci->tmp_coloring    = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
 923                 ci->fronts          = OALLOCNZ(&cloud->obst, int,             n_regs * n_childs);
 924                 ci->color_badness   = OALLOCNZ(&cloud->obst, int,             n_regs);
 925
 926                 for (j = 0; j < env->n_regs; j++)
 927                         ci->col_costs[j] = INT_MAX;
 928         }
 929
 930         determine_color_badness(cloud->mst_root, 0);
 931         best_col = coalesce_top_down(cloud->mst_root, -1, 0);
 932         unfix_subtree(cloud->mst_root);
 933         apply_coloring(cloud->mst_root, best_col, 0);
 934
 935         /* The coloring should represent the one with the best costs. */
 936         //materialize_coloring(&changed);
 937         DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
 938                 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
 939
 940         /* Fix all nodes in the cloud. */
 941         for (i = 0; i < cloud->n_memb; ++i)
 942                 cloud->seq[i]->inh.fixed = 1;
 943
 944         /* Free all space used while optimizing this cloud. */
 945         obstack_free(&cloud->obst, NULL);
 946 }
 947
 948 static int cloud_costs(co2_cloud_t *cloud)
 949 {
 950         int i, costs = 0;
 951
 952         for (i = 0; i < cloud->n_memb; ++i) {
 953                 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
 954                 col_t col = get_col(cloud->env, ci->irn);
 955                 co_gs_foreach_neighb(ci->aff, n) {
 956                         col_t n_col = get_col(cloud->env, n->irn);
 957                         costs += col != n_col ? n->costs : 0;
 958                 }
 959         }
 960
 961         return costs / 2;
 962 }
 963
 964 static void writeback_colors(co2_t *env)
 965 {
 966         co2_irn_t *irn;
 967
 968         for (irn = env->touched; irn; irn = irn->touched_next) {
 969                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
 970                 arch_set_irn_register((ir_node*)irn->irn, reg);
 971         }
 972 }
 973
 974 static void process(co2_t *env)
 975 {
 976         co2_cloud_t **clouds;
 977         int n_clouds;
 978         int i;
 979         int init_costs  = 0;
 980         int all_costs   = 0;
 981         int final_costs = 0;
 982
 983         n_clouds = 0;
 984         co_gs_foreach_aff_node(env->co, a) {
 985                 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
 986
 987                 if (!ci->cloud) {
 988                         new_cloud(env, a);
 989                         n_clouds++;
 990                 }
 991         }
 992
 993         i = 0;
 994         clouds = XMALLOCN(co2_cloud_t*, n_clouds);
 995         list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
 996                 clouds[i++] = pos;
 997         qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
 998
 999         for (i = 0; i < n_clouds; ++i) {
1000                 init_costs  += cloud_costs(clouds[i]);
1001
1002                 /* Process the cloud. */
1003                 process_cloud(clouds[i]);
1004
1005                 all_costs   += clouds[i]->costs;
1006                 final_costs += cloud_costs(clouds[i]);
1007         }
1008
1009         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1010
1011         xfree(clouds);
1012 }
1013
1014 static int co_solve_heuristic_new(copy_opt_t *co)
1015 {
1016         co2_t env;
1017
1018         ir_nodemap_init(&env.map, co->irg);
1019         obstack_init(&env.obst);
1020         env.touched     = NULL;
1021         env.visited     = 0;
1022         env.co          = co;
1023         env.n_regs      = co->cls->n_regs;
1024         env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1025         be_put_allocatable_regs(co->irg, co->cls, env.allocatable_regs);
1026         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1027         INIT_LIST_HEAD(&env.cloud_head);
1028
1029         process(&env);
1030
1031         writeback_colors(&env);
1032         obstack_free(&env.obst, NULL);
1033         ir_nodemap_destroy(&env.map);
1034         return 0;
1035 }
1036
1037 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1038 void be_init_copyheur2(void)
1039 {
1040         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1041         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1042         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1043         lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1044
1045         static co_algo_info copyheur = {
1046                 co_solve_heuristic_new, 0
1047         };
1048
1049         lc_opt_add_table(co2_grp, options);
1050         be_register_copyopt("heur2", &copyheur);
1051 }