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  * @brief
  26  */
  27 #include "config.h"
  28
  29 #include "debug.h"
  30 #include "ircons.h"
  31 #include "irdom.h"
  32 #include "iredges.h"
  33 #include "irflag.h"
  34 #include "irgmod.h"
  35 #include "irgopt.h"
  36 #include "irgwalk.h"
  37 #include "irnodehashmap.h"
  38 #include "irnodeset.h"
  39 #include "iropt_dbg.h"
  40 #include "iroptimize.h"
  41 #include "irouts.h"
  42 #include "irpass.h"
  43 #include "valueset.h"
  44 #include "irloop.h"
  45
  46 #include "irgraph_t.h"
  47 #include "irnode_t.h"
  48 #include "iropt_t.h"
  49 #include "plist.h"
  50
  51 /* suggested by GVN-PRE authors */
  52 #define MAX_ANTIC_ITER 10
  53 #define MAX_INSERT_ITER 3
  54
  55 /* Infinite loops will be unrolled during antic iteration and
  56    will iterate until otherwise stopped.
  57    This also leaves every possible values of iteration variables in antic_in.
  58 */
  59 #define NO_INF_LOOPS 0
  60
  61 /* Attempt to reduce register pressure and reduce code size
  62    for hoisted nodes. */
  63 #define HOIST_HIGH 0
  64 #define COMMON_DOM 1
  65
  66 /* Seamless implementation of handling loads and generally memory
  67    dependent nodes with GVN-PRE. */
  68 #define LOADS 0
  69 #define DIVMODS 0
  70
  71 /* Experimental */
  72 #define MIN_CUT 0
  73
  74 #define OLD_DIVMODS 0
  75 #define NO_INF_LOOPS2 0
  76
  77 /* NIY Choose to be optimized nodes in a more sophisticated way
  78    to reduce number of newly introduced phi nodes. */
  79 #define BETTER_GREED 0
  80
  81
  82 /** Additional info we need for every block. */
  83 typedef struct block_info {
  84         ir_valueset_t     *exp_gen;    /* contains this blocks clean expressions */
  85         ir_valueset_t     *avail_out;  /* available values at block end */
  86         ir_valueset_t     *antic_in;   /* clean anticipated values at block entry */
  87         ir_valueset_t     *antic_done; /* keeps elements of antic_in after insert nodes phase */
  88         ir_valueset_t     *new_set;    /* new by hoisting made available values */
  89         ir_nodehashmap_t  *trans;      /* contains translated nodes translated into block */
  90         ir_node           *avail;      /* saves available node for insert node phase */
  91         int                found;      /* saves kind of availability for insert_node phase */
  92         ir_node           *block;      /* block of the block_info */
  93         struct block_info *next;       /* links all instances for easy access */
  94 } block_info;
  95
  96 /**
  97  * A pair of nodes to be exchanged.
  98  * We have to defer the exchange because there are still needed references
  99  * to certain nodes.
 100  */
 101 typedef struct elim_pair {
 102         ir_node *old_node;      /* node that will be replaced */
 103         ir_node *new_node;      /* replacement for old_node */
 104         struct elim_pair *next; /* links all instances for easy access */
 105         int     reason;         /* reason for the replacement */
 106 } elim_pair;
 107
 108 /** environment for the GVN-PRE algorithm */
 109 typedef struct pre_env {
 110         ir_graph       *graph;        /* current graph */
 111         struct obstack *obst;         /* obstack to allocate on */
 112         ir_node        *start_block;  /* start block of the current graph */
 113         ir_node        *end_block;    /* end block of the current graph */
 114         ir_node        *end_node;     /* end node of the current graph */
 115         block_info     *list;         /* block_info list head */
 116         elim_pair      *pairs;        /* elim_pair list head */
 117         ir_nodeset_t   *keeps;        /* a list of to be removed phis to kill their keep alive edges */
 118         unsigned        last_idx;     /* last node index of input graph */
 119         char            changes;      /* flag for fixed point iterations - non-zero if changes occurred */
 120         char            first_iter;   /* non-zero for first fixed point iteration */
 121         int             iteration;    /* iteration counter */
 122 } pre_env;
 123
 124 static pre_env *environ;
 125
 126 /* custom GVN value map */
 127 static ir_nodehashmap_t value_map;
 128
 129 /* debug module handle */
 130 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 131
 132 #ifdef DEBUG_libfirm
 133
 134 /* --------------------------------------------------------
 135  * Statistics
 136  * --------------------------------------------------------
 137  */
 138
 139 typedef struct gvnpre_statistics {
 140         int replaced;
 141         int partially;
 142         int fully;
 143         int loads;
 144         int divmods;
 145         int hoist_high;
 146         int first_iter_found;
 147         int antic_iterations;
 148         int insert_iterations;
 149         int infinite_loops;
 150 } gvnpre_statistics;
 151
 152 gvnpre_statistics *gvnpre_stats = NULL;
 153
 154 static void init_stats()
 155 {
 156         gvnpre_stats = XMALLOCZ(gvnpre_statistics);
 157 }
 158
 159 static void free_stats()
 160 {
 161         free(gvnpre_stats);
 162         gvnpre_stats = NULL;
 163 }
 164
 165 static void print_stats()
 166 {
 167         gvnpre_statistics *stats = gvnpre_stats;
 168         DB((dbg, LEVEL_1, "replaced             : %d\n", stats->replaced));
 169         DB((dbg, LEVEL_1, "antic_in iterations  : %d\n", stats->antic_iterations));
 170         DB((dbg, LEVEL_1, "insert iterations    : %d\n", stats->insert_iterations));
 171         DB((dbg, LEVEL_1, "infinite loops       : %d\n", stats->infinite_loops));
 172         DB((dbg, LEVEL_1, "fully redundant      : %d\n", stats->fully));
 173         DB((dbg, LEVEL_1, "partially redundant  : %d\n", stats->partially));
 174         DB((dbg, LEVEL_1, "  loads                : %d\n", stats->loads));
 175         DB((dbg, LEVEL_1, "  Divs/Mods            : %d\n", stats->divmods));
 176         DB((dbg, LEVEL_1, "  hoist high           : %d\n", stats->hoist_high));
 177         DB((dbg, LEVEL_1, "  first iteration      : %d\n", stats->first_iter_found));
 178 }
 179
 180 #define set_stats(var, value) (var)=(value)
 181 #define inc_stats(var)        ((var)+=1)
 182
 183 /* --------------------------------------------------------
 184  * Dump valuesets
 185  * --------------------------------------------------------
 186  */
 187
 188 /**
 189  * Dump a value set.
 190  *
 191  * @param set    the set to dump
 192  * @param txt    a text to describe the set
 193  * @param block  the owner block of the set
 194  */
 195 static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
 196 {
 197         ir_valueset_iterator_t iter;
 198         ir_node *value, *expr;
 199         int i;
 200
 201         DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
 202         i = 0;
 203         foreach_valueset(set, value, expr, iter) {
 204                 if ((i & 3) == 3)
 205                         DB((dbg, LEVEL_2, "\n"));
 206                 if (value != expr)
 207                         DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
 208                 else
 209                         DB((dbg, LEVEL_2, " %+F,", expr));
 210                 ++i;
 211         }
 212         DB((dbg, LEVEL_2, "\n}\n"));
 213 }  /* dump_value_set */
 214
 215 /**
 216  * Dump all exp_gen value sets.
 217  *
 218  * @param list  the list of block infos to retrieve the sets from
 219  */
 220 static void dump_all_expgen_sets(block_info *list)
 221 {
 222         block_info *block_info;
 223
 224         for (block_info = list; block_info != NULL; block_info = block_info->next) {
 225                 dump_value_set(block_info->exp_gen, "[Exp_gen]", block_info->block);
 226         }
 227 }
 228
 229 #else
 230
 231 #define dump_all_expgen_sets(list)
 232 #define dump_value_set(set, txt, block)
 233
 234 #endif /* DEBUG_libfirm */
 235
 236 /* --------------------------------------------------------
 237  * GVN Functions
 238  * --------------------------------------------------------
 239  */
 240
 241 /**
 242  * Compares node collisions in valuetable.
 243  * Modified identities_cmp().
 244  */
 245 static int compare_gvn_identities(const void *elt, const void *key)
 246 {
 247         ir_node *a = (ir_node *)elt;
 248         ir_node *b = (ir_node *)key;
 249         int i, irn_arity_a;
 250
 251         if (a == b) return 0;
 252
 253         /* phi nodes kill predecessor values and are always different */
 254         if (is_Phi(a) || is_Phi(b))
 255                 return 1;
 256
 257         /* memops are not the same, even if we want to optimize them
 258            we have to take the order in account */
 259         if (is_memop(a) || is_memop(b)) {
 260                 /* Loads with the same predecessors are the same value;
 261                    this should only happen after phi translation. */
 262                 if (! is_Load(a) || ! is_Load(b))
 263                         return 1;
 264         }
 265
 266         if ((get_irn_op(a) != get_irn_op(b)) ||
 267             (get_irn_mode(a) != get_irn_mode(b))) return 1;
 268
 269         /* compare if a's in and b's in are of equal length */
 270         irn_arity_a = get_irn_arity(a);
 271         if (irn_arity_a != get_irn_arity(b))
 272                 return 1;
 273
 274         /* blocks are never the same */
 275         if (is_Block(a) || is_Block(b))
 276                 return 1;
 277
 278         /* should only be used with gcse enabled */
 279         assert(get_opt_global_cse());
 280
 281         /* compare a->in[0..ins] with b->in[0..ins] */
 282         for (i = 0; i < irn_arity_a; ++i) {
 283                 ir_node *pred_a = get_irn_n(a, i);
 284                 ir_node *pred_b = get_irn_n(b, i);
 285                 if (pred_a != pred_b) {
 286                         if (!is_irn_cse_neutral(pred_a) || !is_irn_cse_neutral(pred_b))
 287                                 return 1;
 288                 }
 289         }
 290
 291         /*
 292          * here, we already now that the nodes are identical except their
 293          * attributes
 294          */
 295         if (a->op->ops.node_cmp_attr)
 296                 return a->op->ops.node_cmp_attr(a, b);
 297
 298         return 0;
 299 }
 300
 301 /**
 302  * Identify does a lookup in the GVN valuetable.
 303  * To be used when no new GVN values are to be created.
 304  *
 305  * @param e  a node representing an expression
 306  * @return a node representing the value
 307  */
 308 static ir_node *identify(ir_node *irn)
 309 {
 310         ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
 311         if (value)
 312                 return value;
 313         /* irn represents a new value, so return the leader */
 314         return identify_remember(irn);
 315 }
 316
 317 /**
 318  * remember() adds node irn to the GVN valuetable.
 319  * Identify_remember only identifies values of nodes with the
 320  * same predecessor nodes (not values). By creating a node from the predecessor
 321  * values/leaders, a true valuetree is built. Phis kill their predecessor value,
 322  * so no circular dependencies need to be resolved.
 323  *
 324  * TODO Improvement:
 325  *      Maybe this could be implemented with a custom node hash that takes
 326  *      phi nodes and true values (instead of predecessors) into account,
 327  *      resulting in value numbers.
 328  * TODO This unnecessarily also handles nodes like calls, which are never equal.
 329  *
 330  * @param irn  a node representing an expression
 331  * @return     the value of the expression
 332  */
 333 static ir_node *remember(ir_node *irn)
 334 {
 335         int       arity   = get_irn_arity(irn);
 336         int       i;
 337         int       changed = 0;
 338         ir_node **in      = XMALLOCN(ir_node *, arity);
 339         ir_node  *value;
 340
 341         for (i = 0; i < arity; ++i) {
 342                 ir_node *pred       = get_irn_n(irn, i);
 343                 /* value and leader at the same time */
 344                 ir_node *pred_value = identify(pred);
 345
 346                 /* phi will be translated anyway, so kill the predecessor values
 347                    this also prevents circular dependencies */
 348                 if (is_Phi(pred)) {
 349                         /* every phi represents its own value */
 350                         in[i] = pred;
 351                         continue;
 352                 }
 353
 354                 /* predecessor is not its value representation/the leader */
 355                 if (pred != pred_value)
 356                         changed = 1;
 357                 in[i] = pred_value;
 358         }
 359
 360         if (changed) {
 361                 /* create representative for */
 362                 ir_node *nn = new_ir_node(
 363                         get_irn_dbg_info(irn),
 364                         get_irn_irg(irn),
 365                         get_nodes_block(irn),
 366                         get_irn_op(irn),
 367                         get_irn_mode(irn),
 368                         get_irn_arity(irn),
 369                         in);
 370                 copy_node_attr(environ->graph, irn, nn);
 371
 372                 /* now the value can be determined because the
 373                    predecessors are the leaders */
 374                 value = identify_remember(nn);
 375         } else {
 376                 value = identify_remember(irn);
 377         }
 378         free(in);
 379
 380         DB((dbg, LEVEL_4, "Remember %+F as value %+F\n", irn, value));
 381         ir_nodehashmap_insert(&value_map, irn, value);
 382
 383         return value;
 384 }
 385
 386 /**
 387  * When the value map has been built we may lookup expressions
 388  * and remember them if new.
 389  */
 390 static ir_node *identify_or_remember(ir_node *irn)
 391 {
 392         ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
 393         if (value)
 394                 return value;
 395         else
 396                 return remember(irn);
 397 }
 398
 399 /* --------------------------------------------------------
 400  * Block info
 401  * --------------------------------------------------------
 402  */
 403
 404 /**
 405  * Allocate block info for block block.
 406  *
 407  * @param block   the block
 408  * @param env     the environment
 409  */
 410 static void alloc_block_info(ir_node *block, pre_env *env)
 411 {
 412         block_info *info = OALLOC(env->obst, block_info);
 413
 414         set_irn_link(block, info);
 415         info->exp_gen    = ir_valueset_new(16);
 416         info->avail_out  = ir_valueset_new(16);
 417         info->antic_in   = ir_valueset_new(16);
 418         info->antic_done = ir_valueset_new(16);
 419         info->trans = XMALLOC(ir_nodehashmap_t);
 420         ir_nodehashmap_init(info->trans);
 421
 422         info->new_set = NULL;
 423         info->avail   = NULL;
 424         info->block   = block;
 425         info->found   = 1;
 426
 427         info->next = env->list;
 428         env->list  = info;
 429 }  /* alloc_block_info */
 430
 431 static void free_block_info(block_info *block_info)
 432 {
 433         ir_valueset_del(block_info->exp_gen);
 434         ir_valueset_del(block_info->avail_out);
 435         ir_valueset_del(block_info->antic_in);
 436         if (block_info->trans) {
 437                 ir_nodehashmap_destroy(block_info->trans);
 438                 free(block_info->trans);
 439         }
 440         if (block_info->new_set)
 441                 ir_valueset_del(block_info->new_set);
 442 }
 443
 444 /**
 445  * Bottom up walker that ensures that every block gets a block info.
 446  *
 447  * @param irn   the node
 448  * @param ctx   the environment
 449  */
 450 static void block_info_walker(ir_node *irn, void *ctx)
 451 {
 452         if (is_Block(irn)) {
 453                 pre_env *env = (pre_env*)ctx;
 454                 alloc_block_info(irn, env);
 455         }
 456 }
 457
 458 /**
 459  * Returns the block info of a block.
 460  */
 461 static block_info *get_block_info(ir_node *block)
 462 {
 463         return (block_info*)get_irn_link(block);
 464 }
 465
 466 /* --------------------------------------------------------
 467  * Infinite loop analysis
 468  * --------------------------------------------------------
 469  */
 470
 471 /**
 472  * Walker to set block marks and loop links to 0.
 473  */
 474 static void clear_block_mark_loop_link(ir_node *block, void *env)
 475 {
 476         (void) env;
 477
 478         if (is_Block(block)) {
 479                 set_Block_mark(block, 0);
 480                 set_loop_link(get_irn_loop(block), NULL);
 481         }
 482 }
 483
 484 /**
 485  * Returns non-zero if block is part of real loop loop.
 486  */
 487
 488 static unsigned in_loop(ir_node *block, ir_loop *loop)
 489 {
 490         ir_loop *l     = get_irn_loop(block);
 491         ir_loop *outer = get_irg_loop(environ->graph);
 492
 493         while (l != loop) {
 494                 /* loop tree root is not a loop */
 495                 if (l == NULL || l == outer)
 496                         return 0;
 497                 l = get_loop_outer_loop(l);
 498         }
 499         return 1;
 500 }
 501
 502 /**
 503  * Returns the outermost real loop of loop.
 504  */
 505 static ir_loop *get_loop_outermost(ir_loop *loop)
 506 {
 507         ir_loop *outer = get_irg_loop(environ->graph);
 508         ir_loop *l     = loop;
 509         ir_loop *last  = NULL;
 510
 511         while(l != outer) {
 512                 last = l;
 513                 l = get_loop_outer_loop(l);
 514         }
 515         return last;
 516 }
 517
 518 /**
 519  * Topologic bottom-up walker sets links of infinite loops to non-zero.
 520  * Block marks are used to flag blocks reachable (from end) on the one hand,
 521  * on the other hand they are set if the block is not part of an infinite loop.
 522  */
 523 static void infinite_loop_walker(ir_node *block, void *env)
 524 {
 525         int arity;
 526         int i;
 527         (void) env;
 528
 529         if (! is_Block(block))
 530                 return;
 531
 532         /* start block has no predecessors */
 533         if (block == environ->start_block)
 534                 return;
 535
 536         arity = get_irn_arity(block);
 537
 538         /* block not part of a real loop: no infinite loop */
 539         if (get_irn_loop(block) == get_irg_loop(environ->graph))
 540                 set_Block_mark(block, 1);
 541
 542         if (get_Block_mark(block)) {
 543                 /* reachable block: mark all cf predecessors */
 544                 for (i = 0; i < arity; ++i) {
 545                         ir_node *pred = get_Block_cfgpred_block(block, i);
 546                         if (is_Bad(pred))
 547                                 continue;
 548                         set_Block_mark(pred, 1);
 549                 }
 550         } else {
 551                 /* We are in a real loop and see an unreachable block. */
 552                 ir_loop *outermost_loop = get_loop_outermost(get_irn_loop(block));
 553
 554                 /* flag loop as infinite */
 555                 set_loop_link(outermost_loop, outermost_loop);
 556                 DEBUG_ONLY(inc_stats(gvnpre_stats->infinite_loops);)
 557
 558                 /* The cf predecessors are unreachable, but can never be part of
 559                    an infinite loop, because we just reached them. So we set the
 560                    blockmark to prevent triggering the infinite loop detection. */
 561
 562                 /* passing information to the cf predecessors */
 563                 for (i = 0; i < arity; ++i) {
 564                         ir_node *pred = get_Block_cfgpred_block(block, i);
 565
 566                         if (is_Bad(pred))
 567                                 continue;
 568
 569                         /* If our cf predecessor is in the same endless loop,
 570                            it is also unreachable. */
 571                         if (in_loop(pred, outermost_loop)) {
 572                                 set_Block_mark(pred, 0);
 573                         } else {
 574                                 /* When we leave the unreachable loop, we artificially
 575                                    declare the cf predecessor reachable. */
 576                                 set_Block_mark(pred, 1);
 577                         }
 578                 }
 579         }
 580 }
 581
 582 /**
 583  * Sets loop links of outermost infinite loops to non-zero.
 584  */
 585 static void analyse_loops(ir_graph *irg)
 586 {
 587         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
 588
 589         /* reset block mark and loop links */
 590         irg_walk_blkwise_graph(irg, clear_block_mark_loop_link, NULL, NULL);
 591
 592         /* mark end block reachable */
 593         set_Block_mark(get_irg_end_block(irg), 1);
 594         irg_walk_blkwise_graph(irg, infinite_loop_walker, NULL, NULL);
 595
 596         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
 597 }
 598
 599 #if NO_INF_LOOPS || NO_INF_LOOPS2
 600 /**
 601  * Returns non-zero if block is part of an infinite loop.
 602  */
 603 static unsigned is_in_infinite_loop(ir_node *block)
 604 {
 605         ir_loop *loop;
 606
 607         assert(is_Block(block));
 608         loop = get_irn_loop(block);
 609         assert(loop);
 610
 611         loop = get_loop_outermost(loop);
 612         if (loop)
 613                 return (get_loop_link(loop) != NULL);
 614         else
 615                 return 0;
 616 }
 617 #endif
 618
 619 /* --------------------------------------------------------
 620  * GVN-PRE Exp_gen
 621  * --------------------------------------------------------
 622  */
 623
 624 /**
 625  * Returns non-zero if a node is movable and a possible candidate for PRE.
 626  */
 627 static unsigned is_nice_value(ir_node *n)
 628 {
 629         ir_mode *mode = get_irn_mode(n);
 630
 631         if (is_Phi(n))
 632                 return 1;
 633
 634 #if LOADS || OLD_DIVMODS || DIVMODS
 635         if (is_Proj(n) && mode != mode_X && mode != mode_T)
 636                 return 1;
 637 #else
 638         if (is_Proj(n))
 639                 return 0;
 640 #endif
 641
 642 #if LOADS
 643         if (is_Load(n))
 644                 return get_Load_volatility(n) == volatility_non_volatile;
 645 #endif
 646
 647         if (get_irn_pinned(n) == op_pin_state_pinned)
 648                 return 0;
 649
 650         if (! mode_is_data(mode)) {
 651                 if (! is_Div(n) && ! is_Mod(n))
 652                         return 0;
 653         }
 654         return 1;
 655 }
 656
 657 /**
 658  * Checks if a node n is clean in block block for exp_gen.
 659  *
 660  * @param n      the node
 661  * @param block  the block
 662  * @return non-zero value for clean node
 663  */
 664 static unsigned is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *valueset)
 665 {
 666         int         i, arity;
 667
 668         if (is_Phi(n))
 669                 return 1;
 670
 671         if (! is_nice_value(n))
 672                 return 0;
 673
 674 #if LOADS
 675         /* filter loads with no phi predecessor from antic_in */
 676         if (is_Load(n) && ! is_Phi(get_Load_mem(n)))
 677                 return 0;
 678 #endif
 679
 680 #if DIVMODS
 681         if (is_Div(n)) {
 682                 ir_node *mem = get_Div_mem(n);
 683
 684                 mem = skip_Pin(mem);
 685
 686                 if (! is_Phi(mem) && ! is_NoMem(mem))
 687                         return 0;
 688         }
 689
 690         if (is_Mod(n) && ! is_Phi(get_Mod_mem(n)))
 691                 return 0;
 692 #endif
 693
 694         arity = get_irn_arity(n);
 695         for (i = 0; i < arity; ++i) {
 696                 ir_node *pred   = get_irn_n(n, i);
 697                 ir_node *value;
 698
 699                 if (is_Phi(pred))
 700                         continue;
 701
 702                 /* we only handle current block */
 703                 if (get_nodes_block(pred) != block)
 704                         continue;
 705
 706                 if (! is_nice_value(pred))
 707                         return 0;
 708
 709                 value = identify(pred);
 710                 if (! ir_valueset_lookup(valueset, value))
 711                         return 0;
 712
 713         }
 714         return 1;
 715 }
 716
 717 /**
 718  * Topological walker puts nodes in top-down topological order into exp_gen set.
 719  * Assumed to walk blockwise and nodewise topologically top-down.
 720  *
 721  * @param irn    the node
 722  * @param ctx    the environment
 723  */
 724 static void topo_walker(ir_node *irn, void *ctx)
 725 {
 726         ir_node    *block;
 727         block_info *info;
 728         ir_node    *value;
 729         (void) ctx;
 730
 731         if (is_Block(irn))
 732                 return;
 733
 734         /* GVN step: remember the value. */
 735         value = remember(irn);
 736
 737         /* values that are not in antic_in also dont't need to be in any other set */
 738         if (! is_nice_value(irn))
 739                 return;
 740
 741         if (is_irn_constlike(irn))
 742                 return;
 743
 744         block = get_nodes_block(irn);
 745         info  = get_block_info(block);
 746
 747         ir_valueset_insert(info->avail_out, value, irn);
 748
 749         if (is_clean_in_block(irn, block, info->exp_gen)) {
 750                 DB((dbg, LEVEL_3, "%+F clean in block %+F\n", irn, block));
 751
 752                 ir_valueset_insert(info->exp_gen, value, irn);
 753         }
 754 }
 755
 756 /* --------------------------------------------------------
 757  * GVN-PRE Antic_in
 758  * --------------------------------------------------------
 759  */
 760
 761 /**
 762  * Gets result of nodes phi translation into block.
 763  *
 764  * @param node   the node
 765  * @param block  the target block
 766  *
 767  * @return a phi translation of node node into block block or NULL
 768  */
 769 static ir_node *get_translated(ir_node *block, ir_node *node)
 770 {
 771         if (is_irn_constlike(node))
 772                 return node;
 773
 774         return ir_nodehashmap_get(ir_node, get_block_info(block)->trans, node);
 775 }
 776
 777 /**
 778  * Saves result of phi translation of node into predecessor
 779  * at pos of block succ.
 780  *
 781  * @param node   the node
 782  * @param succ   the successor of the translation target block
 783  * @param pos    the position of the predecessor block
 784  * @param trans  the translation result
 785  *
 786  */
 787 static void set_translated(ir_nodehashmap_t *map, ir_node *node, ir_node *trans)
 788 {
 789         if (is_irn_constlike(node))
 790                 return;
 791         /* insert or replace */
 792         ir_nodehashmap_insert(map, node, trans);
 793 }
 794
 795 #if OLD_DIVMODS
 796 /* Helper function to compare the values of pred and avail_pred. */
 797 static unsigned match_pred(ir_node *pred, ir_node *avail_pred, ir_node *block, int pos)
 798 {
 799         ir_node *avail_value = identify(avail_pred);
 800         ir_node *pred_block  = get_Block_cfgpred_block(block, pos);
 801         ir_node *trans_pred  = get_translated(pred_block, pred);
 802         ir_node *value;
 803
 804         if (trans_pred == NULL)
 805                 trans_pred = pred;
 806         value = identify(trans_pred);
 807
 808         DB((dbg, LEVEL_3, "manual compare %+F  %+F\n", pred, avail_pred));
 809
 810         return (value == avail_value);
 811 }
 812
 813 /**
 814  * Does phi translation for redundant Div/Mod nodes only.
 815  * Returns NULL for non-redundant node, which needs to be phi translated.
 816  */
 817 static ir_node *phi_translate_divmod(ir_node *divmod, ir_node *block, int pos)
 818 {
 819         ir_node *mem   = get_memop_mem(divmod);
 820         ir_node *trans = get_translated_pred(block, pos, mem);
 821
 822         if (trans == NULL)
 823                 trans = mem;
 824
 825         /* no partial redundancy if this is a mode_M phi */
 826         if (is_Proj(trans)) {
 827                 /* The last memory operation in predecessor block */
 828                 ir_node *avail_op = get_Proj_pred(trans);
 829
 830                 if (get_irn_op(divmod) == get_irn_op(avail_op)) {
 831                         unsigned left, right;
 832
 833                         if (is_Div(avail_op)) {
 834                                 if (get_Div_resmode(divmod) == get_Div_resmode(avail_op) &&
 835                                     get_Div_no_remainder(divmod) == get_Div_no_remainder(avail_op)) {
 836
 837                                         left  = match_pred(get_Div_left(divmod), get_Div_left(avail_op), block, pos);
 838                                         right = match_pred(get_Div_right(divmod), get_Div_right(avail_op), block, pos);
 839
 840                                         if (left && right)
 841                                                 return avail_op;
 842                                 }
 843                         } else if (is_Mod(avail_op)) {
 844                             if (get_Mod_resmode(divmod) == get_Mod_resmode(avail_op)) {
 845
 846                                         left  = match_pred(get_Mod_left(divmod), get_Mod_left(avail_op), block, pos);
 847                                         right = match_pred(get_Mod_right(divmod), get_Mod_right(avail_op), block, pos);
 848
 849                                         if (left && right)
 850                                                 return avail_op;
 851                                 }
 852                         }
 853                 }
 854         }
 855         return NULL;
 856 }
 857 #endif
 858
 859 /**
 860  * Translates an expression above a Phi.
 861  *
 862  * @param node        the node
 863  * @param block       the block the node is translated into
 864  * @param pos         the input number of the destination block
 865  *
 866  * @return a node representing the translated value
 867  */
 868 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *leaderset)
 869 {
 870         int       i;
 871         int       arity;
 872         ir_node **in;
 873         ir_node  *pred_block = get_Block_cfgpred_block(block, pos);
 874         ir_node  *nn;
 875         unsigned  needed;
 876
 877         if (is_Phi(node)) {
 878                 if (get_nodes_block(node) == block)
 879                         return get_Phi_pred(node, pos);
 880                 /* this phi does not need translation */
 881                 return node;
 882         }
 883         arity = get_irn_arity(node);
 884
 885 #if OLD_DIVMODS
 886         if (is_Div(node) || is_Mod(node)) {
 887                 ir_node *avail_op = phi_translate_divmod(node, block, pos);
 888                 if (avail_op)
 889                         return avail_op;
 890         }
 891 #endif
 892
 893         needed = 0;
 894         in = ALLOCANZ(ir_node *, arity);
 895
 896         /* A value has several representatives. The anti leader is chosen to be
 897            the main representative. If we access a node as representative of a
 898            value we always use the anti leader. The anti leader can be found by
 899            antic_in(identify(node)). */
 900         for (i = 0; i < arity; ++i) {
 901                 ir_node *pred   = get_irn_n(node, i);
 902                 ir_node *value  = identify(pred);
 903                 /* get leader for pred to lookup its translated value */
 904                 ir_node *leader = ir_valueset_lookup(leaderset, value);
 905                 ir_node *pred_trans;
 906                 ir_node *new_pred;
 907
 908                 if (! leader)
 909                         leader = pred;
 910
 911                 /* we cannot find this value in antic_in, because the value
 912                    has (possibly) changed! */
 913                 pred_trans  = get_translated(pred_block, leader);
 914
 915
 916 #if DIVMODS
 917                 if (is_Div(node)) {
 918                         ir_node *mem = get_Div_mem(node);
 919
 920                         mem = skip_Pin(mem);
 921
 922                         if (! is_Phi(mem))
 923                                 pred_trans = get_Div_mem(node);
 924                 }
 925 #endif
 926
 927                 DB((dbg, LEVEL_3, "trans %+F of %+F is  %+F\n", leader, pred_block, pred_trans));
 928                 if (pred_trans == NULL) {
 929                         new_pred = pred;
 930                 } else {
 931                         new_pred = pred_trans;
 932
 933                         /* loads: Predecessor is a memory phi, which translated yields a proj or
 934                            another phi. In case of projection and a load predecessor,
 935                            skip them and use the loads memory. */
 936                         if (is_Proj(pred_trans) && get_irn_mode(pred_trans) == mode_M) {
 937 #if LOADS || DIVMODS
 938                                 ir_node *load = get_Proj_pred(pred_trans);
 939                                 /* If we do not translate this node, we will get its value wrong. */
 940                                 needed |= 1;
 941
 942                                 if (is_Load(load)) {
 943                                         /* Put new load under the adjacent loads memory edge
 944                                            such that GVN may compare them. */
 945                                         new_pred = get_Load_mem(load);
 946                                 }
 947 #endif
 948                         } else {
 949                                 /* predecessor value changed, so translation is needed */
 950                                 if (identify(new_pred) != identify(pred))
 951                                         needed |= 1;
 952                         }
 953                 }
 954
 955                 DB((dbg, LEVEL_4, "in %+F\n", new_pred));
 956                 in[i] = new_pred;
 957         }
 958
 959         if (! needed)
 960                 return node;
 961
 962         DB((dbg, LEVEL_3, "Translate\n"));
 963
 964         if (is_Proj(node))
 965                 pred_block = get_nodes_block(in[0]);
 966
 967         /* copy node to represent the new value.
 968            We do not translate nodes that do not need translation,
 969            so we use the newly created nodes as value representatives only.
 970            Their block is not important, because we create new ones during
 971            the insert node phase. */
 972         nn = new_ir_node(
 973                 get_irn_dbg_info(node),
 974                 environ->graph,
 975                 pred_block,
 976                 get_irn_op(node),
 977                 get_irn_mode(node),
 978                 arity,
 979                 in);
 980         /* We need the attribute copy here, because the Hash value of a
 981            node might depend on it. */
 982         copy_node_attr(environ->graph, node, nn);
 983         /* Optimizing nn here is tempting but might be against the GVN-PRE algorithm
 984            because it already uses availability. */
 985
 986         DB((dbg, LEVEL_3, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
 987         return nn;
 988 }
 989
 990 /**
 991  * Block-walker, computes Antic_in(block).
 992  * Builds a value tree out of the graph by translating values
 993  * over phi nodes.
 994  *
 995  * @param block  the block
 996  * @param ctx    the walker environment
 997  */
 998 static void compute_antic(ir_node *block, void *ctx)
 999 {
1000         pre_env                *env       = (pre_env*)ctx;
1001         block_info             *succ_info;
1002         block_info             *info;
1003         ir_node                *succ;
1004         ir_node                *value;
1005         ir_node                *expr;
1006         size_t                  size;
1007         ir_valueset_iterator_t  iter;
1008         int                     n_succ;
1009
1010         /* filter blocks from topological walker */
1011         if (! is_Block(block))
1012                 return;
1013
1014         /* the end block has no successor */
1015         if (block == env->end_block)
1016                 return;
1017
1018         info = get_block_info(block);
1019         /* track changes */
1020         size = ir_valueset_size(info->antic_in);
1021         n_succ = get_Block_n_cfg_outs(block);
1022
1023         /* add exp_gen */
1024         if (env->first_iter) {
1025 #if NO_INF_LOOPS
1026                 /* keep antic_in of infinite loops empty */
1027                 if (! is_in_infinite_loop(block)) {
1028                         foreach_valueset(info->exp_gen, value, expr, iter) {
1029                                 ir_valueset_insert(info->antic_in, value, expr);
1030                         }
1031                 }
1032 #else
1033                 foreach_valueset(info->exp_gen, value, expr, iter) {
1034                         ir_valueset_insert(info->antic_in, value, expr);
1035                 }
1036 #endif
1037         }
1038
1039         /* successor might have phi nodes */
1040         if (n_succ == 1 && get_irn_arity(get_Block_cfg_out(block, 0)) > 1) {
1041                 succ      = get_Block_cfg_out(block, 0);
1042                 int pos   = get_Block_cfgpred_pos(succ, block);
1043                 succ_info = get_block_info(succ);
1044
1045                 /* initialize translated set */
1046                 if (env->first_iter) {
1047                         info->trans = XMALLOC(ir_nodehashmap_t);
1048                         ir_nodehashmap_init(info->trans);
1049                 }
1050
1051                 foreach_valueset(succ_info->antic_in, value, expr, iter) {
1052                         ir_node *trans = get_translated(block, expr);
1053                         ir_node *trans_value;
1054                         ir_node *represent;
1055
1056                         if (trans == NULL)
1057                                 trans = phi_translate(expr, succ, pos, get_block_info(succ)->antic_in);
1058                         /* create new value if necessary */
1059                         trans_value = identify_or_remember(trans);
1060
1061                         DB((dbg, LEVEL_3, "Translate %+F %+F to %d = %+F (%+F)\n", expr, succ, pos, trans, trans_value));
1062
1063                         /* On value change (phi present) we need the translated node
1064                            to represent the new value for possible further translation. */
1065                         if (value != trans_value)
1066                                 represent = trans;
1067                         else
1068                                 represent = expr;
1069
1070                         if (is_clean_in_block(expr, block, info->antic_in)) {
1071 #if NO_INF_LOOPS2
1072                                 /* no flow over the backedge of endless loops */
1073                                 if (env->iteration <= 2 || ! (! is_in_infinite_loop(succ) || ! is_backedge(succ, pos))) {
1074                                         ir_valueset_replace(info->antic_in, trans_value, represent);
1075                                 }
1076 #else
1077                                 ir_valueset_replace(info->antic_in, trans_value, represent);
1078 #endif
1079                         }
1080                         set_translated(info->trans, expr, represent);
1081                 }
1082
1083         } else if (n_succ > 1) {
1084                 int         i;
1085                 ir_node    *common     = NULL;
1086                 ir_node    *succ0      = get_Block_cfg_out(block, 0);
1087                 block_info *succ0_info = get_block_info(succ0);
1088
1089                 /* disjoint of antic_ins */
1090                 foreach_valueset(succ0_info->antic_in, value, expr, iter) {
1091                         /* iterate over remaining successors */
1092                         for (i = 1; i < n_succ; ++i) {
1093                                 ir_node    *succ      = get_Block_cfg_out(block, i);
1094                                 block_info *succ_info = get_block_info(succ);
1095
1096                                 /* value in antic_in? */
1097                                 common = ir_valueset_lookup(succ_info->antic_in, value);
1098                                 if (common == NULL)
1099                                         break;
1100                         }
1101
1102                         if (common && is_clean_in_block(expr, block, info->antic_in))
1103                                 ir_valueset_replace(info->antic_in, value, expr);
1104                 }
1105         }
1106
1107
1108         DEBUG_ONLY(dump_value_set(info->antic_in, "Antic_in", block);)
1109
1110         if (size != ir_valueset_size(info->antic_in))
1111                 env->changes |= 1;
1112 }
1113
1114 /* --------------------------------------------------------
1115  * Main algorithm Avail_out
1116  * --------------------------------------------------------
1117  */
1118
1119 /**
1120  * Computes Avail_out(block):
1121  *
1122  * Avail_in(block)  = Avail_out(dom(block))
1123  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
1124  *
1125  * Precondition:
1126  *  This function must be called in the top-down topological order:
1127  *  Then it computes Leader(Nodes(block)) instead of Nodes(block) !
1128  *
1129  * @param block   the block
1130  * @param ctx     walker context
1131  */
1132 static void compute_avail_top_down(ir_node *block, void *ctx)
1133 {
1134         pre_env    *env   = (pre_env*)ctx;
1135         block_info *info;
1136
1137         if (block == env->end_block)
1138                 return;
1139
1140         info  = get_block_info(block);
1141
1142         /* Add all nodes from the immediate dominator.
1143            This ensures that avail_out contains the leader. */
1144         if (block != env->start_block) {
1145                 ir_node                *dom_block = get_Block_idom(block);
1146                 block_info             *dom_info  = get_block_info(dom_block);
1147                 ir_node                *value;
1148                 ir_node                *expr;
1149                 ir_valueset_iterator_t  iter;
1150
1151                 foreach_valueset(dom_info->avail_out, value, expr, iter)
1152                         /* replace: use the leader from dominator, not local exp_gen */
1153                         ir_valueset_replace(info->avail_out, value, expr);
1154         }
1155
1156         DEBUG_ONLY(dump_value_set(info->avail_out, "Avail_out", block);)
1157 }
1158
1159 /* --------------------------------------------------------
1160  * Main algorithm redundancy detection
1161  * --------------------------------------------------------
1162  */
1163
1164 /**
1165  * Returns a valid mode if the value of expr is a partially redundant value.
1166  *
1167  * @param block   the block
1168  * @param expr    the expression
1169  *
1170  * @return mode of the expression if it is partially redundant else NULL
1171  */
1172 static ir_mode *is_partially_redundant(ir_node *block, ir_node *expr, ir_node *value)
1173 {
1174         ir_node *first_avail         = NULL;
1175         int      pos;
1176         int      arity               = get_irn_arity(block);
1177         int      fully_redundant     = 1;
1178         int      partially_redundant = 0;
1179         ir_mode *mode                = NULL;
1180
1181         DB((dbg, LEVEL_3, "is partially redundant %+F(%+F) of %+F\n", expr, value, block));
1182
1183         /* for each predecessor blocks */
1184         for (pos = 0; pos < arity; ++pos) {
1185                 ir_node    *pred_block  = get_Block_cfgpred_block(block, pos);
1186                 block_info *pred_info;
1187                 ir_node    *trans_expr;
1188                 ir_node    *trans_value;
1189                 ir_node    *avail_expr;
1190
1191                 pred_info  = get_block_info(pred_block);
1192                 trans_expr = get_translated(pred_block, expr);
1193                 trans_value = identify(trans_expr);
1194
1195                 if (is_Const(trans_expr))
1196                         avail_expr = trans_expr;
1197                 else
1198                         avail_expr = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
1199
1200                 /* value might be available through a not yet existing constant */
1201                 if (avail_expr == NULL && is_Const(trans_expr)) {
1202                         /* limit range of new constants */
1203                         ir_mode   *cmode = get_irn_mode(trans_expr);
1204                         ir_tarval *upper = new_tarval_from_long(127, cmode);
1205                         ir_tarval *lower = new_tarval_from_long(-127, cmode);
1206                         ir_tarval *c     = get_Const_tarval(trans_expr);
1207
1208                         /* tarval within range? */
1209                         if (tarval_cmp(lower, c) == ir_relation_less_equal &&
1210                                 tarval_cmp(c, upper) == ir_relation_less_equal) {
1211                                 avail_expr = trans_expr;
1212                         } else {
1213                                 avail_expr = NULL;
1214                         }
1215             }
1216
1217                 DB((dbg, LEVEL_3, "avail_expr %+F  trans_expr %+F\n", avail_expr, trans_expr));
1218
1219                 if (avail_expr == NULL) {
1220                         pred_info->avail = trans_expr;
1221                         pred_info->found = 0;
1222                         fully_redundant  = 0;
1223                 } else {
1224                         /* expr is available, use the leader */
1225                         pred_info->avail    = avail_expr;
1226                         pred_info->found    = 1;
1227                         mode                = get_irn_mode(avail_expr);
1228                         partially_redundant = 1;
1229
1230                         if (first_avail == NULL)
1231                                 first_avail = avail_expr;
1232                         else if (first_avail != avail_expr)
1233                                 /* Multiple different expressions are available,
1234                                    This is why we need no cut over avail_out sets. */
1235                                 fully_redundant = 0;
1236
1237                         DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, avail_expr, pred_block));
1238                 }
1239         }
1240
1241 #if BETTER_GREED
1242         /* value is redundant from last iteration,
1243            but has not been removed from antic_in (is not optimized) */
1244         if (! environ->first_iter && is_redundant(block, expr))
1245                 return mode;
1246 #endif
1247
1248         /* If it is not the same value already existing along every predecessor
1249        and it is defined by some predecessor then it is partially redundant. */
1250         if (! partially_redundant || fully_redundant)
1251                 return NULL;
1252         return mode;
1253 }
1254
1255 /**
1256  * Updates the new_set of a block by adding the new_set of
1257  * the immediate dominating block.
1258  *
1259  * @param  the block
1260  */
1261 static void update_new_set(ir_node *block, ir_node *idom)
1262 {
1263         ir_node                *value;
1264         ir_node                *expr;
1265         ir_valueset_iterator_t  iter;
1266         block_info             *curr_info = get_block_info(block);
1267         block_info             *idom_info = get_block_info(idom);
1268         int                     updated   = 0;
1269
1270         DEBUG_ONLY(dump_value_set(idom_info->new_set, "[New Set]", idom);)
1271         foreach_valueset(idom_info->new_set, value, expr, iter) {
1272                 /* inherit new_set from immediate dominator */
1273                 ir_valueset_insert(curr_info->new_set, value, expr);
1274                 /* replace in avail_out */
1275                 updated |= ir_valueset_replace(curr_info->avail_out, value, expr);
1276         }
1277 #ifdef DEBUG_libfirm
1278         if (updated)
1279                 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
1280 #endif
1281 } /* update_new_set */
1282
1283 #if BETTER_GREED
1284 /*
1285  * Returns redundant flag of node irn in block block.
1286  */
1287 static unsigned is_redundant(ir_node *block, ir_node *irn)
1288 {
1289         (void) block;
1290         (void) irn;
1291
1292         /* TODO Needs to use a flag, because antic_done should only be used
1293            if node is finally processed by insert_nodes. */
1294         return 0;
1295 }
1296 #endif
1297
1298 /**
1299  * Checks if hoisting irn is greedy.
1300  * Greedy hoisting means that there are non partially redundant nodes
1301  * hoisted. This happens if a partially redundant node has
1302  * non redundant predecessors.
1303  */
1304 static unsigned is_hoisting_greedy(ir_node *irn, ir_node *block)
1305 {
1306         int block_arity = get_irn_arity(block);
1307         int arity = get_irn_arity(irn);
1308         int pos, i;
1309         block_info *info = get_block_info(block);
1310
1311         /* As long as the predecessor values are available in all predecessor blocks,
1312            we can hoist this value. */
1313         for (pos = 0; pos < block_arity; ++pos) {
1314                 ir_node    *pred_block = get_Block_cfgpred_block(block, pos);
1315                 block_info *pred_info  = get_block_info(pred_block);
1316
1317                 for (i = 0; i < arity; ++i) {
1318                         ir_node *pred     = get_irn_n(irn, i);
1319                         ir_node *value;
1320                         ir_node *leader;
1321                         ir_node *trans;
1322                         ir_node *trans_val;
1323                         ir_node *avail;
1324
1325 #if MIN_CUT
1326                         /* Very conservative min cut. Phi might only have 1 user. */
1327                         if (is_Phi(pred) && get_irn_n_edges(pred) != 1)
1328                                 return 1;
1329 #endif
1330
1331                         if (is_Phi(pred) && get_nodes_block(pred) == block)
1332                                 continue;
1333
1334                         DB((dbg, LEVEL_3, "pred %+F\n", pred));
1335                         value = identify(pred);
1336                         leader = ir_valueset_lookup(info->antic_in, value);
1337                         if (! leader)
1338                                 leader = pred;
1339                         DB((dbg, LEVEL_3, "lead %+F\n", leader));
1340                         trans   = get_translated(pred_block, leader);
1341                         if (! trans)
1342                                 trans = pred;
1343                         DB((dbg, LEVEL_3, "trans %+F\n", trans));
1344
1345                         trans_val = identify(trans);
1346                         DB((dbg, LEVEL_3, "value %+F\n", trans_val));
1347
1348                         if (is_Const(trans_val) || is_SymConst(trans_val)) {
1349                                 /* existing constant */
1350                                 if (get_irn_idx(trans_val) < environ->last_idx) {
1351                                         continue;
1352                                 } else {
1353                                         /* limit range of new constants */
1354                                         ir_mode   *cmode = get_irn_mode(trans);
1355                                         ir_tarval *upper = new_tarval_from_long(128, cmode);
1356                                         ir_tarval *lower = new_tarval_from_long(-128, cmode);
1357                                         ir_tarval *c     = get_Const_tarval(trans);
1358
1359                                         /* tarval within range? */
1360                                         if (tarval_cmp(lower, c) == ir_relation_less &&
1361                                                 tarval_cmp(c, upper) == ir_relation_less) {
1362                                                 continue;
1363                                         } else {
1364                                                 return 1;
1365                                         }
1366                                 }
1367                         }
1368
1369                         /* */
1370                         if (is_irn_constlike(trans_val))
1371                                 continue;
1372
1373                         avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
1374
1375                         if (! avail)
1376                                 return 1;
1377 #if MIN_CUT
1378                         /* only optimize if predecessors have been optimized */
1379                         if (ir_valueset_lookup(info->antic_done, value) == NULL)
1380                                 return 1;
1381 #endif
1382                 }
1383         }
1384         return 0;
1385 }
1386
1387 /**
1388  * Perform insertion of partially redundant values.
1389  * For every block node, do the following:
1390  * 1.  Propagate the NEW_SETS of the dominator into the current block.
1391  * If the block has multiple predecessors,
1392  *     2a. Iterate over the ANTIC expressions for the block to see if
1393  *         any of them are partially redundant.
1394  *     2b. If so, insert them into the necessary predecessors to make
1395  *         the expression fully redundant.
1396  *     2c. Insert a new Phi merging the values of the predecessors.
1397  *     2d. Insert the new Phi, and the new expressions, into the
1398  *         NEW_SETS set.
1399  *
1400  * @param block  the block
1401  * @param ctx    the walker environment
1402  */
1403 static void insert_nodes_walker(ir_node *block, void *ctx)
1404 {
1405         pre_env                *env    = (pre_env*)ctx;
1406         int                     arity  = get_irn_arity(block);
1407         ir_node                *value;
1408         ir_node                *expr;
1409         block_info             *info;
1410         ir_node                *idom;
1411         int                     pos;
1412         ir_valueset_iterator_t  iter;
1413 #if BETTER_GREED
1414         plist_t *stack;
1415 #endif
1416
1417         /* only blocks */
1418         if (! is_Block(block))
1419                 return;
1420
1421         /* ensure that even the start block has a new_set */
1422         info = get_block_info(block);
1423         if (info->new_set)
1424                 ir_valueset_del(info->new_set);
1425         info->new_set = ir_valueset_new(16);
1426
1427         if (block == env->start_block)
1428                 return;
1429
1430         DB((dbg, LEVEL_2, "Insert operation of %+F\n", block));
1431
1432         idom = get_Block_idom(block);
1433         update_new_set(block, idom);
1434
1435         /* process only path joining blocks */
1436         if (arity < 2) {
1437                 return;
1438         }
1439
1440 #if BETTER_GREED
1441         stack = plist_new();
1442         foreach_valueset(info->antic_in, value, expr, iter) {
1443                 /* inverse topologic */
1444                 plist_insert_front(stack, expr);
1445         }
1446 #endif
1447
1448         /* This is the main reason antic_in is preverred over antic_out;
1449            we may iterate over every anticipated value first and not
1450            over the predecessor blocks. */
1451         foreach_valueset(info->antic_in, value, expr, iter) {
1452                 ir_mode  *mode;
1453                 ir_node  *phi;
1454                 ir_node **phi_in;
1455
1456                 /* already done? */
1457                 if (ir_valueset_lookup(info->antic_done, value))
1458                         continue;
1459
1460                 /* filter phi nodes from antic_in */
1461                 if (is_Phi(expr))
1462                         continue;
1463
1464                 DB((dbg, LEVEL_2, "Insert for %+F (value %+F) in %+F\n", expr, value, block));
1465
1466                 /* A value computed in the dominator is totally redundant.
1467                    Hence we have nothing to insert. */
1468                 if (ir_valueset_lookup(get_block_info(idom)->avail_out, value)) {
1469                         DB((dbg, LEVEL_2, "Fully redundant expr %+F value %+F\n", expr, value));
1470                         DEBUG_ONLY(inc_stats(gvnpre_stats->fully);)
1471
1472                         ir_valueset_insert(info->antic_done, value, expr);
1473                         continue;
1474                 }
1475
1476 #if !BETTER_GREED
1477                 if (is_hoisting_greedy(expr, block)) {
1478                         DB((dbg, LEVEL_2, "greedy\n"));
1479                         continue;
1480                 }
1481 #endif
1482
1483                 mode = is_partially_redundant(block, expr, value);
1484                 if (mode == NULL)
1485                         continue;
1486
1487 #if BETTER_GREED
1488                 if (is_hoisting_greedy(expr, block)) {
1489                         DB((dbg, LEVEL_2, "Better greed: greedy\n"));
1490                         continue;
1491                 }
1492 #endif
1493
1494 #if LOADS || OLD_DIVMODS || DIVMODS
1495                 /* save old mode_M phis to remove keepalive edges later */
1496                 if (is_memop(expr)) {
1497                         ir_node *mem = get_memop_mem(expr);
1498                         if (is_Phi(mem) && get_nodes_block(mem) == get_nodes_block(expr)) {
1499                                 ir_nodeset_insert(env->keeps, mem);
1500                         }
1501                 }
1502 #endif
1503
1504 #ifdef DEBUG_libfirm
1505                 if (! is_Proj(expr)) {
1506                         if (env->first_iter)
1507                                 inc_stats(gvnpre_stats->first_iter_found);
1508                         inc_stats(gvnpre_stats->partially);
1509                 }
1510                 if (is_Load(expr))
1511                         inc_stats(gvnpre_stats->loads);
1512                 else if (is_Div(expr) || is_Mod(expr))
1513                         inc_stats(gvnpre_stats->divmods);
1514 #endif
1515
1516                 phi_in = XMALLOCN(ir_node *, arity);
1517
1518                 /* for each predecessor block */
1519                 for (pos = 0; pos < arity; ++pos) {
1520                         ir_node    *pred_block = get_Block_cfgpred_block(block, pos);
1521                         block_info *pred_info;
1522
1523                         pred_info = get_block_info(pred_block);
1524
1525                         if (! pred_info->found) {
1526                                 int i;
1527                                 int node_arity = get_irn_arity(expr);
1528                                 ir_node **in = XMALLOCNZ(ir_node *, node_arity);
1529                                 ir_node *trans;
1530                                 ir_node *new_value, *new_value2;
1531                                 ir_node *target_block = pred_block;
1532
1533                                 for (i = 0; i < node_arity; ++i) {
1534                                         ir_node *pred     = get_irn_n(expr, i);
1535                                         ir_node *value    = identify(pred);
1536                                         ir_node *leader;
1537                                         ir_node *trans;
1538                                         ir_node *trans_val;
1539                                         ir_node *avail;
1540
1541                                         /* transform knowledge over the predecessor from
1542                                            anti-leader world into leader world. */
1543
1544                                         DB((dbg, LEVEL_3, "pred %+F\n", pred));
1545                                         value = identify(pred);
1546
1547                                         /* get leader for pred to lookup its translated value */
1548                                         leader = ir_valueset_lookup(info->antic_in, value);
1549                                         if (! leader)
1550                                                 leader = pred;
1551                                         DB((dbg, LEVEL_3, "lead %+F\n", leader));
1552
1553                                         trans   = get_translated(pred_block, leader);
1554                                         if (!trans)
1555                                                 trans = pred;
1556                                         DB((dbg, LEVEL_3, "trans %+F\n", trans));
1557
1558                                         /* in case of phi, we are done */
1559                                         if (is_Phi(pred) && get_nodes_block(pred) == block) {
1560                                                 in[i] = trans;
1561                                                 continue;
1562                                         }
1563
1564                                         trans_val = identify(trans);
1565                                         DB((dbg, LEVEL_3, "value %+F\n", trans_val));
1566
1567                                         /* constants are always available but not in avail set */
1568                                         if (is_irn_constlike(trans_val)) {
1569                                                 in[i] = trans;
1570                                                 continue;
1571                                         }
1572
1573                                         /* use the leader
1574                                            In case of loads we need to make sure the hoisted
1575                                            loads are found despite their unique value. */
1576                                         avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
1577                                         DB((dbg, LEVEL_3, "avail %+F\n", avail));
1578
1579                                         assert(avail && "predecessor has to be available");
1580                                         in[i] = avail;
1581                                 }
1582
1583                                 if (is_Proj(expr))
1584                                         target_block = get_nodes_block(in[0]);
1585
1586                                 /* Copy node to represent the new value.
1587                                    We use translated nodes as value representatives only.
1588                                    They have anti leaders as predecessors, not leaders!
1589                                    So we have to create a new node using leaders. */
1590                                 trans = new_ir_node(
1591                                         get_irn_dbg_info(expr),
1592                                         environ->graph,
1593                                         target_block,
1594                                         get_irn_op(expr),
1595                                         get_irn_mode(expr),
1596                                         get_irn_arity(expr),
1597                                         in);
1598                                 free(in);
1599                                 /* We need the attribute copy here, because the Hash value of a
1600                                    node might depend on it. */
1601                                 copy_node_attr(environ->graph, expr, trans);
1602
1603                                 /* value is now available in target block through trans
1604                                    insert (not replace) because it has not been available */
1605                                 new_value = identify_or_remember(trans);
1606                                 ir_valueset_insert(pred_info->avail_out, new_value, trans);
1607                                 DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value));
1608
1609                                 new_value2 = identify(get_translated(pred_block, expr));
1610                                 ir_valueset_insert(pred_info->avail_out, new_value2, trans);
1611                                 DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value2));
1612
1613                                 DB((dbg, LEVEL_3, "Use new %+F in %+F because %+F(%+F) not available\n", trans, pred_block, expr, value));
1614
1615                                 phi_in[pos] = trans;
1616                         } else {
1617                                 /* value available */
1618                                 phi_in[pos] = pred_info->avail;
1619                         }
1620                         DB((dbg, LEVEL_3, "phi_in %+F\n", phi_in[pos]));
1621                 }
1622
1623                 /* We do not connect tuples as they will be connected automatically
1624                    by the corresponding projections. */
1625                 if (get_irn_mode(expr) != mode_T) {
1626
1627                         phi = new_r_Phi(block, arity, phi_in, mode);
1628                         DB((dbg, LEVEL_3, "New %+F for redundant %+F created\n", phi, expr));
1629
1630                         /* This value is now available through the new phi.
1631                            insert || replace in avail_out */
1632                         ir_valueset_replace(info->avail_out, value, phi);
1633                         ir_valueset_insert(info->new_set, value, phi);
1634                 }
1635                 free(phi_in);
1636
1637                 /* already optimized this value in this block */
1638                 ir_valueset_insert(info->antic_done, value, expr);
1639                 env->changes |= 1;
1640         }
1641
1642 #if BETTER_GREED
1643         /* TODO Unfinished
1644            Better greed first determines which values are redundant
1645            and decides then which to take.
1646            insert_nodes needs to be split up for that. The cycle could be
1647            for each block: flag redundant nodes,
1648            use heuristic to adjust these flags (also consider antic_done),
1649            do insert nodes.
1650            This way we could decide if we should hoist a non redundant node,
1651            if all its successors are redundant.
1652            Or we might try to minimize the cut along hoisted nodes and their
1653            non redundant successors.
1654          */
1655         if (env->changes) {
1656                 plist_element_t *it;
1657                 /* iterate in inverse topological order */
1658                 foreach_plist(stack, it) {
1659                         ir_node *irn   = (ir_node *)plist_element_get_value(it);
1660                         ir_node *block = get_nodes_block(irn);
1661                         int      j;
1662                         char     redundant = 1;
1663
1664                         /* does irn only have redundant successors? */
1665
1666                         foreach_out_edge(irn, edge) {
1667                                 ir_node *succ = get_edge_src_irn(edge);
1668
1669                                 /* if succ and irn are in the same block */
1670                                 if (get_nodes_block(succ) == block && is_redundant(block, succ)) {
1671                                         continue;
1672                                 } else {
1673                                         redundant = 0;
1674                                         break;
1675                                 }
1676                         }
1677
1678                         if (redundant)
1679                                 flag_redundant(irn, 1);
1680                 }
1681         }
1682         plist_free(stack);
1683 #endif
1684
1685 }
1686
1687 #if HOIST_HIGH
1688 static void update_new_set_walker(ir_node *block, void *ctx)
1689 {
1690         pre_env *env = (pre_env*)ctx;
1691
1692         if (! is_Block(block))
1693                 return;
1694         if (block == env->start_block)
1695                 return;
1696
1697         update_new_set(block, get_Block_idom(block));
1698 }
1699
1700 /**
1701  * Domtree block walker to insert nodes with dying operands
1702  * into the highest possible block whilst still being anticipated.
1703  */
1704 static void hoist_high(ir_node *block, void *ctx)
1705 {
1706         pre_env                *env        = (pre_env*)ctx;
1707         block_info             *curr_info;
1708         ir_valueset_iterator_t  iter;
1709         ir_node                *expr;
1710         ir_node                *value;
1711         int                     arity      = get_irn_arity(block);
1712
1713         if (! is_Block(block))
1714                 return;
1715
1716         curr_info = get_block_info(block);
1717
1718         if (curr_info->new_set)
1719                 ir_valueset_del(curr_info->new_set);
1720         curr_info->new_set = ir_valueset_new(16);
1721
1722         if (block == env->start_block)
1723                 return;
1724
1725         if (arity < 2)
1726                 return;
1727
1728         DB((dbg, LEVEL_2, "High hoisting %+F\n", block));
1729
1730         /* foreach entry optimized by insert node phase */
1731         foreach_valueset(curr_info->antic_done, value, expr, iter) {
1732                 int pos;
1733
1734                 /* TODO currently we cannot handle load and their projections */
1735                 if (is_memop(expr) || is_Proj(expr))
1736                         continue;
1737
1738                 DB((dbg, LEVEL_4, "leader %+F value %+F\n", expr, value));
1739
1740                 /* visit hoisted expressions */
1741                 for (pos = 0; pos < arity; ++pos) {
1742                         /* standard target is predecessor block */
1743                         ir_node    *target     = get_Block_cfgpred_block(block, pos);
1744                         block_info *pred_info  = get_block_info(target);
1745                         ir_node    *avail;
1746                         ir_node    *new_target;
1747                         ir_node    *trans_expr;
1748                         ir_node    *trans_value;
1749                         ir_node    *dom;
1750                         int         avail_arity;
1751                         int         i;
1752                         unsigned    nest_depth;
1753                         block_info *dom_info;
1754
1755                         /* get phi translated value */
1756                         trans_expr  = get_translated(target, expr);
1757                         trans_value = identify(trans_expr);
1758                         avail       = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
1759
1760                         /* get the used expr on this path */
1761
1762                         /* TODO when does this happen? */
1763                         if (avail == NULL)
1764                                 continue;
1765
1766                         avail_arity = get_irn_arity(avail);
1767                         value = identify(avail);
1768
1769                         /* anticipation border */
1770                         new_target  = NULL;
1771                         nest_depth  = get_loop_depth(get_irn_loop(target));
1772
1773                         /* Either push the hoisted nodes up their path,
1774                            or try to put them directly into their common dominator. */
1775 #if COMMON_DOM
1776                         /* By using block (instead of target) as initial block,
1777                            we only allow hoisting into a common block of
1778                            both predecessor blocks. */
1779                         dom         = block;
1780 #else
1781                         dom         = target;
1782 #endif
1783
1784                         while (dom && dom != get_Block_idom(block)) {
1785
1786                                 dom = get_Block_idom(dom);
1787                                 dom_info = get_block_info(dom);
1788                                 DB((dbg, LEVEL_4, "testing dom %+F\n", dom));
1789
1790                                 /* TODO Being in antic_in means hoistable above block,
1791                                    but we need 'hoistable into block'.
1792                                    This could be achieved by a flag for each valueset pair,
1793                                    being set during antic computation. */
1794
1795                                 /* check if available node ist still anticipated and clean */
1796                                 if (! ir_valueset_lookup(dom_info->antic_in, value)) {
1797                                         DB((dbg, LEVEL_4, "%+F not antic in %+F\n", value, dom));
1798                                         break;
1799                                 }
1800
1801                                 nest_depth = get_loop_depth(get_irn_loop(dom));
1802
1803                                 /* do not hoist into loops */
1804                                 if (get_loop_depth(get_irn_loop(dom)) > nest_depth) {
1805                                         DB((dbg, LEVEL_4, "%+F deeper nested\n", dom));
1806                                         /* not a suitable location */
1807                                         continue;
1808                                 }
1809
1810                                 /* check if operands die */
1811
1812                                 /* check for uses on current path */
1813                                 for (i = 0; i < avail_arity; i++) {
1814                                         ir_node   *pred       = get_irn_n(avail, i);
1815                                         ir_node   *pred_value = identify(pred);
1816
1817                                         if (dom == NULL)
1818                                                 break;
1819
1820                                         DB((dbg, LEVEL_4, "testing pred %+F\n", pred));
1821
1822                                         if (! ir_valueset_lookup(dom_info->avail_out, pred_value)) {
1823                                                 DB((dbg, LEVEL_4, "pred %+F not available\n", pred));
1824                                                 dom = NULL;
1825                                                 break;
1826                                         }
1827
1828                                         /* check every successor */
1829                                         foreach_out_edge(pred, edge) {
1830                                                 ir_node *succ = get_edge_src_irn(edge);
1831                                                 DB((dbg, LEVEL_4, "testing succ %+F\n", succ));
1832
1833                                                 /* check only successors on current path to end */
1834                                                 if (block_dominates(dom, get_nodes_block(succ))) {
1835                                                         ir_node *succ_value = identify(succ);
1836
1837                                                         /* Do we have another user than avail?
1838                                                            Then predecessor is not dead after removal of avail. */
1839                                                         if (succ_value != value) {
1840                                                                 DB((dbg, LEVEL_4, "still used in %+F\n", succ));
1841                                                                 dom = NULL;
1842                                                                 break;
1843                                                         }
1844                                                 }
1845                                         }
1846                                 }
1847                                 if (dom)
1848                                         new_target = dom;
1849
1850 #if COMMON_DOM
1851                                 /* only try common dominator */
1852                                 break;
1853 #endif
1854                         }
1855
1856                         /* put node into new target block */
1857                         if (new_target) {
1858                                 block_info *target_info = get_block_info(new_target);
1859                                 int         nn_arity    = get_irn_arity(avail);
1860                                 ir_node   **in          = XMALLOCN(ir_node *, nn_arity);
1861                                 ir_node    *nn;
1862                                 int         i;
1863
1864                                 DB((dbg, LEVEL_2, "Hoisting %+F into %+F\n", avail, new_target));
1865                                 DEBUG_ONLY(inc_stats(gvnpre_stats->hoist_high);)
1866
1867                                 for (i = 0; i < nn_arity; ++i) {
1868                                         ir_node *pred       = get_irn_n(avail, i);
1869                                         ir_node *avail_pred = ir_valueset_lookup(target_info->avail_out, identify(pred));
1870                                         assert(avail_pred);
1871                                         in[i] = avail_pred;
1872                                 }
1873                                 nn = new_ir_node(
1874                                         get_irn_dbg_info(avail),
1875                                         environ->graph,
1876                                         new_target,
1877                                         get_irn_op(avail),
1878                                         get_irn_mode(avail),
1879                                         nn_arity,
1880                                         in);
1881                                 free(in);
1882
1883                                 identify_or_remember(nn);
1884                                 /* TODO Nodes are inserted into a dominating block and should
1885                                    be available from this point on. Currently we do not push
1886                                    the availability information through during the walk. */
1887                                 ir_valueset_insert(target_info->new_set, value, nn);
1888                         }
1889                 }
1890         }
1891 }
1892 #endif
1893
1894 /* --------------------------------------------------------
1895  * Elimination of fully redundant nodes
1896  * --------------------------------------------------------
1897  */
1898
1899 /**
1900  * Walker which finds redundant nodes using avail_out sets
1901  * and exchanges them for existing ones.
1902  * We cannot change the graph here as this would affect
1903  * the hash values of the nodes.
1904  *
1905  * @param irn  the node
1906  * @param ctx  the walker environment
1907  */
1908 static void eliminate(ir_node *irn, void *ctx)
1909 {
1910         pre_env *env = (pre_env*)ctx;
1911
1912         if (! is_Block(irn)) {
1913                 ir_node    *block = get_nodes_block(irn);
1914                 block_info *info  = get_block_info(block);
1915                 ir_node    *value = identify(irn);
1916
1917                 if (value != NULL) {
1918                         ir_node *expr = (ir_node*)ir_valueset_lookup(info->avail_out, value);
1919                         DB((dbg, LEVEL_3, "Elim %+F(%+F) avail %+F\n", irn, value, expr));
1920
1921                         if (expr != NULL && expr != irn) {
1922                                 elim_pair *p = OALLOC(env->obst, elim_pair);
1923
1924                                 p->old_node = irn;
1925                                 p->new_node = expr;
1926                                 p->next     = env->pairs;
1927                                 if (get_irn_idx(expr) > env->last_idx)
1928                                         p->reason = FS_OPT_GVN_PARTLY;
1929                                 else
1930                                         p->reason = FS_OPT_GVN_FULLY;
1931                                 env->pairs = p;
1932                                 DEBUG_ONLY(inc_stats(gvnpre_stats->replaced);)
1933                         }
1934                 }
1935         }
1936 }  /* eliminate */
1937
1938 /**
1939  * Do all the recorded changes and optimize
1940  * newly created Phi's.
1941  *
1942  * @param pairs  list of elimination pairs
1943  */
1944 static void eliminate_nodes(elim_pair *pairs, ir_nodeset_t *keeps)
1945 {
1946         elim_pair             *p;
1947         ir_node               *end    = environ->end_node;
1948
1949         for (p = pairs; p != NULL; p = p->next) {
1950                 /* might be already changed */
1951                 p->new_node = skip_Id(p->new_node);
1952
1953                 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
1954
1955                 /* PRE tends to create Phi(self, self, ... , x, self, self, ...)
1956                  * which we can optimize here */
1957                 if (is_Phi(p->new_node)) {
1958                         int      i;
1959                         ir_node *res = NULL;
1960
1961                         for (i = get_irn_arity(p->new_node) - 1; i >= 0; --i) {
1962                                 ir_node *pred = get_irn_n(p->new_node, i);
1963
1964                                 if (pred != p->old_node) {
1965                                         if (res) {
1966                                                 res = NULL;
1967                                                 break;
1968                                         }
1969                                         res = pred;
1970                                 }
1971                         }
1972                         if (res) {
1973                                 exchange(p->new_node, res);
1974                                 p->new_node = res;
1975                         }
1976                 }
1977                 DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
1978
1979                 exchange(p->old_node, p->new_node);
1980         }
1981
1982         /* remove keep alive edges of unused mode_M phis */
1983         foreach_ir_nodeset(keeps, m_phi, iter) {
1984                 remove_End_keepalive(end, m_phi);
1985         }
1986 }  /* eliminate_nodes */
1987
1988
1989 /* --------------------------------------------------------
1990  * GVN PRE pass
1991  * --------------------------------------------------------
1992  */
1993
1994 /**
1995  * Gvn_Pre algorithm.
1996  *
1997  * @param irg   the graph
1998  * @param env   the environment
1999  */
2000 static void gvn_pre(ir_graph *irg, pre_env *env)
2001 {
2002         unsigned              antic_iter;
2003         unsigned              insert_iter;
2004
2005         DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg));
2006
2007         /* allocate block info */
2008         irg_walk_blkwise_graph(irg, block_info_walker, NULL, env);
2009
2010         ir_nodehashmap_init(&value_map);
2011
2012         /* generate exp_gen */
2013         irg_walk_blkwise_graph(irg, NULL, topo_walker, env);
2014         dump_all_expgen_sets(env->list);
2015
2016         /* compute the avail_out sets for all blocks */
2017         dom_tree_walk_irg(irg, compute_avail_top_down, NULL, env);
2018
2019         /* compute the anticipated value sets for all blocks */
2020         antic_iter      = 0;
2021         env->first_iter = 1;
2022
2023         env->iteration = 1;
2024         /* antic_in passes */
2025         do {
2026                 ++antic_iter;
2027                 DB((dbg, LEVEL_2, "= Antic_in Iteration %d ========================\n", antic_iter));
2028                 env->changes = 0;
2029                 irg_walk_blkwise_graph(irg, compute_antic, NULL, env);
2030                 env->first_iter = 0;
2031                 DB((dbg, LEVEL_2, "----------------------------------------------\n"));
2032                 env->iteration ++;
2033         } while (env->changes != 0 && antic_iter < MAX_ANTIC_ITER);
2034
2035         DEBUG_ONLY(set_stats(gvnpre_stats->antic_iterations, antic_iter);)
2036
2037         ir_nodeset_init(env->keeps);
2038         insert_iter       = 0;
2039         env->first_iter   = 1;
2040         /* compute redundant expressions */
2041         do {
2042                 ++insert_iter;
2043                 DB((dbg, LEVEL_2, "= Insert Iteration %d ==========================\n", insert_iter));
2044                 env->changes = 0;
2045                 /* TODO topologically top down would be better; fewer iterations. */
2046                 dom_tree_walk_irg(irg, insert_nodes_walker, NULL, env);
2047                 env->first_iter = 0;
2048                 DB((dbg, LEVEL_2, "----------------------------------------------\n"));
2049         } while (env->changes != 0 && insert_iter < MAX_INSERT_ITER);
2050         DEBUG_ONLY(set_stats(gvnpre_stats->insert_iterations, insert_iter);)
2051
2052 #if HOIST_HIGH
2053         /* An attempt to reduce lifetimes by hoisting already hoisted values
2054            even higher if their operands die. */
2055         dom_tree_walk_irg(irg, hoist_high, NULL, env);
2056         /* update avail_out for elimination */
2057         dom_tree_walk_irg(irg, update_new_set_walker, NULL, env);
2058 #endif
2059
2060         /* Deactivate edges to prevent intelligent removal of nodes,
2061            or else we will get deleted nodes which we try to exchange. */
2062         edges_deactivate(environ->graph);
2063
2064         /* eliminate nodes */
2065         irg_walk_graph(irg, NULL, eliminate, env);
2066         eliminate_nodes(env->pairs, env->keeps);
2067
2068         ir_nodeset_destroy(env->keeps);
2069 }
2070
2071 /**
2072  * Gvn_Pre pass for graph irg.
2073  *
2074  * @param irg   the graph
2075  */
2076 void do_gvn_pre(ir_graph *irg)
2077 {
2078         struct obstack        obst;
2079         pre_env               env;
2080         ir_nodeset_t          keeps;
2081         optimization_state_t  state;
2082         block_info           *block_info;
2083
2084         /* bads and unreachables cause too much trouble with dominance,
2085            loop info for endless loop detection,
2086            no critical edges is PRE precondition
2087          */
2088         assure_irg_properties(irg,
2089                 IR_GRAPH_PROPERTY_NO_BADS
2090                 | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
2091                 | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO
2092                 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
2093                 | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
2094                 | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
2095
2096         /* register a debug mask */
2097         FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
2098
2099         save_optimization_state(&state);
2100         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_LOOP_LINK);
2101
2102         edges_activate(irg);
2103
2104         environ = &env;
2105         DEBUG_ONLY(init_stats();)
2106
2107         /* setup environment */
2108         obstack_init(&obst);
2109         env.graph        = irg;
2110         env.obst         = &obst;
2111         env.list         = NULL;
2112         env.start_block  = get_irg_start_block(irg);
2113         env.end_block    = get_irg_end_block(irg);
2114         env.end_node     = get_irg_end(irg);
2115         env.pairs        = NULL;
2116         env.keeps        = &keeps;
2117         env.last_idx     = get_irg_last_idx(irg);
2118
2119         /* Detect and set links of infinite loops to non-zero. */
2120         analyse_loops(irg);
2121
2122         /* Switch on GCSE. We need it to correctly compute
2123            the value of a node, which is independent from
2124            its block. */
2125         set_opt_global_cse(1);
2126         /* new_identities */
2127         if (irg->value_table != NULL)
2128                 del_pset(irg->value_table);
2129         /* initially assumed nodes in pset are 512 */
2130         irg->value_table = new_pset(compare_gvn_identities, 512);
2131
2132         /* do GVN-PRE pass */
2133         gvn_pre(irg, &env);
2134         DEBUG_ONLY(print_stats();)
2135
2136         /* clean up: delete all sets */
2137         for (block_info = env.list; block_info != NULL; block_info = block_info->next) {
2138                 free_block_info(block_info);
2139         }
2140
2141         DEBUG_ONLY(free_stats();)
2142         ir_nodehashmap_destroy(&value_map);
2143         obstack_free(&obst, NULL);
2144         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_LOOP_LINK);
2145
2146         /* Pin the graph again.
2147            This is needed due to the use of set_opt_global_cse(1) */
2148         set_irg_pinned(irg, op_pin_state_pinned);
2149         restore_optimization_state(&state);
2150         confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
2151
2152         /* TODO There seem to be optimizations that try to use the existing
2153            value_table. */
2154         new_identities(irg);
2155
2156         /* TODO assure nothing else breaks. */
2157         set_opt_global_cse(0);
2158         edges_activate(irg);
2159 }
2160
2161 /* Creates an ir_graph pass for do_gvn_pre. */
2162 ir_graph_pass_t *do_gvn_pre_pass(const char *name)
2163 {
2164         return def_graph_pass(name ? name : "gvn_pre", do_gvn_pre);
2165 }