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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Copy minimization driver.
  23  * @author      Daniel Grund
  24  * @date        12.04.2005
  25  * @version     $Id$
  26  *
  27  * Main file for the optimization reducing the copies needed for:
  28  * - Phi coalescing
  29  * - Register-constrained nodes
  30  * - Two-address code instructions
  31  */
  32 #include "config.h"
  33
  34 #include "execfreq.h"
  35 #include "xmalloc.h"
  36 #include "debug.h"
  37 #include "pmap.h"
  38 #include "raw_bitset.h"
  39 #include "irnode.h"
  40 #include "irgraph.h"
  41 #include "irgwalk.h"
  42 #include "irprog.h"
  43 #include "irloop_t.h"
  44 #include "iredges_t.h"
  45 #include "phiclass.h"
  46 #include "irbitset.h"
  47 #include "irphase_t.h"
  48 #include "irprintf_t.h"
  49
  50 #include "bemodule.h"
  51 #include "bearch_t.h"
  52 #include "benode_t.h"
  53 #include "beutil.h"
  54 #include "beifg_t.h"
  55 #include "beintlive_t.h"
  56 #include "becopyopt_t.h"
  57 #include "becopystat.h"
  58 #include "belive_t.h"
  59 #include "beinsn_t.h"
  60 #include "besched_t.h"
  61 #include "bestatevent.h"
  62 #include "beirg_t.h"
  63 #include "error.h"
  64
  65 #include "lc_opts.h"
  66 #include "lc_opts_enum.h"
  67
  68 #define DUMP_BEFORE 1
  69 #define DUMP_AFTER  2
  70 #define DUMP_APPEL  4
  71 #define DUMP_ALL    2 * DUMP_APPEL - 1
  72
  73 #define COST_FUNC_FREQ     1
  74 #define COST_FUNC_LOOP     2
  75 #define COST_FUNC_ALL_ONE  3
  76
  77 static unsigned   dump_flags  = 0;
  78 static unsigned   style_flags = 0;
  79 static unsigned   do_stats    = 0;
  80 static cost_fct_t cost_func   = co_get_costs_exec_freq;
  81 static unsigned   algo        = CO_ALGO_HEUR4;
  82 static int        improve     = 1;
  83
  84 static const lc_opt_enum_mask_items_t dump_items[] = {
  85         { "before",  DUMP_BEFORE },
  86         { "after",   DUMP_AFTER  },
  87         { "appel",   DUMP_APPEL  },
  88         { "all",     DUMP_ALL    },
  89         { NULL,      0 }
  90 };
  91
  92 static const lc_opt_enum_mask_items_t style_items[] = {
  93         { "color",   CO_IFG_DUMP_COLORS },
  94         { "labels",  CO_IFG_DUMP_LABELS },
  95         { "constr",  CO_IFG_DUMP_CONSTR },
  96         { "shape",   CO_IFG_DUMP_SHAPE  },
  97         { "full",    2 * CO_IFG_DUMP_SHAPE - 1 },
  98         { NULL,      0 }
  99 };
 100
 101 static const lc_opt_enum_mask_items_t algo_items[] = {
 102         { "none",   CO_ALGO_NONE  },
 103         { "heur",   CO_ALGO_HEUR  },
 104         { "heur2",  CO_ALGO_HEUR2 },
 105         { "heur3",  CO_ALGO_HEUR3 },
 106         { "heur4",  CO_ALGO_HEUR4 },
 107         { "ilp",    CO_ALGO_ILP   },
 108         { NULL,     0 }
 109 };
 110
 111 typedef int (*opt_funcptr)(void);
 112
 113 static const lc_opt_enum_func_ptr_items_t cost_func_items[] = {
 114         { "freq",   (opt_funcptr) co_get_costs_exec_freq },
 115         { "loop",   (opt_funcptr) co_get_costs_loop_depth },
 116         { "one",    (opt_funcptr) co_get_costs_all_one },
 117         { NULL,     NULL }
 118 };
 119
 120 static lc_opt_enum_mask_var_t dump_var = {
 121         &dump_flags, dump_items
 122 };
 123
 124 static lc_opt_enum_mask_var_t style_var = {
 125         &style_flags, style_items
 126 };
 127
 128 static lc_opt_enum_mask_var_t algo_var = {
 129         &algo, algo_items
 130 };
 131
 132 static lc_opt_enum_func_ptr_var_t cost_func_var = {
 133         (opt_funcptr*) &cost_func, cost_func_items
 134 };
 135
 136 static const lc_opt_table_entry_t options[] = {
 137         LC_OPT_ENT_ENUM_INT      ("algo",    "select copy optimization algo",                           &algo_var),
 138         LC_OPT_ENT_ENUM_FUNC_PTR ("cost",    "select a cost function",                                  &cost_func_var),
 139         LC_OPT_ENT_ENUM_MASK     ("dump",    "dump ifg before or after copy optimization",              &dump_var),
 140         LC_OPT_ENT_ENUM_MASK     ("style",   "dump style for ifg dumping",                              &style_var),
 141         LC_OPT_ENT_BOOL          ("stats",   "dump statistics after each optimization",                 &do_stats),
 142         LC_OPT_ENT_BOOL          ("improve", "run heur3 before if algo can exploit start solutions",    &improve),
 143         LC_OPT_LAST
 144 };
 145
 146 /* Insert additional options registration functions here. */
 147 extern void be_co_ilp_register_options(lc_opt_entry_t *grp);
 148 extern void be_co2_register_options(lc_opt_entry_t *grp);
 149 extern void be_co3_register_options(lc_opt_entry_t *grp);
 150
 151 void be_init_copycoal(void)
 152 {
 153         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 154         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
 155         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
 156         lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
 157
 158         lc_opt_add_table(co_grp, options);
 159 }
 160
 161 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copycoal);
 162
 163 #undef QUICK_AND_DIRTY_HACK
 164
 165 static int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
 166 {
 167         if (env->ifg)
 168                 return be_ifg_connected(env->ifg, a, b);
 169         else
 170                 return values_interfere(env->birg, a, b);
 171 }
 172
 173
 174 /******************************************************************************
 175     _____                           _
 176    / ____|                         | |
 177   | |  __  ___ _ __   ___ _ __ __ _| |
 178   | | |_ |/ _ \ '_ \ / _ \ '__/ _` | |
 179   | |__| |  __/ | | |  __/ | | (_| | |
 180    \_____|\___|_| |_|\___|_|  \__,_|_|
 181
 182  ******************************************************************************/
 183
 184 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 185
 186
 187 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
 188 {
 189         const char *s1, *s2, *s3;
 190         int len;
 191         copy_opt_t *co;
 192
 193         FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
 194
 195         co = XMALLOCZ(copy_opt_t);
 196         co->cenv      = chordal_env;
 197         co->irg       = chordal_env->irg;
 198         co->cls       = chordal_env->cls;
 199         co->get_costs = get_costs;
 200
 201         s1 = get_irp_prog_name();
 202         s2 = get_entity_name(get_irg_entity(co->irg));
 203         s3 = chordal_env->cls->name;
 204         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
 205         co->name = XMALLOCN(char, len);
 206         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
 207
 208         return co;
 209 }
 210
 211 void free_copy_opt(copy_opt_t *co) {
 212         xfree(co->name);
 213         free(co);
 214 }
 215
 216 /**
 217  * Checks if a node is optimizable, viz. has something to do with coalescing
 218  * @param irn  The irn to check
 219  */
 220 static int co_is_optimizable_root(ir_node *irn)
 221 {
 222         const arch_register_req_t *req;
 223         const arch_register_t *reg;
 224
 225         if (arch_irn_is(irn, ignore))
 226                 return 0;
 227
 228         reg = arch_get_irn_register(irn);
 229         if (arch_register_type_is(reg, ignore))
 230                 return 0;
 231
 232         if (is_Reg_Phi(irn) || is_Perm_Proj(irn))
 233                 return 1;
 234
 235         req = arch_get_register_req(irn, -1);
 236         if (is_2addr_code(req))
 237                 return 1;
 238
 239         return 0;
 240 }
 241
 242 int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 243         int cost = 0;
 244         ir_loop *loop;
 245         ir_node *root_block = get_nodes_block(root);
 246         (void) co;
 247         (void) arg;
 248
 249         if (is_Phi(root)) {
 250                 /* for phis the copies are placed in the corresponding pred-block */
 251                 loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
 252         } else {
 253                 /* a perm places the copy in the same block as it resides */
 254                 loop = get_irn_loop(root_block);
 255         }
 256         if (loop) {
 257                 int d = get_loop_depth(loop);
 258                 cost = d*d;
 259         }
 260         return 1+cost;
 261 }
 262
 263 int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 264         int res;
 265         ir_node *root_bl = get_nodes_block(root);
 266         ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
 267         (void) arg;
 268         res = get_block_execfreq_ulong(co->cenv->birg->exec_freq, copy_bl);
 269
 270         /* don't allow values smaller than one. */
 271         return res < 1 ? 1 : res;
 272 }
 273
 274
 275 int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node *arg, int pos) {
 276         (void) co;
 277         (void) root;
 278         (void) arg;
 279         (void) 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         bitset_pos_t pos;
 304         int max, curr_weight, best_weight = 0;
 305
 306         /* assign the nodes into two groups.
 307          * safe: node has no interference, hence it is in every max stable set.
 308          * unsafe: node has an interference
 309          */
 310         safe = alloca((ou->node_count-1) * sizeof(*safe));
 311         safe_costs = 0;
 312         safe_count = 0;
 313         unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
 314         unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
 315         unsafe_count = 0;
 316         for(i=1; i<ou->node_count; ++i) {
 317                 int is_safe = 1;
 318                 for(o=1; o<ou->node_count; ++o) {
 319                         if (i==o)
 320                                 continue;
 321                         if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
 322                                 unsafe_costs[unsafe_count] = ou->costs[i];
 323                                 unsafe[unsafe_count] = ou->nodes[i];
 324                                 ++unsafe_count;
 325                                 is_safe = 0;
 326                                 break;
 327                         }
 328                 }
 329                 if (is_safe) {
 330                         safe_costs += ou->costs[i];
 331                         safe[safe_count++] = ou->nodes[i];
 332                 }
 333         }
 334
 335
 336         /* now compute the best set out of the unsafe nodes*/
 337         if (unsafe_count > MIS_HEUR_TRIGGER) {
 338                 bitset_t *best = bitset_alloca(unsafe_count);
 339                 /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
 340                 for (i=0; i<unsafe_count; ++i) {
 341                         bitset_set(best, i);
 342                         /* check if it is a stable set */
 343                         for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
 344                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
 345                                         bitset_clear(best, i); /* clear the bit and try next one */
 346                                         break;
 347                                 }
 348                 }
 349                 /* compute the weight */
 350                 bitset_foreach(best, pos)
 351                         best_weight += unsafe_costs[pos];
 352         } else {
 353                 /* Exact Algorithm: Brute force */
 354                 curr = bitset_alloca(unsafe_count);
 355                 bitset_set_all(curr);
 356                 while ((max = bitset_popcnt(curr)) != 0) {
 357                         /* check if curr is a stable set */
 358                         for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
 359                                 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) */
 360                                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
 361                                                         goto no_stable_set;
 362
 363                         /* if we arrive here, we have a stable set */
 364                         /* compute the weigth of the stable set*/
 365                         curr_weight = 0;
 366                         bitset_foreach(curr, pos)
 367                                 curr_weight += unsafe_costs[pos];
 368
 369                         /* any better ? */
 370                         if (curr_weight > best_weight) {
 371                                 best_weight = curr_weight;
 372                         }
 373
 374         no_stable_set:
 375                         bitset_minus1(curr);
 376                 }
 377         }
 378
 379         return safe_costs+best_weight;
 380 }
 381
 382 static void co_collect_units(ir_node *irn, void *env)
 383 {
 384         const arch_register_req_t *req = arch_get_register_req(irn, -1);
 385         copy_opt_t                *co  = env;
 386         unit_t *unit;
 387
 388         if (req->cls != co->cls)
 389                 return;
 390         if (!co_is_optimizable_root(irn))
 391                 return;
 392
 393         /* Init a new unit */
 394         unit = XMALLOCZ(unit_t);
 395         unit->co = co;
 396         unit->node_count = 1;
 397         INIT_LIST_HEAD(&unit->queue);
 398
 399         /* Phi with some/all of its arguments */
 400         if (is_Reg_Phi(irn)) {
 401                 int i, arity;
 402
 403                 /* init */
 404                 arity = get_irn_arity(irn);
 405                 unit->nodes = XMALLOCN(ir_node*, arity + 1);
 406                 unit->costs = XMALLOCN(int,      arity + 1);
 407                 unit->nodes[0] = irn;
 408
 409                 /* fill */
 410                 for (i=0; i<arity; ++i) {
 411                         int o, arg_pos;
 412                         ir_node *arg = get_irn_n(irn, i);
 413
 414                         assert(arch_get_irn_reg_class(arg, -1) == co->cls && "Argument not in same register class.");
 415                         if (arg == irn)
 416                                 continue;
 417                         if (nodes_interfere(co->cenv, irn, arg)) {
 418                                 unit->inevitable_costs += co->get_costs(co, irn, arg, i);
 419                                 continue;
 420                         }
 421
 422                         /* Else insert the argument of the phi to the members of this ou */
 423                         DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
 424
 425                         if (!arch_irn_is(arg, ignore)) {
 426                                 /* Check if arg has occurred at a prior position in the arg/list */
 427                                 arg_pos = 0;
 428                                 for (o=1; o<unit->node_count; ++o) {
 429                                         if (unit->nodes[o] == arg) {
 430                                                 arg_pos = o;
 431                                                 break;
 432                                         }
 433                                 }
 434
 435                                 if (!arg_pos) { /* a new argument */
 436                                         /* insert node, set costs */
 437                                         unit->nodes[unit->node_count] = arg;
 438                                         unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
 439                                         unit->node_count++;
 440                                 } else { /* arg has occurred before in same phi */
 441                                         /* increase costs for existing arg */
 442                                         unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
 443                                 }
 444                         }
 445                 }
 446                 unit->nodes = XREALLOC(unit->nodes, ir_node*, unit->node_count);
 447                 unit->costs = XREALLOC(unit->costs, int,      unit->node_count);
 448         } else if (is_Perm_Proj(irn)) {
 449                 /* Proj of a perm with corresponding arg */
 450                 assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 451                 unit->nodes = XMALLOCN(ir_node*, 2);
 452                 unit->costs = XMALLOCN(int,      2);
 453                 unit->node_count = 2;
 454                 unit->nodes[0] = irn;
 455                 unit->nodes[1] = get_Perm_src(irn);
 456                 unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
 457         } else {
 458                 /* Src == Tgt of a 2-addr-code instruction */
 459                 if (is_2addr_code(req)) {
 460                         const unsigned other = req->other_same;
 461                         int            count = 0;
 462                         int            i;
 463
 464                         for (i = 0; (1U << i) <= other; ++i) {
 465                                 if (other & (1U << i)) {
 466                                         ir_node *o  = get_irn_n(skip_Proj(irn), i);
 467                                         if (!arch_irn_is(o, ignore) &&
 468                                                         !nodes_interfere(co->cenv, irn, o)) {
 469                                                 ++count;
 470                                         }
 471                                 }
 472                         }
 473
 474                         if (count != 0) {
 475                                 int k = 0;
 476                                 ++count;
 477                                 unit->nodes = XMALLOCN(ir_node*, count);
 478                                 unit->costs = XMALLOCN(int,      count);
 479                                 unit->node_count = count;
 480                                 unit->nodes[k++] = irn;
 481
 482                                 for (i = 0; 1U << i <= other; ++i) {
 483                                         if (other & (1U << i)) {
 484                                                 ir_node *o  = get_irn_n(skip_Proj(irn), i);
 485                                                 if (!arch_irn_is(o, ignore) &&
 486                                                                 !nodes_interfere(co->cenv, irn, o)) {
 487                                                         unit->nodes[k] = o;
 488                                                         unit->costs[k] = co->get_costs(co, irn, o, -1);
 489                                                         ++k;
 490                                                 }
 491                                         }
 492                                 }
 493                         }
 494                 } else {
 495                         assert(0 && "This is not an optimizable node!");
 496                 }
 497         }
 498
 499         /* Insert the new unit at a position according to its costs */
 500         if (unit->node_count > 1) {
 501                 int i;
 502                 struct list_head *tmp;
 503
 504                 /* Determine the maximum costs this unit can cause: all_nodes_cost */
 505                 for(i=1; i<unit->node_count; ++i) {
 506                         unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
 507                         unit->all_nodes_costs += unit->costs[i];
 508                 }
 509
 510                 /* Determine the minimal costs this unit will cause: min_nodes_costs */
 511                 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
 512                 /* Insert the new ou according to its sort_key */
 513                 tmp = &co->units;
 514                 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
 515                         tmp = tmp->next;
 516                 list_add(&unit->units, tmp);
 517         } else {
 518                 free(unit);
 519         }
 520 }
 521
 522 #ifdef QUICK_AND_DIRTY_HACK
 523
 524 static int compare_ous(const void *k1, const void *k2) {
 525         const unit_t *u1 = *((const unit_t **) k1);
 526         const unit_t *u2 = *((const unit_t **) k2);
 527         int i, o, u1_has_constr, u2_has_constr;
 528         arch_register_req_t req;
 529
 530         /* Units with constraints come first */
 531         u1_has_constr = 0;
 532         for (i=0; i<u1->node_count; ++i) {
 533                 arch_get_register_req(&req, u1->nodes[i], -1);
 534                 if (arch_register_req_is(&req, limited)) {
 535                         u1_has_constr = 1;
 536                         break;
 537                 }
 538         }
 539
 540         u2_has_constr = 0;
 541         for (i=0; i<u2->node_count; ++i) {
 542                 arch_get_register_req(&req, u2->nodes[i], -1);
 543                 if (arch_register_req_is(&req, limited)) {
 544                         u2_has_constr = 1;
 545                         break;
 546                 }
 547         }
 548
 549         if (u1_has_constr != u2_has_constr)
 550                 return u2_has_constr - u1_has_constr;
 551
 552         /* Now check, whether the two units are connected */
 553 #if 0
 554         for (i=0; i<u1->node_count; ++i)
 555                 for (o=0; o<u2->node_count; ++o)
 556                         if (u1->nodes[i] == u2->nodes[o])
 557                                 return 0;
 558 #endif
 559
 560         /* After all, the sort key decides. Greater keys come first. */
 561         return u2->sort_key - u1->sort_key;
 562
 563 }
 564
 565 /**
 566  * Sort the ou's according to constraints and their sort_key
 567  */
 568 static void co_sort_units(copy_opt_t *co) {
 569         int i, count = 0, costs;
 570         unit_t *ou, **ous;
 571
 572         /* get the number of ous, remove them form the list and fill the array */
 573         list_for_each_entry(unit_t, ou, &co->units, units)
 574                 count++;
 575         ous = alloca(count * sizeof(*ous));
 576
 577         costs = co_get_max_copy_costs(co);
 578
 579         i = 0;
 580         list_for_each_entry(unit_t, ou, &co->units, units)
 581                 ous[i++] = ou;
 582
 583         INIT_LIST_HEAD(&co->units);
 584
 585         assert(count == i && list_empty(&co->units));
 586
 587         for (i=0; i<count; ++i)
 588                 ir_printf("%+F\n", ous[i]->nodes[0]);
 589
 590         qsort(ous, count, sizeof(*ous), compare_ous);
 591
 592         ir_printf("\n\n");
 593         for (i=0; i<count; ++i)
 594                 ir_printf("%+F\n", ous[i]->nodes[0]);
 595
 596         /* reinsert into list in correct order */
 597         for (i=0; i<count; ++i)
 598                 list_add_tail(&ous[i]->units, &co->units);
 599
 600         assert(costs == co_get_max_copy_costs(co));
 601 }
 602 #endif
 603
 604 void co_build_ou_structure(copy_opt_t *co) {
 605         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
 606         INIT_LIST_HEAD(&co->units);
 607         irg_walk_graph(co->irg, co_collect_units, NULL, co);
 608 #ifdef QUICK_AND_DIRTY_HACK
 609         co_sort_units(co);
 610 #endif
 611 }
 612
 613 void co_free_ou_structure(copy_opt_t *co) {
 614         unit_t *curr, *tmp;
 615         ASSERT_OU_AVAIL(co);
 616         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 617                 xfree(curr->nodes);
 618                 xfree(curr->costs);
 619                 xfree(curr);
 620         }
 621         co->units.next = NULL;
 622 }
 623
 624 /* co_solve_heuristic() is implemented in becopyheur.c */
 625
 626 int co_get_max_copy_costs(const copy_opt_t *co) {
 627         int i, res = 0;
 628         unit_t *curr;
 629
 630         ASSERT_OU_AVAIL(co);
 631
 632         list_for_each_entry(unit_t, curr, &co->units, units) {
 633                 res += curr->inevitable_costs;
 634                 for (i=1; i<curr->node_count; ++i)
 635                         res += curr->costs[i];
 636         }
 637         return res;
 638 }
 639
 640 int co_get_inevit_copy_costs(const copy_opt_t *co) {
 641         int res = 0;
 642         unit_t *curr;
 643
 644         ASSERT_OU_AVAIL(co);
 645
 646         list_for_each_entry(unit_t, curr, &co->units, units)
 647                 res += curr->inevitable_costs;
 648         return res;
 649 }
 650
 651 int co_get_copy_costs(const copy_opt_t *co) {
 652         int i, res = 0;
 653         unit_t *curr;
 654
 655         ASSERT_OU_AVAIL(co);
 656
 657         list_for_each_entry(unit_t, curr, &co->units, units) {
 658                 int root_col = get_irn_col(curr->nodes[0]);
 659                 DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
 660                 res += curr->inevitable_costs;
 661                 for (i=1; i<curr->node_count; ++i) {
 662                         int arg_col = get_irn_col(curr->nodes[i]);
 663                         if (root_col != arg_col) {
 664                                 DBG((dbg, LEVEL_1, "  %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
 665                                 res += curr->costs[i];
 666                         }
 667                 }
 668         }
 669         return res;
 670 }
 671
 672 int co_get_lower_bound(const copy_opt_t *co) {
 673         int res = 0;
 674         unit_t *curr;
 675
 676         ASSERT_OU_AVAIL(co);
 677
 678         list_for_each_entry(unit_t, curr, &co->units, units)
 679                 res += curr->inevitable_costs + curr->min_nodes_costs;
 680         return res;
 681 }
 682
 683 void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
 684 {
 685         bitset_t *seen = bitset_irg_malloc(co->irg);
 686         affinity_node_t *an;
 687
 688         memset(stat, 0, sizeof(stat[0]));
 689
 690         /* count affinity edges. */
 691         co_gs_foreach_aff_node(co, an) {
 692                 neighb_t *neigh;
 693                 stat->aff_nodes += 1;
 694                 bitset_add_irn(seen, an->irn);
 695                 co_gs_foreach_neighb(an, neigh) {
 696                         if(!bitset_contains_irn(seen, neigh->irn)) {
 697                                 stat->aff_edges += 1;
 698                                 stat->max_costs += neigh->costs;
 699
 700                                 if (get_irn_col(an->irn) != get_irn_col(neigh->irn)) {
 701                                         stat->costs += neigh->costs;
 702                                         stat->unsatisfied_edges += 1;
 703                                 }
 704
 705                                 if(nodes_interfere(co->cenv, an->irn, neigh->irn)) {
 706                                         stat->aff_int += 1;
 707                                         stat->inevit_costs += neigh->costs;
 708                                 }
 709
 710                         }
 711                 }
 712         }
 713
 714         bitset_free(seen);
 715 }
 716
 717 /******************************************************************************
 718    _____                 _        _____ _
 719   / ____|               | |      / ____| |
 720  | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 721  | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 722  | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
 723   \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
 724                   | |                                       __/ |
 725                   |_|                                      |___/
 726  ******************************************************************************/
 727
 728 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
 729         const affinity_node_t *n1 = k1;
 730         const affinity_node_t *n2 = k2;
 731         (void) size;
 732
 733         return (n1->irn != n2->irn);
 734 }
 735
 736 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 737         affinity_node_t new_node, *node;
 738         neighb_t        *nbr;
 739         int             allocnew = 1;
 740
 741         new_node.irn        = n1;
 742         new_node.degree     = 0;
 743         new_node.neighbours = NULL;
 744         node = set_insert(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
 745
 746         for (nbr = node->neighbours; nbr; nbr = nbr->next)
 747                 if (nbr->irn == n2) {
 748                         allocnew = 0;
 749                         break;
 750                 }
 751
 752         /* if we did not find n2 in n1's neighbourhood insert it */
 753         if (allocnew) {
 754                 nbr        = obstack_alloc(&co->obst, sizeof(*nbr));
 755                 nbr->irn   = n2;
 756                 nbr->costs = 0;
 757                 nbr->next  = node->neighbours;
 758
 759                 node->neighbours = nbr;
 760                 node->degree++;
 761         }
 762
 763         /* now nbr points to n1's neighbour-entry of n2 */
 764         nbr->costs += costs;
 765 }
 766
 767 static inline void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 768         if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
 769                 add_edge(co, n1, n2, costs);
 770                 add_edge(co, n2, n1, costs);
 771         }
 772 }
 773
 774 static void build_graph_walker(ir_node *irn, void *env) {
 775         const arch_register_req_t *req = arch_get_register_req(irn, -1);
 776         copy_opt_t                *co  = env;
 777         int pos, max;
 778         const arch_register_t *reg;
 779
 780         if (req->cls != co->cls || arch_irn_is(irn, ignore))
 781                 return;
 782
 783         reg = arch_get_irn_register(irn);
 784         if (arch_register_type_is(reg, ignore))
 785                 return;
 786
 787         if (is_Reg_Phi(irn)) { /* Phis */
 788                 for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 789                         ir_node *arg = get_irn_n(irn, pos);
 790                         add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
 791                 }
 792         } else if (is_Perm_Proj(irn)) { /* Perms */
 793                 ir_node *arg = get_Perm_src(irn);
 794                 add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
 795         } else { /* 2-address code */
 796                 if (is_2addr_code(req)) {
 797                         const unsigned other = req->other_same;
 798                         int i;
 799
 800                         for (i = 0; 1U << i <= other; ++i) {
 801                                 if (other & (1U << i)) {
 802                                         ir_node *other = get_irn_n(skip_Proj(irn), i);
 803                                         if (!arch_irn_is(other, ignore))
 804                                                 add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
 805                                 }
 806                         }
 807                 }
 808         }
 809 }
 810
 811 void co_build_graph_structure(copy_opt_t *co) {
 812         obstack_init(&co->obst);
 813         co->nodes = new_set(compare_affinity_node_t, 32);
 814
 815         irg_walk_graph(co->irg, build_graph_walker, NULL, co);
 816 }
 817
 818 void co_free_graph_structure(copy_opt_t *co) {
 819         ASSERT_GS_AVAIL(co);
 820
 821         del_set(co->nodes);
 822         obstack_free(&co->obst, NULL);
 823         co->nodes = NULL;
 824 }
 825
 826 /* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */
 827
 828 int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) {
 829         affinity_node_t new_node, *n;
 830
 831         ASSERT_GS_AVAIL(co);
 832
 833         new_node.irn = irn;
 834         n = set_find(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
 835         if (n) {
 836                 return (n->degree > 0);
 837         } else
 838                 return 0;
 839 }
 840
 841 static int co_dump_appel_disjoint_constraints(const copy_opt_t *co, ir_node *a, ir_node *b)
 842 {
 843         ir_node *nodes[]  = { a, b };
 844         bitset_t *constr[] = { NULL, NULL };
 845         const arch_register_req_t *req;
 846         int j;
 847
 848         constr[0] = bitset_alloca(co->cls->n_regs);
 849         constr[1] = bitset_alloca(co->cls->n_regs);
 850
 851         for (j = 0; j < 2; ++j) {
 852                 req = arch_get_register_req(nodes[j], BE_OUT_POS(0));
 853                 if(arch_register_req_is(req, limited))
 854                         rbitset_copy_to_bitset(req->limited, constr[j]);
 855                 else
 856                         bitset_set_all(constr[j]);
 857
 858         }
 859
 860         return !bitset_intersect(constr[0], constr[1]);
 861 }
 862
 863 void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 864 {
 865         be_ifg_t *ifg  = co->cenv->ifg;
 866         int *color_map = alloca(co->cls->n_regs * sizeof(color_map[0]));
 867         int *node_map  = XMALLOCN(int, get_irg_last_idx(co->irg) + 1);
 868
 869         ir_node *irn;
 870         void *it, *nit;
 871         int n, n_regs;
 872         unsigned i;
 873
 874         n_regs = 0;
 875         for(i = 0; i < co->cls->n_regs; ++i) {
 876                 const arch_register_t *reg = &co->cls->regs[i];
 877                 color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_regs++;
 878         }
 879
 880         /*
 881          * n contains the first node number.
 882          * the values below n are the pre-colored register nodes
 883          */
 884
 885         it  = be_ifg_nodes_iter_alloca(ifg);
 886         nit = be_ifg_neighbours_iter_alloca(ifg);
 887
 888         n = n_regs;
 889         be_ifg_foreach_node(ifg, it, irn) {
 890                 if (!arch_irn_is(irn, ignore))
 891                         node_map[get_irn_idx(irn)] = n++;
 892         }
 893
 894         fprintf(f, "%d %d\n", n, n_regs);
 895
 896         be_ifg_foreach_node(ifg, it, irn) {
 897                 if (!arch_irn_is(irn, ignore)) {
 898                         int idx            = node_map[get_irn_idx(irn)];
 899                         affinity_node_t *a = get_affinity_info(co, irn);
 900
 901                         const arch_register_req_t *req;
 902                         ir_node *adj;
 903
 904                         req = arch_get_register_req(irn, BE_OUT_POS(0));
 905                         if(arch_register_req_is(req, limited)) {
 906                                 for(i = 0; i < co->cls->n_regs; ++i) {
 907                                         if(!rbitset_is_set(req->limited, i) && color_map[i] >= 0)
 908                                                 fprintf(f, "%d %d -1\n", color_map[i], idx);
 909                                 }
 910                         }
 911
 912                         be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
 913                                 if (!arch_irn_is(adj, ignore) &&
 914                                                 !co_dump_appel_disjoint_constraints(co, irn, adj)) {
 915                                         int adj_idx = node_map[get_irn_idx(adj)];
 916                                         if(idx < adj_idx)
 917                                                 fprintf(f, "%d %d -1\n", idx, adj_idx);
 918                                 }
 919                         }
 920
 921                         if(a) {
 922                                 neighb_t *n;
 923
 924                                 co_gs_foreach_neighb(a, n) {
 925                                         if (!arch_irn_is(n->irn, ignore)) {
 926                                                 int n_idx = node_map[get_irn_idx(n->irn)];
 927                                                 if(idx < n_idx)
 928                                                         fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
 929                                         }
 930                                 }
 931                         }
 932                 }
 933         }
 934
 935         xfree(node_map);
 936 }
 937
 938 /*
 939          ___ _____ ____   ____   ___ _____   ____                        _
 940         |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
 941          | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
 942          | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
 943         |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
 944                                                                   |_|            |___/
 945 */
 946
 947 static const char *get_dot_color_name(size_t col)
 948 {
 949         static const char *names[] = {
 950                 "blue",
 951                 "red",
 952                 "green",
 953                 "yellow",
 954                 "cyan",
 955                 "magenta",
 956                 "orange",
 957                 "chocolate",
 958                 "beige",
 959                 "navy",
 960                 "darkgreen",
 961                 "darkred",
 962                 "lightPink",
 963                 "chartreuse",
 964                 "lightskyblue",
 965                 "linen",
 966                 "pink",
 967                 "lightslateblue",
 968                 "mintcream",
 969                 "red",
 970                 "darkolivegreen",
 971                 "mediumblue",
 972                 "mistyrose",
 973                 "salmon",
 974                 "darkseagreen",
 975                 "mediumslateblue"
 976                 "moccasin",
 977                 "tomato",
 978                 "forestgreen",
 979                 "darkturquoise",
 980                 "palevioletred"
 981         };
 982
 983         return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
 984 }
 985
 986 typedef struct _co_ifg_dump_t {
 987         const copy_opt_t *co;
 988         unsigned flags;
 989 } co_ifg_dump_t;
 990
 991 static void ifg_dump_graph_attr(FILE *f, void *self)
 992 {
 993         (void) self;
 994         fprintf(f, "overlap=scale");
 995 }
 996
 997 static int ifg_is_dump_node(void *self, ir_node *irn)
 998 {
 999         (void)self;
1000         return !arch_irn_is(irn, ignore);
1001 }
1002
1003 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1004 {
1005         co_ifg_dump_t *env         = self;
1006         const arch_register_t *reg = arch_get_irn_register(irn);
1007         const arch_register_req_t *req;
1008         int limited;
1009
1010         req = arch_get_register_req(irn, BE_OUT_POS(0));
1011         limited = arch_register_req_is(req, limited);
1012
1013         if(env->flags & CO_IFG_DUMP_LABELS) {
1014                 ir_fprintf(f, "label=\"%+F", irn);
1015
1016                 if((env->flags & CO_IFG_DUMP_CONSTR) && limited) {
1017                         bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
1018                         rbitset_copy_to_bitset(req->limited, bs);
1019                         ir_fprintf(f, "\\n%B", bs);
1020                 }
1021                 ir_fprintf(f, "\" ");
1022         } else {
1023                 fprintf(f, "label=\"\" shape=point " );
1024         }
1025
1026         if(env->flags & CO_IFG_DUMP_SHAPE)
1027                 fprintf(f, "shape=%s ", limited ? "diamond" : "ellipse");
1028
1029         if(env->flags & CO_IFG_DUMP_COLORS)
1030                 fprintf(f, "style=filled color=%s ", get_dot_color_name(reg->index));
1031 }
1032
1033 static void ifg_dump_at_end(FILE *file, void *self)
1034 {
1035         co_ifg_dump_t *env = self;
1036         affinity_node_t *a;
1037
1038         co_gs_foreach_aff_node(env->co, a) {
1039                 const arch_register_t *ar = arch_get_irn_register(a->irn);
1040                 unsigned aidx = get_irn_idx(a->irn);
1041                 neighb_t *n;
1042
1043                 co_gs_foreach_neighb(a, n) {
1044                         const arch_register_t *nr = arch_get_irn_register(n->irn);
1045                         unsigned nidx = get_irn_idx(n->irn);
1046
1047                         if(aidx < nidx) {
1048                                 const char *color = nr == ar ? "blue" : "red";
1049                                 fprintf(file, "\tn%d -- n%d [weight=0.01 ", aidx, nidx);
1050                                 if(env->flags & CO_IFG_DUMP_LABELS)
1051                                         fprintf(file, "label=\"%d\" ", n->costs);
1052                                 if(env->flags & CO_IFG_DUMP_COLORS)
1053                                         fprintf(file, "color=%s ", color);
1054                                 else
1055                                         fprintf(file, "style=dotted");
1056                                 fprintf(file, "];\n");
1057                         }
1058                 }
1059         }
1060 }
1061
1062
1063 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1064         ifg_is_dump_node,
1065         ifg_dump_graph_attr,
1066         ifg_dump_node_attr,
1067         NULL,
1068         NULL,
1069         ifg_dump_at_end
1070 };
1071
1072
1073
1074 void co_dump_ifg_dot(const copy_opt_t *co, FILE *f, unsigned flags)
1075 {
1076         co_ifg_dump_t cod;
1077
1078         cod.co    = co;
1079         cod.flags = flags;
1080         be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &cod);
1081 }
1082
1083
1084 void co_solve_park_moon(copy_opt_t *opt)
1085 {
1086         (void) opt;
1087 }
1088
1089 static int void_algo(copy_opt_t *co)
1090 {
1091         (void) co;
1092         return 0;
1093 }
1094
1095 /*
1096                 _    _                  _ _   _
1097            / \  | | __ _  ___  _ __(_) |_| |__  _ __ ___  ___
1098           / _ \ | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \/ __|
1099          / ___ \| | (_| | (_) | |  | | |_| | | | | | | | \__ \
1100         /_/   \_\_|\__, |\___/|_|  |_|\__|_| |_|_| |_| |_|___/
1101                            |___/
1102 */
1103
1104 typedef struct {
1105         co_algo_t  *algo;
1106         const char *name;
1107         int        can_improve_existing;
1108 } co_algo_info_t;
1109
1110 static co_algo_info_t algos[] = {
1111         { void_algo,               "none",  0 },
1112         { co_solve_heuristic,      "heur1", 0 },
1113         { co_solve_heuristic_new,  "heur2", 0 },
1114 #ifdef WITH_JVM
1115         { co_solve_heuristic_java, "heur3", 0 },
1116 #else
1117         { NULL,                    "heur3", 0 },
1118 #endif
1119         { co_solve_heuristic_mst,  "heur4", 0 },
1120 #ifdef WITH_ILP
1121         { co_solve_ilp2,           "ilp",   1 },
1122 #else
1123         { NULL,                    "ilp",   1 },
1124 #endif
1125         { NULL,                    "",      0 }
1126 };
1127
1128 /*
1129     __  __       _         ____       _
1130    |  \/  | __ _(_)_ __   |  _ \ _ __(_)_   _____ _ __
1131    | |\/| |/ _` | | '_ \  | | | | '__| \ \ / / _ \ '__|
1132    | |  | | (_| | | | | | | |_| | |  | |\ V /  __/ |
1133    |_|  |_|\__,_|_|_| |_| |____/|_|  |_| \_/ \___|_|
1134
1135 */
1136
1137 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
1138 {
1139         FILE *result;
1140         char buf[1024];
1141         size_t i, n;
1142         char *tu_name;
1143
1144         n = strlen(env->birg->main_env->cup_name);
1145         tu_name = XMALLOCN(char, n + 1);
1146         strcpy(tu_name, env->birg->main_env->cup_name);
1147         for (i = 0; i < n; ++i)
1148                 if (tu_name[i] == '.')
1149                         tu_name[i] = '_';
1150
1151
1152         ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
1153         xfree(tu_name);
1154         result = fopen(buf, "wt");
1155         if(result == NULL) {
1156                 panic("Couldn't open '%s' for writing.", buf);
1157         }
1158
1159         return result;
1160 }
1161
1162 void co_driver(be_chordal_env_t *cenv)
1163 {
1164         ir_timer_t          *timer = ir_timer_register("firm.be.copyopt", "runtime");
1165         co_complete_stats_t before, after;
1166         copy_opt_t          *co;
1167         co_algo_t           *algo_func;
1168         int                 was_optimal = 0;
1169
1170         if (algo >= CO_ALGO_LAST)
1171                 return;
1172
1173         be_liveness_assure_chk(be_get_birg_liveness(cenv->birg));
1174
1175         co = new_copy_opt(cenv, cost_func);
1176         co_build_ou_structure(co);
1177         co_build_graph_structure(co);
1178
1179         co_complete_stats(co, &before);
1180
1181         be_stat_ev_ull("co_aff_nodes",    before.aff_nodes);
1182         be_stat_ev_ull("co_aff_edges",    before.aff_edges);
1183         be_stat_ev_ull("co_max_costs",    before.max_costs);
1184         be_stat_ev_ull("co_inevit_costs", before.inevit_costs);
1185         be_stat_ev_ull("co_aff_int",      before.aff_int);
1186
1187         be_stat_ev_ull("co_init_costs",   before.costs);
1188         be_stat_ev_ull("co_init_unsat",   before.unsatisfied_edges);
1189
1190         if (dump_flags & DUMP_BEFORE) {
1191                 FILE *f = my_open(cenv, "", "-before.dot");
1192                 co_dump_ifg_dot(co, f, style_flags);
1193                 fclose(f);
1194         }
1195
1196         /* if the algo can improve results, provide an initial solution with heur3 */
1197         if (improve && algos[algo].can_improve_existing) {
1198                 co_complete_stats_t stats;
1199
1200                 /* produce a heuristic solution */
1201 #ifdef WITH_JVM
1202                 co_solve_heuristic_java(co);
1203 #else
1204                 co_solve_heuristic(co);
1205 #endif /* WITH_JVM */
1206
1207                 /* do the stats and provide the current costs */
1208                 co_complete_stats(co, &stats);
1209                 be_stat_ev_ull("co_prepare_costs", stats.costs);
1210         }
1211
1212 #ifdef WITH_JVM
1213         /* start the JVM here so that it does not tamper the timing. */
1214         if (algo == CO_ALGO_HEUR3)
1215                 be_java_coal_start_jvm();
1216 #endif /* WITH_JVM */
1217
1218         algo_func = algos[algo].algo;
1219
1220         /* perform actual copy minimization */
1221         ir_timer_reset_and_start(timer);
1222         was_optimal = algo_func(co);
1223         ir_timer_stop(timer);
1224
1225         be_stat_ev("co_time", ir_timer_elapsed_msec(timer));
1226         be_stat_ev_ull("co_optimal", was_optimal);
1227
1228         if (dump_flags & DUMP_AFTER) {
1229                 FILE *f = my_open(cenv, "", "-after.dot");
1230                 co_dump_ifg_dot(co, f, style_flags);
1231                 fclose(f);
1232         }
1233
1234         co_complete_stats(co, &after);
1235
1236         if (do_stats) {
1237                 ulong64 optimizable_costs = after.max_costs - after.inevit_costs;
1238                 ulong64 evitable          = after.costs     - after.inevit_costs;
1239
1240                 ir_printf("%30F ", cenv->irg);
1241                 printf("%10s %10" ULL_FMT "%10" ULL_FMT "%10" ULL_FMT, cenv->cls->name, after.max_costs, before.costs, after.inevit_costs);
1242
1243                 if(optimizable_costs > 0)
1244                         printf("%10" ULL_FMT " %5.2f\n", after.costs, (evitable * 100.0) / optimizable_costs);
1245                 else
1246                         printf("%10" ULL_FMT " %5s\n", after.costs, "-");
1247         }
1248
1249         /* Dump the interference graph in Appel's format. */
1250         if (dump_flags & DUMP_APPEL) {
1251                 FILE *f = my_open(cenv, "", ".apl");
1252                 fprintf(f, "# %lld %lld\n", after.costs, after.unsatisfied_edges);
1253                 co_dump_appel_graph(co, f);
1254                 fclose(f);
1255         }
1256
1257         be_stat_ev_ull("co_after_costs", after.costs);
1258         be_stat_ev_ull("co_after_unsat", after.unsatisfied_edges);
1259
1260         co_free_graph_structure(co);
1261         co_free_ou_structure(co);
1262         free_copy_opt(co);
1263 }