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);
134 /** computes dst = dst \/ src for node sets */
135 static void node_union(node_set *dst, node_set *src)
138 node_set_foreach(entry, src) {
139 node_add(dst, entry);
145 * Lookup a node in a node set.
147 static ir_node *node_lookup(node_set *set, ir_node *n)
149 return pset_find(set, n, ir_node_hash(n));
153 /* ---------- Functions for Value sets ---------- */
155 #define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
158 * calculate a hash value for a value represented by a node
160 static unsigned value_hash(ir_node *value) {
161 return ir_node_hash(value);
165 * Compare two value entries.
167 static int value_cmp(const void *elt, const void *key, size_t size)
169 const value_entry *e1 = elt;
170 const value_entry *e2 = key;
172 return identities_cmp(e1->value, e2->value);
175 /** Create a new value set. */
176 static value_set *new_value_set(void) {
177 return new_set(value_cmp, 8);
180 /** Deletes a value set. */
181 static void del_value_set(value_set *set) {
186 * Add a node node representing the value value to the set.
188 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
193 return set_insert(set, &key, sizeof(key), value_hash(value));
196 /** computes dst = dst \/ src for value sets */
197 static void value_union(value_set *dst, value_set *src)
200 value_set_foreach(entry, src)
201 value_add(dst, entry->node, entry->value);
204 /** computes dst = dst \/ (value_set)src for value sets */
205 static void value_union_nodes(value_set *dst, node_set *src)
208 node_set_foreach(n, src)
209 value_add(dst, n, n);
213 * Lookup a value in a value set.
215 static ir_node *value_lookup(value_set *value_set, ir_node *n)
220 e = set_find(value_set, &key, sizeof(key), value_hash(n));
221 return e ? e->node : NULL;
225 * Add or replace a value in a set by an node computing the same
226 * value in a dominator block.
228 * @return non-zero if a replacement took place
230 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
232 value_entry *e = value_add(set, node, value);
234 if (e->node != node) {
235 /* node must dominate old one here */
236 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
245 * Returns non-zero if a node is movable.
247 static int is_nice_value(ir_node *n) {
251 n = get_Proj_pred(n);
252 mode = get_irn_mode(n);
254 * FIXME: For now, we cannot handle Div/even if it's movable.
255 * That should be fixed.
257 if (!mode_is_data(mode))
259 if (is_irn_constlike(n))
261 return (get_irn_pinned(n) != op_pin_state_pinned);
268 static void dump_node_set(node_set *set, char *txt, ir_node *block)
273 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
275 node_set_foreach(n, set) {
277 DB((dbg, LEVEL_2, "\n"));
278 DB((dbg, LEVEL_2, " %+F,", n));
281 DB((dbg, LEVEL_2, "\n}\n"));
287 static void dump_value_set(value_set *set, char *txt, ir_node *block)
292 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
294 value_set_foreach(e, set) {
296 DB((dbg, LEVEL_2, "\n"));
297 if (e->node != e->value)
298 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
300 DB((dbg, LEVEL_2, " %+F,", e->node));
303 DB((dbg, LEVEL_2, "\n}\n"));
307 #define dump_node_set(set, txt, block)
308 #define dump_value_set(set, txt, block)
309 #endif /* DEBUG_libfirm */
313 * Return the block info of a block
315 static block_info *get_block_info(ir_node *block) {
316 return get_irn_link(block);
320 * Computes Avail_out(block):
322 * Avail_in(block) = Avail_out(dom(block))
323 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
326 * This function must be called in the top-down dominance order:
327 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
329 static void compute_avail_top_down(ir_node *block, void *ctx)
332 block_info *dom_info;
333 block_info *info = get_block_info(block);
336 /* we don't need the end block Avail */
337 if (block == env->end_block)
341 * First add all nodes from the dominator.
342 * This must be done to ensure that Antic_out contains the leader
343 * for every node. The root has no dominator.
345 if (block != env->start_block) {
346 dom_blk = get_Block_idom(block);
347 assert(is_Block(dom_blk));
349 dom_info = get_block_info(dom_blk);
352 value_union(info->avail_out, dom_info->avail_out);
354 value_union_nodes(info->avail_out, info->nodes);
356 dump_value_set(info->avail_out, "Avail_out", block);
360 * returns non-zero if a tree node must be copied because of
363 static int need_copy(ir_node *node, ir_node *block)
367 /* Phi always stop the recursion */
369 return get_irn_intra_n(node, -1) == block;
371 if (! is_nice_value(node))
374 /* check predecessor */
375 arity = get_irn_intra_arity(node);
376 for (i = 0; i < arity; ++i) {
377 ir_node *pred = get_irn_intra_n(node, i);
378 ir_node *local_bl = get_irn_intra_n(pred, -1);
379 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
381 pred = leader != NULL ? leader : pred;
382 if (need_copy(pred, block))
391 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
393 int i, arity, need_new;
394 ir_node *res, *nn, **in;
396 /* Phi always stop the recursion */
398 if (get_irn_intra_n(node, -1) == block)
399 return get_Phi_pred(node, pos);
403 if (! is_nice_value(node))
406 arity = get_irn_intra_arity(node);
408 NEW_ARR_A(ir_node *, in, arity);
412 ir_node *pred = get_irn_intra_n(node, i);
413 ir_node *pred_blk = get_irn_intra_n(pred, -1);
414 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
415 in[i] = translate(leader ? leader : pred, block, pos, env);
416 need_new |= (in[i] != pred);
424 get_irn_dbg_info(node),
426 get_Block_cfgpred_block(block, pos),
431 /* We need the attribute copy here, because the Hash value of a
432 node might depend on that. */
433 copy_node_attr(node, nn);
434 res = node_add(env->trans_set, nn);
436 obstack_free(env->obst, nn);
438 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
446 * Implements phi_translate.
448 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
453 if (! need_copy(node, block))
456 /* Create a copy of the node in the pos'th predecessor block.
457 Use our environmental obstack, as these nodes are always
459 old = current_ir_graph->obst;
460 current_ir_graph->obst = env->obst;
461 res = translate(node, block, pos, env);
462 current_ir_graph->obst = old;
465 } /* phi_translate */
469 * Implements phi_translate.
471 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
478 if (get_irn_intra_n(node, -1) == block)
479 return get_Phi_pred(node, pos);
483 arity = get_irn_intra_arity(node);
485 /* check if the node has at least one Phi predecessor */
486 for (i = 0; i < arity; ++i) {
487 ir_node *pred = get_irn_intra_n(node, i);
488 ir_node *pred_bl = get_irn_intra_n(pred, -1);
489 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
491 leader = leader != NULL ? leader : pred;
492 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
496 /* no Phi in the predecessors */
500 /* Create a copy of the node in the pos'th predecessor block.
501 Use our environmental obstack, as these nodes are always
503 old = current_ir_graph->obst;
504 current_ir_graph->obst = env->obst;
506 get_irn_dbg_info(node),
513 /* We need the attribute copy here, because the Hash value of a
514 node might depend on that. */
515 copy_node_attr(node, nn);
517 set_irn_n(nn, -1, get_irn_intra_n(node, -1));
518 for (i = 0; i < arity; ++i) {
519 ir_node *pred = get_irn_intra_n(node, i);
520 ir_node *pred_bl = get_irn_intra_n(pred, -1);
521 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
523 leader = leader != NULL ? leader : pred;
524 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
525 set_irn_n(nn, i, get_Phi_pred(leader, pos));
527 set_irn_n(nn, i, leader);
529 res = node_add(env->trans_set, nn);
530 current_ir_graph->obst = old;
533 obstack_free(env->obst, nn);
535 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
538 } /* phi_translate */
541 * check if a node n is clean in block block.
543 static int _is_clean(ir_node *n, ir_node *block)
547 if (get_nodes_block(n) != block)
555 if (! is_nice_value(n))
557 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
558 ir_node *pred = get_irn_n(n, i);
559 if (! _is_clean(pred, block))
569 * check if a node n is clean.
571 static int is_clean(ir_node *n)
573 int res = _is_clean(n, get_nodes_block(n));
579 * This function is called for node sets with is_clean
580 * nodes only, so we must just remove nodes that don't
581 * have available inputs
583 static void clean_node_set(node_set *set, ir_node *blk)
585 ir_node *n, *pred, *pred_blk;
589 for (n = node_set_first(set); n; n = node_set_next(set)) {
590 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
591 pred = get_irn_intra_n(n, i);
593 pred_blk = get_irn_intra_n(pred, -1);
594 if (block_dominates(pred_blk, blk))
596 /* pred do not dominate it, but may be in the set */
597 if (node_lookup(set, pred) != NULL)
599 /* we found a node that must be removed */
601 node_set_remove(set, n);
602 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
609 * computes Antic_in(block):
611 static void compute_antic(ir_node *block, void *ctx)
614 block_info *succ_info;
615 block_info *info = get_block_info(block);
619 /* no need for computations in start block */
620 if (block == env->start_block)
623 size = node_set_count(info->antic_in);
625 /* the end block has no successor */
626 if (block != env->end_block) {
627 int n_succ = get_Block_n_cfg_outs(block);
630 ir_node *node, *list;
633 /* find blocks position in succ's block predecessors */
634 succ = get_Block_cfg_out(block, 0);
635 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
636 if (get_Block_cfgpred_block(succ, i) == block) {
643 succ_info = get_block_info(succ);
644 /* translate into list: we cannot insert into a set we iterate
645 * and succ might be equal to block for endless loops */
647 node_set_foreach(node, succ_info->antic_in) {
648 set_irn_link(node, list);
651 for (node = list; node; node = get_irn_link(node)) {
652 ir_node *trans = phi_translate(node, succ, pos, env);
655 node_add(info->antic_in, trans);
660 block_info *succ0_info;
665 /* Select a successor to compute the disjoint of all Nodes
666 sets, it might be useful to select the block with the
667 smallest number of nodes. For simplicity we choose the
669 succ0 = get_Block_cfg_out(block, 0);
670 succ0_info = get_block_info(succ0);
671 node_set_foreach(n, succ0_info->antic_in) {
672 /* we need the disjoint */
673 for (i = 1; i < n_succ; ++i) {
674 ir_node *succ = get_Block_cfg_out(block, i);
675 block_info *succ_info = get_block_info(succ);
676 if (node_lookup(succ_info->antic_in, n) == NULL)
680 /* we found a node that is common in all Antic_in(succ(b)),
681 put it in Antic_in(b) */
682 node_add(info->antic_in, n);
688 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
689 * It is enough to do this in the first iteration, because
690 * the set info->nodes is not changed anymore.
692 if (env->first_iter) {
694 node_set_foreach(n, info->nodes) {
696 node_add(info->antic_in, n);
701 // clean_node_set(info->antic_in, block);
702 (void) clean_node_set;
704 dump_node_set(info->antic_in, "Antic_in", block);
705 if (size != node_set_count(info->antic_in)) {
706 /* the Antic_in set has changed */
709 } /* compute_antic */
712 * allocate a block info
714 static void alloc_blk_info(ir_node *block, void *ctx)
718 block_info *info = obstack_alloc(env->obst, sizeof(*info));
720 set_irn_link(block, info);
721 info->nodes = new_node_set();
722 info->antic_in = new_node_set();
723 info->avail_out = new_value_set();
726 info->new_set = NULL;
727 info->next = env->list;
730 /* fill the nodes set, we will need it later */
731 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
732 ir_node *n = get_irn_out(block, i);
734 set_irn_link(n, NULL);
736 /* we cannot optimize pinned nodes, so do not remember them */
737 if (is_nice_value(n))
738 node_add(info->nodes, n);
743 * Perform insertion of partially redundant values.
744 * For every Block node, do the following:
745 * 1. Propagate the NEW_SETS of the dominator into the current block.
746 * If the block has multiple predecessors,
747 * 2a. Iterate over the ANTIC expressions for the block to see if
748 * any of them are partially redundant.
749 * 2b. If so, insert them into the necessary predecessors to make
750 * the expression fully redundant.
751 * 2c. Insert a new Phi merging the values of the predecessors.
752 * 2d. Insert the new Phi, and the new expressions, into the
755 static void insert_nodes(ir_node *block, void *ctx)
759 ir_node *e, *idom, *first_s, *worklist;
760 block_info *curr_info, *idom_info;
761 int pos, arity = get_irn_intra_arity(block);
762 int all_same, by_some, updated;
764 /* ensure that even the start block has a new_set */
765 curr_info = get_block_info(block);
766 if (curr_info->new_set)
767 del_value_set(curr_info->new_set);
768 curr_info->new_set = new_value_set();
770 if (block == env->start_block)
773 idom = get_Block_idom(block);
774 idom_info = get_block_info(idom);
776 /* update the new_sets */
778 dump_value_set(idom_info->new_set, "[New Set]", idom);
779 value_set_foreach(entry, idom_info->new_set) {
780 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
783 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
788 /* convert the set into a list. This allows the removal of
789 * elements from the set */
791 node_set_foreach(e, curr_info->antic_in) {
792 set_irn_link(e, worklist);
796 for (e = worklist; e != NULL; e = get_irn_link(e)) {
799 /* If the value was already computed in the dominator, then
800 it is totally redundant. Hence we have nothing to insert. */
801 if (value_lookup(idom_info->avail_out, e)) {
802 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
811 /* for all predecessor blocks */
812 for (pos = 0; pos < arity; ++pos) {
813 block_info *pred_info;
814 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
815 ir_node *e_prime, *v_prime, *e_dprime;
817 /* ignore bad blocks. */
818 if (is_Bad(pred_blk))
821 e_prime = phi_translate(e, block, pos, env);
824 pred_info = get_block_info(pred_blk);
825 e_dprime = value_lookup(pred_info->avail_out, v_prime);
827 if (e_dprime == NULL) {
829 pred_info->avail = e_prime;
830 pred_info->not_found = 1;
833 mode = get_irn_mode(e_dprime);
835 pred_info->avail = e_dprime;
836 pred_info->not_found = 0;
840 else if (first_s != e_dprime)
843 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
847 /* If it's not the same value already existing along every predecessor, and
848 it's defined by some predecessor, it is partially redundant. */
849 if (! all_same && by_some) {
852 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
854 in = xmalloc(arity * sizeof(*in));
855 /* for all predecessor blocks */
856 for (pos = 0; pos < arity; ++pos) {
857 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
858 block_info *pred_info = get_block_info(pred_blk);
860 /* ignore bad blocks. */
861 if (is_Bad(pred_blk)) {
866 /* ignore blocks that already have the expression */
867 if (pred_info->not_found) {
868 ir_node *e_prime = pred_info->avail;
870 if (!is_Phi(e_prime)) {
871 mode = get_irn_mode(e_prime);
873 get_irn_dbg_info(e_prime),
874 current_ir_graph, pred_blk,
877 get_irn_arity(e_prime),
878 get_irn_in(e_prime) + 1);
879 copy_node_attr(e_prime, nn);
881 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
882 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
885 in[pos] = pred_info->avail;
887 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
889 value_add_or_replace(curr_info->avail_out, phi, e);
890 value_add(curr_info->new_set, phi, e);
891 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
893 /* the good case: we really replace an instruction */
894 node_set_remove(curr_info->antic_in, e);
898 } /* node_set_foreach */
902 * Do the elimination step: collect all changes
903 * We cannot do the changes right here, as this would change
904 * the hash values of the nodes in the avail_out set!
906 static void collect_elim_pairs(ir_node *block, void *ctx)
909 block_info *curr_info = get_block_info(block);
912 dump_node_set(curr_info->nodes, "Updating nodes", block);
913 node_set_foreach(v, curr_info->nodes) {
914 ir_node *l = value_lookup(curr_info->avail_out, v);
918 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
922 p->next = env->pairs;
929 * Do all the recorded changes and optimize
930 * newly created Phi's.
932 static void eliminate_nodes(elim_pair *pairs)
936 for (p = pairs; p != NULL; p = p->next) {
937 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
939 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
940 * which we can optimize here
942 if (is_Phi(p->new_node)) {
946 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
947 ir_node *pred = get_irn_n(p->new_node, i);
949 if (pred != p->old_node) {
960 exchange(p->old_node, p->new_node);
965 * Argh: Endless loops cause problems, because the
966 * insert algorithm did not terminate. We get tranalated nodes that
967 * references the origin. These nodes are translated again and again...
969 * The current fix is to use post-dominance. This simple ignores
970 * endless loops, ie we cannot optimize them.
972 void do_gvn_pre(ir_graph *irg)
976 optimization_state_t state;
978 unsigned antic_iter, insert_iter;
980 /* register a debug mask */
981 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
982 firm_dbg_set_mask(dbg, SET_LEVEL_2);
986 a_env.trans_set = new_node_set();
988 a_env.start_block = get_irg_start_block(irg);
989 a_env.end_block = get_irg_end_block(irg);
992 /* Move Proj's into the same block as their args,
993 else we would assign the result to wrong blocks */
994 normalize_proj_nodes(irg);
996 /* critical edges MUST be removed */
997 remove_critical_cf_edges(irg);
999 /* we need dominator for Antic_out calculation */
1000 if (get_irg_dom_state(irg) != dom_consistent)
1002 if (get_irg_postdom_state(irg) != dom_consistent)
1003 compute_postdoms(irg);
1004 /* we get all nodes of a block by following outs */
1005 if (get_irg_outs_state(irg) != outs_consistent)
1006 compute_irg_outs(irg);
1009 * Switch on GCSE. We need it to correctly compute
1010 * the leader of a node by hashing.
1012 save_optimization_state(&state);
1013 set_opt_global_cse(1);
1015 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1016 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1018 /* allocate block info for all blocks */
1019 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1021 /* compute the available value sets for all blocks */
1022 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1024 /* compute the anticipated value sets for all blocks */
1025 inc_irg_visited(irg);
1027 a_env.first_iter = 1;
1029 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1031 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1032 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1033 a_env.first_iter = 0;
1034 DB((dbg, LEVEL_1, "------------------------\n"));
1035 } while (a_env.changes != 0);
1037 /* compute redundant expressions */
1040 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1042 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1043 DB((dbg, LEVEL_1, "------------------------\n"));
1044 } while (a_env.changes != 0);
1046 /* last step: eliminate nodes */
1047 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1048 eliminate_nodes(a_env.pairs);
1050 restore_optimization_state(&state);
1052 /* clean up: delete all sets */
1053 for (p = a_env.list; p != NULL; p = p->next) {
1055 del_node_set(p->antic_in);
1057 del_value_set(p->avail_out);
1059 del_node_set(p->nodes);
1061 del_value_set(p->new_set);
1063 del_node_set(a_env.trans_set);
1064 obstack_free(&obst, NULL);
1065 set_irg_pinned(irg, op_pin_state_pinned);
1068 set_irg_outs_inconsistent(irg);
1069 set_irg_loopinfo_inconsistent(irg);