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