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