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

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