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
  15 #include "debug.h"
  16 #include "bitfiddle.h"
  17
  18 #include "irphase_t.h"
  19 #include "irgraph_t.h"
  20 #include "irnode_t.h"
  21 #include "irprintf.h"
  22
  23 #include "beabi.h"
  24 #include "benode_t.h"
  25 #include "becopyopt.h"
  26 #include "becopyopt_t.h"
  27 #include "bechordal_t.h"
  28
  29 #define INFEASIBLE(cost) ((cost) == INT_MAX)
  30
  31 static be_ifg_dump_dot_cb_t ifg_dot_cb;
  32
  33 typedef unsigned col_t;
  34
  35 typedef struct _co2_irn_t   co2_irn_t;
  36 typedef struct _co2_cloud_t co2_cloud_t;
  37
  38 typedef struct {
  39         phase_t ph;
  40         copy_opt_t *co;
  41         bitset_t *ignore_regs;
  42         co2_irn_t *touched;
  43         int visited;
  44         struct list_head cloud_head;
  45         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  46 } co2_t;
  47
  48 struct _co2_irn_t {
  49         ir_node         *irn;
  50         co2_cloud_t     *cloud;
  51         co2_irn_t       *touched_next;
  52         affinity_node_t *aff;
  53         int              costs;
  54         col_t            tmp_col;
  55         col_t            orig_col;
  56         int              visited;
  57         int              rank;
  58         unsigned         fixed     : 1;
  59         unsigned         tmp_fixed : 1;
  60         struct list_head changed_list;
  61         struct list_head cloud_list;
  62 };
  63
  64 struct _co2_cloud_t {
  65         int costs;
  66         int inevit;
  67         int best_costs;
  68         int n_memb;
  69         int max_degree;
  70         co2_irn_t *master;
  71         co2_irn_t **seq;
  72         col_t      *best_cols;
  73         struct list_head members_head;
  74         struct list_head list;
  75 };
  76
  77 #define NEIGHBOR_FIXED   1
  78 #define NEIGHBOR_CONSTR  2
  79 #define SELF_CONSTR      4
  80 #define DONT_WANT        8
  81
  82 typedef struct {
  83         col_t col;
  84         int costs;
  85         unsigned flags;
  86 } col_cost_pair_t;
  87
  88 #define get_co2_irn(co2, irn)   ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
  89
  90 static void co2_irn_init(phase_t *ph, const ir_node *irn, void *data)
  91 {
  92         co2_t *env    = (co2_t *) ph;
  93         co2_irn_t *ci = data;
  94
  95         memset(ci, 0, sizeof(ci[0]));
  96         INIT_LIST_HEAD(&ci->changed_list);
  97         INIT_LIST_HEAD(&ci->cloud_list);
  98         ci->irn          = irn;
  99         ci->touched_next = env->touched;
 100         ci->orig_col     = get_irn_col(env->co, irn);
 101         ci->aff          = get_affinity_info(env->co, (ir_node *)irn);
 102         env->touched     = ci;
 103 }
 104
 105
 106 static int co2_irn_cmp(const void *a, const void *b)
 107 {
 108         const co2_irn_t **p = a;
 109         const co2_irn_t **q = b;
 110         return (*q)->costs - (*p)->costs;
 111 }
 112
 113 static int cmp_clouds(const void *a, const void *b)
 114 {
 115         const co2_cloud_t **p = a;
 116         const co2_cloud_t **q = b;
 117         return (*q)->costs - (*p)->costs;
 118 }
 119
 120 static co2_cloud_t *new_cloud(co2_t *env)
 121 {
 122         co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
 123         memset(cloud, 0, sizeof(cloud[0]));
 124         INIT_LIST_HEAD(&cloud->members_head);
 125         INIT_LIST_HEAD(&cloud->list);
 126         cloud->best_costs = INT_MAX;
 127         return cloud;
 128 }
 129
 130 /**
 131  * An order on color/costs pairs.
 132  * If the costs are equal, we use the color as a kind of normalization.
 133  */
 134 static int col_cost_pair_lt(const void *a, const void *b)
 135 {
 136         const col_cost_pair_t *p = a;
 137         const col_cost_pair_t *q = b;
 138         int c = p->costs;
 139         int d = q->costs;
 140
 141         return (c > d) - (c < d);
 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  = add_saturated(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 = add_saturated(col_costs[col].costs, -n->costs * 128);
 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 = add_saturated(col_costs[col].costs, 8 * 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%2{firm:indent}trying 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%2{firm:indent}color %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%2{firm:indent}color %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%2{firm:indent}clearing %+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%2{firm:indent}trying 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 static void process_cloud(co2_t *env, co2_cloud_t *cloud)
 576 {
 577         int n_regs            = env->co->cls->n_regs;
 578         col_cost_pair_t *cols = alloca(n_regs * sizeof(cols[0]));
 579         int best_costs        = cloud_costs(env, cloud);
 580         int best_col          = 0;
 581
 582         struct list_head changed;
 583         co2_irn_t *ci;
 584         int i;
 585
 586
 587         i = 0;
 588         DB((env->dbg, LEVEL_2, "processing cloud with costs %d and master %+F containing:\n", cloud->costs, cloud->master->irn));
 589         list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
 590                 DB((env->dbg, LEVEL_2, "\t%+F %d\n", ci->irn, ci->costs));
 591         }
 592
 593         determine_color_costs(env, cloud->master, cols);
 594         qsort(cols, n_regs, sizeof(cols[0]), col_cost_pair_lt);
 595
 596         best_col = cols[0].col;
 597         for(i = 0; i < n_regs; ++i) {
 598                 col_t col  = cols[i].col;
 599                 int reject = 1;
 600                 int costs;
 601
 602                 INIT_LIST_HEAD(&changed);
 603                 DBG((env->dbg, LEVEL_2, "\n\ttrying color %d. current costs: %d\n", col, best_costs));
 604
 605                 /* try to recolor all the cloud members. */
 606                 try_color(env, cloud->master, col, &changed);
 607
 608                 /* recoloring of all nodes did succeed. measure the costs and decide if the coloring shall be kept. */
 609                 costs = cloud_costs(env, cloud);
 610
 611                 /* materialize the new coloring. */
 612                 if(costs < best_costs) {
 613                         materialize_coloring(&changed);
 614                         best_costs = costs;
 615                         best_col   = col;
 616                         reject     = 0;
 617                 }
 618
 619                 /* We won't get the cloud any better so stop it. */
 620                 if(costs == 0)
 621                         break;
 622
 623                 if(reject)
 624                         reject_coloring(&changed);
 625         }
 626
 627         DB((env->dbg, LEVEL_2, "\tfinished cloud with costs %d\n", best_costs));
 628
 629         /* fix all cloud members */
 630         list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
 631                 ci->fixed = 1;
 632         }
 633
 634         {
 635                 char buf[256];
 636                 FILE *f;
 637
 638                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%F.dot", env->co->irg, env->co->cls->name, cloud->master);
 639                 if(f = fopen(buf, "wt")) {
 640                         be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
 641                         fclose(f);
 642                 }
 643         }
 644 }
 645
 646 static void try_affinity_node(co2_t *env, co2_irn_t *ci, col_t preferred, struct list_head *parent_changed)
 647 {
 648         ir_node *irn = ci->irn;
 649
 650         if(!color_is_fix(env, irn)) {
 651                 int n_regs      = env->co->cls->n_regs;
 652                 bitset_t *tried = bitset_alloca(n_regs);
 653                 bitset_t *adm   = bitset_alloca(n_regs);
 654                 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
 655
 656                 affinity_node_t *a = get_affinity_info(env->co, irn);
 657                 int best_costs  = cloud_costs(env, ci->cloud);
 658                 int best_col    = get_col(env, ci->irn);
 659
 660                 int i;
 661
 662                 determine_color_costs(env, ci, seq);
 663                 if(!INFEASIBLE(seq[preferred].costs))
 664                         seq[preferred].costs = INT_MIN;
 665
 666                 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
 667
 668                 for(i = 0; i < n_regs; ++i) {
 669                         col_t col = seq[i].col;
 670
 671                         struct list_head changed;
 672                         int ok, costs;
 673
 674                         INIT_LIST_HEAD(&changed);
 675                         ok  = change_color_single(env, irn, col, &changed, 0);
 676                         col = get_col(env, irn);
 677
 678                         if(!bitset_is_set(tried, col)) {
 679                                 neighb_t *n;
 680
 681                                 if(!ci->tmp_col) {
 682                                         ci->tmp_col   = col;
 683                                         ci->tmp_fixed = 1;
 684                                         list_add(&ci->changed_list, &changed);
 685                                 }
 686
 687                                 co_gs_foreach_neighb(a, n) {
 688                                         co2_irn_t *ni = get_co2_irn(env, n->irn);
 689                                         try_affinity_node(env, ni, col, &changed);
 690                                 }
 691
 692                                 examine_coloring(env, ci->cloud);
 693                                 reject_coloring(&changed);
 694
 695                                 bitset_set(tried, col);
 696                         }
 697                 }
 698         }
 699 }
 700 #endif
 701
 702 static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
 703 {
 704         int costs = cloud_costs(env, cloud);
 705
 706         if(costs < cloud->best_costs) {
 707                 int i;
 708
 709                 for(i = 0; i < cloud->n_memb; ++i)
 710                         cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
 711
 712                 cloud->best_costs = costs;
 713         }
 714 }
 715
 716 static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors)
 717 {
 718         col_t col = get_col(env, ci->irn);
 719         neighb_t *n;
 720         int balance = 0;
 721
 722         co_gs_foreach_neighb(ci->aff, n) {
 723                 col_t nc  = get_col(env, n->irn);
 724                 int fixed = color_is_fix(env, n->irn);
 725
 726                 if(nc == col)
 727                         balance -= n->costs;
 728                 else if(!fixed || !bitset_is_set(tried_colors, nc))
 729                         balance += n->costs;
 730         }
 731
 732         DBG((env->dbg, LEVEL_4, "\t\tbalance for changing %+F color %d\n", ci->irn, balance));
 733         return balance;
 734 }
 735
 736 static void adjust_start_colors(co2_t *env, co2_cloud_t *cloud, col_cost_pair_t *seq)
 737 {
 738         int n_regs    = env->co->cls->n_regs;
 739         bitset_t *adm = bitset_alloca(n_regs);
 740         bitset_pos_t col;
 741         int i;
 742
 743         for(i = 0; i < cloud->n_memb; ++i) {
 744                 co2_irn_t *ci = cloud->seq[i];
 745                 int n_constr;
 746
 747                 /* Prefer precolored neighbors. */
 748                 bitset_clear_all(adm);
 749                 admissible_colors(env, ci, adm);
 750                 n_constr = bitset_popcnt(adm);
 751
 752                 bitset_foreach(adm, col) {
 753                         seq[col].costs = add_saturated(seq[col].costs, -128 * (n_regs - n_constr));
 754                 }
 755
 756                 bitset_foreach_clear(adm, col) {
 757                         seq[col].costs = add_saturated(seq[col].costs, 128);
 758                 }
 759         }
 760
 761         admissible_colors(env, cloud->master, adm);
 762         bitset_flip_all(adm);
 763
 764         bitset_foreach(adm, col)
 765                 seq[col].costs = INT_MAX;
 766 }
 767
 768 static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
 769 {
 770         struct list_head changed;
 771         int res = 0;
 772
 773         if(index < cloud->n_memb) {
 774                 co2_irn_t *ci           = cloud->seq[index];
 775                 int n_regs              = env->co->cls->n_regs;
 776                 col_cost_pair_t *seq    = alloca(n_regs * sizeof(seq[0]));
 777                 bitset_t *cols_tried    = bitset_alloca(n_regs);
 778                 int done                = 0;
 779                 //col_cost_pair_t *single = alloca(n_regs * sizeof(seq[0]));
 780
 781                 int i;
 782
 783                 determine_color_costs(env, ci, seq);
 784                 if(index == 0)
 785                         adjust_start_colors(env, cloud, seq);
 786
 787 #if 0
 788                 if(index == 0) {
 789                         col_t col     = get_col(env, ci->irn);
 790                         int min_costs = INT_MAX;
 791                         int i;
 792
 793                         for(i = 0; i < n_regs; ++i)
 794                                 min_costs = MIN(min_costs, seq[i].costs);
 795
 796                         seq[col].costs = min_costs - 1;
 797                 }
 798 #endif
 799
 800                 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
 801
 802 #if 0
 803                 if(index == cloud->n_memb - 1) {
 804                         for(i = 0; i < n_regs; ++i)
 805                                 if(seq[i].costs >= 0)
 806                                         seq[i].costs = INT_MAX;
 807                 }
 808 #endif
 809
 810
 811                 for(i = 0; i < n_regs && !done; ++i) {
 812                         col_t col = seq[i].col;
 813                         int costs = seq[i].costs;
 814                         int ok;
 815
 816                         /*
 817                                 if all affinity neighbors fixed,
 818                                 try only color changes to affinity colors.
 819                                 all other colors do no good.
 820                         */
 821
 822                         DB((env->dbg, LEVEL_2, "\t%2{firm:indent}trying %+F index %d for color %d\n", index, ci->irn, index, col));
 823                         if(INFEASIBLE(costs)) {
 824                                 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
 825                                 break;
 826                         }
 827
 828                         bitset_set(cols_tried, col);
 829                         INIT_LIST_HEAD(&changed);
 830                         ok = change_color_single(env, ci->irn, col, &changed, 0);
 831                         DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", index, ok ? "ok" : "failed"));
 832
 833                         /* if we succeeded changing the color, we will figure out the next node. */
 834                         if(ok) {
 835                                 int finish;
 836
 837                                 /* materialize the coloring and fix the node's color. */
 838                                 ci->fixed = 1;
 839
 840                                 /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */
 841                                 finish = process_node(env, cloud, index + 1);
 842
 843                                 /* if this is the last node in the coloring sequence, examine the coloring */
 844                                 if(index == cloud->n_memb - 1) {
 845                                         examine_cloud_coloring(env, cloud);
 846                                         DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> current best coloring %d\n", index, cloud->best_costs));
 847                                         if(cloud->best_costs == cloud->inevit) {
 848                                                 done = 1;
 849                                                 res  = 1;
 850                                         }
 851                                 }
 852
 853                                 /* unfix the node. */
 854                                 reject_coloring(&changed);
 855                                 ci->fixed = 0;
 856
 857                                 if(finish || color_change_balance(env, ci, cols_tried) <= 0) {
 858                                         res  = finish;
 859                                         done = 1;
 860                                 }
 861                         }
 862
 863                 }
 864         }
 865
 866         return res;
 867 }
 868
 869 static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs)
 870 {
 871         int i;
 872         neighb_t *n;
 873
 874         i = 0;
 875         co_gs_foreach_neighb(ci->aff, n) {
 876                 nbs[i++] = get_co2_irn(env, n->irn);
 877         }
 878
 879         qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
 880         return nbs;
 881 }
 882
 883 static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud)
 884 {
 885         pdeq *q         = new_pdeq1(cloud->master);
 886         bitset_t *seen  = bitset_malloc(get_irg_last_idx(env->co->irg));
 887         co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0]));
 888         int i, j;
 889
 890         j = 0;
 891         bitset_set(seen, get_irn_idx(cloud->master->irn));
 892         while(!pdeq_empty(q)) {
 893                 co2_irn_t *curr = pdeq_getl(q);
 894
 895                 cloud->seq[j++] = curr;
 896                 get_neighb_arr(env, curr, nbs);
 897
 898                 for(i = 0; i < curr->aff->degree; ++i) {
 899                         co2_irn_t *ni = nbs[i];
 900                         int idx       = get_irn_idx(ni->irn);
 901                         if(!bitset_is_set(seen, idx)) {
 902                                 pdeq_putr(q, ni);
 903                                 bitset_set(seen, idx);
 904                         }
 905                 }
 906         }
 907
 908         del_pdeq(q);
 909         bitset_free(seen);
 910 }
 911
 912 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
 913 {
 914         be_ifg_t *ifg = env->co->cenv->ifg;
 915         co2_irn_t *ci = get_co2_irn(env, a->irn);
 916         int costs     = 0;
 917         neighb_t *n;
 918
 919         if(ci->visited >= env->visited)
 920                 return;
 921
 922         /* mark the node as visited and add it to the cloud. */
 923         ci->visited = env->visited;
 924         ci->cloud   = cloud;
 925         list_add(&ci->cloud_list, &cloud->members_head);
 926
 927         DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
 928
 929         /* determine the nodes costs */
 930         co_gs_foreach_neighb(a, n) {
 931                 costs += n->costs;
 932                 DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
 933                 if(be_ifg_connected(ifg, a->irn, n->irn))
 934                         cloud->inevit += n->costs;
 935         }
 936
 937         /* add the node's cost to the total costs of the cloud. */
 938         ci->costs          = costs;
 939         cloud->costs      += costs;
 940         cloud->max_degree  = MAX(cloud->max_degree, ci->aff->degree);
 941         cloud->n_memb++;
 942
 943         /* If this is the heaviest node in the cloud, set it as the cloud's master. */
 944         if(costs >= curr_costs) {
 945                 cloud->master = ci;
 946                 curr_costs    = costs;
 947         }
 948
 949         /* add all the neighbors of the node to the cloud. */
 950         co_gs_foreach_neighb(a, n) {
 951                 affinity_node_t *an = get_affinity_info(env->co, n->irn);
 952                 assert(an);
 953                 populate_cloud(env, cloud, an, curr_costs);
 954         }
 955 }
 956
 957 static void init_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a)
 958 {
 959         env->visited++;
 960         populate_cloud(env, cloud, a, 0);
 961
 962         cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
 963         cloud->seq       = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
 964         env->visited++;
 965         cloud->seq[0] = cloud->master;
 966         determine_coloring_sequence(env, cloud);
 967 }
 968
 969 static void process_cloud(co2_t *env, co2_cloud_t *cloud, int nr)
 970 {
 971         struct list_head changed;
 972         int i;
 973
 974         /* initialize the best coloring. */
 975         examine_cloud_coloring(env, cloud);
 976
 977         DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
 978         for(i = 0; i < cloud->n_memb; ++i) {
 979                 co2_irn_t *ci = cloud->seq[i];
 980                 DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn)));
 981         }
 982
 983         process_node(env, cloud, 0);
 984         DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
 985
 986         /* re-try the best coloring. */
 987         INIT_LIST_HEAD(&changed);
 988         for(i = 0; i < cloud->n_memb; ++i) {
 989                 co2_irn_t *ci = cloud->seq[i];
 990                 col_t col     = cloud->best_cols[i];
 991
 992                 int ok;
 993
 994                 DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col));
 995                 ok = change_color_single(env, ci->irn, col, &changed, 0);
 996                 assert(ok);
 997                 ci->fixed = 1;
 998         }
 999         materialize_coloring(&changed);
