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 "set.h"
  25 #include "irgopt.h"
  26 #include "iropt_t.h"
  27 #include "irprintf.h"
  28 #include "irnode_t.h"
  29 #include "ircons.h"
  30 #include "irgmod.h"
  31 #include "debug.h"
  32 #include "gvn_pre.h"
  33 #include "xmalloc.h"
  34
  35 /** The debug module handle. */
  36 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  37
  38
  39 /** A value set. */
  40 typedef struct set value_set;
  41
  42 /** A node set. */
  43 typedef struct pset node_set;
  44
  45 /** An entry in the value set. */
  46 typedef struct value_entry {
  47   ir_node *node;  /**< the node */
  48   ir_node *value; /**< the value of the node */
  49 } value_entry;
  50
  51 /** Additional info we need for every block. */
  52 typedef struct block_info {
  53   node_set *nodes;      /**< The set of nodes per block. */
  54   value_set *avail_out; /**< The Avail_out set for a block. */
  55   node_set *antic_in;   /**< The Antic_in set for a block. */
  56   value_set *new_set;   /**< The set of all new values for a block. */
  57   ir_node *avail;       /**< The get_map(avail, block) result. */
  58   int not_found;        /**< Non-zero, if avail was not found in this block. */
  59   struct block_info *next;  /**< Links all entries, so we can recover the sets easily. */
  60 } block_info;
  61
  62 /**
  63  * A pair of nodes that must be exchanged.
  64  * We must defer the exchange because our hash-sets cannot
  65  * find an already replace node else.
  66  */
  67 typedef struct elim_pair {
  68   ir_node *old_node;      /**< The old node that will be replaced. */
  69   ir_node *new_node;      /**< The new node. */
  70   struct elim_pair *next; /**< Links all entries in a list. */
  71 } elim_pair;
  72
  73 /** The environment for the GVN-PRE algorithm */
  74 typedef struct pre_env {
  75   struct obstack *obst;   /**< The obstack to allocate on. */
  76   node_set *trans_set;    /**< The set of all translated values. */
  77   ir_node *start_block;   /**< The start block of the current graph. */
  78   ir_node *end_block;     /**< The end block of the current graph */
  79   block_info *list;       /**< Links all block info entires for easier recovery. */
  80   elim_pair *pairs;       /**< A list of node pairs that must be eliminated. */
  81   char changes;           /**< Non-zero, if calculation of Antic_in has changed. */
  82   char first_iter;        /**< non-zero for first iteration */
  83 } pre_env;
  84
  85 /* ----------  Functions for Node sets ---------- */
  86
  87 #define node_set_first(s)       pset_first(s)
  88 #define node_set_next(s)        pset_next(s)
  89 #define node_set_break(s)       pset_break(s)
  90 #define node_set_foreach(v, s)  for ((v) = node_set_first(s); (v); (v) = node_set_next(s))
  91
  92 /**
  93  * Creates a new node set.
  94  */
  95 static node_set *new_node_set(void) {
  96   return new_pset(identities_cmp, 8);
  97 }
  98
  99 /**
 100  * Deletes a node set.
 101  */
 102 static void del_node_set(node_set *set) {
 103   del_pset(set);
 104 }
 105
 106 /**
 107  * Add a node to the set.
 108  */
 109 static ir_node *node_add(node_set *set, ir_node *node) {
 110   return identify_remember(set, node);
 111 }
 112
 113 /**
 114  * Remove a node from a node set.
 115  */
 116 static void node_set_remove(node_set *set, ir_node *node) {
 117   pset_remove(set, node, ir_node_hash(node));
 118 }
 119
 120 /**
 121  * Return the number of entries in a node set.
 122  */
 123 static int node_set_count(node_set *set) {
 124   return pset_count(set);
 125 }
 126
 127 #if 0
 128 /** computes dst = dst \/ src for node sets */
 129 static void node_union(node_set *dst, node_set *src)
 130 {
 131   ir_node *entry;
 132   node_set_foreach(entry, src) {
 133     node_add(dst, entry);
 134   }
 135 }
 136 #endif
 137
 138 /**
 139  * Lookup a node in a node set.
 140  */
 141 static ir_node *node_lookup(node_set *set, ir_node *n)
 142 {
 143   return pset_find(set, n, ir_node_hash(n));
 144 }
 145
 146
 147 /* ----------  Functions for Value sets ---------- */
 148
 149 #define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
 150
 151 /**
 152  * calculate a hash value for a value represented by a node
 153  */
 154 static unsigned value_hash(ir_node *value) {
 155   return ir_node_hash(value);
 156 }
 157
 158 /**
 159  * Compare two value entries.
 160  */
 161 static int value_cmp(const void *elt, const void *key, size_t size)
 162 {
 163   const value_entry *e1 = elt;
 164   const value_entry *e2 = key;
 165
 166   return identities_cmp(e1->value, e2->value);
 167 }
 168
 169 /** Create a new value set. */
 170 static value_set *new_value_set(void) {
 171   return new_set(value_cmp, 8);
 172 }
 173
 174 /** Deletes a value set. */
 175 static void del_value_set(value_set *set) {
 176   del_set(set);
 177 }
 178
 179 /**
 180  * Add a node node representing the value value to the set.
 181  */
 182 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
 183 {
 184   value_entry key;
 185   key.node  = node;
 186   key.value = value;
 187   return set_insert(set, &key, sizeof(key), value_hash(value));
 188 }
 189
 190 /** computes dst = dst \/ src for value sets */
 191 static void value_union(value_set *dst, value_set *src)
 192 {
 193   value_entry *entry;
 194   value_set_foreach(entry, src)
 195     value_add(dst, entry->node, entry->value);
 196 }
 197
 198 /** computes dst = dst \/ (value_set)src for value sets */
 199 static void value_union_nodes(value_set *dst, node_set *src)
 200 {
 201   ir_node *n;
 202   node_set_foreach(n, src)
 203     value_add(dst, n, n);
 204 }
 205
 206 /**
 207  * Lookup a value in a value set.
 208  */
 209 static ir_node *value_lookup(value_set *value_set, ir_node *n)
 210 {
 211   value_entry key, *e;
 212
 213   key.value = n;
 214   e = set_find(value_set, &key, sizeof(key), value_hash(n));
 215   return e ? e->node : NULL;
 216 }
 217
 218 /**
 219  * Add or replace a value in a set by an node computing the same
 220  * value in a dominator block.
 221  *
 222  * @return non-zero if a replacement took place
 223  */
 224 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
 225 {
 226   value_entry *e = value_add(set, node, value);
 227
 228   if (e->node != node) {
 229     /* node must dominate old one here */
 230     assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
 231
 232     e->node = node;
 233     return 1;
 234   }
 235   return 0;
 236 }
 237
 238 /**
 239  * Returns non-zero if a node is movable.
 240  */
 241 static int is_nice_value(ir_node *n) {
 242   ir_mode *mode;
 243
 244   while (is_Proj(n))
 245     n = get_Proj_pred(n);
 246   mode = get_irn_mode(n);
 247   /*
 248    * FIXME: For now, we cannot handle Div/even if it's movable.
 249    * That should be fixed.
 250    */
 251   if (!mode_is_data(mode))
 252     return 0;
 253   if (is_irn_constlike(n))
 254     return 0;
 255   return (get_irn_pinned(n) != op_pin_state_pinned);
 256 }
 257
 258 #ifdef DEBUG_libfirm
 259 /**
 260  * Dump a set.
 261  */
 262 static void dump_node_set(node_set *set, char *txt, ir_node *block)
 263 {
 264   ir_node *n;
 265   int i;
 266
 267   DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
 268   i = 0;
 269   node_set_foreach(n, set) {
 270     if ((i & 3) == 3)
 271       DB((dbg, LEVEL_2, "\n"));
 272     DB((dbg, LEVEL_2, " %+F,", n));
 273     ++i;
 274   }
 275   DB((dbg, LEVEL_2, "\n}\n"));
 276 }  /* dump_set */
 277
 278 /**
 279  * Dump a value set.
 280  */
 281 static void dump_value_set(value_set *set, char *txt, ir_node *block)
 282 {
 283   value_entry *e;
 284   int i;
 285
 286   DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
 287   i = 0;
 288   value_set_foreach(e, set) {
 289     if ((i & 3) == 3)
 290       DB((dbg, LEVEL_2, "\n"));
 291     if (e->node != e->value)
 292       DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
 293     else
 294       DB((dbg, LEVEL_2, " %+F,", e->node));
 295     ++i;
 296   }
 297   DB((dbg, LEVEL_2, "\n}\n"));
 298 }  /* dump_set */
 299
 300 #else
 301 #define dump_node_set(set, txt, block)
 302 #define dump_value_set(set, txt, block)
 303 #endif /* DEBUG_libfirm */
 304
 305
 306 /**
 307  * Return the block info of a block
 308  */
 309 static block_info *get_block_info(ir_node *block) {
 310   return get_irn_link(block);
 311 }
 312
 313 /**
 314  * Computes Avail_out(block):
 315  *
 316  * Avail_in(block)  = Avail_out(dom(block))
 317  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
 318  *
 319  * Precondition:
 320  *  This function must be called in the top-down dominance order:
 321  *  Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
 322  */
 323 static void compute_avail_top_down(ir_node *block, void *ctx)
 324 {
 325   pre_env *env = ctx;
 326   block_info *dom_info;
 327   block_info *info = get_block_info(block);
 328   ir_node *dom_blk;
 329
 330   /* we don't need the end block Avail */
 331   if (block == env->end_block)
 332     return;
 333
 334   /*
 335    * First add all nodes from the dominator.
 336    * This must be done to ensure that Antic_out contains the leader
 337    * for every node. The root has no dominator.
 338    */
 339   if (block != env->start_block) {
 340     dom_blk = get_Block_idom(block);
 341     assert(is_Block(dom_blk));
 342
 343     dom_info = get_block_info(dom_blk);
 344     assert(dom_info);
 345
 346     value_union(info->avail_out, dom_info->avail_out);
 347   }
 348   value_union_nodes(info->avail_out, info->nodes);
 349
 350   dump_value_set(info->avail_out, "Avail_out", block);
 351 }
 352
 353 /**
 354  * returns non-zero if a tree node must be copied because of
 355  * a phi_translate.
 356  */
 357 static int need_copy(ir_node *node, ir_node *block)
 358 {
 359   int i, arity;
 360
 361   /* Phi always stop the recursion */
 362   if (is_Phi(node))
 363     return get_irn_intra_n(node, -1) == block;
 364
 365   if (! is_nice_value(node))
 366     return 0;
 367
 368   /* check predecessor */
 369   arity = get_irn_intra_arity(node);
 370   for (i = 0; i < arity; ++i) {
 371     ir_node *pred     = get_irn_intra_n(node, i);
 372     ir_node *local_bl = get_irn_intra_n(pred, -1);
 373     ir_node *leader   = value_lookup(get_block_info(local_bl)->avail_out, pred);
 374
 375     pred = leader != NULL ? leader : pred;
 376     if (need_copy(pred, block))
 377       return 1;
 378   }
 379   return 0;
 380 }
 381
 382 /**
 383  * Translate a node
 384  */
 385 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
 386 {
 387   int i, arity, need_new;
 388   ir_node *res, *nn, **in;
 389
 390   /* Phi always stop the recursion */
 391   if (is_Phi(node)) {
 392     if (get_irn_intra_n(node, -1) == block)
 393       return get_Phi_pred(node, pos);
 394     return node;
 395   }
 396
 397   if (! is_nice_value(node))
 398     return node;
 399
 400   arity = get_irn_intra_arity(node);
 401   if (arity > 0) {
 402     NEW_ARR_A(ir_node *, in, arity);
 403     i = arity - 1;
 404     need_new = 0;
 405     do {
 406       ir_node *pred = get_irn_intra_n(node, i);
 407       ir_node *pred_blk = get_irn_intra_n(pred, -1);
 408       ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
 409       in[i] = translate(leader ? leader : pred, block, pos, env);
 410       need_new |= (in[i] != pred);
 411       --i;
 412     } while(i >= 0);
 413     if (! need_new)
 414       return node;
 415
 416     /* create a copy */
 417     nn = new_ir_node(
 418           get_irn_dbg_info(node),
 419           current_ir_graph,
 420           get_Block_cfgpred_block(block, pos),
 421           get_irn_op(node),
 422           get_irn_mode(node),
 423           arity,
 424           in);
 425     /* We need the attribute copy here, because the Hash value of a
 426        node might depend on that. */
 427     copy_node_attr(node, nn);
 428     res = node_add(env->trans_set, nn);
 429     if (nn != res)
 430       obstack_free(env->obst, nn);
 431     else
 432       DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
 433     return res;
 434   }
 435   return node;
 436 }
 437
 438 #if 0
 439 /**
 440  * Implements phi_translate.
 441  */
 442 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
 443 {
 444   struct obstack *old;
 445   ir_node *res;
 446
 447   if (! need_copy(node, block))
 448     return node;
 449
 450   /* Create a copy of the node in the pos'th predecessor block.
 451      Use our environmental obstack, as these nodes are always
 452      temporary. */
 453   old = current_ir_graph->obst;
 454   current_ir_graph->obst = env->obst;
 455   res = translate(node, block, pos, env);
 456   current_ir_graph->obst = old;
 457
 458   return res;
 459 }  /* phi_translate */
 460 #endif
 461
 462 /**
 463  * Implements phi_translate.
 464  */
 465 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
 466 {
 467   ir_node *nn, *res;
 468   int i, arity;
 469   struct obstack *old;
 470
 471   if (is_Phi(node)) {
 472     if (get_irn_intra_n(node, -1) == block)
 473       return get_Phi_pred(node, pos);
 474     return node;
 475   }
 476
 477   arity = get_irn_intra_arity(node);
 478
 479   /* check if the node has at least one Phi predecessor */
 480   for (i = 0; i < arity; ++i) {
 481     ir_node *pred    = get_irn_intra_n(node, i);
 482     ir_node *pred_bl = get_irn_intra_n(pred, -1);
 483     ir_node *leader  = value_lookup(get_block_info(pred_bl)->avail_out, pred);
 484
 485     leader = leader != NULL ? leader : pred;
 486     if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
 487       break;
 488   }
 489   if (i >= arity) {
 490     /* no Phi in the predecessors */
 491     return node;
 492   }
 493
 494   /* Create a copy of the node in the pos'th predecessor block.
 495      Use our environmental obstack, as these nodes are always
 496      temporary. */
 497   old = current_ir_graph->obst;
 498   current_ir_graph->obst = env->obst;
 499   nn = new_ir_node(
 500           get_irn_dbg_info(node),
 501           current_ir_graph,
 502           NULL,
 503           get_irn_op(node),
 504           get_irn_mode(node),
 505           arity,
 506           get_irn_in(node));
 507   /* We need the attribute copy here, because the Hash value of a
 508      node might depend on that. */
 509   copy_node_attr(node, nn);
 510
 511   set_irn_n(nn, -1, get_irn_intra_n(node, -1));
 512   for (i = 0; i < arity; ++i) {
 513     ir_node *pred    = get_irn_intra_n(node, i);
 514     ir_node *pred_bl = get_irn_intra_n(pred, -1);
 515     ir_node *leader  = value_lookup(get_block_info(pred_bl)->avail_out, pred);
 516
 517     leader = leader != NULL ? leader : pred;
 518     if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
 519       set_irn_n(nn, i, get_Phi_pred(leader, pos));
 520     else
 521       set_irn_n(nn, i, leader);
 522   }
 523   res = node_add(env->trans_set, nn);
 524   current_ir_graph->obst = old;
 525
 526   if (nn != res)
 527     obstack_free(env->obst, nn);
 528   else {
 529     DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
 530   }
 531   return res;
 532 }  /* phi_translate */
 533
 534 /**
 535  * check if a node n is clean in block block.
 536  */
 537 static int _is_clean(ir_node *n, ir_node *block)
 538 {
 539   int i;
 540
 541   if (get_nodes_block(n) != block)
 542     return 1;
 543   if (is_Phi(n))
 544     return 1;
 545
 546   if (irn_visited(n))
 547     return 0;
 548
 549   if (! is_nice_value(n))
 550     goto bad;
 551   for (i = get_irn_arity(n) - 1; i >= 0; --i) {
 552     ir_node *pred = get_irn_n(n, i);
 553     if (! _is_clean(pred, block))
 554       goto bad;
 555   }
 556   return 1;
 557 bad:
 558   mark_irn_visited(n);
 559   return 0;
 560 }
 561
 562 /**
 563  * check if a node n is clean.
 564  */
 565 static int is_clean(ir_node *n)
 566 {
 567   int res = _is_clean(n, get_nodes_block(n));
 568   return res;
 569 }
 570
 571 /**
 572  * Clean a node set.
 573  * This function is called for node sets with is_clean
 574  * nodes only, so we must just remove nodes that don't
 575  * have available inputs
 576  */
 577 static void clean_node_set(node_set *set, ir_node *blk)
 578 {
 579   ir_node *n, *pred, *pred_blk;
 580   int i;
 581
 582 restart:
 583   for (n = node_set_first(set); n; n = node_set_next(set)) {
 584     for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
 585       pred = get_irn_intra_n(n, i);
 586
 587       pred_blk = get_irn_intra_n(pred, -1);
 588       if (block_dominates(pred_blk, blk))
 589         continue;
 590       /* pred do not dominate it, but may be in the set */
 591       if (node_lookup(set, pred) != NULL)
 592         continue;
 593       /* we found a node that must be removed */
 594       node_set_break(set);
 595       node_set_remove(set, n);
 596       DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
 597       goto restart;
 598     }
 599   }
 600 }
 601
 602 /**
 603  * computes Antic_in(block):
 604  */
 605 static void compute_antic(ir_node *block, void *ctx)
 606 {
 607   pre_env *env = ctx;
 608   block_info *succ_info;
 609   block_info *info = get_block_info(block);
 610   ir_node *succ;
 611   int size;
 612
 613   /* no need for computations in start block */
 614   if (block == env->start_block)
 615     return;
 616
 617   size = node_set_count(info->antic_in);
 618
 619   /* the end block has no successor */
 620   if (block != env->end_block) {
 621     int n_succ = get_Block_n_cfg_outs(block);
 622
 623     if (n_succ == 1) {
 624       ir_node *node, *list;
 625       int i, pos = -1;
 626
 627       /* find blocks position in succ's block predecessors */
 628       succ = get_Block_cfg_out(block, 0);
 629       for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
 630         if (get_Block_cfgpred_block(succ, i) == block) {
 631           pos = i;
 632           break;
 633         }
 634       }
 635       assert(pos >= 0);
 636
 637       succ_info = get_block_info(succ);
 638       /* translate into list: we cannot insert into a set we iterate
 639        * and succ might be equal to block for endless loops */
 640       list = NULL;
 641       node_set_foreach(node, succ_info->antic_in) {
 642         set_irn_link(node, list);
 643         list = node;
 644       }
 645       for (node = list; node; node = get_irn_link(node)) {
 646         ir_node *trans = phi_translate(node, succ, pos, env);
 647
 648         if (is_clean(trans))
 649           node_add(info->antic_in, trans);
 650       }
 651     }
 652     else {
 653       ir_node *n, *succ0;
 654       block_info *succ0_info;
 655       int i;
 656
 657       assert(n_succ > 1);
 658
 659       /* Select a successor to compute the disjoint of all Nodes
 660          sets, it might be useful to select the block with the
 661          smallest number of nodes.  For simplicity we choose the
 662          first one. */
 663       succ0 = get_Block_cfg_out(block, 0);
 664       succ0_info = get_block_info(succ0);
 665       node_set_foreach(n, succ0_info->antic_in) {
 666         /* we need the disjoint */
 667         for (i = 1; i < n_succ; ++i) {
 668           ir_node *succ = get_Block_cfg_out(block, i);
 669           block_info *succ_info = get_block_info(succ);
 670           if (node_lookup(succ_info->antic_in, n) == NULL)
 671             break;
 672         }
 673         if (i >= n_succ) {
 674           /* we found a node that is common in all Antic_in(succ(b)),
 675              put it in Antic_in(b) */
 676           node_add(info->antic_in, n);
 677         }
 678       }
 679     }
 680
 681     /*
 682      * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
 683      * It is enough to do this in the first iteration, because
 684      * the set info->nodes is not changed anymore.
 685      */
 686     if (env->first_iter) {
 687       ir_node *n;
 688       node_set_foreach(n, info->nodes) {
 689         if (is_clean(n))
 690           node_add(info->antic_in, n);
 691       }
 692     }
 693   }
 694
 695 //  clean_node_set(info->antic_in, block);
 696   (void) clean_node_set;
 697
 698   dump_node_set(info->antic_in, "Antic_in", block);
 699   if (size != node_set_count(info->antic_in)) {
 700     /* the Antic_in set has changed */
 701     env->changes |= 1;
 702   }
 703 }  /* compute_antic */
 704
 705 /**
 706  * allocate a block info
 707  */
 708 static void alloc_blk_info(ir_node *block, void *ctx)
 709 {
 710   int i;
 711   pre_env *env = ctx;
 712   block_info *info = obstack_alloc(env->obst, sizeof(*info));
 713
 714   set_irn_link(block, info);
 715   info->nodes     = new_node_set();
 716   info->antic_in  = new_node_set();
 717   info->avail_out = new_value_set();
 718   info->avail     = NULL;
 719   info->not_found = 0;
 720   info->new_set   = NULL;
 721   info->next      = env->list;
 722   env->list       = info;
 723
 724   /* fill the nodes set, we will need it later */
 725   for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
 726     ir_node *n = get_irn_out(block, i);
 727
 728     set_irn_link(n, NULL);
 729
 730     /* we cannot optimize pinned nodes, so do not remember them */
 731     if (is_nice_value(n))
 732       node_add(info->nodes, n);
 733   }
 734 }
 735
 736 /**
 737  * Perform insertion of partially redundant values.
 738  * For every Block node, do the following:
 739  * 1.  Propagate the NEW_SETS of the dominator into the current block.
 740  * If the block has multiple predecessors,
 741  *     2a. Iterate over the ANTIC expressions for the block to see if
 742  *         any of them are partially redundant.
 743  *     2b. If so, insert them into the necessary predecessors to make
 744  *         the expression fully redundant.
 745  *     2c. Insert a new Phi merging the values of the predecessors.
 746  *     2d. Insert the new Phi, and the new expressions, into the
 747  *         NEW_SETS set.
 748  */
 749 static void insert_nodes(ir_node *block, void *ctx)
 750 {
 751   pre_env *env = ctx;
 752   value_entry *entry;
 753   ir_node *e, *idom, *first_s, *worklist;
 754   block_info *curr_info, *idom_info;
 755   int pos, arity = get_irn_intra_arity(block);
 756   int all_same, by_some, updated;
 757
 758   /* ensure that even the start block has a new_set */
 759   curr_info = get_block_info(block);
 760   if (curr_info->new_set)
 761     del_value_set(curr_info->new_set);
 762   curr_info->new_set = new_value_set();
 763
 764   if (block == env->start_block)
 765     return;
 766
 767   idom = get_Block_idom(block);
 768   idom_info = get_block_info(idom);
 769
 770   /* update the new_sets */
 771   updated = 0;
 772   dump_value_set(idom_info->new_set, "[New Set]", idom);
 773   value_set_foreach(entry, idom_info->new_set) {
 774     updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
 775   }
 776   if (updated)
 777     dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
 778
 779   if (arity <= 1)
 780     return;
 781
 782   /* convert the set into a list. This allows the removal of
 783    * elements from the set */
 784   worklist = NULL;
 785   node_set_foreach(e, curr_info->antic_in) {
 786     set_irn_link(e, worklist);
 787     worklist = e;
 788   }
 789
 790   for (e = worklist; e != NULL; e = get_irn_link(e)) {
 791     ir_mode *mode;
 792
 793     /* If the value was already computed in the dominator, then
 794        it is totally redundant.  Hence we have nothing to insert. */
 795     if (value_lookup(idom_info->avail_out, e)) {
 796 //      DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
 797       continue;
 798     }
 799
 800     by_some  = 0;
 801     all_same = 1;
 802     first_s  = NULL;
 803     mode     = NULL;
 804
 805     /* for all predecessor blocks */
 806     for (pos = 0; pos < arity; ++pos) {
 807       block_info *pred_info;
 808       ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 809       ir_node *e_prime, *v_prime, *e_dprime;
 810
 811       /* ignore bad blocks. */
 812       if (is_Bad(pred_blk))
 813         continue;
 814
 815       e_prime = phi_translate(e, block, pos, env);
 816       v_prime = e_prime;
 817
 818       pred_info = get_block_info(pred_blk);
 819       e_dprime = value_lookup(pred_info->avail_out, v_prime);
 820
 821       if (e_dprime == NULL) {
 822         all_same = 0;
 823         pred_info->avail = e_prime;
 824         pred_info->not_found = 1;
 825       }
 826       else {
 827         mode     = get_irn_mode(e_dprime);
 828         e_dprime = e_dprime;
 829         pred_info->avail = e_dprime;
 830         pred_info->not_found = 0;
 831         by_some = 1;
 832         if (first_s == NULL)
 833           first_s = e_dprime;
 834         else if (first_s != e_dprime)
 835           all_same = 0;
 836
 837         DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
 838       }  /* if */
 839     }  /* for */
 840
 841     /* If it's not the same value already existing along every predecessor, and
 842        it's defined by some predecessor, it is partially redundant. */
 843     if (! all_same && by_some) {
 844       ir_node *phi, **in;
 845
 846       DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
 847
 848       in = xmalloc(arity * sizeof(*in));
 849       /* for all predecessor blocks */
 850       for (pos = 0; pos < arity; ++pos) {
 851         ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 852         block_info *pred_info = get_block_info(pred_blk);
 853
 854         /* ignore bad blocks. */
 855         if (is_Bad(pred_blk)) {
 856           in[pos] = new_Bad();
 857           continue;
 858         }
 859
 860         /* ignore blocks that already have the expression */
 861         if (pred_info->not_found) {
 862           ir_node *e_prime = pred_info->avail;
 863           ir_node *nn;
 864           if (!is_Phi(e_prime)) {
 865             mode = get_irn_mode(e_prime);
 866             nn = new_ir_node(
 867               get_irn_dbg_info(e_prime),
 868               current_ir_graph, pred_blk,
 869               get_irn_op(e_prime),
 870               mode,
 871               get_irn_arity(e_prime),
 872               get_irn_in(e_prime) + 1);
 873             copy_node_attr(e_prime, nn);
 874
 875             DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
 876             pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
 877           }
 878         }
 879         in[pos] = pred_info->avail;
 880       }  /* for */
 881       phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
 882       free(in);
 883       value_add_or_replace(curr_info->avail_out, phi, e);
 884       value_add(curr_info->new_set, phi, e);
 885       DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
 886
 887       /* the good case: we really replace an instruction */
 888       node_set_remove(curr_info->antic_in, e);
 889
 890       env->changes |= 1;
 891     }  /* if */
 892   }  /* node_set_foreach */
 893 }  /* insert_nodes */
 894
 895 /**
 896  * Do the elimination step: collect all changes
 897  * We cannot do the changes right here, as this would change
 898  * the hash values of the nodes in the avail_out set!
 899  */
 900 static void collect_elim_pairs(ir_node *block, void *ctx)
 901 {
 902   pre_env *env = ctx;
 903   block_info *curr_info = get_block_info(block);
 904   ir_node *v;
 905
 906   dump_node_set(curr_info->nodes, "Updating nodes", block);
 907   node_set_foreach(v, curr_info->nodes) {
 908     ir_node *l = value_lookup(curr_info->avail_out, v);
 909
 910     assert(l);
 911     if (l != v) {
 912       elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
 913
 914       p->old_node = v;
 915       p->new_node = l;
 916       p->next     = env->pairs;
 917       env->pairs  = p;
 918     }
 919   }
 920 }
 921
 922 /**
 923  * Do all the recorded changes and optimize
 924  * newly created Phi's.
 925  */
 926 static void eliminate_nodes(elim_pair *pairs)
 927 {
 928   elim_pair *p;
 929
 930   for (p = pairs; p != NULL; p = p->next) {
 931     DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
 932     /*
 933      * PRE tends to create Phi(self, self, ... , x, self, self, ...)
 934      * which we can optimize here
 935      */
 936     if (is_Phi(p->new_node)) {
 937       int i;
 938       ir_node *res = NULL;
 939
 940       for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
 941         ir_node *pred = get_irn_n(p->new_node, i);
 942
 943         if (pred != p->old_node) {
 944           if (res) {
 945             res = NULL;
 946             break;
 947           }
 948           res = pred;
 949         }
 950       }
 951       if (res)
 952         p->new_node = res;
 953     }
 954     exchange(p->old_node, p->new_node);
 955   }
 956 }
 957
 958 /*
 959  * Argh: Endless loops cause problems, because the
 960  * insert algorithm did not terminate. We get tranalated nodes that
 961  * references the origin. These nodes are translated again and again...
 962  *
 963  * The current fix is to use post-dominance. This simple ignores
 964  * endless loops, ie we cannot optimize them.
 965  */
 966 void do_gvn_pre(ir_graph *irg)
 967 {
 968   struct obstack obst;
 969   pre_env a_env;
 970   optimization_state_t state;
 971   block_info *p;
 972   unsigned antic_iter, insert_iter;
 973
 974   /* register a debug mask */
 975   FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
 976   firm_dbg_set_mask(dbg, SET_LEVEL_2);
 977
 978   obstack_init(&obst);
 979   a_env.obst        = &obst;
 980   a_env.trans_set   = new_node_set();
 981   a_env.list        = NULL;
 982   a_env.start_block = get_irg_start_block(irg);
 983   a_env.end_block   = get_irg_end_block(irg);
 984   a_env.pairs       = NULL;
 985
 986   /* Move Proj's into the same block as their args,
 987      else we would assign the result to wrong blocks */
 988   normalize_proj_nodes(irg);
 989
 990   /* critical edges MUST be removed */
 991   remove_critical_cf_edges(irg);
 992
 993   /* we need dominator for Antic_out calculation */
 994   if (get_irg_dom_state(irg) != dom_consistent)
 995     compute_doms(irg);
 996   if (get_irg_postdom_state(irg) != dom_consistent)
 997     compute_postdoms(irg);
 998   /* we get all nodes of a block by following outs */
 999   if (get_irg_outs_state(irg) != outs_consistent)
1000     compute_irg_outs(irg);
1001
1002   /*
1003    * Switch on GCSE. We need it to correctly compute
1004    * the leader of a node by hashing.
1005    */
1006   save_optimization_state(&state);
1007   set_opt_global_cse(1);
1008
1009   DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1010   printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1011
1012   /* allocate block info for all blocks */
1013   irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1014
1015   /* compute the available value sets for all blocks */
1016   dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1017
1018   /* compute the anticipated value sets for all blocks */
1019   inc_irg_visited(irg);
1020   antic_iter = 0;
1021   a_env.first_iter = 1;
1022   do {
1023     DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1024     a_env.changes = 0;
1025     irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1026 //    postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1027     a_env.first_iter = 0;
1028     DB((dbg, LEVEL_1, "------------------------\n"));
1029   } while (a_env.changes != 0);
1030
1031   /* compute redundant expressions */
1032   insert_iter = 0;
1033   do {
1034     DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1035     a_env.changes = 0;
1036     dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1037     DB((dbg, LEVEL_1, "------------------------\n"));
1038   } while (a_env.changes != 0);
1039
1040   /* last step: eliminate nodes */
1041   dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1042   eliminate_nodes(a_env.pairs);
1043
1044   restore_optimization_state(&state);
1045
1046   /* clean up: delete all sets */
1047   for (p = a_env.list; p != NULL; p = p->next) {
1048     if (p->antic_in)
1049       del_node_set(p->antic_in);
1050     if (p->avail_out)
1051       del_value_set(p->avail_out);
1052     if (p->nodes)
1053       del_node_set(p->nodes);
1054     if (p->new_set)
1055       del_value_set(p->new_set);
1056   }
1057   del_node_set(a_env.trans_set);
1058   obstack_free(&obst, NULL);
1059   set_irg_pinned(irg, op_pin_state_pinned);
1060
1061   if (a_env.pairs) {
1062     set_irg_outs_inconsistent(irg);
1063     set_irg_loopinfo_inconsistent(irg);
1064   }
1065 }  /* do_gvn_pre */