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