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