nsz Git - libfirm/blob - ir/opt/gvn_pre.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/gvn_pre.c
   4  * Purpose:     Global Value Numbering Partial Redundancy Elimination
   5  *              (VanDrunen Hosking 2004)
   6  * Author:      Michael Beck, Rubino Geiss
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2006 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include "config.h"
  15 #endif
  16
  17 #include <assert.h>
  18
  19 #include "irgraph_t.h"
  20 #include "irgwalk.h"
  21 #include "irdom.h"
  22 #include "irouts.h"
  23 #include "pset.h"
  24 #include "irgopt.h"
  25 #include "iropt_t.h"
  26 #include "irprintf.h"
  27 #include "irnode_t.h"
  28 #include "ircons.h"
  29 #include "irgmod.h"
  30 #include "debug.h"
  31 #include "gvn_pre.h"
  32
  33 /* */
  34 typedef struct block_info {
  35   pset *nodes;        /**< the set of nodes per block */
  36   pset *avail_out;    /**< the Avail_out set for a block */
  37   pset *antic_in;     /**< the Antic_in set for a block */
  38   pset *new_set;      /**< the set of all new values for a block */
  39   ir_node *avail;     /**< the get_map(avail, block) result */
  40   int not_found;      /**< non-zero, if avail was not found in this block */
  41   struct block_info *next;
  42 } block_info;
  43
  44 typedef struct pre_env {
  45   struct obstack *obst;   /**< the obstack to allocate on */
  46   ir_node *start_block;   /**< the start block of the current graph */
  47   ir_node *end_block;     /**< the end block of the current graph */
  48   block_info *list;       /**< links all block info entires for easier recovery */
  49   int changes;            /**< non-zero, if calculation of Antic_in has changed */
  50 } pre_env;
  51
  52 /** The debug module handle. */
  53 static firm_dbg_module_t *dbg;
  54
  55 /**
  56  * returns non-zero if a node is movable.
  57  */
  58 static int is_nice_value(ir_node *n) {
  59   ir_mode *mode = get_irn_mode(n);
  60
  61   if (!mode_is_data(mode))
  62     return 0;
  63   if (is_irn_constlike(n))
  64     return 0;
  65   return (get_irn_pinned(n) != op_pin_state_pinned);
  66 }
  67
  68 #define pset_foreach(v, s)  for ((v) = pset_first(s); (v); (v) = pset_next(s))
  69
  70 typedef unsigned (*HASH_FUNC)(void *);
  71
  72 /** computes dst = dst \/ src */
  73 static void pset_union(pset *dst, pset *src, HASH_FUNC hash)
  74 {
  75   void *entry;
  76
  77   pset_foreach(entry, src) {
  78     pset_insert(dst, entry, hash(entry));
  79   }
  80 }
  81
  82 #define pset_union(d, s)  pset_union(d, s, (HASH_FUNC)ir_node_hash)
  83
  84 #ifdef DEBUG_libfirm
  85 /**
  86  * Dump the Avail or Antic sets
  87  */
  88 static void dump_set(pset *set, char *txt, ir_node *block)
  89 {
  90   ir_node *n;
  91   int i;
  92
  93   DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
  94   i = 0;
  95   pset_foreach(n, set) {
  96     if ((i & 3) == 3)
  97       DB((dbg, LEVEL_2, "\n"));
  98     DB((dbg, LEVEL_2, " %+F,", n));
  99     ++i;
 100   }
 101   DB((dbg, LEVEL_2, "\n}\n"));
 102 }  /* dump_set */
 103
 104 #else
 105 #define dump_set(set, txt, block)
 106 #endif /* DEBUG_libfirm */
 107
 108
 109 /**
 110  * Return the block info of a block
 111  */
 112 static block_info *get_block_info(ir_node *block) {
 113   return get_irn_link(block);
 114 }
 115
 116 /**
 117  * computes Avail_out(block):
 118  *
 119  * Avail_in(block)  = Avail_out(dom(block))
 120  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
 121  *
 122  * Precondition:
 123  *  This function must be called in the top-down dominance order:
 124  *  Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
 125  */
 126 static void compute_avail_top_down(ir_node *block, void *ctx)
 127 {
 128   pre_env *env = ctx;
 129   block_info *dom_info;
 130   block_info *info = get_block_info(block);
 131   ir_node *dom_blk;
 132
 133   /* we don't need the end block Avail */
 134   if (block == env->end_block)
 135     return;
 136
 137   pset_union(info->avail_out, info->nodes);
 138
 139   /* the root has no dominator */
 140   if (block != env->start_block) {
 141     dom_blk = get_Block_idom(block);
 142     assert(is_Block(dom_blk));
 143
 144     dom_info = get_block_info(dom_blk);
 145     assert(dom_info);
 146
 147     pset_union(info->avail_out, dom_info->avail_out);
 148   }
 149   dump_set(info->avail_out, "Avail_out", block);
 150 }
 151
 152 /**
 153  * Get the leader of an expression. In Firm, only
 154  * Phi nodes can be leaders, all other 'leader' are
 155  * handled by the identify_remember mechanism right.
 156  */
 157 static ir_node *find_leader(ir_node *n)
 158 {
 159   ir_node *l = get_irn_link(n);
 160
 161   if (l) {
 162     assert(is_Phi(l));
 163     return l;
 164   }
 165   return n;
 166 }  /* find_leader */
 167
 168 /**
 169  * Returns the Phi-leader if one exists, else NULL.
 170  */
 171 static ir_node *has_leader(ir_node *n)
 172 {
 173   ir_node *l = get_irn_link(n);
 174
 175   if (l) {
 176     assert(is_Phi(l));
 177     return l;
 178   }
 179   return NULL;
 180 }  /* has_leader */
 181
 182 /**
 183  * Implements phi_translate
 184  */
 185 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
 186 {
 187   ir_node *pred_block;
 188   ir_node *res;
 189   int i, arity = get_irn_intra_arity(node);
 190   struct obstack *old;
 191
 192   if (is_Phi(node)) {
 193     if (get_nodes_block(node) == block)
 194       return get_Phi_pred(node, pos);
 195     return node;
 196   }
 197
 198   /* check if the node has at least one Phi predecessor */
 199   for (i = 0; i < arity; ++i) {
 200     ir_node *pred   = get_irn_intra_n(node, i);
 201     ir_node *leader = find_leader(pred);
 202     if (is_Phi(leader) && get_nodes_block(leader) == block)
 203       break;
 204   }
 205   if (i >= arity) {
 206     /* no Phi in the predecessors */
 207     return node;
 208   }
 209
 210   pred_block = get_Block_cfgpred_block(block, pos);
 211
 212   /* Create a copy of the node in the pos'th predecessor block.
 213      Use our environmental obstack, as these nodes are always
 214      temporary. */
 215   old = current_ir_graph->obst;
 216   current_ir_graph->obst = env->obst;
 217   res   = new_ir_node(
 218             get_irn_dbg_info(node),
 219             current_ir_graph,
 220             pred_block,
 221             get_irn_op(node),
 222             get_irn_mode(node),
 223             arity,
 224             get_irn_in(node));
 225   /* We need the attribute copy here, because the Hash value of a
 226      node might depend on that. */
 227   copy_node_attr(node, res);
 228   current_ir_graph->obst = old;
 229
 230   set_irn_n(res, -1, get_irn_intra_n(node, -1));
 231   for (i = 0; i < arity; ++i) {
 232     ir_node *pred = get_irn_intra_n(node, i);
 233     ir_node *leader = find_leader(pred);
 234
 235     if (is_Phi(leader) && get_nodes_block(leader) == block)
 236       set_irn_n(res, i, get_Phi_pred(leader, pos));
 237     else
 238       set_irn_n(res, i, leader);
 239   }
 240   set_irn_link(res, NULL);
 241
 242   if (is_op_commutative(get_irn_op(res))) {
 243     ir_node *l = get_binop_left(res);
 244     ir_node *r = get_binop_right(res);
 245
 246     /* for commutative operators perform  a OP b == b OP a */
 247     if (l > r) {
 248       set_binop_left(res, r);
 249       set_binop_right(res, l);
 250     }
 251   }
 252
 253   return res;
 254 }  /* phi_translate */
 255
 256 /**
 257  * computes Antic_in(block):
 258  */
 259 static void compute_antic(ir_node *block, void *ctx)
 260 {
 261   pre_env *env = ctx;
 262   block_info *succ_info;
 263   block_info *info = get_block_info(block);
 264   ir_node *succ;
 265   int size;
 266
 267   /* no need for computations in start block */
 268   if (block == env->start_block)
 269     return;
 270
 271   size = pset_count(info->antic_in);
 272
 273   /* the root has no dominator */
 274   if (block != env->end_block) {
 275     int n_succ = get_Block_n_cfg_outs(block);
 276
 277     if (n_succ == 1) {
 278       ir_node *node;
 279       int i, pos = -1;
 280       pset *nodes = new_pset(identities_cmp, 8);
 281
 282       pset_union(nodes, info->nodes);
 283
 284       /* find blocks position in succ's block predecessors */
 285       succ = get_Block_cfg_out(block, 0);
 286       for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
 287         if (get_Block_cfgpred_block(succ, i) == block) {
 288           pos = i;
 289           break;
 290         }
 291       }
 292       assert(pos >= 0);
 293
 294       succ_info = get_block_info(succ);
 295       for (node = pset_first(succ_info->antic_in);
 296            node;
 297            node = pset_next(succ_info->antic_in)) {
 298         ir_node *trans = phi_translate(node, succ, pos, env);
 299
 300         identify_remember(nodes, trans);
 301
 302         /* add all predecessors of node */
 303         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 304           ir_node *pred = get_irn_n(node, i);
 305           ir_node *trans = phi_translate(pred, succ, pos, env);
 306
 307           if (is_nice_value(trans))
 308             identify_remember(nodes, trans);
 309         }
 310       }
 311      /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
 312      pset_union(info->antic_in, nodes);
 313      del_pset(nodes);
 314    }
 315     else {
 316       ir_node *n, *succ0;
 317       block_info *succ0_info;
 318       int i;
 319
 320       assert(n_succ > 1);
 321
 322       /* Select a successor to compute the disjoint of all Nodes
 323          sets, it might be useful to select the block with the
 324          smallest number of nodes.  For simplicity we choose the
 325          first one. */
 326       succ0 = get_Block_cfg_out(block, 0);
 327       succ0_info = get_block_info(succ0);
 328       for (n = pset_first(succ0_info->antic_in);
 329            n;
 330            n = pset_next(succ0_info->antic_in)) {
 331         /* we need the disjoint */
 332         for (i = 1; i < n_succ; ++i) {
 333           ir_node *succ = get_Block_cfg_out(block, i);
 334           block_info *succ_info = get_block_info(succ);
 335           if (pset_find(succ_info->antic_in, n, ir_node_hash(n)) == NULL)
 336             break;
 337         }
 338         if (i >= n_succ) {
 339           /* we found a node that is common in all Antic_in(succ(b)),
 340              put it in Antic_in(b) */
 341           identify_remember(info->antic_in, n);
 342         }
 343       }
 344       /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
 345       pset_union(info->antic_in, info->nodes);
 346     }
 347   }
 348
 349   if (size != pset_count(info->antic_in))
 350     /* the Antic_in set has changed */
 351     env->changes |= 1;
 352
 353   dump_set(info->antic_in, "Antic_in", block);
 354 }  /* compute_antic */
 355
 356 /**
 357  * allocate a block info
 358  */
 359 static void alloc_blk_info(ir_node *block, void *ctx)
 360 {
 361   int i;
 362   pre_env *env = ctx;
 363   block_info *info = obstack_alloc(env->obst, sizeof(block_info));
 364
 365   set_irn_link(block, info);
 366   info->nodes     = new_pset(identities_cmp, 8);
 367   info->antic_in  = new_pset(identities_cmp, 8);
 368   info->avail_out = new_pset(identities_cmp, 8);
 369   info->avail     = NULL;
 370   info->not_found = 0;
 371   info->new_set   = NULL;
 372   info->next      = env->list;
 373   env->list       = info->next;
 374
 375   /* fill the nodes set, we will need it later */
 376   for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
 377     ir_node *n = get_irn_out(block, i);
 378
 379     /* clear the link field here, we need it later */
 380     set_irn_link(n, NULL);
 381
 382     /* we cannot optimize pinned nodes, so do not remember them */
 383     if (is_nice_value(n))
 384       identify_remember(info->nodes, n);
 385     else if (is_Phi(n) && get_irn_mode(n) != mode_M) {
 386       /*
 387        * Phis are "temporaries" and must be handled special:
 388        * They are avail, but are not in Antic_in
 389        */
 390       identify_remember(info->avail_out, n);
 391     }
 392   }
 393 }
 394
 395 /**
 396  * Compare two nodes for equal operands.
 397  */
 398 static int operands_equal(ir_node *n1, ir_node *n2)
 399 {
 400   int i, arity = get_irn_arity(n1);
 401   assert(n1->op == n2->op && arity == get_irn_arity(n2));
 402   for (i = 0; i < arity; ++i)
 403     if (get_irn_n(n1, i) != get_irn_n(n2, i))
 404       return 0;
 405   return 1;
 406 }
 407
 408 /**
 409  * Replace a value in a set by an node computing the same
 410  * value in a dominator block.
 411  *
 412  * @return non-zero if a replacement took place
 413  */
 414 static int value_replace(pset *set, ir_node *e)
 415 {
 416   ir_node *old = identify_remember(set, e);
 417
 418   if (old != e) {
 419     /* e must dominate old here */
 420     assert(block_dominates(get_nodes_block(e), get_nodes_block(old)));
 421
 422     pset_remove(set, old, ir_node_hash(old));
 423     identify_remember(set, e);
 424     return 1;
 425   }
 426   return 0;
 427 }
 428
 429 /**
 430  * Perform insertion of partially redundant values.
 431  * For every Block node, do the following:
 432  * 1.  Propagate the NEW_SETS of the dominator into the current block.
 433  * If the block has multiple predecessors,
 434  *     2a. Iterate over the ANTIC expressions for the block to see if
 435  *         any of them are partially redundant.
 436  *     2b. If so, insert them into the necessary predecessors to make
 437  *         the expression fully redundant.
 438  *     2c. Insert a new Phi merging the values of the predecessors.
 439  *     2d. Insert the new Phi, and the new expressions, into the
 440  *         NEW_SETS set.
 441  */
 442 static void insert_nodes(ir_node *block, void *ctx)
 443 {
 444   pre_env *env = ctx;
 445   ir_node *e, *idom, *first_s;
 446   block_info *curr_info, *idom_info;
 447   int pos, arity = get_irn_intra_arity(block);
 448   int all_same, by_some, updated;
 449
 450   curr_info = get_block_info(block);
 451   curr_info->new_set = new_pset(identities_cmp, 8);
 452
 453   if (block == env->start_block)
 454     return;
 455
 456   idom = get_Block_idom(block);
 457   idom_info = get_block_info(idom);
 458
 459   /* update the new_sets */
 460   updated = 0;
 461   dump_set(idom_info->new_set, "[New Set]", idom);
 462   pset_foreach(e, idom_info->new_set) {
 463     identify_remember(curr_info->new_set, e);
 464     updated |= value_replace(curr_info->avail_out, e);
 465   }
 466   if (updated)
 467     dump_set(curr_info->avail_out, "Updated [Avail_out]", block);
 468
 469   if (arity <= 1)
 470     return;
 471
 472   pset_foreach(e, curr_info->antic_in) {
 473     /*
 474      * If we already have a leader for this node,
 475      * it is totally redundant.
 476      */
 477     if (has_leader(e))
 478       continue;
 479
 480     /* If the value was already computed in the dominator, then
 481        it is totally redundant.  Hence we have nothing to insert. */
 482     if (pset_find(idom_info->avail_out, e, ir_node_hash(e))) {
 483 //      DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
 484       continue;
 485     }
 486
 487     by_some  = 0;
 488     all_same = 1;
 489     first_s  = NULL;
 490
 491     /* for all predecessor blocks */
 492     for (pos = 0; pos < arity; ++pos) {
 493       block_info *pred_info;
 494       ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 495       ir_node *e_prime, *v_prime, *e_dprime;
 496
 497       /* ignore bad blocks. */
 498       if (is_Bad(pred_blk))
 499         continue;
 500
 501       e_prime = phi_translate(e, block, pos, env);
 502       v_prime = e_prime;
 503
 504       pred_info = get_block_info(pred_blk);
 505       e_dprime = pset_find(pred_info->avail_out, v_prime, ir_node_hash(v_prime));
 506
 507       if (e_dprime == NULL) {
 508         all_same = 0;
 509         pred_info->avail = e_prime;
 510         pred_info->not_found = 1;
 511       }
 512       else {
 513         e_dprime = find_leader(e_dprime);
 514         pred_info->avail = e_dprime;
 515         pred_info->not_found = 0;
 516         by_some = 1;
 517         if (first_s == NULL)
 518           first_s = e_dprime;
 519         else if (first_s != e_dprime)
 520           all_same = 0;
 521
 522         DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
 523       }  /* if */
 524     }  /* for */
 525
 526     /* If it's not the same value already existing along every predecessor, and
 527        it's defined by some predecessor, it is partially redundant. */
 528     if (! all_same && by_some) {
 529       ir_node *phi, **in;
 530       ir_mode *mode = NULL;
 531       DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
 532
 533       in = xmalloc(arity * sizeof(*in));
 534       /* for all predecessor blocks */
 535       for (pos = 0; pos < arity; ++pos) {
 536         ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 537         block_info *pred_info = get_block_info(pred_blk);
 538
 539         /* ignore bad blocks. */
 540         if (is_Bad(pred_blk)) {
 541           in[pos] = new_Bad();
 542           continue;
 543         }
 544
 545         /* ignore blocks that already have the expression */
 546         if (pred_info->not_found) {
 547           ir_node *e_prime = pred_info->avail;
 548           ir_node *nn;
 549           assert(! is_Phi(e_prime));
 550
 551           mode = get_irn_mode(e_prime);
 552           nn = new_ir_node(
 553             get_irn_dbg_info(e_prime),
 554             current_ir_graph, pred_blk,
 555             get_irn_op(e_prime),
 556             mode,
 557             get_irn_arity(e_prime),
 558             get_irn_in(e_prime) + 1);
 559
 560           pred_info->avail = identify_remember(pred_info->avail_out, nn);
 561         }
 562         in[pos] = pred_info->avail;
 563       }  /* for */
 564       phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
 565       free(in);
 566       identify_remember(curr_info->avail_out, phi);
 567       identify_remember(curr_info->new_set, phi);
 568       /* e might be translated, so add it here */
 569       identify_remember(curr_info->avail_out, e);
 570       identify_remember(curr_info->new_set, e);
 571       set_irn_link(e, phi);
 572       DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
 573       env->changes |= 1;
 574     }  /* if */
 575   }  /* pset_foreach */
 576 }  /* insert_nodes */
 577
 578 /**
 579  * Do the elimination step
 580  */
 581 static void eliminate_nodes(ir_node *block, void *ctx)
 582 {
 583   block_info *curr_info = get_block_info(block);
 584   ir_node *v;
 585
 586   pset_foreach(v, curr_info->nodes) {
 587     ir_node *l = identify_remember(curr_info->avail_out, v);
 588
 589     l = find_leader(l);
 590     if (l != v) {
 591       DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", v, l));
 592       exchange(v, l);
 593     }
 594   }
 595 }
 596
 597 void do_gvn_pre(ir_graph *irg)
 598 {
 599   struct obstack obst;
 600   pre_env a_env;
 601   optimization_state_t state;
 602   block_info *p;
 603   int iter = 0;
 604
 605   /* register a debug mask */
 606   dbg = firm_dbg_register("firm.opt.gvn_pre");
 607   firm_dbg_set_mask(dbg, SET_LEVEL_2);
 608
 609   obstack_init(&obst);
 610   a_env.obst        = &obst;
 611   a_env.list        = NULL;
 612   a_env.start_block = get_irg_start_block(irg);
 613   a_env.end_block   = get_irg_end_block(irg);
 614
 615   /* Move Proj's into the same block as their args,
 616      else we would assign the result to wrong blocks */
 617   normalize_proj_nodes(irg);
 618
 619   /* critical edges MUST be removed */
 620   remove_critical_cf_edges(irg);
 621
 622   /* we need dominator AND post dominator information */
 623   if (get_irg_dom_state(irg) != dom_consistent)
 624     compute_doms(irg);
 625   if (get_irg_postdom_state(irg) != dom_consistent)
 626     compute_postdoms(irg);
 627   if (get_irg_outs_state(irg) != outs_consistent)
 628     compute_irg_outs(irg);
 629
 630   /*
 631    * Switch on GCSE. We need it to correctly compute
 632    * the leader of a node by hashing.
 633    */
 634   save_optimization_state(&state);
 635   set_opt_global_cse(1);
 636
 637   /* allocate block info for all blocks */
 638   irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
 639
 640   /* compute the available value sets for all blocks */
 641   dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
 642
 643   /* compute the anticipated value sets for all blocks */
 644   do {
 645     DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++iter));
 646     a_env.changes = 0;
 647     irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
 648 //    postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
 649     DB((dbg, LEVEL_1, "------------------------\n"));
 650   } while (a_env.changes != 0);
 651
 652   /* compute redundant expressions */
 653   iter = 0;
 654   do {
 655     DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++iter));
 656     a_env.changes = 0;
 657     dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
 658     DB((dbg, LEVEL_1, "------------------------\n"));
 659   } while (a_env.changes != 0);
 660
 661   /* last step: eliminate nodes */
 662   dom_tree_walk_irg(irg, eliminate_nodes, NULL, &a_env);
 663
 664   restore_optimization_state(&state);
 665
 666   /* clean up: delete all sets */
 667   for (p = a_env.list; p != NULL; p = p->next) {
 668     if (p->antic_in)
 669       del_pset(p->antic_in);
 670     if (p->avail_out)
 671       del_pset(p->avail_out);
 672     if (p->nodes)
 673       del_pset(p->nodes);
 674   }
 675   obstack_free(&obst, NULL);
 676 }  /* do_gvn_pre */