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.
19 #include "irgraph_t.h"
35 /** The debug module handle. */
36 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
40 typedef struct set value_set;
43 typedef struct pset node_set;
45 /** An entry in the value set. */
46 typedef struct value_entry {
47 ir_node *node; /**< the node */
48 ir_node *value; /**< the value of the node */
51 /** Additional info we need for every block. */
52 typedef struct block_info {
53 node_set *nodes; /**< The set of nodes per block. */
54 value_set *avail_out; /**< The Avail_out set for a block. */
55 node_set *antic_in; /**< The Antic_in set for a block. */
56 value_set *new_set; /**< The set of all new values for a block. */
57 ir_node *avail; /**< The get_map(avail, block) result. */
58 int not_found; /**< Non-zero, if avail was not found in this block. */
59 struct block_info *next; /**< Links all entries, so we can recover the sets easily. */
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. */
73 /** The environment for the GVN-PRE algorithm */
74 typedef struct pre_env {
75 struct obstack *obst; /**< The obstack to allocate on. */
76 node_set *trans_set; /**< The set of all translated values. */
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 entires for easier recovery. */
80 elim_pair *pairs; /**< A list of node pairs that must be eliminated. */
81 char changes; /**< Non-zero, if calculation of Antic_in has changed. */
82 char first_iter; /**< non-zero for first iteration */
85 /* ---------- Functions for Node sets ---------- */
87 #define node_set_first(s) pset_first(s)
88 #define node_set_next(s) pset_next(s)
89 #define node_set_break(s) pset_break(s)
90 #define node_set_foreach(v, s) for ((v) = node_set_first(s); (v); (v) = node_set_next(s))
93 * Creates a new node set.
95 static node_set *new_node_set(void) {
96 return new_pset(identities_cmp, 8);
100 * Deletes a node set.
102 static void del_node_set(node_set *set) {
107 * Add a node to the set.
109 static ir_node *node_add(node_set *set, ir_node *node) {
110 return identify_remember(set, node);
114 * Remove a node from a node set.
116 static void node_set_remove(node_set *set, ir_node *node) {
117 pset_remove(set, node, ir_node_hash(node));
121 * Return the number of entries in a node set.
123 static int node_set_count(node_set *set) {
124 return pset_count(set);
128 /** computes dst = dst \/ src for node sets */
129 static void node_union(node_set *dst, node_set *src)
132 node_set_foreach(entry, src) {
133 node_add(dst, entry);
139 * Lookup a node in a node set.
141 static ir_node *node_lookup(node_set *set, ir_node *n)
143 return pset_find(set, n, ir_node_hash(n));
147 /* ---------- Functions for Value sets ---------- */
149 #define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
152 * calculate a hash value for a value represented by a node
154 static unsigned value_hash(ir_node *value) {
155 return ir_node_hash(value);
159 * Compare two value entries.
161 static int value_cmp(const void *elt, const void *key, size_t size)
163 const value_entry *e1 = elt;
164 const value_entry *e2 = key;
166 return identities_cmp(e1->value, e2->value);
169 /** Create a new value set. */
170 static value_set *new_value_set(void) {
171 return new_set(value_cmp, 8);
174 /** Deletes a value set. */
175 static void del_value_set(value_set *set) {
180 * Add a node node representing the value value to the set.
182 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
187 return set_insert(set, &key, sizeof(key), value_hash(value));
190 /** computes dst = dst \/ src for value sets */
191 static void value_union(value_set *dst, value_set *src)
194 value_set_foreach(entry, src)
195 value_add(dst, entry->node, entry->value);
198 /** computes dst = dst \/ (value_set)src for value sets */
199 static void value_union_nodes(value_set *dst, node_set *src)
202 node_set_foreach(n, src)
203 value_add(dst, n, n);
207 * Lookup a value in a value set.
209 static ir_node *value_lookup(value_set *value_set, ir_node *n)
214 e = set_find(value_set, &key, sizeof(key), value_hash(n));
215 return e ? e->node : NULL;
219 * Add or replace a value in a set by an node computing the same
220 * value in a dominator block.
222 * @return non-zero if a replacement took place
224 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
226 value_entry *e = value_add(set, node, value);
228 if (e->node != node) {
229 /* node must dominate old one here */
230 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
239 * Returns non-zero if a node is movable.
241 static int is_nice_value(ir_node *n) {
245 n = get_Proj_pred(n);
246 mode = get_irn_mode(n);
248 * FIXME: For now, we cannot handle Div/even if it's movable.
249 * That should be fixed.
251 if (!mode_is_data(mode))
253 if (is_irn_constlike(n))
255 return (get_irn_pinned(n) != op_pin_state_pinned);
262 static void dump_node_set(node_set *set, char *txt, ir_node *block)
267 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
269 node_set_foreach(n, set) {
271 DB((dbg, LEVEL_2, "\n"));
272 DB((dbg, LEVEL_2, " %+F,", n));
275 DB((dbg, LEVEL_2, "\n}\n"));
281 static void dump_value_set(value_set *set, char *txt, ir_node *block)
286 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
288 value_set_foreach(e, set) {
290 DB((dbg, LEVEL_2, "\n"));
291 if (e->node != e->value)
292 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
294 DB((dbg, LEVEL_2, " %+F,", e->node));
297 DB((dbg, LEVEL_2, "\n}\n"));
301 #define dump_node_set(set, txt, block)
302 #define dump_value_set(set, txt, block)
303 #endif /* DEBUG_libfirm */
307 * Return the block info of a block
309 static block_info *get_block_info(ir_node *block) {
310 return get_irn_link(block);
314 * Computes Avail_out(block):
316 * Avail_in(block) = Avail_out(dom(block))
317 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
320 * This function must be called in the top-down dominance order:
321 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
323 static void compute_avail_top_down(ir_node *block, void *ctx)
326 block_info *dom_info;
327 block_info *info = get_block_info(block);
330 /* we don't need the end block Avail */
331 if (block == env->end_block)
335 * First add all nodes from the dominator.
336 * This must be done to ensure that Antic_out contains the leader
337 * for every node. The root has no dominator.
339 if (block != env->start_block) {
340 dom_blk = get_Block_idom(block);
341 assert(is_Block(dom_blk));
343 dom_info = get_block_info(dom_blk);
346 value_union(info->avail_out, dom_info->avail_out);
348 value_union_nodes(info->avail_out, info->nodes);
350 dump_value_set(info->avail_out, "Avail_out", block);
354 * returns non-zero if a tree node must be copied because of
357 static int need_copy(ir_node *node, ir_node *block)
361 /* Phi always stop the recursion */
363 return get_irn_intra_n(node, -1) == block;
365 if (! is_nice_value(node))
368 /* check predecessor */
369 arity = get_irn_intra_arity(node);
370 for (i = 0; i < arity; ++i) {
371 ir_node *pred = get_irn_intra_n(node, i);
372 ir_node *local_bl = get_irn_intra_n(pred, -1);
373 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
375 pred = leader != NULL ? leader : pred;
376 if (need_copy(pred, block))
385 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
387 int i, arity, need_new;
388 ir_node *res, *nn, **in;
390 /* Phi always stop the recursion */
392 if (get_irn_intra_n(node, -1) == block)
393 return get_Phi_pred(node, pos);
397 if (! is_nice_value(node))
400 arity = get_irn_intra_arity(node);
402 NEW_ARR_A(ir_node *, in, arity);
406 ir_node *pred = get_irn_intra_n(node, i);
407 ir_node *pred_blk = get_irn_intra_n(pred, -1);
408 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
409 in[i] = translate(leader ? leader : pred, block, pos, env);
410 need_new |= (in[i] != pred);
418 get_irn_dbg_info(node),
420 get_Block_cfgpred_block(block, pos),
425 /* We need the attribute copy here, because the Hash value of a
426 node might depend on that. */
427 copy_node_attr(node, nn);
428 res = node_add(env->trans_set, nn);
430 obstack_free(env->obst, nn);
432 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
440 * Implements phi_translate.
442 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
447 if (! need_copy(node, block))
450 /* Create a copy of the node in the pos'th predecessor block.
451 Use our environmental obstack, as these nodes are always
453 old = current_ir_graph->obst;
454 current_ir_graph->obst = env->obst;
455 res = translate(node, block, pos, env);
456 current_ir_graph->obst = old;
459 } /* phi_translate */
463 * Implements phi_translate.
465 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
472 if (get_irn_intra_n(node, -1) == block)
473 return get_Phi_pred(node, pos);
477 arity = get_irn_intra_arity(node);
479 /* check if the node has at least one Phi predecessor */
480 for (i = 0; i < arity; ++i) {
481 ir_node *pred = get_irn_intra_n(node, i);
482 ir_node *pred_bl = get_irn_intra_n(pred, -1);
483 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
485 leader = leader != NULL ? leader : pred;
486 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
490 /* no Phi in the predecessors */
494 /* Create a copy of the node in the pos'th predecessor block.
495 Use our environmental obstack, as these nodes are always
497 old = current_ir_graph->obst;
498 current_ir_graph->obst = env->obst;
500 get_irn_dbg_info(node),
507 /* We need the attribute copy here, because the Hash value of a
508 node might depend on that. */
509 copy_node_attr(node, nn);
511 set_irn_n(nn, -1, get_irn_intra_n(node, -1));
512 for (i = 0; i < arity; ++i) {
513 ir_node *pred = get_irn_intra_n(node, i);
514 ir_node *pred_bl = get_irn_intra_n(pred, -1);
515 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
517 leader = leader != NULL ? leader : pred;
518 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
519 set_irn_n(nn, i, get_Phi_pred(leader, pos));
521 set_irn_n(nn, i, leader);
523 res = node_add(env->trans_set, nn);
524 current_ir_graph->obst = old;
527 obstack_free(env->obst, nn);
529 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
532 } /* phi_translate */
535 * check if a node n is clean in block block.
537 static int _is_clean(ir_node *n, ir_node *block)
541 if (get_nodes_block(n) != block)
549 if (! is_nice_value(n))
551 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
552 ir_node *pred = get_irn_n(n, i);
553 if (! _is_clean(pred, block))
563 * check if a node n is clean.
565 static int is_clean(ir_node *n)
567 int res = _is_clean(n, get_nodes_block(n));
573 * This function is called for node sets with is_clean
574 * nodes only, so we must just remove nodes that don't
575 * have available inputs
577 static void clean_node_set(node_set *set, ir_node *blk)
579 ir_node *n, *pred, *pred_blk;
583 for (n = node_set_first(set); n; n = node_set_next(set)) {
584 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
585 pred = get_irn_intra_n(n, i);
587 pred_blk = get_irn_intra_n(pred, -1);
588 if (block_dominates(pred_blk, blk))
590 /* pred do not dominate it, but may be in the set */
591 if (node_lookup(set, pred) != NULL)
593 /* we found a node that must be removed */
595 node_set_remove(set, n);
596 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
603 * computes Antic_in(block):
605 static void compute_antic(ir_node *block, void *ctx)
608 block_info *succ_info;
609 block_info *info = get_block_info(block);
613 /* no need for computations in start block */
614 if (block == env->start_block)
617 size = node_set_count(info->antic_in);
619 /* the end block has no successor */
620 if (block != env->end_block) {
621 int n_succ = get_Block_n_cfg_outs(block);
624 ir_node *node, *list;
627 /* find blocks position in succ's block predecessors */
628 succ = get_Block_cfg_out(block, 0);
629 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
630 if (get_Block_cfgpred_block(succ, i) == block) {
637 succ_info = get_block_info(succ);
638 /* translate into list: we cannot insert into a set we iterate
639 * and succ might be equal to block for endless loops */
641 node_set_foreach(node, succ_info->antic_in) {
642 set_irn_link(node, list);
645 for (node = list; node; node = get_irn_link(node)) {
646 ir_node *trans = phi_translate(node, succ, pos, env);
649 node_add(info->antic_in, trans);
654 block_info *succ0_info;
659 /* Select a successor to compute the disjoint of all Nodes
660 sets, it might be useful to select the block with the
661 smallest number of nodes. For simplicity we choose the
663 succ0 = get_Block_cfg_out(block, 0);
664 succ0_info = get_block_info(succ0);
665 node_set_foreach(n, succ0_info->antic_in) {
666 /* we need the disjoint */
667 for (i = 1; i < n_succ; ++i) {
668 ir_node *succ = get_Block_cfg_out(block, i);
669 block_info *succ_info = get_block_info(succ);
670 if (node_lookup(succ_info->antic_in, n) == NULL)
674 /* we found a node that is common in all Antic_in(succ(b)),
675 put it in Antic_in(b) */
676 node_add(info->antic_in, n);
682 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
683 * It is enough to do this in the first iteration, because
684 * the set info->nodes is not changed anymore.
686 if (env->first_iter) {
688 node_set_foreach(n, info->nodes) {
690 node_add(info->antic_in, n);
695 // clean_node_set(info->antic_in, block);
696 (void) clean_node_set;
698 dump_node_set(info->antic_in, "Antic_in", block);
699 if (size != node_set_count(info->antic_in)) {
700 /* the Antic_in set has changed */
703 } /* compute_antic */
706 * allocate a block info
708 static void alloc_blk_info(ir_node *block, void *ctx)
712 block_info *info = obstack_alloc(env->obst, sizeof(*info));
714 set_irn_link(block, info);
715 info->nodes = new_node_set();
716 info->antic_in = new_node_set();
717 info->avail_out = new_value_set();
720 info->new_set = NULL;
721 info->next = env->list;
724 /* fill the nodes set, we will need it later */
725 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
726 ir_node *n = get_irn_out(block, i);
728 set_irn_link(n, NULL);
730 /* we cannot optimize pinned nodes, so do not remember them */
731 if (is_nice_value(n))
732 node_add(info->nodes, n);
737 * Perform insertion of partially redundant values.
738 * For every Block node, do the following:
739 * 1. Propagate the NEW_SETS of the dominator into the current block.
740 * If the block has multiple predecessors,
741 * 2a. Iterate over the ANTIC expressions for the block to see if
742 * any of them are partially redundant.
743 * 2b. If so, insert them into the necessary predecessors to make
744 * the expression fully redundant.
745 * 2c. Insert a new Phi merging the values of the predecessors.
746 * 2d. Insert the new Phi, and the new expressions, into the
749 static void insert_nodes(ir_node *block, void *ctx)
753 ir_node *e, *idom, *first_s, *worklist;
754 block_info *curr_info, *idom_info;
755 int pos, arity = get_irn_intra_arity(block);
756 int all_same, by_some, updated;
758 /* ensure that even the start block has a new_set */
759 curr_info = get_block_info(block);
760 if (curr_info->new_set)
761 del_value_set(curr_info->new_set);
762 curr_info->new_set = new_value_set();
764 if (block == env->start_block)
767 idom = get_Block_idom(block);
768 idom_info = get_block_info(idom);
770 /* update the new_sets */
772 dump_value_set(idom_info->new_set, "[New Set]", idom);
773 value_set_foreach(entry, idom_info->new_set) {
774 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
777 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
782 /* convert the set into a list. This allows the removal of
783 * elements from the set */
785 node_set_foreach(e, curr_info->antic_in) {
786 set_irn_link(e, worklist);
790 for (e = worklist; e != NULL; e = get_irn_link(e)) {
793 /* If the value was already computed in the dominator, then
794 it is totally redundant. Hence we have nothing to insert. */
795 if (value_lookup(idom_info->avail_out, e)) {
796 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
805 /* for all predecessor blocks */
806 for (pos = 0; pos < arity; ++pos) {
807 block_info *pred_info;
808 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
809 ir_node *e_prime, *v_prime, *e_dprime;
811 /* ignore bad blocks. */
812 if (is_Bad(pred_blk))
815 e_prime = phi_translate(e, block, pos, env);
818 pred_info = get_block_info(pred_blk);
819 e_dprime = value_lookup(pred_info->avail_out, v_prime);
821 if (e_dprime == NULL) {
823 pred_info->avail = e_prime;
824 pred_info->not_found = 1;
827 mode = get_irn_mode(e_dprime);
829 pred_info->avail = e_dprime;
830 pred_info->not_found = 0;
834 else if (first_s != e_dprime)
837 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
841 /* If it's not the same value already existing along every predecessor, and
842 it's defined by some predecessor, it is partially redundant. */
843 if (! all_same && by_some) {
846 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
848 in = xmalloc(arity * sizeof(*in));
849 /* for all predecessor blocks */
850 for (pos = 0; pos < arity; ++pos) {
851 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
852 block_info *pred_info = get_block_info(pred_blk);
854 /* ignore bad blocks. */
855 if (is_Bad(pred_blk)) {
860 /* ignore blocks that already have the expression */
861 if (pred_info->not_found) {
862 ir_node *e_prime = pred_info->avail;
864 if (!is_Phi(e_prime)) {
865 mode = get_irn_mode(e_prime);
867 get_irn_dbg_info(e_prime),
868 current_ir_graph, pred_blk,
871 get_irn_arity(e_prime),
872 get_irn_in(e_prime) + 1);
873 copy_node_attr(e_prime, nn);
875 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
876 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
879 in[pos] = pred_info->avail;
881 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
883 value_add_or_replace(curr_info->avail_out, phi, e);
884 value_add(curr_info->new_set, phi, e);
885 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
887 /* the good case: we really replace an instruction */
888 node_set_remove(curr_info->antic_in, e);
892 } /* node_set_foreach */
896 * Do the elimination step: collect all changes
897 * We cannot do the changes right here, as this would change
898 * the hash values of the nodes in the avail_out set!
900 static void collect_elim_pairs(ir_node *block, void *ctx)
903 block_info *curr_info = get_block_info(block);
906 dump_node_set(curr_info->nodes, "Updating nodes", block);
907 node_set_foreach(v, curr_info->nodes) {
908 ir_node *l = value_lookup(curr_info->avail_out, v);
912 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
916 p->next = env->pairs;
923 * Do all the recorded changes and optimize
924 * newly created Phi's.
926 static void eliminate_nodes(elim_pair *pairs)
930 for (p = pairs; p != NULL; p = p->next) {
931 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
933 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
934 * which we can optimize here
936 if (is_Phi(p->new_node)) {
940 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
941 ir_node *pred = get_irn_n(p->new_node, i);
943 if (pred != p->old_node) {
954 exchange(p->old_node, p->new_node);
959 * Argh: Endless loops cause problems, because the
960 * insert algorithm did not terminate. We get tranalated nodes that
961 * references the origin. These nodes are translated again and again...
963 * The current fix is to use post-dominance. This simple ignores
964 * endless loops, ie we cannot optimize them.
966 void do_gvn_pre(ir_graph *irg)
970 optimization_state_t state;
972 unsigned antic_iter, insert_iter;
974 /* register a debug mask */
975 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
976 firm_dbg_set_mask(dbg, SET_LEVEL_2);
980 a_env.trans_set = new_node_set();
982 a_env.start_block = get_irg_start_block(irg);
983 a_env.end_block = get_irg_end_block(irg);
986 /* Move Proj's into the same block as their args,
987 else we would assign the result to wrong blocks */
988 normalize_proj_nodes(irg);
990 /* critical edges MUST be removed */
991 remove_critical_cf_edges(irg);
993 /* we need dominator for Antic_out calculation */
994 if (get_irg_dom_state(irg) != dom_consistent)
996 if (get_irg_postdom_state(irg) != dom_consistent)
997 compute_postdoms(irg);
998 /* we get all nodes of a block by following outs */
999 if (get_irg_outs_state(irg) != outs_consistent)
1000 compute_irg_outs(irg);
1003 * Switch on GCSE. We need it to correctly compute
1004 * the leader of a node by hashing.
1006 save_optimization_state(&state);
1007 set_opt_global_cse(1);
1009 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1010 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1012 /* allocate block info for all blocks */
1013 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1015 /* compute the available value sets for all blocks */
1016 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1018 /* compute the anticipated value sets for all blocks */
1019 inc_irg_visited(irg);
1021 a_env.first_iter = 1;
1023 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1025 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1026 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1027 a_env.first_iter = 0;
1028 DB((dbg, LEVEL_1, "------------------------\n"));
1029 } while (a_env.changes != 0);
1031 /* compute redundant expressions */
1034 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1036 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1037 DB((dbg, LEVEL_1, "------------------------\n"));
1038 } while (a_env.changes != 0);
1040 /* last step: eliminate nodes */
1041 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1042 eliminate_nodes(a_env.pairs);
1044 restore_optimization_state(&state);
1046 /* clean up: delete all sets */
1047 for (p = a_env.list; p != NULL; p = p->next) {
1049 del_node_set(p->antic_in);
1051 del_value_set(p->avail_out);
1053 del_node_set(p->nodes);
1055 del_value_set(p->new_set);
1057 del_node_set(a_env.trans_set);
1058 obstack_free(&obst, NULL);
1059 set_irg_pinned(irg, op_pin_state_pinned);
1062 set_irg_outs_inconsistent(irg);
1063 set_irg_loopinfo_inconsistent(irg);