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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                12.04.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  */
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10 #ifdef HAVE_ALLOCA_H
  11 #include <alloca.h>
  12 #endif
  13 #ifdef HAVE_MALLOC_H
  14 #include <malloc.h>
  15 #endif
  16
  17 #include "xmalloc.h"
  18 #include "debug.h"
  19 #include "pmap.h"
  20 #include "irgraph.h"
  21 #include "irgwalk.h"
  22 #include "irprog.h"
  23 #include "irloop_t.h"
  24 #include "iredges_t.h"
  25 #include "phiclass.h"
  26
  27 #include "bearch.h"
  28 #include "beutil.h"
  29 #include "beifg_t.h"
  30 #include "becopyopt_t.h"
  31 #include "becopystat.h"
  32
  33
  34 #ifdef WITH_LIBCORE
  35
  36 /* Insert additional options registration functions here. */
  37 extern void be_co2_register_options(lc_opt_entry_t *grp);
  38
  39 void co_register_options(lc_opt_entry_t *grp)
  40 {
  41         be_co2_register_options(grp);
  42 }
  43 #endif
  44
  45
  46 #undef QUICK_AND_DIRTY_HACK
  47
  48 /******************************************************************************
  49     _____                           _
  50    / ____|                         | |
  51   | |  __  ___ _ __   ___ _ __ __ _| |
  52   | | |_ |/ _ \ '_ \ / _ \ '__/ _` | |
  53   | |__| |  __/ | | |  __/ | | (_| | |
  54    \_____|\___|_| |_|\___|_|  \__,_|_|
  55
  56  ******************************************************************************/
  57
  58 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  59
  60 void be_copy_opt_init(void) {
  61 }
  62
  63 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node*, ir_node*, int)) {
  64         const char *s1, *s2, *s3;
  65         int len;
  66         copy_opt_t *co;
  67
  68         FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
  69
  70         co = xcalloc(1, sizeof(*co));
  71         co->cenv      = chordal_env;
  72         co->aenv      = chordal_env->birg->main_env->arch_env;
  73         co->irg       = chordal_env->irg;
  74         co->cls       = chordal_env->cls;
  75         co->get_costs = get_costs;
  76
  77         s1 = get_irp_prog_name();
  78         s2 = get_entity_name(get_irg_entity(co->irg));
  79         s3 = chordal_env->cls->name;
  80         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
  81         co->name = xmalloc(len);
  82         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
  83
  84         return co;
  85 }
  86
  87 void free_copy_opt(copy_opt_t *co) {
  88         xfree(co->name);
  89         free(co);
  90 }
  91
  92 int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
  93         arch_register_req_t req;
  94         const arch_register_t *reg;
  95
  96         if (arch_irn_is(co->aenv, irn, ignore))
  97                 return 0;
  98
  99         reg = arch_get_irn_register(co->aenv, irn);
 100         if (arch_register_type_is(reg, ignore))
 101                 return 0;
 102
 103         if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(co->aenv, irn, &req))
 104                 return 1;
 105
 106         return 0;
 107 }
 108
 109 int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
 110         const ir_edge_t *edge;
 111         const arch_register_t *reg;
 112
 113         assert(0 && "Is buggy and obsolete. Do not use");
 114
 115         if (arch_irn_is(co->aenv, irn, ignore))
 116                 return 0;
 117
 118         reg = arch_get_irn_register(co->aenv, irn);
 119         if (arch_register_type_is(reg, ignore))
 120                 return 0;
 121
 122         foreach_out_edge(irn, edge) {
 123                 ir_node *n = edge->src;
 124
 125                 if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
 126                         arch_register_req_t req;
 127                         arch_get_register_req(co->aenv, &req, n, -1);
 128
 129                         if(is_Reg_Phi(n) ||
 130                            is_Perm(co->aenv, n) ||
 131                            (arch_register_req_is(&req, should_be_same) && req.other_same == irn)
 132                           )
 133                                 return 1;
 134                 }
 135         }
 136
 137         return 0;
 138 }
 139
 140 int co_get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) {
 141         int cost = 0;
 142         ir_loop *loop;
 143         ir_node *root_block = get_nodes_block(root);
 144
 145         if (is_Phi(root)) {
 146                 /* for phis the copies are placed in the corresponding pred-block */
 147                 loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
 148         } else {
 149                 /* a perm places the copy in the same block as it resides */
 150                 loop = get_irn_loop(root_block);
 151         }
 152         if (loop) {
 153                 int d = get_loop_depth(loop);
 154                 cost = d*d;
 155         }
 156         return cost+1;
 157 }
 158
 159 int co_get_costs_all_one(ir_node *root, ir_node* arg, int pos) {
 160         return 1;
 161 }
 162
 163 /******************************************************************************
 164    ____        _   _    _       _ _          _____ _
 165   / __ \      | | | |  | |     (_) |        / ____| |
 166  | |  | |_ __ | |_| |  | |_ __  _| |_ ___  | (___ | |_ ___  _ __ __ _  __ _  ___
 167  | |  | | '_ \| __| |  | | '_ \| | __/ __|  \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 168  | |__| | |_) | |_| |__| | | | | | |_\__ \  ____) | || (_) | | | (_| | (_| |  __/
 169   \____/| .__/ \__|\____/|_| |_|_|\__|___/ |_____/ \__\___/|_|  \__,_|\__, |\___|
 170         | |                                                            __/ |
 171         |_|                                                           |___/
 172  ******************************************************************************/
 173
 174 /**
 175  * Determines a maximum weighted independent set with respect to
 176  * the interference and conflict edges of all nodes in a qnode.
 177  */
 178 static int ou_max_ind_set_costs(unit_t *ou) {
 179         be_chordal_env_t *chordal_env = ou->co->cenv;
 180         ir_node **safe, **unsafe;
 181         int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
 182         bitset_t *curr;
 183         int max, pos, curr_weight, best_weight = 0;
 184
 185         /* assign the nodes into two groups.
 186          * safe: node has no interference, hence it is in every max stable set.
 187          * unsafe: node has an interference
 188          */
 189         safe = alloca((ou->node_count-1) * sizeof(*safe));
 190         safe_costs = 0;
 191         safe_count = 0;
 192         unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
 193         unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
 194         unsafe_count = 0;
 195         for(i=1; i<ou->node_count; ++i) {
 196                 int is_safe = 1;
 197                 for(o=1; o<ou->node_count; ++o) {
 198                         if (i==o)
 199                                 continue;
 200                         if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
 201                                 unsafe_costs[unsafe_count] = ou->costs[i];
 202                                 unsafe[unsafe_count] = ou->nodes[i];
 203                                 ++unsafe_count;
 204                                 is_safe = 0;
 205                                 break;
 206                         }
 207                 }
 208                 if (is_safe) {
 209                         safe_costs += ou->costs[i];
 210                         safe[safe_count++] = ou->nodes[i];
 211                 }
 212         }
 213
 214
 215         /* now compute the best set out of the unsafe nodes*/
 216         if (unsafe_count > MIS_HEUR_TRIGGER) {
 217                 bitset_t *best = bitset_alloca(unsafe_count);
 218                 /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
 219                 for (i=0; i<unsafe_count; ++i) {
 220                         bitset_set(best, i);
 221                         /* check if it is a stable set */
 222                         for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
 223                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
 224                                         bitset_clear(best, i); /* clear the bit and try next one */
 225                                         break;
 226                                 }
 227                 }
 228                 /* compute the weight */
 229                 bitset_foreach(best, pos)
 230                         best_weight += unsafe_costs[pos];
 231         } else {
 232                 /* Exact Algorithm: Brute force */
 233                 curr = bitset_alloca(unsafe_count);
 234                 bitset_set_all(curr);
 235                 while ((max = bitset_popcnt(curr)) != 0) {
 236                         /* check if curr is a stable set */
 237                         for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
 238                                 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) */
 239                                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
 240                                                         goto no_stable_set;
 241
 242                         /* if we arrive here, we have a stable set */
 243                         /* compute the weigth of the stable set*/
 244                         curr_weight = 0;
 245                         bitset_foreach(curr, pos)
 246                                 curr_weight += unsafe_costs[pos];
 247
 248                         /* any better ? */
 249                         if (curr_weight > best_weight) {
 250                                 best_weight = curr_weight;
 251                         }
 252
 253         no_stable_set:
 254                         bitset_minus1(curr);
 255                 }
 256         }
 257
 258         return safe_costs+best_weight;
 259 }
 260
 261 static void co_collect_units(ir_node *irn, void *env) {
 262         copy_opt_t *co = env;
 263         unit_t *unit;
 264         arch_register_req_t req;
 265
 266         if (!is_curr_reg_class(co, irn))
 267                 return;
 268         if (!co_is_optimizable_root(co, irn))
 269                 return;
 270
 271         /* Init a new unit */
 272         unit = xcalloc(1, sizeof(*unit));
 273         unit->co = co;
 274         unit->node_count = 1;
 275         INIT_LIST_HEAD(&unit->queue);
 276
 277         /* Phi with some/all of its arguments */
 278         if (is_Reg_Phi(irn)) {
 279                 int i, arity;
 280
 281                 /* init */
 282                 arity = get_irn_arity(irn);
 283                 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
 284                 unit->costs = xmalloc((arity+1) * sizeof(*unit->costs));
 285                 unit->nodes[0] = irn;
 286
 287                 /* fill */
 288                 for (i=0; i<arity; ++i) {
 289                         int o, arg_pos;
 290                         ir_node *arg = get_irn_n(irn, i);
 291
 292                         assert(is_curr_reg_class(co, arg) && "Argument not in same register class.");
 293                         if (arg == irn)
 294                                 continue;
 295                         if (nodes_interfere(co->cenv, irn, arg)) {
 296                                 unit->inevitable_costs += co->get_costs(irn, arg, i);
 297                                 continue;
 298                         }
 299
 300                         /* Else insert the argument of the phi to the members of this ou */
 301                         DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
 302
 303                         /* Check if arg has occurred at a prior position in the arg/list */
 304                         arg_pos = 0;
 305                         for (o=0; o<unit->node_count; ++o)
 306                                 if (unit->nodes[o] == arg) {
 307                                         arg_pos = o;
 308                                         break;
 309                                 }
 310
 311                         if (!arg_pos) { /* a new argument */
 312                                 /* insert node, set costs */
 313                                 unit->nodes[unit->node_count] = arg;
 314                                 unit->costs[unit->node_count] = co->get_costs(irn, arg, i);
 315                                 unit->node_count++;
 316                         } else { /* arg has occured before in same phi */
 317                                 /* increase costs for existing arg */
 318                                 unit->costs[arg_pos] += co->get_costs(irn, arg, i);
 319                         }
 320                 }
 321                 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
 322                 unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
 323         } else
 324
 325         /* Proj of a perm with corresponding arg */
 326         if (is_Perm_Proj(co->aenv, irn)) {
 327                 assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 328                 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 329                 unit->costs = xmalloc(2 * sizeof(*unit->costs));
 330                 unit->node_count = 2;
 331                 unit->nodes[0] = irn;
 332                 unit->nodes[1] = get_Perm_src(irn);
 333                 unit->costs[1] = co->get_costs(irn, unit->nodes[1], -1);
 334         } else
 335
 336         /* Src == Tgt of a 2-addr-code instruction */
 337         if (is_2addr_code(co->aenv, irn, &req)) {
 338                 ir_node *other = req.other_same;
 339                 if (!nodes_interfere(co->cenv, irn, other)) {
 340                         unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 341                         unit->costs = xmalloc(2 * sizeof(*unit->costs));
 342                         unit->node_count = 2;
 343                         unit->nodes[0] = irn;
 344                         unit->nodes[1] = other;
 345                         unit->costs[1] = co->get_costs(irn, other, -1);
 346                 }
 347         } else
 348                 assert(0 && "This is not an optimizable node!");
 349
 350         /* Insert the new unit at a position according to its costs */
 351         if (unit->node_count > 1) {
 352                 int i;
 353                 struct list_head *tmp;
 354
 355                 /* Determine the maximum costs this unit can cause: all_nodes_cost */
 356                 for(i=1; i<unit->node_count; ++i) {
 357                         unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
 358                         unit->all_nodes_costs += unit->costs[i];
 359                 }
 360
 361                 /* Determine the minimal costs this unit will cause: min_nodes_costs */
 362                 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
 363                 /* Insert the new ou according to its sort_key */
 364                 tmp = &co->units;
 365                 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
 366                         tmp = tmp->next;
 367                 list_add(&unit->units, tmp);
 368         } else {
 369                 free(unit);
 370         }
 371 }
 372
 373 #ifdef QUICK_AND_DIRTY_HACK
 374
 375 static int compare_ous(const void *k1, const void *k2) {
 376         const unit_t *u1 = *((const unit_t **) k1);
 377         const unit_t *u2 = *((const unit_t **) k2);
 378         int i, o, u1_has_constr, u2_has_constr;
 379         arch_register_req_t req;
 380         const arch_env_t *aenv = u1->co->aenv;
 381
 382         /* Units with constraints come first */
 383         u1_has_constr = 0;
 384         for (i=0; i<u1->node_count; ++i) {
 385                 arch_get_register_req(aenv, &req, u1->nodes[i], -1);
 386                 if (arch_register_req_is(&req, limited)) {
 387                         u1_has_constr = 1;
 388                         break;
 389                 }
 390         }
 391
 392         u2_has_constr = 0;
 393         for (i=0; i<u2->node_count; ++i) {
 394                 arch_get_register_req(aenv, &req, u2->nodes[i], -1);
 395                 if (arch_register_req_is(&req, limited)) {
 396                         u2_has_constr = 1;
 397                         break;
 398                 }
 399         }
 400
 401         if (u1_has_constr != u2_has_constr)
 402                 return u2_has_constr - u1_has_constr;
 403
 404         /* Now check, whether the two units are connected */
 405 #if 0
 406         for (i=0; i<u1->node_count; ++i)
 407                 for (o=0; o<u2->node_count; ++o)
 408                         if (u1->nodes[i] == u2->nodes[o])
 409                                 return 0;
 410 #endif
 411
 412         /* After all, the sort key decides. Greater keys come first. */
 413         return u2->sort_key - u1->sort_key;
 414
 415 }
 416
 417 /**
 418  * Sort the ou's according to constraints and their sort_key
 419  */
 420 static void co_sort_units(copy_opt_t *co) {
 421         int i, count = 0, costs;
 422         unit_t *ou, **ous;
 423
 424         /* get the number of ous, remove them form the list and fill the array */
 425         list_for_each_entry(unit_t, ou, &co->units, units)
 426                 count++;
 427         ous = alloca(count * sizeof(*ous));
 428
 429         costs = co_get_max_copy_costs(co);
 430
 431         i = 0;
 432         list_for_each_entry(unit_t, ou, &co->units, units)
 433                 ous[i++] = ou;
 434
 435         INIT_LIST_HEAD(&co->units);
 436
 437         assert(count == i && list_empty(&co->units));
 438
 439         for (i=0; i<count; ++i)
 440                 ir_printf("%+F\n", ous[i]->nodes[0]);
 441
 442         qsort(ous, count, sizeof(*ous), compare_ous);
 443
 444         ir_printf("\n\n");
 445         for (i=0; i<count; ++i)
 446                 ir_printf("%+F\n", ous[i]->nodes[0]);
 447
 448         /* reinsert into list in correct order */
 449         for (i=0; i<count; ++i)
 450                 list_add_tail(&ous[i]->units, &co->units);
 451
 452         assert(costs == co_get_max_copy_costs(co));
 453 }
 454 #endif
 455
 456 void co_build_ou_structure(copy_opt_t *co) {
 457         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
 458         INIT_LIST_HEAD(&co->units);
 459         irg_walk_graph(co->irg, co_collect_units, NULL, co);
 460 #ifdef QUICK_AND_DIRTY_HACK
 461         co_sort_units(co);
 462 #endif
 463 }
 464
 465 void co_free_ou_structure(copy_opt_t *co) {
 466         unit_t *curr, *tmp;
 467         ASSERT_OU_AVAIL(co);
 468         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 469                 xfree(curr->nodes);
 470                 xfree(curr->costs);
 471                 xfree(curr);
 472         }
 473         co->units.next = NULL;
 474 }
 475
 476 /* co_solve_heuristic() is implemented in becopyheur.c */
 477
 478 int co_get_max_copy_costs(const copy_opt_t *co) {
 479         int i, res = 0;
 480         unit_t *curr;
 481
 482         ASSERT_OU_AVAIL(co);
 483
 484         list_for_each_entry(unit_t, curr, &co->units, units) {
 485                 res += curr->inevitable_costs;
 486                 for (i=1; i<curr->node_count; ++i)
 487                         res += curr->costs[i];
 488         }
 489         return res;
 490 }
 491
 492 int co_get_inevit_copy_costs(const copy_opt_t *co) {
 493         int res = 0;
 494         unit_t *curr;
 495
 496         ASSERT_OU_AVAIL(co);
 497
 498         list_for_each_entry(unit_t, curr, &co->units, units)
 499                 res += curr->inevitable_costs;
 500         return res;
 501 }
 502
 503 int co_get_copy_costs(const copy_opt_t *co) {
 504         int i, res = 0;
 505         unit_t *curr;
 506
 507         ASSERT_OU_AVAIL(co);
 508
 509         list_for_each_entry(unit_t, curr, &co->units, units) {
 510                 int root_col = get_irn_col(co, curr->nodes[0]);
 511                 DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
 512                 res += curr->inevitable_costs;
 513                 for (i=1; i<curr->node_count; ++i) {
 514                         int arg_col = get_irn_col(co, curr->nodes[i]);
 515                         if (root_col != arg_col) {
 516                                 DBG((dbg, LEVEL_1, "  %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
 517                                 res += curr->costs[i];
 518                         }
 519                 }
 520         }
 521         return res;
 522 }
 523
 524 int co_get_lower_bound(const copy_opt_t *co) {
 525         int res = 0;
 526         unit_t *curr;
 527
 528         ASSERT_OU_AVAIL(co);
 529
 530         list_for_each_entry(unit_t, curr, &co->units, units)
 531                 res += curr->inevitable_costs + curr->min_nodes_costs;
 532         return res;
 533 }
 534
 535 /******************************************************************************
 536    _____                 _        _____ _
 537   / ____|               | |      / ____| |
 538  | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 539  | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 540  | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
 541   \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
 542                   | |                                       __/ |
 543                   |_|                                      |___/
 544  ******************************************************************************/
 545
 546 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
 547         const affinity_node_t *n1 = k1;
 548         const affinity_node_t *n2 = k2;
 549
 550         return (n1->irn != n2->irn);
 551 }
 552
 553 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 554         affinity_node_t new_node, *node;
 555         neighb_t new_nbr, *nbr;
 556         int allocnew;
 557
 558         new_node.irn        = n1;
 559         new_node.degree     = 0;
 560         new_node.neighbours = NULL;
 561         node = set_insert(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn));
 562
 563         allocnew = 1;
 564         for (nbr = node->neighbours; nbr; nbr = nbr->next)
 565                 if (nbr->irn == n2) {
 566                         allocnew = 0;
 567                         break;
 568                 }
 569
 570         /* if we did not find n2 in n1's neighbourhood insert it */
 571         if (allocnew) {
 572                 obstack_grow(&co->obst, &new_nbr, sizeof(new_nbr));
 573                 nbr = obstack_finish(&co->obst);
 574                 nbr->irn   = n2;
 575                 nbr->costs = 0;
 576                 nbr->next  = node->neighbours;
 577                 node->neighbours = nbr;
 578                 node->degree++;
 579         }
 580
 581         /* now nbr points to n1's neighbour-entry of n2 */
 582         nbr->costs += costs;
 583 }
 584
 585 static INLINE void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 586         if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
 587                 add_edge(co, n1, n2, costs);
 588                 add_edge(co, n2, n1, costs);
 589         }
 590 }
 591
 592 static void build_graph_walker(ir_node *irn, void *env) {
 593         copy_opt_t *co = env;
 594         int pos, max;
 595         arch_register_req_t req;
 596         const arch_register_t *reg;
 597
 598         if (!is_curr_reg_class(co, irn) || arch_irn_is(co->aenv, irn, ignore))
 599                 return;
 600
 601         reg = arch_get_irn_register(co->aenv, irn);
 602         if (arch_register_type_is(reg, ignore))
 603                 return;
 604
 605         /* Phis */
 606         if (is_Reg_Phi(irn))
 607                 for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 608                         ir_node *arg = get_irn_n(irn, pos);
 609                         add_edges(co, irn, arg, co->get_costs(irn, arg, pos));
 610                 }
 611
 612         /* Perms */
 613         else if (is_Perm_Proj(co->aenv, irn)) {
 614                 ir_node *arg = get_Perm_src(irn);
 615                 add_edges(co, irn, arg, co->get_costs(irn, arg, 0));
 616         }
 617
 618         /* 2-address code */
 619         else if (is_2addr_code(co->aenv, irn, &req))
 620                 add_edges(co, irn, req.other_same, co->get_costs(irn, req.other_same, 0));
 621 }
 622
 623 void co_build_graph_structure(copy_opt_t *co) {
 624         obstack_init(&co->obst);
 625         co->nodes = new_set(compare_affinity_node_t, 32);
 626
 627         irg_walk_graph(co->irg, build_graph_walker, NULL, co);
 628 }
 629
 630 void co_free_graph_structure(copy_opt_t *co) {
 631         ASSERT_GS_AVAIL(co);
 632
 633         del_set(co->nodes);
 634         obstack_free(&co->obst, NULL);
 635         co->nodes = NULL;
 636 }
 637
 638 /* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */
 639
 640 int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) {
 641         affinity_node_t new_node, *n;
 642
 643         ASSERT_GS_AVAIL(co);
 644
 645         new_node.irn = irn;
 646         n = set_find(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn));
 647         if (n) {
 648                 return (n->degree > 0);
 649         } else
 650                 return 0;
 651 }
 652
 653 void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 654 {
 655         be_ifg_t *ifg = co->cenv->ifg;
 656
 657         ir_node *irn;
 658         void *it, *nit;
 659         int n;
 660
 661         it  = be_ifg_nodes_iter_alloca(ifg);
 662         nit = be_ifg_neighbours_iter_alloca(ifg);
 663
 664         n = 0;
 665         be_ifg_foreach_node(ifg, it, irn) {
 666                 set_irn_link(irn, INT_TO_PTR(n++));
 667         }
 668
 669         fprintf(f, "%d %d\n", n, co->cls->n_regs);
 670
 671         be_ifg_foreach_node(ifg, it, irn) {
 672                 int idx            = PTR_TO_INT(get_irn_link(irn));
 673                 affinity_node_t *a = get_affinity_info(co, irn);
 674
 675                 ir_node *adj;
 676
 677                 be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
 678                         int adj_idx = PTR_TO_INT(get_irn_link(adj));
 679                         if(idx < adj_idx)
 680                                 fprintf(f, "%d %d -1\n", idx, adj_idx);
 681                 }
 682
 683                 if(a) {
 684                         neighb_t *n;
 685
 686                         co_gs_foreach_neighb(a, n) {
 687                                 int n_idx = PTR_TO_INT(get_irn_link(n->irn));
 688                                 if(idx < n_idx)
 689                                         fprintf(f, "%d %d %d\n", idx, n_idx, n->costs);
 690                         }
 691                 }
 692         }
 693 }
 694
 695 void co_solve_park_moon(copy_opt_t *opt)
 696 {
 697
 698 }