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