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