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
29 #include "iroptimize.h"
38 #include "irnodehashmap.h"
39 #include "irnodeset.h"
41 #include "iropt_dbg.h"
45 #include "irgraph_t.h"
49 /** Additional info we need for every block. */
50 typedef struct block_info {
51 ir_valueset_t *exp_gen; /**< contains this blocks clean expressions */
52 ir_valueset_t *avail_out; /**< The Avail_out set for a block. */
53 ir_valueset_t *antic_in; /**< The Antic_in set for a block. */
54 ir_valueset_t *new_set; /**< The set of all new values for a block. */
55 ir_nodehashmap_t *trans; /**< contains translated nodes in block */
56 ir_node *avail; /**< The get_map(avail, block) result. */
57 ir_node *block; /**< The Block of the block info. */
58 struct block_info *next; /**< Links all entries, so we can recover the sets easily. */
59 int found; /**< Non-zero, if avail was found in this block. */
63 * A pair of nodes that must be exchanged.
64 * We must defer the exchange because our hash-sets cannot
65 * find an already replace node else.
67 typedef struct elim_pair {
68 ir_node *old_node; /**< The old node that will be replaced. */
69 ir_node *new_node; /**< The new node. */
70 struct elim_pair *next; /**< Links all entries in a list. */
71 int reason; /**< The reason for the replacement. */
74 /** The environment for the GVN-PRE algorithm */
75 typedef struct pre_env {
76 struct obstack *obst; /**< The obstack to allocate on. */
77 ir_node *start_block; /**< The start block of the current graph. */
78 ir_node *end_block; /**< The end block of the current graph */
79 block_info *list; /**< Links all block info entries for easier recovery. */
80 elim_pair *pairs; /**< A list of node pairs that must be eliminated. */
81 unsigned last_idx; /**< last node index of "old" nodes, all higher indexes are newly created once. */
82 char changes; /**< Non-zero, if calculation of Antic_in has changed. */
83 char first_iter; /**< non-zero for first iteration */
86 /** The debug module handle. */
87 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
89 /* ---------- Functions for Value sets ---------- */
93 * computes dst = dst \/ src for value sets
95 * @param dst the union result set
96 * @param src the source set
98 static void value_union(ir_valueset_t *dst, ir_valueset_t *src)
100 ir_valueset_iterator_t iter;
101 ir_node *value, *expr;
103 foreach_valueset(src, value, expr, iter) {
104 /* dominator tree walk; use first available expr as leader */
105 ir_valueset_insert(dst, value, expr);
110 /* ---------- Functions for Values ---------- */
113 * Remember adds a node e to the GCSE valuetable.
115 * @param e a node representing an expression
116 * @return the final value for the expression e
118 static ir_node *remember(ir_node *e)
123 ir_node *pred = get_Proj_pred(e);
124 ir_node *v_pred = identify_remember(pred);
126 if (v_pred != pred) {
127 ir_node *proj = new_r_Proj(v_pred, get_irn_mode(e), get_Proj_proj(e));
128 value = identify_remember(proj);
133 value = identify_remember(e);
138 * Identify does a lookup in the GCSE valuetable.
140 * @param e a node representing an expression
141 * @return a node representing the value or NULL if no identified
143 static ir_node *identify(ir_node *e)
145 return identify_remember(e);
149 * Returns the block info of a block.
151 * @param block the block
152 * @return block info of block
154 static block_info *get_block_info(ir_node *block)
156 block_info *info = (block_info*)get_irn_link(block);
161 * Allocate block info for block block.
163 * @param block the block
164 * @param env the environment
166 static void alloc_blk_info(ir_node *block, pre_env *env)
168 block_info *info = OALLOC(env->obst, block_info);
170 set_irn_link(block, info);
171 info->exp_gen = ir_valueset_new(16);
172 info->avail_out = ir_valueset_new(16);
173 info->antic_in = ir_valueset_new(16);
174 /* valueset has much nicer interface */
175 info->trans = XMALLOC(ir_nodehashmap_t);
176 ir_nodehashmap_init(info->trans);
178 info->new_set = NULL;
183 info->next = env->list;
185 } /* alloc_blk_info */
188 * Returns non-zero if a node is movable and a possible candidate for PRE.
191 * @return non-zero if value is nice
193 static int is_nice_value(ir_node *n)
197 if (get_irn_mode(n) == mode_M)
204 n = get_Proj_pred(n);
206 /* we may not move pinned nodes */
207 if (get_irn_pinned(n) == op_pin_state_pinned)
210 mode = get_irn_mode(n);
211 if (!mode_is_data(mode)) {
212 /* Div and Mod are only nice if they do not use memory. */
213 if (! is_Div(n) && ! is_Mod(n))
215 if (! is_NoMem(get_memop_mem(n)))
219 } /* is_nice_value */
226 * @param set the set to dump
227 * @param txt a text to describe the set
228 * @param block the owner block of the set
230 static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
232 ir_valueset_iterator_t iter;
233 ir_node *value, *expr;
236 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
238 foreach_valueset(set, value, expr, iter) {
240 DB((dbg, LEVEL_2, "\n"));
242 DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
244 DB((dbg, LEVEL_2, " %+F,", expr));
247 DB((dbg, LEVEL_2, "\n}\n"));
248 } /* dump_value_set */
251 * Dump all exp_gen value sets.
253 * @param list the list of block infos to retrieve the sets from
255 static void dump_all_expgen_sets(block_info *list)
259 for (bl_info = list; bl_info != NULL; bl_info = bl_info->next) {
260 dump_value_set(bl_info->exp_gen, "[Exp_gen]", bl_info->block);
265 #define dump_value_set(set, txt, block)
266 #define dump_all_expgen_sets(list, txt)
267 #endif /* DEBUG_libfirm */
270 * Gets result of nodes phi translation into block.
272 * @param node the node
273 * @param block the target block
275 * @return a phi translation of node node into block block or NULL
277 static ir_node *get_translated(ir_node *node, ir_node *block)
279 if (is_irn_constlike(node)) {
283 block_info *bi = get_block_info(block);
284 ir_node *trans = (ir_node *)ir_nodehashmap_get(bi->trans, node);
290 * Saves result of phi translation of node into predecessor
291 * at pos of block succ.
293 * @param node the node
294 * @param succ the successor of the translation target block
295 * @param pos the position of the predecessor block
296 * @param trans the translation result
299 static void set_translated(ir_node *node, ir_node *succ, int pos, ir_node *trans)
301 ir_node *pred = get_Block_cfgpred_block(succ, pos);
302 block_info *bi = get_block_info(pred);
304 ir_nodehashmap_insert(bi->trans, node, trans);
308 * Checks if a node node is clean in block block for use in antic_in.
310 * A clean node in block block can be hoisted above block block.
311 * A node is not clean if its value is killed in block block.
312 * The node can still be hoisted into block block.
314 * @param n the phi translated or not translated node
315 * @param block the block
316 * @return non-zero value for clean node
318 static int is_clean_in_block_antic(ir_node *node, ir_node *block)
322 if (get_irn_mode(node) == mode_M)
325 /* a phi only has predecessors in other blocks */
329 /* constants are in start block */
330 if (is_irn_constlike(node))
333 /* what we really want to check
334 Only for node is translated case; other are clean anyway */
335 if (! is_nice_value(node)) {
339 /* cleanliness depends on nodes predecessors
340 At least if node is translated. */
341 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
342 ir_node *pred = get_irn_n(node, i);
343 ir_node *trans, *value;
345 if (is_irn_constlike(pred))
348 /* exp_gen only contains clean nodes */
349 if (ir_valueset_lookup(get_block_info(block)->exp_gen, pred))
352 /* block of pred strictly dominates target block. pred irrelevant. */
353 if (block_strictly_dominates(get_nodes_block(pred), block))
356 /* --- pred neither in block, nor dominating -- */
358 /* This pred is in antic_in and such clean.
359 Not every clean pred is in antic_in though.
360 Predecessor might be translated or not */
361 value = identify(pred);
362 if (ir_valueset_lookup(get_block_info(block)->antic_in, value))
365 /* This check is not redundant for translated nodes;
366 non translated ones are already nice. */
367 if (! is_nice_value(pred)) {
368 DB((dbg, LEVEL_5, "unclean %+F because pred %+F not nice\n", node, pred));
372 /* predecessor is not translated. This is legal if
373 predecessor is dominating or in target block (already checked). */
374 trans = get_translated(pred, block);
376 DB((dbg, LEVEL_5, "unclean %+F because pred %+F unclean (not translated)\n", node, pred));
380 /* Node and predecessor are translated, but is pred clean?
381 The value of the translated predecessor has to be in antic_in. */
382 ir_node *value = identify(trans);
383 if (! ir_valueset_lookup(get_block_info(block)->antic_in, value)) {
384 DB((dbg, LEVEL_5, "unclean %+F because pred %+F value %+F not antic\n", node, pred, value));
389 assert(0 && "should have been catched");
394 } /* is_clean_in_block */
397 * Checks if a node n is clean in block block for exp_gen.
400 * @param block the block
401 * @return non-zero value for clean node
403 static int is_clean_in_block_expgen(ir_node *n, ir_node *block)
407 if (get_irn_mode(n) == mode_M)
413 if (! is_nice_value(n))
416 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
417 ir_node *pred = get_irn_n(n, i);
419 /* sufficient for exp_gen because block is always block of node */
420 if (get_nodes_block(pred) != block)
424 so it needs to be clean (already in exp_gen) */
425 if (! get_irn_link(pred)) {
426 DB((dbg, LEVEL_5, "unclean %+F because pred %+F unclean\n", n, pred));
433 } /* is_clean_in_block */
436 * Does blocklocal common subexpression elimination (cse).
438 * @param irn the node
439 * @param ctx the environment
441 static void cse_walker(ir_node *irn, void *ctx)
443 ir_node *opt = identify_remember(irn);
447 DB((dbg, LEVEL_5, "CSE %+F to %+F\n", irn, opt));
453 * Bottom up walker that ensures that every block gets a block info.
455 * @param irn the node
456 * @param ctx the environment
458 static void block_info_walker(ir_node *irn, void *ctx)
461 pre_env *env = (pre_env*)ctx;
462 alloc_blk_info(irn, env);
467 * Topological walker puts nodes in top-down topological order into exp_gen set.
469 * @param irn the node
470 * @param ctx the environment
472 static void topo_walker(ir_node *irn, void *ctx)
479 /* GVN step: remember the value */
480 value = remember(irn);
482 /* no need to put constants into the sets: they are always redundant */
483 if (! is_nice_value(irn) || is_irn_constlike(irn))
486 /* Do not put mode_T nodes info the sets, or PhiT will be created
487 (which are not allowed in Firm). Instead, put the Proj's here only. */
488 if (get_irn_mode(irn) == mode_T)
491 block = get_nodes_block(irn);
492 info = get_block_info(block);
494 if (is_clean_in_block_expgen(irn, block)) {
495 /* two expressions with same value in block;
496 should have been fixed by cse pass */
497 assert(get_nodes_block(irn) == block &&
498 (! ir_valueset_lookup(info->exp_gen, value)));
500 DB((dbg, LEVEL_5, "%+F clean in block %+F\n", irn, block));
502 ir_valueset_insert(info->exp_gen, value, irn);
503 /* flag irn as clean*/
504 set_irn_link(irn, irn);
506 /* flag irn as not clean */
507 set_irn_link(irn, NULL);
512 * Computes Avail_out(block):
514 * Avail_in(block) = Avail_out(dom(block))
515 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
518 * This function must be called in the top-down topological order:
519 * Then it computes Leader(Nodes(block)) instead of Nodes(block) !
521 * @param block the block
522 * @param ctx walker context
524 static void compute_avail_top_down(ir_node *block, void *ctx)
526 pre_env *env = (pre_env*)ctx;
527 block_info *dom_info;
528 block_info *info = get_block_info(block);
531 /* filter blocks from topological walker */
532 if (! is_Block(block))
535 if (block == env->end_block)
538 /* First, add all nodes from the immediate dominator.
539 This ensures that avail_out contains the leader.
540 The start block has no dominators. */
541 if (block != env->start_block) {
542 dom_blk = get_Block_idom(block);
543 assert(is_Block(dom_blk));
544 dom_info = get_block_info(dom_blk);
546 value_union(info->avail_out, dom_info->avail_out);
548 /* Second, add values from exp_gen. */
549 value_union(info->avail_out, info->exp_gen);
551 dump_value_set(info->avail_out, "Avail_out", block);
555 * Translates an expression above a Phi.
557 * @param node the node
558 * @param block the block the node is translated into
559 * @param pos the input number of the destination block
561 * @return a node representing the translated value
563 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos)
570 if (get_nodes_block(node) == block) {
571 /* a Phi inside target block */
572 return get_Phi_pred(node, pos);
574 /* already outside */
578 arity = get_irn_arity(node);
579 in = XMALLOCN(ir_node *, arity);
581 for (i = 0; i < arity; ++i) {
582 ir_node *pred = get_irn_n(node, i);
583 ir_node *pred_block = get_Block_cfgpred_block(block,pos);
584 ir_node *trans = get_translated(pred, pred_block);
586 /* if node is topologically first in block then
587 there is no translated predecessor.
588 We do not check cleanliness here, so pred might be not clean. */
596 get_irn_dbg_info(node),
598 get_Block_cfgpred_block(block, pos),
604 /* We need the attribute copy here, because the Hash value of a
605 node might depend on that. */
606 copy_node_attr(get_irn_irg(node), node, nn);
607 DB((dbg, LEVEL_5, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
610 nn = optimize_node(nn);
611 DB((dbg, LEVEL_5, "New gcse optimized node %+F origin %+F\n", nn, node));
613 /* During the insert phase we need to compare the global value numbers
614 of blocks that do not dominate each other. 'Blocksafe' GCSE requires
615 the two equivalent nodes to be in blocks that dominate each other.
616 (see identities_cmp() in iropt.c)
617 If we do not translate a node into the predecessor block, their values
618 will not be considered equivalent. (we are at a merging block.)
619 So we have to translate a node into its predecessor block.
620 If we switched off blocksafety we will find matching values that are
621 not dominating (in loops) which we cannot use.
623 Also, blocksafe GCSE does not kill nn even if its value is already
624 present in the successor because the predecessor blocks do not dominate.
625 This is required for antic_in.
627 The nodes produced here are not necessarily in the designated block.
628 They are used to determine the value of node node.
629 If we use them for hoisting, we need to make sure that they are in the
630 designated block. fix_translated() does this job. */
633 } /* phi_translate */
636 * Block-walker, computes Antic_in(block).
638 * @param block the block
639 * @param ctx the walker environment
641 static void compute_antic(ir_node *block, void *ctx)
643 pre_env *env = (pre_env*)ctx;
644 block_info *succ_info;
646 ir_node *succ, *value, *expr;
648 ir_valueset_iterator_t iter;
650 /* filter blocks from topologic walker */
651 if (! is_Block(block))
654 /* no need for computations in start block */
655 if (block == env->start_block)
658 /* the end block has no successor */
659 if (block == env->end_block)
662 info = get_block_info(block);
663 size = ir_valueset_size(info->antic_in);
666 /* This step puts all generated expression from the
667 current block into antic_in.
668 This is needs to be done in the first iteration only. */
669 if (env->first_iter) {
670 foreach_valueset(info->exp_gen, value, expr, iter) {
671 /* We will have phi nodes in antic in.
672 This should prevent special cases in several places. */
673 ir_valueset_insert(info->antic_in, value, expr);
677 /* TODO handle endless loops. */
679 n_succ = get_Block_n_cfg_outs(block);
683 /* find blocks position in succ's block predecessors */
684 succ = get_Block_cfg_out(block, 0);
685 pos = get_Block_cfgpred_pos(succ, block);
688 succ_info = get_block_info(succ);
689 /* translate into list: we cannot insert into a set we iterate
690 * and succ might be equal to block for endless loops */
691 foreach_valueset(succ_info->antic_in, value, expr, iter) {
692 ir_node *trans, *newval;
694 DB((dbg, LEVEL_5, "Begin phi translate antic: expr %+F from %+F to %d\n", expr, succ, pos));
696 /* TODO if successor block has 1 predecessor we need no phi translation.
697 But the clean_in_block check is still needed! */
698 /* TODO phi translation and clean in block are overlapping,
699 because phi trans perhaps should know in advance if predecessors are clean. */
700 trans = phi_translate(expr, succ, pos);
701 newval = remember(trans);
703 DB((dbg, LEVEL_5, "----> phi translate antic: expr %+F from %+F to %d is trans %+F\n", expr, succ, pos, trans));
705 if (is_clean_in_block_antic(trans, block)) {
706 if (! is_irn_constlike(trans)) {
707 ir_valueset_insert(info->antic_in, newval, trans);
709 DB((dbg, LEVEL_5, " translated %+F clean in %+F\n", trans, block));
712 DB((dbg, LEVEL_5, " translated %+F not clean in %+F\n", trans, block));
715 /* We have to set translated anyway
716 because expr might still be hoisted _into_ block. */
717 set_translated(expr, succ, pos, trans);
719 DB((dbg, LEVEL_5, "- end: expr %+F -----\n\n", expr));
722 } else if (n_succ > 1) {
724 block_info *succ0_info;
727 /* Select a successor to compute the disjoint of all nodes
728 sets, it might be useful to select the block with the
729 smallest number of nodes. For simplicity we choose the
731 succ0 = get_Block_cfg_out(block, 0);
732 succ0_info = get_block_info(succ0);
734 foreach_valueset(succ0_info->antic_in, value, expr, iter) {
735 /* we need the disjoint */
736 for (i = 1; i < n_succ; ++i) {
737 ir_node *succ = get_Block_cfg_out(block, i);
738 block_info *succ_info = get_block_info(succ);
740 if (ir_valueset_lookup(succ_info->antic_in, value) == NULL) {
747 /* we found a value that is common in all Antic_in(succ(b)),
748 put it in Antic_in(b) if the value is not already represented. */
749 if (is_clean_in_block_antic(expr, block)) {
750 ir_valueset_insert(info->antic_in, value, expr);
752 set_translated(expr, succ0, 0, expr);
755 set_translated(expr, succ0, 0, expr);
761 dump_value_set(info->antic_in, "Antic_in", block);
762 if (size != ir_valueset_size(info->antic_in)) {
766 } /* compute_antic */
769 * Finds if the value of expr is a partially redundant value in block.
771 * @param block the block
772 * @param expr the expression
774 * @return mode of the expression if it is partially redundant else NULL
776 static ir_mode *find_partially_redundant(ir_node *block, ir_node *expr)
778 ir_node *first_avail;
779 int pos, arity = get_irn_arity(block);
780 int fully_redundant, partially_redundant;
783 DB((dbg, LEVEL_3, "Examine expr %+F of %+F\n", expr, block));
785 partially_redundant = 0;
790 /* for each predecessor blocks */
791 for (pos = 0; pos < arity; ++pos) {
792 block_info *pred_info;
793 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
794 ir_node *trans_expr, *trans_value, *avail_expr;
796 /* ignore bad blocks. */
797 if (is_Bad(pred_blk))
800 trans_expr = get_translated(expr, get_Block_cfgpred_block(block,pos));
801 DB((dbg, LEVEL_2, "expr %+F trans @ %d is translated %+F\n", expr, pos, trans_expr));
802 /* exp in antic in, so pred is clean
803 uncover when it is not */
806 trans_value = identify(trans_expr);
807 DB((dbg, LEVEL_2, "trans_value %+F\n", trans_value));
810 pred_info = get_block_info(pred_blk);
811 avail_expr = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
812 DB((dbg, LEVEL_2, "avail_expr %+F\n", avail_expr));
814 if (avail_expr == NULL) {
815 /* expr not available */
816 pred_info->avail = expr;
817 pred_info->found = 0;
821 /* expr is available */
822 pred_info->avail = avail_expr;
823 pred_info->found = 1;
824 mode = get_irn_mode(avail_expr);
825 partially_redundant = 1;
827 if (first_avail == NULL)
828 first_avail = avail_expr;
829 else if (first_avail != avail_expr)
830 /* Multiple differnet expressions are available */
833 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, avail_expr, pred_blk));
837 /* If it is not the same value already existing along every predecessor
838 and it is defined by some predecessor then it is partially redundant. */
839 if (! fully_redundant && partially_redundant)
846 * Copies node and its predecessors to a block that dominates the target block.
848 * @param node the node
849 * @param target the target block
851 * @return copy of node node dominating target block
853 static ir_node *fix_translation(ir_node *node, ir_node *target)
859 DB((dbg, LEVEL_1, "Fix_translation %+F into %+F\n", node, target));
861 /* identifies unreachable blocks using domination */
862 if (get_Block_dom_depth(get_nodes_block(node)) < 0 ||
863 (get_Block_dom_depth(target) < 0))
864 return new_r_Bad(get_irn_irg(node), get_irn_mode(node));
866 /* Walk upwards until the node dominates its use in target block.
867 Precondition is that the node is clean. */
868 if (block_dominates(get_nodes_block(node), target))
871 DB((dbg, LEVEL_1, "Fix_translation%+F of node %+F does not dominate target %+F\n", get_nodes_block(node), node, target));
873 arity = get_irn_arity(node);
874 ins = XMALLOCN(ir_node*, arity);
876 for (i = arity - 1; i >= 0; --i) {
877 ir_node *pred = get_irn_n(node, i);
878 ir_node *fixed = fix_translation(pred, target);
880 DB((dbg, LEVEL_1, "Fixed %+F to %+F for node %+F\n", pred, fixed, node));
885 get_irn_dbg_info(node),
893 copy_node_attr(get_irn_irg(node), node, nn);
895 DB((dbg, LEVEL_1, "New fixed node %+F from translated %+F. target %+F\n", nn, node, target));
897 nn = optimize_node(nn);
900 } /* fix_translation */
903 * Updates the new_set of a block by adding the new_set of
904 * the immediate dominating block.
908 static void update_new_set(ir_node *block, ir_node *idom)
910 ir_node *value, *expr;
911 ir_valueset_iterator_t iter;
912 block_info *curr_info = get_block_info(block);
913 block_info *idom_info = get_block_info(idom);
916 dump_value_set(idom_info->new_set, "[New Set]", idom);
917 foreach_valueset(idom_info->new_set, value, expr, iter) {
918 ir_valueset_insert(curr_info->new_set, value, expr);
919 updated |= ir_valueset_replace(curr_info->avail_out, value, expr);
922 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
924 } /* update_new_set */
927 * Perform insertion of partially redundant values.
928 * For every block node, do the following:
929 * 1. Propagate the NEW_SETS of the dominator into the current block.
930 * If the block has multiple predecessors,
931 * 2a. Iterate over the ANTIC expressions for the block to see if
932 * any of them are partially redundant.
933 * 2b. If so, insert them into the necessary predecessors to make
934 * the expression fully redundant.
935 * 2c. Insert a new Phi merging the values of the predecessors.
936 * 2d. Insert the new Phi, and the new expressions, into the
939 * @param block the block
940 * @param ctx the walker environment
942 static void insert_nodes(ir_node *block, void *ctx)
944 pre_env *env = (pre_env*)ctx;
945 ir_node *value, *expr, *idom;
946 block_info *curr_info;
947 int pos, arity = get_irn_arity(block);
948 ir_valueset_iterator_t iter;
950 /* filter only blocks */
951 if (! is_Block(block))
954 /* ensure that even the start block has a new_set */
955 curr_info = get_block_info(block);
956 if (curr_info->new_set)
957 ir_valueset_del(curr_info->new_set);
958 curr_info->new_set = ir_valueset_new(16);
960 if (block == env->start_block)
963 DB((dbg, LEVEL_2, "Insert operation of %+F\n", block));
965 idom = get_Block_idom(block);
966 update_new_set(block, idom);
968 /* process only merge blocks */
972 /* for each antic_in */
973 foreach_valueset(curr_info->antic_in, value, expr, iter) {
975 ir_node *phi, *phi_value;
978 /* filter phi nodes from antic in */
982 /* A value computed in the dominator is totally redundant.
983 Hence we have nothing to insert. */
984 if (ir_valueset_lookup(get_block_info(idom)->avail_out, value)) {
985 DB((dbg, LEVEL_2, "Fully redundant expr %+F value %+F\n", expr, value));
989 mode = find_partially_redundant(block, expr);
993 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block));
995 phi_in = XMALLOCN(ir_node *, arity);
997 /* for all predecessor blocks */
998 for (pos = 0; pos < arity; ++pos) {
999 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
1000 block_info *pred_info;
1002 /* ignore bad blocks. */
1003 if (is_Bad(pred_blk)) {
1004 ir_graph *irg = get_irn_irg(pred_blk);
1005 phi_in[pos] = new_r_Bad(irg, mode);
1008 pred_info = get_block_info(pred_blk);
1010 /* ignore blocks that already have the expression */
1011 if (! pred_info->found) {
1012 ir_node *translated, *trans_value;
1014 translated = get_translated(expr, pred_blk);
1015 /* make sure translated domintes its use */
1016 translated = fix_translation(translated, pred_blk);
1017 DB((dbg, LEVEL_3, "Use translated %+F in %+F because expr %+F not available\n", translated, pred_blk, expr));
1019 /* make the new node available */
1020 trans_value = remember(translated);
1021 ir_valueset_insert(pred_info->avail_out, trans_value, translated);
1022 phi_in[pos] = translated;
1023 DB((dbg, LEVEL_5, "phi_in %+F\n", translated));
1025 phi_in[pos] = pred_info->avail;
1026 DB((dbg, LEVEL_5, "phi_in %+F\n", pred_info->avail));
1031 phi = new_r_Phi(block, arity, phi_in, mode);
1033 DB((dbg, LEVEL_1, "New %+F for redundant %+F created\n", phi, expr));
1035 phi_value = remember(phi);
1037 /* this 'global' value is now available through the new phi */
1038 ir_valueset_replace(curr_info->avail_out, value, phi);
1039 /* add this phi and its 'blocklocal' value */
1040 ir_valueset_insert(curr_info->avail_out, phi_value, phi);
1042 ir_valueset_insert(curr_info->new_set, value, phi);
1043 ir_valueset_insert(curr_info->new_set, phi_value, phi);
1045 /* remove from antic_in to prevent reprocessing */
1046 ir_valueset_remove_iterator(curr_info->antic_in, &iter);
1050 } /* node_set_foreach */
1051 } /* insert_nodes */
1054 * Walker which finds redundant nodes using avail_out sets
1055 * and exchanges them for existing ones.
1056 * We cannot change the graph here as this would affect
1057 * the hash values of the nodes.
1059 * @param irn the node
1060 * @param ctx the walker environment
1062 static void eliminate(ir_node *irn, void *ctx)
1064 pre_env *env = (pre_env*)ctx;
1066 if (! is_Block(irn)) {
1067 ir_node *block = get_nodes_block(irn);
1068 block_info *bl = get_block_info(block);
1069 ir_node *value = identify(irn);
1071 if (value != NULL) {
1072 ir_node *expr = (ir_node*)ir_valueset_lookup(bl->avail_out, value);
1074 if (expr != NULL && expr != irn) {
1075 elim_pair *p = OALLOC(env->obst, elim_pair);
1079 p->next = env->pairs;
1080 if (get_irn_idx(expr) >= env->last_idx)
1081 p->reason = FS_OPT_GVN_PARTLY;
1083 p->reason = FS_OPT_GVN_FULLY;
1091 * Do all the recorded changes and optimize
1092 * newly created Phi's.
1094 * @param pairs list of elimination pairs
1096 static void eliminate_nodes(elim_pair *pairs)
1100 for (p = pairs; p != NULL; p = p->next) {
1101 /* might be already changed */
1102 p->new_node = skip_Id(p->new_node);
1104 DB((dbg, LEVEL_1, "Replacing %+F by %+F\n", p->old_node, p->new_node));
1105 /* PRE tends to create Phi(self, self, ... , x, self, self, ...)
1106 * which we can optimize here */
1107 if (is_Phi(p->new_node)) {
1109 ir_node *res = NULL;
1111 for (i = get_irn_arity(p->new_node) - 1; i >= 0; --i) {
1112 ir_node *pred = get_irn_n(p->new_node, i);
1114 if (pred != p->old_node) {
1123 exchange(p->new_node, res);
1127 DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
1128 exchange(p->old_node, p->new_node);
1130 } /* eliminate_nodes */
1133 * Gvn_Pre pass for graph irg.
1135 * @param irg the graph
1137 void do_gvn_pre(ir_graph *irg)
1139 struct obstack obst;
1141 optimization_state_t state;
1142 block_info *bl_info;
1143 unsigned antic_iter, insert_iter;
1145 /* register a debug mask */
1146 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
1147 /* edges will crash if enabled due to our allocate on other obstack trick */
1148 edges_deactivate(irg);
1150 /* algorithm preconditions */
1151 remove_critical_cf_edges(irg);
1152 /* we get all nodes of a block by following outs */
1153 assure_irg_outs(irg);
1154 /* we need dominator for Antic_out calculation */
1156 compute_postdoms(irg);
1158 save_optimization_state(&state);
1161 * If there are two nodes with the same value in one block,
1162 * the exp_gen valueset can only contain one of them. */
1163 set_opt_global_cse(0);
1164 new_identities(irg);
1165 irg_walk_graph(irg, NULL, cse_walker, &a_env);
1167 DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg));
1169 /* Switch on GCSE. We need it to correctly compute
1170 the value of a node, which is independent from
1172 set_opt_global_cse(1);
1173 new_identities(irg);
1175 /* setup environment */
1176 obstack_init(&obst);
1179 a_env.start_block = get_irg_start_block(irg);
1180 a_env.end_block = get_irg_end_block(irg);
1183 /* allocate block info */
1184 irg_walk_blkwise_graph(irg, block_info_walker, NULL, &a_env);
1186 /* generate exp_gen */
1187 irg_walk_blkwise_dom_top_down(irg, NULL, topo_walker, &a_env);
1188 dump_all_expgen_sets(a_env.list);
1190 /* compute the avail_out sets for all blocks */
1191 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1193 /* compute the anticipated value sets for all blocks */
1195 a_env.first_iter = 1;
1197 /* antic_in passes */
1199 DB((dbg, LEVEL_1, "= Antic_in Iteration %d ========================\n",
1202 irg_walk_blkwise_graph(irg, compute_antic, NULL, &a_env);
1203 a_env.first_iter = 0;
1204 DB((dbg, LEVEL_1, "----------------------------------------------\n"));
1205 /* TODO bad endless loop protection */
1206 } while (a_env.changes != 0 && antic_iter < 40);
1208 /* compute redundant expressions */
1210 a_env.last_idx = get_irg_last_idx(irg);
1213 DB((dbg, LEVEL_1, "= Insert Iteration %d ==========================\n", insert_iter));
1215 /* TODO topologically top down would be better; fewer iterations. */
1216 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1217 DB((dbg, LEVEL_1, "----------------------------------------------\n"));
1218 } while (a_env.changes != 0);
1220 /* last step: eliminate nodes */
1221 irg_walk_graph(irg, NULL, eliminate, &a_env);
1222 eliminate_nodes(a_env.pairs);
1224 /* clean up: delete all sets */
1225 for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
1226 ir_valueset_del(bl_info->exp_gen);
1227 ir_valueset_del(bl_info->avail_out);
1228 ir_valueset_del(bl_info->antic_in);
1229 ir_nodehashmap_destroy(bl_info->trans);
1230 free(bl_info->trans);
1231 if (bl_info->new_set)
1232 ir_valueset_del(bl_info->new_set);
1235 obstack_free(&obst, NULL);
1237 /* pin the graph again.
1238 This is needed due to the use of set_opt_global_cse(1) */
1239 set_irg_pinned(irg, op_pin_state_pinned);
1240 restore_optimization_state(&state);
1244 /* Creates an ir_graph pass for do_gvn_pre. */
1245 ir_graph_pass_t *do_gvn_pre_pass(const char *name)
1247 return def_graph_pass(name ? name : "gvn_pre", do_gvn_pre);
1248 } /* do_gvn_pre_pass */