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