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