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