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;
185 return identities_cmp(e1->value, e2->value);
188 /** Create a new value set. */
189 static value_set *new_value_set(void) {
190 return new_set(value_cmp, 8);
193 /** Deletes a value set. */
194 static void del_value_set(value_set *set) {
199 * Add a node node representing the value value to the set.
201 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
206 return set_insert(set, &key, sizeof(key), value_hash(value));
209 /** computes dst = dst \/ src for value sets */
210 static void value_union(value_set *dst, value_set *src)
213 value_set_foreach(entry, src)
214 value_add(dst, entry->node, entry->value);
217 /** computes dst = dst \/ (value_set)src for value sets */
218 static void value_union_nodes(value_set *dst, node_set *src)
221 node_set_foreach(n, src)
222 value_add(dst, n, n);
226 * Lookup a value in a value set.
228 static ir_node *value_lookup(value_set *value_set, ir_node *n)
233 e = set_find(value_set, &key, sizeof(key), value_hash(n));
234 return e ? e->node : NULL;
238 * Add or replace a value in a set by an node computing the same
239 * value in a dominator block.
241 * @return non-zero if a replacement took place
243 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
245 value_entry *e = value_add(set, node, value);
247 if (e->node != node) {
248 /* node must dominate old one here */
249 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
258 * Returns non-zero if a node is movable.
260 static int is_nice_value(ir_node *n) {
264 n = get_Proj_pred(n);
265 mode = get_irn_mode(n);
267 * FIXME: For now, we cannot handle Div/even if it's movable.
268 * That should be fixed.
270 if (!mode_is_data(mode))
272 if (is_irn_constlike(n))
274 return (get_irn_pinned(n) != op_pin_state_pinned);
281 static void dump_node_set(node_set *set, char *txt, ir_node *block)
286 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
288 node_set_foreach(n, set) {
290 DB((dbg, LEVEL_2, "\n"));
291 DB((dbg, LEVEL_2, " %+F,", n));
294 DB((dbg, LEVEL_2, "\n}\n"));
300 static void dump_value_set(value_set *set, char *txt, ir_node *block)
305 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
307 value_set_foreach(e, set) {
309 DB((dbg, LEVEL_2, "\n"));
310 if (e->node != e->value)
311 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
313 DB((dbg, LEVEL_2, " %+F,", e->node));
316 DB((dbg, LEVEL_2, "\n}\n"));
320 #define dump_node_set(set, txt, block)
321 #define dump_value_set(set, txt, block)
322 #endif /* DEBUG_libfirm */
326 * Return the block info of a block
328 static block_info *get_block_info(ir_node *block) {
329 return get_irn_link(block);
333 * Computes Avail_out(block):
335 * Avail_in(block) = Avail_out(dom(block))
336 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
339 * This function must be called in the top-down dominance order:
340 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
342 static void compute_avail_top_down(ir_node *block, void *ctx)
345 block_info *dom_info;
346 block_info *info = get_block_info(block);
349 /* we don't need the end block Avail */
350 if (block == env->end_block)
354 * First add all nodes from the dominator.
355 * This must be done to ensure that Antic_out contains the leader
356 * for every node. The root has no dominator.
358 if (block != env->start_block) {
359 dom_blk = get_Block_idom(block);
360 assert(is_Block(dom_blk));
362 dom_info = get_block_info(dom_blk);
365 value_union(info->avail_out, dom_info->avail_out);
367 value_union_nodes(info->avail_out, info->nodes);
369 dump_value_set(info->avail_out, "Avail_out", block);
373 * returns non-zero if a tree node must be copied because of
376 static int need_copy(ir_node *node, ir_node *block)
380 /* Phi always stop the recursion */
382 return get_irn_intra_n(node, -1) == block;
384 if (! is_nice_value(node))
387 /* check predecessor */
388 arity = get_irn_intra_arity(node);
389 for (i = 0; i < arity; ++i) {
390 ir_node *pred = get_irn_intra_n(node, i);
391 ir_node *local_bl = get_irn_intra_n(pred, -1);
392 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
394 pred = leader != NULL ? leader : pred;
395 if (need_copy(pred, block))
404 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
406 int i, arity, need_new;
407 ir_node *res, *nn, **in;
409 /* Phi always stop the recursion */
411 if (get_irn_intra_n(node, -1) == block)
412 return get_Phi_pred(node, pos);
416 if (! is_nice_value(node))
419 arity = get_irn_intra_arity(node);
421 NEW_ARR_A(ir_node *, in, arity);
425 ir_node *pred = get_irn_intra_n(node, i);
426 ir_node *pred_blk = get_irn_intra_n(pred, -1);
427 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
428 in[i] = translate(leader ? leader : pred, block, pos, env);
429 need_new |= (in[i] != pred);
437 get_irn_dbg_info(node),
439 get_Block_cfgpred_block(block, pos),
444 /* We need the attribute copy here, because the Hash value of a
445 node might depend on that. */
446 copy_node_attr(node, nn);
447 res = node_add(env->trans_set, nn);
449 obstack_free(env->obst, nn);
451 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
459 * Implements phi_translate.
461 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
466 if (! need_copy(node, block))
469 /* Create a copy of the node in the pos'th predecessor block.
470 Use our environmental obstack, as these nodes are always
472 old = current_ir_graph->obst;
473 current_ir_graph->obst = env->obst;
474 res = translate(node, block, pos, env);
475 current_ir_graph->obst = old;
478 } /* phi_translate */
482 * Implements phi_translate.
484 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
491 if (get_irn_intra_n(node, -1) == block)
492 return get_Phi_pred(node, pos);
496 arity = get_irn_intra_arity(node);
498 /* check if the node has at least one Phi predecessor */
499 for (i = 0; i < arity; ++i) {
500 ir_node *pred = get_irn_intra_n(node, i);
501 ir_node *pred_bl = get_irn_intra_n(pred, -1);
502 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
504 leader = leader != NULL ? leader : pred;
505 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
509 /* no Phi in the predecessors */
513 /* Create a copy of the node in the pos'th predecessor block.
514 Use our environmental obstack, as these nodes are always
516 old = current_ir_graph->obst;
517 current_ir_graph->obst = env->obst;
519 get_irn_dbg_info(node),
526 /* We need the attribute copy here, because the Hash value of a
527 node might depend on that. */
528 copy_node_attr(node, nn);
530 set_irn_n(nn, -1, get_irn_intra_n(node, -1));
531 for (i = 0; i < arity; ++i) {
532 ir_node *pred = get_irn_intra_n(node, i);
533 ir_node *pred_bl = get_irn_intra_n(pred, -1);
534 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
536 leader = leader != NULL ? leader : pred;
537 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
538 set_irn_n(nn, i, get_Phi_pred(leader, pos));
540 set_irn_n(nn, i, leader);
542 res = node_add(env->trans_set, nn);
543 current_ir_graph->obst = old;
546 obstack_free(env->obst, nn);
548 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
551 } /* phi_translate */
554 * check if a node n is clean in block block.
556 static int _is_clean(ir_node *n, ir_node *block)
560 if (get_nodes_block(n) != block)
568 if (! is_nice_value(n))
570 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
571 ir_node *pred = get_irn_n(n, i);
572 if (! _is_clean(pred, block))
582 * check if a node n is clean.
584 static int is_clean(ir_node *n)
586 int res = _is_clean(n, get_nodes_block(n));
592 * This function is called for node sets with is_clean
593 * nodes only, so we must just remove nodes that don't
594 * have available inputs
596 static void clean_node_set(node_set *set, ir_node *blk)
598 ir_node *n, *pred, *pred_blk;
602 for (n = node_set_first(set); n; n = node_set_next(set)) {
603 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
604 pred = get_irn_intra_n(n, i);
606 pred_blk = get_irn_intra_n(pred, -1);
607 if (block_dominates(pred_blk, blk))
609 /* pred do not dominate it, but may be in the set */
610 if (node_lookup(set, pred) != NULL)
612 /* we found a node that must be removed */
614 node_set_remove(set, n);
615 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
622 * computes Antic_in(block):
624 static void compute_antic(ir_node *block, void *ctx)
627 block_info *succ_info;
628 block_info *info = get_block_info(block);
632 /* no need for computations in start block */
633 if (block == env->start_block)
636 size = node_set_count(info->antic_in);
638 /* the end block has no successor */
639 if (block != env->end_block) {
640 int n_succ = get_Block_n_cfg_outs(block);
643 ir_node *node, *list;
646 /* find blocks position in succ's block predecessors */
647 succ = get_Block_cfg_out(block, 0);
648 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
649 if (get_Block_cfgpred_block(succ, i) == block) {
656 succ_info = get_block_info(succ);
657 /* translate into list: we cannot insert into a set we iterate
658 * and succ might be equal to block for endless loops */
660 node_set_foreach(node, succ_info->antic_in) {
661 set_irn_link(node, list);
664 for (node = list; node; node = get_irn_link(node)) {
665 ir_node *trans = phi_translate(node, succ, pos, env);
668 node_add(info->antic_in, trans);
673 block_info *succ0_info;
678 /* Select a successor to compute the disjoint of all Nodes
679 sets, it might be useful to select the block with the
680 smallest number of nodes. For simplicity we choose the
682 succ0 = get_Block_cfg_out(block, 0);
683 succ0_info = get_block_info(succ0);
684 node_set_foreach(n, succ0_info->antic_in) {
685 /* we need the disjoint */
686 for (i = 1; i < n_succ; ++i) {
687 ir_node *succ = get_Block_cfg_out(block, i);
688 block_info *succ_info = get_block_info(succ);
689 if (node_lookup(succ_info->antic_in, n) == NULL)
693 /* we found a node that is common in all Antic_in(succ(b)),
694 put it in Antic_in(b) */
695 node_add(info->antic_in, n);
701 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
702 * It is enough to do this in the first iteration, because
703 * the set info->nodes is not changed anymore.
705 if (env->first_iter) {
707 node_set_foreach(n, info->nodes) {
709 node_add(info->antic_in, n);
714 // clean_node_set(info->antic_in, block);
715 (void) clean_node_set;
717 dump_node_set(info->antic_in, "Antic_in", block);
718 if (size != node_set_count(info->antic_in)) {
719 /* the Antic_in set has changed */
722 } /* compute_antic */
725 * allocate a block info
727 static void alloc_blk_info(ir_node *block, void *ctx)
731 block_info *info = obstack_alloc(env->obst, sizeof(*info));
733 set_irn_link(block, info);
734 info->nodes = new_node_set();
735 info->antic_in = new_node_set();
736 info->avail_out = new_value_set();
739 info->new_set = NULL;
740 info->next = env->list;
743 /* fill the nodes set, we will need it later */
744 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
745 ir_node *n = get_irn_out(block, i);
747 set_irn_link(n, NULL);
749 /* we cannot optimize pinned nodes, so do not remember them */
750 if (is_nice_value(n))
751 node_add(info->nodes, n);
756 * Perform insertion of partially redundant values.
757 * For every Block node, do the following:
758 * 1. Propagate the NEW_SETS of the dominator into the current block.
759 * If the block has multiple predecessors,
760 * 2a. Iterate over the ANTIC expressions for the block to see if
761 * any of them are partially redundant.
762 * 2b. If so, insert them into the necessary predecessors to make
763 * the expression fully redundant.
764 * 2c. Insert a new Phi merging the values of the predecessors.
765 * 2d. Insert the new Phi, and the new expressions, into the
768 static void insert_nodes(ir_node *block, void *ctx)
772 ir_node *e, *idom, *first_s, *worklist;
773 block_info *curr_info, *idom_info;
774 int pos, arity = get_irn_intra_arity(block);
775 int all_same, by_some, updated;
777 /* ensure that even the start block has a new_set */
778 curr_info = get_block_info(block);
779 if (curr_info->new_set)
780 del_value_set(curr_info->new_set);
781 curr_info->new_set = new_value_set();
783 if (block == env->start_block)
786 idom = get_Block_idom(block);
787 idom_info = get_block_info(idom);
789 /* update the new_sets */
791 dump_value_set(idom_info->new_set, "[New Set]", idom);
792 value_set_foreach(entry, idom_info->new_set) {
793 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
796 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
801 /* convert the set into a list. This allows the removal of
802 * elements from the set */
804 node_set_foreach(e, curr_info->antic_in) {
805 set_irn_link(e, worklist);
809 for (e = worklist; e != NULL; e = get_irn_link(e)) {
812 /* If the value was already computed in the dominator, then
813 it is totally redundant. Hence we have nothing to insert. */
814 if (value_lookup(idom_info->avail_out, e)) {
815 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
824 /* for all predecessor blocks */
825 for (pos = 0; pos < arity; ++pos) {
826 block_info *pred_info;
827 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
828 ir_node *e_prime, *v_prime, *e_dprime;
830 /* ignore bad blocks. */
831 if (is_Bad(pred_blk))
834 e_prime = phi_translate(e, block, pos, env);
837 pred_info = get_block_info(pred_blk);
838 e_dprime = value_lookup(pred_info->avail_out, v_prime);
840 if (e_dprime == NULL) {
842 pred_info->avail = e_prime;
843 pred_info->not_found = 1;
846 mode = get_irn_mode(e_dprime);
848 pred_info->avail = e_dprime;
849 pred_info->not_found = 0;
853 else if (first_s != e_dprime)
856 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
860 /* If it's not the same value already existing along every predecessor, and
861 it's defined by some predecessor, it is partially redundant. */
862 if (! all_same && by_some) {
865 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
867 in = xmalloc(arity * sizeof(*in));
868 /* for all predecessor blocks */
869 for (pos = 0; pos < arity; ++pos) {
870 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
871 block_info *pred_info = get_block_info(pred_blk);
873 /* ignore bad blocks. */
874 if (is_Bad(pred_blk)) {
879 /* ignore blocks that already have the expression */
880 if (pred_info->not_found) {
881 ir_node *e_prime = pred_info->avail;
883 if (!is_Phi(e_prime)) {
884 mode = get_irn_mode(e_prime);
886 get_irn_dbg_info(e_prime),
887 current_ir_graph, pred_blk,
890 get_irn_arity(e_prime),
891 get_irn_in(e_prime) + 1);
892 copy_node_attr(e_prime, nn);
894 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
895 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
898 in[pos] = pred_info->avail;
900 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
902 value_add_or_replace(curr_info->avail_out, phi, e);
903 value_add(curr_info->new_set, phi, e);
904 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
906 /* the good case: we really replace an instruction */
907 node_set_remove(curr_info->antic_in, e);
911 } /* node_set_foreach */
915 * Do the elimination step: collect all changes
916 * We cannot do the changes right here, as this would change
917 * the hash values of the nodes in the avail_out set!
919 static void collect_elim_pairs(ir_node *block, void *ctx)
922 block_info *curr_info = get_block_info(block);
925 dump_node_set(curr_info->nodes, "Updating nodes", block);
926 node_set_foreach(v, curr_info->nodes) {
927 ir_node *l = value_lookup(curr_info->avail_out, v);
931 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
935 p->next = env->pairs;
942 * Do all the recorded changes and optimize
943 * newly created Phi's.
945 static void eliminate_nodes(elim_pair *pairs)
949 for (p = pairs; p != NULL; p = p->next) {
950 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
952 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
953 * which we can optimize here
955 if (is_Phi(p->new_node)) {
959 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
960 ir_node *pred = get_irn_n(p->new_node, i);
962 if (pred != p->old_node) {
973 exchange(p->old_node, p->new_node);
978 * Argh: Endless loops cause problems, because the
979 * insert algorithm did not terminate. We get translated nodes that
980 * references the origin. These nodes are translated again and again...
982 * The current fix is to use post-dominance. This simple ignores
983 * endless loops, ie we cannot optimize them.
985 void do_gvn_pre(ir_graph *irg)
989 optimization_state_t state;
991 unsigned antic_iter, insert_iter;
993 assert(!"COMPLETELY BROKEN YET, DO NOT USE");
995 /* register a debug mask */
996 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
997 firm_dbg_set_mask(dbg, SET_LEVEL_2);
1001 a_env.trans_set = new_node_set();
1003 a_env.start_block = get_irg_start_block(irg);
1004 a_env.end_block = get_irg_end_block(irg);
1007 /* Move Proj's into the same block as their args,
1008 else we would assign the result to wrong blocks */
1009 normalize_proj_nodes(irg);
1011 /* critical edges MUST be removed */
1012 remove_critical_cf_edges(irg);
1014 /* we need dominator for Antic_out calculation */
1015 if (get_irg_dom_state(irg) != dom_consistent)
1017 if (get_irg_postdom_state(irg) != dom_consistent)
1018 compute_postdoms(irg);
1019 /* we get all nodes of a block by following outs */
1020 if (get_irg_outs_state(irg) != outs_consistent)
1021 compute_irg_outs(irg);
1024 * Switch on GCSE. We need it to correctly compute
1025 * the leader of a node by hashing.
1027 save_optimization_state(&state);
1028 set_opt_global_cse(1);
1030 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1031 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1033 /* allocate block info for all blocks */
1034 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1036 /* compute the available value sets for all blocks */
1037 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1039 /* compute the anticipated value sets for all blocks */
1040 inc_irg_visited(irg);
1042 a_env.first_iter = 1;
1044 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1046 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1047 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1048 a_env.first_iter = 0;
1049 DB((dbg, LEVEL_1, "------------------------\n"));
1050 } while (a_env.changes != 0);
1052 /* compute redundant expressions */
1055 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1057 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1058 DB((dbg, LEVEL_1, "------------------------\n"));
1059 } while (a_env.changes != 0);
1061 /* last step: eliminate nodes */
1062 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1063 eliminate_nodes(a_env.pairs);
1065 restore_optimization_state(&state);
1067 /* clean up: delete all sets */
1068 for (p = a_env.list; p != NULL; p = p->next) {
1070 del_node_set(p->antic_in);
1072 del_value_set(p->avail_out);
1074 del_node_set(p->nodes);
1076 del_value_set(p->new_set);
1078 del_node_set(a_env.trans_set);
1079 obstack_free(&obst, NULL);
1080 set_irg_pinned(irg, op_pin_state_pinned);
1083 set_irg_outs_inconsistent(irg);
1084 set_irg_loopinfo_inconsistent(irg);