+/**
+ * Finds if the value of expr is a partially redundant value in block.
+ *
+ * @param block the block
+ * @param expr the expression
+ *
+ * @return mode of the expression if it is partially redundant else NULL
+ */
+static ir_mode *find_partially_redundant(ir_node *block, ir_node *expr)
+{
+ ir_node *first_avail = NULL;
+ int pos;
+ int arity = get_irn_arity(block);
+ int fully_redundant = 1;
+ int partially_redundant = 0;
+ ir_mode *mode = NULL;
+
+ DB((dbg, LEVEL_3, "Examine expr %+F of %+F\n", expr, block));
+
+ /* for each predecessor blocks */
+ for (pos = 0; pos < arity; ++pos) {
+ block_info *pred_info;
+ ir_node *pred_block = get_Block_cfgpred_block(block, pos);
+ ir_node *trans_expr;
+ ir_node *trans_value;
+ ir_node *avail_expr;
+
+ /* ignore bad blocks. */
+ if (is_Bad(pred_block))
+ continue;
+
+ trans_expr = get_translated(expr, get_Block_cfgpred_block(block,pos));
+ DB((dbg, LEVEL_2, "expr %+F trans @ %d is translated %+F\n", expr, pos, trans_expr));
+ /* exp in antic in, so pred is clean
+ uncover when it is not */
+ assert(trans_expr);
+
+ trans_value = identify(trans_expr);
+ DB((dbg, LEVEL_2, "trans_value %+F\n", trans_value));
+ assert(trans_value);
+
+ pred_info = get_block_info(pred_block);
+ avail_expr = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
+ DB((dbg, LEVEL_2, "avail_expr %+F\n", avail_expr));
+
+ if (avail_expr == NULL) {
+ /* expr not available */
+ pred_info->avail = expr;
+ pred_info->found = 0;
+ fully_redundant = 0;
+
+ } else {
+ /* expr is available */
+ pred_info->avail = avail_expr;
+ pred_info->found = 1;
+ mode = get_irn_mode(avail_expr);
+ partially_redundant = 1;
+
+ if (first_avail == NULL)
+ first_avail = avail_expr;
+ else if (first_avail != avail_expr)
+ /* Multiple different expressions are available */
+ fully_redundant = 0;
+
+ DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, avail_expr, pred_block));
+ } /* if */
+ } /* for */
+
+ /* If it is not the same value already existing along every predecessor
+ and it is defined by some predecessor then it is partially redundant. */
+ if (! fully_redundant && partially_redundant)
+ return mode;
+
+ return NULL;
+}
+
+/**
+ * Copies node and its predecessors to a block that dominates the target block.
+ *
+ * @param node the node
+ * @param target the target block
+ *
+ * @return copy of node node dominating target block
+ */
+static ir_node *fix_translation(ir_node *node, ir_node *target)
+{
+ ir_node *nn;
+ int i;
+ int arity;
+ ir_node **ins;
+
+ DB((dbg, LEVEL_1, "Fix_translation %+F into %+F\n", node, target));
+
+ /* identifies unreachable blocks using domination */
+ if (get_Block_dom_depth(get_nodes_block(node)) < 0 ||
+ (get_Block_dom_depth(target) < 0))
+ return new_r_Bad(get_irn_irg(node), get_irn_mode(node));
+
+ /* Walk upwards until the node dominates its use in target block.
+ Precondition is that the node is clean. */
+ if (block_dominates(get_nodes_block(node), target))
+ return node;
+
+ DB((dbg, LEVEL_1, "Fix_translation%+F of node %+F does not dominate target %+F\n", get_nodes_block(node), node, target));
+
+ arity = get_irn_arity(node);
+ ins = XMALLOCN(ir_node*, arity);
+
+ for (i = arity - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(node, i);
+ ir_node *fixed = fix_translation(pred, target);
+
+ DB((dbg, LEVEL_1, "Fixed %+F to %+F for node %+F\n", pred, fixed, node));
+ ins[i] = fixed;
+ }
+
+ nn = new_ir_node(
+ get_irn_dbg_info(node),
+ get_irn_irg(node),
+ target,
+ get_irn_op(node),
+ get_irn_mode(node),
+ arity,
+ ins);
+ free(ins);
+ copy_node_attr(get_irn_irg(node), node, nn);
+
+ DB((dbg, LEVEL_1, "New fixed node %+F from translated %+F. target %+F\n", nn, node, target));
+
+ nn = optimize_node(nn);
+ remember(nn);
+ return nn;
+} /* fix_translation */
+
+/**
+ * Updates the new_set of a block by adding the new_set of
+ * the immediate dominating block.
+ *
+ * @param the block
+ */
+static void update_new_set(ir_node *block, ir_node *idom)
+{
+ ir_node *value;
+ ir_node *expr;
+ ir_valueset_iterator_t iter;
+ block_info *curr_info = get_block_info(block);
+ block_info *idom_info = get_block_info(idom);
+ int 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);
+ }
+} /* update_new_set */
+