+ 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 */
+ } /* node_set_foreach */
+} /* insert_nodes */
+
+/**
+ * Do the elimination step: collect all changes
+ * We cannot do the changes right here, as this would change
+ * the hash values of the nodes in the avail_out set!
+ */
+static void collect_elim_pairs(ir_node *block, void *ctx)
+{
+ pre_env *env = ctx;
+ block_info *curr_info = get_block_info(block);
+ ir_node *v;
+
+ dump_node_set(curr_info->nodes, "Updating nodes", block);
+ node_set_foreach(v, curr_info->nodes) {
+ ir_node *l = value_lookup(curr_info->avail_out, v);
+
+ assert(l);
+ if (l != v) {
+ elim_pair *p = obstack_alloc(env->obst, sizeof(*p));
+
+ p->old_node = v;
+ p->new_node = l;
+ p->next = env->pairs;
+ env->pairs = p;