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   block_info *pred_info = get_block_info(pred_block);
 473
 474   if (is_Phi(node)) {
 475     if (get_irn_intra_n(node, -1) == block)
 476       return get_Phi_pred(node, pos);
 477     return node;
 478   }
 479
 480   arity = get_irn_intra_arity(node);
 481
 482   /* check if the node has at least one Phi predecessor */
 483   for (i = 0; i < arity; ++i) {
 484     ir_node *pred    = get_irn_intra_n(node, i);
 485     ir_node *pred_bl = get_irn_intra_n(pred, -1);
 486     ir_node *leader  = value_lookup(get_block_info(pred_bl)->avail_out, pred);
 487
 488     leader = leader != NULL ? leader : pred;
 489     if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
 490       break;
 491   }
 492   if (i >= arity) {
 493     /* no Phi in the predecessors */
 494     return node;
 495   }
 496
 497   /* Create a copy of the node in the pos'th predecessor block.
 498      Use our environmental obstack, as these nodes are always
 499      temporary. */
 500   old = current_ir_graph->obst;
 501   current_ir_graph->obst = env->obst;
 502   nn = new_ir_node(
 503           get_irn_dbg_info(node),
 504           current_ir_graph,
 505           NULL,
 506           get_irn_op(node),
 507           get_irn_mode(node),
 508           arity,
 509           get_irn_in(node));
 510   /* We need the attribute copy here, because the Hash value of a
 511      node might depend on that. */
 512   copy_node_attr(node, nn);
 513
 514   set_irn_n(nn, -1, get_irn_intra_n(node, -1));
 515   for (i = 0; i < arity; ++i) {
 516     ir_node *pred    = get_irn_intra_n(node, i);
 517     ir_node *pred_bl = get_irn_intra_n(pred, -1);
 518     ir_node *leader  = value_lookup(get_block_info(pred_bl)->avail_out, pred);
 519
 520     leader = leader != NULL ? leader : pred;
 521     if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
 522       set_irn_n(nn, i, get_Phi_pred(leader, pos));
 523     else
 524       set_irn_n(nn, i, leader);
 525   }
 526   res = node_add(env->trans_set, nn);
 527   current_ir_graph->obst = old;
 528
 529   if (nn != res)
 530     obstack_free(env->obst, nn);
 531   else {
 532     DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
 533   }
 534   return res;
 535 }  /* phi_translate */
 536
 537 /**
 538  * check if a node n is clean in block block.
 539  */
 540 static int _is_clean(ir_node *n, ir_node *block)
 541 {
 542   int i;
 543
 544   if (get_nodes_block(n) != block)
 545     return 1;
 546   if (is_Phi(n))
 547     return 1;
 548
 549   if (irn_visited(n))
 550     return 0;
 551
 552   if (! is_nice_value(n))
 553     goto bad;
 554   for (i = get_irn_arity(n) - 1; i >= 0; --i) {
 555     ir_node *pred = get_irn_n(n, i);
 556     if (! _is_clean(pred, block))
 557       goto bad;
 558   }
 559   return 1;
 560 bad:
 561   mark_irn_visited(n);
 562   return 0;
 563 }
 564
 565 /**
 566  * check if a node n is clean.
 567  */
 568 static int is_clean(ir_node *n)
 569 {
 570   int res = _is_clean(n, get_nodes_block(n));
 571   return res;
 572 }
 573
 574 /**
 575  * Clean a node set.
 576  * This function is called for node sets with is_clean
 577  * nodes only, so we must just remove nodes that don't
 578  * have available inputs
 579  */
 580 static void clean_node_set(node_set *set, ir_node *blk)
 581 {
 582   ir_node *n, *pred, *pred_blk;
 583   int i;
 584
 585 restart:
 586   for (n = node_set_first(set); n; n = node_set_next(set)) {
 587     for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
 588       pred = get_irn_intra_n(n, i);
 589
 590       pred_blk = get_irn_intra_n(pred, -1);
 591       if (block_dominates(pred_blk, blk))
 592         continue;
 593       /* pred do not dominate it, but may be in the set */
 594       if (node_lookup(set, pred) != NULL)
 595         continue;
 596       /* we found a node that must be removed */
 597       node_set_break(set);
 598       node_set_remove(set, n);
 599       DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
 600       goto restart;
 601     }
 602   }
 603 }
 604
 605 /**
 606  * computes Antic_in(block):
 607  */
 608 static void compute_antic(ir_node *block, void *ctx)
 609 {
 610   pre_env *env = ctx;
 611   block_info *succ_info;
 612   block_info *info = get_block_info(block);
 613   ir_node *succ;
 614   int size;
 615
 616   /* no need for computations in start block */
 617   if (block == env->start_block)
 618     return;
 619
 620   size = node_set_count(info->antic_in);
 621
 622   /* the end block has no successor */
 623   if (block != env->end_block) {
 624     int n_succ = get_Block_n_cfg_outs(block);
 625
 626     if (n_succ == 1) {
 627       ir_node *node, *list;
 628       int i, pos = -1;
 629
 630       /* find blocks position in succ's block predecessors */
 631       succ = get_Block_cfg_out(block, 0);
 632       for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
 633         if (get_Block_cfgpred_block(succ, i) == block) {
 634           pos = i;
 635           break;
 636         }
 637       }
 638       assert(pos >= 0);
 639
 640       succ_info = get_block_info(succ);
 641       /* translate into list: we cannot insert into a set we iterate
 642        * and succ might be equal to block for endless loops */
 643       list = NULL;
 644       node_set_foreach(node, succ_info->antic_in) {
 645         set_irn_link(node, list);
 646         list = node;
 647       }
 648       for (node = list; node; node = get_irn_link(node)) {
 649         ir_node *trans = phi_translate(node, succ, pos, env);
 650
 651         if (is_clean(trans))
 652           node_add(info->antic_in, trans);
 653       }
 654     }
 655     else {
 656       ir_node *n, *succ0;
 657       block_info *succ0_info;
 658       int i;
 659
 660       assert(n_succ > 1);
 661
 662       /* Select a successor to compute the disjoint of all Nodes
 663          sets, it might be useful to select the block with the
 664          smallest number of nodes.  For simplicity we choose the
 665          first one. */
 666       succ0 = get_Block_cfg_out(block, 0);
 667       succ0_info = get_block_info(succ0);
 668       node_set_foreach(n, succ0_info->antic_in) {
 669         /* we need the disjoint */
 670         for (i = 1; i < n_succ; ++i) {
 671           ir_node *succ = get_Block_cfg_out(block, i);
 672           block_info *succ_info = get_block_info(succ);
 673           if (node_lookup(succ_info->antic_in, n) == NULL)
 674             break;
 675         }
 676         if (i >= n_succ) {
 677           /* we found a node that is common in all Antic_in(succ(b)),
 678              put it in Antic_in(b) */
 679           node_add(info->antic_in, n);
 680         }
 681       }
 682     }
 683
 684     /*
 685      * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
 686      * It is enough to do this in the first iteration, because
 687      * the set info->nodes is not changed anymore.
 688      */
 689     if (env->first_iter) {
 690       ir_node *n;
 691       node_set_foreach(n, info->nodes) {
 692         if (is_clean(n))
 693           node_add(info->antic_in, n);
 694       }
 695     }
 696   }
 697
 698 //  clean_node_set(info->antic_in, block);
 699
 700   dump_node_set(info->antic_in, "Antic_in", block);
 701   if (size != node_set_count(info->antic_in)) {
 702     /* the Antic_in set has changed */
 703     env->changes |= 1;
 704   }
 705 }  /* compute_antic */
 706
 707 /**
 708  * allocate a block info
 709  */
 710 static void alloc_blk_info(ir_node *block, void *ctx)
 711 {
 712   int i;
 713   pre_env *env = ctx;
 714   block_info *info = obstack_alloc(env->obst, sizeof(*info));
 715
 716   set_irn_link(block, info);
 717   info->nodes     = new_node_set();
 718   info->antic_in  = new_node_set();
 719   info->avail_out = new_value_set();
 720   info->avail     = NULL;
 721   info->not_found = 0;
 722   info->new_set   = NULL;
 723   info->next      = env->list;
 724   env->list       = info;
 725
 726   /* fill the nodes set, we will need it later */
 727   for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
 728     ir_node *n = get_irn_out(block, i);
 729
 730     set_irn_link(n, NULL);
 731
 732     /* we cannot optimize pinned nodes, so do not remember them */
 733     if (is_nice_value(n))
 734       node_add(info->nodes, n);
 735   }
 736 }
 737
 738 /**
 739  * Perform insertion of partially redundant values.
 740  * For every Block node, do the following:
 741  * 1.  Propagate the NEW_SETS of the dominator into the current block.
 742  * If the block has multiple predecessors,
 743  *     2a. Iterate over the ANTIC expressions for the block to see if
 744  *         any of them are partially redundant.
 745  *     2b. If so, insert them into the necessary predecessors to make
 746  *         the expression fully redundant.
 747  *     2c. Insert a new Phi merging the values of the predecessors.
 748  *     2d. Insert the new Phi, and the new expressions, into the
 749  *         NEW_SETS set.
 750  */
 751 static void insert_nodes(ir_node *block, void *ctx)
 752 {
 753   pre_env *env = ctx;
 754   value_entry *entry;
 755   ir_node *e, *idom, *first_s, *worklist;
 756   block_info *curr_info, *idom_info;
 757   int pos, arity = get_irn_intra_arity(block);
 758   int all_same, by_some, updated;
 759
 760   /* ensure that even the start block has a new_set */
 761   curr_info = get_block_info(block);
 762   if (curr_info->new_set)
 763     del_value_set(curr_info->new_set);
 764   curr_info->new_set = new_value_set();
 765
 766   if (block == env->start_block)
 767     return;
 768
 769   idom = get_Block_idom(block);
 770   idom_info = get_block_info(idom);
 771
 772   /* update the new_sets */
 773   updated = 0;
 774   dump_value_set(idom_info->new_set, "[New Set]", idom);
 775   value_set_foreach(entry, idom_info->new_set) {
 776     updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
 777   }
 778   if (updated)
 779     dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
 780
 781   if (arity <= 1)
 782     return;
 783
 784   /* convert the set into a list. This allows the removal of
 785    * elements from the set */
 786   worklist = NULL;
 787   node_set_foreach(e, curr_info->antic_in) {
 788     set_irn_link(e, worklist);
 789     worklist = e;
 790   }
 791
 792   for (e = worklist; e != NULL; e = get_irn_link(e)) {
 793     ir_mode *mode;
 794
 795     /* If the value was already computed in the dominator, then
 796        it is totally redundant.  Hence we have nothing to insert. */
 797     if (value_lookup(idom_info->avail_out, e)) {
 798 //      DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
 799       continue;
 800     }
 801
 802     by_some  = 0;
 803     all_same = 1;
 804     first_s  = NULL;
 805     mode     = NULL;
 806
 807     /* for all predecessor blocks */
 808     for (pos = 0; pos < arity; ++pos) {
 809       block_info *pred_info;
 810       ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 811       ir_node *e_prime, *v_prime, *e_dprime;
 812
 813       /* ignore bad blocks. */
 814       if (is_Bad(pred_blk))
 815         continue;
 816
 817       e_prime = phi_translate(e, block, pos, env);
 818       v_prime = e_prime;
 819
 820       pred_info = get_block_info(pred_blk);
 821       e_dprime = value_lookup(pred_info->avail_out, v_prime);
 822
 823       if (e_dprime == NULL) {
 824         all_same = 0;
 825         pred_info->avail = e_prime;
 826         pred_info->not_found = 1;
 827       }
 828       else {
 829         mode     = get_irn_mode(e_dprime);
 830         e_dprime = e_dprime;
 831         pred_info->avail = e_dprime;
 832         pred_info->not_found = 0;
 833         by_some = 1;
 834         if (first_s == NULL)
 835           first_s = e_dprime;
 836         else if (first_s != e_dprime)
 837           all_same = 0;
 838
 839         DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
 840       }  /* if */
 841     }  /* for */
 842
 843     /* If it's not the same value already existing along every predecessor, and
 844        it's defined by some predecessor, it is partially redundant. */
 845     if (! all_same && by_some) {
 846       ir_node *phi, **in;
 847
 848       DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
 849
 850       in = xmalloc(arity * sizeof(*in));
 851       /* for all predecessor blocks */
 852       for (pos = 0; pos < arity; ++pos) {
 853         ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 854         block_info *pred_info = get_block_info(pred_blk);
 855
 856         /* ignore bad blocks. */
 857         if (is_Bad(pred_blk)) {
 858           in[pos] = new_Bad();
 859           continue;
 860         }
 861
 862         /* ignore blocks that already have the expression */
 863         if (pred_info->not_found) {
 864           ir_node *e_prime = pred_info->avail;
 865           ir_node *nn;
 866           if (!is_Phi(e_prime)) {
 867             mode = get_irn_mode(e_prime);
 868             nn = new_ir_node(
 869               get_irn_dbg_info(e_prime),
 870               current_ir_graph, pred_blk,
 871               get_irn_op(e_prime),
 872               mode,
 873               get_irn_arity(e_prime),
 874               get_irn_in(e_prime) + 1);
 875             copy_node_attr(e_prime, nn);
 876
 877             DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
 878             pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
 879           }
 880         }
 881         in[pos] = pred_info->avail;
 882       }  /* for */
 883       phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
 884       free(in);
 885       value_add_or_replace(curr_info->avail_out, phi, e);
 886       value_add(curr_info->new_set, phi, e);
 887       DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
 888
 889       /* the good case: we really replace an instruction */
 890       node_set_remove(curr_info->antic_in, e);
 891
 892       env->changes |= 1;
 893     }  /* if */
 894   }  /* node_set_foreach */
 895 }  /* insert_nodes */
 896
 897 /**
 898  * Do the elimination step: collect all changes
 899  * We cannot do the changes right here, as this would change
 900  * the hash values of the nodes in the avail_out set!
 901  */
 902 static void collect_elim_pairs(ir_node *block, void *ctx)
 903 {
 904   pre_env *env = ctx;
 905   block_info *curr_info = get_block_info(block);
 906   ir_node *v;
 907
 908   dump_node_set(curr_info->nodes, "Updating nodes", block);
 909   node_set_foreach(v, curr_info->nodes) {
 910     ir_node *l = value_lookup(curr_info->avail_out, v);
 911
 912     assert(l);
 913     if (l != v) {
 914       elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
 915
 916       p->old_node = v;
 917       p->new_node = l;
 918       p->next     = env->pairs;
 919       env->pairs  = p;
 920     }
 921   }
 922 }
 923
 924 /**
 925  * Do all the recorded changes and optimize
 926  * newly created Phi's.
 927  */
 928 static void eliminate_nodes(elim_pair *pairs)
 929 {
 930   elim_pair *p;
 931
 932   for (p = pairs; p != NULL; p = p->next) {
 933     DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
 934     /*
 935      * PRE tends to create Phi(self, self, ... , x, self, self, ...)
 936      * which we can optimize here
 937      */
 938     if (is_Phi(p->new_node)) {
 939       int i;
 940       ir_node *res = NULL;
 941
 942       for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
 943         ir_node *pred = get_irn_n(p->new_node, i);
 944
 945         if (pred != p->old_node) {
 946           if (res) {
 947             res = NULL;
 948             break;
 949           }
 950           res = pred;
 951         }
 952       }
 953       if (res)
 954         p->new_node = res;
 955     }
 956     exchange(p->old_node, p->new_node);
 957   }
 958 }
 959
 960 /*
 961  * Argh: Endless loops cause problems, because the
 962  * insert algorithm did not terminate. We get tranalated nodes that
 963  * references the origin. These nodes are translated again and again...
 964  *
 965  * The current fix is to use post-dominance. This simple ignores
 966  * endless loops, ie we cannot optimize them.
 967  */
 968 void do_gvn_pre(ir_graph *irg)
 969 {
 970   struct obstack obst;
 971   pre_env a_env;
 972   optimization_state_t state;
 973   block_info *p;
 974   unsigned antic_iter, insert_iter;
 975
 976   /* register a debug mask */
 977   FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
 978   firm_dbg_set_mask(dbg, SET_LEVEL_2);
 979
 980   obstack_init(&obst);
 981   a_env.obst        = &obst;
 982   a_env.trans_set   = new_node_set();
 983   a_env.list        = NULL;
 984   a_env.start_block = get_irg_start_block(irg);
 985   a_env.end_block   = get_irg_end_block(irg);
 986   a_env.pairs       = NULL;
 987
 988   /* Move Proj's into the same block as their args,
 989      else we would assign the result to wrong blocks */
 990   normalize_proj_nodes(irg);
 991
 992   /* critical edges MUST be removed */
 993   remove_critical_cf_edges(irg);
 994
 995   /* we need dominator for Antic_out calculation */
 996   if (get_irg_dom_state(irg) != dom_consistent)
 997     compute_doms(irg);
 998   if (get_irg_postdom_state(irg) != dom_consistent)
 999     compute_postdoms(irg);
1000   /* we get all nodes of a block by following outs */
1001   if (get_irg_outs_state(irg) != outs_consistent)
1002     compute_irg_outs(irg);
1003
1004   /*
1005    * Switch on GCSE. We need it to correctly compute
1006    * the leader of a node by hashing.
1007    */
1008   save_optimization_state(&state);
1009   set_opt_global_cse(1);
1010
1011   DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1012   printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1013
1014   /* allocate block info for all blocks */
1015   irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1016
1017   /* compute the available value sets for all blocks */
1018   dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1019
1020   /* compute the anticipated value sets for all blocks */
1021   inc_irg_visited(irg);
1022   antic_iter = 0;
1023   a_env.first_iter = 1;
1024   do {
1025     DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1026     a_env.changes = 0;
1027     irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1028 //    postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1029     a_env.first_iter = 0;
1030     DB((dbg, LEVEL_1, "------------------------\n"));
1031   } while (a_env.changes != 0);
1032
1033   /* compute redundant expressions */
1034   insert_iter = 0;
1035   do {
1036     DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1037     a_env.changes = 0;
1038     dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1039     DB((dbg, LEVEL_1, "------------------------\n"));
1040   } while (a_env.changes != 0);
1041
1042   /* last step: eliminate nodes */
1043   dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1044   eliminate_nodes(a_env.pairs);
1045
1046   restore_optimization_state(&state);
1047
1048   /* clean up: delete all sets */
1049   for (p = a_env.list; p != NULL; p = p->next) {
1050     if (p->antic_in)
1051       del_node_set(p->antic_in);
1052     if (p->avail_out)
1053       del_value_set(p->avail_out);
1054     if (p->nodes)
1055       del_node_set(p->nodes);
1056     if (p->new_set)
1057       del_value_set(p->new_set);
1058   }
1059   del_node_set(a_env.trans_set);
1060   obstack_free(&obst, NULL);
1061   set_irg_pinned(irg, op_pin_state_pinned);
1062
1063   if (a_env.pairs) {
1064     set_irg_outs_inconsistent(irg);
1065     set_irg_loopinfo_inconsistent(irg);
1066   }
1067 }  /* do_gvn_pre */