nsz Git - libfirm/blob - ir/opt/gvn_pre.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Global Value Numbering Partial Redundancy Elimination
  23  *          (VanDrunen Hosking 2004)
  24  * @author  Michael Beck
  25  * @version $Id$
  26  * @brief
  27  */
  28 #include "config.h"
  29
  30 #include "iroptimize.h"
  31 #include "irflag.h"
  32 #include "irdom.h"
  33 #include "irouts.h"
  34 #include "irgopt.h"
  35 #include "irgwalk.h"
  36 #include "ircons.h"
  37 #include "irgmod.h"
  38 #include "valueset.h"
  39 #include "irnodemap.h"
  40 #include "irnodeset.h"
  41 #include "iredges.h"
  42 #include "iropt_dbg.h"
  43 #include "debug.h"
  44 #include "irpass.h"
  45
  46 #include "irgraph_t.h"
  47 #include "irnode_t.h"
  48 #include "iropt_t.h"
  49
  50 /** Additional info we need for every block. */
  51 typedef struct block_info {
  52         ir_valueset_t     *exp_gen;   /**< The set of expression per block. */
  53         ir_valueset_t     *avail_out; /**< The Avail_out set for a block. */
  54         ir_valueset_t     *antic_in;  /**< The Antic_in set for a block. */
  55         ir_valueset_t     *new_set;   /**< The set of all new values for a block. */
  56         ir_node           *avail;     /**< The get_map(avail, block) result. */
  57         ir_node           *block;     /**< The Block of the block info. */
  58         struct block_info *next;      /**< Links all entries, so we can recover the sets easily. */
  59         int               not_found;  /**< Non-zero, if avail was not found in this block. */
  60 } block_info;
  61
  62 /**
  63  * A pair of nodes that must be exchanged.
  64  * We must defer the exchange because our hash-sets cannot
  65  * find an already replace node else.
  66  */
  67 typedef struct elim_pair {
  68         ir_node *old_node;      /**< The old node that will be replaced. */
  69         ir_node *new_node;      /**< The new node. */
  70         struct elim_pair *next; /**< Links all entries in a list. */
  71         int     reason;         /**< The reason for the replacement. */
  72 } elim_pair;
  73
  74 /** The environment for the GVN-PRE algorithm */
  75 typedef struct pre_env {
  76         struct obstack *obst;   /**< The obstack to allocate on. */
  77         ir_node *start_block;   /**< The start block of the current graph. */
  78         ir_node *end_block;     /**< The end block of the current graph */
  79         block_info *list;       /**< Links all block info entries for easier recovery. */
  80         elim_pair *pairs;       /**< A list of node pairs that must be eliminated. */
  81         unsigned last_idx;      /**< last node index of "old" nodes, all higher indexes are newly created once. */
  82         char changes;           /**< Non-zero, if calculation of Antic_in has changed. */
  83         char first_iter;        /**< non-zero for first iteration */
  84 } pre_env;
  85
  86 static ir_nodemap_t value_map;
  87
  88 /** The debug module handle. */
  89 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  90
  91 /* ----------  Functions for Value sets ---------- */
  92
  93 /** computes dst = dst \/ src for value sets */
  94 static void value_union(ir_valueset_t *dst, ir_valueset_t *src)
  95 {
  96         ir_valueset_iterator_t iter;
  97         ir_node *value, *expr;
  98
  99         foreach_valueset(src, value, expr, iter) {
 100                 ir_valueset_insert(dst, value, expr);
 101         }
 102 }
 103
 104
 105 /* ----------  Functions for Values ---------- */
 106
 107 /**
 108  * Add a node e representing the value v to the set.
 109  *
 110  * @param e  a node representing an expression
 111  * @param v  a node representing a value
 112  *
 113  * @return the final value for the expression e
 114  */
 115 static ir_node *add(ir_node *e, ir_node *v)
 116 {
 117         if (is_Proj(v)) {
 118                 ir_node *pred = get_Proj_pred(v);
 119                 ir_node *v_pred = identify_remember(pred);
 120
 121                 if (v_pred != pred) {
 122                         /* must create a new value here */
 123                         v = new_r_Proj(v_pred, get_irn_mode(v), get_Proj_proj(v));
 124                 }
 125         }
 126         v = identify_remember(v);
 127         ir_nodemap_insert(&value_map, e, v);
 128         return v;
 129 }  /* add */
 130
 131 /**
 132  * Lookup a value in a value set.
 133  *
 134  * @param e  a node representing an expression
 135  *
 136  * @return a node representing the value or NULL if
 137  *         the given expression is not available
 138  */
 139 static ir_node *lookup(ir_node *e)
 140 {
 141         ir_node *value = (ir_node*)ir_nodemap_get(&value_map, e);
 142         if (value != NULL)
 143                 return identify_remember(value);
 144         return NULL;
 145 }
 146
 147 /**
 148  * Return the block info of a block.
 149  *
 150  * @param block  the block
 151  */
 152 static block_info *get_block_info(ir_node *block)
 153 {
 154         return (block_info*)get_irn_link(block);
 155 }
 156
 157 /**
 158  * Allocate a block info for a block.
 159  *
 160  * @param block   the block
 161  * @param env     the environment
 162  */
 163 static void alloc_blk_info(ir_node *block, pre_env *env)
 164 {
 165         block_info *info = OALLOC(env->obst, block_info);
 166
 167         set_irn_link(block, info);
 168         info->exp_gen   = ir_valueset_new(16);
 169         info->avail_out = ir_valueset_new(16);
 170         info->antic_in  = ir_valueset_new(16);
 171         info->new_set   = NULL;
 172         info->avail     = NULL;
 173         info->block     = block;
 174         info->next      = env->list;
 175         env->list       = info;
 176         info->not_found = 0;
 177 }  /* alloc_blk_info */
 178
 179 /**
 180  * Returns non-zero if a node is movable and a possible candidate for PRE.
 181  *
 182  * @param n  the node
 183  */
 184 static int is_nice_value(ir_node *n)
 185 {
 186         ir_mode *mode;
 187
 188         while (is_Proj(n))
 189                 n = get_Proj_pred(n);
 190         if (get_irn_pinned(n) == op_pin_state_pinned)
 191                 return 0;
 192         mode = get_irn_mode(n);
 193         if (!mode_is_data(mode)) {
 194                 if (! is_Div(n) && ! is_Mod(n))
 195                         return 0;
 196                 if (! is_NoMem(get_fragile_op_mem(n)))
 197                         return 0;
 198         }
 199         return 1;
 200 }  /* is_nice_value */
 201
 202 #ifdef DEBUG_libfirm
 203 /**
 204  * Dump a value set.
 205  *
 206  * @param set    the set to dump
 207  * @param txt    a text to describe the set
 208  * @param block  the owner block of the set
 209  */
 210 static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
 211 {
 212         ir_valueset_iterator_t iter;
 213         ir_node *value, *expr;
 214         int i;
 215
 216         DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
 217         i = 0;
 218         foreach_valueset(set, value, expr, iter) {
 219                 if ((i & 3) == 3)
 220                         DB((dbg, LEVEL_2, "\n"));
 221                 if (value != expr)
 222                         DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
 223                 else
 224                         DB((dbg, LEVEL_2, " %+F,", expr));
 225                 ++i;
 226         }
 227         DB((dbg, LEVEL_2, "\n}\n"));
 228 }  /* dump_value_set */
 229
 230 #else
 231 #define dump_value_set(set, txt, block)
 232 #endif /* DEBUG_libfirm */
 233
 234 /**
 235  * Topological walker. Allocates block info for every block and place nodes in
 236  * topological order into the nodes set.
 237  */
 238 static void topo_walker(ir_node *irn, void *ctx)
 239 {
 240         pre_env    *env = (pre_env*)ctx;
 241         ir_node    *block;
 242         block_info *info;
 243         ir_node    *value;
 244
 245         if (is_Block(irn)) {
 246                 /* the topological walker ensures that blocks are visited before anything else */
 247                 alloc_blk_info(irn, env);
 248                 return;
 249         }
 250         /* GVN step: remember the value */
 251         value = add(irn, irn);
 252
 253         /* no need to put constants into the sets: they are always redundant */
 254         if (! is_nice_value(irn) || is_irn_constlike(irn))
 255                 return;
 256
 257         /* Do not put mode_T nodes info the sets, or PhiT will be created
 258           (which are not allowed in Firm). Instead, put the Proj's here only. */
 259         if (get_irn_mode(irn) == mode_T)
 260                 return;
 261
 262         /* place this node into the set of possible nodes of its block */
 263         block = get_nodes_block(irn);
 264         info  = get_block_info(block);
 265
 266         ir_valueset_insert(info->exp_gen, value, irn);
 267 }
 268
 269 /**
 270  * Computes Avail_out(block):
 271  *
 272  * Avail_in(block)  = Avail_out(dom(block))
 273  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
 274  *
 275  * Precondition:
 276  *  This function must be called in the top-down dominance order:
 277  *  Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
 278  *
 279  * @param block   the block
 280  * @param ctx     walker context
 281  */
 282 static void compute_avail_top_down(ir_node *block, void *ctx)
 283 {
 284         pre_env    *env = (pre_env*)ctx;
 285         block_info *dom_info;
 286         block_info *info = get_block_info(block);
 287         ir_node    *dom_blk;
 288
 289         /* we don't need the end block Avail */
 290         if (block == env->end_block)
 291                 return;
 292
 293         /*
 294          * First add all nodes from the dominator.
 295          * This must be done to ensure that Antic_out contains the leader
 296          * for every node. The root has no dominator.
 297          */
 298         if (block != env->start_block) {
 299                 dom_blk = get_Block_idom(block);
 300                 assert(is_Block(dom_blk));
 301
 302                 dom_info = get_block_info(dom_blk);
 303                 assert(dom_info);
 304
 305                 value_union(info->avail_out, dom_info->avail_out);
 306         }
 307         value_union(info->avail_out, info->exp_gen);
 308
 309         dump_value_set(info->avail_out, "Avail_out", block);
 310 }
 311
 312 /**
 313  * check if a node n is clean in block block.
 314  *
 315  * @param n      the node
 316  * @param block  the block
 317  * @param set    a value set, containing the already processed predecessors
 318  */
 319 static int is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *set)
 320 {
 321         int i;
 322
 323         if (is_Phi(n))
 324                 return 1;
 325
 326         if (! is_nice_value(n))
 327                 return 0;
 328
 329         for (i = get_irn_arity(n) - 1; i >= 0; --i) {
 330                 ir_node *pred = get_irn_n(n, i);
 331                 ir_node *value;
 332
 333                 if (get_nodes_block(pred) != block)
 334                         continue;
 335
 336                 if (is_Phi(pred))
 337                         continue;
 338
 339                 if (! is_nice_value(pred))
 340                         return 0;
 341
 342                 value = lookup(pred);
 343                 if (! value)
 344                         return 0;
 345                 if (! ir_valueset_lookup(set, value))
 346                         return 0;
 347         }
 348         return 1;
 349 }  /* is_clean_in_block */
 350
 351 /**
 352  * Implements phi_translate. Translate a expression above a Phi.
 353  *
 354  * @param node        the node
 355  * @param block       the block in which the node is translated
 356  * @param pos         the input number of the destination block
 357  * @param translated  the valueset containing the other already translated nodes
 358  *
 359  * @return a node representing the translated value
 360  */
 361 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *translated)
 362 {
 363         ir_node        *nn;
 364         int            i, arity;
 365
 366         if (is_Phi(node)) {
 367                 if (get_nodes_block(node) == block) {
 368                         /* a Phi inside our block */
 369                         return get_Phi_pred(node, pos);
 370                 }
 371                 /* already outside */
 372                 return node;
 373         }
 374
 375         arity = get_irn_arity(node);
 376
 377         /* check if the node has at least one Phi predecessor */
 378         for (i = 0; i < arity; ++i) {
 379                 ir_node *pred    = get_irn_n(node, i);
 380                 ir_node *leader  = lookup(pred);
 381                 ir_node *trans;
 382
 383                 leader = leader != NULL ? leader : pred;
 384                 trans  = (ir_node*)ir_valueset_lookup(translated, leader);
 385
 386                 if ((trans != NULL && trans != leader) || (is_Phi(leader) && get_nodes_block(leader) == block))
 387                         break;
 388         }
 389         if (i >= arity) {
 390                 /* no translation needed */
 391                 return node;
 392         }
 393
 394         nn = new_ir_node(
 395                 get_irn_dbg_info(node),
 396                 current_ir_graph,
 397                 get_nodes_block(node),
 398                 get_irn_op(node),
 399                 get_irn_mode(node),
 400                 arity,
 401                 get_irn_in(node));
 402         /* We need the attribute copy here, because the Hash value of a
 403            node might depend on that. */
 404         copy_node_attr(current_ir_graph, node, nn);
 405
 406         for (i = 0; i < arity; ++i) {
 407                 ir_node *pred    = get_irn_n(node, i);
 408                 ir_node *leader  = lookup(pred);
 409                 ir_node *trans;
 410
 411                 leader = leader != NULL ? leader : pred;
 412                 trans  = (ir_node*)ir_valueset_lookup(translated, leader);
 413                 if (trans == NULL)
 414                         trans = leader;
 415
 416                 if (is_Phi(trans) && get_nodes_block(trans) == block)
 417                         set_irn_n(nn, i, get_Phi_pred(trans, pos));
 418                 else
 419                         set_irn_n(nn, i, trans);
 420         }
 421         nn = optimize_node(nn);
 422         return nn;
 423 }  /* phi_translate */
 424
 425 /**
 426  * Block-walker, computes Antic_in(block).
 427  *
 428  * @param block  the block
 429  * @param ctx    the walker environment
 430  */
 431 static void compute_antic(ir_node *block, void *ctx)
 432 {
 433         pre_env    *env = (pre_env*)ctx;
 434         block_info *succ_info;
 435         block_info *info = get_block_info(block);
 436         ir_node    *succ, *value, *expr;
 437         size_t     size;
 438         ir_valueset_iterator_t  iter;
 439
 440         /* no need for computations in start block */
 441         if (block == env->start_block)
 442                 return;
 443
 444         size = ir_valueset_size(info->antic_in);
 445
 446         /* the end block has no successor */
 447         if (block != env->end_block) {
 448                 int n_succ;
 449
 450                 /*
 451                  * This step puts all generated expression from the current
 452                  * current block into Antic_in.
 453                  * It is enough to do this in the first iteration only, because
 454                  * the set info->exp_gen is not changed anymore.
 455                  */
 456                 if (env->first_iter) {
 457                         foreach_valueset(info->exp_gen, value, expr, iter) {
 458                                 ir_valueset_insert(info->antic_in, value, expr);
 459                         }
 460                 }
 461
 462                 n_succ = get_Block_n_cfg_outs(block);
 463                 if (n_succ == 1) {
 464                         int pos = -1;
 465
 466                         /* find blocks position in succ's block predecessors */
 467                         succ = get_Block_cfg_out(block, 0);
 468                         pos  = get_Block_cfgpred_pos(succ, block);
 469                         assert(pos >= 0);
 470
 471                         succ_info = get_block_info(succ);
 472                         /* translate into list: we cannot insert into a set we iterate
 473                          * and succ might be equal to block for endless loops */
 474                         foreach_valueset(succ_info->antic_in, value, expr, iter) {
 475                                 ir_node *trans = phi_translate(expr, succ, pos, info->antic_in);
 476
 477                                 if (is_clean_in_block(trans, block, info->antic_in))
 478                                         ir_valueset_insert(info->antic_in, value, trans);
 479                         }
 480                 } else { /* n_succ > 1 */
 481                         ir_node    *succ0;
 482                         block_info *succ0_info;
 483                         int        i;
 484
 485                         assert(n_succ > 1);
 486
 487                         /* Select a successor to compute the disjoint of all Nodes
 488                            sets, it might be useful to select the block with the
 489                            smallest number of nodes.  For simplicity we choose the
 490                            first one. */
 491                         succ0      = get_Block_cfg_out(block, 0);
 492                         succ0_info = get_block_info(succ0);
 493                         foreach_valueset(succ0_info->antic_in, value, expr, iter) {
 494                                 /* we need the disjoint */
 495                                 for (i = 1; i < n_succ; ++i) {
 496                                         ir_node *succ = get_Block_cfg_out(block, i);
 497                                         block_info *succ_info = get_block_info(succ);
 498                                         if (ir_valueset_lookup(succ_info->antic_in, value) == NULL)
 499                                                 break;
 500                                 }
 501                                 if (i >= n_succ) {
 502                                         /* we found a value that is common in all Antic_in(succ(b)),
 503                                             put it in Antic_in(b) if the value is NOT already represented. */
 504                                         if (is_clean_in_block(expr, block, info->antic_in))
 505                                                 ir_valueset_insert(info->antic_in, value, expr);
 506                                 }
 507                         }
 508                 }
 509         }
 510
 511         /* we do not need a clean here, because we ensure that only cleaned nodes are in exp_gen
 512          * and all other sets */
 513
 514         dump_value_set(info->antic_in, "Antic_in", block);
 515         if (size != ir_valueset_size(info->antic_in)) {
 516                 /* the Antic_in set has changed */
 517                 env->changes |= 1;
 518         }
 519 }  /* compute_antic */
 520
 521 /**
 522  * Perform insertion of partially redundant values.
 523  * For every Block node, do the following:
 524  * 1.  Propagate the NEW_SETS of the dominator into the current block.
 525  * If the block has multiple predecessors,
 526  *     2a. Iterate over the ANTIC expressions for the block to see if
 527  *         any of them are partially redundant.
 528  *     2b. If so, insert them into the necessary predecessors to make
 529  *         the expression fully redundant.
 530  *     2c. Insert a new Phi merging the values of the predecessors.
 531  *     2d. Insert the new Phi, and the new expressions, into the
 532  *         NEW_SETS set.
 533  *
 534  * @param block  the block
 535  * @param ctx    the walker environment
 536  */
 537 static void insert_nodes(ir_node *block, void *ctx)
 538 {
 539         pre_env    *env = (pre_env*)ctx;
 540         ir_node    *value, *expr, *idom, *first_s;
 541         block_info *curr_info, *idom_info;
 542         int        pos, arity = get_irn_arity(block);
 543         int        all_same, by_some, updated;
 544         ir_valueset_iterator_t iter;
 545
 546         /* ensure that even the start block has a new_set */
 547         curr_info = get_block_info(block);
 548         if (curr_info->new_set)
 549                 ir_valueset_del(curr_info->new_set);
 550         curr_info->new_set = ir_valueset_new(16);
 551
 552         if (block == env->start_block)
 553                 return;
 554
 555         idom      = get_Block_idom(block);
 556         idom_info = get_block_info(idom);
 557
 558         /* update the new_sets */
 559         updated = 0;
 560         dump_value_set(idom_info->new_set, "[New Set]", idom);
 561         foreach_valueset(idom_info->new_set, value, expr, iter) {
 562                 ir_valueset_insert(curr_info->new_set, value, expr);
 563                 updated |= ir_valueset_replace(curr_info->avail_out, value, expr);
 564         }
 565         if (updated) {
 566                 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
 567         }
 568
 569         if (arity <= 1)
 570                 return;
 571
 572         /* convert the set into a list. This allows the removal of
 573          * elements from the set */
 574         foreach_valueset(curr_info->antic_in, value, expr, iter) {
 575                 ir_mode *mode;
 576
 577                 /* If the value was already computed in the dominator, then
 578                    it is totally redundant.  Hence we have nothing to insert. */
 579                 if (ir_valueset_lookup(idom_info->avail_out, value)) {
 580                         //      DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
 581                         continue;
 582                 }
 583
 584                 by_some  = 0;
 585                 all_same = 1;
 586                 first_s  = NULL;
 587                 mode     = NULL;
 588
 589                 /* for all predecessor blocks */
 590                 for (pos = 0; pos < arity; ++pos) {
 591                         block_info *pred_info;
 592                         ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 593                         ir_node *e_prime, *v_prime, *e_dprime;
 594
 595                         /* ignore bad blocks. */
 596                         if (is_Bad(pred_blk))
 597                                 continue;
 598
 599                         e_prime = phi_translate(expr, block, pos, curr_info->avail_out);
 600                         v_prime = lookup(e_prime);
 601                         if (v_prime == NULL)
 602                                 v_prime = value;
 603
 604                         pred_info = get_block_info(pred_blk);
 605                         e_dprime  = (ir_node*)ir_valueset_lookup(pred_info->avail_out, v_prime);
 606
 607                         if (e_dprime == NULL) {
 608                                 pred_info->avail     = e_prime;
 609                                 pred_info->not_found = 1;
 610                                 all_same = 0;
 611                         } else {
 612                                 pred_info->avail     = e_dprime;
 613                                 pred_info->not_found = 0;
 614                                 mode     = get_irn_mode(e_dprime);
 615                                 e_dprime = e_dprime;
 616                                 by_some  = 1;
 617                                 if (first_s == NULL)
 618                                         first_s = e_dprime;
 619                                 else if (first_s != e_dprime)
 620                                         all_same = 0;
 621
 622                                 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, e_dprime, pred_blk));
 623                         }  /* if */
 624                 }  /* for */
 625
 626                 /* If it's not the same value already existing along every predecessor, and
 627                    it's defined by some predecessor, it is partially redundant. */
 628                 if (! all_same && by_some) {
 629                         ir_node *phi, *l, **in;
 630
 631                         DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block));
 632
 633                         in = XMALLOCN(ir_node*, arity);
 634                         /* for all predecessor blocks */
 635                         for (pos = 0; pos < arity; ++pos) {
 636                                 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 637                                 block_info *pred_info = get_block_info(pred_blk);
 638
 639                                 /* ignore bad blocks. */
 640                                 if (is_Bad(pred_blk)) {
 641                                         ir_graph *irg = get_irn_irg(pred_blk);
 642                                         in[pos] = new_r_Bad(irg, mode_X);
 643                                         continue;
 644                                 }
 645
 646                                 /* ignore blocks that already have the expression */
 647                                 if (pred_info->not_found) {
 648                                         ir_node *e_prime = pred_info->avail;
 649                                         ir_node *nn;
 650                                         if (!is_Phi(e_prime)) {
 651                                                 ir_node *proj_pred = NULL;
 652                                                 if (is_Proj(e_prime)) {
 653                                                         ir_node *pred = get_Proj_pred(e_prime);
 654                                                         mode = get_irn_mode(pred);
 655                                                         nn = new_ir_node(
 656                                                                 get_irn_dbg_info(pred),
 657                                                                 current_ir_graph, pred_blk,
 658                                                                 get_irn_op(pred),
 659                                                                 mode,
 660                                                                 get_irn_arity(pred),
 661                                                                 get_irn_in(pred) + 1);
 662                                                         copy_node_attr(current_ir_graph, pred, nn);
 663
 664                                                         DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk));
 665                                                         proj_pred = nn;
 666                                                 }
 667                                                 mode = get_irn_mode(e_prime);
 668                                                 nn = new_ir_node(
 669                                                         get_irn_dbg_info(e_prime),
 670                                                         current_ir_graph, pred_blk,
 671                                                         get_irn_op(e_prime),
 672                                                         mode,
 673                                                         get_irn_arity(e_prime),
 674                                                         get_irn_in(e_prime) + 1);
 675                                                 copy_node_attr(current_ir_graph, e_prime, nn);
 676                                                 if (proj_pred != NULL) {
 677                                                         set_Proj_pred(nn, proj_pred);
 678                                                 }
 679
 680                                                 DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk));
 681                                                 l = lookup(expr);
 682                                                 if (l == NULL) {
 683                                                         l = add(expr, value);
 684                                                 }
 685                                                 ir_valueset_insert(pred_info->avail_out, add(nn, l), nn);
 686                                                 pred_info->avail = nn;
 687                                         }
 688                                 }
 689                                 in[pos] = pred_info->avail;
 690                         }  /* for */
 691                         phi = new_r_Phi(block, arity, in, mode);
 692                         l = lookup(expr);
 693                         if (l == NULL) {
 694                                 l = add(expr, value);
 695                         }
 696                         value = add(phi, l);
 697                         ir_valueset_replace(curr_info->avail_out, value, phi);
 698                         ir_valueset_insert(curr_info->new_set, value, phi);
 699                         free(in);
 700                         DB((dbg, LEVEL_1, "New %+F for redundant %+F created\n", phi, expr));
 701                         ir_valueset_remove_iterator(curr_info->antic_in, &iter);
 702                         env->changes |= 1;
 703                 }  /* if */
 704   }  /* node_set_foreach */
 705 }  /* insert_nodes */
 706
 707 /**
 708  * Walker, change nodes by its value if different.
 709  *
 710  * We cannot do the changes right here, as this would change
 711  * the hash values of the nodes in the avail_out set!
 712  *
 713  * @param irn  the node
 714  * @param ctx  the walker environment
 715  */
 716 static void eliminate(ir_node *irn, void *ctx)
 717 {
 718         pre_env *env = (pre_env*)ctx;
 719
 720         if (!is_Block(irn)) {
 721                 ir_node *block = get_nodes_block(irn);
 722                 block_info *bl = get_block_info(block);
 723                 ir_node *value = lookup(irn);
 724
 725                 if (value != NULL) {
 726                         ir_node *expr = (ir_node*)ir_valueset_lookup(bl->avail_out, value);
 727
 728                         if (expr != NULL && expr != irn) {
 729                                 elim_pair *p = OALLOC(env->obst, elim_pair);
 730
 731                                 p->old_node = irn;
 732                                 p->new_node = expr;
 733                                 p->next     = env->pairs;
 734                                 p->reason   = get_irn_idx(expr) >= env->last_idx ? FS_OPT_GVN_PARTLY : FS_OPT_GVN_FULLY;
 735                                 env->pairs  = p;
 736                         }
 737                 }
 738         }
 739 }  /* eliminate */
 740
 741 /**
 742  * Do all the recorded changes and optimize
 743  * newly created Phi's.
 744  *
 745  * @param pairs  list of elimination pairs
 746  */
 747 static void eliminate_nodes(elim_pair *pairs)
 748 {
 749         elim_pair *p;
 750
 751         for (p = pairs; p != NULL; p = p->next) {
 752                 /* might be already changed */
 753                 p->new_node = skip_Id(p->new_node);
 754
 755                 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
 756                 /*
 757                  * PRE tends to create Phi(self, self, ... , x, self, self, ...)
 758                  * which we can optimize here
 759                  */
 760                 if (is_Phi(p->new_node)) {
 761                         int i;
 762                         ir_node *res = NULL;
 763
 764                         for (i = get_irn_arity(p->new_node) - 1; i >= 0; --i) {
 765                                 ir_node *pred = get_irn_n(p->new_node, i);
 766
 767                                 if (pred != p->old_node) {
 768                                         if (res) {
 769                                                 res = NULL;
 770                                                 break;
 771                                         }
 772                                         res = pred;
 773                                 }
 774                         }
 775                         if (res) {
 776                                 exchange(p->new_node, res);
 777                                 p->new_node = res;
 778                         }
 779                 }
 780                 DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
 781                 exchange(p->old_node, p->new_node);
 782         }
 783 }  /* eliminate_nodes */
 784
 785 /*
 786  * Argh: Endless loops cause problems, because the
 787  * insert algorithm did not terminate. We get translated nodes that
 788  * references the origin. These nodes are translated again and again...
 789  *
 790  * The current fix is to use post-dominance. This simple ignores
 791  * endless loops, i.e. we cannot optimize them.
 792  */
 793 void do_gvn_pre(ir_graph *irg)
 794 {
 795         struct obstack       obst;
 796         pre_env              a_env;
 797         optimization_state_t state;
 798         block_info           *bl_info;
 799         unsigned             antic_iter, insert_iter;
 800         ir_node              *value, *expr;
 801
 802         /* register a debug mask */
 803         FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
 804
 805         /* edges will crash if enabled due to our allocate on other obstack trick */
 806         edges_deactivate(irg);
 807
 808         new_identities(irg);
 809         ir_nodemap_init(&value_map);
 810
 811         obstack_init(&obst);
 812         a_env.obst        = &obst;
 813         a_env.list        = NULL;
 814         a_env.start_block = get_irg_start_block(irg);
 815         a_env.end_block   = get_irg_end_block(irg);
 816         a_env.pairs       = NULL;
 817
 818         /* critical edges MUST be removed */
 819         remove_critical_cf_edges(irg);
 820
 821         /* we need dominator for Antic_out calculation */
 822         assure_doms(irg);
 823         assure_postdoms(irg);
 824         /* we get all nodes of a block by following outs */
 825         assure_irg_outs(irg);
 826
 827         /*
 828          * Switch on GCSE. We need it to correctly compute
 829          * the value of a node, which is independent from
 830          * its block.
 831          */
 832         save_optimization_state(&state);
 833         set_opt_global_cse(1);
 834
 835         DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg));
 836
 837         /* allocate block info for all blocks */
 838         irg_walk_blkwise_dom_top_down(irg, NULL, topo_walker, &a_env);
 839
 840         /* clean the exp_gen set. Doing this here saves the cleanup in the iteration. */
 841         for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
 842                 ir_valueset_iterator_t iter;
 843
 844                 foreach_valueset(bl_info->exp_gen, value, expr, iter) {
 845                         if (!is_clean_in_block(expr, bl_info->block, bl_info->exp_gen))
 846                                 ir_valueset_remove_iterator(bl_info->exp_gen, &iter);
 847                 }
 848         }
 849         /* compute the available value sets for all blocks */
 850         dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
 851
 852         /* compute the anticipated value sets for all blocks */
 853         antic_iter = 0;
 854         a_env.first_iter = 1;
 855
 856         /* we use the visited flag to mark non-clean nodes */
 857         inc_irg_visited(irg);
 858         do {
 859                 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
 860                 a_env.changes = 0;
 861                 postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
 862                 a_env.first_iter = 0;
 863                 DB((dbg, LEVEL_1, "------------------------\n"));
 864         } while (a_env.changes != 0);
 865
 866         /* compute redundant expressions */
 867         insert_iter = 0;
 868         a_env.last_idx = get_irg_last_idx(irg);
 869         do {
 870                 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
 871                 a_env.changes = 0;
 872                 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
 873                 DB((dbg, LEVEL_1, "------------------------\n"));
 874         } while (a_env.changes != 0);
 875
 876         /* last step: eliminate nodes */
 877         irg_walk_graph(irg, NULL, eliminate, &a_env);
 878         eliminate_nodes(a_env.pairs);
 879
 880         /* clean up: delete all sets */
 881         for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
 882                 ir_valueset_del(bl_info->exp_gen);
 883                 ir_valueset_del(bl_info->avail_out);
 884                 ir_valueset_del(bl_info->antic_in);
 885                 if (bl_info->new_set)
 886                         ir_valueset_del(bl_info->new_set);
 887         }
 888         ir_nodemap_destroy(&value_map);
 889         obstack_free(&obst, NULL);
 890
 891         /* pin the graph again: This is needed due to the use of set_opt_global_cse(1) */
 892         set_irg_pinned(irg, op_pin_state_pinned);
 893         restore_optimization_state(&state);
 894 }  /* do_gvn_pre */
 895
 896 /* Creates an ir_graph pass for do_gvn_pre. */
 897 ir_graph_pass_t *do_gvn_pre_pass(const char *name)
 898 {
 899         return def_graph_pass(name ? name : "gvn_pre", do_gvn_pre);
 900 }  /* do_gvn_pre_pass */