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