2 * Copyright (C) 1995-2007 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, Rubino Geiss
28 * Currently completely broken because our sets do NOT preserve
29 * the topological sort!
35 #include "iroptimize.h"
39 #include "irgraph_t.h"
54 /** The debug module handle. */
55 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
59 typedef struct set value_set;
62 typedef struct pset node_set;
64 /** An entry in the value set. */
65 typedef struct value_entry {
66 ir_node *node; /**< the node */
67 ir_node *value; /**< the value of the node */
70 /** Additional info we need for every block. */
71 typedef struct block_info {
72 node_set *nodes; /**< The set of nodes per block. */
73 value_set *avail_out; /**< The Avail_out set for a block. */
74 node_set *antic_in; /**< The Antic_in set for a block. */
75 value_set *new_set; /**< The set of all new values for a block. */
76 ir_node *avail; /**< The get_map(avail, block) result. */
77 int not_found; /**< Non-zero, if avail was not found in this block. */
78 struct block_info *next; /**< Links all entries, so we can recover the sets easily. */
82 * A pair of nodes that must be exchanged.
83 * We must defer the exchange because our hash-sets cannot
84 * find an already replace node else.
86 typedef struct elim_pair {
87 ir_node *old_node; /**< The old node that will be replaced. */
88 ir_node *new_node; /**< The new node. */
89 struct elim_pair *next; /**< Links all entries in a list. */
92 /** The environment for the GVN-PRE algorithm */
93 typedef struct pre_env {
94 struct obstack *obst; /**< The obstack to allocate on. */
95 node_set *trans_set; /**< The set of all translated values. */
96 ir_node *start_block; /**< The start block of the current graph. */
97 ir_node *end_block; /**< The end block of the current graph */
98 block_info *list; /**< Links all block info entires for easier recovery. */
99 elim_pair *pairs; /**< A list of node pairs that must be eliminated. */
100 char changes; /**< Non-zero, if calculation of Antic_in has changed. */
101 char first_iter; /**< non-zero for first iteration */
104 /* ---------- Functions for Node sets ---------- */
106 #define node_set_first(s) pset_first(s)
107 #define node_set_next(s) pset_next(s)
108 #define node_set_break(s) pset_break(s)
109 #define node_set_foreach(v, s) for ((v) = node_set_first(s); (v); (v) = node_set_next(s))
112 * Creates a new node set.
114 static node_set *new_node_set(void) {
115 return new_pset(identities_cmp, 8);
119 * Deletes a node set.
121 static void del_node_set(node_set *set) {
126 * Add a node to the set.
128 static ir_node *node_add(node_set *set, ir_node *node) {
129 return identify_remember(set, node);
133 * Remove a node from a node set.
135 static void node_set_remove(node_set *set, ir_node *node) {
136 pset_remove(set, node, ir_node_hash(node));
140 * Return the number of entries in a node set.
142 static int node_set_count(node_set *set) {
143 return pset_count(set);
147 /** computes dst = dst \/ src for node sets */
148 static void node_union(node_set *dst, node_set *src)
151 node_set_foreach(entry, src) {
152 node_add(dst, entry);
158 * Lookup a node in a node set.
160 static ir_node *node_lookup(node_set *set, ir_node *n)
162 return pset_find(set, n, ir_node_hash(n));
166 /* ---------- Functions for Value sets ---------- */
168 #define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
171 * calculate a hash value for a value represented by a node
173 static unsigned value_hash(ir_node *value) {
174 return ir_node_hash(value);
178 * Compare two value entries.
180 static int value_cmp(const void *elt, const void *key, size_t size)
182 const value_entry *e1 = elt;
183 const value_entry *e2 = key;
186 return identities_cmp(e1->value, e2->value);
189 /** Create a new value set. */
190 static value_set *new_value_set(void) {
191 return new_set(value_cmp, 8);
194 /** Deletes a value set. */
195 static void del_value_set(value_set *set) {
200 * Add a node node representing the value value to the set.
202 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
207 return set_insert(set, &key, sizeof(key), value_hash(value));
210 /** computes dst = dst \/ src for value sets */
211 static void value_union(value_set *dst, value_set *src)
214 value_set_foreach(entry, src)
215 value_add(dst, entry->node, entry->value);
218 /** computes dst = dst \/ (value_set)src for value sets */
219 static void value_union_nodes(value_set *dst, node_set *src)
222 node_set_foreach(n, src)
223 value_add(dst, n, n);
227 * Lookup a value in a value set.
229 static ir_node *value_lookup(value_set *value_set, ir_node *n)
234 e = set_find(value_set, &key, sizeof(key), value_hash(n));
235 return e ? e->node : NULL;
239 * Add or replace a value in a set by an node computing the same
240 * value in a dominator block.
242 * @return non-zero if a replacement took place
244 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
246 value_entry *e = value_add(set, node, value);
248 if (e->node != node) {
249 /* node must dominate old one here */
250 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
259 * Returns non-zero if a node is movable.
261 static int is_nice_value(ir_node *n) {
265 n = get_Proj_pred(n);
266 mode = get_irn_mode(n);
268 * FIXME: For now, we cannot handle Div/even if it's movable.
269 * That should be fixed.
271 if (!mode_is_data(mode))
273 if (is_irn_constlike(n))
275 return (get_irn_pinned(n) != op_pin_state_pinned);
282 static void dump_node_set(node_set *set, char *txt, ir_node *block)
287 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
289 node_set_foreach(n, set) {
291 DB((dbg, LEVEL_2, "\n"));
292 DB((dbg, LEVEL_2, " %+F,", n));
295 DB((dbg, LEVEL_2, "\n}\n"));
301 static void dump_value_set(value_set *set, char *txt, ir_node *block)
306 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
308 value_set_foreach(e, set) {
310 DB((dbg, LEVEL_2, "\n"));
311 if (e->node != e->value)
312 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
314 DB((dbg, LEVEL_2, " %+F,", e->node));
317 DB((dbg, LEVEL_2, "\n}\n"));
321 #define dump_node_set(set, txt, block)
322 #define dump_value_set(set, txt, block)
323 #endif /* DEBUG_libfirm */
327 * Return the block info of a block
329 static block_info *get_block_info(ir_node *block) {
330 return get_irn_link(block);
334 * Computes Avail_out(block):
336 * Avail_in(block) = Avail_out(dom(block))
337 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
340 * This function must be called in the top-down dominance order:
341 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
343 static void compute_avail_top_down(ir_node *block, void *ctx)
346 block_info *dom_info;
347 block_info *info = get_block_info(block);
350 /* we don't need the end block Avail */
351 if (block == env->end_block)
355 * First add all nodes from the dominator.
356 * This must be done to ensure that Antic_out contains the leader
357 * for every node. The root has no dominator.
359 if (block != env->start_block) {
360 dom_blk = get_Block_idom(block);
361 assert(is_Block(dom_blk));
363 dom_info = get_block_info(dom_blk);
366 value_union(info->avail_out, dom_info->avail_out);
368 value_union_nodes(info->avail_out, info->nodes);
370 dump_value_set(info->avail_out, "Avail_out", block);
374 * returns non-zero if a tree node must be copied because of
377 static int need_copy(ir_node *node, ir_node *block)
381 /* Phi always stop the recursion */
383 return get_nodes_block(node) == block;
385 if (! is_nice_value(node))
388 /* check predecessor */
389 arity = get_irn_intra_arity(node);
390 for (i = 0; i < arity; ++i) {
391 ir_node *pred = get_irn_intra_n(node, i);
392 ir_node *local_bl = get_irn_intra_n(pred, -1);
393 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
395 pred = leader != NULL ? leader : pred;
396 if (need_copy(pred, block))
405 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
407 int i, arity, need_new;
408 ir_node *res, *nn, **in;
410 /* Phi always stop the recursion */
412 if (get_nodes_block(node) == block)
413 return get_Phi_pred(node, pos);
417 if (! is_nice_value(node))
420 arity = get_irn_intra_arity(node);
422 NEW_ARR_A(ir_node *, in, arity);
426 ir_node *pred = get_irn_intra_n(node, i);
427 ir_node *pred_blk = get_nodes_block(pred);
428 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
429 in[i] = translate(leader ? leader : pred, block, pos, env);
430 need_new |= (in[i] != pred);
438 get_irn_dbg_info(node),
440 get_Block_cfgpred_block(block, pos),
445 /* We need the attribute copy here, because the Hash value of a
446 node might depend on that. */
447 copy_node_attr(node, nn);
448 res = node_add(env->trans_set, nn);
450 obstack_free(env->obst, nn);
452 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
460 * Implements phi_translate.
462 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
467 if (! need_copy(node, block))
470 /* Create a copy of the node in the pos'th predecessor block.
471 Use our environmental obstack, as these nodes are always
473 old = current_ir_graph->obst;
474 current_ir_graph->obst = env->obst;
475 res = translate(node, block, pos, env);
476 current_ir_graph->obst = old;
479 } /* phi_translate */
483 * Implements phi_translate.
485 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
492 if (get_nodes_block(node) == block)
493 return get_Phi_pred(node, pos);
497 arity = get_irn_intra_arity(node);
499 /* check if the node has at least one Phi predecessor */
500 for (i = 0; i < arity; ++i) {
501 ir_node *pred = get_irn_intra_n(node, i);
502 ir_node *pred_bl = get_nodes_block(pred);
503 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
505 leader = leader != NULL ? leader : pred;
506 if (is_Phi(leader) && get_nodes_block(pred) == block)
510 /* no Phi in the predecessors */
514 /* Create a copy of the node in the pos'th predecessor block.
515 Use our environmental obstack, as these nodes are always
517 old = current_ir_graph->obst;
518 current_ir_graph->obst = env->obst;
520 get_irn_dbg_info(node),
527 /* We need the attribute copy here, because the Hash value of a
528 node might depend on that. */
529 copy_node_attr(node, nn);
531 set_nodes_block(nn, get_nodes_block(node));
532 for (i = 0; i < arity; ++i) {
533 ir_node *pred = get_irn_intra_n(node, i);
534 ir_node *pred_bl = get_nodes_block(pred);
535 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
537 leader = leader != NULL ? leader : pred;
538 if (is_Phi(leader) && get_nodes_block(pred) == block)
539 set_irn_n(nn, i, get_Phi_pred(leader, pos));
541 set_irn_n(nn, i, leader);
543 res = node_add(env->trans_set, nn);
544 current_ir_graph->obst = old;
547 obstack_free(env->obst, nn);
549 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
552 } /* phi_translate */
555 * check if a node n is clean in block block.
557 static int _is_clean(ir_node *n, ir_node *block)
561 if (get_nodes_block(n) != block)
569 if (! is_nice_value(n))
571 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
572 ir_node *pred = get_irn_n(n, i);
573 if (! _is_clean(pred, block))
583 * check if a node n is clean.
585 static int is_clean(ir_node *n)
587 int res = _is_clean(n, get_nodes_block(n));
593 * This function is called for node sets with is_clean
594 * nodes only, so we must just remove nodes that don't
595 * have available inputs
597 static void clean_node_set(node_set *set, ir_node *blk)
599 ir_node *n, *pred, *pred_blk;
603 for (n = node_set_first(set); n; n = node_set_next(set)) {
604 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
605 pred = get_irn_intra_n(n, i);
607 pred_blk = get_nodes_block(pred);
608 if (block_dominates(pred_blk, blk))
610 /* pred do not dominate it, but may be in the set */
611 if (node_lookup(set, pred) != NULL)
613 /* we found a node that must be removed */
615 node_set_remove(set, n);
616 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
623 * computes Antic_in(block):
625 static void compute_antic(ir_node *block, void *ctx)
628 block_info *succ_info;
629 block_info *info = get_block_info(block);
633 /* no need for computations in start block */
634 if (block == env->start_block)
637 size = node_set_count(info->antic_in);
639 /* the end block has no successor */
640 if (block != env->end_block) {
641 int n_succ = get_Block_n_cfg_outs(block);
644 ir_node *node, *list;
647 /* find blocks position in succ's block predecessors */
648 succ = get_Block_cfg_out(block, 0);
649 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
650 if (get_Block_cfgpred_block(succ, i) == block) {
657 succ_info = get_block_info(succ);
658 /* translate into list: we cannot insert into a set we iterate
659 * and succ might be equal to block for endless loops */
661 node_set_foreach(node, succ_info->antic_in) {
662 set_irn_link(node, list);
665 for (node = list; node; node = get_irn_link(node)) {
666 ir_node *trans = phi_translate(node, succ, pos, env);
669 node_add(info->antic_in, trans);
674 block_info *succ0_info;
679 /* Select a successor to compute the disjoint of all Nodes
680 sets, it might be useful to select the block with the
681 smallest number of nodes. For simplicity we choose the
683 succ0 = get_Block_cfg_out(block, 0);
684 succ0_info = get_block_info(succ0);
685 node_set_foreach(n, succ0_info->antic_in) {
686 /* we need the disjoint */
687 for (i = 1; i < n_succ; ++i) {
688 ir_node *succ = get_Block_cfg_out(block, i);
689 block_info *succ_info = get_block_info(succ);
690 if (node_lookup(succ_info->antic_in, n) == NULL)
694 /* we found a node that is common in all Antic_in(succ(b)),
695 put it in Antic_in(b) */
696 node_add(info->antic_in, n);
702 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
703 * It is enough to do this in the first iteration, because
704 * the set info->nodes is not changed anymore.
706 if (env->first_iter) {
708 node_set_foreach(n, info->nodes) {
710 node_add(info->antic_in, n);
715 // clean_node_set(info->antic_in, block);
716 (void) clean_node_set;
718 dump_node_set(info->antic_in, "Antic_in", block);
719 if (size != node_set_count(info->antic_in)) {
720 /* the Antic_in set has changed */
723 } /* compute_antic */
726 * allocate a block info
728 static void alloc_blk_info(ir_node *block, void *ctx)
732 block_info *info = obstack_alloc(env->obst, sizeof(*info));
734 set_irn_link(block, info);
735 info->nodes = new_node_set();
736 info->antic_in = new_node_set();
737 info->avail_out = new_value_set();
740 info->new_set = NULL;
741 info->next = env->list;
744 /* fill the nodes set, we will need it later */
745 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
746 ir_node *n = get_irn_out(block, i);
748 set_irn_link(n, NULL);
750 /* we cannot optimize pinned nodes, so do not remember them */
751 if (is_nice_value(n))
752 node_add(info->nodes, n);
757 * Perform insertion of partially redundant values.
758 * For every Block node, do the following:
759 * 1. Propagate the NEW_SETS of the dominator into the current block.
760 * If the block has multiple predecessors,
761 * 2a. Iterate over the ANTIC expressions for the block to see if
762 * any of them are partially redundant.
763 * 2b. If so, insert them into the necessary predecessors to make
764 * the expression fully redundant.
765 * 2c. Insert a new Phi merging the values of the predecessors.
766 * 2d. Insert the new Phi, and the new expressions, into the
769 static void insert_nodes(ir_node *block, void *ctx)
773 ir_node *e, *idom, *first_s, *worklist;
774 block_info *curr_info, *idom_info;
775 int pos, arity = get_irn_intra_arity(block);
776 int all_same, by_some, updated;
778 /* ensure that even the start block has a new_set */
779 curr_info = get_block_info(block);
780 if (curr_info->new_set)
781 del_value_set(curr_info->new_set);
782 curr_info->new_set = new_value_set();
784 if (block == env->start_block)
787 idom = get_Block_idom(block);
788 idom_info = get_block_info(idom);
790 /* update the new_sets */
792 dump_value_set(idom_info->new_set, "[New Set]", idom);
793 value_set_foreach(entry, idom_info->new_set) {
794 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
797 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
802 /* convert the set into a list. This allows the removal of
803 * elements from the set */
805 node_set_foreach(e, curr_info->antic_in) {
806 set_irn_link(e, worklist);
810 for (e = worklist; e != NULL; e = get_irn_link(e)) {
813 /* If the value was already computed in the dominator, then
814 it is totally redundant. Hence we have nothing to insert. */
815 if (value_lookup(idom_info->avail_out, e)) {
816 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
825 /* for all predecessor blocks */
826 for (pos = 0; pos < arity; ++pos) {
827 block_info *pred_info;
828 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
829 ir_node *e_prime, *v_prime, *e_dprime;
831 /* ignore bad blocks. */
832 if (is_Bad(pred_blk))
835 e_prime = phi_translate(e, block, pos, env);
838 pred_info = get_block_info(pred_blk);
839 e_dprime = value_lookup(pred_info->avail_out, v_prime);
841 if (e_dprime == NULL) {
843 pred_info->avail = e_prime;
844 pred_info->not_found = 1;
847 mode = get_irn_mode(e_dprime);
849 pred_info->avail = e_dprime;
850 pred_info->not_found = 0;
854 else if (first_s != e_dprime)
857 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
861 /* If it's not the same value already existing along every predecessor, and
862 it's defined by some predecessor, it is partially redundant. */
863 if (! all_same && by_some) {
866 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
868 in = xmalloc(arity * sizeof(*in));
869 /* for all predecessor blocks */
870 for (pos = 0; pos < arity; ++pos) {
871 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
872 block_info *pred_info = get_block_info(pred_blk);
874 /* ignore bad blocks. */
875 if (is_Bad(pred_blk)) {
880 /* ignore blocks that already have the expression */
881 if (pred_info->not_found) {
882 ir_node *e_prime = pred_info->avail;
884 if (!is_Phi(e_prime)) {
885 mode = get_irn_mode(e_prime);
887 get_irn_dbg_info(e_prime),
888 current_ir_graph, pred_blk,
891 get_irn_arity(e_prime),
892 get_irn_in(e_prime) + 1);
893 copy_node_attr(e_prime, nn);
895 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
896 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
899 in[pos] = pred_info->avail;
901 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
903 value_add_or_replace(curr_info->avail_out, phi, e);
904 value_add(curr_info->new_set, phi, e);
905 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
907 /* the good case: we really replace an instruction */
908 node_set_remove(curr_info->antic_in, e);
912 } /* node_set_foreach */
916 * Do the elimination step: collect all changes
917 * We cannot do the changes right here, as this would change
918 * the hash values of the nodes in the avail_out set!
920 static void collect_elim_pairs(ir_node *block, void *ctx)
923 block_info *curr_info = get_block_info(block);
926 dump_node_set(curr_info->nodes, "Updating nodes", block);
927 node_set_foreach(v, curr_info->nodes) {
928 ir_node *l = value_lookup(curr_info->avail_out, v);
932 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
936 p->next = env->pairs;
943 * Do all the recorded changes and optimize
944 * newly created Phi's.
946 static void eliminate_nodes(elim_pair *pairs)
950 for (p = pairs; p != NULL; p = p->next) {
951 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
953 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
954 * which we can optimize here
956 if (is_Phi(p->new_node)) {
960 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
961 ir_node *pred = get_irn_n(p->new_node, i);
963 if (pred != p->old_node) {
974 exchange(p->old_node, p->new_node);
979 * Argh: Endless loops cause problems, because the
980 * insert algorithm did not terminate. We get translated nodes that
981 * references the origin. These nodes are translated again and again...
983 * The current fix is to use post-dominance. This simple ignores
984 * endless loops, ie we cannot optimize them.
986 void do_gvn_pre(ir_graph *irg)
990 optimization_state_t state;
992 unsigned antic_iter, insert_iter;
994 assert(!"COMPLETELY BROKEN YET, DO NOT USE");
996 /* register a debug mask */
997 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
998 firm_dbg_set_mask(dbg, SET_LEVEL_2);
1000 obstack_init(&obst);
1002 a_env.trans_set = new_node_set();
1004 a_env.start_block = get_irg_start_block(irg);
1005 a_env.end_block = get_irg_end_block(irg);
1008 /* critical edges MUST be removed */
1009 remove_critical_cf_edges(irg);
1011 /* we need dominator for Antic_out calculation */
1012 if (get_irg_dom_state(irg) != dom_consistent)
1014 if (get_irg_postdom_state(irg) != dom_consistent)
1015 compute_postdoms(irg);
1016 /* we get all nodes of a block by following outs */
1017 if (get_irg_outs_state(irg) != outs_consistent)
1018 compute_irg_outs(irg);
1021 * Switch on GCSE. We need it to correctly compute
1022 * the leader of a node by hashing.
1024 save_optimization_state(&state);
1025 set_opt_global_cse(1);
1027 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1028 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1030 /* allocate block info for all blocks */
1031 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1033 /* compute the available value sets for all blocks */
1034 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1036 /* compute the anticipated value sets for all blocks */
1037 inc_irg_visited(irg);
1039 a_env.first_iter = 1;
1041 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1043 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1044 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1045 a_env.first_iter = 0;
1046 DB((dbg, LEVEL_1, "------------------------\n"));
1047 } while (a_env.changes != 0);
1049 /* compute redundant expressions */
1052 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1054 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1055 DB((dbg, LEVEL_1, "------------------------\n"));
1056 } while (a_env.changes != 0);
1058 /* last step: eliminate nodes */
1059 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1060 eliminate_nodes(a_env.pairs);
1062 restore_optimization_state(&state);
1064 /* clean up: delete all sets */
1065 for (p = a_env.list; p != NULL; p = p->next) {
1067 del_node_set(p->antic_in);
1069 del_value_set(p->avail_out);
1071 del_node_set(p->nodes);
1073 del_value_set(p->new_set);
1075 del_node_set(a_env.trans_set);
1076 obstack_free(&obst, NULL);
1077 set_irg_pinned(irg, op_pin_state_pinned);
1080 set_irg_outs_inconsistent(irg);
1081 set_irg_loopinfo_inconsistent(irg);