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