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 #include <stdlib.h>
   9 #include <limits.h>
  10
  11 #include "list.h"
  12 #include "pdeq.h"
  13 #include "bitset.h"
  14 #include "debug.h"
  15
  16 #include "irphase_t.h"
  17 #include "irgraph_t.h"
  18 #include "irnode_t.h"
  19 #include "irprintf.h"
  20
  21 #include "beabi.h"
  22 #include "benode_t.h"
  23 #include "becopyopt.h"
  24 #include "becopyopt_t.h"
  25 #include "bechordal_t.h"
  26
  27 #define INFEASIBLE(col) ((col) > (INT_MAX - 10))
  28
  29 typedef unsigned col_t;
  30
  31 typedef struct _co2_irn_t   co2_irn_t;
  32 typedef struct _co2_cloud_t co2_cloud_t;
  33
  34 typedef struct {
  35         phase_t ph;
  36         copy_opt_t *co;
  37         bitset_t *ignore_regs;
  38         co2_irn_t *touched;
  39         int visited;
  40         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  41 } co2_t;
  42
  43 struct _co2_irn_t {
  44         ir_node         *irn;
  45         co2_cloud_t     *cloud;
  46         co2_irn_t       *touched_next;
  47         affinity_node_t *aff;
  48         int              costs;
  49         col_t            tmp_col;
  50         col_t            orig_col;
  51         int              visited;
  52         int              rank;
  53         unsigned         fixed     : 1;
  54         unsigned         tmp_fixed : 1;
  55         struct list_head changed_list;
  56         struct list_head cloud_list;
  57 };
  58
  59 struct _co2_cloud_t {
  60         int costs;
  61         int inevit;
  62         int best_costs;
  63         int n_memb;
  64         int max_degree;
  65         co2_irn_t *master;
  66         co2_irn_t **seq;
  67         col_t      *best_cols;
  68         struct list_head members_head;
  69         struct list_head list;
  70 };
  71
  72 #define NEIGHBOR_FIXED   1
  73 #define NEIGHBOR_CONSTR  2
  74 #define SELF_CONSTR      4
  75 #define DONT_WANT        8
  76
  77 typedef struct {
  78         col_t col;
  79         int costs;
  80         unsigned flags;
  81 } col_cost_pair_t;
  82
  83 #define get_co2_irn(co2, irn)   ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
  84
  85 static void co2_irn_init(phase_t *ph, const ir_node *irn, void *data)
  86 {
  87         co2_t *env    = (co2_t *) ph;
  88         co2_irn_t *ci = data;
  89
  90         memset(ci, 0, sizeof(ci[0]));
  91         INIT_LIST_HEAD(&ci->changed_list);
  92         INIT_LIST_HEAD(&ci->cloud_list);
  93         ci->irn          = irn;
  94         ci->touched_next = env->touched;
  95         ci->orig_col     = get_irn_col(env->co, irn);
  96         ci->aff          = get_affinity_info(env->co, irn);
  97         env->touched     = ci;
  98 }
  99
 100
 101 static int co2_irn_cmp(const void *a, const void *b)
 102 {
 103         const co2_irn_t **p = a;
 104         const co2_irn_t **q = b;
 105         return (*q)->costs - (*p)->costs;
 106 }
 107
 108 static int cmp_clouds(const void *a, const void *b)
 109 {
 110         const co2_cloud_t **p = a;
 111         const co2_cloud_t **q = b;
 112         return (*q)->costs - (*p)->costs;
 113 }
 114
 115 static co2_cloud_t *new_cloud(co2_t *env)
 116 {
 117         co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
 118         memset(cloud, 0, sizeof(cloud[0]));
 119         INIT_LIST_HEAD(&cloud->members_head);
 120         INIT_LIST_HEAD(&cloud->list);
 121         cloud->best_costs = INT_MAX;
 122         return cloud;
 123 }
 124
 125 /**
 126  * An order on color/costs pairs.
 127  * If the costs are equal, we use the color as a kind of normalization.
 128  */
 129 static int col_cost_pair_lt(const void *a, const void *b)
 130 {
 131         const col_cost_pair_t *p = a;
 132         const col_cost_pair_t *q = b;
 133         int c = p->costs;
 134         int d = q->costs;
 135
 136         if(c > d)
 137                 return 1;
 138         if(c < d)
 139                 return -1;
 140
 141         return 0;
 142 }
 143
 144 const char *flag_str(unsigned int fl)
 145 {
 146         static char buf[10];
 147
 148         buf[0] = fl & NEIGHBOR_CONSTR ? 'c' : '-';
 149         buf[1] = fl & NEIGHBOR_FIXED  ? 'n' : '-';
 150         buf[2] = fl & SELF_CONSTR     ? 'C' : '-';
 151         buf[3] = fl & DONT_WANT       ? 'd' : '-';
 152         buf[4] = '\0';
 153         return buf;
 154 }
 155
 156 static col_t get_col(co2_t *env, ir_node *irn)
 157 {
 158         co2_irn_t *ci = get_co2_irn(env, irn);
 159         return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
 160 }
 161
 162 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
 163 {
 164         co2_irn_t *ci = get_co2_irn(env, irn);
 165         return ci->fixed || ci->tmp_fixed;
 166 }
 167
 168 static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
 169 {
 170         arch_register_req_t req;
 171
 172         arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
 173         if(arch_register_req_is(&req, limited))
 174                 req.limited(req.limited_env, bs);
 175         else {
 176                 bitset_copy(bs, env->ignore_regs);
 177                 bitset_flip_all(bs);
 178         }
 179
 180         return bs;
 181 }
 182
 183 static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
 184 {
 185         bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
 186         admissible_colors(env, ci, bs);
 187         return bitset_is_set(bs, col);
 188 }
 189
 190 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
 191 {
 192         bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
 193         arch_register_req_t req;
 194
 195         arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
 196
 197         if(arch_register_req_is(&req, limited)) {
 198                 bitset_pos_t elm;
 199                 int n_constr;
 200
 201                 req.limited(req.limited_env, aux);
 202                 n_constr = bitset_popcnt(aux);
 203                 bitset_foreach(aux, elm) {
 204                         col_costs[elm].costs += costs / n_constr;
 205                         col_costs[elm].flags |= NEIGHBOR_CONSTR;
 206                 }
 207         }
 208 }
 209
 210 /**
 211  * Determine costs which shall indicate how cheap/expensive it is to try
 212  * to assign a node some color.
 213  * The costs are computed for all colors. INT_MAX means that it is impossible
 214  * to give the node that specific color.
 215  *
 216  * @param env       The co2 this pointer.
 217  * @param irn       The node.
 218  * @param col_costs An array of colors x costs where the costs are written to.
 219  */
 220 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
 221 {
 222         ir_node *irn       = ci->irn;
 223         be_ifg_t *ifg      = env->co->cenv->ifg;
 224         int n_regs         = env->co->cls->n_regs;
 225         bitset_t *forb     = bitset_alloca(n_regs);
 226         affinity_node_t *a = get_affinity_info(env->co, irn);
 227
 228         bitset_pos_t elm;
 229         ir_node *pos;
 230         void *it;
 231         int i;
 232
 233         if(get_irn_node_nr(irn) == 2040) {
 234                 printf("Hallo");
 235         }
 236
 237         /* Put all forbidden colors into the aux bitset. */
 238         admissible_colors(env, ci, forb);
 239         bitset_flip_all(forb);
 240
 241         for(i = 0; i < n_regs; ++i) {
 242                 col_costs[i].col   = i;
 243                 col_costs[i].costs = 0;
 244                 col_costs[i].flags = 0;
 245         }
 246
 247         if(a) {
 248                 neighb_t *n;
 249
 250                 co_gs_foreach_neighb(a, n) {
 251                         if(color_is_fix(env, n->irn)) {
 252                                 col_t col = get_col(env, n->irn);
 253                                 col_costs[col].costs -= 100 * n->costs;
 254                         }
 255
 256                         incur_constraint_costs(env, n->irn, col_costs, -n->costs);
 257                 }
 258         }
 259
 260         it = be_ifg_neighbours_iter_alloca(ifg);
 261         be_ifg_foreach_neighbour(ifg, it, irn, pos) {
 262                 col_t col = get_col(env, pos);
 263                 if(color_is_fix(env, pos)) {
 264                         col_costs[col].costs  = INT_MAX;
 265                         col_costs[col].flags |= NEIGHBOR_FIXED;
 266                 }
 267                 else {
 268                         incur_constraint_costs(env, pos, col_costs, INT_MAX);
 269                         col_costs[col].costs += 10 * be_ifg_degree(ifg, pos);
 270                 }
 271         }
 272
 273         /* Set the costs to infinity for each color which is not allowed at this node. */
 274         bitset_foreach(forb, elm) {
 275                 col_costs[elm].costs  = INT_MAX;
 276                 col_costs[elm].flags |= SELF_CONSTR;
 277         }
 278
 279 }
 280
 281 static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq)
 282 {
 283         int n_regs = env->co->cls->n_regs;
 284         int i;
 285
 286         for(i = 0; i < n_regs; ++i) {
 287                 seq[i].col   = i;
 288                 seq[i].costs = INT_MAX;
 289                 seq[i].flags = 0;
 290                 seq[i].flags = DONT_WANT;
 291         }
 292
 293         seq[col].col = 0;
 294         seq[0].col   = col;
 295         seq[0].costs = 0;
 296         seq[0].flags = 0;
 297 }
 298
 299 static int curr_costs(co2_t *env, affinity_node_t *a)
 300 {
 301         col_t a_col = get_col(env, a->irn);
 302         int costs   = 0;
 303         neighb_t *n;
 304
 305         co_gs_foreach_neighb(a, n) {
 306                 col_t n_col = get_col(env, n->irn);
 307                 costs += n_col != a_col ? n->costs : 0;
 308         }
 309
 310         return costs;
 311 }
 312
 313 static int cloud_costs(co2_t *env, co2_cloud_t *cloud)
 314 {
 315         int costs = 0;
 316         co2_irn_t *ci;
 317
 318         list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
 319                 affinity_node_t *a = get_affinity_info(env->co, ci->irn);
 320                 costs += curr_costs(env, a);
 321         }
 322
 323         return costs;
 324 }
 325
 326 static void reject_coloring(struct list_head *h)
 327 {
 328         co2_irn_t *pos;
 329
 330         list_for_each_entry(co2_irn_t, pos, h, changed_list)
 331                 pos->tmp_fixed = 0;
 332 }
 333
 334 static void materialize_coloring(struct list_head *h)
 335 {
 336         co2_irn_t *pos;
 337
 338         list_for_each_entry(co2_irn_t, pos, h, changed_list) {
 339                 pos->orig_col = pos->tmp_col;
 340                 pos->tmp_fixed = 0;
 341         }
 342 }
 343
 344 typedef struct {
 345         co2_irn_t *ci;
 346         col_t col;
 347 } col_entry_t;
 348
 349 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
 350 {
 351         co2_irn_t *pos;
 352         col_entry_t ent;
 353
 354         list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
 355                 ent.ci  = pos;
 356                 ent.col = pos->tmp_col;
 357                 pos->tmp_col = 0;
 358                 obstack_grow(obst, &ent, sizeof(ent));
 359         }
 360         memset(&ent, 0, sizeof(ent));
 361         obstack_grow(obst, &ent, sizeof(ent));
 362         return obstack_finish(obst);
 363 }
 364
 365 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 366 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
 367
 368 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
 369 {
 370         int n_regs         = env->co->cls->n_regs;
 371         be_ifg_t *ifg      = env->co->cenv->ifg;
 372         co2_irn_t *ci      = get_co2_irn(env, irn);
 373         int res            = 0;
 374         int n_aff          = 0;
 375
 376         int i;
 377
 378         for(i = 0; i < n_regs; ++i) {
 379                 col_t tgt_col  = col_list[i].col;
 380                 unsigned costs = col_list[i].costs;
 381                 int neigh_ok   = 1;
 382
 383                 struct list_head changed;
 384                 ir_node *n;
 385                 void *it;
 386
 387                 DBG((env->dbg, LEVEL_3, "\t\t%2Ntrying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
 388
 389                 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 390                 if(INFEASIBLE(costs)) {
 391                         DB((env->dbg, LEVEL_4, "\t\t%2Ncolor %d infeasible due to %s\n", depth, tgt_col, flag_str(col_list[i].flags)));
 392                         ci->tmp_fixed = 0;
 393                         return 0;
 394                 }
 395
 396                 /* Set the new color of the node and mark the node as temporarily fixed. */
 397                 ci->tmp_col   = tgt_col;
 398                 ci->tmp_fixed = 1;
 399
 400                 /*
 401                 If that color has costs > 0, there's at least one neighbor having that color,
 402                 so we will try to change the neighbors' colors, too.
 403                 */
 404                 INIT_LIST_HEAD(&changed);
 405                 list_add(&ci->changed_list, &changed);
 406
 407                 it = be_ifg_neighbours_iter_alloca(ifg);
 408                 be_ifg_foreach_neighbour(ifg, it, irn, n) {
 409
 410                         /* try to re-color the neighbor if it has the target color. */
 411                         if(get_col(env, n) == tgt_col) {
 412                                 struct list_head tmp;
 413
 414                                 /*
 415                                 Try to change the color of the neighbor and record all nodes which
 416                                 get changed in the tmp list. Add this list to the "changed" list for
 417                                 that color. If we did not succeed to change the color of the neighbor,
 418                                 we bail out and try the next color.
 419                                 */
 420                                 INIT_LIST_HEAD(&tmp);
 421                                 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
 422                                 list_splice(&tmp, &changed);
 423                                 if(!neigh_ok)
 424                                         break;
 425                         }
 426                 }
 427
 428                 /*
 429                 We managed to assign the target color to all neighbors, so from the perspective
 430                 of the current node, every thing was ok and we can return safely.
 431                 */
 432                 if(neigh_ok) {
 433                         DBG((env->dbg, LEVEL_3, "\t\t%2Ncolor %d(%d) was ok\n", depth, tgt_col, costs));
 434                         list_splice(&changed, parent_changed);
 435                         res = 1;
 436                         break;
 437                 }
 438
 439                 /*
 440                 If not, that color did not succeed and we unfix all nodes we touched
 441                 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
 442                 */
 443                 else
 444                         reject_coloring(&changed);
 445         }
 446
 447         return res;
 448 }
 449
 450 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
 451 {
 452         co2_irn_t *ci = get_co2_irn(env, irn);
 453         int res       = 0;
 454         col_t col     = get_col(env, irn);
 455
 456         DBG((env->dbg, LEVEL_3, "\t\t%2Nclearing %+F(%d) of color %d\n", depth, irn, col, not_col));
 457
 458         /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
 459         if(col != not_col) {
 460                 if(!ci->tmp_fixed) {
 461                         ci->tmp_col   = col;
 462                         ci->tmp_fixed = 1;
 463                 }
 464
 465                 list_add(&ci->changed_list, parent_changed);
 466                 return 1;
 467         }
 468
 469         /* The node has the color it should not have _and_ has not been visited yet. */
 470         if(!color_is_fix(env, irn)) {
 471                 int n_regs            = env->co->cls->n_regs;
 472                 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
 473
 474                 /* Get the costs for giving the node a specific color. */
 475                 determine_color_costs(env, ci, csts);
 476
 477                 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
 478                 csts[not_col].costs = INT_MAX;
 479
 480                 /* sort the colors according costs, cheapest first. */
 481                 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
 482
 483                 /* Try recoloring the node using the color list. */
 484                 res = recolor(env, irn, csts, parent_changed, depth);
 485         }
 486
 487         /* If we came here, everything went ok. */
 488         return res;
 489 }
 490
 491 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
 492 {
 493         co2_irn_t *ci = get_co2_irn(env, irn);
 494         col_t col     = get_col(env, irn);
 495         int res       = 0;
 496
 497         DBG((env->dbg, LEVEL_3, "\t\t%2Ntrying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
 498
 499         /* If the color is already fix, bail out. */
 500         if(color_is_fix(env, irn))
 501                 return 0;
 502
 503         /* the node has the wanted color. That's fine, mark it as visited and return. */
 504         if(col == tgt_col) {
 505                 if(!ci->tmp_fixed) {
 506                         ci->tmp_col   = col;
 507                         ci->tmp_fixed = 1;
 508                 }
 509
 510                 list_add(&ci->changed_list, parent_changed);
 511                 DB((env->dbg, LEVEL_3, "\t\tok\n"));
 512                 return 1;
 513         }
 514
 515         else {
 516                 int n_regs           = env->co->cls->n_regs;
 517                 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
 518
 519                 /* Get the costs for giving the node a specific color. */
 520                 single_color_cost(env, tgt_col, seq);
 521
 522                 /* Try recoloring the node using the color list. */
 523                 res = recolor(env, irn, seq, parent_changed, depth);
 524
 525                 DB((env->dbg, LEVEL_3, "\t\tcolor %d %s for %+F\n", tgt_col, res ? "was ok" : "failed", irn));
 526         }
 527
 528         return res;
 529 }
 530
 531
 532 #if 0
 533 static void try_color(co2_t *env, co2_irn_t *ci, col_t col, struct list_head *parent_changed)
 534 {
 535         be_ifg_t *ifg            = env->co->cenv->ifg;
 536         int n_regs               = env->co->cls->n_regs;
 537         col_cost_pair_t *col_seq = alloca(n_regs * sizeof(col_seq[0]));
 538         affinity_node_t *a       = get_affinity_info(env->co, ci->irn);
 539         co2_irn_t **nbs          = alloca(a->degree * sizeof(nbs[0]));
 540         int ok = 0;
 541
 542         col_t new_col;
 543         neighb_t *n;
 544
 545         assert(a != NULL && "This node must be an affinity node");
 546
 547         /* If that node has already been fixed, leave it alone. */
 548         if(color_is_fix(env, ci->irn) || !is_color_admissible(env, ci, col)) {
 549                 // DB((env->dbg, LEVEL_2, "\t-> color is already fix: %d\n", get_col(env, ci->irn)));
 550                 return;
 551         }
 552
 553         DB((env->dbg, LEVEL_1, "\taffinity node %+F cost %d trying color %d\n", ci->irn, ci->costs, col));
 554
 555         single_color_cost(env, col, col_seq);
 556         recolor(env, ci->irn, col_seq, parent_changed, 0);
 557         new_col = get_col(env, ci->irn);
 558
 559         ci->tmp_fixed = 1;
 560         ci->tmp_col   = new_col;
 561
 562         DB((env->dbg, LEVEL_2, "\t-> has color %d now. %d wanted\n", new_col, col));
 563
 564         i = 0;
 565         co_gs_foreach_neighb(a, n)
 566                 nbs[i++] = get_co2_irn(env, n->irn);
 567
 568         co_gs_foreach_neighb(a, n) {
 569                 co2_irn_t *ni = get_co2_irn(env, n->irn);
 570                 col_t tgt_col = be_ifg_connected(ifg, ci->irn, ni->irn) ? get_col(env, ni->irn) : new_col;
 571                 try_color(env, ni, tgt_col, parent_changed);
 572         }
 573 }
 574
 575
 576 static void process_cloud(co2_t *env, co2_cloud_t *cloud)
 577 {
 578         int n_regs            = env->co->cls->n_regs;
 579         col_cost_pair_t *cols = alloca(n_regs * sizeof(cols[0]));
 580         int best_costs        = cloud_costs(env, cloud);
 581         int best_col          = 0;
 582
 583         struct list_head changed;
 584         co2_irn_t *ci;
 585         int i;
 586
 587
 588         i = 0;
 589         DB((env->dbg, LEVEL_2, "processing cloud with costs %d and master %+F containing:\n", cloud->costs, cloud->master->irn));
 590         list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
 591                 DB((env->dbg, LEVEL_2, "\t%+F %d\n", ci->irn, ci->costs));
 592         }
 593
 594         determine_color_costs(env, cloud->master, cols);
 595         qsort(cols, n_regs, sizeof(cols[0]), col_cost_pair_lt);
 596
 597         best_col = cols[0].col;
 598         for(i = 0; i < n_regs; ++i) {
 599                 col_t col  = cols[i].col;
 600                 int reject = 1;
 601                 int costs;
 602
 603                 INIT_LIST_HEAD(&changed);
 604                 DBG((env->dbg, LEVEL_2, "\n\ttrying color %d. current costs: %d\n", col, best_costs));
 605
 606                 /* try to recolor all the cloud members. */
 607                 try_color(env, cloud->master, col, &changed);
 608
 609                 /* recoloring of all nodes did succeed. measure the costs and decide if the coloring shall be kept. */
 610                 costs = cloud_costs(env, cloud);
 611
 612                 /* materialize the new coloring. */
 613                 if(costs < best_costs) {
 614                         materialize_coloring(&changed);
 615                         best_costs = costs;
 616                         best_col   = col;
 617                         reject     = 0;
 618                 }
 619
 620                 /* We won't get the cloud any better so stop it. */
 621                 if(costs == 0)
 622                         break;
 623
 624                 if(reject)
 625                         reject_coloring(&changed);
 626         }
 627
 628         DB((env->dbg, LEVEL_2, "\tfinished cloud with costs %d\n", best_costs));
 629
 630         /* fix all cloud members */
 631         list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
 632                 ci->fixed = 1;
 633         }
 634
 635 }
 636
 637 static void try_affinity_node(co2_t *env, co2_irn_t *ci, col_t preferred, struct list_head *parent_changed)
 638 {
 639         ir_node *irn = ci->irn;
 640
 641         if(!color_is_fix(env, irn)) {
 642                 int n_regs      = env->co->cls->n_regs;
 643                 bitset_t *tried = bitset_alloca(n_regs);
 644                 bitset_t *adm   = bitset_alloca(n_regs);
 645                 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
 646
 647                 affinity_node_t *a = get_affinity_info(env->co, irn);
 648                 int best_costs  = cloud_costs(env, ci->cloud);
 649                 int best_col    = get_col(env, ci->irn);
 650
 651                 int i;
 652
 653                 determine_color_costs(env, ci, seq);
 654                 if(!INFEASIBLE(seq[preferred].costs))
 655                         seq[preferred].costs = INT_MIN;
 656
 657                 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
 658
 659                 for(i = 0; i < n_regs; ++i) {
 660                         col_t col = seq[i].col;
 661
 662                         struct list_head changed;
 663                         int ok, costs;
 664
 665                         INIT_LIST_HEAD(&changed);
 666                         ok  = change_color_single(env, irn, col, &changed, 0);
 667                         col = get_col(env, irn);
 668
 669                         if(!bitset_is_set(tried, col)) {
 670                                 neighb_t *n;
 671
 672                                 if(!ci->tmp_col) {
 673                                         ci->tmp_col   = col;
 674                                         ci->tmp_fixed = 1;
 675                                         list_add(&ci->changed_list, &changed);
 676                                 }
 677
 678                                 co_gs_foreach_neighb(a, n) {
 679                                         co2_irn_t *ni = get_co2_irn(env, n->irn);
 680                                         try_affinity_node(env, ni, col, &changed);
 681                                 }
 682
 683                                 examine_coloring(env, ci->cloud);
 684                                 reject_coloring(&changed);
 685
 686                                 bitset_set(tried, col);
 687                         }
 688                 }
 689         }
 690 }
 691 #endif
 692
 693 static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
 694 {
 695         int costs = cloud_costs(env, cloud);
 696
 697         if(costs < cloud->best_costs) {
 698                 int i;
 699
 700                 for(i = 0; i < cloud->n_memb; ++i)
 701                         cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
 702
 703                 cloud->best_costs = costs;
 704         }
 705 }
 706
 707 static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors)
 708 {
 709         col_t col = get_col(env, ci->irn);
 710         neighb_t *n;
 711         int balance = 0;
 712
 713         co_gs_foreach_neighb(ci->aff, n) {
 714                 col_t nc  = get_col(env, n->irn);
 715                 int fixed = color_is_fix(env, n->irn);
 716
 717                 if(nc == col)
 718                         balance -= n->costs;
 719                 else if(!fixed || !bitset_is_set(tried_colors, nc))
 720                         balance += n->costs;
 721         }
 722
 723         DBG((env->dbg, LEVEL_4, "\t\tbalance for changing %+F color %d\n", ci->irn, balance));
 724         return balance;
 725 }
 726
 727 static void keep_sensible_colors(co2_t *env, co2_irn_t *ci, col_cost_pair_t *seq)
 728 {
 729         bitset_t *fixed_cols = bitset_alloca(env->co->cls->n_regs);
 730         int all_fixed = 1;
 731         neighb_t *n;
 732
 733         co_gs_foreach_neighb(ci->aff, n) {
 734                 all_fixed &= color_is_fix(env, n->irn);
 735                 bitset_set(fixed_cols, get_col(env, n->irn));
 736         }
 737
 738         if(all_fixed) {
 739                 bitset_pos_t i;
 740                 bitset_flip_all(fixed_cols);
 741                 bitset_foreach(fixed_cols, i)
 742                         seq[i].costs = INT_MAX;
 743         }
 744 }
 745
 746 static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
 747 {
 748         struct list_head changed;
 749         int res = 0;
 750
 751         if(index < cloud->n_memb) {
 752                 co2_irn_t *ci           = cloud->seq[index];
 753                 int n_regs              = env->co->cls->n_regs;
 754                 col_cost_pair_t *seq    = alloca(n_regs * sizeof(seq[0]));
 755                 bitset_t *cols_tried    = bitset_alloca(n_regs);
 756                 int done                = 0;
 757                 //col_cost_pair_t *single = alloca(n_regs * sizeof(seq[0]));
 758
 759                 int i;
 760
 761                 determine_color_costs(env, ci, seq);
 762
 763                 if(index == 0) {
 764                         col_t col     = get_col(env, ci->irn);
 765                         int min_costs = INT_MAX;
 766                         int i;
 767
 768                         for(i = 0; i < n_regs; ++i)
 769                                 min_costs = MIN(min_costs, seq[i].costs);
 770
 771                         seq[col].costs = min_costs - 1;
 772                 }
 773
 774                 //keep_sensible_colors(env, ci, seq);
 775                 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
 776
 777 #if 0
 778                 if(index == cloud->n_memb - 1) {
 779                         for(i = 0; i < n_regs; ++i)
 780                                 if(seq[i].costs >= 0)
 781                                         seq[i].costs = INT_MAX;
 782                 }
 783 #endif
 784
 785
 786                 for(i = 0; i < n_regs && !done; ++i) {
 787                         col_t col = seq[i].col;
 788                         int costs = seq[i].costs;
 789                         int ok;
 790
 791                         /*
 792                                 if all affinity neighbors fixed,
 793                                 try only color changes to affinity colors.
 794                                 all other colors do no good.
 795                         */
 796
 797                         DB((env->dbg, LEVEL_2, "\t%2Ntrying %+F index %d for color %d\n", index, ci->irn, index, col));
 798                         if(INFEASIBLE(costs)) {
 799                                 DBG((env->dbg, LEVEL_2, "\t%2N-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
 800                                 break;
 801                         }
 802
 803                         bitset_set(cols_tried, col);
 804                         INIT_LIST_HEAD(&changed);
 805                         ok = change_color_single(env, ci->irn, col, &changed, 0);
 806                         DB((env->dbg, LEVEL_2, "\t%2N-> %s\n", index, ok ? "ok" : "failed"));
 807
 808                         /* if we succeeded changing the color, we will figure out the next node. */
 809                         if(ok) {
 810                                 int finish;
 811
 812                                 /* materialize the coloring and fix the node's color. */
 813                                 ci->fixed = 1;
 814
 815                                 /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */
 816                                 finish = process_node(env, cloud, index + 1);
 817
 818                                 /* if this is the last node in the coloring sequence, examine the coloring */
 819                                 if(index == cloud->n_memb - 1) {
 820                                         examine_cloud_coloring(env, cloud);
 821                                         DB((env->dbg, LEVEL_2, "\t%2N-> current best coloring %d\n", index, cloud->best_costs));
 822                                         if(cloud->best_costs == cloud->inevit) {
 823                                                 done = 1;
 824                                                 res  = 1;
 825                                         }
 826                                 }
 827
 828                                 /* unfix the node. */
 829                                 reject_coloring(&changed);
 830                                 ci->fixed = 0;
 831
 832                                 if(finish || color_change_balance(env, ci, cols_tried) <= 0) {
 833                                         res  = finish;
 834                                         done = 1;
 835                                 }
 836                         }
 837
 838                 }
 839         }
 840
 841         return res;
 842 }
 843
 844 static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs)
 845 {
 846         int i;
 847         neighb_t *n;
 848
 849         i = 0;
 850         co_gs_foreach_neighb(ci->aff, n) {
 851                 nbs[i++] = get_co2_irn(env, n->irn);
 852         }
 853
 854         qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
 855         return nbs;
 856 }
 857
 858 static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud)
 859 {
 860         pdeq *q         = new_pdeq1(cloud->master);
 861         bitset_t *seen  = bitset_malloc(get_irg_last_idx(env->co->irg));
 862         co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0]));
 863         int i, j;
 864
 865         j = 0;
 866         bitset_set(seen, get_irn_idx(cloud->master->irn));
 867         while(!pdeq_empty(q)) {
 868                 co2_irn_t *curr = pdeq_getl(q);
 869
 870                 cloud->seq[j++] = curr;
 871                 get_neighb_arr(env, curr, nbs);
 872
 873                 for(i = 0; i < curr->aff->degree; ++i) {
 874                         co2_irn_t *ni = nbs[i];
 875                         int idx       = get_irn_idx(ni->irn);
 876                         if(!bitset_is_set(seen, idx)) {
 877                                 pdeq_putr(q, ni);
 878                                 bitset_set(seen, idx);
 879                         }
 880                 }
 881         }
 882
 883         del_pdeq(q);
 884         bitset_free(seen);
 885 }
 886
 887 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
 888 {
 889         be_ifg_t *ifg = env->co->cenv->ifg;
 890         co2_irn_t *ci = get_co2_irn(env, a->irn);
 891         int costs     = 0;
 892         neighb_t *n;
 893
 894         if(ci->visited >= env->visited)
 895                 return;
 896
 897         /* mark the node as visited and add it to the cloud. */
 898         ci->visited = env->visited;
 899         ci->cloud   = cloud;
 900         list_add(&ci->cloud_list, &cloud->members_head);
 901
 902         DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
 903
 904         /* determine the nodes costs */
 905         co_gs_foreach_neighb(a, n) {
 906                 costs += n->costs;
 907                 DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
 908                 if(be_ifg_connected(ifg, a->irn, n->irn))
 909                         cloud->inevit += n->costs;
 910         }
 911
 912         /* add the node's cost to the total costs of the cloud. */
 913         ci->costs          = costs;
 914         cloud->costs      += costs;
 915         cloud->max_degree  = MAX(cloud->max_degree, ci->aff->degree);
 916         cloud->n_memb++;
 917
 918         /* If this is the heaviest node in the cloud, set it as the cloud's master. */
 919         if(costs >= curr_costs) {
 920                 cloud->master = ci;
 921                 curr_costs    = costs;
 922         }
 923
 924         /* add all the neighbors of the node to the cloud. */
 925         co_gs_foreach_neighb(a, n) {
 926                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 927                 assert(an);
 928                 populate_cloud(env, cloud, an, curr_costs);
 929         }
 930 }
 931
 932 static void init_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a)
 933 {
 934         env->visited++;
 935         populate_cloud(env, cloud, a, 0);
 936
 937         cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
 938         cloud->seq       = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
 939         env->visited++;
 940         cloud->seq[0] = cloud->master;
 941         determine_coloring_sequence(env, cloud);
 942 }
 943
 944 static void process_cloud(co2_t *env, co2_cloud_t *cloud)
 945 {
 946         struct list_head changed;
 947         int i;
 948
 949         /* initialize the best coloring. */
 950         examine_cloud_coloring(env, cloud);
 951
 952         DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
 953         for(i = 0; i < cloud->n_memb; ++i) {
 954                 co2_irn_t *ci = cloud->seq[i];
 955                 DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn)));
 956         }
 957
 958         process_node(env, cloud, 0);
 959         DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
 960
 961         /* re-try the best coloring. */
 962         INIT_LIST_HEAD(&changed);
 963         for(i = 0; i < cloud->n_memb; ++i) {
 964                 co2_irn_t *ci = cloud->seq[i];
 965                 col_t col     = cloud->best_cols[i];
 966
 967                 int ok;
 968
 969                 DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col));
 970                 ok = change_color_single(env, ci->irn, col, &changed, 0);
 971                 assert(ok);
 972                 ci->fixed = 1;
 973         }
 974         materialize_coloring(&changed);
 975
 976         {
 977                 co2_irn_t *ci;
 978                 int some_fixed = 0;
 979                 for(ci = env->touched; ci; ci = ci->touched_next) {
 980                         if(ci->tmp_fixed) {
 981                                 some_fixed = 1;
 982                                 ir_printf("%+F is still temp fixed\n", ci->irn);
 983                         }
 984                 }
 985                 assert(!some_fixed);
 986         }
 987 }
 988
 989 static void process(co2_t *env)
 990 {
 991         affinity_node_t *a;
 992         struct list_head cloud_head;
 993         co2_cloud_t *pos;
 994         co2_cloud_t **clouds;
 995         int n_clouds;
 996         int i;
 997         int init_costs  = 0;
 998         int all_costs   = 0;
 999         int final_costs = 0;
1000
1001
1002         INIT_LIST_HEAD(&cloud_head);
1003
1004         n_clouds = 0;
1005         co_gs_foreach_aff_node(env->co, a) {
1006                 co2_irn_t *ci = get_co2_irn(env, a->irn);
1007
1008                 if(!ci->cloud) {
1009                         co2_cloud_t *cloud = new_cloud(env);
1010
1011                         init_cloud(env, cloud, a);
1012                         list_add(&cloud->list, &cloud_head);
1013                         n_clouds++;
1014                 }
1015         }
1016
1017         i = 0;
1018         clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1019         list_for_each_entry(co2_cloud_t, pos, &cloud_head, list)
1020                 clouds[i++] = pos;
1021         qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
1022
1023         for(i = 0; i < n_clouds; ++i) {
1024                 init_costs  += cloud_costs(env, clouds[i]);
1025                 process_cloud(env, clouds[i]);
1026                 all_costs   += clouds[i]->costs;
1027                 final_costs += clouds[i]->best_costs;
1028         }
1029
1030         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1031
1032         xfree(clouds);
1033 }
1034
1035 static void writeback_colors(co2_t *env)
1036 {
1037         const arch_env_t *aenv = env->co->aenv;
1038         co2_irn_t *irn;
1039
1040         for(irn = env->touched; irn; irn = irn->touched_next) {
1041                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1042                 arch_set_irn_register(aenv, irn->irn, reg);
1043         }
1044 }
1045
1046 void co_solve_heuristic_new(copy_opt_t *co)
1047 {
1048         co2_t env;
1049
1050         phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
1051         env.touched     = NULL;
1052         env.visited     = 0;
1053         env.co          = co;
1054         env.ignore_regs = bitset_alloca(co->cls->n_regs);
1055         arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1056         bitset_flip_all(env.ignore_regs);
1057         be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1058         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1059
1060         process(&env);
1061         writeback_colors(&env);
1062         phase_free(&env.ph);
1063 }