3 * File name: ir/opt/gvn_pre.c
4 * Purpose: Global Value Numbering Partial Redundancy Elimination
5 * (VanDrunen Hosking 2004)
6 * Author: Michael Beck, Rubino Geiss
9 * Copyright: (c) 1998-2006 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
26 #include "irgraph_t.h"
41 /** The debug module handle. */
42 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
46 typedef struct set value_set;
49 typedef struct pset node_set;
51 /** An entry in the value set. */
52 typedef struct value_entry {
53 ir_node *node; /**< the node */
54 ir_node *value; /**< the value of the node */
57 /** Additional info we need for every block. */
58 typedef struct block_info {
59 node_set *nodes; /**< The set of nodes per block. */
60 value_set *avail_out; /**< The Avail_out set for a block. */
61 node_set *antic_in; /**< The Antic_in set for a block. */
62 value_set *new_set; /**< The set of all new values for a block. */
63 ir_node *avail; /**< The get_map(avail, block) result. */
64 int not_found; /**< Non-zero, if avail was not found in this block. */
65 struct block_info *next; /**< Links all entries, so we can recover the sets easily. */
69 * A pair of nodes that must be exchanged.
70 * We must defer the exchange because our hash-sets cannot
71 * find an already replace node else.
73 typedef struct elim_pair {
74 ir_node *old_node; /**< The old node that will be replaced. */
75 ir_node *new_node; /**< The new node. */
76 struct elim_pair *next; /**< Links all entries in a list. */
79 /** The environment for the GVN-PRE algorithm */
80 typedef struct pre_env {
81 struct obstack *obst; /**< The obstack to allocate on. */
82 node_set *trans_set; /**< The set of all translated values. */
83 ir_node *start_block; /**< The start block of the current graph. */
84 ir_node *end_block; /**< The end block of the current graph */
85 block_info *list; /**< Links all block info entires for easier recovery. */
86 elim_pair *pairs; /**< A list of node pairs that must be eliminated. */
87 char changes; /**< Non-zero, if calculation of Antic_in has changed. */
88 char first_iter; /**< non-zero for first iteration */
91 /* ---------- Functions for Node sets ---------- */
93 #define node_set_first(s) pset_first(s)
94 #define node_set_next(s) pset_next(s)
95 #define node_set_break(s) pset_break(s)
96 #define node_set_foreach(v, s) for ((v) = node_set_first(s); (v); (v) = node_set_next(s))
99 * Creates a new node set.
101 static node_set *new_node_set(void) {
102 return new_pset(identities_cmp, 8);
106 * Deletes a node set.
108 static void del_node_set(node_set *set) {
113 * Add a node to the set.
115 static ir_node *node_add(node_set *set, ir_node *node) {
116 return identify_remember(set, node);
120 * Remove a node from a node set.
122 static void node_set_remove(node_set *set, ir_node *node) {
123 pset_remove(set, node, ir_node_hash(node));
127 * Return the number of entries in a node set.
129 static int node_set_count(node_set *set) {
130 return pset_count(set);
133 /** computes dst = dst \/ src for node sets */
134 static void node_union(node_set *dst, node_set *src)
137 node_set_foreach(entry, src)
138 node_add(dst, entry);
142 * Lookup a node in a node set.
144 static ir_node *node_lookup(node_set *set, ir_node *n)
146 return pset_find(set, n, ir_node_hash(n));
150 /* ---------- Functions for Value sets ---------- */
152 #define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
155 * calculate a hash value for a value represented by a node
157 static unsigned value_hash(ir_node *value) {
158 return ir_node_hash(value);
162 * Compare two value entries.
164 static int value_cmp(const void *elt, const void *key, size_t size)
166 const value_entry *e1 = elt;
167 const value_entry *e2 = key;
169 return identities_cmp(e1->value, e2->value);
172 /** Create a new value set. */
173 static value_set *new_value_set(void) {
174 return new_set(value_cmp, 8);
177 /** Deletes a value set. */
178 static void del_value_set(value_set *set) {
183 * Add a node node representing the value value to the set.
185 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
190 return set_insert(set, &key, sizeof(key), value_hash(value));
193 /** computes dst = dst \/ src for value sets */
194 static void value_union(value_set *dst, value_set *src)
197 value_set_foreach(entry, src)
198 value_add(dst, entry->node, entry->value);
201 /** computes dst = dst \/ (value_set)src for value sets */
202 static void value_union_nodes(value_set *dst, node_set *src)
205 node_set_foreach(n, src)
206 value_add(dst, n, n);
210 * Lookup a value in a value set.
212 static ir_node *value_lookup(value_set *value_set, ir_node *n)
217 e = set_find(value_set, &key, sizeof(key), value_hash(n));
218 return e ? e->node : NULL;
222 * Add or replace a value in a set by an node computing the same
223 * value in a dominator block.
225 * @return non-zero if a replacement took place
227 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
229 value_entry *e = value_add(set, node, value);
231 if (e->node != node) {
232 /* node must dominate old one here */
233 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
242 * Returns non-zero if a node is movable.
244 static int is_nice_value(ir_node *n) {
248 n = get_Proj_pred(n);
249 mode = get_irn_mode(n);
251 * FIXME: For now, we cannot handle Div/even if it's movable.
252 * That should be fixed.
254 if (!mode_is_data(mode))
256 if (is_irn_constlike(n))
258 return (get_irn_pinned(n) != op_pin_state_pinned);
265 static void dump_node_set(node_set *set, char *txt, ir_node *block)
270 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
272 node_set_foreach(n, set) {
274 DB((dbg, LEVEL_2, "\n"));
275 DB((dbg, LEVEL_2, " %+F,", n));
278 DB((dbg, LEVEL_2, "\n}\n"));
284 static void dump_value_set(value_set *set, char *txt, ir_node *block)
289 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
291 value_set_foreach(e, set) {
293 DB((dbg, LEVEL_2, "\n"));
294 if (e->node != e->value)
295 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
297 DB((dbg, LEVEL_2, " %+F,", e->node));
300 DB((dbg, LEVEL_2, "\n}\n"));
304 #define dump_node_set(set, txt, block)
305 #define dump_value_set(set, txt, block)
306 #endif /* DEBUG_libfirm */
310 * Return the block info of a block
312 static block_info *get_block_info(ir_node *block) {
313 return get_irn_link(block);
317 * Computes Avail_out(block):
319 * Avail_in(block) = Avail_out(dom(block))
320 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
323 * This function must be called in the top-down dominance order:
324 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
326 static void compute_avail_top_down(ir_node *block, void *ctx)
329 block_info *dom_info;
330 block_info *info = get_block_info(block);
333 /* we don't need the end block Avail */
334 if (block == env->end_block)
338 * First add all nodes from the dominator.
339 * This must be done to ensure that Antic_out contains the leader
340 * for every node. The root has no dominator.
342 if (block != env->start_block) {
343 dom_blk = get_Block_idom(block);
344 assert(is_Block(dom_blk));
346 dom_info = get_block_info(dom_blk);
349 value_union(info->avail_out, dom_info->avail_out);
351 value_union_nodes(info->avail_out, info->nodes);
353 dump_value_set(info->avail_out, "Avail_out", block);
357 * returns non-zero if a tree node must be copied because of
360 static int need_copy(ir_node *node, ir_node *block)
364 /* Phi always stop the recursion */
366 return get_irn_intra_n(node, -1) == block;
368 if (! is_nice_value(node))
371 /* check predecessor */
372 arity = get_irn_intra_arity(node);
373 for (i = 0; i < arity; ++i) {
374 ir_node *pred = get_irn_intra_n(node, i);
375 ir_node *local_bl = get_irn_intra_n(pred, -1);
376 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
378 pred = leader != NULL ? leader : pred;
379 if (need_copy(pred, block))
388 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
390 int i, arity, need_new;
391 ir_node *res, *nn, **in;
393 /* Phi always stop the recursion */
395 if (get_irn_intra_n(node, -1) == block)
396 return get_Phi_pred(node, pos);
400 if (! is_nice_value(node))
403 arity = get_irn_intra_arity(node);
405 NEW_ARR_A(ir_node *, in, arity);
409 ir_node *pred = get_irn_intra_n(node, i);
410 ir_node *pred_blk = get_irn_intra_n(pred, -1);
411 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
412 in[i] = translate(leader ? leader : pred, block, pos, env);
413 need_new |= (in[i] != pred);
421 get_irn_dbg_info(node),
423 get_Block_cfgpred_block(block, pos),
428 /* We need the attribute copy here, because the Hash value of a
429 node might depend on that. */
430 copy_node_attr(node, nn);
431 res = node_add(env->trans_set, nn);
433 obstack_free(env->obst, nn);
435 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
442 * Implements phi_translate.
444 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
449 if (! need_copy(node, block))
452 /* Create a copy of the node in the pos'th predecessor block.
453 Use our environmental obstack, as these nodes are always
455 old = current_ir_graph->obst;
456 current_ir_graph->obst = env->obst;
457 res = translate(node, block, pos, env);
458 current_ir_graph->obst = old;
461 } /* phi_translate */
464 * Implements phi_translate.
466 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
471 ir_node *pred_block = get_Block_cfgpred_block(block, pos);
472 block_info *pred_info = get_block_info(pred_block);
475 if (get_irn_intra_n(node, -1) == block)
476 return get_Phi_pred(node, pos);
480 arity = get_irn_intra_arity(node);
482 /* check if the node has at least one Phi predecessor */
483 for (i = 0; i < arity; ++i) {
484 ir_node *pred = get_irn_intra_n(node, i);
485 ir_node *pred_bl = get_irn_intra_n(pred, -1);
486 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
488 leader = leader != NULL ? leader : pred;
489 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
493 /* no Phi in the predecessors */
497 /* Create a copy of the node in the pos'th predecessor block.
498 Use our environmental obstack, as these nodes are always
500 old = current_ir_graph->obst;
501 current_ir_graph->obst = env->obst;
503 get_irn_dbg_info(node),
510 /* We need the attribute copy here, because the Hash value of a
511 node might depend on that. */
512 copy_node_attr(node, nn);
514 set_irn_n(nn, -1, get_irn_intra_n(node, -1));
515 for (i = 0; i < arity; ++i) {
516 ir_node *pred = get_irn_intra_n(node, i);
517 ir_node *pred_bl = get_irn_intra_n(pred, -1);
518 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
520 leader = leader != NULL ? leader : pred;
521 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
522 set_irn_n(nn, i, get_Phi_pred(leader, pos));
524 set_irn_n(nn, i, leader);
526 res = node_add(env->trans_set, nn);
527 current_ir_graph->obst = old;
530 obstack_free(env->obst, nn);
532 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
535 } /* phi_translate */
538 * check if a node n is clean in block block.
540 static int _is_clean(ir_node *n, ir_node *block)
544 if (get_nodes_block(n) != block)
552 if (! is_nice_value(n))
554 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
555 ir_node *pred = get_irn_n(n, i);
556 if (! _is_clean(pred, block))
566 * check if a node n is clean.
568 static int is_clean(ir_node *n)
570 int res = _is_clean(n, get_nodes_block(n));
576 * This function is called for node sets with is_clean
577 * nodes only, so we must just remove nodes that don't
578 * have available inputs
580 static void clean_node_set(node_set *set, ir_node *blk)
582 ir_node *n, *pred, *pred_blk;
586 for (n = node_set_first(set); n; n = node_set_next(set)) {
587 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
588 pred = get_irn_intra_n(n, i);
590 pred_blk = get_irn_intra_n(pred, -1);
591 if (block_dominates(pred_blk, blk))
593 /* pred do not dominate it, but may be in the set */
594 if (node_lookup(set, pred) != NULL)
596 /* we found a node that must be removed */
598 node_set_remove(set, n);
599 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
606 * computes Antic_in(block):
608 static void compute_antic(ir_node *block, void *ctx)
611 block_info *succ_info;
612 block_info *info = get_block_info(block);
616 /* no need for computations in start block */
617 if (block == env->start_block)
620 size = node_set_count(info->antic_in);
622 /* the end block has no successor */
623 if (block != env->end_block) {
624 int n_succ = get_Block_n_cfg_outs(block);
627 ir_node *node, *list;
630 /* find blocks position in succ's block predecessors */
631 succ = get_Block_cfg_out(block, 0);
632 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
633 if (get_Block_cfgpred_block(succ, i) == block) {
640 succ_info = get_block_info(succ);
641 /* translate into list: we cannot insert into a set we iterate
642 * and succ might be equal to block for endless loops */
644 node_set_foreach(node, succ_info->antic_in) {
645 set_irn_link(node, list);
648 for (node = list; node; node = get_irn_link(node)) {
649 ir_node *trans = phi_translate(node, succ, pos, env);
652 node_add(info->antic_in, trans);
657 block_info *succ0_info;
662 /* Select a successor to compute the disjoint of all Nodes
663 sets, it might be useful to select the block with the
664 smallest number of nodes. For simplicity we choose the
666 succ0 = get_Block_cfg_out(block, 0);
667 succ0_info = get_block_info(succ0);
668 node_set_foreach(n, succ0_info->antic_in) {
669 /* we need the disjoint */
670 for (i = 1; i < n_succ; ++i) {
671 ir_node *succ = get_Block_cfg_out(block, i);
672 block_info *succ_info = get_block_info(succ);
673 if (node_lookup(succ_info->antic_in, n) == NULL)
677 /* we found a node that is common in all Antic_in(succ(b)),
678 put it in Antic_in(b) */
679 node_add(info->antic_in, n);
685 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
686 * It is enough to do this in the first iteration, because
687 * the set info->nodes is not changed anymore.
689 if (env->first_iter) {
691 node_set_foreach(n, info->nodes) {
693 node_add(info->antic_in, n);
698 // clean_node_set(info->antic_in, block);
700 dump_node_set(info->antic_in, "Antic_in", block);
701 if (size != node_set_count(info->antic_in)) {
702 /* the Antic_in set has changed */
705 } /* compute_antic */
708 * allocate a block info
710 static void alloc_blk_info(ir_node *block, void *ctx)
714 block_info *info = obstack_alloc(env->obst, sizeof(*info));
716 set_irn_link(block, info);
717 info->nodes = new_node_set();
718 info->antic_in = new_node_set();
719 info->avail_out = new_value_set();
722 info->new_set = NULL;
723 info->next = env->list;
726 /* fill the nodes set, we will need it later */
727 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
728 ir_node *n = get_irn_out(block, i);
730 set_irn_link(n, NULL);
732 /* we cannot optimize pinned nodes, so do not remember them */
733 if (is_nice_value(n))
734 node_add(info->nodes, n);
739 * Perform insertion of partially redundant values.
740 * For every Block node, do the following:
741 * 1. Propagate the NEW_SETS of the dominator into the current block.
742 * If the block has multiple predecessors,
743 * 2a. Iterate over the ANTIC expressions for the block to see if
744 * any of them are partially redundant.
745 * 2b. If so, insert them into the necessary predecessors to make
746 * the expression fully redundant.
747 * 2c. Insert a new Phi merging the values of the predecessors.
748 * 2d. Insert the new Phi, and the new expressions, into the
751 static void insert_nodes(ir_node *block, void *ctx)
755 ir_node *e, *idom, *first_s, *worklist;
756 block_info *curr_info, *idom_info;
757 int pos, arity = get_irn_intra_arity(block);
758 int all_same, by_some, updated;
760 /* ensure that even the start block has a new_set */
761 curr_info = get_block_info(block);
762 if (curr_info->new_set)
763 del_value_set(curr_info->new_set);
764 curr_info->new_set = new_value_set();
766 if (block == env->start_block)
769 idom = get_Block_idom(block);
770 idom_info = get_block_info(idom);
772 /* update the new_sets */
774 dump_value_set(idom_info->new_set, "[New Set]", idom);
775 value_set_foreach(entry, idom_info->new_set) {
776 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
779 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
784 /* convert the set into a list. This allows the removal of
785 * elements from the set */
787 node_set_foreach(e, curr_info->antic_in) {
788 set_irn_link(e, worklist);
792 for (e = worklist; e != NULL; e = get_irn_link(e)) {
795 /* If the value was already computed in the dominator, then
796 it is totally redundant. Hence we have nothing to insert. */
797 if (value_lookup(idom_info->avail_out, e)) {
798 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
807 /* for all predecessor blocks */
808 for (pos = 0; pos < arity; ++pos) {
809 block_info *pred_info;
810 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
811 ir_node *e_prime, *v_prime, *e_dprime;
813 /* ignore bad blocks. */
814 if (is_Bad(pred_blk))
817 e_prime = phi_translate(e, block, pos, env);
820 pred_info = get_block_info(pred_blk);
821 e_dprime = value_lookup(pred_info->avail_out, v_prime);
823 if (e_dprime == NULL) {
825 pred_info->avail = e_prime;
826 pred_info->not_found = 1;
829 mode = get_irn_mode(e_dprime);
831 pred_info->avail = e_dprime;
832 pred_info->not_found = 0;
836 else if (first_s != e_dprime)
839 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
843 /* If it's not the same value already existing along every predecessor, and
844 it's defined by some predecessor, it is partially redundant. */
845 if (! all_same && by_some) {
848 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
850 in = xmalloc(arity * sizeof(*in));
851 /* for all predecessor blocks */
852 for (pos = 0; pos < arity; ++pos) {
853 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
854 block_info *pred_info = get_block_info(pred_blk);
856 /* ignore bad blocks. */
857 if (is_Bad(pred_blk)) {
862 /* ignore blocks that already have the expression */
863 if (pred_info->not_found) {
864 ir_node *e_prime = pred_info->avail;
866 if (!is_Phi(e_prime)) {
867 mode = get_irn_mode(e_prime);
869 get_irn_dbg_info(e_prime),
870 current_ir_graph, pred_blk,
873 get_irn_arity(e_prime),
874 get_irn_in(e_prime) + 1);
875 copy_node_attr(e_prime, nn);
877 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
878 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
881 in[pos] = pred_info->avail;
883 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
885 value_add_or_replace(curr_info->avail_out, phi, e);
886 value_add(curr_info->new_set, phi, e);
887 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
889 /* the good case: we really replace an instruction */
890 node_set_remove(curr_info->antic_in, e);
894 } /* node_set_foreach */
898 * Do the elimination step: collect all changes
899 * We cannot do the changes right here, as this would change
900 * the hash values of the nodes in the avail_out set!
902 static void collect_elim_pairs(ir_node *block, void *ctx)
905 block_info *curr_info = get_block_info(block);
908 dump_node_set(curr_info->nodes, "Updating nodes", block);
909 node_set_foreach(v, curr_info->nodes) {
910 ir_node *l = value_lookup(curr_info->avail_out, v);
914 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
918 p->next = env->pairs;
925 * Do all the recorded changes and optimize
926 * newly created Phi's.
928 static void eliminate_nodes(elim_pair *pairs)
932 for (p = pairs; p != NULL; p = p->next) {
933 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
935 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
936 * which we can optimize here
938 if (is_Phi(p->new_node)) {
942 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
943 ir_node *pred = get_irn_n(p->new_node, i);
945 if (pred != p->old_node) {
956 exchange(p->old_node, p->new_node);
961 * Argh: Endless loops cause problems, because the
962 * insert algorithm did not terminate. We get tranalated nodes that
963 * references the origin. These nodes are translated again and again...
965 * The current fix is to use post-dominance. This simple ignores
966 * endless loops, ie we cannot optimize them.
968 void do_gvn_pre(ir_graph *irg)
972 optimization_state_t state;
974 unsigned antic_iter, insert_iter;
976 /* register a debug mask */
977 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
978 firm_dbg_set_mask(dbg, SET_LEVEL_2);
982 a_env.trans_set = new_node_set();
984 a_env.start_block = get_irg_start_block(irg);
985 a_env.end_block = get_irg_end_block(irg);
988 /* Move Proj's into the same block as their args,
989 else we would assign the result to wrong blocks */
990 normalize_proj_nodes(irg);
992 /* critical edges MUST be removed */
993 remove_critical_cf_edges(irg);
995 /* we need dominator for Antic_out calculation */
996 if (get_irg_dom_state(irg) != dom_consistent)
998 if (get_irg_postdom_state(irg) != dom_consistent)
999 compute_postdoms(irg);
1000 /* we get all nodes of a block by following outs */
1001 if (get_irg_outs_state(irg) != outs_consistent)
1002 compute_irg_outs(irg);
1005 * Switch on GCSE. We need it to correctly compute
1006 * the leader of a node by hashing.
1008 save_optimization_state(&state);
1009 set_opt_global_cse(1);
1011 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1012 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1014 /* allocate block info for all blocks */
1015 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1017 /* compute the available value sets for all blocks */
1018 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1020 /* compute the anticipated value sets for all blocks */
1021 inc_irg_visited(irg);
1023 a_env.first_iter = 1;
1025 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1027 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1028 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1029 a_env.first_iter = 0;
1030 DB((dbg, LEVEL_1, "------------------------\n"));
1031 } while (a_env.changes != 0);
1033 /* compute redundant expressions */
1036 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1038 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1039 DB((dbg, LEVEL_1, "------------------------\n"));
1040 } while (a_env.changes != 0);
1042 /* last step: eliminate nodes */
1043 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1044 eliminate_nodes(a_env.pairs);
1046 restore_optimization_state(&state);
1048 /* clean up: delete all sets */
1049 for (p = a_env.list; p != NULL; p = p->next) {
1051 del_node_set(p->antic_in);
1053 del_value_set(p->avail_out);
1055 del_node_set(p->nodes);
1057 del_value_set(p->new_set);
1059 del_node_set(a_env.trans_set);
1060 obstack_free(&obst, NULL);
1061 set_irg_pinned(irg, op_pin_state_pinned);
1064 set_irg_outs_inconsistent(irg);
1065 set_irg_loopinfo_inconsistent(irg);