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