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