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

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