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

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