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  * @summary
  27  */
  28 #ifdef HAVE_CONFIG_H
  29 # include "config.h"
  30 #endif
  31
  32 #include "irflag.h"
  33 #include "irdom.h"
  34 #include "irouts.h"
  35 #include "irgopt.h"
  36 #include "irgwalk.h"
  37 #include "ircons.h"
  38 #include "irgmod.h"
  39 #include "valueset.h"
  40 #include "irnodemap.h"
  41 #include "irnodeset.h"
  42 #include "iredges.h"
  43 #include "iropt_dbg.h"
  44 #include "debug.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 entires 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(current_ir_graph, get_nodes_block(v_pred), 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         return get_irn_link(block);
 155 }  /* get_block_info */
 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         block_info *info = obstack_alloc(env->obst, sizeof(*info));
 165
 166         set_irn_link(block, info);
 167         info->exp_gen   = ir_valueset_new(16);
 168         info->avail_out = ir_valueset_new(16);
 169         info->antic_in  = ir_valueset_new(16);
 170         info->new_set   = NULL;
 171         info->avail     = NULL;
 172         info->block     = block;
 173         info->next      = env->list;
 174         env->list       = info;
 175         info->not_found = 0;
 176 }  /* alloc_blk_info */
 177
 178 /**
 179  * Returns non-zero if a node is movable and a possible candidate for PRE.
 180  *
 181  * @param n  the node
 182  */
 183 static int is_nice_value(ir_node *n) {
 184         ir_mode *mode;
 185
 186         while (is_Proj(n))
 187                 n = get_Proj_pred(n);
 188         if (get_irn_pinned(n) == op_pin_state_pinned)
 189                 return 0;
 190         mode = get_irn_mode(n);
 191         if (!mode_is_data(mode)) {
 192                 if (! is_Div(n) && ! is_Mod(n) && ! is_DivMod(n))
 193                         return 0;
 194                 if (! is_NoMem(get_fragile_op_mem(n)))
 195                         return 0;
 196         }
 197         return 1;
 198 }  /* is_nice_value */
 199
 200 #ifdef DEBUG_libfirm
 201 /**
 202  * Dump a value set.
 203  *
 204  * @param set    the set to dump
 205  * @param txt    a text to describe the set
 206  * @param block  the owner block of the set
 207  */
 208 static void dump_value_set(ir_valueset_t *set, char *txt, ir_node *block) {
 209         ir_valueset_iterator_t iter;
 210         ir_node *value, *expr;
 211         int i;
 212
 213         DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
 214         i = 0;
 215         foreach_valueset(set, value, expr, iter) {
 216                 if ((i & 3) == 3)
 217                         DB((dbg, LEVEL_2, "\n"));
 218                 if (value != expr)
 219                         DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
 220                 else
 221                         DB((dbg, LEVEL_2, " %+F,", expr));
 222                 ++i;
 223         }
 224         DB((dbg, LEVEL_2, "\n}\n"));
 225 }  /* dump_value_set */
 226
 227 #else
 228 #define dump_value_set(set, txt, block)
 229 #endif /* DEBUG_libfirm */
 230
 231 /**
 232  * Topological walker. Allocates block info for every block and place nodes in topological
 233  * order into the nodes set.
 234  */
 235 static void topo_walker(ir_node *irn, void *ctx) {
 236         pre_env    *env = ctx;
 237         ir_node    *block;
 238         block_info *info;
 239         ir_node    *value;
 240
 241         if (is_Block(irn)) {
 242                 /* the topological walker ensures that blocks are visited before anything else */
 243                 alloc_blk_info(irn, env);
 244                 return;
 245         }
 246         /* GVN step: remember the value */
 247         value = add(irn, irn);
 248
 249         /* no need to put constants into the sets: they are always redundant */
 250         if (! is_nice_value(irn) || is_irn_constlike(irn))
 251                 return;
 252
 253         /* Do not put mode_T nodes info the sets, or PhiT will be created
 254           (which are not allowed in Firm). Instead, put the Proj's here only. */
 255         if (get_irn_mode(irn) == mode_T)
 256                 return;
 257
 258         /* place this node into the set of possible nodes of its block */
 259         block = get_nodes_block(irn);
 260         info  = get_block_info(block);
 261
 262         ir_valueset_insert(info->exp_gen, value, irn);
 263 }  /* topo_walker */
 264
 265 /**
 266  * Computes Avail_out(block):
 267  *
 268  * Avail_in(block)  = Avail_out(dom(block))
 269  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
 270  *
 271  * Precondition:
 272  *  This function must be called in the top-down dominance order:
 273  *  Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
 274  *
 275  * @param block   the block
 276  * @param ctx     walker context
 277  */
 278 static void compute_avail_top_down(ir_node *block, void *ctx)
 279 {
 280         pre_env    *env = ctx;
 281         block_info *dom_info;
 282         block_info *info = get_block_info(block);
 283         ir_node    *dom_blk;
 284
 285         /* we don't need the end block Avail */
 286         if (block == env->end_block)
 287                 return;
 288
 289         /*
 290          * First add all nodes from the dominator.
 291          * This must be done to ensure that Antic_out contains the leader
 292          * for every node. The root has no dominator.
 293          */
 294         if (block != env->start_block) {
 295                 dom_blk = get_Block_idom(block);
 296                 assert(is_Block(dom_blk));
 297
 298                 dom_info = get_block_info(dom_blk);
 299                 assert(dom_info);
 300
 301                 value_union(info->avail_out, dom_info->avail_out);
 302         }
 303         value_union(info->avail_out, info->exp_gen);
 304
 305         dump_value_set(info->avail_out, "Avail_out", block);
 306 }  /* compute_avail_top_down */
 307
 308 /**
 309  * check if a node n is clean in block block.
 310  *
 311  * @param n      the node
 312  * @param block  the block
 313  * @param set    a value set, containing the already processed predecessors
 314  */
 315 static int is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *set) {
 316         int i;
 317
 318         if (is_Phi(n))
 319                 return 1;
 320
 321         if (! is_nice_value(n))
 322                 return 0;
 323
 324         for (i = get_irn_arity(n) - 1; i >= 0; --i) {
 325                 ir_node *pred = get_irn_n(n, i);
 326                 ir_node *value;
 327
 328                 if (get_nodes_block(pred) != block)
 329                         continue;
 330
 331                 if (is_Phi(pred))
 332                         continue;
 333
 334                 if (! is_nice_value(pred))
 335                         return 0;
 336
 337                 value = lookup(pred);
 338                 if (! value)
 339                         return 0;
 340                 if (! ir_valueset_lookup(set, value))
 341                         return 0;
 342         }
 343         return 1;
 344 }  /* is_clean_in_block */
 345
 346 /**
 347  * Implements phi_translate. Translate a expression above a Phi.
 348  *
 349  * @param node        the node
 350  * @param block       the block in which the node is translated
 351  * @param pos         the input number of the destination block
 352  * @param translated  the valueset containing the other already translated nodes
 353  *
 354  * @return a node representing the translated value
 355  */
 356 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *translated)
 357 {
 358         ir_node        *nn;
 359         int            i, arity;
 360
 361         if (is_Phi(node)) {
 362                 if (get_nodes_block(node) == block) {
 363                         /* a Phi inside our block */
 364                         return get_Phi_pred(node, pos);
 365                 }
 366                 /* already outside */
 367                 return node;
 368         }
 369
 370         arity = get_irn_intra_arity(node);
 371
 372         /* check if the node has at least one Phi predecessor */
 373         for (i = 0; i < arity; ++i) {
 374                 ir_node *pred    = get_irn_intra_n(node, i);
 375                 ir_node *leader  = lookup(pred);
 376                 ir_node *trans;
 377
 378                 leader = leader != NULL ? leader : pred;
 379                 trans  = ir_valueset_lookup(translated, leader);
 380
 381                 if ((trans != NULL && trans != leader) || (is_Phi(leader) && get_nodes_block(leader) == block))
 382                         break;
 383         }
 384         if (i >= arity) {
 385                 /* no translation needed */
 386                 return node;
 387         }
 388
 389         nn = new_ir_node(
 390                 get_irn_dbg_info(node),
 391                 current_ir_graph,
 392                 NULL,
 393                 get_irn_op(node),
 394                 get_irn_mode(node),
 395                 arity,
 396                 get_irn_in(node));
 397         /* We need the attribute copy here, because the Hash value of a
 398            node might depend on that. */
 399         copy_node_attr(node, nn);
 400
 401         set_nodes_block(nn, get_nodes_block(node));
 402         for (i = 0; i < arity; ++i) {
 403                 ir_node *pred    = get_irn_intra_n(node, i);
 404                 ir_node *leader  = lookup(pred);
 405                 ir_node *trans;
 406
 407                 leader = leader != NULL ? leader : pred;
 408                 trans  = ir_valueset_lookup(translated, leader);
 409                 if (trans == NULL)
 410                         trans = leader;
 411
 412                 if (is_Phi(trans) && get_nodes_block(trans) == block)
 413                         set_irn_n(nn, i, get_Phi_pred(trans, pos));
 414                 else
 415                         set_irn_n(nn, i, trans);
 416         }
 417         nn = optimize_node(nn);
 418         return nn;
 419 }  /* phi_translate */
 420
 421 /**
 422  * Block-walker, computes Antic_in(block).
 423  *
 424  * @param block  the block
 425  * @param ctx    the walker environment
 426  */
 427 static void compute_antic(ir_node *block, void *ctx) {
 428         pre_env    *env = ctx;
 429         block_info *succ_info;
 430         block_info *info = get_block_info(block);
 431         ir_node    *succ, *value, *expr;
 432         size_t     size;
 433         ir_valueset_iterator_t  iter;
 434
 435         /* no need for computations in start block */
 436         if (block == env->start_block)
 437                 return;
 438
 439         size = ir_valueset_size(info->antic_in);
 440
 441         /* the end block has no successor */
 442         if (block != env->end_block) {
 443                 int n_succ;
 444
 445                 /*
 446                  * This step puts all generated expression from the current
 447                  * current block into Antic_in.
 448                  * It is enough to do this in the first iteration only, because
 449                  * the set info->exp_gen is not changed anymore.
 450                  */
 451                 if (env->first_iter) {
 452                         foreach_valueset(info->exp_gen, value, expr, iter) {
 453                                 ir_valueset_insert(info->antic_in, value, expr);
 454                         }
 455                 }
 456
 457                 n_succ = get_Block_n_cfg_outs(block);
 458                 if (n_succ == 1) {
 459                         int i, pos = -1;
 460
 461                         /* find blocks position in succ's block predecessors */
 462                         succ = get_Block_cfg_out(block, 0);
 463                         for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
 464                                 if (get_Block_cfgpred_block(succ, i) == block) {
 465                                         pos = i;
 466                                         break;
 467                                 }
 468                         }
 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 = ctx;
 540         ir_node    *value, *expr, *idom, *first_s, *worklist;
 541         block_info *curr_info, *idom_info;
 542         int        pos, arity = get_irn_intra_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         worklist = NULL;
 575         foreach_valueset(curr_info->antic_in, value, expr, iter) {
 576                 ir_mode *mode;
 577
 578                 /* If the value was already computed in the dominator, then
 579                    it is totally redundant.  Hence we have nothing to insert. */
 580                 if (ir_valueset_lookup(idom_info->avail_out, value)) {
 581                         //      DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
 582                         continue;
 583                 }
 584
 585                 by_some  = 0;
 586                 all_same = 1;
 587                 first_s  = NULL;
 588                 mode     = NULL;
 589
 590                 /* for all predecessor blocks */
 591                 for (pos = 0; pos < arity; ++pos) {
 592                         block_info *pred_info;
 593                         ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 594                         ir_node *e_prime, *v_prime, *e_dprime;
 595
 596                         /* ignore bad blocks. */
 597                         if (is_Bad(pred_blk))
 598                                 continue;
 599
 600                         e_prime = phi_translate(expr, block, pos, curr_info->avail_out);
 601                         v_prime = lookup(e_prime);
 602                         if (v_prime == NULL)
 603                                 v_prime = value;
 604
 605                         pred_info = get_block_info(pred_blk);
 606                         e_dprime  = ir_valueset_lookup(pred_info->avail_out, v_prime);
 607
 608                         if (e_dprime == NULL) {
 609                                 pred_info->avail     = e_prime;
 610                                 pred_info->not_found = 1;
 611                                 all_same = 0;
 612                         } else {
 613                                 pred_info->avail     = e_dprime;
 614                                 pred_info->not_found = 0;
 615                                 mode     = get_irn_mode(e_dprime);
 616                                 e_dprime = e_dprime;
 617                                 by_some  = 1;
 618                                 if (first_s == NULL)
 619                                         first_s = e_dprime;
 620                                 else if (first_s != e_dprime)
 621                                         all_same = 0;
 622
 623                                 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, e_dprime, pred_blk));
 624                         }  /* if */
 625                 }  /* for */
 626
 627                 /* If it's not the same value already existing along every predecessor, and
 628                    it's defined by some predecessor, it is partially redundant. */
 629                 if (! all_same && by_some) {
 630                         ir_node *phi, *l, **in;
 631
 632                         DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block));
 633
 634                         in = XMALLOCN(ir_node*, arity);
 635                         /* for all predecessor blocks */
 636                         for (pos = 0; pos < arity; ++pos) {
 637                                 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 638                                 block_info *pred_info = get_block_info(pred_blk);
 639
 640                                 /* ignore bad blocks. */
 641                                 if (is_Bad(pred_blk)) {
 642                                         in[pos] = new_Bad();
 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(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(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(current_ir_graph, 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         pre_env *env = ctx;
 718
 719         if (is_no_Block(irn)) {
 720                 ir_node *block = get_nodes_block(irn);
 721                 block_info *bl = get_block_info(block);
 722                 ir_node *value = lookup(irn);
 723
 724                 if (value != NULL) {
 725                         ir_node *expr = ir_valueset_lookup(bl->avail_out, value);
 726
 727                         if (expr != NULL && expr != irn) {
 728                                 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
 729
 730                                 p->old_node = irn;
 731                                 p->new_node = expr;
 732                                 p->next     = env->pairs;
 733                                 p->reason   = get_irn_idx(expr) >= env->last_idx ? FS_OPT_GVN_PARTLY : FS_OPT_GVN_FULLY;
 734                                 env->pairs  = p;
 735                         }
 736                 }
 737         }
 738 }  /* eliminate */
 739
 740 /**
 741  * Do all the recorded changes and optimize
 742  * newly created Phi's.
 743  *
 744  * @param pairs  list of elimination pairs
 745  */
 746 static void eliminate_nodes(elim_pair *pairs) {
 747         elim_pair *p;
 748
 749         for (p = pairs; p != NULL; p = p->next) {
 750                 /* might be already changed */
 751                 p->new_node = skip_Id(p->new_node);
 752
 753                 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
 754                 /*
 755                  * PRE tends to create Phi(self, self, ... , x, self, self, ...)
 756                  * which we can optimize here
 757                  */
 758                 if (is_Phi(p->new_node)) {
 759                         int i;
 760                         ir_node *res = NULL;
 761
 762                         for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
 763                                 ir_node *pred = get_irn_n(p->new_node, i);
 764
 765                                 if (pred != p->old_node) {
 766                                         if (res) {
 767                                                 res = NULL;
 768                                                 break;
 769                                         }
 770                                         res = pred;
 771                                 }
 772                         }
 773                         if (res) {
 774                                 exchange(p->new_node, res);
 775                                 p->new_node = res;
 776                         }
 777                 }
 778                 DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
 779                 exchange(p->old_node, p->new_node);
 780         }
 781 }  /* eliminate_nodes */
 782
 783 /*
 784  * Argh: Endless loops cause problems, because the
 785  * insert algorithm did not terminate. We get translated nodes that
 786  * references the origin. These nodes are translated again and again...
 787  *
 788  * The current fix is to use post-dominance. This simple ignores
 789  * endless loops, ie we cannot optimize them.
 790  */
 791 void do_gvn_pre(ir_graph *irg)
 792 {
 793         struct obstack       obst;
 794         pre_env              a_env;
 795         optimization_state_t state;
 796         block_info           *bl_info;
 797         unsigned             antic_iter, insert_iter;
 798         ir_node              *value, *expr;
 799
 800         /* register a debug mask */
 801         FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
 802         firm_dbg_set_mask(dbg, 3);
 803
 804         /* edges will crash if enabled due to our allocate on other obstack trick */
 805         edges_deactivate(irg);
 806
 807         value_table = new_identities();
 808         ir_nodemap_init(&value_map);
 809
 810         obstack_init(&obst);
 811         a_env.obst        = &obst;
 812         a_env.list        = NULL;
 813         a_env.start_block = get_irg_start_block(irg);
 814         a_env.end_block   = get_irg_end_block(irg);
 815         a_env.pairs       = NULL;
 816
 817         /* Move Proj's into the same block as their args,
 818            else we would assign the result to wrong blocks */
 819         normalize_proj_nodes(irg);
 820
 821         /* critical edges MUST be removed */
 822         remove_critical_cf_edges(irg);
 823
 824         /* we need dominator for Antic_out calculation */
 825         assure_doms(irg);
 826         assure_postdoms(irg);
 827         /* we get all nodes of a block by following outs */
 828         assure_irg_outs(irg);
 829
 830         /*
 831          * Switch on GCSE. We need it to correctly compute
 832          * the value of a node, which is independent from
 833          * its block.
 834          */
 835         save_optimization_state(&state);
 836         set_opt_global_cse(1);
 837
 838         DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg));
 839
 840         /* allocate block info for all blocks */
 841         irg_walk_blkwise_dom_top_down(irg, NULL, topo_walker, &a_env);
 842
 843         /* clean the exp_gen set. Doing this here saves the cleanup in the iteration. */
 844         for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
 845                 ir_valueset_iterator_t iter;
 846
 847                 foreach_valueset(bl_info->exp_gen, value, expr, iter) {
 848                         if (!is_clean_in_block(expr, bl_info->block, bl_info->exp_gen))
 849                                 ir_valueset_remove_iterator(bl_info->exp_gen, &iter);
 850                 }
 851         }
 852         /* compute the available value sets for all blocks */
 853         dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
 854
 855         /* compute the anticipated value sets for all blocks */
 856         antic_iter = 0;
 857         a_env.first_iter = 1;
 858
 859         /* we use the visited flag to mark non-clean nodes */
 860         inc_irg_visited(irg);
 861         do {
 862                 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
 863                 a_env.changes = 0;
 864                 postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
 865                 a_env.first_iter = 0;
 866                 DB((dbg, LEVEL_1, "------------------------\n"));
 867         } while (a_env.changes != 0);
 868
 869         /* compute redundant expressions */
 870         insert_iter = 0;
 871         a_env.last_idx = get_irg_last_idx(irg);
 872         do {
 873                 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
 874                 a_env.changes = 0;
 875                 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
 876                 DB((dbg, LEVEL_1, "------------------------\n"));
 877         } while (a_env.changes != 0);
 878
 879         /* last step: eliminate nodes */
 880         irg_walk_graph(irg, NULL, eliminate, &a_env);
 881         eliminate_nodes(a_env.pairs);
 882
 883         /* clean up: delete all sets */
 884         for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
 885                 ir_valueset_del(bl_info->exp_gen);
 886                 ir_valueset_del(bl_info->avail_out);
 887                 ir_valueset_del(bl_info->antic_in);
 888                 if (bl_info->new_set)
 889                         ir_valueset_del(bl_info->new_set);
 890         }
 891         del_identities(value_table);
 892         ir_nodemap_destroy(&value_map);
 893         obstack_free(&obst, NULL);
 894         value_table = NULL;
 895
 896         /* pin the graph again: This is needed due to the use of set_opt_global_cse(1) */
 897         set_irg_pinned(irg, op_pin_state_pinned);
 898         restore_optimization_state(&state);
 899
 900         if (a_env.pairs) {
 901                 set_irg_outs_inconsistent(irg);
 902                 set_irg_loopinfo_inconsistent(irg);
 903         }
 904 }  /* do_gvn_pre */