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