2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Global Value Numbering Partial Redundancy Elimination
9 * (VanDrunen Hosking 2004)
10 * @author Michael Beck
23 #include "irnodehashmap.h"
24 #include "irnodeset.h"
25 #include "iropt_dbg.h"
26 #include "iroptimize.h"
31 #include "firmstat_t.h"
33 #include "irgraph_t.h"
38 /* suggested by GVN-PRE authors */
39 #define MAX_ANTIC_ITER 10
40 #define MAX_INSERT_ITER 3
42 /* Stops antic iteration from processing endless loops. */
43 #define IGNORE_INF_LOOPS 1
44 /* Stops antic information to flow over infinite loop backedge */
45 #define NO_INF_LOOPS 0
47 /* Attempt to reduce register pressure and reduce code size
52 /* Seamless implementation of handling loads and generally memory
53 dependent nodes with GVN-PRE. */
59 /* Only optimize node directly after phi node if node is only successor. */
62 /* GVN is very limited. This enables optimize_node during value recognition.
63 GVN ist still very limited, since a+1+b+1 doesn't equal a+b+2.
64 TODO Broken for yet unknown reasons. */
65 #define OPTIMIZE_NODES 0
68 /** Additional info we need for every block. */
69 typedef struct block_info {
70 ir_valueset_t *exp_gen; /* contains this blocks clean expressions */
71 ir_valueset_t *avail_out; /* available values at block end */
72 ir_valueset_t *antic_in; /* clean anticipated values at block entry */
73 ir_valueset_t *antic_done; /* keeps elements of antic_in after insert nodes phase */
74 ir_valueset_t *new_set; /* new by hoisting made available values */
75 ir_nodehashmap_t *trans; /* contains translated nodes translated into block */
76 ir_node *avail; /* saves available node for insert node phase */
77 int found; /* saves kind of availability for insert_node phase */
78 ir_node *block; /* block of the block_info */
79 struct block_info *next; /* links all instances for easy access */
83 * A pair of nodes to be exchanged.
84 * We have to defer the exchange because there are still needed references
87 typedef struct elim_pair {
88 ir_node *old_node; /* node that will be replaced */
89 ir_node *new_node; /* replacement for old_node */
90 struct elim_pair *next; /* links all instances for easy access */
91 int reason; /* reason for the replacement */
94 /** environment for the GVN-PRE algorithm */
95 typedef struct pre_env {
96 ir_graph *graph; /* current graph */
97 struct obstack obst; /* obstack to allocate on */
98 ir_node *start_block; /* start block of the current graph */
99 ir_node *end_block; /* end block of the current graph */
100 ir_node *end_node; /* end node of the current graph */
101 block_info *list; /* block_info list head */
102 elim_pair *pairs; /* elim_pair list head */
103 ir_nodeset_t *keeps; /* a list of to be removed phis to kill their keep alive edges */
104 unsigned last_idx; /* last node index of input graph */
105 char changes; /* flag for fixed point iterations - non-zero if changes occurred */
106 char first_iter; /* non-zero for first fixed point iteration */
107 int iteration; /* iteration counter */
109 pset *value_table; /* standard value table*/
110 pset *gvnpre_values; /* gvnpre value table */
114 static pre_env *environ;
116 /* custom GVN value map */
117 static ir_nodehashmap_t value_map;
119 /* debug module handle */
120 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
124 /* --------------------------------------------------------
126 * --------------------------------------------------------
129 typedef struct gvnpre_statistics {
136 int first_iter_found;
137 int antic_iterations;
138 int insert_iterations;
142 static gvnpre_statistics *gvnpre_stats = NULL;
144 static void init_stats(void)
146 gvnpre_stats = XMALLOCZ(gvnpre_statistics);
149 static void free_stats(void)
155 static void print_stats(void)
157 gvnpre_statistics *stats = gvnpre_stats;
158 DB((dbg, LEVEL_1, "replaced : %d\n", stats->replaced));
159 DB((dbg, LEVEL_1, "antic_in iterations : %d\n", stats->antic_iterations));
160 DB((dbg, LEVEL_1, "insert iterations : %d\n", stats->insert_iterations));
161 DB((dbg, LEVEL_1, "infinite loops : %d\n", stats->infinite_loops));
162 DB((dbg, LEVEL_1, "fully redundant : %d\n", stats->fully));
163 DB((dbg, LEVEL_1, "partially redundant : %d\n", stats->partially));
164 DB((dbg, LEVEL_1, " loads : %d\n", stats->loads));
165 DB((dbg, LEVEL_1, " Divs/Mods : %d\n", stats->divmods));
166 DB((dbg, LEVEL_1, " hoist high : %d\n", stats->hoist_high));
167 DB((dbg, LEVEL_1, " first iteration : %d\n", stats->first_iter_found));
170 #define set_stats(var, value) (var)=(value)
171 #define inc_stats(var) ((var)+=1)
173 /* --------------------------------------------------------
175 * --------------------------------------------------------
181 * @param set the set to dump
182 * @param txt a text to describe the set
183 * @param block the owner block of the set
185 static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
187 ir_valueset_iterator_t iter;
188 ir_node *value, *expr;
191 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
193 foreach_valueset(set, value, expr, iter) {
195 DB((dbg, LEVEL_2, "\n"));
197 DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
199 DB((dbg, LEVEL_2, " %+F,", expr));
202 DB((dbg, LEVEL_2, "\n}\n"));
206 * Dump all exp_gen value sets.
208 * @param list the list of block infos to retrieve the sets from
210 static void dump_all_expgen_sets(block_info *list)
212 block_info *block_info;
214 for (block_info = list; block_info != NULL; block_info = block_info->next) {
215 dump_value_set(block_info->exp_gen, "[Exp_gen]", block_info->block);
221 #define dump_all_expgen_sets(list)
222 #define dump_value_set(set, txt, block)
224 #endif /* DEBUG_libfirm */
226 /* --------------------------------------------------------
228 * --------------------------------------------------------
232 * Compares node collisions in valuetable.
233 * Modified identities_cmp().
235 static int compare_gvn_identities(const void *elt, const void *key)
237 ir_node *a = (ir_node *)elt;
238 ir_node *b = (ir_node *)key;
241 if (a == b) return 0;
243 /* phi nodes kill predecessor values and are always different */
244 if (is_Phi(a) || is_Phi(b))
247 /* memops are not the same, even if we want to optimize them
248 we have to take the order in account */
249 if (is_memop(a) || is_memop(b) ||
250 get_irn_mode(a) == mode_T ||
251 get_irn_mode(b) == mode_T) {
252 /* Loads with the same predecessors are the same value;
253 this should only happen after phi translation. */
254 if ((! is_Load(a) || ! is_Load(b)) && (! is_Store(a) || ! is_Store(b)))
258 if ((get_irn_op(a) != get_irn_op(b)) ||
259 (get_irn_mode(a) != get_irn_mode(b))) return 1;
261 /* compare if a's in and b's in are of equal length */
262 irn_arity_a = get_irn_arity(a);
263 if (irn_arity_a != get_irn_arity(b))
266 /* blocks are never the same */
267 if (is_Block(a) || is_Block(b))
270 /* should only be used with gcse enabled */
271 assert(get_opt_global_cse());
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))
284 * here, we already now that the nodes are identical except their
287 if (a->op->ops.node_cmp_attr)
288 return a->op->ops.node_cmp_attr(a, b);
294 * Identify does a lookup in the GVN valuetable.
295 * To be used when no new GVN values are to be created.
297 * @param e a node representing an expression
298 * @return a node representing the value
300 static ir_node *identify(ir_node *irn)
302 ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
305 /* irn represents a new value, so return the leader */
306 return identify_remember(irn);
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.
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.
322 * @param irn a node representing an expression
323 * @return the value of the expression
325 static ir_node *remember(ir_node *irn)
327 int arity = get_irn_arity(irn);
330 ir_node **in = XMALLOCN(ir_node *, arity);
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);
338 /* phi will be translated anyway, so kill the predecessor values
339 this also prevents circular dependencies */
341 /* every phi represents its own value */
346 /* predecessor is not its value representation/the leader */
347 if (pred != pred_value)
352 if (changed && !is_memop(irn) && get_irn_mode(irn) != mode_X) {
353 /* create representative for */
354 ir_node *nn = new_ir_node(
355 get_irn_dbg_info(irn),
357 get_nodes_block(irn),
362 copy_node_attr(environ->graph, irn, nn);
365 /* TODO optimize_node() uses the valuetable and thus the custom
366 identify_cmp() and will fail trying. */
367 environ->graph->value_table = environ->value_table;
368 nn = optimize_node(nn);
369 environ->graph->value_table = environ->gvnpre_values;
372 /* now the value can be determined because the
373 predecessors are the leaders */
374 value = identify_remember(nn);
376 value = identify_remember(irn);
380 DB((dbg, LEVEL_4, "Remember %+F as value %+F\n", irn, value));
381 ir_nodehashmap_insert(&value_map, irn, value);
387 * When the value map has been built we may lookup expressions
388 * and remember them if new.
390 static ir_node *identify_or_remember(ir_node *irn)
392 ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
396 return remember(irn);
399 /* --------------------------------------------------------
401 * --------------------------------------------------------
405 * Allocate block info for block block.
407 * @param block the block
408 * @param env the environment
410 static void alloc_block_info(ir_node *block, pre_env *env)
412 block_info *info = OALLOC(&env->obst, block_info);
414 set_irn_link(block, info);
415 info->exp_gen = ir_valueset_new(16);
416 info->avail_out = ir_valueset_new(16);
417 info->antic_in = ir_valueset_new(16);
418 info->antic_done = ir_valueset_new(16);
419 info->trans = XMALLOC(ir_nodehashmap_t);
420 ir_nodehashmap_init(info->trans);
422 info->new_set = NULL;
427 info->next = env->list;
431 static void free_block_info(block_info *block_info)
433 ir_valueset_del(block_info->exp_gen);
434 ir_valueset_del(block_info->avail_out);
435 ir_valueset_del(block_info->antic_in);
436 if (block_info->trans) {
437 ir_nodehashmap_destroy(block_info->trans);
438 free(block_info->trans);
440 if (block_info->new_set)
441 ir_valueset_del(block_info->new_set);
445 * Bottom up walker that ensures that every block gets a block info.
447 * @param irn the node
448 * @param ctx the environment
450 static void block_info_walker(ir_node *irn, void *ctx)
453 pre_env *env = (pre_env*)ctx;
454 alloc_block_info(irn, env);
459 * Returns the block info of a block.
461 static block_info *get_block_info(ir_node *block)
463 return (block_info*)get_irn_link(block);
466 /* --------------------------------------------------------
467 * Infinite loop analysis
468 * --------------------------------------------------------
472 * Walker to set block marks and loop links to 0.
474 static void clear_block_mark_loop_link(ir_node *block, void *env)
478 if (is_Block(block)) {
479 set_Block_mark(block, 0);
480 set_loop_link(get_irn_loop(block), NULL);
485 * Returns non-zero if block is part of real loop loop.
488 static unsigned in_loop(ir_node *block, ir_loop *loop)
490 ir_loop *l = get_irn_loop(block);
491 ir_loop *outer = get_irg_loop(environ->graph);
494 /* loop tree root is not a loop */
495 if (l == NULL || l == outer)
497 l = get_loop_outer_loop(l);
503 * Returns the outermost real loop of loop.
505 static ir_loop *get_loop_outermost(ir_loop *loop)
507 ir_loop *outer = get_irg_loop(environ->graph);
509 ir_loop *last = NULL;
513 l = get_loop_outer_loop(l);
519 * Topologic bottom-up walker sets links of infinite loops to non-zero.
520 * Block marks are used to flag blocks reachable (from end) on the one hand,
521 * on the other hand they are set if the block is not part of an infinite loop.
523 static void infinite_loop_walker(ir_node *block, void *env)
529 if (! is_Block(block))
532 /* start block has no predecessors */
533 if (block == environ->start_block)
536 arity = get_irn_arity(block);
538 /* block not part of a real loop: no infinite loop */
539 if (get_irn_loop(block) == get_irg_loop(environ->graph))
540 set_Block_mark(block, 1);
542 if (get_Block_mark(block)) {
543 /* reachable block: mark all cf predecessors */
544 for (i = 0; i < arity; ++i) {
545 ir_node *pred = get_Block_cfgpred_block(block, i);
548 set_Block_mark(pred, 1);
551 /* We are in a real loop and see an unreachable block. */
552 ir_loop *outermost_loop = get_loop_outermost(get_irn_loop(block));
554 /* flag loop as infinite */
555 set_loop_link(outermost_loop, outermost_loop);
556 DEBUG_ONLY(inc_stats(gvnpre_stats->infinite_loops);)
558 /* The cf predecessors are unreachable, but can never be part of
559 an infinite loop, because we just reached them. So we set the
560 blockmark to prevent triggering the infinite loop detection. */
562 /* passing information to the cf predecessors */
563 for (i = 0; i < arity; ++i) {
564 ir_node *pred = get_Block_cfgpred_block(block, i);
569 /* If our cf predecessor is in the same endless loop,
570 it is also unreachable. */
571 if (in_loop(pred, outermost_loop)) {
572 set_Block_mark(pred, 0);
574 /* When we leave the unreachable loop, we artificially
575 declare the cf predecessor reachable. */
576 set_Block_mark(pred, 1);
583 * Sets loop links of outermost infinite loops to non-zero.
585 static void analyse_loops(ir_graph *irg)
587 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
589 /* reset block mark and loop links */
590 irg_walk_blkwise_graph(irg, clear_block_mark_loop_link, NULL, NULL);
592 /* mark end block reachable */
593 set_Block_mark(get_irg_end_block(irg), 1);
594 irg_walk_blkwise_graph(irg, infinite_loop_walker, NULL, NULL);
596 ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
599 #if IGNORE_INF_LOOPS || NO_INF_LOOPS
601 * Returns non-zero if block is part of an infinite loop.
603 static unsigned is_in_infinite_loop(ir_node *block)
607 assert(is_Block(block));
608 loop = get_irn_loop(block);
611 loop = get_loop_outermost(loop);
613 return (get_loop_link(loop) != NULL);
619 /* --------------------------------------------------------
621 * --------------------------------------------------------
625 * Returns non-zero if a node is movable and a possible candidate for PRE.
627 static unsigned is_nice_value(ir_node *n)
629 ir_mode *mode = get_irn_mode(n);
635 if (is_Proj(n) && mode != mode_X && mode != mode_T)
644 return get_Load_volatility(n) == volatility_non_volatile;
646 return get_Store_volatility(n) == volatility_non_volatile;
649 if (get_irn_pinned(n) == op_pin_state_pinned)
652 if (! mode_is_data(mode)) {
653 if (! is_Div(n) && ! is_Mod(n))
660 * Checks if a node n is clean in block block for exp_gen.
663 * @param block the block
664 * @return non-zero value for clean node
666 static unsigned is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *valueset)
673 if (! is_nice_value(n))
677 /* filter loads with no phi predecessor from antic_in */
678 if (is_Load(n) && ! is_Phi(get_Load_mem(n)))
680 if (is_Store(n) && ! is_Phi(get_Store_mem(n)))
686 ir_node *mem = get_Div_mem(n);
690 if (! is_Phi(mem) && ! is_NoMem(mem))
694 if (is_Mod(n) && ! is_Phi(get_Mod_mem(n)))
698 arity = get_irn_arity(n);
699 for (i = 0; i < arity; ++i) {
700 ir_node *pred = get_irn_n(n, i);
706 /* we only handle current block */
707 if (get_nodes_block(pred) != block)
710 if (! is_nice_value(pred))
713 value = identify(pred);
714 if (! ir_valueset_lookup(valueset, value))
722 * Topological walker puts nodes in top-down topological order into exp_gen set.
723 * Assumed to walk blockwise and nodewise topologically top-down.
725 * @param irn the node
726 * @param ctx the environment
728 static void topo_walker(ir_node *irn, void *ctx)
739 environ->graph->value_table = environ->value_table;
740 identify_remember(irn);
741 environ->graph->value_table = environ->gvnpre_values;
744 /* GVN step: remember the value. */
745 value = remember(irn);
747 if (is_irn_constlike(irn))
750 block = get_nodes_block(irn);
751 info = get_block_info(block);
753 if (get_irn_mode(irn) != mode_X)
754 ir_valueset_insert(info->avail_out, value, irn);
756 /* values that are not in antic_in also dont't need to be in any other set */
758 if (! is_nice_value(irn))
761 if (is_clean_in_block(irn, block, info->exp_gen)) {
762 DB((dbg, LEVEL_3, "%+F clean in block %+F\n", irn, block));
764 ir_valueset_insert(info->exp_gen, value, irn);
768 /* --------------------------------------------------------
770 * --------------------------------------------------------
774 * Gets result of nodes phi translation into block.
776 * @param node the node
777 * @param block the target block
779 * @return a phi translation of node node into block block or NULL
781 static ir_node *get_translated(ir_node *block, ir_node *node)
783 if (is_irn_constlike(node))
786 return ir_nodehashmap_get(ir_node, get_block_info(block)->trans, node);
790 * Saves result of phi translation of node into predecessor
791 * at pos of block succ.
793 * @param node the node
794 * @param succ the successor of the translation target block
795 * @param pos the position of the predecessor block
796 * @param trans the translation result
799 static void set_translated(ir_nodehashmap_t *map, ir_node *node, ir_node *trans)
801 if (is_irn_constlike(node))
803 /* insert or replace */
804 ir_nodehashmap_insert(map, node, trans);
808 * Translates an expression above a Phi.
810 * @param node the node
811 * @param block the block the node is translated into
812 * @param pos the input number of the destination block
814 * @return a node representing the translated value
816 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *leaderset)
821 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
826 if (get_nodes_block(node) == block)
827 return get_Phi_pred(node, pos);
828 /* this phi does not need translation */
831 arity = get_irn_arity(node);
834 in = ALLOCANZ(ir_node *, arity);
836 /* A value has several representatives. The anti leader is chosen to be
837 the main representative. If we access a node as representative of a
838 value we always use the anti leader. The anti leader can be found by
839 antic_in(identify(node)). */
840 for (i = 0; i < arity; ++i) {
841 ir_node *pred = get_irn_n(node, i);
842 ir_node *value = identify(pred);
843 /* get leader for pred to lookup its translated value */
844 ir_node *leader = ir_valueset_lookup(leaderset, value);
851 /* we cannot find this value in antic_in, because the value
852 has (possibly) changed! */
853 pred_trans = get_translated(pred_block, leader);
858 ir_node *mem = get_Div_mem(node);
863 pred_trans = get_Div_mem(node);
867 DB((dbg, LEVEL_3, "trans %+F of %+F is %+F\n", leader, pred_block, pred_trans));
868 if (pred_trans == NULL) {
871 new_pred = pred_trans;
873 /* loads: Predecessor is a memory phi, which translated yields a proj or
874 another phi. In case of projection and a load predecessor,
875 skip them and use the loads memory. */
876 if (is_Proj(pred_trans) && get_irn_mode(pred_trans) == mode_M) {
878 ir_node *loadstore = get_Proj_pred(pred_trans);
879 /* If we do not translate this node, we will get its value wrong. */
882 if (is_Load(loadstore)) {
883 /* Put new load under the adjacent loads memory edge
884 such that GVN may compare them. */
885 new_pred = get_Load_mem(loadstore);
886 } else if (is_Store(loadstore)) {
887 new_pred = get_Store_mem(loadstore);
891 /* predecessor value changed, so translation is needed */
892 if (identify(new_pred) != identify(pred))
897 DB((dbg, LEVEL_4, "in %+F\n", new_pred));
904 DB((dbg, LEVEL_3, "Translate\n"));
907 pred_block = get_nodes_block(in[0]);
909 /* copy node to represent the new value.
910 We do not translate nodes that do not need translation,
911 so we use the newly created nodes as value representatives only.
912 Their block is not important, because we create new ones during
913 the insert node phase. */
915 get_irn_dbg_info(node),
922 /* We need the attribute copy here, because the Hash value of a
923 node might depend on it. */
924 copy_node_attr(environ->graph, node, nn);
925 /* Optimizing nn here is tempting but might be against the GVN-PRE algorithm
926 because it already uses availability. */
928 DB((dbg, LEVEL_3, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
933 * Block-walker, computes Antic_in(block).
934 * Builds a value tree out of the graph by translating values
937 * @param block the block
938 * @param ctx the walker environment
940 static void compute_antic(ir_node *block, void *ctx)
942 pre_env *env = (pre_env*)ctx;
943 block_info *succ_info;
949 ir_valueset_iterator_t iter;
952 /* filter blocks from topological walker */
953 if (! is_Block(block))
956 /* the end block has no successor */
957 if (block == env->end_block)
960 info = get_block_info(block);
962 size = ir_valueset_size(info->antic_in);
963 n_succ = get_Block_n_cfg_outs(block);
966 if (env->first_iter) {
968 /* keep antic_in of infinite loops empty */
969 if (! is_in_infinite_loop(block)) {
970 foreach_valueset(info->exp_gen, value, expr, iter) {
971 ir_valueset_insert(info->antic_in, value, expr);
975 foreach_valueset(info->exp_gen, value, expr, iter) {
976 ir_valueset_insert(info->antic_in, value, expr);
981 /* successor might have phi nodes */
982 if (n_succ == 1 && get_irn_arity(get_Block_cfg_out(block, 0)) > 1) {
983 succ = get_Block_cfg_out(block, 0);
984 int pos = get_Block_cfgpred_pos(succ, block);
985 succ_info = get_block_info(succ);
987 /* initialize translated set */
988 if (env->first_iter) {
989 info->trans = XMALLOC(ir_nodehashmap_t);
990 ir_nodehashmap_init(info->trans);
993 foreach_valueset(succ_info->antic_in, value, expr, iter) {
994 ir_node *trans = get_translated(block, expr);
995 ir_node *trans_value;
999 trans = phi_translate(expr, succ, pos, get_block_info(succ)->antic_in);
1001 /* create new value if necessary */
1002 trans_value = identify_or_remember(trans);
1004 DB((dbg, LEVEL_3, "Translate %+F %+F to %d = %+F (%+F)\n", expr, succ, pos, trans, trans_value));
1006 /* On value change (phi present) we need the translated node
1007 to represent the new value for possible further translation. */
1008 if (value != trans_value)
1013 if (is_clean_in_block(expr, block, info->antic_in)) {
1015 /* Prevent information flow over the backedge of endless loops. */
1016 if (env->iteration <= 2 || (is_backedge(succ, pos) && !is_in_infinite_loop(succ))) {
1017 ir_valueset_replace(info->antic_in, trans_value, represent);
1020 ir_valueset_replace(info->antic_in, trans_value, represent);
1023 set_translated(info->trans, expr, represent);
1026 } else if (n_succ > 1) {
1028 ir_node *common = NULL;
1029 ir_node *succ0 = get_Block_cfg_out(block, 0);
1030 block_info *succ0_info = get_block_info(succ0);
1032 /* disjoint of antic_ins */
1033 foreach_valueset(succ0_info->antic_in, value, expr, iter) {
1034 /* iterate over remaining successors */
1035 for (i = 1; i < n_succ; ++i) {
1036 ir_node *succ = get_Block_cfg_out(block, i);
1037 block_info *succ_info = get_block_info(succ);
1039 /* value in antic_in? */
1040 common = ir_valueset_lookup(succ_info->antic_in, value);
1045 if (common && is_clean_in_block(expr, block, info->antic_in))
1046 ir_valueset_replace(info->antic_in, value, expr);
1051 DEBUG_ONLY(dump_value_set(info->antic_in, "Antic_in", block);)
1053 if (size != ir_valueset_size(info->antic_in))
1057 /* --------------------------------------------------------
1058 * Main algorithm Avail_out
1059 * --------------------------------------------------------
1063 * Computes Avail_out(block):
1065 * Avail_in(block) = Avail_out(dom(block))
1066 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
1069 * This function must be called in the top-down topological order:
1070 * Then it computes Leader(Nodes(block)) instead of Nodes(block) !
1072 * @param block the block
1073 * @param ctx walker context
1075 static void compute_avail_top_down(ir_node *block, void *ctx)
1077 pre_env *env = (pre_env*)ctx;
1080 if (block == env->end_block)
1083 info = get_block_info(block);
1085 /* Add all nodes from the immediate dominator.
1086 This ensures that avail_out contains the leader. */
1087 if (block != env->start_block) {
1088 ir_node *dom_block = get_Block_idom(block);
1089 block_info *dom_info = get_block_info(dom_block);
1092 ir_valueset_iterator_t iter;
1094 foreach_valueset(dom_info->avail_out, value, expr, iter)
1095 /* replace: use the leader from dominator, not local exp_gen */
1096 ir_valueset_replace(info->avail_out, value, expr);
1099 DEBUG_ONLY(dump_value_set(info->avail_out, "Avail_out", block);)
1102 /* --------------------------------------------------------
1103 * Main algorithm redundancy detection
1104 * --------------------------------------------------------
1108 * Returns a valid mode if the value of expr is a partially redundant value.
1110 * @param block the block
1111 * @param expr the expression
1113 * @return mode of the expression if it is partially redundant else NULL
1115 static ir_mode *is_partially_redundant(ir_node *block, ir_node *expr, ir_node *value)
1117 ir_node *first_avail = NULL;
1119 int arity = get_irn_arity(block);
1120 int fully_redundant = 1;
1121 int partially_redundant = 0;
1122 ir_mode *mode = NULL;
1124 DB((dbg, LEVEL_3, "is partially redundant %+F(%+F) of %+F\n", expr, value, block));
1126 /* for each predecessor blocks */
1127 for (pos = 0; pos < arity; ++pos) {
1128 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
1129 block_info *pred_info;
1130 ir_node *trans_expr;
1131 ir_node *trans_value;
1132 ir_node *avail_expr;
1134 pred_info = get_block_info(pred_block);
1135 trans_expr = get_translated(pred_block, expr);
1136 trans_value = identify(trans_expr);
1138 if (is_Const(trans_expr))
1139 avail_expr = trans_expr;
1141 avail_expr = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
1143 /* value might be available through a not yet existing constant */
1144 if (avail_expr == NULL && is_Const(trans_expr)) {
1145 /* limit range of new constants */
1146 ir_mode *cmode = get_irn_mode(trans_expr);
1147 ir_tarval *upper = new_tarval_from_long(127, cmode);
1148 ir_tarval *lower = new_tarval_from_long(-127, cmode);
1149 ir_tarval *c = get_Const_tarval(trans_expr);
1151 /* tarval within range? */
1152 if (tarval_cmp(lower, c) == ir_relation_less_equal &&
1153 tarval_cmp(c, upper) == ir_relation_less_equal) {
1154 avail_expr = trans_expr;
1160 DB((dbg, LEVEL_3, "avail_expr %+F trans_expr %+F\n", avail_expr, trans_expr));
1162 if (avail_expr == NULL) {
1163 pred_info->avail = trans_expr;
1164 pred_info->found = 0;
1165 fully_redundant = 0;
1167 /* expr is available, use the leader */
1168 pred_info->avail = avail_expr;
1169 pred_info->found = 1;
1170 mode = get_irn_mode(avail_expr);
1171 partially_redundant = 1;
1173 if (first_avail == NULL)
1174 first_avail = avail_expr;
1175 else if (first_avail != avail_expr)
1176 /* Multiple different expressions are available,
1177 This is why we need no cut over avail_out sets. */
1178 fully_redundant = 0;
1180 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, avail_expr, pred_block));
1184 /* If it is not the same value already existing along every predecessor
1185 and it is defined by some predecessor then it is partially redundant. */
1186 if (! partially_redundant || fully_redundant)
1192 * Updates the new_set of a block by adding the new_set of
1193 * the immediate dominating block.
1197 static void update_new_set(ir_node *block, ir_node *idom)
1201 ir_valueset_iterator_t iter;
1202 block_info *curr_info = get_block_info(block);
1203 block_info *idom_info = get_block_info(idom);
1206 DEBUG_ONLY(dump_value_set(idom_info->new_set, "[New Set]", idom);)
1207 foreach_valueset(idom_info->new_set, value, expr, iter) {
1208 /* inherit new_set from immediate dominator */
1209 ir_valueset_insert(curr_info->new_set, value, expr);
1210 /* replace in avail_out */
1211 updated |= ir_valueset_replace(curr_info->avail_out, value, expr);
1213 #ifdef DEBUG_libfirm
1215 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
1220 * Checks if hoisting irn is greedy.
1221 * Greedy hoisting means that there are non partially redundant nodes
1222 * hoisted. This happens if a partially redundant node has
1223 * non redundant predecessors.
1225 static unsigned is_hoisting_greedy(ir_node *irn, ir_node *block)
1227 int block_arity = get_irn_arity(block);
1228 int arity = get_irn_arity(irn);
1230 block_info *info = get_block_info(block);
1232 /* As long as the predecessor values are available in all predecessor blocks,
1233 we can hoist this value. */
1234 for (pos = 0; pos < block_arity; ++pos) {
1235 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
1236 block_info *pred_info = get_block_info(pred_block);
1238 for (i = 0; i < arity; ++i) {
1239 ir_node *pred = get_irn_n(irn, i);
1247 /* Very conservative min cut. Phi might only have 1 user. */
1248 if (is_Phi(pred) && get_irn_n_edges(pred) != 1)
1252 if (is_Phi(pred) && get_nodes_block(pred) == block)
1255 DB((dbg, LEVEL_3, "pred %+F\n", pred));
1256 value = identify(pred);
1257 leader = ir_valueset_lookup(info->antic_in, value);
1260 DB((dbg, LEVEL_3, "lead %+F\n", leader));
1261 trans = get_translated(pred_block, leader);
1264 DB((dbg, LEVEL_3, "trans %+F\n", trans));
1266 trans_val = identify(trans);
1267 DB((dbg, LEVEL_3, "value %+F\n", trans_val));
1269 if (is_Const(trans_val) || is_SymConst(trans_val)) {
1270 /* existing constant */
1271 if (get_irn_idx(trans_val) < environ->last_idx) {
1274 /* limit range of new constants */
1275 ir_mode *cmode = get_irn_mode(trans);
1276 ir_tarval *upper = new_tarval_from_long(128, cmode);
1277 ir_tarval *lower = new_tarval_from_long(-128, cmode);
1278 ir_tarval *c = get_Const_tarval(trans);
1280 /* tarval within range? */
1281 if (tarval_cmp(lower, c) == ir_relation_less &&
1282 tarval_cmp(c, upper) == ir_relation_less) {
1291 if (is_irn_constlike(trans_val))
1294 avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
1296 DB((dbg, LEVEL_3, "avail %+F\n", avail));
1300 /* only optimize if predecessors have been optimized */
1301 if (ir_valueset_lookup(info->antic_done, value) == NULL)
1310 * Perform insertion of partially redundant values.
1311 * For every block node, do the following:
1312 * 1. Propagate the NEW_SETS of the dominator into the current block.
1313 * If the block has multiple predecessors,
1314 * 2a. Iterate over the ANTIC expressions for the block to see if
1315 * any of them are partially redundant.
1316 * 2b. If so, insert them into the necessary predecessors to make
1317 * the expression fully redundant.
1318 * 2c. Insert a new Phi merging the values of the predecessors.
1319 * 2d. Insert the new Phi, and the new expressions, into the
1322 * @param block the block
1323 * @param ctx the walker environment
1325 static void insert_nodes_walker(ir_node *block, void *ctx)
1327 pre_env *env = (pre_env*)ctx;
1328 int arity = get_irn_arity(block);
1334 ir_valueset_iterator_t iter;
1337 if (! is_Block(block))
1340 /* ensure that even the start block has a new_set */
1341 info = get_block_info(block);
1343 ir_valueset_del(info->new_set);
1344 info->new_set = ir_valueset_new(16);
1346 if (block == env->start_block)
1349 DB((dbg, LEVEL_2, "Insert operation of %+F\n", block));
1351 idom = get_Block_idom(block);
1352 update_new_set(block, idom);
1354 /* process only path joining blocks */
1359 /* This is the main reason antic_in is preverred over antic_out;
1360 we may iterate over every anticipated value first and not
1361 over the predecessor blocks. */
1362 foreach_valueset(info->antic_in, value, expr, iter) {
1368 if (ir_valueset_lookup(info->antic_done, value))
1371 /* filter phi nodes from antic_in */
1375 DB((dbg, LEVEL_2, "Insert for %+F (value %+F) in %+F\n", expr, value, block));
1377 /* A value computed in the dominator is totally redundant.
1378 Hence we have nothing to insert. */
1379 if (ir_valueset_lookup(get_block_info(idom)->avail_out, value)) {
1380 DB((dbg, LEVEL_2, "Fully redundant expr %+F value %+F\n", expr, value));
1381 DEBUG_ONLY(inc_stats(gvnpre_stats->fully);)
1383 ir_valueset_insert(info->antic_done, value, expr);
1387 if (is_hoisting_greedy(expr, block)) {
1388 DB((dbg, LEVEL_2, "greedy\n"));
1392 mode = is_partially_redundant(block, expr, value);
1396 #if LOADS || DIVMODS
1397 /* save old mode_M phis to remove keepalive edges later */
1398 if (is_memop(expr)) {
1399 ir_node *mem = get_memop_mem(expr);
1400 if (is_Phi(mem) && get_nodes_block(mem) == get_nodes_block(expr)) {
1401 ir_nodeset_insert(env->keeps, mem);
1406 #ifdef DEBUG_libfirm
1407 if (! is_Proj(expr)) {
1408 if (env->first_iter)
1409 inc_stats(gvnpre_stats->first_iter_found);
1410 inc_stats(gvnpre_stats->partially);
1412 if (is_Load(expr) || is_Store(expr))
1413 inc_stats(gvnpre_stats->loads);
1414 else if (is_Div(expr) || is_Mod(expr))
1415 inc_stats(gvnpre_stats->divmods);
1418 phi_in = XMALLOCN(ir_node *, arity);
1420 /* for each predecessor block */
1421 for (pos = 0; pos < arity; ++pos) {
1422 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
1423 block_info *pred_info;
1425 pred_info = get_block_info(pred_block);
1427 if (! pred_info->found) {
1429 int node_arity = get_irn_arity(expr);
1430 ir_node **in = XMALLOCNZ(ir_node *, node_arity);
1432 ir_node *new_value, *new_value2;
1433 ir_node *target_block = pred_block;
1435 for (i = 0; i < node_arity; ++i) {
1436 ir_node *pred = get_irn_n(expr, i);
1437 ir_node *value = identify(pred);
1443 /* transform knowledge over the predecessor from
1444 anti-leader world into leader world. */
1446 DB((dbg, LEVEL_3, "pred %+F\n", pred));
1447 value = identify(pred);
1449 /* get leader for pred to lookup its translated value */
1450 leader = ir_valueset_lookup(info->antic_in, value);
1453 DB((dbg, LEVEL_3, "lead %+F\n", leader));
1455 trans = get_translated(pred_block, leader);
1458 DB((dbg, LEVEL_3, "trans %+F\n", trans));
1460 /* in case of phi, we are done */
1461 if (is_Phi(pred) && get_nodes_block(pred) == block) {
1466 trans_val = identify(trans);
1467 DB((dbg, LEVEL_3, "value %+F\n", trans_val));
1469 /* constants are always available but not in avail set */
1470 if (is_irn_constlike(trans_val)) {
1476 In case of loads we need to make sure the hoisted
1477 loads are found despite their unique value. */
1478 avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
1479 DB((dbg, LEVEL_3, "avail %+F\n", avail));
1481 assert(avail && "predecessor has to be available");
1486 target_block = get_nodes_block(in[0]);
1488 /* Copy node to represent the new value.
1489 We use translated nodes as value representatives only.
1490 They have anti leaders as predecessors, not leaders!
1491 So we have to create a new node using leaders. */
1492 trans = new_ir_node(
1493 get_irn_dbg_info(expr),
1498 get_irn_arity(expr),
1501 /* We need the attribute copy here, because the Hash value of a
1502 node might depend on it. */
1503 copy_node_attr(environ->graph, expr, trans);
1505 /* value is now available in target block through trans
1506 insert (not replace) because it has not been available */
1507 new_value = identify_or_remember(trans);
1508 ir_valueset_insert(pred_info->avail_out, new_value, trans);
1509 DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value));
1511 new_value2 = identify(get_translated(pred_block, expr));
1512 ir_valueset_insert(pred_info->avail_out, new_value2, trans);
1513 DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value2));
1515 DB((dbg, LEVEL_3, "Use new %+F in %+F because %+F(%+F) not available\n", trans, pred_block, expr, value));
1517 phi_in[pos] = trans;
1519 /* value available */
1520 phi_in[pos] = pred_info->avail;
1522 DB((dbg, LEVEL_3, "phi_in %+F\n", phi_in[pos]));
1525 /* We do not connect tuples as they will be connected automatically
1526 by the corresponding projections. */
1527 if (get_irn_mode(expr) != mode_T) {
1529 phi = new_r_Phi(block, arity, phi_in, mode);
1530 DB((dbg, LEVEL_3, "New %+F for redundant %+F created\n", phi, expr));
1532 /* This value is now available through the new phi.
1533 insert || replace in avail_out */
1534 ir_valueset_replace(info->avail_out, value, phi);
1535 ir_valueset_insert(info->new_set, value, phi);
1539 /* already optimized this value in this block */
1540 ir_valueset_insert(info->antic_done, value, expr);
1546 static void update_new_set_walker(ir_node *block, void *ctx)
1548 pre_env *env = (pre_env*)ctx;
1550 if (! is_Block(block))
1552 if (block == env->start_block)
1555 update_new_set(block, get_Block_idom(block));
1559 * Domtree block walker to insert nodes with dying operands
1560 * into the highest possible block whilst still being anticipated.
1562 static void hoist_high(ir_node *block, void *ctx)
1566 block_info *curr_info;
1567 ir_valueset_iterator_t iter;
1570 int arity = get_irn_arity(block);
1572 if (! is_Block(block))
1575 curr_info = get_block_info(block);
1577 if (curr_info->new_set)
1578 ir_valueset_del(curr_info->new_set);
1579 curr_info->new_set = ir_valueset_new(16);
1584 DB((dbg, LEVEL_2, "High hoisting %+F\n", block));
1586 /* foreach entry optimized by insert node phase */
1587 foreach_valueset(curr_info->antic_done, value, expr, iter) {
1590 /* TODO currently we cannot handle load and their projections */
1591 if (is_memop(expr) || is_Proj(expr))
1594 DB((dbg, LEVEL_4, "leader %+F value %+F\n", expr, value));
1596 /* visit hoisted expressions */
1597 for (pos = 0; pos < arity; ++pos) {
1598 /* standard target is predecessor block */
1599 ir_node *target = get_Block_cfgpred_block(block, pos);
1600 block_info *pred_info = get_block_info(target);
1602 ir_node *new_target;
1603 ir_node *trans_expr;
1604 ir_node *trans_value;
1608 unsigned nest_depth;
1609 block_info *dom_info;
1611 /* get phi translated value */
1612 trans_expr = get_translated(target, expr);
1613 trans_value = identify(trans_expr);
1614 avail = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
1616 /* get the used expr on this path */
1618 /* TODO when does this happen? */
1622 avail_arity = get_irn_arity(avail);
1623 value = identify(avail);
1625 /* anticipation border */
1627 nest_depth = get_loop_depth(get_irn_loop(target));
1629 /* Either push the hoisted nodes up their path,
1630 or try to put them directly into their common dominator. */
1632 /* By using block (instead of target) as initial block,
1633 we only allow hoisting into a common block of
1634 both predecessor blocks. */
1640 while (dom && dom != get_Block_idom(block)) {
1642 dom = get_Block_idom(dom);
1643 dom_info = get_block_info(dom);
1644 DB((dbg, LEVEL_4, "testing dom %+F\n", dom));
1646 /* TODO Being in antic_in means hoistable above block,
1647 but we need 'hoistable into block'.
1648 This could be achieved by a flag for each valueset pair,
1649 being set during antic computation. */
1651 /* check if available node ist still anticipated and clean */
1652 if (! ir_valueset_lookup(dom_info->antic_in, value)) {
1653 DB((dbg, LEVEL_4, "%+F not antic in %+F\n", value, dom));
1657 nest_depth = get_loop_depth(get_irn_loop(dom));
1659 /* do not hoist into loops */
1660 if (get_loop_depth(get_irn_loop(dom)) > nest_depth) {
1661 DB((dbg, LEVEL_4, "%+F deeper nested\n", dom));
1662 /* not a suitable location */
1666 /* check if operands die */
1668 /* check for uses on current path */
1669 for (i = 0; i < avail_arity; i++) {
1670 ir_node *pred = get_irn_n(avail, i);
1671 ir_node *pred_value = identify(pred);
1676 DB((dbg, LEVEL_4, "testing pred %+F\n", pred));
1678 if (! ir_valueset_lookup(dom_info->avail_out, pred_value)) {
1679 DB((dbg, LEVEL_4, "pred %+F not available\n", pred));
1684 /* check every successor */
1685 foreach_out_edge(pred, edge) {
1686 ir_node *succ = get_edge_src_irn(edge);
1687 DB((dbg, LEVEL_4, "testing succ %+F\n", succ));
1689 /* check only successors on current path to end */
1690 if (block_dominates(dom, get_nodes_block(succ))) {
1691 ir_node *succ_value = identify(succ);
1693 /* Do we have another user than avail?
1694 Then predecessor is not dead after removal of avail. */
1695 if (succ_value != value) {
1696 DB((dbg, LEVEL_4, "still used in %+F\n", succ));
1707 /* only try common dominator */
1712 /* put node into new target block */
1714 block_info *target_info = get_block_info(new_target);
1715 int nn_arity = get_irn_arity(avail);
1716 ir_node **in = XMALLOCN(ir_node *, nn_arity);
1720 DB((dbg, LEVEL_2, "Hoisting %+F into %+F\n", avail, new_target));
1721 DEBUG_ONLY(inc_stats(gvnpre_stats->hoist_high);)
1723 for (i = 0; i < nn_arity; ++i) {
1724 ir_node *pred = get_irn_n(avail, i);
1725 ir_node *avail_pred = ir_valueset_lookup(target_info->avail_out, identify(pred));
1730 get_irn_dbg_info(avail),
1734 get_irn_mode(avail),
1739 identify_or_remember(nn);
1740 /* TODO Nodes are inserted into a dominating block and should
1741 be available from this point on. Currently we do not push
1742 the availability information through during the walk. */
1743 ir_valueset_insert(target_info->new_set, value, nn);
1744 ir_valueset_insert(target_info->avail_out, value, nn);
1751 /* --------------------------------------------------------
1752 * Elimination of fully redundant nodes
1753 * --------------------------------------------------------
1757 * Walker which finds redundant nodes using avail_out sets
1758 * and exchanges them for existing ones.
1759 * We cannot change the graph here as this would affect
1760 * the hash values of the nodes.
1762 * @param irn the node
1763 * @param ctx the walker environment
1765 static void eliminate(ir_node *irn, void *ctx)
1767 pre_env *env = (pre_env*)ctx;
1769 if (! is_Block(irn)) {
1770 ir_node *block = get_nodes_block(irn);
1771 block_info *info = get_block_info(block);
1772 ir_node *value = identify(irn);
1774 if (value != NULL) {
1775 ir_node *expr = (ir_node*)ir_valueset_lookup(info->avail_out, value);
1776 DB((dbg, LEVEL_3, "Elim %+F(%+F) avail %+F\n", irn, value, expr));
1778 if (expr != NULL && expr != irn) {
1779 elim_pair *p = OALLOC(&env->obst, elim_pair);
1783 p->next = env->pairs;
1784 if (get_irn_idx(expr) > env->last_idx)
1785 p->reason = FS_OPT_GVN_PARTLY;
1787 p->reason = FS_OPT_GVN_FULLY;
1789 DEBUG_ONLY(inc_stats(gvnpre_stats->replaced);)
1796 * Do all the recorded changes and optimize
1797 * newly created Phi's.
1799 * @param pairs list of elimination pairs
1801 static void eliminate_nodes(elim_pair *pairs, ir_nodeset_t *keeps)
1804 ir_node *end = environ->end_node;
1806 for (p = pairs; p != NULL; p = p->next) {
1807 /* might be already changed */
1808 p->new_node = skip_Id(p->new_node);
1810 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
1812 /* PRE tends to create Phi(self, self, ... , x, self, self, ...)
1813 * which we can optimize here */
1814 if (is_Phi(p->new_node)) {
1816 ir_node *res = NULL;
1818 for (i = get_irn_arity(p->new_node) - 1; i >= 0; --i) {
1819 ir_node *pred = get_irn_n(p->new_node, i);
1821 if (pred != p->old_node) {
1830 exchange(p->new_node, res);
1834 DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
1836 exchange(p->old_node, p->new_node);
1839 /* remove keep alive edges of unused mode_M phis */
1840 foreach_ir_nodeset(keeps, m_phi, iter) {
1841 remove_End_keepalive(end, m_phi);
1846 /* --------------------------------------------------------
1848 * --------------------------------------------------------
1852 * Gvn_Pre algorithm.
1854 * @param irg the graph
1855 * @param env the environment
1857 static void gvn_pre(ir_graph *irg, pre_env *env)
1859 unsigned antic_iter;
1860 unsigned insert_iter;
1862 DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg));
1864 /* allocate block info */
1865 irg_walk_blkwise_graph(irg, block_info_walker, NULL, env);
1867 ir_nodehashmap_init(&value_map);
1869 /* generate exp_gen */
1870 irg_walk_blkwise_graph(irg, NULL, topo_walker, env);
1871 dump_all_expgen_sets(env->list);
1873 /* compute the avail_out sets for all blocks */
1874 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, env);
1876 /* compute the anticipated value sets for all blocks */
1878 env->first_iter = 1;
1881 /* antic_in passes */
1884 DB((dbg, LEVEL_2, "= Antic_in Iteration %d ========================\n", antic_iter));
1886 irg_walk_blkwise_graph(irg, compute_antic, NULL, env);
1887 env->first_iter = 0;
1888 DB((dbg, LEVEL_2, "----------------------------------------------\n"));
1890 } while (env->changes != 0 && antic_iter < MAX_ANTIC_ITER);
1892 DEBUG_ONLY(set_stats(gvnpre_stats->antic_iterations, antic_iter);)
1894 ir_nodeset_init(env->keeps);
1896 env->first_iter = 1;
1897 /* compute redundant expressions */
1900 DB((dbg, LEVEL_2, "= Insert Iteration %d ==========================\n", insert_iter));
1902 /* TODO topologically top down would be better; fewer iterations. */
1903 dom_tree_walk_irg(irg, insert_nodes_walker, NULL, env);
1904 env->first_iter = 0;
1905 DB((dbg, LEVEL_2, "----------------------------------------------\n"));
1906 } while (env->changes != 0 && insert_iter < MAX_INSERT_ITER);
1907 DEBUG_ONLY(set_stats(gvnpre_stats->insert_iterations, insert_iter);)
1910 /* An attempt to reduce lifetimes by hoisting already hoisted values
1911 even higher if their operands die. */
1912 dom_tree_walk_irg(irg, hoist_high, NULL, NULL);
1913 /* update avail_out for elimination */
1914 dom_tree_walk_irg(irg, update_new_set_walker, NULL, env);
1917 /* Deactivate edges to prevent intelligent removal of nodes,
1918 or else we will get deleted nodes which we try to exchange. */
1919 edges_deactivate(environ->graph);
1921 /* eliminate nodes */
1922 irg_walk_graph(irg, NULL, eliminate, env);
1923 eliminate_nodes(env->pairs, env->keeps);
1925 ir_nodeset_destroy(env->keeps);
1929 * Gvn_Pre pass for graph irg.
1931 * @param irg the graph
1933 void do_gvn_pre(ir_graph *irg)
1937 optimization_state_t state;
1938 block_info *block_info;
1940 /* bads and unreachables cause too much trouble with dominance,
1941 loop info for endless loop detection,
1942 no critical edges is PRE precondition
1944 assure_irg_properties(irg,
1945 IR_GRAPH_PROPERTY_NO_BADS
1946 | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
1947 | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO
1948 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
1949 | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
1950 | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
1952 /* register a debug mask */
1953 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
1955 save_optimization_state(&state);
1956 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_LOOP_LINK);
1958 edges_activate(irg);
1961 DEBUG_ONLY(init_stats();)
1963 /* setup environment */
1966 env.start_block = get_irg_start_block(irg);
1967 env.end_block = get_irg_end_block(irg);
1968 env.end_node = get_irg_end(irg);
1971 env.last_idx = get_irg_last_idx(irg);
1972 obstack_init(&env.obst);
1974 /* Detect and set links of infinite loops to non-zero. */
1978 new_identities(irg);
1979 env.value_table = irg->value_table;
1980 irg->value_table = NULL;
1983 /* Switch on GCSE. We need it to correctly compute
1984 the value of a node, which is independent from
1986 set_opt_global_cse(1);
1987 /* new_identities() */
1988 if (irg->value_table != NULL)
1989 del_pset(irg->value_table);
1990 /* initially assumed nodes in pset are 512 */
1991 irg->value_table = new_pset(compare_gvn_identities, 512);
1993 env.gvnpre_values = irg->value_table;
1996 /* do GVN-PRE pass */
1998 DEBUG_ONLY(print_stats();)
2000 /* clean up: delete all sets */
2001 for (block_info = env.list; block_info != NULL; block_info = block_info->next) {
2002 free_block_info(block_info);
2005 DEBUG_ONLY(free_stats();)
2006 ir_nodehashmap_destroy(&value_map);
2007 obstack_free(&env.obst, NULL);
2008 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_LOOP_LINK);
2010 /* Pin the graph again.
2011 This is needed due to the use of set_opt_global_cse(1) */
2012 set_irg_pinned(irg, op_pin_state_pinned);
2013 restore_optimization_state(&state);
2014 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
2017 irg->value_table = env.value_table;
2018 del_pset(irg->value_table);
2019 irg->value_table = env.gvnpre_values;
2022 /* TODO There seem to be optimizations that try to use the existing
2024 new_identities(irg);
2026 /* TODO assure nothing else breaks. */
2027 set_opt_global_cse(0);
2028 edges_activate(irg);
2031 /* Creates an ir_graph pass for do_gvn_pre. */
2032 ir_graph_pass_t *do_gvn_pre_pass(const char *name)
2034 return def_graph_pass(name ? name : "gvn_pre", do_gvn_pre);