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