1000
1001         {
1002                 co2_irn_t *ci;
1003                 int some_fixed = 0;
1004                 for(ci = env->touched; ci; ci = ci->touched_next) {
1005                         if(ci->tmp_fixed) {
1006                                 some_fixed = 1;
1007                                 ir_printf("%+F is still temp fixed\n", ci->irn);
1008                         }
1009                 }
1010                 assert(!some_fixed);
1011         }
1012
1013         {
1014                 char buf[256];
1015                 FILE *f;
1016
1017                 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, nr);
1018                 if(f = fopen(buf, "wt")) {
1019                         be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1020                         fclose(f);
1021                 }
1022         }
1023
1024 }
1025
1026 static void process(co2_t *env)
1027 {
1028         affinity_node_t *a;
1029         co2_cloud_t *pos;
1030         co2_cloud_t **clouds;
1031         int n_clouds;
1032         int i;
1033         int init_costs  = 0;
1034         int all_costs   = 0;
1035         int final_costs = 0;
1036
1037
1038         n_clouds = 0;
1039         co_gs_foreach_aff_node(env->co, a) {
1040                 co2_irn_t *ci = get_co2_irn(env, a->irn);
1041
1042                 if(!ci->cloud) {
1043                         co2_cloud_t *cloud = new_cloud(env);
1044
1045                         init_cloud(env, cloud, a);
1046                         list_add(&cloud->list, &env->cloud_head);
1047                         n_clouds++;
1048                 }
1049         }
1050
1051         i = 0;
1052         clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1053         list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1054                 clouds[i++] = pos;
1055         qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
1056
1057         for(i = 0; i < n_clouds; ++i) {
1058                 init_costs  += cloud_costs(env, clouds[i]);
1059                 process_cloud(env, clouds[i], i);
1060                 all_costs   += clouds[i]->costs;
1061                 final_costs += clouds[i]->best_costs;
1062         }
1063
1064         DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1065
1066         xfree(clouds);
1067 }
1068
1069 static void writeback_colors(co2_t *env)
1070 {
1071         const arch_env_t *aenv = env->co->aenv;
1072         co2_irn_t *irn;
1073
1074         for(irn = env->touched; irn; irn = irn->touched_next) {
1075                 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1076                 arch_set_irn_register(aenv, irn->irn, reg);
1077         }
1078 }
1079
1080 /*
1081   ___ _____ ____   ____   ___ _____   ____                        _
1082  |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1083   | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1084   | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
1085  |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1086                                                            |_|            |___/
1087 */
1088
1089 static const char *get_dot_color_name(int col)
1090 {
1091         static const char *names[] = {
1092                 "blue",
1093                 "red",
1094                 "green",
1095                 "yellow",
1096                 "cyan",
1097                 "magenta",
1098                 "orange",
1099                 "chocolate",
1100                 "beige",
1101                 "navy",
1102                 "darkgreen",
1103                 "darkred",
1104                 "lightPink",
1105                 "chartreuse",
1106                 "lightskyblue",
1107                 "linen",
1108                 "pink",
1109                 "lightslateblue",
1110                 "mintcream",
1111                 "red",
1112                 "darkolivegreen",
1113                 "mediumblue",
1114                 "mistyrose",
1115                 "salmon",
1116                 "darkseagreen",
1117                 "mediumslateblue"
1118                 "moccasin",
1119                 "tomato",
1120                 "forestgreen",
1121                 "darkturquoise",
1122                 "palevioletred"
1123         };
1124
1125         return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1126 }
1127
1128 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1129 {
1130         arch_register_req_t req;
1131
1132         arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1133         if(arch_register_req_is(&req, limited))
1134                 return "diamond";
1135
1136         if(ci->fixed)
1137                 return "rectangle";
1138
1139         if(ci->tmp_fixed)
1140                 return "hexagon";
1141
1142         return "ellipse";
1143 }
1144
1145 static void ifg_dump_graph_attr(FILE *f, void *self)
1146 {
1147         fprintf(f, "overlay=false");
1148 }
1149
1150 static int ifg_is_dump_node(void *self, ir_node *irn)
1151 {
1152         co2_t *env = self;
1153         return !arch_irn_is(env->co->aenv, irn, ignore);
1154 }
1155
1156 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1157 {
1158         co2_t *env    = self;
1159         co2_irn_t *ci = get_co2_irn(env, irn);
1160
1161         ir_fprintf(f, "label=\"%+F,%d\" style=filled color=%s shape=%s", irn, ci->costs,
1162                 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1163 }
1164
1165 static void ifg_dump_at_end(FILE *file, void *self)
1166 {
1167         co2_t *env = self;
1168         affinity_node_t *a;
1169
1170         co_gs_foreach_aff_node(env->co, a) {
1171                 int idx = get_irn_idx(a->irn);
1172                 neighb_t *n;
1173
1174                 co_gs_foreach_neighb(a, n) {
1175                         int nidx = get_irn_idx(n->irn);
1176
1177                         if(idx < nidx) {
1178                                 const char *style = get_col(env, a->irn) == get_col(env, n->irn) ? "dashed" : "dotted";
1179                                 fprintf(file, "\tn%d -- n%d [label=\"%d\" style=%s weight=0.01];\n", idx, nidx, n->costs, style);
1180                         }
1181                 }
1182         }
1183
1184 }
1185
1186 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1187         ifg_is_dump_node,
1188         ifg_dump_graph_attr,
1189         ifg_dump_node_attr,
1190         NULL,
1191         NULL,
1192         ifg_dump_at_end
1193 };
1194
1195 void co_solve_heuristic_new(copy_opt_t *co)
1196 {
1197         co2_t env;
1198         FILE *f;
1199
1200         phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
1201         env.touched     = NULL;
1202         env.visited     = 0;
1203         env.co          = co;
1204         env.ignore_regs = bitset_alloca(co->cls->n_regs);
1205         arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1206         bitset_flip_all(env.ignore_regs);
1207         be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1208         FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1209         INIT_LIST_HEAD(&env.cloud_head);
1210
1211         if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) {
1212                 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1213                 fclose(f);
1214         }
1215
1216         process(&env);
1217
1218         if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) {
1219                 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1220                 fclose(f);
1221         }
1222
1223         writeback_colors(&env);
1224         phase_free(&env.ph);
1225 }