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