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

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