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 "execfreq.h"
  18 #include "xmalloc.h"
  19 #include "debug.h"
  20 #include "pmap.h"
  21 #include "irgraph.h"
  22 #include "irgwalk.h"
  23 #include "irprog.h"
  24 #include "irloop_t.h"
  25 #include "iredges_t.h"
  26 #include "phiclass.h"
  27 #include "irbitset.h"
  28 #include "irphase_t.h"
  29
  30 #include "bearch.h"
  31 #include "benode_t.h"
  32 #include "beutil.h"
  33 #include "beifg_t.h"
  34 #include "becopyopt_t.h"
  35 #include "becopystat.h"
  36 #include "belive_t.h"
  37 #include "beinsn_t.h"
  38 #include "besched_t.h"
  39
  40 #ifdef WITH_LIBCORE
  41
  42 /* Insert additional options registration functions here. */
  43 extern void be_co2_register_options(lc_opt_entry_t *grp);
  44
  45 void co_register_options(lc_opt_entry_t *grp)
  46 {
  47         be_co2_register_options(grp);
  48 }
  49 #endif
  50
  51
  52 #undef QUICK_AND_DIRTY_HACK
  53
  54 /******************************************************************************
  55     _____                           _
  56    / ____|                         | |
  57   | |  __  ___ _ __   ___ _ __ __ _| |
  58   | | |_ |/ _ \ '_ \ / _ \ '__/ _` | |
  59   | |__| |  __/ | | |  __/ | | (_| | |
  60    \_____|\___|_| |_|\___|_|  \__,_|_|
  61
  62  ******************************************************************************/
  63
  64 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  65
  66 void be_copy_opt_init(void) {
  67 }
  68
  69 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
  70 {
  71         const char *s1, *s2, *s3;
  72         int len;
  73         copy_opt_t *co;
  74
  75         FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
  76
  77         co = xcalloc(1, sizeof(*co));
  78         co->cenv      = chordal_env;
  79         co->aenv      = chordal_env->birg->main_env->arch_env;
  80         co->irg       = chordal_env->irg;
  81         co->cls       = chordal_env->cls;
  82         co->get_costs = get_costs;
  83
  84         s1 = get_irp_prog_name();
  85         s2 = get_entity_name(get_irg_entity(co->irg));
  86         s3 = chordal_env->cls->name;
  87         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
  88         co->name = xmalloc(len);
  89         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
  90
  91         return co;
  92 }
  93
  94 void free_copy_opt(copy_opt_t *co) {
  95         xfree(co->name);
  96         free(co);
  97 }
  98
  99 int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
 100         arch_register_req_t req;
 101         const arch_register_t *reg;
 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         if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(co->aenv, irn, &req))
 111                 return 1;
 112
 113         return 0;
 114 }
 115
 116 int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
 117         const ir_edge_t *edge;
 118         const arch_register_t *reg;
 119
 120         assert(0 && "Is buggy and obsolete. Do not use");
 121
 122         if (arch_irn_is(co->aenv, irn, ignore))
 123                 return 0;
 124
 125         reg = arch_get_irn_register(co->aenv, irn);
 126         if (arch_register_type_is(reg, ignore))
 127                 return 0;
 128
 129         foreach_out_edge(irn, edge) {
 130                 ir_node *n = edge->src;
 131
 132                 if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
 133                         arch_register_req_t req;
 134                         arch_get_register_req(co->aenv, &req, n, -1);
 135
 136                         if(is_Reg_Phi(n) ||
 137                            is_Perm(co->aenv, n) ||
 138                            (arch_register_req_is(&req, should_be_same) && req.other_same == irn)
 139                           )
 140                                 return 1;
 141                 }
 142         }
 143
 144         return 0;
 145 }
 146
 147 int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 148         int cost = 0;
 149         ir_loop *loop;
 150         ir_node *root_block = get_nodes_block(root);
 151
 152         if (is_Phi(root)) {
 153                 /* for phis the copies are placed in the corresponding pred-block */
 154                 loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
 155         } else {
 156                 /* a perm places the copy in the same block as it resides */
 157                 loop = get_irn_loop(root_block);
 158         }
 159         if (loop) {
 160                 int d = get_loop_depth(loop);
 161                 cost = d*d;
 162         }
 163         return cost+1;
 164 }
 165
 166 int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 167         ir_node *root_bl = get_nodes_block(root);
 168         ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
 169         return (int) get_block_execfreq(co->cenv->exec_freq, copy_bl);
 170 }
 171
 172
 173 int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 174         return 1;
 175 }
 176
 177 /******************************************************************************
 178    ____        _   _    _       _ _          _____ _
 179   / __ \      | | | |  | |     (_) |        / ____| |
 180  | |  | |_ __ | |_| |  | |_ __  _| |_ ___  | (___ | |_ ___  _ __ __ _  __ _  ___
 181  | |  | | '_ \| __| |  | | '_ \| | __/ __|  \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 182  | |__| | |_) | |_| |__| | | | | | |_\__ \  ____) | || (_) | | | (_| | (_| |  __/
 183   \____/| .__/ \__|\____/|_| |_|_|\__|___/ |_____/ \__\___/|_|  \__,_|\__, |\___|
 184         | |                                                            __/ |
 185         |_|                                                           |___/
 186  ******************************************************************************/
 187
 188 /**
 189  * Determines a maximum weighted independent set with respect to
 190  * the interference and conflict edges of all nodes in a qnode.
 191  */
 192 static int ou_max_ind_set_costs(unit_t *ou) {
 193         be_chordal_env_t *chordal_env = ou->co->cenv;
 194         ir_node **safe, **unsafe;
 195         int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
 196         bitset_t *curr;
 197         int max, pos, curr_weight, best_weight = 0;
 198
 199         /* assign the nodes into two groups.
 200          * safe: node has no interference, hence it is in every max stable set.
 201          * unsafe: node has an interference
 202          */
 203         safe = alloca((ou->node_count-1) * sizeof(*safe));
 204         safe_costs = 0;
 205         safe_count = 0;
 206         unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
 207         unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
 208         unsafe_count = 0;
 209         for(i=1; i<ou->node_count; ++i) {
 210                 int is_safe = 1;
 211                 for(o=1; o<ou->node_count; ++o) {
 212                         if (i==o)
 213                                 continue;
 214                         if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
 215                                 unsafe_costs[unsafe_count] = ou->costs[i];
 216                                 unsafe[unsafe_count] = ou->nodes[i];
 217                                 ++unsafe_count;
 218                                 is_safe = 0;
 219                                 break;
 220                         }
 221                 }
 222                 if (is_safe) {
 223                         safe_costs += ou->costs[i];
 224                         safe[safe_count++] = ou->nodes[i];
 225                 }
 226         }
 227
 228
 229         /* now compute the best set out of the unsafe nodes*/
 230         if (unsafe_count > MIS_HEUR_TRIGGER) {
 231                 bitset_t *best = bitset_alloca(unsafe_count);
 232                 /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
 233                 for (i=0; i<unsafe_count; ++i) {
 234                         bitset_set(best, i);
 235                         /* check if it is a stable set */
 236                         for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
 237                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
 238                                         bitset_clear(best, i); /* clear the bit and try next one */
 239                                         break;
 240                                 }
 241                 }
 242                 /* compute the weight */
 243                 bitset_foreach(best, pos)
 244                         best_weight += unsafe_costs[pos];
 245         } else {
 246                 /* Exact Algorithm: Brute force */
 247                 curr = bitset_alloca(unsafe_count);
 248                 bitset_set_all(curr);
 249                 while ((max = bitset_popcnt(curr)) != 0) {
 250                         /* check if curr is a stable set */
 251                         for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
 252                                 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) */
 253                                                 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
 254                                                         goto no_stable_set;
 255
 256                         /* if we arrive here, we have a stable set */
 257                         /* compute the weigth of the stable set*/
 258                         curr_weight = 0;
 259                         bitset_foreach(curr, pos)
 260                                 curr_weight += unsafe_costs[pos];
 261
 262                         /* any better ? */
 263                         if (curr_weight > best_weight) {
 264                                 best_weight = curr_weight;
 265                         }
 266
 267         no_stable_set:
 268                         bitset_minus1(curr);
 269                 }
 270         }
 271
 272         return safe_costs+best_weight;
 273 }
 274
 275 static void co_collect_units(ir_node *irn, void *env) {
 276         copy_opt_t *co = env;
 277         unit_t *unit;
 278         arch_register_req_t req;
 279
 280         if (!is_curr_reg_class(co, irn))
 281                 return;
 282         if (!co_is_optimizable_root(co, irn))
 283                 return;
 284
 285         /* Init a new unit */
 286         unit = xcalloc(1, sizeof(*unit));
 287         unit->co = co;
 288         unit->node_count = 1;
 289         INIT_LIST_HEAD(&unit->queue);
 290
 291         /* Phi with some/all of its arguments */
 292         if (is_Reg_Phi(irn)) {
 293                 int i, arity;
 294
 295                 /* init */
 296                 arity = get_irn_arity(irn);
 297                 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
 298                 unit->costs = xmalloc((arity+1) * sizeof(*unit->costs));
 299                 unit->nodes[0] = irn;
 300
 301                 /* fill */
 302                 for (i=0; i<arity; ++i) {
 303                         int o, arg_pos;
 304                         ir_node *arg = get_irn_n(irn, i);
 305
 306                         assert(is_curr_reg_class(co, arg) && "Argument not in same register class.");
 307                         if (arg == irn)
 308                                 continue;
 309                         if (nodes_interfere(co->cenv, irn, arg)) {
 310                                 unit->inevitable_costs += co->get_costs(co, irn, arg, i);
 311                                 continue;
 312                         }
 313
 314                         /* Else insert the argument of the phi to the members of this ou */
 315                         DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
 316
 317                         /* Check if arg has occurred at a prior position in the arg/list */
 318                         arg_pos = 0;
 319                         for (o=0; o<unit->node_count; ++o)
 320                                 if (unit->nodes[o] == arg) {
 321                                         arg_pos = o;
 322                                         break;
 323                                 }
 324
 325                         if (!arg_pos) { /* a new argument */
 326                                 /* insert node, set costs */
 327                                 unit->nodes[unit->node_count] = arg;
 328                                 unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
 329                                 unit->node_count++;
 330                         } else { /* arg has occured before in same phi */
 331                                 /* increase costs for existing arg */
 332                                 unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
 333                         }
 334                 }
 335                 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
 336                 unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
 337         } else
 338
 339         /* Proj of a perm with corresponding arg */
 340         if (is_Perm_Proj(co->aenv, irn)) {
 341                 assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 342                 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 343                 unit->costs = xmalloc(2 * sizeof(*unit->costs));
 344                 unit->node_count = 2;
 345                 unit->nodes[0] = irn;
 346                 unit->nodes[1] = get_Perm_src(irn);
 347                 unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
 348         } else
 349
 350         /* Src == Tgt of a 2-addr-code instruction */
 351         if (is_2addr_code(co->aenv, irn, &req)) {
 352                 ir_node *other = req.other_same;
 353                 if (!nodes_interfere(co->cenv, irn, other)) {
 354                         unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 355                         unit->costs = xmalloc(2 * sizeof(*unit->costs));
 356                         unit->node_count = 2;
 357                         unit->nodes[0] = irn;
 358                         unit->nodes[1] = other;
 359                         unit->costs[1] = co->get_costs(co, irn, other, -1);
 360                 }
 361         } else
 362                 assert(0 && "This is not an optimizable node!");
 363
 364         /* Insert the new unit at a position according to its costs */
 365         if (unit->node_count > 1) {
 366                 int i;
 367                 struct list_head *tmp;
 368
 369                 /* Determine the maximum costs this unit can cause: all_nodes_cost */
 370                 for(i=1; i<unit->node_count; ++i) {
 371                         unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
 372                         unit->all_nodes_costs += unit->costs[i];
 373                 }
 374
 375                 /* Determine the minimal costs this unit will cause: min_nodes_costs */
 376                 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
 377                 /* Insert the new ou according to its sort_key */
 378                 tmp = &co->units;
 379                 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
 380                         tmp = tmp->next;
 381                 list_add(&unit->units, tmp);
 382         } else {
 383                 free(unit);
 384         }
 385 }
 386
 387 #ifdef QUICK_AND_DIRTY_HACK
 388
 389 static int compare_ous(const void *k1, const void *k2) {
 390         const unit_t *u1 = *((const unit_t **) k1);
 391         const unit_t *u2 = *((const unit_t **) k2);
 392         int i, o, u1_has_constr, u2_has_constr;
 393         arch_register_req_t req;
 394         const arch_env_t *aenv = u1->co->aenv;
 395
 396         /* Units with constraints come first */
 397         u1_has_constr = 0;
 398         for (i=0; i<u1->node_count; ++i) {
 399                 arch_get_register_req(aenv, &req, u1->nodes[i], -1);
 400                 if (arch_register_req_is(&req, limited)) {
 401                         u1_has_constr = 1;
 402                         break;
 403                 }
 404         }
 405
 406         u2_has_constr = 0;
 407         for (i=0; i<u2->node_count; ++i) {
 408                 arch_get_register_req(aenv, &req, u2->nodes[i], -1);
 409                 if (arch_register_req_is(&req, limited)) {
 410                         u2_has_constr = 1;
 411                         break;
 412                 }
 413         }
 414
 415         if (u1_has_constr != u2_has_constr)
 416                 return u2_has_constr - u1_has_constr;
 417
 418         /* Now check, whether the two units are connected */
 419 #if 0
 420         for (i=0; i<u1->node_count; ++i)
 421                 for (o=0; o<u2->node_count; ++o)
 422                         if (u1->nodes[i] == u2->nodes[o])
 423                                 return 0;
 424 #endif
 425
 426         /* After all, the sort key decides. Greater keys come first. */
 427         return u2->sort_key - u1->sort_key;
 428
 429 }
 430
 431 /**
 432  * Sort the ou's according to constraints and their sort_key
 433  */
 434 static void co_sort_units(copy_opt_t *co) {
 435         int i, count = 0, costs;
 436         unit_t *ou, **ous;
 437
 438         /* get the number of ous, remove them form the list and fill the array */
 439         list_for_each_entry(unit_t, ou, &co->units, units)
 440                 count++;
 441         ous = alloca(count * sizeof(*ous));
 442
 443         costs = co_get_max_copy_costs(co);
 444
 445         i = 0;
 446         list_for_each_entry(unit_t, ou, &co->units, units)
 447                 ous[i++] = ou;
 448
 449         INIT_LIST_HEAD(&co->units);
 450
 451         assert(count == i && list_empty(&co->units));
 452
 453         for (i=0; i<count; ++i)
 454                 ir_printf("%+F\n", ous[i]->nodes[0]);
 455
 456         qsort(ous, count, sizeof(*ous), compare_ous);
 457
 458         ir_printf("\n\n");
 459         for (i=0; i<count; ++i)
 460                 ir_printf("%+F\n", ous[i]->nodes[0]);
 461
 462         /* reinsert into list in correct order */
 463         for (i=0; i<count; ++i)
 464                 list_add_tail(&ous[i]->units, &co->units);
 465
 466         assert(costs == co_get_max_copy_costs(co));
 467 }
 468 #endif
 469
 470 void co_build_ou_structure(copy_opt_t *co) {
 471         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
 472         INIT_LIST_HEAD(&co->units);
 473         irg_walk_graph(co->irg, co_collect_units, NULL, co);
 474 #ifdef QUICK_AND_DIRTY_HACK
 475         co_sort_units(co);
 476 #endif
 477 }
 478
 479 void co_free_ou_structure(copy_opt_t *co) {
 480         unit_t *curr, *tmp;
 481         ASSERT_OU_AVAIL(co);
 482         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 483                 xfree(curr->nodes);
 484                 xfree(curr->costs);
 485                 xfree(curr);
 486         }
 487         co->units.next = NULL;
 488 }
 489
 490 /* co_solve_heuristic() is implemented in becopyheur.c */
 491
 492 int co_get_max_copy_costs(const copy_opt_t *co) {
 493         int i, 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                 for (i=1; i<curr->node_count; ++i)
 501                         res += curr->costs[i];
 502         }
 503         return res;
 504 }
 505
 506 int co_get_inevit_copy_costs(const copy_opt_t *co) {
 507         int res = 0;
 508         unit_t *curr;
 509
 510         ASSERT_OU_AVAIL(co);
 511
 512         list_for_each_entry(unit_t, curr, &co->units, units)
 513                 res += curr->inevitable_costs;
 514         return res;
 515 }
 516
 517 int co_get_copy_costs(const copy_opt_t *co) {
 518         int i, res = 0;
 519         unit_t *curr;
 520
 521         ASSERT_OU_AVAIL(co);
 522
 523         list_for_each_entry(unit_t, curr, &co->units, units) {
 524                 int root_col = get_irn_col(co, curr->nodes[0]);
 525                 DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
 526                 res += curr->inevitable_costs;
 527                 for (i=1; i<curr->node_count; ++i) {
 528                         int arg_col = get_irn_col(co, curr->nodes[i]);
 529                         if (root_col != arg_col) {
 530                                 DBG((dbg, LEVEL_1, "  %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
 531                                 res += curr->costs[i];
 532                         }
 533                 }
 534         }
 535         return res;
 536 }
 537
 538 int co_get_lower_bound(const copy_opt_t *co) {
 539         int res = 0;
 540         unit_t *curr;
 541
 542         ASSERT_OU_AVAIL(co);
 543
 544         list_for_each_entry(unit_t, curr, &co->units, units)
 545                 res += curr->inevitable_costs + curr->min_nodes_costs;
 546         return res;
 547 }
 548
 549 /******************************************************************************
 550    _____                 _        _____ _
 551   / ____|               | |      / ____| |
 552  | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 553  | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 554  | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
 555   \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
 556                   | |                                       __/ |
 557                   |_|                                      |___/
 558  ******************************************************************************/
 559
 560 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
 561         const affinity_node_t *n1 = k1;
 562         const affinity_node_t *n2 = k2;
 563
 564         return (n1->irn != n2->irn);
 565 }
 566
 567 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 568         affinity_node_t new_node, *node;
 569         neighb_t new_nbr, *nbr;
 570         int allocnew;
 571
 572         new_node.irn        = n1;
 573         new_node.degree     = 0;
 574         new_node.neighbours = NULL;
 575         node = set_insert(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn));
 576
 577         allocnew = 1;
 578         for (nbr = node->neighbours; nbr; nbr = nbr->next)
 579                 if (nbr->irn == n2) {
 580                         allocnew = 0;
 581                         break;
 582                 }
 583
 584         /* if we did not find n2 in n1's neighbourhood insert it */
 585         if (allocnew) {
 586                 obstack_grow(&co->obst, &new_nbr, sizeof(new_nbr));
 587                 nbr = obstack_finish(&co->obst);
 588                 nbr->irn   = n2;
 589                 nbr->costs = 0;
 590                 nbr->next  = node->neighbours;
 591                 node->neighbours = nbr;
 592                 node->degree++;
 593         }
 594
 595         /* now nbr points to n1's neighbour-entry of n2 */
 596         nbr->costs += costs;
 597 }
 598
 599 static INLINE void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 600         if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
 601                 add_edge(co, n1, n2, costs);
 602                 add_edge(co, n2, n1, costs);
 603         }
 604 }
 605
 606 static void build_graph_walker(ir_node *irn, void *env) {
 607         copy_opt_t *co = env;
 608         int pos, max;
 609         arch_register_req_t req;
 610         const arch_register_t *reg;
 611
 612         if (!is_curr_reg_class(co, irn) || arch_irn_is(co->aenv, irn, ignore))
 613                 return;
 614
 615         reg = arch_get_irn_register(co->aenv, irn);
 616         if (arch_register_type_is(reg, ignore))
 617                 return;
 618
 619         /* Phis */
 620         if (is_Reg_Phi(irn))
 621                 for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 622                         ir_node *arg = get_irn_n(irn, pos);
 623                         add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
 624                 }
 625
 626         /* Perms */
 627         else if (is_Perm_Proj(co->aenv, irn)) {
 628                 ir_node *arg = get_Perm_src(irn);
 629                 add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
 630         }
 631
 632         /* 2-address code */
 633         else if (is_2addr_code(co->aenv, irn, &req))
 634                 add_edges(co, irn, req.other_same, co->get_costs(co, irn, req.other_same, 0));
 635 }
 636
 637 void co_build_graph_structure(copy_opt_t *co) {
 638         obstack_init(&co->obst);
 639         co->nodes = new_set(compare_affinity_node_t, 32);
 640
 641         irg_walk_graph(co->irg, build_graph_walker, NULL, co);
 642 }
 643
 644 void co_free_graph_structure(copy_opt_t *co) {
 645         ASSERT_GS_AVAIL(co);
 646
 647         del_set(co->nodes);
 648         obstack_free(&co->obst, NULL);
 649         co->nodes = NULL;
 650 }
 651
 652 /* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */
 653
 654 int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) {
 655         affinity_node_t new_node, *n;
 656
 657         ASSERT_GS_AVAIL(co);
 658
 659         new_node.irn = irn;
 660         n = set_find(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn));
 661         if (n) {
 662                 return (n->degree > 0);
 663         } else
 664                 return 0;
 665 }
 666
 667 void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 668 {
 669         be_ifg_t *ifg  = co->cenv->ifg;
 670         int *color_map = alloca(co->cls->n_regs * sizeof(color_map[0]));
 671         bitset_t *adm  = bitset_alloca(co->cls->n_regs);
 672
 673         ir_node *irn;
 674         void *it, *nit;
 675         int i, n, n_regs;
 676
 677         n_regs = 0;
 678         for(i = 0; i < co->cls->n_regs; ++i) {
 679                 const arch_register_t *reg = &co->cls->regs[i];
 680                 color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_regs++;
 681         }
 682
 683         /*
 684          * n contains the first node number.
 685          * the values below n are the pre-colored register nodes
 686          */
 687
 688         it  = be_ifg_nodes_iter_alloca(ifg);
 689         nit = be_ifg_neighbours_iter_alloca(ifg);
 690
 691         n = n_regs;
 692         be_ifg_foreach_node(ifg, it, irn) {
 693                 if(!arch_irn_is(co->aenv, irn, ignore))
 694                         set_irn_link(irn, INT_TO_PTR(n++));
 695         }
 696
 697         fprintf(f, "%d %d\n", n, n_regs);
 698
 699         be_ifg_foreach_node(ifg, it, irn) {
 700                 if(!arch_irn_is(co->aenv, irn, ignore)) {
 701                         int idx            = PTR_TO_INT(get_irn_link(irn));
 702                         affinity_node_t *a = get_affinity_info(co, irn);
 703
 704                         arch_register_req_t req;
 705                         ir_node *adj;
 706
 707                         arch_get_register_req(co->aenv, &req, irn, BE_OUT_POS(0));
 708                         if(arch_register_req_is(&req, limited)) {
 709                                 bitset_clear_all(adm);
 710                                 req.limited(req.limited_env, adm);
 711                                 for(i = 0; i < co->cls->n_regs; ++i)
 712                                         if(!bitset_is_set(adm, i) && color_map[i] >= 0)
 713                                                 fprintf(f, "%d %d -1\n", color_map[i], idx);
 714
 715                         }
 716
 717
 718                         be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
 719                                 if(!arch_irn_is(co->aenv, adj, ignore)) {
 720                                         int adj_idx = PTR_TO_INT(get_irn_link(adj));
 721                                         if(idx < adj_idx)
 722                                                 fprintf(f, "%d %d -1\n", idx, adj_idx);
 723                                 }
 724                         }
 725
 726                         if(a) {
 727                                 neighb_t *n;
 728
 729                                 co_gs_foreach_neighb(a, n) {
 730                                         if(!arch_irn_is(co->aenv, n->irn, ignore)) {
 731                                                 int n_idx = PTR_TO_INT(get_irn_link(n->irn));
 732                                                 if(idx < n_idx)
 733                                                         fprintf(f, "%d %d %d\n", idx, n_idx, n->costs);
 734                                         }
 735                                 }
 736                         }
 737                 }
 738         }
 739 }
 740
 741 typedef struct _appel_clique_walker_t {
 742         phase_t ph;
 743         const copy_opt_t *co;
 744         int curr_nr;
 745         int node_count;
 746         FILE *f;
 747         int dumb;
 748         int *color_map;
 749         struct obstack obst;
 750 } appel_clique_walker_t;
 751
 752 typedef struct _appel_block_info_t {
 753         int *live_end_nr;
 754         int *live_in_nr;
 755         int *phi_nr;
 756         ir_node **live_end;
 757         ir_node **live_in;
 758         ir_node **phi;
 759         int n_live_end;
 760         int n_live_in;
 761         int n_phi;
 762 } appel_block_info_t;
 763
 764 static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
 765 {
 766 #if 0
 767         double freq = get_block_execfreq(env->co->cenv->execfreq, bl);
 768         int res = (int) freq;
 769         return res == 0 ? 1 : res;
 770 #else
 771         ir_loop *loop = get_irn_loop(bl);
 772         if(loop) {
 773                 int d = get_loop_depth(loop);
 774                 return 1 + d * d;
 775         }
 776         return 1;
 777 #endif
 778 }
 779
 780 static void *appel_clique_walker_irn_init(phase_t *phase, ir_node *irn, void *old)
 781 {
 782         appel_block_info_t *res = NULL;
 783
 784         if(is_Block(irn)) {
 785                 appel_clique_walker_t *d = (void *) phase;
 786                 res = phase_alloc(phase, sizeof(res[0]));
 787                 res->phi_nr      = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
 788                 res->live_end_nr = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
 789                 res->live_in_nr  = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in_nr));
 790                 res->live_end    = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end));
 791                 res->live_in     = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
 792                 res->phi         = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
 793         }
 794
 795         return res;
 796 }
 797
 798 typedef struct _insn_list_t {
 799         be_insn_t *insn;
 800         struct list_head list;
 801 } insn_list_t;
 802
 803 static int appel_get_live_end_nr(appel_clique_walker_t *env, ir_node *bl, ir_node *irn)
 804 {
 805         appel_block_info_t *bli = phase_get_irn_data(&env->ph, bl);
 806         int i;
 807
 808         for(i = 0; i < bli->n_live_end; ++i)
 809                 if(bli->live_end[i] == irn)
 810                         return bli->live_end_nr[i];
 811
 812         return -1;
 813 }
 814
 815 static int appel_dump_clique(appel_clique_walker_t *env, pset *live, ir_node *bl, int curr_nr, int start_nr)
 816 {
 817         ir_node **live_arr = alloca(env->co->cls->n_regs * sizeof(live_arr[0]));
 818         ir_node *irn;
 819         int n_live;
 820         int j;
 821
 822         n_live = 0;
 823         foreach_pset(live, irn)
 824                 live_arr[n_live++] = irn;
 825
 826         /* dump the live after clique */
 827         if(!env->dumb) {
 828                 for(j = 0; j < n_live; ++j) {
 829                         int k;
 830
 831                         for(k = j + 1; k < n_live; ++k) {
 832                                 fprintf(env->f, "%d %d -1 ", curr_nr + j, curr_nr + k);
 833                         }
 834                         fprintf(env->f, "\n");
 835                 }
 836         }
 837
 838         /* dump the affinities */
 839         for(j = 0; !env->dumb && j < n_live; ++j) {
 840                 ir_node *irn = live_arr[j];
 841                 int old_nr = PTR_TO_INT(get_irn_link(irn));
 842
 843                 /* if the node was already live in the last insn dump the affinity */
 844                 if(old_nr > start_nr) {
 845                         int weight = appel_aff_weight(env, bl);
 846                         fprintf(env->f, "%d %d %d\n", old_nr, curr_nr + j, weight);
 847                 }
 848         }
 849
 850         /* set the current numbers into the link field. */
 851         for(j = 0; j < n_live; ++j) {
 852                 ir_node *irn = live_arr[j];
 853                 set_irn_link(irn, INT_TO_PTR(curr_nr + j));
 854         }
 855
 856         return curr_nr + n_live;
 857 }
 858
 859 static void appel_walker(ir_node *bl, void *data)
 860 {
 861         appel_clique_walker_t *env = data;
 862         appel_block_info_t *bli    = phase_get_or_set_irn_data(&env->ph, bl);
 863         struct obstack *obst       = &env->obst;
 864         void *base                 = obstack_base(obst);
 865         pset *live                 = pset_new_ptr_default();
 866
 867         int n_insns  = 0;
 868         int n_nodes  = 0;
 869         int start_nr = env->curr_nr;
 870         int curr_nr  = start_nr;
 871
 872         be_insn_env_t insn_env;
 873         int i, j;
 874         ir_node *irn;
 875         be_insn_t **insns;
 876
 877         insn_env.aenv = env->co->aenv;
 878         insn_env.cls  = env->co->cls;
 879         insn_env.obst = obst;
 880         insn_env.ignore_colors = env->co->cenv->ignore_colors;
 881
 882         /* Guess how many insns will be in this block. */
 883         sched_foreach(bl, irn)
 884                 n_nodes++;
 885
 886         bli->n_phi = 0;
 887         insns = malloc(n_nodes * sizeof(insns[0]));
 888
 889         /* Put all insns in an array. */
 890         irn = sched_first(bl);
 891         while(!sched_is_end(irn)) {
 892                 be_insn_t *insn;
 893                 insn = be_scan_insn(&insn_env, irn);
 894                 insns[n_insns++] = insn;
 895                 irn = insn->next_insn;
 896         }
 897
 898         DBG((env->co->cenv->dbg, LEVEL_2, "%+F\n", bl));
 899         be_liveness_end_of_block(env->co->aenv, env->co->cls, bl, live);
 900
 901         /* Generate the bad and ugly. */
 902         for(i = n_insns - 1; i >= 0; --i) {
 903                 be_insn_t *insn = insns[i];
 904
 905                 /* The first live set has to be saved in the block border set. */
 906                 if(i == n_insns - 1) {
 907                         j = 0;
 908                         foreach_pset(live, irn) {
 909                                 bli->live_end[j]    = irn;
 910                                 bli->live_end_nr[j] = curr_nr + j;
 911                                 ++j;
 912                         }
 913                         bli->n_live_end = j;
 914                 }
 915
 916                 if(!env->dumb) {
 917                         for(j = 0; j < insn->use_start; ++j) {
 918                                 ir_node *op   = insn->ops[j].carrier;
 919                                 bitset_t *adm = insn->ops[j].regs;
 920                                 int k;
 921                                 int nr;
 922
 923                                 if(!insn->ops[j].has_constraints)
 924                                         continue;
 925
 926                                 nr = 0;
 927                                 foreach_pset(live, irn) {
 928                                         if(irn == op) {
 929                                                 pset_break(live);
 930                                                 break;
 931                                         }
 932                                         ++nr;
 933                                 }
 934
 935                                 assert(nr < pset_count(live));
 936
 937                                 for(k = 0; k < env->co->cls->n_regs; ++k) {
 938                                         int mapped_col = env->color_map[k];
 939                                         if(mapped_col >= 0 && !bitset_is_set(adm, k) && !bitset_is_set(env->co->cenv->ignore_colors, k))
 940                                                 fprintf(env->f, "%d %d -1\n", curr_nr + nr, mapped_col);
 941                                 }
 942                         }
 943                 }
 944
 945                 /* dump the clique and update the stuff. */
 946                 curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
 947
 948                 /* remove all defs. */
 949                 for(j = 0; j < insn->use_start; ++j)
 950                         pset_remove_ptr(live, insn->ops[j].carrier);
 951
 952                 if(is_Phi(insn->irn) && arch_irn_consider_in_reg_alloc(env->co->aenv, env->co->cls, insn->irn)) {
 953                         bli->phi[bli->n_phi]    = insn->irn;
 954                         bli->phi_nr[bli->n_phi] = PTR_TO_INT(get_irn_link(insn->irn));
 955                         bli->n_phi++;
 956                 }
 957
 958                 /* add all uses */
 959                 else
 960                         for(j = insn->use_start; j < insn->n_ops; ++j)
 961                                 pset_insert_ptr(live, insn->ops[j].carrier);
 962         }
 963
 964         /* print the start clique. */
 965         curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
 966
 967         i = 0;
 968         foreach_pset(live, irn) {
 969                 bli->live_in[i]    = irn;
 970                 bli->live_in_nr[i] = PTR_TO_INT(get_irn_link(irn));
 971                 ++i;
 972         }
 973         bli->n_live_in = i;
 974
 975         del_pset(live);
 976         free(insns);
 977         obstack_free(obst, base);
 978         env->curr_nr = curr_nr;
 979 }
 980
 981 static void appel_inter_block_aff(ir_node *bl, void *data)
 982 {
 983         appel_clique_walker_t *env = data;
 984         appel_block_info_t *bli    = phase_get_irn_data(&env->ph, bl);
 985
 986         int i, j, n;
 987
 988         for(i = 0; i < bli->n_live_in; ++i) {
 989                 ir_node *irn = bli->live_in[i];
 990
 991                 for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) {
 992                         ir_node *pred  = get_Block_cfgpred_block(bl, j);
 993                         appel_block_info_t *pred_bli = phase_get_irn_data(&env->ph, pred);
 994
 995                         int nr = appel_get_live_end_nr(env, pred, irn);
 996                         assert(nr >= 0);
 997                         fprintf(env->f, "%d %d 1\n", bli->live_in_nr[i], nr);
 998                 }
 999         }
