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