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