+/**
+ * Block-walker, computes Antic_in(block).
+ *
+ * @param block the block
+ * @param ctx the walker environment
+ */
+static void compute_antic(ir_node *block, void *ctx)
+{
+ pre_env *env = (pre_env*)ctx;
+ block_info *succ_info;
+ block_info *info;
+ ir_node *succ, *value, *expr;
+ size_t size;
+ ir_valueset_iterator_t iter;
+
+ /* filter blocks from topologic walker */
+ if (! is_Block(block))
+ return;
+
+ /* no need for computations in start block */
+ if (block == env->start_block)
+ return;
+
+ /* the end block has no successor */
+ if (block == env->end_block)
+ return;
+
+ info = get_block_info(block);
+ size = ir_valueset_size(info->antic_in);
+ int n_succ;
+
+ /* This step puts all generated expression from the
+ current block into antic_in.
+ This is needs to be done in the first iteration only. */
+ if (env->first_iter) {
+ foreach_valueset(info->exp_gen, value, expr, iter) {
+ /* We will have phi nodes in antic in.
+ This should prevent special cases in several places. */
+ ir_valueset_insert(info->antic_in, value, expr);
+ }
+ }
+
+ /* TODO handle endless loops. */
+
+ n_succ = get_Block_n_cfg_outs(block);
+ if (n_succ == 1) {
+ int pos = -1;
+
+ /* find blocks position in succ's block predecessors */
+ succ = get_Block_cfg_out(block, 0);
+ pos = get_Block_cfgpred_pos(succ, block);
+ assert(pos >= 0);
+
+ succ_info = get_block_info(succ);
+ /* translate into list: we cannot insert into a set we iterate
+ * and succ might be equal to block for endless loops */
+ foreach_valueset(succ_info->antic_in, value, expr, iter) {
+ ir_node *trans, *newval;
+
+ DB((dbg, LEVEL_5, "Begin phi translate antic: expr %+F from %+F to %d\n", expr, succ, pos));
+
+ /* TODO if successor block has 1 predecessor we need no phi translation.
+ But the clean_in_block check is still needed! */
+ /* TODO phi translation and clean in block are overlapping,
+ because phi trans perhaps should know in advance if predecessors are clean. */
+ trans = phi_translate(expr, succ, pos);
+ newval = remember(trans);
+
+ DB((dbg, LEVEL_5, "----> phi translate antic: expr %+F from %+F to %d is trans %+F\n", expr, succ, pos, trans));
+
+ if (is_clean_in_block_antic(trans, block)) {
+ if (! is_irn_constlike(trans)) {
+ ir_valueset_insert(info->antic_in, newval, trans);
+ }
+ DB((dbg, LEVEL_5, " translated %+F clean in %+F\n", trans, block));
+
+ } else {
+ DB((dbg, LEVEL_5, " translated %+F not clean in %+F\n", trans, block));
+ }
+
+ /* We have to set translated anyway
+ because expr might still be hoisted _into_ block. */
+ set_translated(expr, succ, pos, trans);
+
+ DB((dbg, LEVEL_5, "- end: expr %+F -----\n\n", expr));
+ }
+
+ } else if (n_succ > 1) {
+ ir_node *succ0;
+ block_info *succ0_info;
+ int i, common = 1;
+
+ /* Select a successor to compute the disjoint of all nodes
+ sets, it might be useful to select the block with the
+ smallest number of nodes. For simplicity we choose the
+ first one. */
+ succ0 = get_Block_cfg_out(block, 0);
+ succ0_info = get_block_info(succ0);
+
+ foreach_valueset(succ0_info->antic_in, value, expr, iter) {
+ /* we need the disjoint */
+ for (i = 1; i < n_succ; ++i) {
+ ir_node *succ = get_Block_cfg_out(block, i);
+ block_info *succ_info = get_block_info(succ);
+
+ if (ir_valueset_lookup(succ_info->antic_in, value) == NULL) {
+ common = 0;
+ break;
+ }
+ }
+
+ if (common) {
+ /* we found a value that is common in all Antic_in(succ(b)),
+ put it in Antic_in(b) if the value is not already represented. */
+ if (is_clean_in_block_antic(expr, block)) {
+ ir_valueset_insert(info->antic_in, value, expr);
+ }
+ set_translated(expr, succ0, 0, expr);
+
+ } else {
+ set_translated(expr, succ0, 0, expr);
+ }
+
+ }
+ }
+
+ dump_value_set(info->antic_in, "Antic_in", block);
+ if (size != ir_valueset_size(info->antic_in)) {
+ env->changes |= 1;
+ }
+
+} /* compute_antic */
+
+/**
+ * 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;
+ int pos, arity = get_irn_arity(block);
+ int fully_redundant, partially_redundant;
+ ir_mode *mode;
+
+ DB((dbg, LEVEL_3, "Examine expr %+F of %+F\n", expr, block));
+
+ partially_redundant = 0;
+ fully_redundant = 1;
+ first_avail = NULL;
+ mode = NULL;
+
+ /* for each predecessor blocks */
+ for (pos = 0; pos < arity; ++pos) {
+ block_info *pred_info;
+ ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
+ ir_node *trans_expr, *trans_value, *avail_expr;
+
+ /* ignore bad blocks. */
+ if (is_Bad(pred_blk))
+ 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_blk);
+ 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 differnet 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_blk));
+ } /* 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;
+ else
+ return NULL;