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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                12.04.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  */
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10 #ifdef HAVE_ALLOCA_H
  11 #include <alloca.h>
  12 #endif
  13 #ifdef HAVE_MALLOC_H
  14 #include <malloc.h>
  15 #endif
  16
  17 #include "execfreq.h"
  18 #include "xmalloc.h"
  19 #include "debug.h"
  20 #include "pmap.h"
  21 #include "irgraph.h"
  22 #include "irgwalk.h"
  23 #include "irprog.h"
  24 #include "irloop_t.h"
  25 #include "iredges_t.h"
  26 #include "phiclass.h"
  27 #include "irbitset.h"
  28 #include "irphase_t.h"
  29 #include "irprintf_t.h"
  30
  31
  32 #include "bearch.h"
  33 #include "benode_t.h"
  34 #include "beutil.h"
  35 #include "beifg_t.h"
  36 #include "becopyopt_t.h"
  37 #include "becopystat.h"
  38 #include "belive_t.h"
  39 #include "beinsn_t.h"
  40 #include "besched_t.h"
  41
  42 #define DUMP_BEFORE 1
  43 #define DUMP_AFTER  2
  44 #define DUMP_APPEL  4
  45 #define DUMP_ALL    2 * DUMP_APPEL - 1
  46
  47 #define COST_FUNC_FREQ     1
  48 #define COST_FUNC_LOOP     2
  49 #define COST_FUNC_ALL_ONE  3
  50
  51 static int dump_flags         = 0;
  52 static int style_flags        = 0;
  53 static int do_stats           = 0;
  54 static cost_fct_t cost_func   = co_get_costs_exec_freq;
  55 static int algo               = CO_ALGO_HEUR2;
  56
  57 #ifdef WITH_LIBCORE
  58 static const lc_opt_enum_mask_items_t dump_items[] = {
  59         { "before",  DUMP_BEFORE },
  60         { "after",   DUMP_AFTER  },
  61         { "appel",   DUMP_APPEL  },
  62         { "all",     DUMP_ALL    },
  63         { NULL,      0 }
  64 };
  65
  66 static const lc_opt_enum_mask_items_t style_items[] = {
  67         { "color",   CO_IFG_DUMP_COLORS },
  68         { "labels",  CO_IFG_DUMP_LABELS },
  69         { "constr",  CO_IFG_DUMP_CONSTR },
  70         { "shape",   CO_IFG_DUMP_SHAPE  },
  71         { "full",    2 * CO_IFG_DUMP_SHAPE - 1 },
  72         { NULL,      0 }
  73 };
  74
  75 static const lc_opt_enum_mask_items_t algo_items[] = {
  76         { "heur",   CO_ALGO_HEUR  },
  77         { "heur2",  CO_ALGO_HEUR2 },
  78         { "heur3",  CO_ALGO_HEUR3 },
  79         { "ilp",    CO_ALGO_ILP   },
  80         { NULL,     0 }
  81 };
  82
  83 static const lc_opt_enum_func_ptr_items_t cost_func_items[] = {
  84         { "freq",   co_get_costs_exec_freq },
  85         { "loop",   co_get_costs_loop_depth },
  86         { "one",    co_get_costs_all_one },
  87         { NULL,     0 }
  88 };
  89
  90 static lc_opt_enum_mask_var_t dump_var = {
  91         &dump_flags, dump_items
  92 };
  93
  94 static lc_opt_enum_mask_var_t style_var = {
  95         &style_flags, style_items
  96 };
  97
  98 static lc_opt_enum_mask_var_t algo_var = {
  99         &algo, algo_items
 100 };
 101
 102 static lc_opt_enum_func_ptr_var_t cost_func_var = {
 103         &cost_func, cost_func_items
 104 };
 105
 106 static const lc_opt_table_entry_t options[] = {
 107         LC_OPT_ENT_ENUM_INT      ("algo",  "select copy optimization algo (heur, heur2, heur3, ilp)", &algo_var),
 108         LC_OPT_ENT_ENUM_FUNC_PTR ("cost",  "select a cost function (freq, loop, one)",    &cost_func_var),
 109         LC_OPT_ENT_ENUM_MASK     ("dump",  "dump ifg before or after copy optimization",  &dump_var),
 110         LC_OPT_ENT_ENUM_MASK     ("style", "dump style for ifg dumping",                  &style_var),
 111         LC_OPT_ENT_BOOL          ("stats", "dump statistics after each optimization",     &do_stats),
 112         { NULL }
 113 };
 114
 115 /* Insert additional options registration functions here. */
 116 extern void be_co_ilp_register_options(lc_opt_entry_t *grp);
 117 extern void be_co2_register_options(lc_opt_entry_t *grp);
 118 extern void be_co3_register_options(lc_opt_entry_t *grp);
 119
 120 void co_register_options(lc_opt_entry_t *grp)
 121 {
 122         lc_opt_entry_t *co_grp = lc_opt_get_grp(grp, "co");
 123         lc_opt_add_table(co_grp, options);
 124
 125         be_co2_register_options(co_grp);
 126         be_co3_register_options(co_grp);
 127 #ifdef WITH_ILP
 128         be_co_ilp_register_options(co_grp);
 129 #endif
 130 }
 131 #endif
 132
 133
 134 #undef QUICK_AND_DIRTY_HACK
 135
 136 /******************************************************************************
 137     _____                           _
 138    / ____|                         | |
 139   | |  __  ___ _ __   ___ _ __ __ _| |
 140   | | |_ |/ _ \ '_ \ / _ \ '__/ _` | |
 141   | |__| |  __/ | | |  __/ | | (_| | |
 142    \_____|\___|_| |_|\___|_|  \__,_|_|
 143
 144  ******************************************************************************/
 145
 146 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 147
 148 void be_copy_opt_init(void) {
 149 }
 150
 151 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
 152 {
 153         const char *s1, *s2, *s3;
 154         int len;
 155         copy_opt_t *co;
 156
 157         FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
 158
 159         co = xcalloc(1, sizeof(*co));
 160         co->cenv      = chordal_env;
 161         co->aenv      = chordal_env->birg->main_env->arch_env;
 162         co->irg       = chordal_env->irg;
 163         co->cls       = chordal_env->cls;
 164         co->get_costs = get_costs;
 165
 166         s1 = get_irp_prog_name();
 167         s2 = get_entity_name(get_irg_entity(co->irg));
 168         s3 = chordal_env->cls->name;
 169         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
 170         co->name = xmalloc(len);
 171         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
 172
 173         return co;
 174 }
 175
 176 void free_copy_opt(copy_opt_t *co) {
 177         xfree(co->name);
 178         free(co);
 179 }
 180
 181 int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
 182         arch_register_req_t req;
 183         const arch_register_t *reg;
 184
 185         if (arch_irn_is(co->aenv, irn, ignore))
 186                 return 0;
 187
 188         reg = arch_get_irn_register(co->aenv, irn);
 189         if (arch_register_type_is(reg, ignore))
 190                 return 0;
 191
 192         if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(co->aenv, irn, &req))
 193                 return 1;
 194
 195         return 0;
 196 }
 197
 198 int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
 199         const ir_edge_t *edge;
 200         const arch_register_t *reg;
 201
 202         assert(0 && "Is buggy and obsolete. Do not use");
 203
 204         if (arch_irn_is(co->aenv, irn, ignore))
 205                 return 0;
 206
 207         reg = arch_get_irn_register(co->aenv, irn);
 208         if (arch_register_type_is(reg, ignore))
 209                 return 0;
 210
 211         foreach_out_edge(irn, edge) {
 212                 ir_node *n = edge->src;
 213
 214                 if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
 215                         arch_register_req_t req;
 216                         arch_get_register_req(co->aenv, &req, n, -1);
 217
 218                         if(is_Reg_Phi(n) ||
 219                            is_Perm(co->aenv, n) ||
 220                            (arch_register_req_is(&req, should_be_same) && req.other_same == irn)
 221                           )
 222                                 return 1;
 223                 }
 224         }
 225
 226         return 0;
 227 }
 228
 229 int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 230         int cost = 0;
 231         ir_loop *loop;
 232         ir_node *root_block = get_nodes_block(root);
 233
 234         if (is_Phi(root)) {
 235                 /* for phis the copies are placed in the corresponding pred-block */
 236                 loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
 237         } else {
 238                 /* a perm places the copy in the same block as it resides */
 239                 loop = get_irn_loop(root_block);
 240         }
 241         if (loop) {
 242                 int d = get_loop_depth(loop);
 243                 cost = d*d;
 244         }
 245         return cost+1;
 246 }
 247
 248 int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 249         ir_node *root_bl = get_nodes_block(root);
 250         ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
 251         unsigned long freq = get_block_execfreq_ulong(co->cenv->exec_freq, copy_bl);
 252         return freq > 0 ? (int) freq : 1;
 253 }
 254
 255
 256 int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 257         return 1;
 258 }
 259
 260 /******************************************************************************
 261    ____        _   _    _       _ _          _____ _
 262   / __ \      | | | |  | |     (_) |        / ____| |
 263  | |  | |_ __ | |_| |  | |_ __  _| |_ ___  | (___ | |_ ___  _ __ __ _  __ _  ___
 264  | |  | | '_ \| __| |  | | '_ \| | __/ __|  \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 265  | |__| | |_) | |_| |__| | | | | | |_\__ \  ____) | || (_) | | | (_| | (_| |  __/
 266   \____/| .__/ \__|\____/|_| |_|_|\__|___/ |_____/ \__\___/|_|  \__,_|\__, |\___|
 267         | |                                                            __/ |
 268         |_|                                                           |___/
 269  ******************************************************************************/
 270
 271 /**
 272  * Determines a maximum weighted independent set with respect to
 273  * the interference and conflict edges of all nodes in a qnode.
 274  */
 275 static int ou_max_ind_set_costs(unit_t *ou) {
 276         be_chordal_env_t *chordal_env = ou->co->cenv;
 277         ir_node **safe, **unsafe;
 278         int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
 279         bitset_t *curr;
 280         int max, pos, curr_weight, best_weight = 0;
 281
 282         /* assign the nodes into two groups.
 283          * safe: node has no interference, hence it is in every max stable set.
 284          * unsafe: node has an interference
 285          */
 286         safe = alloca((ou->node_count-1) * sizeof(*safe));
 287         safe_costs = 0;
 288         safe_count = 0;
 289         unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
 290         unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
 291         unsafe_count = 0;
 292         for(i=1; i<ou->node_count; ++i) {
 293                 int is_safe = 1;
 294                 for(o=1; o<ou->node_count; ++o) {
 295                         if (i==o)
 296                                 continue;
 297                         if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
 298                                 unsafe_costs[unsafe_count] = ou->costs[i];
 299                                 unsafe[unsafe_count] = ou->nodes[i];
 300                                 ++unsafe_count;
 301                                 is_safe = 0;
 302                                 break;
 303                         }
 304                 }
 305                 if (is_safe) {
 306                         safe_costs += ou->costs[i];
 307                         safe[safe_count++] = ou->nodes[i];
 308                 }
 309         }
 310
 311
 312         /* now compute the best set out of the unsafe nodes*/
 313         if (unsafe_count > MIS_HEUR_TRIGGER) {
 314                 bitset_t *best = bitset_alloca(unsafe_count);
 315                 /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
 316                 for (i=0; i<unsafe_count; ++i) {
 317                         bitset_set(best, i);
 318                         /* check if it is a stable set */
 319                         for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
 320                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
 321                                         bitset_clear(best, i); /* clear the bit and try next one */
 322                                         break;
 323                                 }
 324                 }
 325                 /* compute the weight */
 326                 bitset_foreach(best, pos)
 327                         best_weight += unsafe_costs[pos];
 328         } else {
 329                 /* Exact Algorithm: Brute force */
 330                 curr = bitset_alloca(unsafe_count);
 331                 bitset_set_all(curr);
 332                 while ((max = bitset_popcnt(curr)) != 0) {
 333                         /* check if curr is a stable set */
 334                         for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
 335                                 for (o=bitset_next_set(curr, i+1); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to qnode_max_ind_set(): NOT (curr, i) */
 336                                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
 337                                                         goto no_stable_set;
 338
 339                         /* if we arrive here, we have a stable set */
 340                         /* compute the weigth of the stable set*/
 341                         curr_weight = 0;
 342                         bitset_foreach(curr, pos)
 343                                 curr_weight += unsafe_costs[pos];
 344
 345                         /* any better ? */
 346                         if (curr_weight > best_weight) {
 347                                 best_weight = curr_weight;
 348                         }
 349
 350         no_stable_set:
 351                         bitset_minus1(curr);
 352                 }
 353         }
 354
 355         return safe_costs+best_weight;
 356 }
 357
 358 static void co_collect_units(ir_node *irn, void *env) {
 359         copy_opt_t *co = env;
 360         unit_t *unit;
 361         arch_register_req_t req;
 362
 363         if (!is_curr_reg_class(co, irn))
 364                 return;
 365         if (!co_is_optimizable_root(co, irn))
 366                 return;
 367
 368         /* Init a new unit */
 369         unit = xcalloc(1, sizeof(*unit));
 370         unit->co = co;
 371         unit->node_count = 1;
 372         INIT_LIST_HEAD(&unit->queue);
 373
 374         /* Phi with some/all of its arguments */
 375         if (is_Reg_Phi(irn)) {
 376                 int i, arity;
 377
 378                 /* init */
 379                 arity = get_irn_arity(irn);
 380                 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
 381                 unit->costs = xmalloc((arity+1) * sizeof(*unit->costs));
 382                 unit->nodes[0] = irn;
 383
 384                 /* fill */
 385                 for (i=0; i<arity; ++i) {
 386                         int o, arg_pos;
 387                         ir_node *arg = get_irn_n(irn, i);
 388
 389                         assert(is_curr_reg_class(co, arg) && "Argument not in same register class.");
 390                         if (arg == irn)
 391                                 continue;
 392                         if (nodes_interfere(co->cenv, irn, arg)) {
 393                                 unit->inevitable_costs += co->get_costs(co, irn, arg, i);
 394                                 continue;
 395                         }
 396
 397                         /* Else insert the argument of the phi to the members of this ou */
 398                         DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
 399
 400                         /* Check if arg has occurred at a prior position in the arg/list */
 401                         arg_pos = 0;
 402                         for (o=0; o<unit->node_count; ++o)
 403                                 if (unit->nodes[o] == arg) {
 404                                         arg_pos = o;
 405                                         break;
 406                                 }
 407
 408                         if (!arg_pos) { /* a new argument */
 409                                 /* insert node, set costs */
 410                                 unit->nodes[unit->node_count] = arg;
 411                                 unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
 412                                 unit->node_count++;
 413                         } else { /* arg has occured before in same phi */
 414                                 /* increase costs for existing arg */
 415                                 unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
 416                         }
 417                 }
 418                 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
 419                 unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
 420         } else
 421
 422         /* Proj of a perm with corresponding arg */
 423         if (is_Perm_Proj(co->aenv, irn)) {
 424                 assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 425                 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 426                 unit->costs = xmalloc(2 * sizeof(*unit->costs));
 427                 unit->node_count = 2;
 428                 unit->nodes[0] = irn;
 429                 unit->nodes[1] = get_Perm_src(irn);
 430                 unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
 431         } else
 432
 433         /* Src == Tgt of a 2-addr-code instruction */
 434         if (is_2addr_code(co->aenv, irn, &req)) {
 435                 ir_node *other = req.other_same;
 436                 if (!nodes_interfere(co->cenv, irn, other)) {
 437                         unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 438                         unit->costs = xmalloc(2 * sizeof(*unit->costs));
 439                         unit->node_count = 2;
 440                         unit->nodes[0] = irn;
 441                         unit->nodes[1] = other;
 442                         unit->costs[1] = co->get_costs(co, irn, other, -1);
 443                 }
 444         } else
 445                 assert(0 && "This is not an optimizable node!");
 446
 447         /* Insert the new unit at a position according to its costs */
 448         if (unit->node_count > 1) {
 449                 int i;
 450                 struct list_head *tmp;
 451
 452                 /* Determine the maximum costs this unit can cause: all_nodes_cost */
 453                 for(i=1; i<unit->node_count; ++i) {
 454                         unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
 455                         unit->all_nodes_costs += unit->costs[i];
 456                 }
 457
 458                 /* Determine the minimal costs this unit will cause: min_nodes_costs */
 459                 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
 460                 /* Insert the new ou according to its sort_key */
 461                 tmp = &co->units;
 462                 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
 463                         tmp = tmp->next;
 464                 list_add(&unit->units, tmp);
 465         } else {
 466                 free(unit);
 467         }
 468 }
 469
 470 #ifdef QUICK_AND_DIRTY_HACK
 471
 472 static int compare_ous(const void *k1, const void *k2) {
 473         const unit_t *u1 = *((const unit_t **) k1);
 474         const unit_t *u2 = *((const unit_t **) k2);
 475         int i, o, u1_has_constr, u2_has_constr;
 476         arch_register_req_t req;
 477         const arch_env_t *aenv = u1->co->aenv;
 478
 479         /* Units with constraints come first */
 480         u1_has_constr = 0;
 481         for (i=0; i<u1->node_count; ++i) {
 482                 arch_get_register_req(aenv, &req, u1->nodes[i], -1);
 483                 if (arch_register_req_is(&req, limited)) {
 484                         u1_has_constr = 1;
 485                         break;
 486                 }
 487         }
 488
 489         u2_has_constr = 0;
 490         for (i=0; i<u2->node_count; ++i) {
 491                 arch_get_register_req(aenv, &req, u2->nodes[i], -1);
 492                 if (arch_register_req_is(&req, limited)) {
 493                         u2_has_constr = 1;
 494                         break;
 495                 }
 496         }
 497
 498         if (u1_has_constr != u2_has_constr)
 499                 return u2_has_constr - u1_has_constr;
 500
 501         /* Now check, whether the two units are connected */
 502 #if 0
 503         for (i=0; i<u1->node_count; ++i)
 504                 for (o=0; o<u2->node_count; ++o)
 505                         if (u1->nodes[i] == u2->nodes[o])
 506                                 return 0;
 507 #endif
 508
 509         /* After all, the sort key decides. Greater keys come first. */
 510         return u2->sort_key - u1->sort_key;
 511
 512 }
 513
 514 /**
 515  * Sort the ou's according to constraints and their sort_key
 516  */
 517 static void co_sort_units(copy_opt_t *co) {
 518         int i, count = 0, costs;
 519         unit_t *ou, **ous;
 520
 521         /* get the number of ous, remove them form the list and fill the array */
 522         list_for_each_entry(unit_t, ou, &co->units, units)
 523                 count++;
 524         ous = alloca(count * sizeof(*ous));
 525
 526         costs = co_get_max_copy_costs(co);
 527
 528         i = 0;
 529         list_for_each_entry(unit_t, ou, &co->units, units)
 530                 ous[i++] = ou;
 531
 532         INIT_LIST_HEAD(&co->units);
 533
 534         assert(count == i && list_empty(&co->units));
 535
 536         for (i=0; i<count; ++i)
 537                 ir_printf("%+F\n", ous[i]->nodes[0]);
 538
 539         qsort(ous, count, sizeof(*ous), compare_ous);
 540
 541         ir_printf("\n\n");
 542         for (i=0; i<count; ++i)
 543                 ir_printf("%+F\n", ous[i]->nodes[0]);
 544
 545         /* reinsert into list in correct order */
 546         for (i=0; i<count; ++i)
 547                 list_add_tail(&ous[i]->units, &co->units);
 548
 549         assert(costs == co_get_max_copy_costs(co));
 550 }
 551 #endif
 552
 553 void co_build_ou_structure(copy_opt_t *co) {
 554         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
 555         INIT_LIST_HEAD(&co->units);
 556         irg_walk_graph(co->irg, co_collect_units, NULL, co);
 557 #ifdef QUICK_AND_DIRTY_HACK
 558         co_sort_units(co);
 559 #endif
 560 }
 561
 562 void co_free_ou_structure(copy_opt_t *co) {
 563         unit_t *curr, *tmp;
 564         ASSERT_OU_AVAIL(co);
 565         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 566                 xfree(curr->nodes);
 567                 xfree(curr->costs);
 568                 xfree(curr);
 569         }
 570         co->units.next = NULL;
 571 }
 572
 573 /* co_solve_heuristic() is implemented in becopyheur.c */
 574
 575 int co_get_max_copy_costs(const copy_opt_t *co) {
 576         int i, res = 0;
 577         unit_t *curr;
 578
 579         ASSERT_OU_AVAIL(co);
 580
 581         list_for_each_entry(unit_t, curr, &co->units, units) {
 582                 res += curr->inevitable_costs;
 583                 for (i=1; i<curr->node_count; ++i)
 584                         res += curr->costs[i];
 585         }
 586         return res;
 587 }
 588
 589 int co_get_inevit_copy_costs(const copy_opt_t *co) {
 590         int res = 0;
 591         unit_t *curr;
 592
 593         ASSERT_OU_AVAIL(co);
 594
 595         list_for_each_entry(unit_t, curr, &co->units, units)
 596                 res += curr->inevitable_costs;
 597         return res;
 598 }
 599
 600 int co_get_copy_costs(const copy_opt_t *co) {
 601         int i, res = 0;
 602         unit_t *curr;
 603
 604         ASSERT_OU_AVAIL(co);
 605
 606         list_for_each_entry(unit_t, curr, &co->units, units) {
 607                 int root_col = get_irn_col(co, curr->nodes[0]);
 608                 DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
 609                 res += curr->inevitable_costs;
 610                 for (i=1; i<curr->node_count; ++i) {
 611                         int arg_col = get_irn_col(co, curr->nodes[i]);
 612                         if (root_col != arg_col) {
 613                                 DBG((dbg, LEVEL_1, "  %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
 614                                 res += curr->costs[i];
 615                         }
 616                 }
 617         }
 618         return res;
 619 }
 620
 621 int co_get_lower_bound(const copy_opt_t *co) {
 622         int res = 0;
 623         unit_t *curr;
 624
 625         ASSERT_OU_AVAIL(co);
 626
 627         list_for_each_entry(unit_t, curr, &co->units, units)
 628                 res += curr->inevitable_costs + curr->min_nodes_costs;
 629         return res;
 630 }
 631
 632 /******************************************************************************
 633    _____                 _        _____ _
 634   / ____|               | |      / ____| |
 635  | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 636  | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 637  | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
 638   \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
 639                   | |                                       __/ |
 640                   |_|                                      |___/
 641  ******************************************************************************/
 642
 643 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
 644         const affinity_node_t *n1 = k1;
 645         const affinity_node_t *n2 = k2;
 646
 647         return (n1->irn != n2->irn);
 648 }
 649
 650 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 651         affinity_node_t new_node, *node;
 652         neighb_t new_nbr, *nbr;
 653         int allocnew;
 654
 655         new_node.irn        = n1;
 656         new_node.degree     = 0;
 657         new_node.neighbours = NULL;
 658         node = set_insert(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn));
 659
 660         allocnew = 1;
 661         for (nbr = node->neighbours; nbr; nbr = nbr->next)
 662                 if (nbr->irn == n2) {
 663                         allocnew = 0;
 664                         break;
 665                 }
 666
 667         /* if we did not find n2 in n1's neighbourhood insert it */
 668         if (allocnew) {
 669                 obstack_grow(&co->obst, &new_nbr, sizeof(new_nbr));
 670                 nbr = obstack_finish(&co->obst);
 671                 nbr->irn   = n2;
 672                 nbr->costs = 0;
 673                 nbr->next  = node->neighbours;
 674                 node->neighbours = nbr;
 675                 node->degree++;
 676         }
 677
 678         /* now nbr points to n1's neighbour-entry of n2 */
 679         nbr->costs += costs;
 680 }
 681
 682 static INLINE void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 683         if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
 684                 add_edge(co, n1, n2, costs);
 685                 add_edge(co, n2, n1, costs);
 686         }
 687 }
 688
 689 static void build_graph_walker(ir_node *irn, void *env) {
 690         copy_opt_t *co = env;
 691         int pos, max;
 692         arch_register_req_t req;
 693         const arch_register_t *reg;
 694
 695         if (!is_curr_reg_class(co, irn) || arch_irn_is(co->aenv, irn, ignore))
 696                 return;
 697
 698         reg = arch_get_irn_register(co->aenv, irn);
 699         if (arch_register_type_is(reg, ignore))
 700                 return;
 701
 702         /* Phis */
 703         if (is_Reg_Phi(irn))
 704                 for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 705                         ir_node *arg = get_irn_n(irn, pos);
 706                         add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
 707                 }
 708
 709         /* Perms */
 710         else if (is_Perm_Proj(co->aenv, irn)) {
 711                 ir_node *arg = get_Perm_src(irn);
 712                 add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
 713         }
 714
 715         /* 2-address code */
 716         else if (is_2addr_code(co->aenv, irn, &req))
 717                 add_edges(co, irn, req.other_same, co->get_costs(co, irn, req.other_same, 0));
 718 }
 719
 720 void co_build_graph_structure(copy_opt_t *co) {
 721         obstack_init(&co->obst);
 722         co->nodes = new_set(compare_affinity_node_t, 32);
 723
 724         irg_walk_graph(co->irg, build_graph_walker, NULL, co);
 725 }
 726
 727 void co_free_graph_structure(copy_opt_t *co) {
 728         ASSERT_GS_AVAIL(co);
 729
 730         del_set(co->nodes);
 731         obstack_free(&co->obst, NULL);
 732         co->nodes = NULL;
 733 }
 734
 735 /* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */
 736
 737 int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) {
 738         affinity_node_t new_node, *n;
 739
 740         ASSERT_GS_AVAIL(co);
 741
 742         new_node.irn = irn;
 743         n = set_find(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn));
 744         if (n) {
 745                 return (n->degree > 0);
 746         } else
 747                 return 0;
 748 }
 749
 750 void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 751 {
 752         be_ifg_t *ifg  = co->cenv->ifg;
 753         int *color_map = alloca(co->cls->n_regs * sizeof(color_map[0]));
 754         bitset_t *adm  = bitset_alloca(co->cls->n_regs);
 755
 756         ir_node *irn;
 757         void *it, *nit;
 758         int i, n, n_regs;
 759
 760         n_regs = 0;
 761         for(i = 0; i < co->cls->n_regs; ++i) {
 762                 const arch_register_t *reg = &co->cls->regs[i];
 763                 color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_regs++;
 764         }
 765
 766         /*
 767          * n contains the first node number.
 768          * the values below n are the pre-colored register nodes
 769          */
 770
 771         it  = be_ifg_nodes_iter_alloca(ifg);
 772         nit = be_ifg_neighbours_iter_alloca(ifg);
 773
 774         n = n_regs;
 775         be_ifg_foreach_node(ifg, it, irn) {
 776                 if(!arch_irn_is(co->aenv, irn, ignore))
 777                         set_irn_link(irn, INT_TO_PTR(n++));
 778         }
 779
 780         fprintf(f, "%d %d\n", n, n_regs);
 781
 782         be_ifg_foreach_node(ifg, it, irn) {
 783                 if(!arch_irn_is(co->aenv, irn, ignore)) {
 784                         int idx            = PTR_TO_INT(get_irn_link(irn));
 785                         affinity_node_t *a = get_affinity_info(co, irn);
 786
 787                         arch_register_req_t req;
 788                         ir_node *adj;
 789
 790                         arch_get_register_req(co->aenv, &req, irn, BE_OUT_POS(0));
 791                         if(arch_register_req_is(&req, limited)) {
 792                                 bitset_clear_all(adm);
 793                                 req.limited(req.limited_env, adm);
 794                                 for(i = 0; i < co->cls->n_regs; ++i)
 795                                         if(!bitset_is_set(adm, i) && color_map[i] >= 0)
 796                                                 fprintf(f, "%d %d -1\n", color_map[i], idx);
 797
 798                         }
 799
 800
 801                         be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
 802                                 if(!arch_irn_is(co->aenv, adj, ignore)) {
 803                                         int adj_idx = PTR_TO_INT(get_irn_link(adj));
 804                                         if(idx < adj_idx)
 805                                                 fprintf(f, "%d %d -1\n", idx, adj_idx);
 806                                 }
 807                         }
 808
 809                         if(a) {
 810                                 neighb_t *n;
 811
 812                                 co_gs_foreach_neighb(a, n) {
 813                                         if(!arch_irn_is(co->aenv, n->irn, ignore)) {
 814                                                 int n_idx = PTR_TO_INT(get_irn_link(n->irn));
 815                                                 if(idx < n_idx)
 816                                                         fprintf(f, "%d %d %d\n", idx, n_idx, n->costs);
 817                                         }
 818                                 }
 819                         }
 820                 }
 821         }
 822 }
 823
 824 typedef struct _appel_clique_walker_t {
 825         phase_t ph;
 826         const copy_opt_t *co;
 827         int curr_nr;
 828         int node_count;
 829         FILE *f;
 830         int dumb;
 831         int *color_map;
 832         struct obstack obst;
 833 } appel_clique_walker_t;
 834
 835 typedef struct _appel_block_info_t {
 836         int *live_end_nr;
 837         int *live_in_nr;
 838         int *phi_nr;
 839         ir_node **live_end;
 840         ir_node **live_in;
 841         ir_node **phi;
 842         int n_live_end;
 843         int n_live_in;
 844         int n_phi;
 845 } appel_block_info_t;
 846
 847 static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
 848 {
 849 #if 0
 850         double freq = get_block_execfreq(env->co->cenv->execfreq, bl);
 851         int res = (int) freq;
 852         return res == 0 ? 1 : res;
 853 #else
 854         ir_loop *loop = get_irn_loop(bl);
 855         if(loop) {
 856                 int d = get_loop_depth(loop);
 857                 return 1 + d * d;
 858         }
 859         return 1;
 860 #endif
 861 }
 862
 863 static void *appel_clique_walker_irn_init(phase_t *phase, ir_node *irn, void *old)
 864 {
 865         appel_block_info_t *res = NULL;
 866
 867         if(is_Block(irn)) {
 868                 appel_clique_walker_t *d = (void *) phase;
 869                 res = phase_alloc(phase, sizeof(res[0]));
 870                 res->phi_nr      = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
 871                 res->live_end_nr = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
 872                 res->live_in_nr  = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in_nr));
 873                 res->live_end    = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end));
 874                 res->live_in     = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
 875                 res->phi         = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
 876         }
 877
 878         return res;
 879 }
 880
 881 typedef struct _insn_list_t {
 882         be_insn_t *insn;
 883         struct list_head list;
 884 } insn_list_t;
 885
 886 static int appel_get_live_end_nr(appel_clique_walker_t *env, ir_node *bl, ir_node *irn)
 887 {
 888         appel_block_info_t *bli = phase_get_irn_data(&env->ph, bl);
 889         int i;
 890
 891         for(i = 0; i < bli->n_live_end; ++i)
 892                 if(bli->live_end[i] == irn)
 893                         return bli->live_end_nr[i];
 894
 895         return -1;
 896 }
 897
 898 static int appel_dump_clique(appel_clique_walker_t *env, pset *live, ir_node *bl, int curr_nr, int start_nr)
 899 {
 900         ir_node **live_arr = alloca(env->co->cls->n_regs * sizeof(live_arr[0]));
 901         ir_node *irn;
 902         int n_live;
 903         int j;
 904
 905         n_live = 0;
 906         foreach_pset(live, irn)
 907                 live_arr[n_live++] = irn;
 908
 909         /* dump the live after clique */
 910         if(!env->dumb) {
 911                 for(j = 0; j < n_live; ++j) {
 912                         int k;
 913
 914                         for(k = j + 1; k < n_live; ++k) {
 915                                 fprintf(env->f, "%d %d -1 ", curr_nr + j, curr_nr + k);
 916                         }
 917                         fprintf(env->f, "\n");
 918                 }
 919         }
 920
 921         /* dump the affinities */
 922         for(j = 0; !env->dumb && j < n_live; ++j) {
 923                 ir_node *irn = live_arr[j];
 924                 int old_nr = PTR_TO_INT(get_irn_link(irn));
 925
 926                 /* if the node was already live in the last insn dump the affinity */
 927                 if(old_nr > start_nr) {
 928                         int weight = appel_aff_weight(env, bl);
 929                         fprintf(env->f, "%d %d %d\n", old_nr, curr_nr + j, weight);
 930                 }
 931         }
 932
 933         /* set the current numbers into the link field. */
 934         for(j = 0; j < n_live; ++j) {
 935                 ir_node *irn = live_arr[j];
 936                 set_irn_link(irn, INT_TO_PTR(curr_nr + j));
 937         }
 938
 939         return curr_nr + n_live;
 940 }
 941
 942 static void appel_walker(ir_node *bl, void *data)
 943 {
 944         appel_clique_walker_t *env = data;
 945         appel_block_info_t *bli    = phase_get_or_set_irn_data(&env->ph, bl);
 946         struct obstack *obst       = &env->obst;
 947         void *base                 = obstack_base(obst);
 948         pset *live                 = pset_new_ptr_default();
 949
 950         int n_insns  = 0;
 951         int n_nodes  = 0;
 952         int start_nr = env->curr_nr;
 953         int curr_nr  = start_nr;
 954
 955         be_insn_env_t insn_env;
 956         int i, j;
 957         ir_node *irn;
 958         be_insn_t **insns;
 959
 960         insn_env.aenv = env->co->aenv;
 961         insn_env.cls  = env->co->cls;
 962         insn_env.obst = obst;
 963         insn_env.ignore_colors = env->co->cenv->ignore_colors;
 964
 965         /* Guess how many insns will be in this block. */
 966         sched_foreach(bl, irn)
 967                 n_nodes++;
 968
 969         bli->n_phi = 0;
 970         insns = malloc(n_nodes * sizeof(insns[0]));
 971
 972         /* Put all insns in an array. */
 973         irn = sched_first(bl);
 974         while(!sched_is_end(irn)) {
 975                 be_insn_t *insn;
 976                 insn = be_scan_insn(&insn_env, irn);
 977                 insns[n_insns++] = insn;
 978                 irn = insn->next_insn;
 979         }
 980
 981         DBG((env->co->cenv->dbg, LEVEL_2, "%+F\n", bl));
 982         be_liveness_end_of_block(env->co->cenv->lv, env->co->aenv, env->co->cls, bl, live);
 983
 984         /* Generate the bad and ugly. */
 985         for(i = n_insns - 1; i >= 0; --i) {
 986                 be_insn_t *insn = insns[i];
 987
 988                 /* The first live set has to be saved in the block border set. */
 989                 if(i == n_insns - 1) {
 990                         j = 0;
 991                         foreach_pset(live, irn) {
 992                                 bli->live_end[j]    = irn;
 993                                 bli->live_end_nr[j] = curr_nr + j;
 994                                 ++j;
 995                         }
 996                         bli->n_live_end = j;
 997                 }
 998
 999                 if(!env->dumb) {
1000                         for(j = 0; j < insn->use_start; ++j) {
1001                                 ir_node *op   = insn->ops[j].carrier;
1002                                 bitset_t *adm = insn->ops[j].regs;
1003                                 int k;
1004                                 int nr;
1005
1006                                 if(!insn->ops[j].has_constraints)
1007                                         continue;
1008
1009                                 nr = 0;
1010                                 foreach_pset(live, irn) {
1011                                         if(irn == op) {
1012                                                 pset_break(live);
1013                                                 break;
1014                                         }
1015                                         ++nr;
1016                                 }
1017
1018                                 assert(nr < pset_count(live));
1019
1020                                 for(k = 0; k < env->co->cls->n_regs; ++k) {
1021                                         int mapped_col = env->color_map[k];
1022                                         if(mapped_col >= 0 && !bitset_is_set(adm, k) && !bitset_is_set(env->co->cenv->ignore_colors, k))
1023                                                 fprintf(env->f, "%d %d -1\n", curr_nr + nr, mapped_col);
1024                                 }
1025                         }
1026                 }
1027
1028                 /* dump the clique and update the stuff. */
1029                 curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
1030
1031                 /* remove all defs. */
1032                 for(j = 0; j < insn->use_start; ++j)
1033                         pset_remove_ptr(live, insn->ops[j].carrier);
1034
1035                 if(is_Phi(insn->irn) && arch_irn_consider_in_reg_alloc(env->co->aenv, env->co->cls, insn->irn)) {
1036                         bli->phi[bli->n_phi]    = insn->irn;
1037                         bli->phi_nr[bli->n_phi] = PTR_TO_INT(get_irn_link(insn->irn));
1038                         bli->n_phi++;
1039                 }
1040
1041                 /* add all uses */
1042                 else
1043                         for(j = insn->use_start; j < insn->n_ops; ++j)
1044                                 pset_insert_ptr(live, insn->ops[j].carrier);
1045         }
1046
1047         /* print the start clique. */
1048         curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
1049
1050         i = 0;
1051         foreach_pset(live, irn) {
1052                 bli->live_in[i]    = irn;
1053                 bli->live_in_nr[i] = PTR_TO_INT(get_irn_link(irn));
1054                 ++i;
1055         }
1056         bli->n_live_in = i;
1057
1058         del_pset(live);
1059         free(insns);
1060         obstack_free(obst, base);
1061         env->curr_nr = curr_nr;
1062 }
1063
1064 static void appel_inter_block_aff(ir_node *bl, void *data)
1065 {
1066         appel_clique_walker_t *env = data;
1067         appel_block_info_t *bli    = phase_get_irn_data(&env->ph, bl);
1068
1069         int i, j, n;
1070
1071         for(i = 0; i < bli->n_live_in; ++i) {
1072                 ir_node *irn = bli->live_in[i];
1073
1074                 for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) {
1075                         ir_node *pred  = get_Block_cfgpred_block(bl, j);
1076                         appel_block_info_t *pred_bli = phase_get_irn_data(&env->ph, pred);
1077
1078                         int nr = appel_get_live_end_nr(env, pred, irn);
1079                         assert(nr >= 0);
1080                         fprintf(env->f, "%d %d 1\n", bli->live_in_nr[i], nr);
1081                 }
1082         }
1083
1084         for(i = 0; i < bli->n_phi; ++i) {
1085                 ir_node *irn = bli->phi[i];
1086
1087                 for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) {
1088                         ir_node *pred  = get_Block_cfgpred_block(bl, j);
1089                         appel_block_info_t *pred_bli = phase_get_irn_data(&env->ph, pred);
1090                         ir_node *op = get_irn_n(irn, j);
1091
1092                         int nr = appel_get_live_end_nr(env, pred, op);
1093                         assert(nr >= 0);
1094                         fprintf(env->f, "%d %d 1\n", bli->phi_nr[i], nr);
1095                 }
1096         }
1097
1098 }
1099
1100 void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f)
1101 {
1102         int i;
1103         int n_colors;
1104         appel_clique_walker_t env;
1105         bitset_t *adm = bitset_alloca(co->cls->n_regs);
1106
1107         be_liveness_recompute(co->cenv->lv);
1108         obstack_init(&env.obst);
1109         phase_init(&env.ph, "appel_clique_dumper", co->irg, PHASE_DEFAULT_GROWTH, appel_clique_walker_irn_init);
1110         env.curr_nr = co->cls->n_regs;
1111         env.co = co;
1112         env.f = f;
1113
1114         bitset_copy(adm, co->cenv->ignore_colors);
1115         bitset_flip_all(adm);
1116
1117         /* Make color map. */
1118         env.color_map = alloca(co->cls->n_regs * sizeof(env.color_map[0]));
1119         for(i = 0, n_colors = 0; i < co->cls->n_regs; ++i) {
1120                 const arch_register_t *reg = &co->cls->regs[i];
1121                 env.color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_colors++;
1122         }
1123
1124         env.dumb = 1;
1125         env.curr_nr = n_colors;
1126         irg_block_walk_graph(co->irg, firm_clear_link, NULL, NULL);
1127         irg_block_walk_graph(co->irg, appel_walker, NULL, &env);
1128
1129         fprintf(f, "%d %d\n", env.curr_nr, n_colors);
1130
1131         /* make the first k nodes interfere */
1132         for(i = 0; i < n_colors; ++i) {
1133                 int j;
1134                 for(j = i + 1; j < n_colors; ++j)
1135                         fprintf(f, "%d %d -1 ", i, j);
1136                 fprintf(f, "\n");
1137         }
1138
1139         env.dumb = 0;
1140         env.curr_nr = n_colors;
1141         irg_block_walk_graph(co->irg, firm_clear_link, NULL, NULL);
1142         irg_block_walk_graph(co->irg, appel_walker, NULL, &env);
1143         irg_block_walk_graph(co->irg, appel_inter_block_aff, NULL, &env);
1144         obstack_free(&env.obst, NULL);
1145 }
1146
1147 /*
1148          ___ _____ ____   ____   ___ _____   ____                        _
1149         |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1150          | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1151          | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
1152         |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1153                                                                   |_|            |___/
1154 */
1155
1156 static const char *get_dot_color_name(int col)
1157 {
1158         static const char *names[] = {
1159                 "blue",
1160                 "red",
1161                 "green",
1162                 "yellow",
1163                 "cyan",
1164                 "magenta",
1165                 "orange",
1166                 "chocolate",
1167                 "beige",
1168                 "navy",
1169                 "darkgreen",
1170                 "darkred",
1171                 "lightPink",
1172                 "chartreuse",
1173                 "lightskyblue",
1174                 "linen",
1175                 "pink",
1176                 "lightslateblue",
1177                 "mintcream",
1178                 "red",
1179                 "darkolivegreen",
1180                 "mediumblue",
1181                 "mistyrose",
1182                 "salmon",
1183                 "darkseagreen",
1184                 "mediumslateblue"
1185                 "moccasin",
1186                 "tomato",
1187                 "forestgreen",
1188                 "darkturquoise",
1189                 "palevioletred"
1190         };
1191
1192         return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1193 }
1194
1195 typedef struct _co_ifg_dump_t {
1196         const copy_opt_t *co;
1197         unsigned flags;
1198 } co_ifg_dump_t;
1199
1200 static void ifg_dump_graph_attr(FILE *f, void *self)
1201 {
1202         fprintf(f, "overlap=scale");
1203 }
1204
1205 static int ifg_is_dump_node(void *self, ir_node *irn)
1206 {
1207         co_ifg_dump_t *cod = self;
1208         return !arch_irn_is(cod->co->aenv, irn, ignore);
1209 }
1210
1211 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1212 {
1213         co_ifg_dump_t *env         = self;
1214         const arch_register_t *reg = arch_get_irn_register(env->co->aenv, irn);
1215         arch_register_req_t req;
1216         int limited;
1217
1218         arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
1219         limited = arch_register_req_is(&req, limited);
1220
1221         if(env->flags & CO_IFG_DUMP_LABELS) {
1222                 ir_fprintf(f, "label=\"%+F", irn);
1223
1224                 if((env->flags & CO_IFG_DUMP_CONSTR) && limited) {
1225                         bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
1226                         req.limited(req.limited_env, bs);
1227                         ir_fprintf(f, "\\n%B", bs);
1228                 }
1229                 ir_fprintf(f, "\" ");
1230         }
1231
1232         else
1233                 fprintf(f, "label=\"\"" );
1234
1235         if(env->flags & CO_IFG_DUMP_SHAPE)
1236                 fprintf(f, "shape=%s ", limited ? "diamond" : "ellipse");
1237
1238         if(env->flags & CO_IFG_DUMP_COLORS)
1239                 fprintf(f, "style=filled color=%s ", get_dot_color_name(reg->index));
1240 }
1241
1242 static void ifg_dump_at_end(FILE *file, void *self)
1243 {
1244         co_ifg_dump_t *env = self;
1245         affinity_node_t *a;
1246
1247         co_gs_foreach_aff_node(env->co, a) {
1248                 const arch_register_t *ar = arch_get_irn_register(env->co->aenv, a->irn);
1249                 unsigned aidx = get_irn_idx(a->irn);
1250                 neighb_t *n;
1251
1252                 co_gs_foreach_neighb(a, n) {
1253                         const arch_register_t *nr = arch_get_irn_register(env->co->aenv, n->irn);
1254                         unsigned nidx = get_irn_idx(n->irn);
1255
1256                         if(aidx < nidx) {
1257                                 const char *color = nr == ar ? "blue" : "red";
1258                                 fprintf(file, "\tn%d -- n%d [weight=0.01 ", aidx, nidx);
1259                                 if(env->flags & CO_IFG_DUMP_LABELS)
1260                                         fprintf(file, "label=\"%d\" ", n->costs);
1261                                 if(env->flags & CO_IFG_DUMP_COLORS)
1262                                         fprintf(file, "color=%s ", color);
1263                                 else
1264                                         fprintf(file, "style=dashed");
1265                                 fprintf(file, "];\n");
1266                         }
1267                 }
1268         }
1269 }
1270
1271
1272 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1273         ifg_is_dump_node,
1274         ifg_dump_graph_attr,
1275         ifg_dump_node_attr,
1276         NULL,
1277         NULL,
1278         ifg_dump_at_end
1279 };
1280
1281
1282
1283 void co_dump_ifg_dot(const copy_opt_t *co, FILE *f, unsigned flags)
1284 {
1285         co_ifg_dump_t cod;
1286
1287         cod.co    = co;
1288         cod.flags = flags;
1289         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &cod);
1290 }
1291
1292
1293 void co_solve_park_moon(copy_opt_t *opt)
1294 {
1295
1296 }
1297
1298 static int void_algo(copy_opt_t *co)
1299 {
1300         return 0;
1301 }
1302
1303 /*
1304                 _    _                  _ _   _
1305            / \  | | __ _  ___  _ __(_) |_| |__  _ __ ___  ___
1306           / _ \ | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \/ __|
1307          / ___ \| | (_| | (_) | |  | | |_| | | | | | | | \__ \
1308         /_/   \_\_|\__, |\___/|_|  |_|\__|_| |_|_| |_| |_|___/
1309                            |___/
1310 */
1311
1312 static co_algo_t *algos[] = {
1313         void_algo,
1314         co_solve_heuristic,
1315         co_solve_heuristic_new,
1316         co_solve_heuristic_java,
1317 #ifdef WITH_ILP
1318         co_solve_ilp2
1319 #endif
1320 };
1321
1322 /*
1323     __  __       _         ____       _
1324    |  \/  | __ _(_)_ __   |  _ \ _ __(_)_   _____ _ __
1325    | |\/| |/ _` | | '_ \  | | | | '__| \ \ / / _ \ '__|
1326    | |  | | (_| | | | | | | |_| | |  | |\ V /  __/ |
1327    |_|  |_|\__,_|_|_| |_| |____/|_|  |_| \_/ \___|_|
1328
1329 */
1330
1331 void co_driver(be_chordal_env_t *cenv)
1332 {
1333         copy_opt_t *co;
1334         co_algo_t  *algo_func;
1335
1336         if(algo < 0 || algo >= CO_ALGO_LAST)
1337                 return;
1338
1339         co = new_copy_opt(cenv, cost_func);
1340         co_build_ou_structure(co);
1341         co_build_graph_structure(co);
1342         if(do_stats) {
1343                 ir_printf("%30F %10s %7d%7d%7d%7d", cenv->irg, cenv->cls->name,
1344                                 co_get_max_copy_costs(co), co_get_copy_costs(co),
1345                                 co_get_inevit_copy_costs(co), co_get_lower_bound(co));
1346         }
1347
1348         /* Dump the interference graph in Appel's format. */
1349         if(dump_flags & DUMP_APPEL) {
1350                 FILE *f = be_chordal_open(cenv, "", ".apl");
1351                 co_dump_appel_graph(co, f);
1352                 fclose(f);
1353         }
1354
1355         if(dump_flags & DUMP_BEFORE) {
1356                 FILE *f = be_chordal_open(cenv, "", "-before.dot");
1357                 co_dump_ifg_dot(co, f, style_flags);
1358                 fclose(f);
1359         }
1360
1361         algo_func = algos[algo];
1362         algo_func(co);
1363
1364         if(dump_flags & DUMP_AFTER) {
1365                 FILE *f = be_chordal_open(cenv, "", "-after.dot");
1366                 co_dump_ifg_dot(co, f, style_flags);
1367                 fclose(f);
1368         }
1369
1370         if(do_stats) {
1371                 int optimizable_costs = co_get_max_copy_costs(co) - co_get_lower_bound(co);
1372                 int remaining         = co_get_copy_costs(co);
1373                 int evitable          = remaining - co_get_lower_bound(co);
1374
1375                 if(optimizable_costs > 0)
1376                         printf("%5d %5.2f\n", remaining, (evitable * 100.0) / optimizable_costs);
1377                 else
1378                         printf("%5d %5s\n", remaining, "-");
1379         }
1380
1381         co_free_graph_structure(co);
1382         co_free_ou_structure(co);
1383         free_copy_opt(co);
1384 }