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