2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Global Value Numbering Partial Redundancy Elimination
23 * (VanDrunen Hosking 2004)
24 * @author Michael Beck
37 #include "irnodehashmap.h"
38 #include "irnodeset.h"
39 #include "iropt_dbg.h"
40 #include "iroptimize.h"
45 #include "firmstat_t.h"
47 #include "irgraph_t.h"
52 /* suggested by GVN-PRE authors */
53 #define MAX_ANTIC_ITER 10
54 #define MAX_INSERT_ITER 3
56 /* Stops antic iteration from processing endless loops. */
57 #define IGNORE_INF_LOOPS 1
58 /* Stops antic information to flow over infinite loop backedge */
59 #define NO_INF_LOOPS 0
61 /* Attempt to reduce register pressure and reduce code size
66 /* Seamless implementation of handling loads and generally memory
67 dependent nodes with GVN-PRE. */
73 /* Only optimize node directly after phi node if node is only successor. */
76 /* GVN is very limited. This enables optimize_node during value recognition.
77 GVN ist still very limited, since a+1+b+1 doesn't equal a+b+2.
78 TODO Broken for yet unknown reasons. */
79 #define OPTIMIZE_NODES 0
82 /** Additional info we need for every block. */
83 typedef struct block_info {
84 ir_valueset_t *exp_gen; /* contains this blocks clean expressions */
85 ir_valueset_t *avail_out; /* available values at block end */
86 ir_valueset_t *antic_in; /* clean anticipated values at block entry */
87 ir_valueset_t *antic_done; /* keeps elements of antic_in after insert nodes phase */
88 ir_valueset_t *new_set; /* new by hoisting made available values */
89 ir_nodehashmap_t *trans; /* contains translated nodes translated into block */
90 ir_node *avail; /* saves available node for insert node phase */
91 int found; /* saves kind of availability for insert_node phase */
92 ir_node *block; /* block of the block_info */
93 struct block_info *next; /* links all instances for easy access */
97 * A pair of nodes to be exchanged.
98 * We have to defer the exchange because there are still needed references
101 typedef struct elim_pair {
102 ir_node *old_node; /* node that will be replaced */
103 ir_node *new_node; /* replacement for old_node */
104 struct elim_pair *next; /* links all instances for easy access */
105 int reason; /* reason for the replacement */
108 /** environment for the GVN-PRE algorithm */
109 typedef struct pre_env {
110 ir_graph *graph; /* current graph */
111 struct obstack *obst; /* obstack to allocate on */
112 ir_node *start_block; /* start block of the current graph */
113 ir_node *end_block; /* end block of the current graph */
114 ir_node *end_node; /* end node of the current graph */
115 block_info *list; /* block_info list head */
116 elim_pair *pairs; /* elim_pair list head */
117 ir_nodeset_t *keeps; /* a list of to be removed phis to kill their keep alive edges */
118 unsigned last_idx; /* last node index of input graph */
119 char changes; /* flag for fixed point iterations - non-zero if changes occurred */
120 char first_iter; /* non-zero for first fixed point iteration */
121 int iteration; /* iteration counter */
123 pset *value_table; /* standard value table*/
124 pset *gvnpre_values; /* gvnpre value table */
128 static pre_env *environ;
130 /* custom GVN value map */
131 static ir_nodehashmap_t value_map;
133 /* debug module handle */
134 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
138 /* --------------------------------------------------------
140 * --------------------------------------------------------
143 typedef struct gvnpre_statistics {
150 int first_iter_found;
151 int antic_iterations;
152 int insert_iterations;
156 static gvnpre_statistics *gvnpre_stats = NULL;
158 static void init_stats(void)
160 gvnpre_stats = XMALLOCZ(gvnpre_statistics);
163 static void free_stats(void)
169 static void print_stats(void)
171 gvnpre_statistics *stats = gvnpre_stats;
172 DB((dbg, LEVEL_1, "replaced : %d\n", stats->replaced));
173 DB((dbg, LEVEL_1, "antic_in iterations : %d\n", stats->antic_iterations));
174 DB((dbg, LEVEL_1, "insert iterations : %d\n", stats->insert_iterations));
175 DB((dbg, LEVEL_1, "infinite loops : %d\n", stats->infinite_loops));
176 DB((dbg, LEVEL_1, "fully redundant : %d\n", stats->fully));
177 DB((dbg, LEVEL_1, "partially redundant : %d\n", stats->partially));
178 DB((dbg, LEVEL_1, " loads : %d\n", stats->loads));
179 DB((dbg, LEVEL_1, " Divs/Mods : %d\n", stats->divmods));
180 DB((dbg, LEVEL_1, " hoist high : %d\n", stats->hoist_high));
181 DB((dbg, LEVEL_1, " first iteration : %d\n", stats->first_iter_found));
184 #define set_stats(var, value) (var)=(value)
185 #define inc_stats(var) ((var)+=1)
187 /* --------------------------------------------------------
189 * --------------------------------------------------------
195 * @param set the set to dump
196 * @param txt a text to describe the set
197 * @param block the owner block of the set
199 static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
201 ir_valueset_iterator_t iter;
202 ir_node *value, *expr;
205 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
207 foreach_valueset(set, value, expr, iter) {
209 DB((dbg, LEVEL_2, "\n"));
211 DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
213 DB((dbg, LEVEL_2, " %+F,", expr));
216 DB((dbg, LEVEL_2, "\n}\n"));
217 } /* dump_value_set */
220 * Dump all exp_gen value sets.
222 * @param list the list of block infos to retrieve the sets from
224 static void dump_all_expgen_sets(block_info *list)
226 block_info *block_info;
228 for (block_info = list; block_info != NULL; block_info = block_info->next) {
229 dump_value_set(block_info->exp_gen, "[Exp_gen]", block_info->block);
235 #define dump_all_expgen_sets(list)
236 #define dump_value_set(set, txt, block)
238 #endif /* DEBUG_libfirm */
240 /* --------------------------------------------------------
242 * --------------------------------------------------------
246 * Compares node collisions in valuetable.
247 * Modified identities_cmp().
249 static int compare_gvn_identities(const void *elt, const void *key)
251 ir_node *a = (ir_node *)elt;
252 ir_node *b = (ir_node *)key;
255 if (a == b) return 0;
257 /* phi nodes kill predecessor values and are always different */
258 if (is_Phi(a) || is_Phi(b))
261 /* memops are not the same, even if we want to optimize them
262 we have to take the order in account */
263 if (is_memop(a) || is_memop(b) ||
264 get_irn_mode(a) == mode_T ||
265 get_irn_mode(b) == mode_T) {
266 /* Loads with the same predecessors are the same value;
267 this should only happen after phi translation. */
268 if ((! is_Load(a) || ! is_Load(b)) && (! is_Store(a) || ! is_Store(b)))
272 if ((get_irn_op(a) != get_irn_op(b)) ||
273 (get_irn_mode(a) != get_irn_mode(b))) return 1;
275 /* compare if a's in and b's in are of equal length */
276 irn_arity_a = get_irn_arity(a);
277 if (irn_arity_a != get_irn_arity(b))
280 /* blocks are never the same */
281 if (is_Block(a) || is_Block(b))
284 /* should only be used with gcse enabled */
285 assert(get_opt_global_cse());
287 /* compare a->in[0..ins] with b->in[0..ins] */
288 for (i = 0; i < irn_arity_a; ++i) {
289 ir_node *pred_a = get_irn_n(a, i);
290 ir_node *pred_b = get_irn_n(b, i);
291 if (pred_a != pred_b) {
292 if (!is_irn_cse_neutral(pred_a) || !is_irn_cse_neutral(pred_b))
298 * here, we already now that the nodes are identical except their
301 if (a->op->ops.node_cmp_attr)
302 return a->op->ops.node_cmp_attr(a, b);
308 * Identify does a lookup in the GVN valuetable.
309 * To be used when no new GVN values are to be created.
311 * @param e a node representing an expression
312 * @return a node representing the value
314 static ir_node *identify(ir_node *irn)
316 ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
319 /* irn represents a new value, so return the leader */
320 return identify_remember(irn);
324 * remember() adds node irn to the GVN valuetable.
325 * Identify_remember only identifies values of nodes with the
326 * same predecessor nodes (not values). By creating a node from the predecessor
327 * values/leaders, a true valuetree is built. Phis kill their predecessor value,
328 * so no circular dependencies need to be resolved.
331 * Maybe this could be implemented with a custom node hash that takes
332 * phi nodes and true values (instead of predecessors) into account,
333 * resulting in value numbers.
334 * TODO This unnecessarily also handles nodes like calls, which are never equal.
336 * @param irn a node representing an expression
337 * @return the value of the expression
339 static ir_node *remember(ir_node *irn)
341 int arity = get_irn_arity(irn);
344 ir_node **in = XMALLOCN(ir_node *, arity);
347 for (i = 0; i < arity; ++i) {
348 ir_node *pred = get_irn_n(irn, i);
349 /* value and leader at the same time */
350 ir_node *pred_value = identify(pred);
352 /* phi will be translated anyway, so kill the predecessor values
353 this also prevents circular dependencies */
355 /* every phi represents its own value */
360 /* predecessor is not its value representation/the leader */
361 if (pred != pred_value)
366 if (changed && !is_memop(irn) && get_irn_mode(irn) != mode_X) {
367 /* create representative for */
368 ir_node *nn = new_ir_node(
369 get_irn_dbg_info(irn),
371 get_nodes_block(irn),
376 copy_node_attr(environ->graph, irn, nn);
379 /* TODO optimize_node() uses the valuetable and thus the custom
380 identify_cmp() and will fail trying. */
381 environ->graph->value_table = environ->value_table;
382 nn = optimize_node(nn);
383 environ->graph->value_table = environ->gvnpre_values;
386 /* now the value can be determined because the
387 predecessors are the leaders */
388 value = identify_remember(nn);
390 value = identify_remember(irn);
394 DB((dbg, LEVEL_4, "Remember %+F as value %+F\n", irn, value));
395 ir_nodehashmap_insert(&value_map, irn, value);
401 * When the value map has been built we may lookup expressions
402 * and remember them if new.
404 static ir_node *identify_or_remember(ir_node *irn)
406 ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
410 return remember(irn);
413 /* --------------------------------------------------------
415 * --------------------------------------------------------
419 * Allocate block info for block block.
421 * @param block the block
422 * @param env the environment
424 static void alloc_block_info(ir_node *block, pre_env *env)
426 block_info *info = OALLOC(env->obst, block_info);
428 set_irn_link(block, info);
429 info->exp_gen = ir_valueset_new(16);
430 info->avail_out = ir_valueset_new(16);
431 info->antic_in = ir_valueset_new(16);
432 info->antic_done = ir_valueset_new(16);
433 info->trans = XMALLOC(ir_nodehashmap_t);
434 ir_nodehashmap_init(info->trans);
436 info->new_set = NULL;
441 info->next = env->list;
443 } /* alloc_block_info */
445 static void free_block_info(block_info *block_info)
447 ir_valueset_del(block_info->exp_gen);
448 ir_valueset_del(block_info->avail_out);
449 ir_valueset_del(block_info->antic_in);
450 if (block_info->trans) {
451 ir_nodehashmap_destroy(block_info->trans);
452 free(block_info->trans);
454 if (block_info->new_set)
455 ir_valueset_del(block_info->new_set);
459 * Bottom up walker that ensures that every block gets a block info.
461 * @param irn the node
462 * @param ctx the environment
464 static void block_info_walker(ir_node *irn, void *ctx)
467 pre_env *env = (pre_env*)ctx;
468 alloc_block_info(irn, env);
473 * Returns the block info of a block.
475 static block_info *get_block_info(ir_node *block)
477 return (block_info*)get_irn_link(block);
480 /* --------------------------------------------------------
481 * Infinite loop analysis
482 * --------------------------------------------------------
486 * Walker to set block marks and loop links to 0.
488 static void clear_block_mark_loop_link(ir_node *block, void *env)
492 if (is_Block(block)) {
493 set_Block_mark(block, 0);
494 set_loop_link(get_irn_loop(block), NULL);
499 * Returns non-zero if block is part of real loop loop.
502 static unsigned in_loop(ir_node *block, ir_loop *loop)
504 ir_loop *l = get_irn_loop(block);
505 ir_loop *outer = get_irg_loop(environ->graph);
508 /* loop tree root is not a loop */
509 if (l == NULL || l == outer)
511 l = get_loop_outer_loop(l);
517 * Returns the outermost real loop of loop.
519 static ir_loop *get_loop_outermost(ir_loop *loop)
521 ir_loop *outer = get_irg_loop(environ->graph);
523 ir_loop *last = NULL;
527 l = get_loop_outer_loop(l);
533 * Topologic bottom-up walker sets links of infinite loops to non-zero.
534 * Block marks are used to flag blocks reachable (from end) on the one hand,
535 * on the other hand they are set if the block is not part of an infinite loop.
537 static void infinite_loop_walker(ir_node *block, void *env)
543 if (! is_Block(block))
546 /* start block has no predecessors */
547 if (block == environ->start_block)
550 arity = get_irn_arity(block);
552 /* block not part of a real loop: no infinite loop */
553 if (get_irn_loop(block) == get_irg_loop(environ->graph))
554 set_Block_mark(block, 1);
556 if (get_Block_mark(block)) {
557 /* reachable block: mark all cf predecessors */
558 for (i = 0; i < arity; ++i) {
559 ir_node *pred = get_Block_cfgpred_block(block, i);
562 set_Block_mark(pred, 1);
565 /* We are in a real loop and see an unreachable block. */
566 ir_loop *outermost_loop = get_loop_outermost(get_irn_loop(block));
568 /* flag loop as infinite */
569 set_loop_link(outermost_loop, outermost_loop);
570 DEBUG_ONLY(inc_stats(gvnpre_stats->infinite_loops);)
572 /* The cf predecessors are unreachable, but can never be part of
573 an infinite loop, because we just reached them. So we set the
574 blockmark to prevent triggering the infinite loop detection. */
576 /* passing information to the cf predecessors */
577 for (i = 0; i < arity; ++i) {
578 ir_node *pred = get_Block_cfgpred_block(block, i);
583 /* If our cf predecessor is in the same endless loop,
584 it is also unreachable. */
585 if (in_loop(pred, outermost_loop)) {
586 set_Block_mark(pred, 0);
588 /* When we leave the unreachable loop, we artificially
589 declare the cf predecessor reachable. */
590 set_Block_mark(pred, 1);
597 * Sets loop links of outermost infinite loops to non-zero.
599 static void analyse_loops(ir_graph *irg)
601 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
603 /* reset block mark and loop links */
604 irg_walk_blkwise_graph(irg, clear_block_mark_loop_link, NULL, NULL);
606 /* mark end block reachable */
607 set_Block_mark(get_irg_end_block(irg), 1);
608 irg_walk_blkwise_graph(irg, infinite_loop_walker, NULL, NULL);
610 ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
613 #if IGNORE_INF_LOOPS || NO_INF_LOOPS
615 * Returns non-zero if block is part of an infinite loop.
617 static unsigned is_in_infinite_loop(ir_node *block)
621 assert(is_Block(block));
622 loop = get_irn_loop(block);
625 loop = get_loop_outermost(loop);
627 return (get_loop_link(loop) != NULL);
633 /* --------------------------------------------------------
635 * --------------------------------------------------------
639 * Returns non-zero if a node is movable and a possible candidate for PRE.
641 static unsigned is_nice_value(ir_node *n)
643 ir_mode *mode = get_irn_mode(n);
649 if (is_Proj(n) && mode != mode_X && mode != mode_T)
658 return get_Load_volatility(n) == volatility_non_volatile;
660 return get_Store_volatility(n) == volatility_non_volatile;
663 if (get_irn_pinned(n) == op_pin_state_pinned)
666 if (! mode_is_data(mode)) {
667 if (! is_Div(n) && ! is_Mod(n))
674 * Checks if a node n is clean in block block for exp_gen.
677 * @param block the block
678 * @return non-zero value for clean node
680 static unsigned is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *valueset)
687 if (! is_nice_value(n))
691 /* filter loads with no phi predecessor from antic_in */
692 if (is_Load(n) && ! is_Phi(get_Load_mem(n)))
694 if (is_Store(n) && ! is_Phi(get_Store_mem(n)))
700 ir_node *mem = get_Div_mem(n);
704 if (! is_Phi(mem) && ! is_NoMem(mem))
708 if (is_Mod(n) && ! is_Phi(get_Mod_mem(n)))
712 arity = get_irn_arity(n);
713 for (i = 0; i < arity; ++i) {
714 ir_node *pred = get_irn_n(n, i);
720 /* we only handle current block */
721 if (get_nodes_block(pred) != block)
724 if (! is_nice_value(pred))
727 value = identify(pred);
728 if (! ir_valueset_lookup(valueset, value))
736 * Topological walker puts nodes in top-down topological order into exp_gen set.
737 * Assumed to walk blockwise and nodewise topologically top-down.
739 * @param irn the node
740 * @param ctx the environment
742 static void topo_walker(ir_node *irn, void *ctx)
753 environ->graph->value_table = environ->value_table;
754 identify_remember(irn);
755 environ->graph->value_table = environ->gvnpre_values;
758 /* GVN step: remember the value. */
759 value = remember(irn);
761 if (is_irn_constlike(irn))
764 block = get_nodes_block(irn);
765 info = get_block_info(block);
767 if (get_irn_mode(irn) != mode_X)
768 ir_valueset_insert(info->avail_out, value, irn);
770 /* values that are not in antic_in also dont't need to be in any other set */
772 if (! is_nice_value(irn))
775 if (is_clean_in_block(irn, block, info->exp_gen)) {
776 DB((dbg, LEVEL_3, "%+F clean in block %+F\n", irn, block));
778 ir_valueset_insert(info->exp_gen, value, irn);
782 /* --------------------------------------------------------
784 * --------------------------------------------------------
788 * Gets result of nodes phi translation into block.
790 * @param node the node
791 * @param block the target block
793 * @return a phi translation of node node into block block or NULL
795 static ir_node *get_translated(ir_node *block, ir_node *node)
797 if (is_irn_constlike(node))
800 return ir_nodehashmap_get(ir_node, get_block_info(block)->trans, node);
804 * Saves result of phi translation of node into predecessor
805 * at pos of block succ.
807 * @param node the node
808 * @param succ the successor of the translation target block
809 * @param pos the position of the predecessor block
810 * @param trans the translation result
813 static void set_translated(ir_nodehashmap_t *map, ir_node *node, ir_node *trans)
815 if (is_irn_constlike(node))
817 /* insert or replace */
818 ir_nodehashmap_insert(map, node, trans);
822 * Translates an expression above a Phi.
824 * @param node the node
825 * @param block the block the node is translated into
826 * @param pos the input number of the destination block
828 * @return a node representing the translated value
830 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *leaderset)
835 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
840 if (get_nodes_block(node) == block)
841 return get_Phi_pred(node, pos);
842 /* this phi does not need translation */
845 arity = get_irn_arity(node);
848 in = ALLOCANZ(ir_node *, arity);
850 /* A value has several representatives. The anti leader is chosen to be
851 the main representative. If we access a node as representative of a
852 value we always use the anti leader. The anti leader can be found by
853 antic_in(identify(node)). */
854 for (i = 0; i < arity; ++i) {
855 ir_node *pred = get_irn_n(node, i);
856 ir_node *value = identify(pred);
857 /* get leader for pred to lookup its translated value */
858 ir_node *leader = ir_valueset_lookup(leaderset, value);
865 /* we cannot find this value in antic_in, because the value
866 has (possibly) changed! */
867 pred_trans = get_translated(pred_block, leader);
872 ir_node *mem = get_Div_mem(node);
877 pred_trans = get_Div_mem(node);
881 DB((dbg, LEVEL_3, "trans %+F of %+F is %+F\n", leader, pred_block, pred_trans));
882 if (pred_trans == NULL) {
885 new_pred = pred_trans;
887 /* loads: Predecessor is a memory phi, which translated yields a proj or
888 another phi. In case of projection and a load predecessor,
889 skip them and use the loads memory. */
890 if (is_Proj(pred_trans) && get_irn_mode(pred_trans) == mode_M) {
892 ir_node *loadstore = get_Proj_pred(pred_trans);
893 /* If we do not translate this node, we will get its value wrong. */
896 if (is_Load(loadstore)) {
897 /* Put new load under the adjacent loads memory edge
898 such that GVN may compare them. */
899 new_pred = get_Load_mem(loadstore);
900 } else if (is_Store(loadstore)) {
901 new_pred = get_Store_mem(loadstore);
905 /* predecessor value changed, so translation is needed */
906 if (identify(new_pred) != identify(pred))
911 DB((dbg, LEVEL_4, "in %+F\n", new_pred));
918 DB((dbg, LEVEL_3, "Translate\n"));
921 pred_block = get_nodes_block(in[0]);
923 /* copy node to represent the new value.
924 We do not translate nodes that do not need translation,
925 so we use the newly created nodes as value representatives only.
926 Their block is not important, because we create new ones during
927 the insert node phase. */
929 get_irn_dbg_info(node),
936 /* We need the attribute copy here, because the Hash value of a
937 node might depend on it. */
938 copy_node_attr(environ->graph, node, nn);
939 /* Optimizing nn here is tempting but might be against the GVN-PRE algorithm
940 because it already uses availability. */
942 DB((dbg, LEVEL_3, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
947 * Block-walker, computes Antic_in(block).
948 * Builds a value tree out of the graph by translating values
951 * @param block the block
952 * @param ctx the walker environment
954 static void compute_antic(ir_node *block, void *ctx)
956 pre_env *env = (pre_env*)ctx;
957 block_info *succ_info;
963 ir_valueset_iterator_t iter;
966 /* filter blocks from topological walker */
967 if (! is_Block(block))
970 /* the end block has no successor */
971 if (block == env->end_block)
974 info = get_block_info(block);
976 size = ir_valueset_size(info->antic_in);
977 n_succ = get_Block_n_cfg_outs(block);
980 if (env->first_iter) {
982 /* keep antic_in of infinite loops empty */
983 if (! is_in_infinite_loop(block)) {
984 foreach_valueset(info->exp_gen, value, expr, iter) {
985 ir_valueset_insert(info->antic_in, value, expr);
989 foreach_valueset(info->exp_gen, value, expr, iter) {
990 ir_valueset_insert(info->antic_in, value, expr);
995 /* successor might have phi nodes */
996 if (n_succ == 1 && get_irn_arity(get_Block_cfg_out(block, 0)) > 1) {
997 succ = get_Block_cfg_out(block, 0);
998 int pos = get_Block_cfgpred_pos(succ, block);
999 succ_info = get_block_info(succ);
1001 /* initialize translated set */
1002 if (env->first_iter) {
1003 info->trans = XMALLOC(ir_nodehashmap_t);
1004 ir_nodehashmap_init(info->trans);
1007 foreach_valueset(succ_info->antic_in, value, expr, iter) {
1008 ir_node *trans = get_translated(block, expr);
1009 ir_node *trans_value;
1013 trans = phi_translate(expr, succ, pos, get_block_info(succ)->antic_in);
1015 /* create new value if necessary */
1016 trans_value = identify_or_remember(trans);
1018 DB((dbg, LEVEL_3, "Translate %+F %+F to %d = %+F (%+F)\n", expr, succ, pos, trans, trans_value));
1020 /* On value change (phi present) we need the translated node
1021 to represent the new value for possible further translation. */
1022 if (value != trans_value)
1027 if (is_clean_in_block(expr, block, info->antic_in)) {
1029 /* Prevent information flow over the backedge of endless loops. */
1030 if (env->iteration <= 2 || (is_backedge(succ, pos) && !is_in_infinite_loop(succ))) {
1031 ir_valueset_replace(info->antic_in, trans_value, represent);
1034 ir_valueset_replace(info->antic_in, trans_value, represent);
1037 set_translated(info->trans, expr, represent);
1040 } else if (n_succ > 1) {
1042 ir_node *common = NULL;
1043 ir_node *succ0 = get_Block_cfg_out(block, 0);
1044 block_info *succ0_info = get_block_info(succ0);
1046 /* disjoint of antic_ins */
1047 foreach_valueset(succ0_info->antic_in, value, expr, iter) {
1048 /* iterate over remaining successors */
1049 for (i = 1; i < n_succ; ++i) {
1050 ir_node *succ = get_Block_cfg_out(block, i);
1051 block_info *succ_info = get_block_info(succ);
1053 /* value in antic_in? */
1054 common = ir_valueset_lookup(succ_info->antic_in, value);
1059 if (common && is_clean_in_block(expr, block, info->antic_in))
1060 ir_valueset_replace(info->antic_in, value, expr);
1065 DEBUG_ONLY(dump_value_set(info->antic_in, "Antic_in", block);)
1067 if (size != ir_valueset_size(info->antic_in))
1071 /* --------------------------------------------------------
1072 * Main algorithm Avail_out
1073 * --------------------------------------------------------
1077 * Computes Avail_out(block):
1079 * Avail_in(block) = Avail_out(dom(block))
1080 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
1083 * This function must be called in the top-down topological order:
1084 * Then it computes Leader(Nodes(block)) instead of Nodes(block) !
1086 * @param block the block
1087 * @param ctx walker context
1089 static void compute_avail_top_down(ir_node *block, void *ctx)
1091 pre_env *env = (pre_env*)ctx;
1094 if (block == env->end_block)
1097 info = get_block_info(block);
1099 /* Add all nodes from the immediate dominator.
1100 This ensures that avail_out contains the leader. */
1101 if (block != env->start_block) {
1102 ir_node *dom_block = get_Block_idom(block);
1103 block_info *dom_info = get_block_info(dom_block);
1106 ir_valueset_iterator_t iter;
1108 foreach_valueset(dom_info->avail_out, value, expr, iter)
1109 /* replace: use the leader from dominator, not local exp_gen */
1110 ir_valueset_replace(info->avail_out, value, expr);
1113 DEBUG_ONLY(dump_value_set(info->avail_out, "Avail_out", block);)
1116 /* --------------------------------------------------------
1117 * Main algorithm redundancy detection
1118 * --------------------------------------------------------
1122 * Returns a valid mode if the value of expr is a partially redundant value.
1124 * @param block the block
1125 * @param expr the expression
1127 * @return mode of the expression if it is partially redundant else NULL
1129 static ir_mode *is_partially_redundant(ir_node *block, ir_node *expr, ir_node *value)
1131 ir_node *first_avail = NULL;
1133 int arity = get_irn_arity(block);
1134 int fully_redundant = 1;
1135 int partially_redundant = 0;
1136 ir_mode *mode = NULL;
1138 DB((dbg, LEVEL_3, "is partially redundant %+F(%+F) of %+F\n", expr, value, block));
1140 /* for each predecessor blocks */
1141 for (pos = 0; pos < arity; ++pos) {
1142 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
1143 block_info *pred_info;
1144 ir_node *trans_expr;
1145 ir_node *trans_value;
1146 ir_node *avail_expr;
1148 pred_info = get_block_info(pred_block);
1149 trans_expr = get_translated(pred_block, expr);
1150 trans_value = identify(trans_expr);
1152 if (is_Const(trans_expr))
1153 avail_expr = trans_expr;
1155 avail_expr = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
1157 /* value might be available through a not yet existing constant */
1158 if (avail_expr == NULL && is_Const(trans_expr)) {
1159 /* limit range of new constants */
1160 ir_mode *cmode = get_irn_mode(trans_expr);
1161 ir_tarval *upper = new_tarval_from_long(127, cmode);
1162 ir_tarval *lower = new_tarval_from_long(-127, cmode);
1163 ir_tarval *c = get_Const_tarval(trans_expr);
1165 /* tarval within range? */
1166 if (tarval_cmp(lower, c) == ir_relation_less_equal &&
1167 tarval_cmp(c, upper) == ir_relation_less_equal) {
1168 avail_expr = trans_expr;
1174 DB((dbg, LEVEL_3, "avail_expr %+F trans_expr %+F\n", avail_expr, trans_expr));
1176 if (avail_expr == NULL) {
1177 pred_info->avail = trans_expr;
1178 pred_info->found = 0;
1179 fully_redundant = 0;
1181 /* expr is available, use the leader */
1182 pred_info->avail = avail_expr;
1183 pred_info->found = 1;
1184 mode = get_irn_mode(avail_expr);
1185 partially_redundant = 1;
1187 if (first_avail == NULL)
1188 first_avail = avail_expr;
1189 else if (first_avail != avail_expr)
1190 /* Multiple different expressions are available,
1191 This is why we need no cut over avail_out sets. */
1192 fully_redundant = 0;
1194 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, avail_expr, pred_block));
1198 /* If it is not the same value already existing along every predecessor
1199 and it is defined by some predecessor then it is partially redundant. */
1200 if (! partially_redundant || fully_redundant)
1206 * Updates the new_set of a block by adding the new_set of
1207 * the immediate dominating block.
1211 static void update_new_set(ir_node *block, ir_node *idom)
1215 ir_valueset_iterator_t iter;
1216 block_info *curr_info = get_block_info(block);
1217 block_info *idom_info = get_block_info(idom);
1220 DEBUG_ONLY(dump_value_set(idom_info->new_set, "[New Set]", idom);)
1221 foreach_valueset(idom_info->new_set, value, expr, iter) {
1222 /* inherit new_set from immediate dominator */
1223 ir_valueset_insert(curr_info->new_set, value, expr);
1224 /* replace in avail_out */
1225 updated |= ir_valueset_replace(curr_info->avail_out, value, expr);
1227 #ifdef DEBUG_libfirm
1229 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
1231 } /* update_new_set */
1234 * Checks if hoisting irn is greedy.
1235 * Greedy hoisting means that there are non partially redundant nodes
1236 * hoisted. This happens if a partially redundant node has
1237 * non redundant predecessors.
1239 static unsigned is_hoisting_greedy(ir_node *irn, ir_node *block)
1241 int block_arity = get_irn_arity(block);
1242 int arity = get_irn_arity(irn);
1244 block_info *info = get_block_info(block);
1246 /* As long as the predecessor values are available in all predecessor blocks,
1247 we can hoist this value. */
1248 for (pos = 0; pos < block_arity; ++pos) {
1249 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
1250 block_info *pred_info = get_block_info(pred_block);
1252 for (i = 0; i < arity; ++i) {
1253 ir_node *pred = get_irn_n(irn, i);
1261 /* Very conservative min cut. Phi might only have 1 user. */
1262 if (is_Phi(pred) && get_irn_n_edges(pred) != 1)
1266 if (is_Phi(pred) && get_nodes_block(pred) == block)
1269 DB((dbg, LEVEL_3, "pred %+F\n", pred));
1270 value = identify(pred);
1271 leader = ir_valueset_lookup(info->antic_in, value);
1274 DB((dbg, LEVEL_3, "lead %+F\n", leader));
1275 trans = get_translated(pred_block, leader);
1278 DB((dbg, LEVEL_3, "trans %+F\n", trans));
1280 trans_val = identify(trans);
1281 DB((dbg, LEVEL_3, "value %+F\n", trans_val));
1283 if (is_Const(trans_val) || is_SymConst(trans_val)) {
1284 /* existing constant */
1285 if (get_irn_idx(trans_val) < environ->last_idx) {
1288 /* limit range of new constants */
1289 ir_mode *cmode = get_irn_mode(trans);
1290 ir_tarval *upper = new_tarval_from_long(128, cmode);
1291 ir_tarval *lower = new_tarval_from_long(-128, cmode);
1292 ir_tarval *c = get_Const_tarval(trans);
1294 /* tarval within range? */
1295 if (tarval_cmp(lower, c) == ir_relation_less &&
1296 tarval_cmp(c, upper) == ir_relation_less) {
1305 if (is_irn_constlike(trans_val))
1308 avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
1310 DB((dbg, LEVEL_3, "avail %+F\n", avail));
1314 /* only optimize if predecessors have been optimized */
1315 if (ir_valueset_lookup(info->antic_done, value) == NULL)
1324 * Perform insertion of partially redundant values.
1325 * For every block node, do the following:
1326 * 1. Propagate the NEW_SETS of the dominator into the current block.
1327 * If the block has multiple predecessors,
1328 * 2a. Iterate over the ANTIC expressions for the block to see if
1329 * any of them are partially redundant.
1330 * 2b. If so, insert them into the necessary predecessors to make
1331 * the expression fully redundant.
1332 * 2c. Insert a new Phi merging the values of the predecessors.
1333 * 2d. Insert the new Phi, and the new expressions, into the
1336 * @param block the block
1337 * @param ctx the walker environment
1339 static void insert_nodes_walker(ir_node *block, void *ctx)
1341 pre_env *env = (pre_env*)ctx;
1342 int arity = get_irn_arity(block);
1348 ir_valueset_iterator_t iter;
1351 if (! is_Block(block))
1354 /* ensure that even the start block has a new_set */
1355 info = get_block_info(block);
1357 ir_valueset_del(info->new_set);
1358 info->new_set = ir_valueset_new(16);
1360 if (block == env->start_block)
1363 DB((dbg, LEVEL_2, "Insert operation of %+F\n", block));
1365 idom = get_Block_idom(block);
1366 update_new_set(block, idom);
1368 /* process only path joining blocks */
1373 /* This is the main reason antic_in is preverred over antic_out;
1374 we may iterate over every anticipated value first and not
1375 over the predecessor blocks. */
1376 foreach_valueset(info->antic_in, value, expr, iter) {
1382 if (ir_valueset_lookup(info->antic_done, value))
1385 /* filter phi nodes from antic_in */
1389 DB((dbg, LEVEL_2, "Insert for %+F (value %+F) in %+F\n", expr, value, block));
1391 /* A value computed in the dominator is totally redundant.
1392 Hence we have nothing to insert. */
1393 if (ir_valueset_lookup(get_block_info(idom)->avail_out, value)) {
1394 DB((dbg, LEVEL_2, "Fully redundant expr %+F value %+F\n", expr, value));
1395 DEBUG_ONLY(inc_stats(gvnpre_stats->fully);)
1397 ir_valueset_insert(info->antic_done, value, expr);
1401 if (is_hoisting_greedy(expr, block)) {
1402 DB((dbg, LEVEL_2, "greedy\n"));
1406 mode = is_partially_redundant(block, expr, value);
1410 #if LOADS || DIVMODS
1411 /* save old mode_M phis to remove keepalive edges later */
1412 if (is_memop(expr)) {
1413 ir_node *mem = get_memop_mem(expr);
1414 if (is_Phi(mem) && get_nodes_block(mem) == get_nodes_block(expr)) {
1415 ir_nodeset_insert(env->keeps, mem);
1420 #ifdef DEBUG_libfirm
1421 if (! is_Proj(expr)) {
1422 if (env->first_iter)
1423 inc_stats(gvnpre_stats->first_iter_found);
1424 inc_stats(gvnpre_stats->partially);
1426 if (is_Load(expr) || is_Store(expr))
1427 inc_stats(gvnpre_stats->loads);
1428 else if (is_Div(expr) || is_Mod(expr))
1429 inc_stats(gvnpre_stats->divmods);
1432 phi_in = XMALLOCN(ir_node *, arity);
1434 /* for each predecessor block */
1435 for (pos = 0; pos < arity; ++pos) {
1436 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
1437 block_info *pred_info;
1439 pred_info = get_block_info(pred_block);
1441 if (! pred_info->found) {
1443 int node_arity = get_irn_arity(expr);
1444 ir_node **in = XMALLOCNZ(ir_node *, node_arity);
1446 ir_node *new_value, *new_value2;
1447 ir_node *target_block = pred_block;
1449 for (i = 0; i < node_arity; ++i) {
1450 ir_node *pred = get_irn_n(expr, i);
1451 ir_node *value = identify(pred);
1457 /* transform knowledge over the predecessor from
1458 anti-leader world into leader world. */
1460 DB((dbg, LEVEL_3, "pred %+F\n", pred));
1461 value = identify(pred);
1463 /* get leader for pred to lookup its translated value */
1464 leader = ir_valueset_lookup(info->antic_in, value);
1467 DB((dbg, LEVEL_3, "lead %+F\n", leader));
1469 trans = get_translated(pred_block, leader);
1472 DB((dbg, LEVEL_3, "trans %+F\n", trans));
1474 /* in case of phi, we are done */
1475 if (is_Phi(pred) && get_nodes_block(pred) == block) {
1480 trans_val = identify(trans);
1481 DB((dbg, LEVEL_3, "value %+F\n", trans_val));
1483 /* constants are always available but not in avail set */
1484 if (is_irn_constlike(trans_val)) {
1490 In case of loads we need to make sure the hoisted
1491 loads are found despite their unique value. */
1492 avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
1493 DB((dbg, LEVEL_3, "avail %+F\n", avail));
1495 assert(avail && "predecessor has to be available");
1500 target_block = get_nodes_block(in[0]);
1502 /* Copy node to represent the new value.
1503 We use translated nodes as value representatives only.
1504 They have anti leaders as predecessors, not leaders!
1505 So we have to create a new node using leaders. */
1506 trans = new_ir_node(
1507 get_irn_dbg_info(expr),
1512 get_irn_arity(expr),
1515 /* We need the attribute copy here, because the Hash value of a
1516 node might depend on it. */
1517 copy_node_attr(environ->graph, expr, trans);
1519 /* value is now available in target block through trans
1520 insert (not replace) because it has not been available */
1521 new_value = identify_or_remember(trans);
1522 ir_valueset_insert(pred_info->avail_out, new_value, trans);
1523 DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value));
1525 new_value2 = identify(get_translated(pred_block, expr));
1526 ir_valueset_insert(pred_info->avail_out, new_value2, trans);
1527 DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value2));
1529 DB((dbg, LEVEL_3, "Use new %+F in %+F because %+F(%+F) not available\n", trans, pred_block, expr, value));
1531 phi_in[pos] = trans;
1533 /* value available */
1534 phi_in[pos] = pred_info->avail;
1536 DB((dbg, LEVEL_3, "phi_in %+F\n", phi_in[pos]));
1539 /* We do not connect tuples as they will be connected automatically
1540 by the corresponding projections. */
1541 if (get_irn_mode(expr) != mode_T) {
1543 phi = new_r_Phi(block, arity, phi_in, mode);
1544 DB((dbg, LEVEL_3, "New %+F for redundant %+F created\n", phi, expr));
1546 /* This value is now available through the new phi.
1547 insert || replace in avail_out */
1548 ir_valueset_replace(info->avail_out, value, phi);
1549 ir_valueset_insert(info->new_set, value, phi);
1553 /* already optimized this value in this block */
1554 ir_valueset_insert(info->antic_done, value, expr);
1560 static void update_new_set_walker(ir_node *block, void *ctx)
1562 pre_env *env = (pre_env*)ctx;
1564 if (! is_Block(block))
1566 if (block == env->start_block)
1569 update_new_set(block, get_Block_idom(block));
1573 * Domtree block walker to insert nodes with dying operands
1574 * into the highest possible block whilst still being anticipated.
1576 static void hoist_high(ir_node *block, void *ctx)
1578 pre_env *env = (pre_env*)ctx;
1579 block_info *curr_info;
1580 ir_valueset_iterator_t iter;
1583 int arity = get_irn_arity(block);
1585 if (! is_Block(block))
1588 curr_info = get_block_info(block);
1590 if (curr_info->new_set)
1591 ir_valueset_del(curr_info->new_set);
1592 curr_info->new_set = ir_valueset_new(16);
1594 if (block == env->start_block)
1600 DB((dbg, LEVEL_2, "High hoisting %+F\n", block));
1602 /* foreach entry optimized by insert node phase */
1603 foreach_valueset(curr_info->antic_done, value, expr, iter) {
1606 /* TODO currently we cannot handle load and their projections */
1607 if (is_memop(expr) || is_Proj(expr))
1610 DB((dbg, LEVEL_4, "leader %+F value %+F\n", expr, value));
1612 /* visit hoisted expressions */
1613 for (pos = 0; pos < arity; ++pos) {
1614 /* standard target is predecessor block */
1615 ir_node *target = get_Block_cfgpred_block(block, pos);
1616 block_info *pred_info = get_block_info(target);
1618 ir_node *new_target;
1619 ir_node *trans_expr;
1620 ir_node *trans_value;
1624 unsigned nest_depth;
1625 block_info *dom_info;
1627 /* get phi translated value */
1628 trans_expr = get_translated(target, expr);
1629 trans_value = identify(trans_expr);
1630 avail = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
1632 /* get the used expr on this path */
1634 /* TODO when does this happen? */
1638 avail_arity = get_irn_arity(avail);
1639 value = identify(avail);
1641 /* anticipation border */
1643 nest_depth = get_loop_depth(get_irn_loop(target));
1645 /* Either push the hoisted nodes up their path,
1646 or try to put them directly into their common dominator. */
1648 /* By using block (instead of target) as initial block,
1649 we only allow hoisting into a common block of
1650 both predecessor blocks. */
1656 while (dom && dom != get_Block_idom(block)) {
1658 dom = get_Block_idom(dom);
1659 dom_info = get_block_info(dom);
1660 DB((dbg, LEVEL_4, "testing dom %+F\n", dom));
1662 /* TODO Being in antic_in means hoistable above block,
1663 but we need 'hoistable into block'.
1664 This could be achieved by a flag for each valueset pair,
1665 being set during antic computation. */
1667 /* check if available node ist still anticipated and clean */
1668 if (! ir_valueset_lookup(dom_info->antic_in, value)) {
1669 DB((dbg, LEVEL_4, "%+F not antic in %+F\n", value, dom));
1673 nest_depth = get_loop_depth(get_irn_loop(dom));
1675 /* do not hoist into loops */
1676 if (get_loop_depth(get_irn_loop(dom)) > nest_depth) {
1677 DB((dbg, LEVEL_4, "%+F deeper nested\n", dom));
1678 /* not a suitable location */
1682 /* check if operands die */
1684 /* check for uses on current path */
1685 for (i = 0; i < avail_arity; i++) {
1686 ir_node *pred = get_irn_n(avail, i);
1687 ir_node *pred_value = identify(pred);
1692 DB((dbg, LEVEL_4, "testing pred %+F\n", pred));
1694 if (! ir_valueset_lookup(dom_info->avail_out, pred_value)) {
1695 DB((dbg, LEVEL_4, "pred %+F not available\n", pred));
1700 /* check every successor */
1701 foreach_out_edge(pred, edge) {
1702 ir_node *succ = get_edge_src_irn(edge);
1703 DB((dbg, LEVEL_4, "testing succ %+F\n", succ));
1705 /* check only successors on current path to end */
1706 if (block_dominates(dom, get_nodes_block(succ))) {
1707 ir_node *succ_value = identify(succ);
1709 /* Do we have another user than avail?
1710 Then predecessor is not dead after removal of avail. */
1711 if (succ_value != value) {
1712 DB((dbg, LEVEL_4, "still used in %+F\n", succ));
1723 /* only try common dominator */
1728 /* put node into new target block */
1730 block_info *target_info = get_block_info(new_target);
1731 int nn_arity = get_irn_arity(avail);
1732 ir_node **in = XMALLOCN(ir_node *, nn_arity);
1736 DB((dbg, LEVEL_2, "Hoisting %+F into %+F\n", avail, new_target));
1737 DEBUG_ONLY(inc_stats(gvnpre_stats->hoist_high);)
1739 for (i = 0; i < nn_arity; ++i) {
1740 ir_node *pred = get_irn_n(avail, i);
1741 ir_node *avail_pred = ir_valueset_lookup(target_info->avail_out, identify(pred));
1746 get_irn_dbg_info(avail),
1750 get_irn_mode(avail),
1755 identify_or_remember(nn);
1756 /* TODO Nodes are inserted into a dominating block and should
1757 be available from this point on. Currently we do not push
1758 the availability information through during the walk. */
1759 ir_valueset_insert(target_info->new_set, value, nn);
1760 ir_valueset_insert(target_info->avail_out, value, nn);
1767 /* --------------------------------------------------------
1768 * Elimination of fully redundant nodes
1769 * --------------------------------------------------------
1773 * Walker which finds redundant nodes using avail_out sets
1774 * and exchanges them for existing ones.
1775 * We cannot change the graph here as this would affect
1776 * the hash values of the nodes.
1778 * @param irn the node
1779 * @param ctx the walker environment
1781 static void eliminate(ir_node *irn, void *ctx)
1783 pre_env *env = (pre_env*)ctx;
1785 if (! is_Block(irn)) {
1786 ir_node *block = get_nodes_block(irn);
1787 block_info *info = get_block_info(block);
1788 ir_node *value = identify(irn);
1790 if (value != NULL) {
1791 ir_node *expr = (ir_node*)ir_valueset_lookup(info->avail_out, value);
1792 DB((dbg, LEVEL_3, "Elim %+F(%+F) avail %+F\n", irn, value, expr));
1794 if (expr != NULL && expr != irn) {
1795 elim_pair *p = OALLOC(env->obst, elim_pair);
1799 p->next = env->pairs;
1800 if (get_irn_idx(expr) > env->last_idx)
1801 p->reason = FS_OPT_GVN_PARTLY;
1803 p->reason = FS_OPT_GVN_FULLY;
1805 DEBUG_ONLY(inc_stats(gvnpre_stats->replaced);)
1812 * Do all the recorded changes and optimize
1813 * newly created Phi's.
1815 * @param pairs list of elimination pairs
1817 static void eliminate_nodes(elim_pair *pairs, ir_nodeset_t *keeps)
1820 ir_node *end = environ->end_node;
1822 for (p = pairs; p != NULL; p = p->next) {
1823 /* might be already changed */
1824 p->new_node = skip_Id(p->new_node);
1826 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
1828 /* PRE tends to create Phi(self, self, ... , x, self, self, ...)
1829 * which we can optimize here */
1830 if (is_Phi(p->new_node)) {
1832 ir_node *res = NULL;
1834 for (i = get_irn_arity(p->new_node) - 1; i >= 0; --i) {
1835 ir_node *pred = get_irn_n(p->new_node, i);
1837 if (pred != p->old_node) {
1846 exchange(p->new_node, res);
1850 DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
1852 exchange(p->old_node, p->new_node);
1855 /* remove keep alive edges of unused mode_M phis */
1856 foreach_ir_nodeset(keeps, m_phi, iter) {
1857 remove_End_keepalive(end, m_phi);
1859 } /* eliminate_nodes */
1862 /* --------------------------------------------------------
1864 * --------------------------------------------------------
1868 * Gvn_Pre algorithm.
1870 * @param irg the graph
1871 * @param env the environment
1873 static void gvn_pre(ir_graph *irg, pre_env *env)
1875 unsigned antic_iter;
1876 unsigned insert_iter;
1878 DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg));
1880 /* allocate block info */
1881 irg_walk_blkwise_graph(irg, block_info_walker, NULL, env);
1883 ir_nodehashmap_init(&value_map);
1885 /* generate exp_gen */
1886 irg_walk_blkwise_graph(irg, NULL, topo_walker, env);
1887 dump_all_expgen_sets(env->list);
1889 /* compute the avail_out sets for all blocks */
1890 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, env);
1892 /* compute the anticipated value sets for all blocks */
1894 env->first_iter = 1;
1897 /* antic_in passes */
1900 DB((dbg, LEVEL_2, "= Antic_in Iteration %d ========================\n", antic_iter));
1902 irg_walk_blkwise_graph(irg, compute_antic, NULL, env);
1903 env->first_iter = 0;
1904 DB((dbg, LEVEL_2, "----------------------------------------------\n"));
1906 } while (env->changes != 0 && antic_iter < MAX_ANTIC_ITER);
1908 DEBUG_ONLY(set_stats(gvnpre_stats->antic_iterations, antic_iter);)
1910 ir_nodeset_init(env->keeps);
1912 env->first_iter = 1;
1913 /* compute redundant expressions */
1916 DB((dbg, LEVEL_2, "= Insert Iteration %d ==========================\n", insert_iter));
1918 /* TODO topologically top down would be better; fewer iterations. */
1919 dom_tree_walk_irg(irg, insert_nodes_walker, NULL, env);
1920 env->first_iter = 0;
1921 DB((dbg, LEVEL_2, "----------------------------------------------\n"));
1922 } while (env->changes != 0 && insert_iter < MAX_INSERT_ITER);
1923 DEBUG_ONLY(set_stats(gvnpre_stats->insert_iterations, insert_iter);)
1926 /* An attempt to reduce lifetimes by hoisting already hoisted values
1927 even higher if their operands die. */
1928 dom_tree_walk_irg(irg, hoist_high, NULL, env);
1929 /* update avail_out for elimination */
1930 dom_tree_walk_irg(irg, update_new_set_walker, NULL, env);
1933 /* Deactivate edges to prevent intelligent removal of nodes,
1934 or else we will get deleted nodes which we try to exchange. */
1935 edges_deactivate(environ->graph);
1937 /* eliminate nodes */
1938 irg_walk_graph(irg, NULL, eliminate, env);
1939 eliminate_nodes(env->pairs, env->keeps);
1941 ir_nodeset_destroy(env->keeps);
1945 * Gvn_Pre pass for graph irg.
1947 * @param irg the graph
1949 void do_gvn_pre(ir_graph *irg)
1951 struct obstack obst;
1954 optimization_state_t state;
1955 block_info *block_info;
1957 /* bads and unreachables cause too much trouble with dominance,
1958 loop info for endless loop detection,
1959 no critical edges is PRE precondition
1961 assure_irg_properties(irg,
1962 IR_GRAPH_PROPERTY_NO_BADS
1963 | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
1964 | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO
1965 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
1966 | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
1967 | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
1969 /* register a debug mask */
1970 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
1972 save_optimization_state(&state);
1973 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_LOOP_LINK);
1975 edges_activate(irg);
1978 DEBUG_ONLY(init_stats();)
1980 /* setup environment */
1981 obstack_init(&obst);
1985 env.start_block = get_irg_start_block(irg);
1986 env.end_block = get_irg_end_block(irg);
1987 env.end_node = get_irg_end(irg);
1990 env.last_idx = get_irg_last_idx(irg);
1992 /* Detect and set links of infinite loops to non-zero. */
1996 new_identities(irg);
1997 env.value_table = irg->value_table;
1998 irg->value_table = NULL;
2001 /* Switch on GCSE. We need it to correctly compute
2002 the value of a node, which is independent from
2004 set_opt_global_cse(1);
2005 /* new_identities() */
2006 if (irg->value_table != NULL)
2007 del_pset(irg->value_table);
2008 /* initially assumed nodes in pset are 512 */
2009 irg->value_table = new_pset(compare_gvn_identities, 512);
2011 env.gvnpre_values = irg->value_table;
2014 /* do GVN-PRE pass */
2016 DEBUG_ONLY(print_stats();)
2018 /* clean up: delete all sets */
2019 for (block_info = env.list; block_info != NULL; block_info = block_info->next) {
2020 free_block_info(block_info);
2023 DEBUG_ONLY(free_stats();)
2024 ir_nodehashmap_destroy(&value_map);
2025 obstack_free(&obst, NULL);
2026 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_LOOP_LINK);
2028 /* Pin the graph again.
2029 This is needed due to the use of set_opt_global_cse(1) */
2030 set_irg_pinned(irg, op_pin_state_pinned);
2031 restore_optimization_state(&state);
2032 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
2035 irg->value_table = env.value_table;
2036 del_pset(irg->value_table);
2037 irg->value_table = env.gvnpre_values;
2040 /* TODO There seem to be optimizations that try to use the existing
2042 new_identities(irg);
2044 /* TODO assure nothing else breaks. */
2045 set_opt_global_cse(0);
2046 edges_activate(irg);
2049 /* Creates an ir_graph pass for do_gvn_pre. */
2050 ir_graph_pass_t *do_gvn_pre_pass(const char *name)
2052 return def_graph_pass(name ? name : "gvn_pre", do_gvn_pre);