+ pre_env *env = ctx;
+ ir_node *value, *expr, *idom, *first_s, *worklist;
+ block_info *curr_info, *idom_info;
+ int pos, arity = get_irn_intra_arity(block);
+ int all_same, by_some, updated;
+ ir_valueset_iterator_t iter;
+
+ /* 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;
+
+ 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);
+ foreach_valueset(idom_info->new_set, value, expr, iter) {
+ ir_valueset_insert(curr_info->new_set, value, expr);
+ updated |= ir_valueset_replace(curr_info->avail_out, value, expr);
+ }
+ 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;
+ foreach_valueset(curr_info->antic_in, value, expr, iter) {
+ ir_mode *mode;
+
+ /* If the value was already computed in the dominator, then
+ it is totally redundant. Hence we have nothing to insert. */
+ if (ir_valueset_lookup(idom_info->avail_out, value)) {
+ // 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(expr, block, pos, curr_info->avail_out);
+ v_prime = lookup(e_prime);
+ if (v_prime == NULL)
+ v_prime = value;
+
+ pred_info = get_block_info(pred_blk);
+ e_dprime = ir_valueset_lookup(pred_info->avail_out, v_prime);
+
+ if (e_dprime == NULL) {
+ pred_info->avail = e_prime;
+ pred_info->not_found = 1;
+ all_same = 0;
+ } else {
+ pred_info->avail = e_dprime;
+ pred_info->not_found = 0;
+ mode = get_irn_mode(e_dprime);
+ e_dprime = e_dprime;
+ 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", expr, 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, *l, **in;
+
+ DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block));
+
+ in = XMALLOCN(ir_node*, arity);
+ /* 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)) {
+ ir_node *proj_pred = NULL;
+ if (is_Proj(e_prime)) {
+ ir_node *pred = get_Proj_pred(e_prime);
+ mode = get_irn_mode(pred);
+ nn = new_ir_node(
+ get_irn_dbg_info(pred),
+ current_ir_graph, pred_blk,
+ get_irn_op(pred),
+ mode,
+ get_irn_arity(pred),
+ get_irn_in(pred) + 1);
+ copy_node_attr(current_ir_graph, pred, nn);
+
+ DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk));
+ proj_pred = nn;
+ }
+ 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(current_ir_graph, e_prime, nn);
+ if (proj_pred != NULL) {
+ set_Proj_pred(nn, proj_pred);
+ }
+
+ DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk));
+ l = lookup(expr);
+ if (l == NULL) {
+ l = add(expr, value);
+ }
+ ir_valueset_insert(pred_info->avail_out, add(nn, l), nn);
+ pred_info->avail = nn;
+ }
+ }
+ in[pos] = pred_info->avail;
+ } /* for */
+ phi = new_r_Phi(block, arity, in, mode);
+ l = lookup(expr);
+ if (l == NULL) {
+ l = add(expr, value);
+ }
+ value = add(phi, l);
+ ir_valueset_replace(curr_info->avail_out, value, phi);
+ ir_valueset_insert(curr_info->new_set, value, phi);
+ free(in);
+ DB((dbg, LEVEL_1, "New %+F for redundant %+F created\n", phi, expr));
+ ir_valueset_remove_iterator(curr_info->antic_in, &iter);
+ env->changes |= 1;
+ } /* if */
+ } /* node_set_foreach */
+} /* insert_nodes */