1000
1001         for(i = 0; i < bli->n_phi; ++i) {
1002                 ir_node *irn = bli->phi[i];
1003
1004                 for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) {
1005                         ir_node *pred  = get_Block_cfgpred_block(bl, j);
1006                         appel_block_info_t *pred_bli = phase_get_irn_data(&env->ph, pred);
1007                         ir_node *op = get_irn_n(irn, j);
1008
1009                         int nr = appel_get_live_end_nr(env, pred, op);
1010                         assert(nr >= 0);
1011                         fprintf(env->f, "%d %d 1\n", bli->phi_nr[i], nr);
1012                 }
1013         }
1014
1015 }
1016
1017 void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f)
1018 {
1019         int i;
1020         int n_colors;
1021         appel_clique_walker_t env;
1022         bitset_t *adm = bitset_alloca(co->cls->n_regs);
1023
1024         be_liveness(co->irg);
1025         obstack_init(&env.obst);
1026         phase_init(&env.ph, "appel_clique_dumper", co->irg, PHASE_DEFAULT_GROWTH, appel_clique_walker_irn_init);
1027         env.curr_nr = co->cls->n_regs;
1028         env.co = co;
1029         env.f = f;
1030
1031         bitset_copy(adm, co->cenv->ignore_colors);
1032         bitset_flip_all(adm);
1033
1034         /* Make color map. */
1035         env.color_map = alloca(co->cls->n_regs * sizeof(env.color_map[0]));
1036         for(i = 0, n_colors = 0; i < co->cls->n_regs; ++i) {
1037                 const arch_register_t *reg = &co->cls->regs[i];
1038                 env.color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_colors++;
1039         }
1040
1041         env.dumb = 1;
1042         env.curr_nr = n_colors;
1043         irg_block_walk_graph(co->irg, firm_clear_link, NULL, NULL);
1044         irg_block_walk_graph(co->irg, appel_walker, NULL, &env);
1045
1046         fprintf(f, "%d %d\n", env.curr_nr, n_colors);
1047
1048         /* make the first k nodes interfere */
1049         for(i = 0; i < n_colors; ++i) {
1050                 int j;
1051                 for(j = i + 1; j < n_colors; ++j)
1052                         fprintf(f, "%d %d -1 ", i, j);
1053                 fprintf(f, "\n");
1054         }
1055
1056         env.dumb = 0;
1057         env.curr_nr = n_colors;
1058         irg_block_walk_graph(co->irg, firm_clear_link, NULL, NULL);
1059         irg_block_walk_graph(co->irg, appel_walker, NULL, &env);
1060         irg_block_walk_graph(co->irg, appel_inter_block_aff, NULL, &env);
1061         obstack_free(&env.obst, NULL);
1062 }
1063
1064
1065 void co_solve_park_moon(copy_opt_t *opt)
1066 {
1067
1068 }