2 * Copyright (C) 1995-2008 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;
186 return identities_cmp(e1->value, e2->value);
189 /** Create a new value set. */
190 static value_set *new_value_set(void) {
191 return new_set(value_cmp, 8);
194 /** Deletes a value set. */
195 static void del_value_set(value_set *set) {
200 * Add a node node representing the value value to the set.
202 static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
207 return set_insert(set, &key, sizeof(key), value_hash(value));
210 /** computes dst = dst \/ src for value sets */
211 static void value_union(value_set *dst, value_set *src)
214 value_set_foreach(entry, src)
215 value_add(dst, entry->node, entry->value);
218 /** computes dst = dst \/ (value_set)src for value sets */
219 static void value_union_nodes(value_set *dst, node_set *src)
222 node_set_foreach(n, src)
223 value_add(dst, n, n);
227 * Lookup a value in a value set.
229 static ir_node *value_lookup(value_set *value_set, ir_node *n)
234 e = set_find(value_set, &key, sizeof(key), value_hash(n));
235 return e ? e->node : NULL;
239 * Add or replace a value in a set by an node computing the same
240 * value in a dominator block.
242 * @return non-zero if a replacement took place
244 static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
246 value_entry *e = value_add(set, node, value);
248 if (e->node != node) {
249 /* node must dominate old one here */
250 assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
259 * Returns non-zero if a node is movable.
261 static int is_nice_value(ir_node *n) {
265 n = get_Proj_pred(n);
266 mode = get_irn_mode(n);
268 * FIXME: For now, we cannot handle Div/even if it's movable.
269 * That should be fixed.
271 if (!mode_is_data(mode))
273 if (is_irn_constlike(n))
275 return (get_irn_pinned(n) != op_pin_state_pinned);
282 static void dump_node_set(node_set *set, char *txt, ir_node *block)
287 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
289 node_set_foreach(n, set) {
291 DB((dbg, LEVEL_2, "\n"));
292 DB((dbg, LEVEL_2, " %+F,", n));
295 DB((dbg, LEVEL_2, "\n}\n"));
301 static void dump_value_set(value_set *set, char *txt, ir_node *block)
306 DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
308 value_set_foreach(e, set) {
310 DB((dbg, LEVEL_2, "\n"));
311 if (e->node != e->value)
312 DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value));
314 DB((dbg, LEVEL_2, " %+F,", e->node));
317 DB((dbg, LEVEL_2, "\n}\n"));
321 #define dump_node_set(set, txt, block)
322 #define dump_value_set(set, txt, block)
323 #endif /* DEBUG_libfirm */
327 * Return the block info of a block
329 static block_info *get_block_info(ir_node *block) {
330 return get_irn_link(block);
334 * Computes Avail_out(block):
336 * Avail_in(block) = Avail_out(dom(block))
337 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
340 * This function must be called in the top-down dominance order:
341 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
343 static void compute_avail_top_down(ir_node *block, void *ctx)
346 block_info *dom_info;
347 block_info *info = get_block_info(block);
350 /* we don't need the end block Avail */
351 if (block == env->end_block)
355 * First add all nodes from the dominator.
356 * This must be done to ensure that Antic_out contains the leader
357 * for every node. The root has no dominator.
359 if (block != env->start_block) {
360 dom_blk = get_Block_idom(block);
361 assert(is_Block(dom_blk));
363 dom_info = get_block_info(dom_blk);
366 value_union(info->avail_out, dom_info->avail_out);
368 value_union_nodes(info->avail_out, info->nodes);
370 dump_value_set(info->avail_out, "Avail_out", block);
374 * returns non-zero if a tree node must be copied because of
377 static int need_copy(ir_node *node, ir_node *block)
381 /* Phi always stop the recursion */
383 return get_irn_intra_n(node, -1) == block;
385 if (! is_nice_value(node))
388 /* check predecessor */
389 arity = get_irn_intra_arity(node);
390 for (i = 0; i < arity; ++i) {
391 ir_node *pred = get_irn_intra_n(node, i);
392 ir_node *local_bl = get_irn_intra_n(pred, -1);
393 ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred);
395 pred = leader != NULL ? leader : pred;
396 if (need_copy(pred, block))
405 static ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env)
407 int i, arity, need_new;
408 ir_node *res, *nn, **in;
410 /* Phi always stop the recursion */
412 if (get_irn_intra_n(node, -1) == block)
413 return get_Phi_pred(node, pos);
417 if (! is_nice_value(node))
420 arity = get_irn_intra_arity(node);
422 NEW_ARR_A(ir_node *, in, arity);
426 ir_node *pred = get_irn_intra_n(node, i);
427 ir_node *pred_blk = get_irn_intra_n(pred, -1);
428 ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred);
429 in[i] = translate(leader ? leader : pred, block, pos, env);
430 need_new |= (in[i] != pred);
438 get_irn_dbg_info(node),
440 get_Block_cfgpred_block(block, pos),
445 /* We need the attribute copy here, because the Hash value of a
446 node might depend on that. */
447 copy_node_attr(node, nn);
448 res = node_add(env->trans_set, nn);
450 obstack_free(env->obst, nn);
452 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
462 * Implements phi_translate.
464 static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
469 if (! need_copy(node, block))
472 /* Create a copy of the node in the pos'th predecessor block.
473 Use our environmental obstack, as these nodes are always
475 old = current_ir_graph->obst;
476 current_ir_graph->obst = env->obst;
477 res = translate(node, block, pos, env);
478 current_ir_graph->obst = old;
481 } /* phi_translate */
485 * Implements phi_translate.
487 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
494 if (get_irn_intra_n(node, -1) == block)
495 return get_Phi_pred(node, pos);
499 arity = get_irn_intra_arity(node);
501 /* check if the node has at least one Phi predecessor */
502 for (i = 0; i < arity; ++i) {
503 ir_node *pred = get_irn_intra_n(node, i);
504 ir_node *pred_bl = get_irn_intra_n(pred, -1);
505 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
507 leader = leader != NULL ? leader : pred;
508 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
512 /* no Phi in the predecessors */
516 /* Create a copy of the node in the pos'th predecessor block.
517 Use our environmental obstack, as these nodes are always
519 old = current_ir_graph->obst;
520 current_ir_graph->obst = env->obst;
522 get_irn_dbg_info(node),
529 /* We need the attribute copy here, because the Hash value of a
530 node might depend on that. */
531 copy_node_attr(node, nn);
533 set_irn_n(nn, -1, get_irn_intra_n(node, -1));
534 for (i = 0; i < arity; ++i) {
535 ir_node *pred = get_irn_intra_n(node, i);
536 ir_node *pred_bl = get_irn_intra_n(pred, -1);
537 ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred);
539 leader = leader != NULL ? leader : pred;
540 if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block)
541 set_irn_n(nn, i, get_Phi_pred(leader, pos));
543 set_irn_n(nn, i, leader);
545 res = node_add(env->trans_set, nn);
546 current_ir_graph->obst = old;
549 obstack_free(env->obst, nn);
551 DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res));
554 } /* phi_translate */
557 * check if a node n is clean in block block.
559 static int _is_clean(ir_node *n, ir_node *block)
563 if (get_nodes_block(n) != block)
571 if (! is_nice_value(n))
573 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
574 ir_node *pred = get_irn_n(n, i);
575 if (! _is_clean(pred, block))
585 * check if a node n is clean.
587 static int is_clean(ir_node *n)
589 int res = _is_clean(n, get_nodes_block(n));
595 * This function is called for node sets with is_clean
596 * nodes only, so we must just remove nodes that don't
597 * have available inputs
599 static void clean_node_set(node_set *set, ir_node *blk)
601 ir_node *n, *pred, *pred_blk;
605 for (n = node_set_first(set); n; n = node_set_next(set)) {
606 for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) {
607 pred = get_irn_intra_n(n, i);
609 pred_blk = get_irn_intra_n(pred, -1);
610 if (block_dominates(pred_blk, blk))
612 /* pred do not dominate it, but may be in the set */
613 if (node_lookup(set, pred) != NULL)
615 /* we found a node that must be removed */
617 node_set_remove(set, n);
618 DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n));
625 * computes Antic_in(block):
627 static void compute_antic(ir_node *block, void *ctx)
630 block_info *succ_info;
631 block_info *info = get_block_info(block);
635 /* no need for computations in start block */
636 if (block == env->start_block)
639 size = node_set_count(info->antic_in);
641 /* the end block has no successor */
642 if (block != env->end_block) {
643 int n_succ = get_Block_n_cfg_outs(block);
646 ir_node *node, *list;
649 /* find blocks position in succ's block predecessors */
650 succ = get_Block_cfg_out(block, 0);
651 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
652 if (get_Block_cfgpred_block(succ, i) == block) {
659 succ_info = get_block_info(succ);
660 /* translate into list: we cannot insert into a set we iterate
661 * and succ might be equal to block for endless loops */
663 node_set_foreach(node, succ_info->antic_in) {
664 set_irn_link(node, list);
667 for (node = list; node; node = get_irn_link(node)) {
668 ir_node *trans = phi_translate(node, succ, pos, env);
671 node_add(info->antic_in, trans);
676 block_info *succ0_info;
681 /* Select a successor to compute the disjoint of all Nodes
682 sets, it might be useful to select the block with the
683 smallest number of nodes. For simplicity we choose the
685 succ0 = get_Block_cfg_out(block, 0);
686 succ0_info = get_block_info(succ0);
687 node_set_foreach(n, succ0_info->antic_in) {
688 /* we need the disjoint */
689 for (i = 1; i < n_succ; ++i) {
690 ir_node *succ = get_Block_cfg_out(block, i);
691 block_info *succ_info = get_block_info(succ);
692 if (node_lookup(succ_info->antic_in, n) == NULL)
696 /* we found a node that is common in all Antic_in(succ(b)),
697 put it in Antic_in(b) */
698 node_add(info->antic_in, n);
704 * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b).
705 * It is enough to do this in the first iteration, because
706 * the set info->nodes is not changed anymore.
708 if (env->first_iter) {
710 node_set_foreach(n, info->nodes) {
712 node_add(info->antic_in, n);
717 // clean_node_set(info->antic_in, block);
718 (void) clean_node_set;
720 dump_node_set(info->antic_in, "Antic_in", block);
721 if (size != node_set_count(info->antic_in)) {
722 /* the Antic_in set has changed */
725 } /* compute_antic */
728 * allocate a block info
730 static void alloc_blk_info(ir_node *block, void *ctx)
734 block_info *info = obstack_alloc(env->obst, sizeof(*info));
736 set_irn_link(block, info);
737 info->nodes = new_node_set();
738 info->antic_in = new_node_set();
739 info->avail_out = new_value_set();
742 info->new_set = NULL;
743 info->next = env->list;
746 /* fill the nodes set, we will need it later */
747 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
748 ir_node *n = get_irn_out(block, i);
750 set_irn_link(n, NULL);
752 /* we cannot optimize pinned nodes, so do not remember them */
753 if (is_nice_value(n))
754 node_add(info->nodes, n);
759 * Perform insertion of partially redundant values.
760 * For every Block node, do the following:
761 * 1. Propagate the NEW_SETS of the dominator into the current block.
762 * If the block has multiple predecessors,
763 * 2a. Iterate over the ANTIC expressions for the block to see if
764 * any of them are partially redundant.
765 * 2b. If so, insert them into the necessary predecessors to make
766 * the expression fully redundant.
767 * 2c. Insert a new Phi merging the values of the predecessors.
768 * 2d. Insert the new Phi, and the new expressions, into the
771 static void insert_nodes(ir_node *block, void *ctx)
775 ir_node *e, *idom, *first_s, *worklist;
776 block_info *curr_info, *idom_info;
777 int pos, arity = get_irn_intra_arity(block);
778 int all_same, by_some, updated;
780 /* ensure that even the start block has a new_set */
781 curr_info = get_block_info(block);
782 if (curr_info->new_set)
783 del_value_set(curr_info->new_set);
784 curr_info->new_set = new_value_set();
786 if (block == env->start_block)
789 idom = get_Block_idom(block);
790 idom_info = get_block_info(idom);
792 /* update the new_sets */
794 dump_value_set(idom_info->new_set, "[New Set]", idom);
795 value_set_foreach(entry, idom_info->new_set) {
796 updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
799 dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
805 /* convert the set into a list. This allows the removal of
806 * elements from the set */
808 node_set_foreach(e, curr_info->antic_in) {
809 set_irn_link(e, worklist);
813 for (e = worklist; e != NULL; e = get_irn_link(e)) {
816 /* If the value was already computed in the dominator, then
817 it is totally redundant. Hence we have nothing to insert. */
818 if (value_lookup(idom_info->avail_out, e)) {
819 // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
828 /* for all predecessor blocks */
829 for (pos = 0; pos < arity; ++pos) {
830 block_info *pred_info;
831 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
832 ir_node *e_prime, *v_prime, *e_dprime;
834 /* ignore bad blocks. */
835 if (is_Bad(pred_blk))
838 e_prime = phi_translate(e, block, pos, env);
841 pred_info = get_block_info(pred_blk);
842 e_dprime = value_lookup(pred_info->avail_out, v_prime);
844 if (e_dprime == NULL) {
846 pred_info->avail = e_prime;
847 pred_info->not_found = 1;
850 mode = get_irn_mode(e_dprime);
852 pred_info->avail = e_dprime;
853 pred_info->not_found = 0;
857 else if (first_s != e_dprime)
860 DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
864 /* If it's not the same value already existing along every predecessor, and
865 it's defined by some predecessor, it is partially redundant. */
866 if (! all_same && by_some) {
869 DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
871 in = xmalloc(arity * sizeof(*in));
872 /* for all predecessor blocks */
873 for (pos = 0; pos < arity; ++pos) {
874 ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
875 block_info *pred_info = get_block_info(pred_blk);
877 /* ignore bad blocks. */
878 if (is_Bad(pred_blk)) {
883 /* ignore blocks that already have the expression */
884 if (pred_info->not_found) {
885 ir_node *e_prime = pred_info->avail;
887 if (!is_Phi(e_prime)) {
888 mode = get_irn_mode(e_prime);
890 get_irn_dbg_info(e_prime),
891 current_ir_graph, pred_blk,
894 get_irn_arity(e_prime),
895 get_irn_in(e_prime) + 1);
896 copy_node_attr(e_prime, nn);
898 DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
899 pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
902 in[pos] = pred_info->avail;
904 phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
906 value_add_or_replace(curr_info->avail_out, phi, e);
907 value_add(curr_info->new_set, phi, e);
908 DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
910 /* the good case: we really replace an instruction */
911 node_set_remove(curr_info->antic_in, e);
915 } /* node_set_foreach */
919 * Do the elimination step: collect all changes
920 * We cannot do the changes right here, as this would change
921 * the hash values of the nodes in the avail_out set!
923 static void collect_elim_pairs(ir_node *block, void *ctx)
926 block_info *curr_info = get_block_info(block);
929 dump_node_set(curr_info->nodes, "Updating nodes", block);
930 node_set_foreach(v, curr_info->nodes) {
931 ir_node *l = value_lookup(curr_info->avail_out, v);
935 elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
939 p->next = env->pairs;
946 * Do all the recorded changes and optimize
947 * newly created Phi's.
949 static void eliminate_nodes(elim_pair *pairs)
953 for (p = pairs; p != NULL; p = p->next) {
954 DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node));
956 * PRE tends to create Phi(self, self, ... , x, self, self, ...)
957 * which we can optimize here
959 if (is_Phi(p->new_node)) {
963 for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) {
964 ir_node *pred = get_irn_n(p->new_node, i);
966 if (pred != p->old_node) {
977 exchange(p->old_node, p->new_node);
982 * Argh: Endless loops cause problems, because the
983 * insert algorithm did not terminate. We get translated nodes that
984 * references the origin. These nodes are translated again and again...
986 * The current fix is to use post-dominance. This simple ignores
987 * endless loops, ie we cannot optimize them.
989 void do_gvn_pre(ir_graph *irg)
993 optimization_state_t state;
995 unsigned antic_iter, insert_iter;
997 assert(!"COMPLETELY BROKEN YET, DO NOT USE");
999 /* register a debug mask */
1000 FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
1001 firm_dbg_set_mask(dbg, SET_LEVEL_2);
1003 obstack_init(&obst);
1005 a_env.trans_set = new_node_set();
1007 a_env.start_block = get_irg_start_block(irg);
1008 a_env.end_block = get_irg_end_block(irg);
1011 /* Move Proj's into the same block as their args,
1012 else we would assign the result to wrong blocks */
1013 normalize_proj_nodes(irg);
1015 /* critical edges MUST be removed */
1016 remove_critical_cf_edges(irg);
1018 /* we need dominator for Antic_out calculation */
1019 if (get_irg_dom_state(irg) != dom_consistent)
1021 if (get_irg_postdom_state(irg) != dom_consistent)
1022 compute_postdoms(irg);
1023 /* we get all nodes of a block by following outs */
1024 if (get_irg_outs_state(irg) != outs_consistent)
1025 compute_irg_outs(irg);
1028 * Switch on GCSE. We need it to correctly compute
1029 * the leader of a node by hashing.
1031 save_optimization_state(&state);
1032 set_opt_global_cse(1);
1034 DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg)));
1035 printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg)));
1037 /* allocate block info for all blocks */
1038 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
1040 /* compute the available value sets for all blocks */
1041 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
1043 /* compute the anticipated value sets for all blocks */
1044 inc_irg_visited(irg);
1046 a_env.first_iter = 1;
1048 DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
1050 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
1051 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
1052 a_env.first_iter = 0;
1053 DB((dbg, LEVEL_1, "------------------------\n"));
1054 } while (a_env.changes != 0);
1056 /* compute redundant expressions */
1059 DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
1061 dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
1062 DB((dbg, LEVEL_1, "------------------------\n"));
1063 } while (a_env.changes != 0);
1065 /* last step: eliminate nodes */
1066 dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env);
1067 eliminate_nodes(a_env.pairs);
1069 restore_optimization_state(&state);
1071 /* clean up: delete all sets */
1072 for (p = a_env.list; p != NULL; p = p->next) {
1074 del_node_set(p->antic_in);
1076 del_value_set(p->avail_out);
1078 del_node_set(p->nodes);
1080 del_value_set(p->new_set);
1082 del_node_set(a_env.trans_set);
1083 obstack_free(&obst, NULL);
1084 set_irg_pinned(irg, op_pin_state_pinned);
1087 set_irg_outs_inconsistent(irg);
1088 set_irg_loopinfo_inconsistent(irg);