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
 315         /* Set the costs to infinity for each color which is not allowed at this node. */
 316         unsigned const *const admissible = ci->admissible;
 317         rbitset_foreach_clear(admissible, n_regs, elm) {
 318                 col_costs[elm].costs  = INT_MAX;
 319         }
 320 }
 321
 322 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
 323 {
 324         int n_regs = env->co->cls->n_regs;
 325         int i;
 326
 327         for (i = 0; i < n_regs; ++i) {
 328                 seq[i].col   = i;
 329                 seq[i].costs = INT_MAX;
 330         }
 331
 332         (void) ci;
 333         assert(is_color_admissible(ci, col));
 334         seq[col].col = 0;
 335         seq[0].col   = col;
 336         seq[0].costs = 0;
 337 }
 338
 339 static void reject_coloring(struct list_head *h)
 340 {
 341         list_for_each_entry(co2_irn_t, pos, h, changed_list)
 342                 pos->tmp_fixed = 0;
 343 }
 344
 345 static void materialize_coloring(struct list_head *h)
 346 {
 347         list_for_each_entry(co2_irn_t, pos, h, changed_list) {
 348                 pos->orig_col  = pos->tmp_col;
 349                 pos->tmp_fixed = 0;
 350         }
 351 }
 352
 353 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 354
 355 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
 356 {
 357         int n_regs         = env->co->cls->n_regs;
 358         be_ifg_t *ifg      = env->co->cenv->ifg;
 359         co2_irn_t *ci      = get_co2_irn(env, irn);
 360         int res            = 0;
 361
 362         int i;
 363
 364         if (depth >= max_depth)
 365           return 0;
 366
 367         for (i = 0; i < n_regs; ++i) {
 368                 col_t tgt_col  = col_list[i].col;
 369                 unsigned costs = col_list[i].costs;
 370                 int neigh_ok   = 1;
 371
 372                 struct list_head changed;
 373                 neighbours_iter_t it;
 374
 375                 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
 376
 377                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 378                 if (INFEASIBLE(costs)) {
 379                         DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
 380                         ci->tmp_fixed = 0;
 381                         return 0;
 382                 }
 383
 384                 /* Set the new color of the node and mark the node as temporarily fixed. */
 385                 ci->tmp_col     = tgt_col;
 386                 ci->tmp_fixed   = 1;
 387
 388                 /*
 389                 If that color has costs > 0, there's at least one neighbor having that color,
 390                 so we will try to change the neighbors' colors, too.
 391                 */
 392                 INIT_LIST_HEAD(&changed);
 393                 list_add(&ci->changed_list, &changed);
 394
 395                 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
 396
 397                         /* try to re-color the neighbor if it has the target color. */
 398                         if (get_col(env, n) == tgt_col) {
 399                                 struct list_head tmp;
 400
 401                                 /*
 402                                 Try to change the color of the neighbor and record all nodes which
 403                                 get changed in the tmp list. Add this list to the "changed" list for
 404                                 that color. If we did not succeed to change the color of the neighbor,
 405                                 we bail out and try the next color.
 406                                 */
 407                                 INIT_LIST_HEAD(&tmp);
 408                                 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
 409                                 list_splice(&tmp, &changed);
 410                                 if (!neigh_ok) {
 411                                         be_ifg_neighbours_break(&it);
 412                                         break;
 413                                 }
 414                         }
 415                 }
 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 }
 576
 577 /**
 578  * Determine the badness of a MST subtree.
 579  * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
 580  * @see node_color_badness() for a definition of badness.
 581  * @param ci    The root of the subtree.
 582  * @param depth Depth for debugging purposes.
 583  */
 584 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
 585 {
 586         co2_t *env     = ci->cloud->env;
 587         int i, j;
 588
 589         node_color_badness(ci, ci->color_badness);
 590
 591         /* Collect the color badness for the whole subtree */
 592         for (i = 0; i < ci->mst_n_childs; ++i) {
 593                 co2_cloud_irn_t *child = ci->mst_childs[i];
 594                 determine_color_badness(child, depth + 1);
 595
 596                 for (j = 0; j < env->n_regs; ++j)
 597                         ci->color_badness[j] += child->color_badness[j];
 598         }
 599
 600         for (j = 0; j < env->n_regs; ++j)
 601                 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
 602 }
 603
 604 /**
 605  * Unfix all nodes in a MST subtree.
 606  */
 607 static void unfix_subtree(co2_cloud_irn_t *ci)
 608 {
 609         int i;
 610
 611         ci->inh.fixed = 0;
 612         for (i = 0; i < ci->mst_n_childs; ++i)
 613                 unfix_subtree(ci->mst_childs[i]);
 614 }
 615
 616 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 617 {
 618         co2_t *env           = ci->cloud->env;
 619         col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
 620         int is_root          = ci->mst_parent == ci;
 621         col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
 622         int min_badness      = INT_MAX;
 623         int best_col_costs   = INT_MAX;
 624         int best_col         = -1;
 625         int n_regs           = env->n_regs;
 626         int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
 627
 628         struct list_head changed;
 629         int ok, i, j;
 630
 631         for (i = 0; i < n_regs; ++i) {
 632                 int badness = ci->color_badness[i];
 633
 634                 seq[i].col   = i;
 635                 seq[i].costs = is_color_admissible(&ci->inh, i) ? badness : INT_MAX;
 636
 637                 min_badness = MIN(min_badness, badness);
 638         }
 639
 640         /* If we are not the root and the parent's color is allowed for this node give it top prio. */
 641         if (!is_root && is_color_admissible(&ci->inh, parent_col))
 642                 seq[parent_col].costs = min_badness - 1;
 643
 644         /* Sort the colors. The will be processed in that ordering. */
 645         qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
 646
 647         DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
 648         INIT_LIST_HEAD(&changed);
 649         for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
 650                 col_t col    = seq[i].col;
 651                 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
 652
 653                 int subtree_costs, sum_costs;
 654
 655                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
 656
 657                 unfix_subtree(ci);
 658                 INIT_LIST_HEAD(&changed);
 659                 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
 660                 if (ok) {
 661                         materialize_coloring(&changed);
 662                         ci->inh.fixed = 1;
 663                 }
 664
 665                 else
 666                         continue;
 667
 668                 for (j = 0; j < ci->mst_n_childs; ++j) {
 669                         co2_cloud_irn_t *child = ci->mst_childs[j];
 670                         ok = coalesce_top_down(child, j, depth + 1) >= 0;
 671                         if (ok)
 672                                 child->inh.fixed = 1;
 673                         else
 674                                 break;
 675                 }
 676
 677                 /* If the subtree could not be colored, we have to try another color. */
 678                 if (!ok)
 679                         continue;
 680
 681                 subtree_costs      = examine_subtree_coloring(ci, col);
 682                 sum_costs          = subtree_costs + add_cost;
 683                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
 684
 685                 if (sum_costs < best_col_costs) {
 686                         best_col           = col;
 687                         best_col_costs     = sum_costs;
 688                         ci->col_costs[col] = subtree_costs;
 689                 }
 690
 691                 if (sum_costs == 0)
 692                         break;
 693         }
 694
 695         if (!is_root) {
 696                 int *front = FRONT_BASE(ci->mst_parent, parent_col);
 697                 front[child_nr] = best_col;
 698         }
 699
 700         return best_col;
 701 }
 702
 703 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
 704 {
 705         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
 706         int costs           = 0;
 707
 708         if (ci->cloud)
 709                 return;
 710
 711         /* mark the node as visited and add it to the cloud. */
 712         ci->cloud   = cloud;
 713         list_add(&ci->cloud_list, &cloud->members_head);
 714
 715         DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
 716
 717         /* determine the nodes costs */
 718         be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
 719         co_gs_foreach_neighb(a, n) {
 720                 costs += n->costs;
 721                 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
 722                 if (be_values_interfere(lv, a->irn, n->irn))
 723                         cloud->inevit += n->costs;
 724         }
 725
 726         /* add the node's cost to the total costs of the cloud. */
 727         ci->costs        = costs;
 728         cloud->costs    += costs;
 729         cloud->freedom  += rbitset_popcount(ci->inh.admissible, env->n_regs);
 730         cloud->n_memb   += 1;
 731
 732         /* If this is the heaviest node in the cloud, set it as the cloud's master. */
 733         if (costs >= curr_costs) {
 734                 curr_costs    = costs;
 735                 cloud->master = ci;
 736         }
 737
 738         /* add all the neighbors of the node to the cloud. */
 739         co_gs_foreach_neighb(a, n) {
 740                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 741                 assert(an);
 742                 populate_cloud(env, cloud, an, curr_costs);
 743         }
 744 }
 745
 746 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
 747 {
 748         co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
 749         int i;
 750
 751         DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
 752         memset(cloud, 0, sizeof(cloud[0]));
 753         INIT_LIST_HEAD(&cloud->members_head);
 754         INIT_LIST_HEAD(&cloud->list);
 755         list_add(&cloud->list, &env->cloud_head);
 756         cloud->best_costs = INT_MAX;
 757         cloud->env = env;
 758         env->visited++;
 759         populate_cloud(env, cloud, a, 0);
 760         cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
 761
 762         /* Also allocate space for the node sequence and compute that sequence. */
 763         cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
 764
 765         i = 0;
 766         list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
 767                 ci->index       = i;
 768                 cloud->seq[i++] = ci;
 769         }
 770         DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
 771
 772         return cloud;
 773 }
 774
 775 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
 776 {
 777         const ir_node *irn = ci->inh.irn;
 778         int *front   = FRONT_BASE(ci, col);
 779         int i;
 780         struct list_head changed;
 781
 782         INIT_LIST_HEAD(&changed);
 783
 784         DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
 785         change_color_single(ci->cloud->env, irn, col, &changed, depth);
 786         materialize_coloring(&changed);
 787
 788         for (i = 0; i < ci->mst_n_childs; ++i) {
 789                 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
 790         }
 791 }
 792
 793 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
 794 {
 795         while (ci != ci->mst_parent)
 796                 ci = ci->mst_parent;
 797         return ci;
 798 }
 799
 800
 801 static void process_cloud(co2_cloud_t *cloud)
 802 {
 803         co2_t *env  = cloud->env;
 804         int n_regs  = env->n_regs;
 805         int n_edges = 0;
 806         int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
 807         pdeq *q;
 808
 809         edge_t *edges;
 810         int i;
 811         int best_col;
 812
 813         /* Collect all edges in the cloud on an obstack and sort the increasingly */
 814         obstack_init(&cloud->obst);
 815         for (i = 0; i < cloud->n_memb; ++i) {
 816                 co2_cloud_irn_t *ci = cloud->seq[i];
 817
 818                 co_gs_foreach_neighb(ci->inh.aff, n) {
 819                         co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
 820                         if (ci->index < ni->index) {
 821                                 edge_t e;
 822                                 e.src   = ci;
 823                                 e.tgt   = ni;
 824                                 e.costs = n->costs;
 825                                 obstack_grow(&cloud->obst, &e, sizeof(e));
 826                                 n_edges++;
 827                         }
 828                 }
 829         }
 830         edges = (edge_t*)obstack_finish(&cloud->obst);
 831         qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
 832
 833         /* Compute the maximum spanning tree using Kruskal/Union-Find */
 834         DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
 835         for (i = 0; i < n_edges; ++i) {
 836                 edge_t *e        = &edges[i];
 837                 co2_cloud_irn_t *rs = find_mst_root(e->src);
 838                 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
 839
 840                 /* if the union/find roots are different */
 841                 if (rs != rt) {
 842                         int si = e->src->index;
 843                         int ti = e->tgt->index;
 844
 845                         /* unify the sets */
 846                         rs->mst_parent = rt;
 847                         DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
 848
 849                         /* this edge is in the MST, so set it in the bitset. */
 850                         mst_edges[si * cloud->n_memb + ti] = e->costs;
 851                         mst_edges[ti * cloud->n_memb + si] = e->costs;
 852                 }
 853         }
 854         obstack_free(&cloud->obst, edges);
 855
 856         cloud->master->mst_parent = cloud->master;
 857         cloud->mst_root = cloud->master;
 858         q = new_pdeq1(cloud->master);
 859         while (!pdeq_empty(q)) {
 860                 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
 861                 int ofs    = ci->index * cloud->n_memb;
 862                 int end    = ofs + cloud->n_memb;
 863                 int i;
 864
 865                 ci->mst_n_childs = 0;
 866                 for (i = ofs; i < end; ++i) {
 867                         if (mst_edges[i] != 0) {
 868                                 int other = i - ofs;
 869                                 co2_cloud_irn_t *child = cloud->seq[i - ofs];
 870
 871                                 /* put the child to the worklist */
 872                                 pdeq_putr(q, child);
 873
 874                                 /* make ci the parent of the child and add the child to the children array of the parent */
 875                                 child->mst_parent = ci;
 876                                 child->mst_costs  = mst_edges[i];
 877                                 ci->mst_n_childs++;
 878                                 obstack_ptr_grow(&cloud->obst, child);
 879
 880                                 mst_edges[other * cloud->n_memb + ci->index] = 0;
 881                                 mst_edges[i] = 0;
 882                         }
 883                 }
 884
 885                 obstack_ptr_grow(&cloud->obst, NULL);
 886                 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
 887         }
 888         del_pdeq(q);
 889         free(mst_edges);
 890
 891
 892         DBG((env->dbg, LEVEL_3, "mst:\n"));
 893         for (i = 0; i < cloud->n_memb; ++i) {
 894                 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
 895                 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
 896         }
 897
 898         for (i = 0; i < cloud->n_memb; ++i) {
 899                 co2_cloud_irn_t *ci = cloud->seq[i];
 900                 int n_childs = ci->mst_n_childs;
 901                 int j;
 902
 903                 ci->col_costs       = OALLOCNZ(&cloud->obst, int,             n_regs);
 904                 ci->tmp_coloring    = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
 905                 ci->fronts          = OALLOCNZ(&cloud->obst, int,             n_regs * n_childs);
 906                 ci->color_badness   = OALLOCNZ(&cloud->obst, int,             n_regs);
 907
 908                 for (j = 0; j < env->n_regs; j++)
 909                         ci->col_costs[j] = INT_MAX;
 910         }
 911
 912         determine_color_badness(cloud->mst_root, 0);
 913         best_col = coalesce_top_down(cloud->mst_root, -1, 0);
 914         unfix_subtree(cloud->mst_root);
 915         apply_coloring(cloud->mst_root, best_col, 0);
 916
 917         /* The coloring should represent the one with the best costs. */
 918         //materialize_coloring(&changed);
 919         DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
 920                 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
 921
 922         /* Fix all nodes in the cloud. */
 923         for (i = 0; i < cloud->n_memb; ++i)
 924                 cloud->seq[i]->inh.fixed = 1;
 925
 926         /* Free all space used while optimizing this cloud. */
 927         obstack_free(&cloud->obst, NULL);
 928 }
 929
 930 static int cloud_costs(co2_cloud_t *cloud)
 931 {
 932         int i, costs = 0;
 933
 934         for (i = 0; i < cloud->n_memb; ++i) {
 935                 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
 936                 col_t col = get_col(cloud->env, ci->irn);
 937                 co_gs_foreach_neighb(ci->aff, n) {
 938                         col_t n_col = get_col(cloud->env, n->irn);
 939                         costs += col != n_col ? n->costs : 0;
 940                 }
 941         }
 942
 943         return costs / 2;
 944 }
 945
 946 static void writeback_colors(co2_t *env)
 947 {
 948         co2_irn_t *irn;
 949
 950         for (irn = env->touched; irn; irn = irn->touched_next) {
 951                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
 952                 arch_set_irn_register((ir_node*)irn->irn, reg);
 953         }
 954 }
 955
 956 static void process(co2_t *env)
 957 {
 958         co2_cloud_t **clouds;
 959         int n_clouds;
 960         int i;
 961         int init_costs  = 0;
 962         int all_costs   = 0;
 963         int final_costs = 0;
 964
 965         n_clouds = 0;
 966         co_gs_foreach_aff_node(env->co, a) {
 967                 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
 968
 969                 if (!ci->cloud) {
 970                         new_cloud(env, a);
 971                         n_clouds++;
 972                 }
 973         }
 974
 975         i = 0;
 976         clouds = XMALLOCN(co2_cloud_t*, n_clouds);
 977         list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
 978                 clouds[i++] = pos;
 979         qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
 980
 981         for (i = 0; i < n_clouds; ++i) {
 982                 init_costs  += cloud_costs(clouds[i]);
 983
 984                 /* Process the cloud. */
 985                 process_cloud(clouds[i]);
 986
 987                 all_costs   += clouds[i]->costs;
 988                 final_costs += cloud_costs(clouds[i]);
 989         }
 990
 991         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
 992
 993         xfree(clouds);
 994 }
 995
 996 static int co_solve_heuristic_new(copy_opt_t *co)
 997 {
 998         co2_t env;
 999
1000         ir_nodemap_init(&env.map, co->irg);
1001         obstack_init(&env.obst);
1002         env.touched          = NULL;
1003         env.visited          = 0;
1004         env.co               = co;
1005         env.n_regs           = co->cls->n_regs;
1006         env.allocatable_regs = co->cenv->allocatable_regs->data;
1007         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1008         INIT_LIST_HEAD(&env.cloud_head);
1009
1010         process(&env);
1011
1012         writeback_colors(&env);
1013         obstack_free(&env.obst, NULL);
1014         ir_nodemap_destroy(&env.map);
1015         return 0;
1016 }
1017
1018 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1019 void be_init_copyheur2(void)
1020 {
1021         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1022         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1023         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1024         lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1025
1026         static co_algo_info copyheur = {
1027                 co_solve_heuristic_new, 0
1028         };
1029
1030         lc_opt_add_table(co2_grp, options);
1031         be_register_copyopt("heur2", &copyheur);
1032 }