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