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 stes so NOT preserve
29 * the topological sort!
37 #include "irgraph_t.h"
53 /** The debug module handle. */
54 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
58 typedef struct set value_set;
61 typedef struct pset node_set;
63 /** An entry in the value set. */
64 typedef struct value_entry {
65 ir_node *node; /**< the node */
66 ir_node *value; /**< the value of the node */
69 /** Additional info we need for every block. */
70 typedef struct block_info {
71 node_set *nodes; /**< The set of nodes per block. */
72 value_set *avail_out; /**< The Avail_out set for a block. */
73 node_set *antic_in; /**< The Antic_in set for a block. */
74 value_set *new_set; /**< The set of all new values for a block. */
75 ir_node *avail; /**< The get_map(avail, block) result. */
76 int not_found; /**< Non-zero, if avail was not found in this block. */
77 struct block_info *next; /**< Links all entries, so we can recover the sets easily. */
81 * A pair of nodes that must be exchanged.
82 * We must defer the exchange because our hash-sets cannot
83 * find an already replace node else.
85 typedef struct elim_pair {
86 ir_node *old_node; /**< The old node that will be replaced. */
87 ir_node *new_node; /**< The new node. */
88 struct elim_pair *next; /**< Links all entries in a list. */
91 /** The environment for the GVN-PRE algorithm */
92 typedef struct pre_env {
93 struct obstack *obst; /**< The obstack to allocate on. */
94 node_set *trans_set; /**< The set of all translated values. */
95 ir_node *start_block; /**< The start block of the current graph. */
96 ir_node *end_block; /**< The end block of the current graph */
97 block_info *list; /**< Links all block info entires for easier recovery. */
98 elim_pair *pairs; /**< A list of node pairs that must be eliminated. */
99 char changes; /**< Non-zero, if calculation of Antic_in has changed. */
100 char first_iter; /**< non-zero for first iteration */
103 /* ---------- Functions for Node sets ---------- */
105 #define node_set_first(s) pset_first(s)
106 #define node_set_next(s) pset_next(s)
107 #define node_set_break(s) pset_break(s)
108 #define node_set_foreach(v, s) for ((v) = node_set_first(s); (v); (v) = node_set_next(s))
111 * Creates a new node set.
113 static node_set *new_node_set(void) {
114 return new_pset(identities_cmp, 8);
118 * Deletes a node set.
120 static void del_node_set(node_set *set) {
125 * Add a node to the set.
127 static ir_node *node_add(node_set *set, ir_node *node) {
128 return identify_remember(set, node);
132 * Remove a node from a node set.
134 static void node_set_remove(node_set *set, ir_node *node) {
135 pset_remove(set, node, ir_node_hash(node));
139 * Return the number of entries in a node set.
141 static int node_set_count(node_set *set) {
142 return pset_count(set);
146 /** computes dst = dst \/ src for node sets */
147 static void node_union(node_set *dst, node_set *src)
150 node_set_foreach(entry, src) {
151 node_add(dst, entry);
157 * Lookup a node in a node set.
159 static ir_node *node_lookup(node_set *set, ir_node *n)
161 return pset_find(set, n, ir_node_hash(n));
165 /* ---------- Functions for Value sets ---------- */
167 #define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
170 * calculate a hash value for a value represented by a node
172 static unsigned value_hash(ir_node *value) {
173 return ir_node_hash(value);
177 * Compare two value entries.
179 static int value_cmp(const void *elt, const void *key, size_t size)
181 const value_entry *e1 = elt;
182 const value_entry *e2 = key;
184 return identities_cmp(e1->value, e2->value);
187 /** Create a new value set. */
188 static value_set *new_value_set(void) {
189 return new_set(value_cmp, 8);
192 /** Deletes a value set. */
193 static void del_value_set(value_set *set) {
198 * Add a node node representing the value value to the set.
200 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
205 return set_insert(set, &key, sizeof(key), value_hash(value));
208 /** computes dst = dst \/ src for value sets */
209 static void value_union(value_set *dst, value_set *src)
212 value_set_foreach(entry, src)
213 value_add(dst, entry->node, entry->value);
216 /** computes dst = dst \/ (value_set)src for value sets */
217 static void value_union_nodes(value_set *dst, node_set *src)
220 node_set_foreach(n, src)
221 value_add(dst, n, n);
225 * Lookup a value in a value set.
227 static ir_node *value_lookup(value_set *value_set, ir_node *n)
232 e = set_find(value_set, &key, sizeof(key), value_hash(n));
233 return e ? e->node : NULL;
237 * Add or replace a value in a set by an node computing the same
238 * value in a dominator block.
240 * @return non-zero if a replacement took place
242 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
244 value_entry *e = value_add(set, node, value);
246 if (e->node != node) {
247 /* node must dominate old one here */
248 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
257 * Returns non-zero if a node is movable.
259 static int is_nice_value(ir_node *n) {
263 n = get_Proj_pred(n);
264 mode = get_irn_mode(n);
266 * FIXME: For now, we cannot handle Div/even if it's movable.
267 * That should be fixed.
269 if (!mode_is_data(mode))
271 if (is_irn_constlike(n))
273 return (get_irn_pinned(n) != op_pin_state_pinned);
280 static void dump_node_set(node_set *set, char *txt, ir_node *block)
285 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
287 node_set_foreach(n, set) {
289 DB((dbg, LEVEL_2, "\n"));
290 DB((dbg, LEVEL_2, " %+F,", n));
293 DB((dbg, LEVEL_2, "\n}\n"));
299 static void dump_value_set(value_set *set, char *txt, ir_node *block)
304 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
306 value_set_foreach(e, set) {
308 DB((dbg, LEVEL_2, "\n"));
309 if (e->node != e->value)
310 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
312 DB((dbg, LEVEL_2, " %+F,", e->node));
315 DB((dbg, LEVEL_2, "\n}\n"));
319 #define dump_node_set(set, txt, block)
320 #define dump_value_set(set, txt, block)
321 #endif /* DEBUG_libfirm */
325 * Return the block info of a block
327 static block_info *get_block_info(ir_node *block) {
328 return get_irn_link(block);
332 * Computes Avail_out(block):
334 * Avail_in(block) = Avail_out(dom(block))
335 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
338 * This function must be called in the top-down dominance order:
339 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
341 static void compute_avail_top_down(ir_node *block, void *ctx)
344 block_info *dom_info;
345 block_info *info = get_block_info(block);
348 /* we don't need the end block Avail */
349 if (block == env->end_block)
353 * First add all nodes from the dominator.
354 * This must be done to ensure that Antic_out contains the leader
355 * for every node. The root has no dominator.
357 if (block != env->start_block) {
358 dom_blk = get_Block_idom(block);
359 assert(is_Block(dom_blk));
361 dom_info = get_block_info(dom_blk);
364 value_union(info->avail_out, dom_info->avail_out);
366 value_union_nodes(info->avail_out, info->nodes);
368 dump_value_set(info->avail_out, "Avail_out", block);
372 * returns non-zero if a tree node must be copied because of
375 static int need_copy(ir_node *node, ir_node *block)
379 /* Phi always stop the recursion */
381 return get_irn_intra_n(node, -1) == block;
383 if (! is_nice_value(node))
386 /* check predecessor */
387 arity = get_irn_intra_arity(node);
388 for (i = 0; i < arity; ++i) {
389 ir_node *pred = get_irn_intra_n(node, i);
390 ir_node *local_bl = get_irn_intra_n(pred, -1);
391 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
393 pred = leader != NULL ? leader : pred;
394 if (need_copy(pred, block))
403 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
405 int i, arity, need_new;
406 ir_node *res, *nn, **in;
408 /* Phi always stop the recursion */
410 if (get_irn_intra_n(node, -1) == block)
411 return get_Phi_pred(node, pos);
415 if (! is_nice_value(node))
418 arity = get_irn_intra_arity(node);
420 NEW_ARR_A(ir_node *, in, arity);
424 ir_node *pred = get_irn_intra_n(node, i);
425 ir_node *pred_blk = get_irn_intra_n(pred, -1);
426 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
427 in[i] = translate(leader ? leader : pred, block, pos, env);
428 need_new |= (in[i] != pred);
436 get_irn_dbg_info(node),
438 get_Block_cfgpred_block(block, pos),
443 /* We need the attribute copy here, because the Hash value of a
444 node might depend on that. */
445 copy_node_attr(node, nn);
446 res = node_add(env->trans_set, nn);
448 obstack_free(env->obst, nn);
450 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
458 * Implements phi_translate.
460 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
465 if (! need_copy(node, block))
468 /* Create a copy of the node in the pos'th predecessor block.
469 Use our environmental obstack, as these nodes are always
471 old = current_ir_graph->obst;
472 current_ir_graph->obst = env->obst;
473 res = translate(node, block, pos, env);
474 current_ir_graph->obst = old;
477 } /* phi_translate */
481 * Implements phi_translate.
483 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
490 if (get_irn_intra_n(node, -1) == block)
491 return get_Phi_pred(node, pos);
495 arity = get_irn_intra_arity(node);
497 /* check if the node has at least one Phi predecessor */
498 for (i = 0; i < arity; ++i) {
499 ir_node *pred = get_irn_intra_n(node, i);
500 ir_node *pred_bl = get_irn_intra_n(pred, -1);
501 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
503 leader = leader != NULL ? leader : pred;
504 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
508 /* no Phi in the predecessors */
512 /* Create a copy of the node in the pos'th predecessor block.
513 Use our environmental obstack, as these nodes are always
515 old = current_ir_graph->obst;
516 current_ir_graph->obst = env->obst;
518 get_irn_dbg_info(node),
525 /* We need the attribute copy here, because the Hash value of a
526 node might depend on that. */
527 copy_node_attr(node, nn);
529 set_irn_n(nn, -1, get_irn_intra_n(node, -1));
530 for (i = 0; i < arity; ++i) {
531 ir_node *pred = get_irn_intra_n(node, i);
532 ir_node *pred_bl = get_irn_intra_n(pred, -1);
533 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
535 leader = leader != NULL ? leader : pred;
536 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
537 set_irn_n(nn, i, get_Phi_pred(leader, pos));
539 set_irn_n(nn, i, leader);
541 res = node_add(env->trans_set, nn);
542 current_ir_graph->obst = old;
545 obstack_free(env->obst, nn);
547 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
550 } /* phi_translate */
553 * check if a node n is clean in block block.
555 static int _is_clean(ir_node *n, ir_node *block)
559 if (get_nodes_block(n) != block)
567 if (! is_nice_value(n))
569 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
570 ir_node *pred = get_irn_n(n, i);
571 if (! _is_clean(pred, block))
581 * check if a node n is clean.
583 static int is_clean(ir_node *n)
585 int res = _is_clean(n, get_nodes_block(n));
591 * This function is called for node sets with is_clean
592 * nodes only, so we must just remove nodes that don't
593 * have available inputs
595 static void clean_node_set(node_set *set, ir_node *blk)
597 ir_node *n, *pred, *pred_blk;
601 for (n = node_set_first(set); n; n = node_set_next(set)) {
602 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
603 pred = get_irn_intra_n(n, i);
605 pred_blk = get_irn_intra_n(pred, -1);
606 if (block_dominates(pred_blk, blk))
608 /* pred do not dominate it, but may be in the set */
609 if (node_lookup(set, pred) != NULL)
611 /* we found a node that must be removed */
613 node_set_remove(set, n);
614 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
621 * computes Antic_in(block):
623 static void compute_antic(ir_node *block, void *ctx)
626 block_info *succ_info;
627 block_info *info = get_block_info(block);
631 /* no need for computations in start block */
632 if (block == env->start_block)
635 size = node_set_count(info->antic_in);
637 /* the end block has no successor */
638 if (block != env->end_block) {
639 int n_succ = get_Block_n_cfg_outs(block);
642 ir_node *node, *list;
645 /* find blocks position in succ's block predecessors */
646 succ = get_Block_cfg_out(block, 0);
647 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
648 if (get_Block_cfgpred_block(succ, i) == block) {
655 succ_info = get_block_info(succ);
656 /* translate into list: we cannot insert into a set we iterate
657 * and succ might be equal to block for endless loops */
659 node_set_foreach(node, succ_info->antic_in) {
660 set_irn_link(node, list);
663 for (node = list; node; node = get_irn_link(node)) {
664 ir_node *trans = phi_translate(node, succ, pos, env);
667 node_add(info->antic_in, trans);
672 block_info *succ0_info;
677 /* Select a successor to compute the disjoint of all Nodes
678 sets, it might be useful to select the block with the
679 smallest number of nodes. For simplicity we choose the
681 succ0 = get_Block_cfg_out(block, 0);
682 succ0_info = get_block_info(succ0);
683 node_set_foreach(n, succ0_info->antic_in) {
684 /* we need the disjoint */
685 for (i = 1; i < n_succ; ++i) {
686 ir_node *succ = get_Block_cfg_out(block, i);
687 block_info *succ_info = get_block_info(succ);
688 if (node_lookup(succ_info->antic_in, n) == NULL)
692 /* we found a node that is common in all Antic_in(succ(b)),
693 put it in Antic_in(b) */
694 node_add(info->antic_in, n);
700 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
701 * It is enough to do this in the first iteration, because
702 * the set info->nodes is not changed anymore.
704 if (env->first_iter) {
706 node_set_foreach(n, info->nodes) {
708 node_add(info->antic_in, n);
713 // clean_node_set(info->antic_in, block);
714 (void) clean_node_set;
716 dump_node_set(info->antic_in, "Antic_in", block);
717 if (size != node_set_count(info->antic_in)) {
718 /* the Antic_in set has changed */
721 } /* compute_antic */
724 * allocate a block info
726 static void alloc_blk_info(ir_node *block, void *ctx)
730 block_info *info = obstack_alloc(env->obst, sizeof(*info));
732 set_irn_link(block, info);
733 info->nodes = new_node_set();
734 info->antic_in = new_node_set();
735 info->avail_out = new_value_set();
738 info->new_set = NULL;
739 info->next = env->list;
742 /* fill the nodes set, we will need it later */
743 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
744 ir_node *n = get_irn_out(block, i);
746 set_irn_link(n, NULL);
748 /* we cannot optimize pinned nodes, so do not remember them */
749 if (is_nice_value(n))
750 node_add(info->nodes, n);
755 * Perform insertion of partially redundant values.
756 * For every Block node, do the following:
757 * 1. Propagate the NEW_SETS of the dominator into the current block.
758 * If the block has multiple predecessors,
759 * 2a. Iterate over the ANTIC expressions for the block to see if
760 * any of them are partially redundant.
761 * 2b. If so, insert them into the necessary predecessors to make
762 * the expression fully redundant.
763 * 2c. Insert a new Phi merging the values of the predecessors.
764 * 2d. Insert the new Phi, and the new expressions, into the
767 static void insert_nodes(ir_node *block, void *ctx)
771 ir_node *e, *idom, *first_s, *worklist;
772 block_info *curr_info, *idom_info;
773 int pos, arity = get_irn_intra_arity(block);
774 int all_same, by_some, updated;
776 /* ensure that even the start block has a new_set */
777 curr_info = get_block_info(block);
778 if (curr_info->new_set)
779 del_value_set(curr_info->new_set);
780 curr_info->new_set = new_value_set();
782 if (block == env->start_block)
785 idom = get_Block_idom(block);
786 idom_info = get_block_info(idom);
788 /* update the new_sets */
790 dump_value_set(idom_info->new_set, "[New Set]", idom);
791 value_set_foreach(entry, idom_info->new_set) {
792 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
795 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
800 /* convert the set into a list. This allows the removal of
801 * elements from the set */
803 node_set_foreach(e, curr_info->antic_in) {
804 set_irn_link(e, worklist);
808 for (e = worklist; e != NULL; e = get_irn_link(e)) {
811 /* If the value was already computed in the dominator, then
812 it is totally redundant. Hence we have nothing to insert. */
813 if (value_lookup(idom_info->avail_out, e)) {
814 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
823 /* for all predecessor blocks */
824 for (pos = 0; pos < arity; ++pos) {
825 block_info *pred_info;
826 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
827 ir_node *e_prime, *v_prime, *e_dprime;
829 /* ignore bad blocks. */
830 if (is_Bad(pred_blk))
833 e_prime = phi_translate(e, block, pos, env);
836 pred_info = get_block_info(pred_blk);
837 e_dprime = value_lookup(pred_info->avail_out, v_prime);
839 if (e_dprime == NULL) {
841 pred_info->avail = e_prime;
842 pred_info->not_found = 1;
845 mode = get_irn_mode(e_dprime);
847 pred_info->avail = e_dprime;
848 pred_info->not_found = 0;
852 else if (first_s != e_dprime)
855 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
859 /* If it's not the same value already existing along every predecessor, and
860 it's defined by some predecessor, it is partially redundant. */
861 if (! all_same && by_some) {
864 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
866 in = xmalloc(arity * sizeof(*in));
867 /* for all predecessor blocks */
868 for (pos = 0; pos < arity; ++pos) {
869 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
870 block_info *pred_info = get_block_info(pred_blk);
872 /* ignore bad blocks. */
873 if (is_Bad(pred_blk)) {
878 /* ignore blocks that already have the expression */
879 if (pred_info->not_found) {
880 ir_node *e_prime = pred_info->avail;
882 if (!is_Phi(e_prime)) {
883 mode = get_irn_mode(e_prime);
885 get_irn_dbg_info(e_prime),
886 current_ir_graph, pred_blk,
889 get_irn_arity(e_prime),
890 get_irn_in(e_prime) + 1);
891 copy_node_attr(e_prime, nn);
893 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
894 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
897 in[pos] = pred_info->avail;
899 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
901 value_add_or_replace(curr_info->avail_out, phi, e);
902 value_add(curr_info->new_set, phi, e);
903 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
905 /* the good case: we really replace an instruction */
906 node_set_remove(curr_info->antic_in, e);
910 } /* node_set_foreach */
914 * Do the elimination step: collect all changes
915 * We cannot do the changes right here, as this would change
916 * the hash values of the nodes in the avail_out set!
918 static void collect_elim_pairs(ir_node *block, void *ctx)
921 block_info *curr_info = get_block_info(block);
924 dump_node_set(curr_info->nodes, "Updating nodes", block);
925 node_set_foreach(v, curr_info->nodes) {
926 ir_node *l = value_lookup(curr_info->avail_out, v);
930 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
934 p->next = env->pairs;
941 * Do all the recorded changes and optimize
942 * newly created Phi's.
944 static void eliminate_nodes(elim_pair *pairs)
948 for (p = pairs; p != NULL; p = p->next) {
949 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
951 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
952 * which we can optimize here
954 if (is_Phi(p->new_node)) {
958 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
959 ir_node *pred = get_irn_n(p->new_node, i);
961 if (pred != p->old_node) {
972 exchange(p->old_node, p->new_node);
977 * Argh: Endless loops cause problems, because the
978 * insert algorithm did not terminate. We get translated nodes that
979 * references the origin. These nodes are translated again and again...
981 * The current fix is to use post-dominance. This simple ignores
982 * endless loops, ie we cannot optimize them.
984 void do_gvn_pre(ir_graph *irg)
988 optimization_state_t state;
990 unsigned antic_iter, insert_iter;
992 assert(!"COMPLETELY BROKEN YET, DO NOT USE");
994 /* register a debug mask */
995 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
996 firm_dbg_set_mask(dbg, SET_LEVEL_2);
1000 a_env.trans_set = new_node_set();
1002 a_env.start_block = get_irg_start_block(irg);
1003 a_env.end_block = get_irg_end_block(irg);
1006 /* Move Proj's into the same block as their args,
1007 else we would assign the result to wrong blocks */
1008 normalize_proj_nodes(irg);
1010 /* critical edges MUST be removed */
1011 remove_critical_cf_edges(irg);
1013 /* we need dominator for Antic_out calculation */
1014 if (get_irg_dom_state(irg) != dom_consistent)
1016 if (get_irg_postdom_state(irg) != dom_consistent)
1017 compute_postdoms(irg);
1018 /* we get all nodes of a block by following outs */
1019 if (get_irg_outs_state(irg) != outs_consistent)
1020 compute_irg_outs(irg);
1023 * Switch on GCSE. We need it to correctly compute
1024 * the leader of a node by hashing.
1026 save_optimization_state(&state);
1027 set_opt_global_cse(1);
1029 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1030 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1032 /* allocate block info for all blocks */
1033 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1035 /* compute the available value sets for all blocks */
1036 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1038 /* compute the anticipated value sets for all blocks */
1039 inc_irg_visited(irg);
1041 a_env.first_iter = 1;
1043 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1045 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1046 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1047 a_env.first_iter = 0;
1048 DB((dbg, LEVEL_1, "------------------------\n"));
1049 } while (a_env.changes != 0);
1051 /* compute redundant expressions */
1054 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1056 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1057 DB((dbg, LEVEL_1, "------------------------\n"));
1058 } while (a_env.changes != 0);
1060 /* last step: eliminate nodes */
1061 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1062 eliminate_nodes(a_env.pairs);
1064 restore_optimization_state(&state);
1066 /* clean up: delete all sets */
1067 for (p = a_env.list; p != NULL; p = p->next) {
1069 del_node_set(p->antic_in);
1071 del_value_set(p->avail_out);
1073 del_node_set(p->nodes);
1075 del_value_set(p->new_set);
1077 del_node_set(a_env.trans_set);
1078 obstack_free(&obst, NULL);
1079 set_irg_pinned(irg, op_pin_state_pinned);
1082 set_irg_outs_inconsistent(irg);
1083 set_irg_loopinfo_inconsistent(irg);