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