- pre_env *env = ctx;
- value_entry *entry;
- ir_node *e, *idom, *first_s, *worklist;
- block_info *curr_info, *idom_info;
- int pos, arity = get_irn_intra_arity(block);
- int all_same, by_some, updated;
-
- /* ensure that even the start block has a new_set */
- curr_info = get_block_info(block);
- if (curr_info->new_set)
- del_value_set(curr_info->new_set);
- curr_info->new_set = new_value_set();
-
- if (block == env->start_block)
- return;
-
- idom = get_Block_idom(block);
- idom_info = get_block_info(idom);
-
- /* update the new_sets */
- updated = 0;
- dump_value_set(idom_info->new_set, "[New Set]", idom);
- value_set_foreach(entry, idom_info->new_set) {
- updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
- }
- if (updated) {
- dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
- }
-
- if (arity <= 1)
- return;
-
- /* convert the set into a list. This allows the removal of
- * elements from the set */
- worklist = NULL;
- node_set_foreach(e, curr_info->antic_in) {
- set_irn_link(e, worklist);
- worklist = e;
- }
-
- for (e = worklist; e != NULL; e = get_irn_link(e)) {
- ir_mode *mode;
-
- /* If the value was already computed in the dominator, then
- it is totally redundant. Hence we have nothing to insert. */
- if (value_lookup(idom_info->avail_out, e)) {
-// DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
- continue;
- }
-
- by_some = 0;
- all_same = 1;
- first_s = NULL;
- mode = NULL;
-
- /* for all predecessor blocks */
- for (pos = 0; pos < arity; ++pos) {
- block_info *pred_info;
- ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
- ir_node *e_prime, *v_prime, *e_dprime;
-
- /* ignore bad blocks. */
- if (is_Bad(pred_blk))
- continue;
-
- e_prime = phi_translate(e, block, pos, env);
- v_prime = e_prime;
-
- pred_info = get_block_info(pred_blk);
- e_dprime = value_lookup(pred_info->avail_out, v_prime);
-
- if (e_dprime == NULL) {
- all_same = 0;
- pred_info->avail = e_prime;
- pred_info->not_found = 1;
- }
- else {
- mode = get_irn_mode(e_dprime);
- e_dprime = e_dprime;
- pred_info->avail = e_dprime;
- pred_info->not_found = 0;
- by_some = 1;
- if (first_s == NULL)
- first_s = e_dprime;
- else if (first_s != e_dprime)
- all_same = 0;
-
- DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
- } /* if */
- } /* for */
-
- /* If it's not the same value already existing along every predecessor, and
- it's defined by some predecessor, it is partially redundant. */
- if (! all_same && by_some) {
- ir_node *phi, **in;
-
- DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block));
-
- in = xmalloc(arity * sizeof(*in));
- /* for all predecessor blocks */
- for (pos = 0; pos < arity; ++pos) {
- ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
- block_info *pred_info = get_block_info(pred_blk);
-
- /* ignore bad blocks. */
- if (is_Bad(pred_blk)) {
- in[pos] = new_Bad();
- continue;
- }
-
- /* ignore blocks that already have the expression */
- if (pred_info->not_found) {
- ir_node *e_prime = pred_info->avail;
- ir_node *nn;
- if (!is_Phi(e_prime)) {
- mode = get_irn_mode(e_prime);
- nn = new_ir_node(
- get_irn_dbg_info(e_prime),
- current_ir_graph, pred_blk,
- get_irn_op(e_prime),
- mode,
- get_irn_arity(e_prime),
- get_irn_in(e_prime) + 1);
- copy_node_attr(e_prime, nn);
-
- DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
- pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node;
- }
- }
- in[pos] = pred_info->avail;
- } /* for */
- phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
- free(in);
- value_add_or_replace(curr_info->avail_out, phi, e);
- value_add(curr_info->new_set, phi, e);
- DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e));
-
- /* the good case: we really replace an instruction */
- node_set_remove(curr_info->antic_in, e);
-
- env->changes |= 1;
- } /* if */
+ pre_env *env = (pre_env*)ctx;
+ ir_node *value;
+ ir_node *expr;
+ ir_node *idom;
+ block_info *curr_info;
+ int pos;
+ int arity = get_irn_arity(block);
+ ir_valueset_iterator_t iter;
+
+ /* filter only blocks */
+ if (! is_Block(block))
+ return;
+
+ /* ensure that even the start block has a new_set */
+ curr_info = get_block_info(block);
+ if (curr_info->new_set)
+ ir_valueset_del(curr_info->new_set);
+ curr_info->new_set = ir_valueset_new(16);
+
+ if (block == env->start_block)
+ return;
+
+ DB((dbg, LEVEL_2, "Insert operation of %+F\n", block));
+
+ idom = get_Block_idom(block);
+ update_new_set(block, idom);
+
+ /* process only merge blocks */
+ if (arity < 2)
+ return;
+
+ /* for each antic_in */
+ foreach_valueset(curr_info->antic_in, value, expr, iter) {
+ ir_mode *mode;
+ ir_node *phi;
+ ir_node *phi_value;
+ ir_node **phi_in;
+
+ /* filter phi nodes from antic in */
+ if (is_Phi(expr))
+ continue;
+
+ /* A value computed in the dominator is totally redundant.
+ Hence we have nothing to insert. */
+ if (ir_valueset_lookup(get_block_info(idom)->avail_out, value)) {
+ DB((dbg, LEVEL_2, "Fully redundant expr %+F value %+F\n", expr, value));
+ continue;
+ }
+
+ mode = find_partially_redundant(block, expr);
+ if (mode == NULL)
+ continue;
+
+ DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block));
+
+ phi_in = XMALLOCN(ir_node *, arity);
+
+ /* for all predecessor blocks */
+ for (pos = 0; pos < arity; ++pos) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, pos);
+ block_info *pred_info;
+
+ /* ignore bad blocks. */
+ if (is_Bad(pred_block)) {
+ ir_graph *irg = get_irn_irg(pred_block);
+ phi_in[pos] = new_r_Bad(irg, mode);
+ continue;
+ }
+ pred_info = get_block_info(pred_block);
+
+ /* ignore blocks that already have the expression */
+ if (! pred_info->found) {
+ ir_node *translated = get_translated(expr, pred_block);
+ ir_node *trans_value;
+
+ /* make sure translated dominates its use */
+ translated = fix_translation(translated, pred_block);
+ DB((dbg, LEVEL_3, "Use translated %+F in %+F because expr %+F not available\n", translated, pred_block, expr));
+
+ /* make the new node available */
+ trans_value = remember(translated);
+ ir_valueset_insert(pred_info->avail_out, trans_value, translated);
+ phi_in[pos] = translated;
+ DB((dbg, LEVEL_5, "phi_in %+F\n", translated));
+ } else {
+ phi_in[pos] = pred_info->avail;
+ DB((dbg, LEVEL_5, "phi_in %+F\n", pred_info->avail));
+ }
+
+ } /* for */
+
+ phi = new_r_Phi(block, arity, phi_in, mode);
+ free(phi_in);
+ DB((dbg, LEVEL_1, "New %+F for redundant %+F created\n", phi, expr));
+
+ phi_value = remember(phi);
+
+ /* this 'global' value is now available through the new phi */
+ ir_valueset_replace(curr_info->avail_out, value, phi);
+ /* add this phi and its 'blocklocal' value */
+ ir_valueset_insert(curr_info->avail_out, phi_value, phi);
+
+ ir_valueset_insert(curr_info->new_set, value, phi);
+ ir_valueset_insert(curr_info->new_set, phi_value, phi);
+
+ /* remove from antic_in to prevent reprocessing */
+ ir_valueset_remove_iterator(curr_info->antic_in, &iter);
+
+ env->changes |= 1;
+