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

   1
   2 /**
   3  * More experiments on coalescing.
   4  * @author Sebastian Hack
   5  * @date   14.04.2006
   6  */
   7
   8 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #ifdef WITH_LIBCORE
  13 #include <libcore/lc_opts.h>
  14 #include <libcore/lc_opts_enum.h>
  15 #endif /* WITH_LIBCORE */
  16
  17 #include <stdlib.h>
  18 #include <limits.h>
  19
  20 #include "list.h"
  21 #include "pdeq.h"
  22 #include "bitset.h"
  23
  24 #include "debug.h"
  25 #include "bitfiddle.h"
  26
  27 #include "irphase_t.h"
  28 #include "irgraph_t.h"
  29 #include "irnode_t.h"
  30 #include "irprintf.h"
  31 #include "irtools.h"
  32
  33 #include "bemodule.h"
  34 #include "beabi.h"
  35 #include "benode_t.h"
  36 #include "becopyopt.h"
  37 #include "becopyopt_t.h"
  38 #include "bechordal_t.h"
  39
  40 #define DUMP_BEFORE 1
  41 #define DUMP_AFTER  2
  42 #define DUMP_CLOUD  4
  43 #define DUMP_ALL    2 * DUMP_CLOUD - 1
  44
  45 static unsigned dump_flags      = 0;
  46 static int      subtree_iter    = 4;
  47 static int      max_depth       = 20;
  48 static double   constr_factor   = 0.9;
  49
  50 /* Options using libcore */
  51 #ifdef WITH_LIBCORE
  52
  53 static const lc_opt_enum_mask_items_t dump_items[] = {
  54         { "before",  DUMP_BEFORE },
  55         { "after",   DUMP_AFTER  },
  56         { "cloud",   DUMP_CLOUD  },
  57         { "all",     DUMP_ALL    },
  58         { NULL,      0 }
  59 };
  60
  61 static lc_opt_enum_mask_var_t dump_var = {
  62         &dump_flags, dump_items
  63 };
  64
  65 static const lc_opt_table_entry_t options[] = {
  66         LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                                         &dump_var),
  67         LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes",                           &subtree_iter),
  68         LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
  69         LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
  70         { NULL }
  71 };
  72
  73 void be_init_copyheur2(void)
  74 {
  75         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
  76         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
  77         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
  78         lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
  79
  80         lc_opt_add_table(co2_grp, options);
  81 }
  82
  83 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
  84 #endif
  85
  86 /*
  87   ____  _             _
  88  / ___|| |_ __ _ _ __| |_
  89  \___ \| __/ _` | '__| __|
  90   ___) | || (_| | |  | |_
  91  |____/ \__\__,_|_|   \__|
  92
  93 */
  94
  95 #define INFEASIBLE(cost) ((cost) == INT_MAX)
  96
  97 static be_ifg_dump_dot_cb_t ifg_dot_cb;
  98
  99 typedef unsigned col_t;
 100
 101 typedef struct _co2_irn_t       co2_irn_t;
 102 typedef struct _co2_cloud_t     co2_cloud_t;
 103 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
 104
 105 typedef struct {
 106         col_t col;
 107         int costs;
 108 } col_cost_pair_t;
 109
 110 typedef struct {
 111         phase_t     ph;
 112         copy_opt_t *co;
 113         bitset_t   *ignore_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         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 #define get_co2_irn(co2, irn)         ((co2_irn_t *)       phase_get_or_set_irn_data(&co2->ph, irn))
 180 #define get_co2_cloud_irn(co2, irn)   ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
 181
 182 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
 183 {
 184         co2_t *env         = (co2_t *) ph;
 185         affinity_node_t *a = get_affinity_info(env->co, irn);
 186         size_t size        = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
 187         co2_irn_t *ci      = data ? data : phase_alloc(ph, size);
 188
 189         memset(ci, 0, size);
 190         INIT_LIST_HEAD(&ci->changed_list);
 191         ci->touched_next = env->touched;
 192         ci->orig_col     = get_irn_col(env->co, irn);
 193         env->touched     = ci;
 194         ci->irn          = irn;
 195         ci->aff          = a;
 196
 197         if(a) {
 198                 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
 199                 INIT_LIST_HEAD(&cci->cloud_list);
 200                 cci->mst_parent   = cci;
 201         }
 202
 203         return ci;
 204 }
 205
 206 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
 207
 208 static int cmp_clouds_gt(const void *a, const void *b)
 209 {
 210         const co2_cloud_t * const *p = a;
 211         const co2_cloud_t * const *q = b;
 212         double c = CLOUD_WEIGHT(*p);
 213         double d = CLOUD_WEIGHT(*q);
 214         return QSORT_CMP(d, c);
 215 }
 216
 217 /**
 218  * An order on color/costs pairs.
 219  * If the costs are equal, we use the color as a kind of normalization.
 220  */
 221 static int col_cost_pair_lt(const void *a, const void *b)
 222 {
 223         const col_cost_pair_t *p = a;
 224         const col_cost_pair_t *q = b;
 225         int c = p->costs;
 226         int d = q->costs;
 227         return QSORT_CMP(c, d);
 228 }
 229
 230 int cmp_edges(const void *a, const void *b)
 231 {
 232         const edge_t *p = a;
 233         const edge_t *q = b;
 234         return QSORT_CMP(q->costs, p->costs);
 235 }
 236
 237 static col_t get_col(co2_t *env, ir_node *irn)
 238 {
 239         co2_irn_t *ci = get_co2_irn(env, irn);
 240         return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
 241 }
 242
 243 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
 244 {
 245         co2_irn_t *ci = get_co2_irn(env, irn);
 246         return ci->fixed || ci->tmp_fixed;
 247 }
 248
 249 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
 250 {
 251         if(!ci->adm_cache) {
 252                 arch_register_req_t req;
 253                 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
 254                 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
 255                 if(arch_register_req_is(&req, limited)) {
 256                         req.limited(req.limited_env, ci->adm_cache);
 257                         ci->is_constrained = 1;
 258                 }
 259                 else {
 260                         bitset_copy(ci->adm_cache, env->ignore_regs);
 261                         bitset_flip_all(ci->adm_cache);
 262                 }
 263         }
 264
 265         return ci->adm_cache;
 266 }
 267
 268 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
 269 {
 270         bitset_copy(bs, get_adm(env, ci));
 271         return bs;
 272 }
 273
 274 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
 275 {
 276         bitset_t *bs = get_adm(env, ci);
 277         return bitset_is_set(bs, col);
 278 }
 279
 280 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
 281 {
 282         if(!ci->adm_cache)
 283                 get_adm(env, ci);
 284         return ci->is_constrained;
 285 }
 286
 287 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
 288 {
 289         bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
 290         arch_register_req_t req;
 291
 292         arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
 293
 294         if(arch_register_req_is(&req, limited)) {
 295                 bitset_pos_t elm;
 296                 int n_constr;
 297
 298                 req.limited(req.limited_env, aux);
 299                 n_constr = bitset_popcnt(aux);
 300                 bitset_foreach(aux, elm) {
 301                         col_costs[elm].costs  = add_saturated(col_costs[elm].costs, costs / n_constr);
 302                 }
 303         }
 304 }
 305
 306 /**
 307  * Determine costs which shall indicate how cheap/expensive it is to try
 308  * to assign a node some color.
 309  * The costs are computed for all colors. INT_MAX means that it is impossible
 310  * to give the node that specific color.
 311  *
 312  * @param env       The co2 this pointer.
 313  * @param irn       The node.
 314  * @param col_costs An array of colors x costs where the costs are written to.
 315  */
 316 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
 317 {
 318         ir_node *irn       = ci->irn;
 319         be_ifg_t *ifg      = env->co->cenv->ifg;
 320         int n_regs         = env->co->cls->n_regs;
 321         bitset_t *forb     = bitset_alloca(n_regs);
 322         affinity_node_t *a = ci->aff;
 323
 324         bitset_pos_t elm;
 325         ir_node *pos;
 326         void *it;
 327         int i;
 328
 329         /* Put all forbidden colors into the aux bitset. */
 330         admissible_colors(env, ci, forb);
 331         bitset_flip_all(forb);
 332
 333         for(i = 0; i < n_regs; ++i) {
 334                 col_costs[i].col   = i;
 335                 col_costs[i].costs = 0;
 336         }
 337
 338         if(a) {
 339                 neighb_t *n;
 340
 341                 co_gs_foreach_neighb(a, n) {
 342                         if(color_is_fix(env, n->irn)) {
 343                                 col_t col = get_col(env, n->irn);
 344                                 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
 345                         }
 346
 347                         incur_constraint_costs(env, n->irn, col_costs, -n->costs);
 348                 }
 349         }
 350
 351         it = be_ifg_neighbours_iter_alloca(ifg);
 352         be_ifg_foreach_neighbour(ifg, it, irn, pos) {
 353                 col_t col = get_col(env, pos);
 354                 if(color_is_fix(env, pos)) {
 355                         col_costs[col].costs  = INT_MAX;
 356                 }
 357                 else {
 358                         incur_constraint_costs(env, pos, col_costs, INT_MAX);
 359                         col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
 360                 }
 361         }
 362         be_ifg_neighbours_break(ifg, it);
 363
 364         /* Set the costs to infinity for each color which is not allowed at this node. */
 365         bitset_foreach(forb, elm) {
 366                 col_costs[elm].costs  = INT_MAX;
 367         }
 368
 369 }
 370
 371 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
 372 {
 373         int n_regs = env->co->cls->n_regs;
 374         int i;
 375
 376         for(i = 0; i < n_regs; ++i) {
 377                 seq[i].col   = i;
 378                 seq[i].costs = INT_MAX;
 379         }
 380
 381         assert(is_color_admissible(env, ci, col));
 382         seq[col].col = 0;
 383         seq[0].col   = col;
 384         seq[0].costs = 0;
 385 }
 386
 387 static void reject_coloring(struct list_head *h)
 388 {
 389         co2_irn_t *pos;
 390
 391         list_for_each_entry(co2_irn_t, pos, h, changed_list)
 392                 pos->tmp_fixed = 0;
 393 }
 394
 395 static void materialize_coloring(struct list_head *h)
 396 {
 397         co2_irn_t *pos;
 398
 399         list_for_each_entry(co2_irn_t, pos, h, changed_list) {
 400                 pos->orig_col  = pos->tmp_col;
 401                 pos->tmp_fixed = 0;
 402         }
 403 }
 404
 405 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 406
 407 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
 408 {
 409         int n_regs         = env->co->cls->n_regs;
 410         be_ifg_t *ifg      = env->co->cenv->ifg;
 411         co2_irn_t *ci      = get_co2_irn(env, irn);
 412         int res            = 0;
 413
 414         int i;
 415
 416         if(depth >= max_depth)
 417           return 0;
 418
 419         for(i = 0; i < n_regs; ++i) {
 420                 col_t tgt_col  = col_list[i].col;
 421                 unsigned costs = col_list[i].costs;
 422                 int neigh_ok   = 1;
 423
 424                 struct list_head changed;
 425                 ir_node *n;
 426                 void *it;
 427
 428                 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
 429
 430                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 431                 if(INFEASIBLE(costs)) {
 432                         DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
 433                         ci->tmp_fixed = 0;
 434                         return 0;
 435                 }
 436
 437                 /* Set the new color of the node and mark the node as temporarily fixed. */
 438                 ci->tmp_col     = tgt_col;
 439                 ci->tmp_fixed   = 1;
 440
 441                 /*
 442                 If that color has costs > 0, there's at least one neighbor having that color,
 443                 so we will try to change the neighbors' colors, too.
 444                 */
 445                 INIT_LIST_HEAD(&changed);
 446                 list_add(&ci->changed_list, &changed);
 447
 448                 it = be_ifg_neighbours_iter_alloca(ifg);
 449                 be_ifg_foreach_neighbour(ifg, it, irn, n) {
 450
 451                         /* try to re-color the neighbor if it has the target color. */
 452                         if(get_col(env, n) == tgt_col) {
 453                                 struct list_head tmp;
 454
 455                                 /*
 456                                 Try to change the color of the neighbor and record all nodes which
 457                                 get changed in the tmp list. Add this list to the "changed" list for
 458                                 that color. If we did not succeed to change the color of the neighbor,
 459                                 we bail out and try the next color.
 460                                 */
 461                                 INIT_LIST_HEAD(&tmp);
 462                                 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
 463                                 list_splice(&tmp, &changed);
 464                                 if(!neigh_ok)
 465                                         break;
 466                         }
 467                 }
 468                 be_ifg_neighbours_break(ifg, it);
 469
 470                 /*
 471                 We managed to assign the target color to all neighbors, so from the perspective
 472                 of the current node, every thing was ok and we can return safely.
 473                 */
 474                 if(neigh_ok) {
 475                         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
 476                         list_splice(&changed, parent_changed);
 477                         res = 1;
 478                         break;
 479                 }
 480
 481                 /*
 482                 If not, that color did not succeed and we unfix all nodes we touched
 483                 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
 484                 */
 485                 else
 486                         reject_coloring(&changed);
 487         }
 488
 489         return res;
 490 }
 491
 492 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
 493 {
 494         co2_irn_t *ci = get_co2_irn(env, irn);
 495         int res       = 0;
 496         col_t col     = get_col(env, irn);
 497
 498         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
 499
 500         /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
 501         if(col != not_col) {
 502                 if(!ci->tmp_fixed) {
 503                         ci->tmp_col     = col;
 504                         ci->tmp_fixed   = 1;
 505                 }
 506
 507                 list_add(&ci->changed_list, parent_changed);
 508                 return 1;
 509         }
 510
 511         /* The node has the color it should not have _and_ has not been visited yet. */
 512         if(!color_is_fix(env, irn)) {
 513                 int n_regs            = env->co->cls->n_regs;
 514                 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
 515
 516                 /* Get the costs for giving the node a specific color. */
 517                 determine_color_costs(env, ci, csts);
 518
 519                 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
 520                 csts[not_col].costs = INT_MAX;
 521
 522                 /* sort the colors according costs, cheapest first. */
 523                 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
 524
 525                 /* Try recoloring the node using the color list. */
 526                 res = recolor(env, irn, csts, parent_changed, depth);
 527         }
 528
 529         /* If we came here, everything went ok. */
 530         return res;
 531 }
 532
 533 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
 534 {
 535         co2_irn_t *ci = get_co2_irn(env, irn);
 536         col_t col     = get_col(env, irn);
 537         int res       = 0;
 538
 539         DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
 540
 541         /* the node has the wanted color. That's fine, mark it as visited and return. */
 542         if(col == tgt_col) {
 543                 if(!ci->tmp_fixed) {
 544                         ci->tmp_col     = col;
 545                         ci->tmp_fixed   = 1;
 546                         list_add(&ci->changed_list, parent_changed);
 547                 }
 548
 549                 res = 1;
 550                 goto end;
 551         }
 552
 553         if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
 554                 int n_regs           = env->co->cls->n_regs;
 555                 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
 556
 557                 /* Get the costs for giving the node a specific color. */
 558                 single_color_cost(env, ci, tgt_col, seq);
 559
 560                 /* Try recoloring the node using the color list. */
 561                 res = recolor(env, irn, seq, parent_changed, depth);
 562
 563         }
 564
 565 end:
 566         DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
 567         return res;
 568 }
 569
 570 /**
 571  * Examine the costs of the current coloring concerning a MST subtree.
 572  * @param ci  The subtree root.
 573  * @param col The color of @p ci.
 574  * @return    The best coloring for that subtree under the assumption that @p ci has color @p col.
 575  */
 576 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
 577 {
 578         int *front = FRONT_BASE(ci, col);
 579         int cost   = 0;
 580         int i;
 581
 582         for(i = 0; i < ci->mst_n_childs; ++i) {
 583                 co2_cloud_irn_t *chld = ci->mst_childs[i];
 584                 col_t chld_col        = front[i];
 585
 586                 cost += examine_subtree_coloring(chld, chld_col);
 587                 cost += col != chld_col ? chld->mst_costs : 0;
 588         }
 589
 590         return cost;
 591 }
 592
 593 /**
 594  * Determine color badnesses of a node.
 595  * Badness means that it is unlikely that the node in question can
 596  * obtain a color. The higher the badness, the more unlikely it is that
 597  * the node can be assigned that color.
 598  * @param ci      The node.
 599  * @param badness An integer array as long as there are registers.
 600  * @note          The array <code>badness</code> is not cleared.
 601  */
 602 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
 603 {
 604         co2_t *env     = ci->cloud->env;
 605         co2_irn_t *ir  = &ci->inh;
 606         int n_regs     = env->n_regs;
 607         be_ifg_t *ifg  = env->co->cenv->ifg;
 608         bitset_t *bs   = bitset_alloca(n_regs);
 609
 610         bitset_pos_t elm;
 611         ir_node *irn;
 612         void *it;
 613
 614         admissible_colors(env, &ci->inh, bs);
 615         bitset_flip_all(bs);
 616         bitset_foreach(bs, elm)
 617                 badness[elm] = ci->costs;
 618
 619         /* Use constrained/fixed interfering neighbors to influence the color badness */
 620         it = be_ifg_neighbours_iter_alloca(ifg);
 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_popcnt(bs) == 1) {
 626                         bitset_pos_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(ifg, 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 = alloca(env->n_regs * sizeof(seq[0]));
 681         int is_root          = ci->mst_parent == ci;
 682         col_t parent_col     = is_root ? -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         neighb_t *n;
 770
 771         if(ci->cloud)
 772                 return;
 773
 774         /* mark the node as visited and add it to the cloud. */
 775         ci->cloud   = cloud;
 776         list_add(&ci->cloud_list, &cloud->members_head);
 777
 778         DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
 779
 780         /* determine the nodes costs */
 781         co_gs_foreach_neighb(a, n) {
 782                 costs += n->costs;
 783                 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
 784                 if(be_ifg_connected(ifg, a->irn, n->irn))
 785                         cloud->inevit += n->costs;
 786         }
 787
 788         /* add the node's cost to the total costs of the cloud. */
 789         ci->costs          = costs;
 790         cloud->costs      += costs;
 791         cloud->n_constr   += is_constrained(env, &ci->inh);
 792         cloud->freedom    += bitset_popcnt(get_adm(env, &ci->inh));
 793         cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
 794         cloud->n_memb++;
 795
 796         /* If this is the heaviest node in the cloud, set it as the cloud's master. */
 797         if(costs >= curr_costs) {
 798                 curr_costs    = costs;
 799                 cloud->master = ci;
 800         }
 801
 802         /* add all the neighbors of the node to the cloud. */
 803         co_gs_foreach_neighb(a, n) {
 804                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 805                 assert(an);
 806                 populate_cloud(env, cloud, an, curr_costs);
 807         }
 808 }
 809
 810 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
 811 {
 812         co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
 813         co2_cloud_irn_t *ci;
 814         int i;
 815
 816         DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
 817         memset(cloud, 0, sizeof(cloud[0]));
 818         INIT_LIST_HEAD(&cloud->members_head);
 819         INIT_LIST_HEAD(&cloud->list);
 820         list_add(&cloud->list, &env->cloud_head);
 821         cloud->best_costs = INT_MAX;
 822         cloud->env = env;
 823         env->visited++;
 824         populate_cloud(env, cloud, a, 0);
 825         cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
 826
 827         /* Also allocate space for the node sequence and compute that sequence. */
 828         cloud->seq    = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
 829
 830         i = 0;
 831         list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
 832                 ci->index       = i;
 833                 cloud->seq[i++] = ci;
 834         }
 835         DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
 836
 837         return cloud;
 838 }
 839
 840 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
 841 {
 842         ir_node *irn = ci->inh.irn;
 843         int *front   = FRONT_BASE(ci, col);
 844         int i, ok;
 845         struct list_head changed;
 846
 847         INIT_LIST_HEAD(&changed);
 848
 849         DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
 850         ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
 851         // assert(ok && "Color changing may not fail while committing the coloring");
 852         materialize_coloring(&changed);
 853
 854         for(i = 0; i < ci->mst_n_childs; ++i) {
 855                 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
 856         }
 857 }
 858
 859 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
 860 {
 861         while(ci != ci->mst_parent)
 862                 ci = ci->mst_parent;
 863         return ci;
 864 }
 865
 866
 867 static void process_cloud(co2_cloud_t *cloud)
 868 {
 869         co2_t *env  = cloud->env;
 870         int n_regs  = env->n_regs;
 871         int n_edges = 0;
 872         int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
 873         pdeq *q;
 874
 875         edge_t *edges;
 876         int i;
 877         int best_col;
 878
 879         memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
 880
 881         /* Collect all edges in the cloud on an obstack and sort the increasingly */
 882         obstack_init(&cloud->obst);
 883         for(i = 0; i < cloud->n_memb; ++i) {
 884                 co2_cloud_irn_t *ci = cloud->seq[i];
 885                 neighb_t *n;
 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 = 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 = 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 = 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       = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
 973                 ci->tmp_coloring    = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
 974                 ci->fronts          = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
 975                 ci->color_badness   = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
 976                 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
 977                 memset(ci->col_costs,     0, n_regs * sizeof(ci->col_costs[0]));
 978                 memset(ci->tmp_coloring,  0, n_regs * sizeof(ci->tmp_coloring[0]));
 979                 memset(ci->fronts,        0, n_regs * n_childs * sizeof(ci->fronts[0]));
 980
 981                 for(j = 0; j < env->n_regs; j++)
 982                         ci->col_costs[j] = INT_MAX;
 983
 984         }
 985
 986         determine_color_badness(cloud->mst_root, 0);
 987         best_col = coalesce_top_down(cloud->mst_root, -1, 0);
 988         unfix_subtree(cloud->mst_root);
 989         apply_coloring(cloud->mst_root, best_col, 0);
 990
 991         /* The coloring should represent the one with the best costs. */
 992         //materialize_coloring(&changed);
 993         DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
 994                 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
 995
 996         /* Fix all nodes in the cloud. */
 997         for(i = 0; i < cloud->n_memb; ++i)
 998                 cloud->seq[i]->inh.fixed = 1;
 999
1000         /* Free all space used while optimizing this cloud. */
1001         obstack_free(&cloud->obst, NULL);
1002 }
1003
1004 static int cloud_costs(co2_cloud_t *cloud)
1005 {
1006         int i, costs = 0;
1007         neighb_t *n;
1008
1009         for(i = 0; i < cloud->n_memb; ++i) {
1010                 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1011                 col_t col = get_col(cloud->env, ci->irn);
1012                 co_gs_foreach_neighb(ci->aff, n) {
1013                         col_t n_col = get_col(cloud->env, n->irn);
1014                         costs += col != n_col ? n->costs : 0;
1015                 }
1016         }
1017
1018         return costs / 2;
1019 }
1020
1021 static void process(co2_t *env)
1022 {
1023         affinity_node_t *a;
1024         co2_cloud_t *pos;
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 = xmalloc(n_clouds * sizeof(clouds[0]));
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                 /* Dump the IFG if the user demanded it. */
1058                 if (dump_flags & DUMP_CLOUD) {
1059                         char buf[256];
1060                         FILE *f;
1061
1062                         ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1063                         f = fopen(buf, "wt");
1064                         if(f != NULL) {
1065                                 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1066                                 fclose(f);
1067                         }
1068                 }
1069         }
1070
1071         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1072
1073         xfree(clouds);
1074 }
1075
1076 static void writeback_colors(co2_t *env)
1077 {
1078         const arch_env_t *aenv = env->co->aenv;
1079         co2_irn_t *irn;
1080
1081         for(irn = env->touched; irn; irn = irn->touched_next) {
1082                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1083                 arch_set_irn_register(aenv, irn->irn, reg);
1084         }
1085 }
1086
1087
1088 /*
1089   ___ _____ ____   ____   ___ _____   ____                        _
1090  |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1091   | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1092   | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
1093  |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1094                                                            |_|            |___/
1095 */
1096
1097 static const char *get_dot_color_name(int col)
1098 {
1099         static const char *names[] = {
1100                 "blue",
1101                 "red",
1102                 "green",
1103                 "yellow",
1104                 "cyan",
1105                 "magenta",
1106                 "orange",
1107                 "chocolate",
1108                 "beige",
1109                 "navy",
1110                 "darkgreen",
1111                 "darkred",
1112                 "lightPink",
1113                 "chartreuse",
1114                 "lightskyblue",
1115                 "linen",
1116                 "pink",
1117                 "lightslateblue",
1118                 "mintcream",
1119                 "red",
1120                 "darkolivegreen",
1121                 "mediumblue",
1122                 "mistyrose",
1123                 "salmon",
1124                 "darkseagreen",
1125                 "mediumslateblue"
1126                 "moccasin",
1127                 "tomato",
1128                 "forestgreen",
1129                 "darkturquoise",
1130                 "palevioletred"
1131         };
1132
1133         return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1134 }
1135
1136 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1137 {
1138         arch_register_req_t req;
1139
1140         arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1141         if(arch_register_req_is(&req, limited))
1142                 return "diamond";
1143
1144         if(ci->fixed)
1145                 return "rectangle";
1146
1147         if(ci->tmp_fixed)
1148                 return "hexagon";
1149
1150         return "ellipse";
1151 }
1152
1153 static void ifg_dump_graph_attr(FILE *f, void *self)
1154 {
1155         fprintf(f, "overlay=false");
1156 }
1157
1158 static int ifg_is_dump_node(void *self, ir_node *irn)
1159 {
1160         co2_t *env = self;
1161         return !arch_irn_is(env->co->aenv, irn, ignore);
1162 }
1163
1164 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1165 {
1166         co2_t *env    = self;
1167         co2_irn_t *ci = get_co2_irn(env, irn);
1168         int peri      = 1;
1169
1170         char buf[128] = "";
1171
1172         if(ci->aff) {
1173                 co2_cloud_irn_t *cci = (void *) ci;
1174                 if (cci->cloud && cci->cloud->mst_root == cci)
1175                         peri = 2;
1176
1177                 if(cci->cloud && cci->cloud->mst_root)
1178                         ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1179         }
1180
1181         ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1182                 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1183 }
1184
1185 static void ifg_dump_at_end(FILE *file, void *self)
1186 {
1187         co2_t *env = self;
1188         affinity_node_t *a;
1189
1190         co_gs_foreach_aff_node(env->co, a) {
1191                 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1192                 int idx = get_irn_idx(a->irn);
1193                 neighb_t *n;
1194
1195                 if(ai->mst_parent != ai)
1196                         fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1197
1198                 co_gs_foreach_neighb(a, n) {
1199                         int nidx = get_irn_idx(n->irn);
1200                         co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1201
1202                         if(idx < nidx) {
1203                                 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1204                                 const char *arr = "arrowhead=dot arrowtail=dot";
1205
1206                                 if(ci->mst_parent == ai)
1207                                         arr = "arrowtail=normal";
1208                                 else if(ai->mst_parent == ci)
1209                                         arr = "arrowhead=normal";
1210
1211                                 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1212                         }
1213                 }
1214         }
1215 }
1216
1217
1218 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1219         ifg_is_dump_node,
1220         ifg_dump_graph_attr,
1221         ifg_dump_node_attr,
1222         NULL,
1223         NULL,
1224         ifg_dump_at_end
1225 };
1226
1227
1228 int co_solve_heuristic_new(copy_opt_t *co)
1229 {
1230         char buf[256];
1231         co2_t env;
1232         FILE *f;
1233
1234         phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1235         env.touched     = NULL;
1236         env.visited     = 0;
1237         env.co          = co;
1238         env.n_regs      = co->cls->n_regs;
1239         env.ignore_regs = bitset_alloca(co->cls->n_regs);
1240         arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1241         bitset_flip_all(env.ignore_regs);
1242         be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1243         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1244         INIT_LIST_HEAD(&env.cloud_head);
1245
1246         if(dump_flags & DUMP_BEFORE) {
1247                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1248                 f = fopen(buf, "wt");
1249                 if (f != NULL) {
1250                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1251                         fclose(f);
1252                 }
1253         }
1254
1255         process(&env);
1256
1257         if(dump_flags & DUMP_AFTER) {
1258                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1259                 f = fopen(buf, "wt");
1260                 if (f != NULL) {
1261                         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1262                         fclose(f);
1263                 }
1264         }
1265
1266         writeback_colors(&env);
1267         phase_free(&env.ph);
1268         return 0;
1269 }