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  *
  26  * Main file for the optimization reducing the copies needed for:
  27  * - Phi coalescing
  28  * - Register-constrained nodes
  29  * - Two-address code instructions
  30  */
  31 #include "config.h"
  32
  33 #include "debug.h"
  34 #include "error.h"
  35 #include "execfreq.h"
  36 #include "irdump_t.h"
  37 #include "iredges_t.h"
  38 #include "irgraph.h"
  39 #include "irgwalk.h"
  40 #include "irloop_t.h"
  41 #include "irnode.h"
  42 #include "irprintf_t.h"
  43 #include "irprog.h"
  44 #include "irtools.h"
  45 #include "pmap.h"
  46 #include "raw_bitset.h"
  47 #include "util.h"
  48 #include "xmalloc.h"
  49
  50 #include "bearch.h"
  51 #include "becopyopt_t.h"
  52 #include "becopystat.h"
  53 #include "bedump.h"
  54 #include "beifg.h"
  55 #include "beinsn_t.h"
  56 #include "beintlive_t.h"
  57 #include "beirg.h"
  58 #include "belive_t.h"
  59 #include "bemodule.h"
  60 #include "benode.h"
  61 #include "besched.h"
  62 #include "bestatevent.h"
  63 #include "beutil.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 /**
  78  * Flags for dumping the IFG.
  79  */
  80 enum {
  81         CO_IFG_DUMP_COLORS = 1 << 0, /**< Dump the graph colored. */
  82         CO_IFG_DUMP_LABELS = 1 << 1, /**< Dump node/edge labels. */
  83         CO_IFG_DUMP_SHAPE  = 1 << 2, /**< Give constrained nodes special shapes. */
  84         CO_IFG_DUMP_CONSTR = 1 << 3, /**< Dump the node constraints in the label. */
  85 };
  86
  87 static int co_get_costs_loop_depth(const ir_node *root, int pos);
  88 static int co_get_costs_exec_freq(const ir_node *root, int pos);
  89 static int co_get_costs_all_one(const ir_node *root, int pos);
  90
  91 static unsigned   dump_flags  = 0;
  92 static unsigned   style_flags = CO_IFG_DUMP_COLORS;
  93 static int        do_stats    = 0;
  94 static cost_fct_t cost_func   = co_get_costs_exec_freq;
  95 static int        improve     = 1;
  96
  97 static const lc_opt_enum_mask_items_t dump_items[] = {
  98         { "before",  DUMP_BEFORE },
  99         { "after",   DUMP_AFTER  },
 100         { "appel",   DUMP_APPEL  },
 101         { "all",     DUMP_ALL    },
 102         { NULL,      0 }
 103 };
 104
 105 static const lc_opt_enum_mask_items_t style_items[] = {
 106         { "color",   CO_IFG_DUMP_COLORS },
 107         { "labels",  CO_IFG_DUMP_LABELS },
 108         { "constr",  CO_IFG_DUMP_CONSTR },
 109         { "shape",   CO_IFG_DUMP_SHAPE  },
 110         { "full",    2 * CO_IFG_DUMP_SHAPE - 1 },
 111         { NULL,      0 }
 112 };
 113
 114 typedef int (*opt_funcptr)(void);
 115 static const lc_opt_enum_func_ptr_items_t cost_func_items[] = {
 116         { "freq",   (opt_funcptr) co_get_costs_exec_freq },
 117         { "loop",   (opt_funcptr) co_get_costs_loop_depth },
 118         { "one",    (opt_funcptr) co_get_costs_all_one },
 119         { NULL,     NULL }
 120 };
 121
 122 static lc_opt_enum_mask_var_t dump_var = {
 123         &dump_flags, dump_items
 124 };
 125
 126 static lc_opt_enum_mask_var_t style_var = {
 127         &style_flags, style_items
 128 };
 129
 130 static lc_opt_enum_func_ptr_var_t cost_func_var = {
 131         (opt_funcptr*) &cost_func, cost_func_items
 132 };
 133
 134 static const lc_opt_table_entry_t options[] = {
 135         LC_OPT_ENT_ENUM_FUNC_PTR ("cost",    "select a cost function",                                  &cost_func_var),
 136         LC_OPT_ENT_ENUM_MASK     ("dump",    "dump ifg before or after copy optimization",              &dump_var),
 137         LC_OPT_ENT_ENUM_MASK     ("style",   "dump style for ifg dumping",                              &style_var),
 138         LC_OPT_ENT_BOOL          ("stats",   "dump statistics after each optimization",                 &do_stats),
 139         LC_OPT_ENT_BOOL          ("improve", "run heur1 before if algo can exploit start solutions",    &improve),
 140         LC_OPT_LAST
 141 };
 142
 143 static be_module_list_entry_t *copyopts = NULL;
 144 static const co_algo_info *selected_copyopt = NULL;
 145
 146 void be_register_copyopt(const char *name, co_algo_info *copyopt)
 147 {
 148         if (selected_copyopt == NULL)
 149                 selected_copyopt = copyopt;
 150         be_add_module_to_list(&copyopts, name, copyopt);
 151 }
 152
 153 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyopt)
 154 void be_init_copyopt(void)
 155 {
 156         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 157         lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
 158         lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
 159         lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
 160
 161         lc_opt_add_table(co_grp, options);
 162         be_add_module_list_opt(co_grp, "algo", "select copy optimization algo",
 163                                        &copyopts, (void**) &selected_copyopt);
 164 }
 165
 166 static int void_algo(copy_opt_t *co)
 167 {
 168         (void) co;
 169         return 0;
 170 }
 171
 172 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copynone)
 173 void be_init_copynone(void)
 174 {
 175         static co_algo_info copyheur = {
 176                 void_algo, 0
 177         };
 178
 179         be_register_copyopt("none", &copyheur);
 180 }
 181
 182 #undef QUICK_AND_DIRTY_HACK
 183
 184 static int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
 185 {
 186         if (env->ifg)
 187                 return be_ifg_connected(env->ifg, a, b);
 188         else {
 189                 be_lv_t *lv = be_get_irg_liveness(env->irg);
 190                 return be_values_interfere(lv, a, b);
 191         }
 192 }
 193
 194
 195 /******************************************************************************
 196     _____                           _
 197    / ____|                         | |
 198   | |  __  ___ _ __   ___ _ __ __ _| |
 199   | | |_ |/ _ \ '_ \ / _ \ '__/ _` | |
 200   | |__| |  __/ | | |  __/ | | (_| | |
 201    \_____|\___|_| |_|\___|_|  \__,_|_|
 202
 203  ******************************************************************************/
 204
 205 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 206
 207
 208 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
 209 {
 210         const char *s1, *s2, *s3;
 211         size_t len;
 212         copy_opt_t *co;
 213
 214         FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
 215
 216         co = XMALLOCZ(copy_opt_t);
 217         co->cenv      = chordal_env;
 218         co->irg       = chordal_env->irg;
 219         co->cls       = chordal_env->cls;
 220         co->get_costs = get_costs;
 221
 222         s1 = get_irp_name();
 223         s2 = get_entity_name(get_irg_entity(co->irg));
 224         s3 = chordal_env->cls->name;
 225         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
 226         co->name = XMALLOCN(char, len);
 227         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
 228
 229         return co;
 230 }
 231
 232 void free_copy_opt(copy_opt_t *co)
 233 {
 234         xfree(co->name);
 235         free(co);
 236 }
 237
 238 /**
 239  * Checks if a node is optimizable, viz. has something to do with coalescing
 240  * @param irn  The irn to check
 241  */
 242 static int co_is_optimizable_root(ir_node *irn)
 243 {
 244         const arch_register_req_t *req;
 245
 246         if (arch_irn_is_ignore(irn))
 247                 return 0;
 248
 249         if (is_Reg_Phi(irn) || is_Perm_Proj(irn))
 250                 return 1;
 251
 252         req = arch_get_irn_register_req(irn);
 253         if (is_2addr_code(req))
 254                 return 1;
 255
 256         return 0;
 257 }
 258
 259 /**
 260  * Computes the costs of a copy according to loop depth
 261  * @param pos  the argument position of arg in the root arguments
 262  * @return     Must be >= 0 in all cases.
 263  */
 264 static int co_get_costs_loop_depth(const ir_node *root, int pos)
 265 {
 266         ir_node *block = get_nodes_block(root);
 267         ir_loop *loop;
 268         int      cost;
 269
 270         if (is_Phi(root)) {
 271                 block = get_Block_cfgpred_block(block, pos);
 272         }
 273         loop = get_irn_loop(block);
 274         if (loop) {
 275                 int d = get_loop_depth(loop);
 276                 cost = d*d;
 277         } else {
 278                 cost = 0;
 279         }
 280         return 1+cost;
 281 }
 282
 283 /**
 284  * Computes the costs of a copy according to execution frequency
 285  * @param pos  the argument position of arg in the root arguments
 286  * @return Must be >= 0 in all cases.
 287  */
 288 static int co_get_costs_exec_freq(const ir_node *root, int pos)
 289 {
 290         ir_graph     *irg       = get_irn_irg(root);
 291         ir_node      *root_bl   = get_nodes_block(root);
 292         ir_node      *copy_bl
 293                 = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
 294         ir_exec_freq *exec_freq = be_get_irg_exec_freq(irg);
 295         int           res       = get_block_execfreq_ulong(exec_freq, copy_bl);
 296
 297         /* don't allow values smaller than one. */
 298         return res < 1 ? 1 : res;
 299 }
 300
 301 /**
 302  * All costs equal 1. Using this will reduce the _number_ of copies.
 303  * @param co   The copy opt object.
 304  * @return Must be >= 0 in all cases.
 305  */
 306 static int co_get_costs_all_one(const ir_node *root, int pos)
 307 {
 308         (void) root;
 309         (void) pos;
 310         return 1;
 311 }
 312
 313 /******************************************************************************
 314    ____        _   _    _       _ _          _____ _
 315   / __ \      | | | |  | |     (_) |        / ____| |
 316  | |  | |_ __ | |_| |  | |_ __  _| |_ ___  | (___ | |_ ___  _ __ __ _  __ _  ___
 317  | |  | | '_ \| __| |  | | '_ \| | __/ __|  \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 318  | |__| | |_) | |_| |__| | | | | | |_\__ \  ____) | || (_) | | | (_| | (_| |  __/
 319   \____/| .__/ \__|\____/|_| |_|_|\__|___/ |_____/ \__\___/|_|  \__,_|\__, |\___|
 320         | |                                                            __/ |
 321         |_|                                                           |___/
 322  ******************************************************************************/
 323
 324 /**
 325  * Determines a maximum weighted independent set with respect to
 326  * the interference and conflict edges of all nodes in a qnode.
 327  */
 328 static int ou_max_ind_set_costs(unit_t *ou)
 329 {
 330         be_chordal_env_t *chordal_env = ou->co->cenv;
 331         ir_node **safe, **unsafe;
 332         int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
 333         bitset_t *curr;
 334         size_t  pos;
 335         int curr_weight, best_weight = 0;
 336
 337         /* assign the nodes into two groups.
 338          * safe: node has no interference, hence it is in every max stable set.
 339          * unsafe: node has an interference
 340          */
 341         safe         = ALLOCAN(ir_node*, ou->node_count - 1);
 342         safe_costs   = 0;
 343         safe_count   = 0;
 344         unsafe       = ALLOCAN(ir_node*, ou->node_count - 1);
 345         unsafe_costs = ALLOCAN(int,      ou->node_count - 1);
 346         unsafe_count = 0;
 347         for (i=1; i<ou->node_count; ++i) {
 348                 int is_safe = 1;
 349                 for (o=1; o<ou->node_count; ++o) {
 350                         if (i==o)
 351                                 continue;
 352                         if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
 353                                 unsafe_costs[unsafe_count] = ou->costs[i];
 354                                 unsafe[unsafe_count] = ou->nodes[i];
 355                                 ++unsafe_count;
 356                                 is_safe = 0;
 357                                 break;
 358                         }
 359                 }
 360                 if (is_safe) {
 361                         safe_costs += ou->costs[i];
 362                         safe[safe_count++] = ou->nodes[i];
 363                 }
 364         }
 365
 366
 367         /* now compute the best set out of the unsafe nodes*/
 368         if (unsafe_count > MIS_HEUR_TRIGGER) {
 369                 bitset_t *best = bitset_alloca(unsafe_count);
 370                 /* Heuristic: Greedy trial and error form index 0 to unsafe_count-1 */
 371                 for (i=0; i<unsafe_count; ++i) {
 372                         bitset_set(best, i);
 373                         /* check if it is a stable set */
 374                         for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
 375                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
 376                                         bitset_clear(best, i); /* clear the bit and try next one */
 377                                         break;
 378                                 }
 379                 }
 380                 /* compute the weight */
 381                 bitset_foreach(best, pos)
 382                         best_weight += unsafe_costs[pos];
 383         } else {
 384                 /* Exact Algorithm: Brute force */
 385                 curr = bitset_alloca(unsafe_count);
 386                 bitset_set_all(curr);
 387                 while (bitset_popcount(curr) != 0) {
 388                         /* check if curr is a stable set */
 389                         for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
 390                                 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) */
 391                                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
 392                                                         goto no_stable_set;
 393
 394                         /* if we arrive here, we have a stable set */
 395                         /* compute the weight of the stable set*/
 396                         curr_weight = 0;
 397                         bitset_foreach(curr, pos)
 398                                 curr_weight += unsafe_costs[pos];
 399
 400                         /* any better ? */
 401                         if (curr_weight > best_weight) {
 402                                 best_weight = curr_weight;
 403                         }
 404
 405         no_stable_set:
 406                         bitset_minus1(curr);
 407                 }
 408         }
 409
 410         return safe_costs+best_weight;
 411 }
 412
 413 static void co_collect_units(ir_node *irn, void *env)
 414 {
 415         const arch_register_req_t *req;
 416         copy_opt_t                *co  = (copy_opt_t*)env;
 417         unit_t *unit;
 418
 419         if (get_irn_mode(irn) == mode_T)
 420                 return;
 421         req = arch_get_irn_register_req(irn);
 422         if (req->cls != co->cls)
 423                 return;
 424         if (!co_is_optimizable_root(irn))
 425                 return;
 426
 427         /* Init a new unit */
 428         unit = XMALLOCZ(unit_t);
 429         unit->co = co;
 430         unit->node_count = 1;
 431         INIT_LIST_HEAD(&unit->queue);
 432
 433         /* Phi with some/all of its arguments */
 434         if (is_Reg_Phi(irn)) {
 435                 int i, arity;
 436
 437                 /* init */
 438                 arity = get_irn_arity(irn);
 439                 unit->nodes = XMALLOCN(ir_node*, arity + 1);
 440                 unit->costs = XMALLOCN(int,      arity + 1);
 441                 unit->nodes[0] = irn;
 442
 443                 /* fill */
 444                 for (i=0; i<arity; ++i) {
 445                         int o, arg_pos;
 446                         ir_node *arg = get_irn_n(irn, i);
 447
 448                         assert(arch_get_irn_reg_class(arg) == co->cls && "Argument not in same register class.");
 449                         if (arg == irn)
 450                                 continue;
 451                         if (nodes_interfere(co->cenv, irn, arg)) {
 452                                 unit->inevitable_costs += co->get_costs(irn, i);
 453                                 continue;
 454                         }
 455
 456                         /* Else insert the argument of the phi to the members of this ou */
 457                         DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
 458
 459                         if (arch_irn_is_ignore(arg))
 460                                 continue;
 461
 462                         /* Check if arg has occurred at a prior position in the arg/list */
 463                         arg_pos = 0;
 464                         for (o=1; o<unit->node_count; ++o) {
 465                                 if (unit->nodes[o] == arg) {
 466                                         arg_pos = o;
 467                                         break;
 468                                 }
 469                         }
 470
 471                         if (!arg_pos) { /* a new argument */
 472                                 /* insert node, set costs */
 473                                 unit->nodes[unit->node_count] = arg;
 474                                 unit->costs[unit->node_count] = co->get_costs(irn, i);
 475                                 unit->node_count++;
 476                         } else { /* arg has occurred before in same phi */
 477                                 /* increase costs for existing arg */
 478                                 unit->costs[arg_pos] += co->get_costs(irn, i);
 479                         }
 480                 }
 481                 unit->nodes = XREALLOC(unit->nodes, ir_node*, unit->node_count);
 482                 unit->costs = XREALLOC(unit->costs, int,      unit->node_count);
 483         } else if (is_Perm_Proj(irn)) {
 484                 /* Proj of a perm with corresponding arg */
 485                 assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 486                 unit->nodes = XMALLOCN(ir_node*, 2);
 487                 unit->costs = XMALLOCN(int,      2);
 488                 unit->node_count = 2;
 489                 unit->nodes[0] = irn;
 490                 unit->nodes[1] = get_Perm_src(irn);
 491                 unit->costs[1] = co->get_costs(irn, -1);
 492         } else {
 493                 /* Src == Tgt of a 2-addr-code instruction */
 494                 if (is_2addr_code(req)) {
 495                         const unsigned other = req->other_same;
 496                         int            count = 0;
 497                         int            i;
 498
 499                         for (i = 0; (1U << i) <= other; ++i) {
 500                                 if (other & (1U << i)) {
 501                                         ir_node *o  = get_irn_n(skip_Proj(irn), i);
 502                                         if (arch_irn_is_ignore(o))
 503                                                 continue;
 504                                         if (nodes_interfere(co->cenv, irn, o))
 505                                                 continue;
 506                                         ++count;
 507                                 }
 508                         }
 509
 510                         if (count != 0) {
 511                                 int k = 0;
 512                                 ++count;
 513                                 unit->nodes = XMALLOCN(ir_node*, count);
 514                                 unit->costs = XMALLOCN(int,      count);
 515                                 unit->node_count = count;
 516                                 unit->nodes[k++] = irn;
 517
 518                                 for (i = 0; 1U << i <= other; ++i) {
 519                                         if (other & (1U << i)) {
 520                                                 ir_node *o  = get_irn_n(skip_Proj(irn), i);
 521                                                 if (!arch_irn_is_ignore(o) &&
 522                                                                 !nodes_interfere(co->cenv, irn, o)) {
 523                                                         unit->nodes[k] = o;
 524                                                         unit->costs[k] = co->get_costs(irn, -1);
 525                                                         ++k;
 526                                                 }
 527                                         }
 528                                 }
 529                         }
 530                 } else {
 531                         assert(0 && "This is not an optimizable node!");
 532                 }
 533         }
 534
 535         /* Insert the new unit at a position according to its costs */
 536         if (unit->node_count > 1) {
 537                 int i;
 538                 struct list_head *tmp;
 539
 540                 /* Determine the maximum costs this unit can cause: all_nodes_cost */
 541                 for (i=1; i<unit->node_count; ++i) {
 542                         unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
 543                         unit->all_nodes_costs += unit->costs[i];
 544                 }
 545
 546                 /* Determine the minimal costs this unit will cause: min_nodes_costs */
 547                 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
 548                 /* Insert the new ou according to its sort_key */
 549                 tmp = &co->units;
 550                 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
 551                         tmp = tmp->next;
 552                 list_add(&unit->units, tmp);
 553         } else {
 554                 free(unit);
 555         }
 556 }
 557
 558 #ifdef QUICK_AND_DIRTY_HACK
 559
 560 static int compare_ous(const void *k1, const void *k2)
 561 {
 562         const unit_t *u1 = *((const unit_t **) k1);
 563         const unit_t *u2 = *((const unit_t **) k2);
 564         int i, o, u1_has_constr, u2_has_constr;
 565         arch_register_req_t req;
 566
 567         /* Units with constraints come first */
 568         u1_has_constr = 0;
 569         for (i=0; i<u1->node_count; ++i) {
 570                 arch_get_irn_register_req(&req, u1->nodes[i]);
 571                 if (arch_register_req_is(&req, limited)) {
 572                         u1_has_constr = 1;
 573                         break;
 574                 }
 575         }
 576
 577         u2_has_constr = 0;
 578         for (i=0; i<u2->node_count; ++i) {
 579                 arch_get_irn_register_req(&req, u2->nodes[i]);
 580                 if (arch_register_req_is(&req, limited)) {
 581                         u2_has_constr = 1;
 582                         break;
 583                 }
 584         }
 585
 586         if (u1_has_constr != u2_has_constr)
 587                 return u2_has_constr - u1_has_constr;
 588
 589         /* Now check, whether the two units are connected */
 590 #if 0
 591         for (i=0; i<u1->node_count; ++i)
 592                 for (o=0; o<u2->node_count; ++o)
 593                         if (u1->nodes[i] == u2->nodes[o])
 594                                 return 0;
 595 #endif
 596
 597         /* After all, the sort key decides. Greater keys come first. */
 598         return u2->sort_key - u1->sort_key;
 599
 600 }
 601
 602 /**
 603  * Sort the ou's according to constraints and their sort_key
 604  */
 605 static void co_sort_units(copy_opt_t *co)
 606 {
 607         int i, count = 0, costs;
 608         unit_t *ou, **ous;
 609
 610         /* get the number of ous, remove them form the list and fill the array */
 611         list_for_each_entry(unit_t, ou, &co->units, units)
 612                 count++;
 613         ous = ALLOCAN(unit_t, count);
 614
 615         costs = co_get_max_copy_costs(co);
 616
 617         i = 0;
 618         list_for_each_entry(unit_t, ou, &co->units, units)
 619                 ous[i++] = ou;
 620
 621         INIT_LIST_HEAD(&co->units);
 622
 623         assert(count == i && list_empty(&co->units));
 624
 625         for (i=0; i<count; ++i)
 626                 ir_printf("%+F\n", ous[i]->nodes[0]);
 627
 628         qsort(ous, count, sizeof(*ous), compare_ous);
 629
 630         ir_printf("\n\n");
 631         for (i=0; i<count; ++i)
 632                 ir_printf("%+F\n", ous[i]->nodes[0]);
 633
 634         /* reinsert into list in correct order */
 635         for (i=0; i<count; ++i)
 636                 list_add_tail(&ous[i]->units, &co->units);
 637
 638         assert(costs == co_get_max_copy_costs(co));
 639 }
 640 #endif
 641
 642 void co_build_ou_structure(copy_opt_t *co)
 643 {
 644         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
 645         INIT_LIST_HEAD(&co->units);
 646         irg_walk_graph(co->irg, co_collect_units, NULL, co);
 647 #ifdef QUICK_AND_DIRTY_HACK
 648         co_sort_units(co);
 649 #endif
 650 }
 651
 652 void co_free_ou_structure(copy_opt_t *co)
 653 {
 654         unit_t *curr, *tmp;
 655         ASSERT_OU_AVAIL(co);
 656         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 657                 xfree(curr->nodes);
 658                 xfree(curr->costs);
 659                 xfree(curr);
 660         }
 661         co->units.next = NULL;
 662 }
 663
 664 /* co_solve_heuristic() is implemented in becopyheur.c */
 665
 666 int co_get_max_copy_costs(const copy_opt_t *co)
 667 {
 668         int i, res = 0;
 669         unit_t *curr;
 670
 671         ASSERT_OU_AVAIL(co);
 672
 673         list_for_each_entry(unit_t, curr, &co->units, units) {
 674                 res += curr->inevitable_costs;
 675                 for (i=1; i<curr->node_count; ++i)
 676                         res += curr->costs[i];
 677         }
 678         return res;
 679 }
 680
 681 int co_get_inevit_copy_costs(const copy_opt_t *co)
 682 {
 683         int res = 0;
 684         unit_t *curr;
 685
 686         ASSERT_OU_AVAIL(co);
 687
 688         list_for_each_entry(unit_t, curr, &co->units, units)
 689                 res += curr->inevitable_costs;
 690         return res;
 691 }
 692
 693 int co_get_copy_costs(const copy_opt_t *co)
 694 {
 695         int i, res = 0;
 696         unit_t *curr;
 697
 698         ASSERT_OU_AVAIL(co);
 699
 700         list_for_each_entry(unit_t, curr, &co->units, units) {
 701                 int root_col = get_irn_col(curr->nodes[0]);
 702                 DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
 703                 res += curr->inevitable_costs;
 704                 for (i=1; i<curr->node_count; ++i) {
 705                         int arg_col = get_irn_col(curr->nodes[i]);
 706                         if (root_col != arg_col) {
 707                                 DBG((dbg, LEVEL_1, "  %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
 708                                 res += curr->costs[i];
 709                         }
 710                 }
 711         }
 712         return res;
 713 }
 714
 715 int co_get_lower_bound(const copy_opt_t *co)
 716 {
 717         int res = 0;
 718         unit_t *curr;
 719
 720         ASSERT_OU_AVAIL(co);
 721
 722         list_for_each_entry(unit_t, curr, &co->units, units)
 723                 res += curr->inevitable_costs + curr->min_nodes_costs;
 724         return res;
 725 }
 726
 727 void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
 728 {
 729         bitset_t *seen = bitset_malloc(get_irg_last_idx(co->irg));
 730         affinity_node_t *an;
 731
 732         memset(stat, 0, sizeof(stat[0]));
 733
 734         /* count affinity edges. */
 735         co_gs_foreach_aff_node(co, an) {
 736                 neighb_t *neigh;
 737                 stat->aff_nodes += 1;
 738                 bitset_set(seen, get_irn_idx(an->irn));
 739                 co_gs_foreach_neighb(an, neigh) {
 740                         if (!bitset_is_set(seen, get_irn_idx(neigh->irn))) {
 741                                 stat->aff_edges += 1;
 742                                 stat->max_costs += neigh->costs;
 743
 744                                 if (get_irn_col(an->irn) != get_irn_col(neigh->irn)) {
 745                                         stat->costs += neigh->costs;
 746                                         stat->unsatisfied_edges += 1;
 747                                 }
 748
 749                                 if (nodes_interfere(co->cenv, an->irn, neigh->irn)) {
 750                                         stat->aff_int += 1;
 751                                         stat->inevit_costs += neigh->costs;
 752                                 }
 753
 754                         }
 755                 }
 756         }
 757
 758         bitset_free(seen);
 759 }
 760
 761 /******************************************************************************
 762    _____                 _        _____ _
 763   / ____|               | |      / ____| |
 764  | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 765  | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 766  | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
 767   \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
 768                   | |                                       __/ |
 769                   |_|                                      |___/
 770  ******************************************************************************/
 771
 772 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size)
 773 {
 774         const affinity_node_t *n1 = (const affinity_node_t*)k1;
 775         const affinity_node_t *n2 = (const affinity_node_t*)k2;
 776         (void) size;
 777
 778         return (n1->irn != n2->irn);
 779 }
 780
 781 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
 782 {
 783         affinity_node_t new_node, *node;
 784         neighb_t        *nbr;
 785         int             allocnew = 1;
 786
 787         new_node.irn        = n1;
 788         new_node.degree     = 0;
 789         new_node.neighbours = NULL;
 790         node = set_insert(affinity_node_t, co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
 791
 792         for (nbr = node->neighbours; nbr; nbr = nbr->next)
 793                 if (nbr->irn == n2) {
 794                         allocnew = 0;
 795                         break;
 796                 }
 797
 798         /* if we did not find n2 in n1's neighbourhood insert it */
 799         if (allocnew) {
 800                 nbr        = OALLOC(&co->obst, neighb_t);
 801                 nbr->irn   = n2;
 802                 nbr->costs = 0;
 803                 nbr->next  = node->neighbours;
 804
 805                 node->neighbours = nbr;
 806                 node->degree++;
 807         }
 808
 809         /* now nbr points to n1's neighbour-entry of n2 */
 810         nbr->costs += costs;
 811 }
 812
 813 static inline void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
 814 {
 815         if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
 816                 add_edge(co, n1, n2, costs);
 817                 add_edge(co, n2, n1, costs);
 818         }
 819 }
 820
 821 static void build_graph_walker(ir_node *irn, void *env)
 822 {
 823         const arch_register_req_t *req;
 824         copy_opt_t                *co  = (copy_opt_t*)env;
 825         int pos, max;
 826
 827         if (get_irn_mode(irn) == mode_T)
 828                 return;
 829         req = arch_get_irn_register_req(irn);
 830         if (req->cls != co->cls || arch_irn_is_ignore(irn))
 831                 return;
 832
 833         if (is_Reg_Phi(irn)) { /* Phis */
 834                 for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 835                         ir_node *arg = get_irn_n(irn, pos);
 836                         add_edges(co, irn, arg, co->get_costs(irn, pos));
 837                 }
 838         } else if (is_Perm_Proj(irn)) { /* Perms */
 839                 ir_node *arg = get_Perm_src(irn);
 840                 add_edges(co, irn, arg, co->get_costs(irn, -1));
 841         } else { /* 2-address code */
 842                 if (is_2addr_code(req)) {
 843                         const unsigned other = req->other_same;
 844                         int i;
 845
 846                         for (i = 0; 1U << i <= other; ++i) {
 847                                 if (other & (1U << i)) {
 848                                         ir_node *other = get_irn_n(skip_Proj(irn), i);
 849                                         if (!arch_irn_is_ignore(other))
 850                                                 add_edges(co, irn, other, co->get_costs(irn, -1));
 851                                 }
 852                         }
 853                 }
 854         }
 855 }
 856
 857 void co_build_graph_structure(copy_opt_t *co)
 858 {
 859         obstack_init(&co->obst);
 860         co->nodes = new_set(compare_affinity_node_t, 32);
 861
 862         irg_walk_graph(co->irg, build_graph_walker, NULL, co);
 863 }
 864
 865 void co_free_graph_structure(copy_opt_t *co)
 866 {
 867         ASSERT_GS_AVAIL(co);
 868
 869         del_set(co->nodes);
 870         obstack_free(&co->obst, NULL);
 871         co->nodes = NULL;
 872 }
 873
 874 int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn)
 875 {
 876         affinity_node_t new_node, *n;
 877
 878         ASSERT_GS_AVAIL(co);
 879
 880         new_node.irn = irn;
 881         n = set_find(affinity_node_t, co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
 882         if (n) {
 883                 return (n->degree > 0);
 884         } else
 885                 return 0;
 886 }
 887
 888 static int co_dump_appel_disjoint_constraints(const copy_opt_t *co, ir_node *a, ir_node *b)
 889 {
 890         ir_node *nodes[]  = { a, b };
 891         bitset_t *constr[] = { NULL, NULL };
 892         int j;
 893
 894         constr[0] = bitset_alloca(co->cls->n_regs);
 895         constr[1] = bitset_alloca(co->cls->n_regs);
 896
 897         for (j = 0; j < 2; ++j) {
 898                 const arch_register_req_t *req = arch_get_irn_register_req(nodes[j]);
 899                 if (arch_register_req_is(req, limited))
 900                         rbitset_copy_to_bitset(req->limited, constr[j]);
 901                 else
 902                         bitset_set_all(constr[j]);
 903
 904         }
 905
 906         return !bitset_intersect(constr[0], constr[1]);
 907 }
 908
 909 /**
 910  * Dump the interference graph according to the Appel/George coalescing contest file format.
 911  * See: http://www.cs.princeton.edu/~appel/coalesce/format.html
 912  * @note Requires graph structure.
 913  * @param co The copy opt object.
 914  * @param f  A file to dump to.
 915  */
 916 static void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 917 {
 918         be_ifg_t *ifg       = co->cenv->ifg;
 919         int      *color_map = ALLOCAN(int, co->cls->n_regs);
 920         int      *node_map  = XMALLOCN(int, get_irg_last_idx(co->irg) + 1);
 921         ir_graph *irg       = co->irg;
 922         be_irg_t *birg      = be_birg_from_irg(irg);
 923
 924         ir_node *irn;
 925         nodes_iter_t it;
 926         neighbours_iter_t nit;
 927         int n, n_regs;
 928         unsigned i;
 929
 930         n_regs = 0;
 931         for (i = 0; i < co->cls->n_regs; ++i) {
 932                 const arch_register_t *reg = &co->cls->regs[i];
 933                 if (rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
 934                         color_map[i] = n_regs++;
 935                 } else {
 936                         color_map[i] = -1;
 937                 }
 938         }
 939
 940         /*
 941          * n contains the first node number.
 942          * the values below n are the pre-colored register nodes
 943          */
 944
 945         n = n_regs;
 946         be_ifg_foreach_node(ifg, &it, irn) {
 947                 if (arch_irn_is_ignore(irn))
 948                         continue;
 949                 node_map[get_irn_idx(irn)] = n++;
 950         }
 951
 952         fprintf(f, "%d %d\n", n, n_regs);
 953
 954         be_ifg_foreach_node(ifg, &it, irn) {
 955                 if (!arch_irn_is_ignore(irn)) {
 956                         int idx                        = node_map[get_irn_idx(irn)];
 957                         affinity_node_t           *a   = get_affinity_info(co, irn);
 958                         const arch_register_req_t *req = arch_get_irn_register_req(irn);
 959                         ir_node                   *adj;
 960
 961                         if (arch_register_req_is(req, limited)) {
 962                                 for (i = 0; i < co->cls->n_regs; ++i) {
 963                                         if (!rbitset_is_set(req->limited, i) && color_map[i] >= 0)
 964                                                 fprintf(f, "%d %d -1\n", color_map[i], idx);
 965                                 }
 966                         }
 967
 968                         be_ifg_foreach_neighbour(ifg, &nit, irn, adj) {
 969                                 if (!arch_irn_is_ignore(adj) &&
 970                                                 !co_dump_appel_disjoint_constraints(co, irn, adj)) {
 971                                         int adj_idx = node_map[get_irn_idx(adj)];
 972                                         if (idx < adj_idx)
 973                                                 fprintf(f, "%d %d -1\n", idx, adj_idx);
 974                                 }
 975                         }
 976
 977                         if (a) {
 978                                 neighb_t *n;
 979
 980                                 co_gs_foreach_neighb(a, n) {
 981                                         if (!arch_irn_is_ignore(n->irn)) {
 982                                                 int n_idx = node_map[get_irn_idx(n->irn)];
 983                                                 if (idx < n_idx)
 984                                                         fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
 985                                         }
 986                                 }
 987                         }
 988                 }
 989         }
 990
 991         xfree(node_map);
 992 }
 993
 994 static FILE *my_open(const be_chordal_env_t *env, const char *prefix,
 995                      const char *suffix)
 996 {
 997         FILE *result;
 998         char buf[1024];
 999         size_t i, n;
1000         char *tu_name;
1001         const char *cup_name = be_get_irg_main_env(env->irg)->cup_name;
1002
1003         n = strlen(cup_name);
1004         tu_name = XMALLOCN(char, n + 1);
1005         strcpy(tu_name, cup_name);
1006         for (i = 0; i < n; ++i)
1007                 if (tu_name[i] == '.')
1008                         tu_name[i] = '_';
1009
1010
1011         ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
1012         xfree(tu_name);
1013         result = fopen(buf, "wt");
1014         if (result == NULL) {
1015                 panic("Couldn't open '%s' for writing.", buf);
1016         }
1017
1018         return result;
1019 }
1020
1021 void co_driver(be_chordal_env_t *cenv)
1022 {
1023         ir_timer_t          *timer = ir_timer_new();
1024         co_complete_stats_t before, after;
1025         copy_opt_t          *co;
1026         int                 was_optimal = 0;
1027
1028         assert(selected_copyopt);
1029
1030         /* skip copymin if algo is 'none' */
1031         if (selected_copyopt->copyopt == void_algo)
1032                 return;
1033
1034         be_assure_live_chk(cenv->irg);
1035
1036         co = new_copy_opt(cenv, cost_func);
1037         co_build_ou_structure(co);
1038         co_build_graph_structure(co);
1039
1040         co_complete_stats(co, &before);
1041
1042         be_stat_ev_ull("co_aff_nodes",    before.aff_nodes);
1043         be_stat_ev_ull("co_aff_edges",    before.aff_edges);
1044         be_stat_ev_ull("co_max_costs",    before.max_costs);
1045         be_stat_ev_ull("co_inevit_costs", before.inevit_costs);
1046         be_stat_ev_ull("co_aff_int",      before.aff_int);
1047
1048         be_stat_ev_ull("co_init_costs",   before.costs);
1049         be_stat_ev_ull("co_init_unsat",   before.unsatisfied_edges);
1050
1051         if (dump_flags & DUMP_BEFORE) {
1052                 FILE *f = my_open(cenv, "", "-before.vcg");
1053                 be_dump_ifg_co(f, co, style_flags & CO_IFG_DUMP_LABELS, style_flags & CO_IFG_DUMP_COLORS);
1054                 fclose(f);
1055         }
1056
1057         /* if the algo can improve results, provide an initial solution with heur1 */
1058         if (improve && selected_copyopt->can_improve_existing) {
1059                 co_complete_stats_t stats;
1060
1061                 /* produce a heuristic solution */
1062                 co_solve_heuristic(co);
1063
1064                 /* do the stats and provide the current costs */
1065                 co_complete_stats(co, &stats);
1066                 be_stat_ev_ull("co_prepare_costs", stats.costs);
1067         }
1068
1069         /* perform actual copy minimization */
1070         ir_timer_reset_and_start(timer);
1071         was_optimal = selected_copyopt->copyopt(co);
1072         ir_timer_stop(timer);
1073
1074         be_stat_ev("co_time", ir_timer_elapsed_msec(timer));
1075         be_stat_ev_ull("co_optimal", was_optimal);
1076         ir_timer_free(timer);
1077
1078         if (dump_flags & DUMP_AFTER) {
1079                 FILE *f = my_open(cenv, "", "-after.vcg");
1080                 be_dump_ifg_co(f, co, style_flags & CO_IFG_DUMP_LABELS, style_flags & CO_IFG_DUMP_COLORS);
1081                 fclose(f);
1082         }
1083
1084         co_complete_stats(co, &after);
1085
1086         if (do_stats) {
1087                 unsigned long long optimizable_costs = after.max_costs - after.inevit_costs;
1088                 unsigned long long evitable          = after.costs     - after.inevit_costs;
1089
1090                 ir_printf("%30F ", cenv->irg);
1091                 printf("%10s %10llu%10llu%10llu", cenv->cls->name, after.max_costs, before.costs, after.inevit_costs);
1092
1093                 if (optimizable_costs > 0)
1094                         printf("%10llu %5.2f\n", after.costs, (evitable * 100.0) / optimizable_costs);
1095                 else
1096                         printf("%10llu %5s\n", after.costs, "-");
1097         }
1098
1099         /* Dump the interference graph in Appel's format. */
1100         if (dump_flags & DUMP_APPEL) {
1101                 FILE *f = my_open(cenv, "", ".apl");
1102                 fprintf(f, "# %llu %llu\n", after.costs, after.unsatisfied_edges);
1103                 co_dump_appel_graph(co, f);
1104                 fclose(f);
1105         }
1106
1107         be_stat_ev_ull("co_after_costs", after.costs);
1108         be_stat_ev_ull("co_after_unsat", after.unsatisfied_edges);
1109
1110         co_free_graph_structure(co);
1111         co_free_ou_structure(co);
1112         free_copy_opt(co);
1113 }