gvn_pre.c

/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief   Global Value Numbering Partial Redundancy Elimination
 *          (VanDrunen Hosking 2004)
 * @author  Michael Beck
 * @brief
 */
#include "debug.h"
#include "ircons.h"
#include "irdom.h"
#include "iredges.h"
#include "irflag.h"
#include "irgmod.h"
#include "irgopt.h"
#include "irgwalk.h"
#include "irnodehashmap.h"
#include "irnodeset.h"
#include "iropt_dbg.h"
#include "iroptimize.h"
#include "irouts.h"
#include "valueset.h"
#include "irloop.h"
#include "firmstat_t.h"

#include "irgraph_t.h"
#include "irnode_t.h"
#include "iropt_t.h"
#include "plist.h"

/* suggested by GVN-PRE authors */
#define MAX_ANTIC_ITER 10
#define MAX_INSERT_ITER 3

/* Stops antic iteration from processing endless loops. */
#define IGNORE_INF_LOOPS 1
/* Stops antic information to flow over infinite loop backedge */
#define NO_INF_LOOPS 0

/* Attempt to reduce register pressure and reduce code size
   for hoisted nodes. */
#define HOIST_HIGH 1
#define COMMON_DOM 1

/* Seamless implementation of handling loads and generally memory
   dependent nodes with GVN-PRE. */
#define LOADS 1
#define DIVMODS 0

/* Experimental */

/* Only optimize node directly after phi node if node is only successor. */
#define MIN_CUT 0

/* GVN is very limited. This enables optimize_node during value recognition.
   GVN ist still very limited, since a+1+b+1 doesn't equal a+b+2.
   TODO Broken for yet unknown reasons. */
#define OPTIMIZE_NODES 0


/** Additional info we need for every block. */
typedef struct block_info {
	ir_valueset_t     *exp_gen;    /* contains this blocks clean expressions */
	ir_valueset_t     *avail_out;  /* available values at block end */
	ir_valueset_t     *antic_in;   /* clean anticipated values at block entry */
	ir_valueset_t     *antic_done; /* keeps elements of antic_in after insert nodes phase */
	ir_valueset_t     *new_set;    /* new by hoisting made available values */
	ir_nodehashmap_t  *trans;      /* contains translated nodes translated into block */
	ir_node           *avail;      /* saves available node for insert node phase */
	int                found;      /* saves kind of availability for insert_node phase */
	ir_node           *block;      /* block of the block_info */
	struct block_info *next;       /* links all instances for easy access */
} block_info;

/**
 * A pair of nodes to be exchanged.
 * We have to defer the exchange because there are still needed references
 * to certain nodes.
 */
typedef struct elim_pair {
	ir_node *old_node;      /* node that will be replaced */
	ir_node *new_node;      /* replacement for old_node */
	struct elim_pair *next; /* links all instances for easy access */
	int     reason;         /* reason for the replacement */
} elim_pair;

/** environment for the GVN-PRE algorithm */
typedef struct pre_env {
	ir_graph       *graph;        /* current graph */
	struct obstack  obst;         /* obstack to allocate on */
	ir_node        *start_block;  /* start block of the current graph */
	ir_node        *end_block;    /* end block of the current graph */
	ir_node        *end_node;     /* end node of the current graph */
	block_info     *list;         /* block_info list head */
	elim_pair      *pairs;        /* elim_pair list head */
	ir_nodeset_t   *keeps;        /* a list of to be removed phis to kill their keep alive edges */
	unsigned        last_idx;     /* last node index of input graph */
	char            changes;      /* flag for fixed point iterations - non-zero if changes occurred */
	char            first_iter;   /* non-zero for first fixed point iteration */
	int             iteration;    /* iteration counter */
#if OPTIMIZE_NODES
	pset           *value_table;   /* standard value table*/
	pset           *gvnpre_values; /* gvnpre value table */
#endif
} pre_env;

static pre_env *environ;

/* custom GVN value map */
static ir_nodehashmap_t value_map;

/* debug module handle */
DEBUG_ONLY(static firm_dbg_module_t *dbg;)

#ifdef DEBUG_libfirm

/* --------------------------------------------------------
 * Statistics
 * --------------------------------------------------------
 */

typedef struct gvnpre_statistics {
	int replaced;
	int partially;
	int fully;
	int loads;
	int divmods;
	int hoist_high;
	int first_iter_found;
	int antic_iterations;
	int insert_iterations;
	int infinite_loops;
} gvnpre_statistics;

static gvnpre_statistics *gvnpre_stats = NULL;

static void init_stats(void)
{
	gvnpre_stats = XMALLOCZ(gvnpre_statistics);
}

static void free_stats(void)
{
	free(gvnpre_stats);
	gvnpre_stats = NULL;
}

static void print_stats(void)
{
	gvnpre_statistics *stats = gvnpre_stats;
	DB((dbg, LEVEL_1, "replaced             : %d\n", stats->replaced));
	DB((dbg, LEVEL_1, "antic_in iterations  : %d\n", stats->antic_iterations));
	DB((dbg, LEVEL_1, "insert iterations    : %d\n", stats->insert_iterations));
	DB((dbg, LEVEL_1, "infinite loops       : %d\n", stats->infinite_loops));
	DB((dbg, LEVEL_1, "fully redundant      : %d\n", stats->fully));
	DB((dbg, LEVEL_1, "partially redundant  : %d\n", stats->partially));
	DB((dbg, LEVEL_1, "  loads                : %d\n", stats->loads));
	DB((dbg, LEVEL_1, "  Divs/Mods            : %d\n", stats->divmods));
	DB((dbg, LEVEL_1, "  hoist high           : %d\n", stats->hoist_high));
	DB((dbg, LEVEL_1, "  first iteration      : %d\n", stats->first_iter_found));
}

#define set_stats(var, value) (var)=(value)
#define inc_stats(var)        ((var)+=1)

/* --------------------------------------------------------
 * Dump valuesets
 * --------------------------------------------------------
 */

/**
 * Dump a value set.
 *
 * @param set    the set to dump
 * @param txt    a text to describe the set
 * @param block  the owner block of the set
 */
static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
{
	ir_valueset_iterator_t iter;
	ir_node *value, *expr;
	int i;

	DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
	i = 0;
	foreach_valueset(set, value, expr, iter) {
		if ((i & 3) == 3)
			DB((dbg, LEVEL_2, "\n"));
		if (value != expr)
			DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
		else
			DB((dbg, LEVEL_2, " %+F,", expr));
		++i;
	}
	DB((dbg, LEVEL_2, "\n}\n"));
}

/**
 * Dump all exp_gen value sets.
 *
 * @param list  the list of block infos to retrieve the sets from
 */
static void dump_all_expgen_sets(block_info *list)
{
	block_info *block_info;

	for (block_info = list; block_info != NULL; block_info = block_info->next) {
		dump_value_set(block_info->exp_gen, "[Exp_gen]", block_info->block);
	}
}

#else

#define dump_all_expgen_sets(list) ((void)(list))
#define dump_value_set(set, txt, block)

#endif /* DEBUG_libfirm */

/* --------------------------------------------------------
 * GVN Functions
 * --------------------------------------------------------
 */

/**
 * Compares node collisions in valuetable.
 * Modified identities_cmp().
 */
static int compare_gvn_identities(const void *elt, const void *key)
{
	ir_node *a = (ir_node *)elt;
	ir_node *b = (ir_node *)key;
	int i, irn_arity_a;

	if (a == b) return 0;

	/* phi nodes kill predecessor values and are always different */
	if (is_Phi(a) || is_Phi(b))
		return 1;

	/* memops are not the same, even if we want to optimize them
	   we have to take the order in account */
	if (is_memop(a) || is_memop(b) ||
	    get_irn_mode(a) == mode_T ||
	    get_irn_mode(b) == mode_T) {
		/* Loads with the same predecessors are the same value;
		   this should only happen after phi translation. */
		if ((! is_Load(a) || ! is_Load(b)) && (! is_Store(a) || ! is_Store(b)))
			return 1;
	}

	if ((get_irn_op(a) != get_irn_op(b)) ||
	    (get_irn_mode(a) != get_irn_mode(b))) return 1;

	/* compare if a's in and b's in are of equal length */
	irn_arity_a = get_irn_arity(a);
	if (irn_arity_a != get_irn_arity(b))
		return 1;

	/* blocks are never the same */
	if (is_Block(a) || is_Block(b))
		return 1;

	/* should only be used with gcse enabled */
	assert(get_opt_global_cse());

	/* compare a->in[0..ins] with b->in[0..ins] */
	for (i = 0; i < irn_arity_a; ++i) {
		ir_node *pred_a = get_irn_n(a, i);
		ir_node *pred_b = get_irn_n(b, i);
		if (pred_a != pred_b) {
			if (!is_irn_cse_neutral(pred_a) || !is_irn_cse_neutral(pred_b))
				return 1;
		}
	}

	/*
	 * here, we already now that the nodes are identical except their
	 * attributes
	 */
	if (a->op->ops.node_cmp_attr)
		return a->op->ops.node_cmp_attr(a, b);

	return 0;
}

/**
 * Identify does a lookup in the GVN valuetable.
 * To be used when no new GVN values are to be created.
 *
 * @param e  a node representing an expression
 * @return a node representing the value
 */
static ir_node *identify(ir_node *irn)
{
	ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
	if (value)
		return value;
	/* irn represents a new value, so return the leader */
	return identify_remember(irn);
}

/**
 * remember() adds node irn to the GVN valuetable.
 * Identify_remember only identifies values of nodes with the
 * same predecessor nodes (not values). By creating a node from the predecessor
 * values/leaders, a true valuetree is built. Phis kill their predecessor value,
 * so no circular dependencies need to be resolved.
 *
 * TODO Improvement:
 *      Maybe this could be implemented with a custom node hash that takes
 *      phi nodes and true values (instead of predecessors) into account,
 *      resulting in value numbers.
 * TODO This unnecessarily also handles nodes like calls, which are never equal.
 *
 * @param irn  a node representing an expression
 * @return     the value of the expression
 */
static ir_node *remember(ir_node *irn)
{
	int       arity   = get_irn_arity(irn);
	int       changed = 0;
	ir_node **in      = XMALLOCN(ir_node *, arity);
	ir_node  *value;

	foreach_irn_in(irn, i, pred) {
		/* value and leader at the same time */
		ir_node *pred_value = identify(pred);

		/* phi will be translated anyway, so kill the predecessor values
		   this also prevents circular dependencies */
		if (is_Phi(pred)) {
			/* every phi represents its own value */
			in[i] = pred;
			continue;
		}

		/* predecessor is not its value representation/the leader */
		if (pred != pred_value)
			changed = 1;
		in[i] = pred_value;
	}

	if (changed && !is_memop(irn) && get_irn_mode(irn) != mode_X) {
		/* create representative for */
		ir_node *nn = new_similar_node(irn, get_nodes_block(irn), in);

#if OPTIMIZE_NODES
		/* TODO optimize_node() uses the valuetable and thus the custom
		   identify_cmp() and will fail trying. */
		environ->graph->value_table = environ->value_table;
		nn = optimize_node(nn);
		environ->graph->value_table = environ->gvnpre_values;
#endif

		/* now the value can be determined because the
		   predecessors are the leaders */
		value = identify_remember(nn);
	} else {
		value = identify_remember(irn);
	}
	free(in);

	DB((dbg, LEVEL_4, "Remember %+F as value %+F\n", irn, value));
	ir_nodehashmap_insert(&value_map, irn, value);

	return value;
}

/**
 * When the value map has been built we may lookup expressions
 * and remember them if new.
 */
static ir_node *identify_or_remember(ir_node *irn)
{
	ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
	if (value)
		return value;
	else
		return remember(irn);
}

/* --------------------------------------------------------
 * Block info
 * --------------------------------------------------------
 */

/**
 * Allocate block info for block block.
 *
 * @param block   the block
 * @param env     the environment
 */
static void alloc_block_info(ir_node *block, pre_env *env)
{
	block_info *info = OALLOC(&env->obst, block_info);

	set_irn_link(block, info);
	info->exp_gen    = ir_valueset_new(16);
	info->avail_out  = ir_valueset_new(16);
	info->antic_in   = ir_valueset_new(16);
	info->antic_done = ir_valueset_new(16);
	info->trans = XMALLOC(ir_nodehashmap_t);
	ir_nodehashmap_init(info->trans);

	info->new_set = NULL;
	info->avail   = NULL;
	info->block   = block;
	info->found   = 1;

	info->next = env->list;
	env->list  = info;
}

static void free_block_info(block_info *block_info)
{
	ir_valueset_del(block_info->exp_gen);
	ir_valueset_del(block_info->avail_out);
	ir_valueset_del(block_info->antic_in);
	if (block_info->trans) {
		ir_nodehashmap_destroy(block_info->trans);
		free(block_info->trans);
	}
	if (block_info->new_set)
		ir_valueset_del(block_info->new_set);
}

/**
 * Bottom up walker that ensures that every block gets a block info.
 *
 * @param irn   the node
 * @param ctx   the environment
 */
static void block_info_walker(ir_node *irn, void *ctx)
{
	if (is_Block(irn)) {
		pre_env *env = (pre_env*)ctx;
		alloc_block_info(irn, env);
	}
}

/**
 * Returns the block info of a block.
 */
static block_info *get_block_info(ir_node *block)
{
	return (block_info*)get_irn_link(block);
}

/* --------------------------------------------------------
 * Infinite loop analysis
 * --------------------------------------------------------
 */

/**
 * Walker to set block marks and loop links to 0.
 */
static void clear_block_mark_loop_link(ir_node *block, void *env)
{
	(void) env;

	if (is_Block(block)) {
		set_Block_mark(block, 0);
		set_loop_link(get_irn_loop(block), NULL);
	}
}

/**
 * Returns non-zero if block is part of real loop loop.
 */

static unsigned in_loop(ir_node *block, ir_loop *loop)
{
	ir_loop *l     = get_irn_loop(block);
	ir_loop *outer = get_irg_loop(environ->graph);

	while (l != loop) {
		/* loop tree root is not a loop */
		if (l == NULL || l == outer)
			return 0;
		l = get_loop_outer_loop(l);
	}
	return 1;
}

/**
 * Returns the outermost real loop of loop.
 */
static ir_loop *get_loop_outermost(ir_loop *loop)
{
	ir_loop *outer = get_irg_loop(environ->graph);
	ir_loop *l     = loop;
	ir_loop *last  = NULL;

	while(l != outer) {
		last = l;
		l = get_loop_outer_loop(l);
	}
	return last;
}

/**
 * Topologic bottom-up walker sets links of infinite loops to non-zero.
 * Block marks are used to flag blocks reachable (from end) on the one hand,
 * on the other hand they are set if the block is not part of an infinite loop.
 */
static void infinite_loop_walker(ir_node *block, void *env)
{
	int arity;
	int i;
	(void) env;

	if (! is_Block(block))
		return;

	/* start block has no predecessors */
	if (block == environ->start_block)
		return;

	arity = get_irn_arity(block);

	/* block not part of a real loop: no infinite loop */
	if (get_irn_loop(block) == get_irg_loop(environ->graph))
		set_Block_mark(block, 1);

	if (get_Block_mark(block)) {
		/* reachable block: mark all cf predecessors */
		for (i = 0; i < arity; ++i) {
			ir_node *pred = get_Block_cfgpred_block(block, i);
			if (pred == NULL)
				continue;
			set_Block_mark(pred, 1);
		}
	} else {
		/* We are in a real loop and see an unreachable block. */
		ir_loop *outermost_loop = get_loop_outermost(get_irn_loop(block));

		/* flag loop as infinite */
		set_loop_link(outermost_loop, outermost_loop);
		DEBUG_ONLY(inc_stats(gvnpre_stats->infinite_loops);)

		/* The cf predecessors are unreachable, but can never be part of
		   an infinite loop, because we just reached them. So we set the
		   blockmark to prevent triggering the infinite loop detection. */

		/* passing information to the cf predecessors */
		for (i = 0; i < arity; ++i) {
			ir_node *pred = get_Block_cfgpred_block(block, i);
			if (pred == NULL)
				continue;

			/* If our cf predecessor is in the same endless loop,
			   it is also unreachable. */
			if (in_loop(pred, outermost_loop)) {
				set_Block_mark(pred, 0);
			} else {
				/* When we leave the unreachable loop, we artificially
				   declare the cf predecessor reachable. */
				set_Block_mark(pred, 1);
			}
		}
	}
}

/**
 * Sets loop links of outermost infinite loops to non-zero.
 */
static void analyse_loops(ir_graph *irg)
{
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);

	/* reset block mark and loop links */
	irg_walk_blkwise_graph(irg, clear_block_mark_loop_link, NULL, NULL);

	/* mark end block reachable */
	set_Block_mark(get_irg_end_block(irg), 1);
	irg_walk_blkwise_graph(irg, infinite_loop_walker, NULL, NULL);

	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
}

#if IGNORE_INF_LOOPS || NO_INF_LOOPS
/**
 * Returns non-zero if block is part of an infinite loop.
 */
static unsigned is_in_infinite_loop(ir_node *block)
{
	ir_loop *loop;

	assert(is_Block(block));
	loop = get_irn_loop(block);
	assert(loop);

	loop = get_loop_outermost(loop);
	if (loop)
		return (get_loop_link(loop) != NULL);
	else
		return 0;
}
#endif

/* --------------------------------------------------------
 * GVN-PRE Exp_gen
 * --------------------------------------------------------
 */

/**
 * Returns non-zero if a node is movable and a possible candidate for PRE.
 */
static unsigned is_nice_value(ir_node *n)
{
	ir_mode *mode = get_irn_mode(n);

	if (is_Phi(n))
		return 1;

#if LOADS || DIVMODS
	if (is_Proj(n) && mode != mode_X && mode != mode_T)
		return 1;
#else
	if (is_Proj(n))
		return 0;
#endif

#if LOADS
	if (is_Load(n))
		return get_Load_volatility(n) == volatility_non_volatile;
	if (is_Store(n))
		return get_Store_volatility(n) == volatility_non_volatile;
#endif

	if (get_irn_pinned(n) == op_pin_state_pinned)
		return 0;

	if (! mode_is_data(mode)) {
		if (! is_Div(n) && ! is_Mod(n))
			return 0;
	}
	return 1;
}

/**
 * Checks if a node n is clean in block block for exp_gen.
 *
 * @param n      the node
 * @param block  the block
 * @return non-zero value for clean node
 */
static unsigned is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *valueset)
{
	if (is_Phi(n))
		return 1;

	if (! is_nice_value(n))
		return 0;

#if LOADS
	/* filter loads with no phi predecessor from antic_in */
	if (is_Load(n) && ! is_Phi(get_Load_mem(n)))
		return 0;
	if (is_Store(n) && ! is_Phi(get_Store_mem(n)))
		return 0;
#endif

#if DIVMODS
	if (is_Div(n)) {
		ir_node *mem = get_Div_mem(n);

		mem = skip_Pin(mem);

		if (! is_Phi(mem) && ! is_NoMem(mem))
			return 0;
	}

	if (is_Mod(n) && ! is_Phi(get_Mod_mem(n)))
		return 0;
#endif

	foreach_irn_in(n, i, pred) {
		if (is_Phi(pred))
			continue;

		/* we only handle current block */
		if (get_nodes_block(pred) != block)
			continue;

		if (! is_nice_value(pred))
			return 0;

		ir_node *const value = identify(pred);
		if (! ir_valueset_lookup(valueset, value))
			return 0;
	}
	return 1;
}

/**
 * Topological walker puts nodes in top-down topological order into exp_gen set.
 * Assumed to walk blockwise and nodewise topologically top-down.
 *
 * @param irn    the node
 * @param ctx    the environment
 */
static void topo_walker(ir_node *irn, void *ctx)
{
	ir_node    *block;
	block_info *info;
	ir_node    *value;
	(void) ctx;

	if (is_Block(irn))
		return;

#if OPTIMIZE_NODES
	environ->graph->value_table = environ->value_table;
	identify_remember(irn);
	environ->graph->value_table = environ->gvnpre_values;
#endif

	/* GVN step: remember the value. */
	value = remember(irn);

	if (is_irn_constlike(irn))
		return;

	block = get_nodes_block(irn);
	info  = get_block_info(block);

	if (get_irn_mode(irn) != mode_X)
		ir_valueset_insert(info->avail_out, value, irn);

	/* values that are not in antic_in also dont't need to be in any other set */

	if (! is_nice_value(irn))
		return;

	if (is_clean_in_block(irn, block, info->exp_gen)) {
		DB((dbg, LEVEL_3, "%+F clean in block %+F\n", irn, block));

		ir_valueset_insert(info->exp_gen, value, irn);
	}
}

/* --------------------------------------------------------
 * GVN-PRE Antic_in
 * --------------------------------------------------------
 */

/**
 * Gets result of nodes phi translation into block.
 *
 * @param node   the node
 * @param block  the target block
 *
 * @return a phi translation of node node into block block or NULL
 */
static ir_node *get_translated(ir_node *block, ir_node *node)
{
	if (is_irn_constlike(node))
		return node;

	return ir_nodehashmap_get(ir_node, get_block_info(block)->trans, node);
}

/**
 * Saves result of phi translation of node into predecessor
 * at pos of block succ.
 *
 * @param node   the node
 * @param succ   the successor of the translation target block
 * @param pos    the position of the predecessor block
 * @param trans  the translation result
 *
 */
static void set_translated(ir_nodehashmap_t *map, ir_node *node, ir_node *trans)
{
	if (is_irn_constlike(node))
		return;
	/* insert or replace */
	ir_nodehashmap_insert(map, node, trans);
}

/**
 * Translates an expression above a Phi.
 *
 * @param node        the node
 * @param block       the block the node is translated into
 * @param pos         the input number of the destination block
 *
 * @return a node representing the translated value
 */
static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *leaderset)
{
	int       arity;
	ir_node **in;
	ir_node  *pred_block = get_Block_cfgpred_block(block, pos);
	unsigned  needed;

	if (is_Phi(node)) {
		if (get_nodes_block(node) == block)
			return get_Phi_pred(node, pos);
		/* this phi does not need translation */
		return node;
	}
	arity = get_irn_arity(node);

	needed = 0;
	in = ALLOCANZ(ir_node *, arity);

	/* A value has several representatives. The anti leader is chosen to be
	   the main representative. If we access a node as representative of a
	   value we always use the anti leader. The anti leader can be found by
	   antic_in(identify(node)). */
	foreach_irn_in(node, i, pred) {
		ir_node *value  = identify(pred);
		/* get leader for pred to lookup its translated value */
		ir_node *leader = ir_valueset_lookup(leaderset, value);
		ir_node *pred_trans;
		ir_node *new_pred;

		if (! leader)
			leader = pred;

		/* we cannot find this value in antic_in, because the value
		   has (possibly) changed! */
		pred_trans  = get_translated(pred_block, leader);


#if DIVMODS
		if (is_Div(node)) {
			ir_node *mem = get_Div_mem(node);

			mem = skip_Pin(mem);

			if (! is_Phi(mem))
				pred_trans = get_Div_mem(node);
		}
#endif

		DB((dbg, LEVEL_3, "trans %+F of %+F is  %+F\n", leader, pred_block, pred_trans));
		if (pred_trans == NULL) {
			new_pred = pred;
		} else {
			new_pred = pred_trans;

			/* loads: Predecessor is a memory phi, which translated yields a proj or
			   another phi. In case of projection and a load predecessor,
			   skip them and use the loads memory. */
			if (is_Proj(pred_trans) && get_irn_mode(pred_trans) == mode_M) {
#if LOADS || DIVMODS
				ir_node *loadstore = get_Proj_pred(pred_trans);
				/* If we do not translate this node, we will get its value wrong. */
				needed |= 1;

				if (is_Load(loadstore)) {
					/* Put new load under the adjacent loads memory edge
					   such that GVN may compare them. */
					new_pred = get_Load_mem(loadstore);
				} else if (is_Store(loadstore)) {
					new_pred = get_Store_mem(loadstore);
				}
#endif
			} else {
				/* predecessor value changed, so translation is needed */
				if (identify(new_pred) != identify(pred))
					needed |= 1;
			}
		}

		DB((dbg, LEVEL_4, "in %+F\n", new_pred));
		in[i] = new_pred;
	}

	if (! needed)
		return node;

	DB((dbg, LEVEL_3, "Translate\n"));

	if (is_Proj(node))
		pred_block = get_nodes_block(in[0]);

	/* copy node to represent the new value.
	   We do not translate nodes that do not need translation,
	   so we use the newly created nodes as value representatives only.
	   Their block is not important, because we create new ones during
	   the insert node phase. */
	ir_node *const nn = new_similar_node(node, pred_block, in);
	/* Optimizing nn here is tempting but might be against the GVN-PRE algorithm
	   because it already uses availability. */

	DB((dbg, LEVEL_3, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
	return nn;
}

/**
 * Block-walker, computes Antic_in(block).
 * Builds a value tree out of the graph by translating values
 * over phi nodes.
 *
 * @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;
	ir_node                *value;
	ir_node                *expr;
	size_t                  size;
	ir_valueset_iterator_t  iter;
	int                     n_succ;

	/* filter blocks from topological walker */
	if (! is_Block(block))
		return;

	/* the end block has no successor */
	if (block == env->end_block)
		return;

	info = get_block_info(block);
	/* track changes */
	size = ir_valueset_size(info->antic_in);
	n_succ = get_Block_n_cfg_outs(block);

	/* add exp_gen */
	if (env->first_iter) {
#if IGNORE_INF_LOOPS
		/* keep antic_in of infinite loops empty */
		if (! is_in_infinite_loop(block)) {
			foreach_valueset(info->exp_gen, value, expr, iter) {
				ir_valueset_insert(info->antic_in, value, expr);
			}
		}
#else
		foreach_valueset(info->exp_gen, value, expr, iter) {
			ir_valueset_insert(info->antic_in, value, expr);
		}
#endif
	}

	/* successor might have phi nodes */
	if (n_succ == 1 && get_irn_arity(get_Block_cfg_out(block, 0)) > 1) {
		succ      = get_Block_cfg_out(block, 0);
		int pos   = get_Block_cfgpred_pos(succ, block);
		succ_info = get_block_info(succ);

		/* initialize translated set */
		if (env->first_iter) {
			info->trans = XMALLOC(ir_nodehashmap_t);
			ir_nodehashmap_init(info->trans);
		}

		foreach_valueset(succ_info->antic_in, value, expr, iter) {
			ir_node *trans = get_translated(block, expr);
			ir_node *trans_value;
			ir_node *represent;

			if (trans == NULL)
				trans = phi_translate(expr, succ, pos, get_block_info(succ)->antic_in);

			/* create new value if necessary */
			trans_value = identify_or_remember(trans);

			DB((dbg, LEVEL_3, "Translate %+F %+F to %d = %+F (%+F)\n", expr, succ, pos, trans, trans_value));

			/* On value change (phi present) we need the translated node
			   to represent the new value for possible further translation. */
			if (value != trans_value)
				represent = trans;
			else
				represent = expr;

			if (is_clean_in_block(expr, block, info->antic_in)) {
#if NO_INF_LOOPS
				/* Prevent information flow over the backedge of endless loops. */
				if (env->iteration <= 2 || (is_backedge(succ, pos) && !is_in_infinite_loop(succ))) {
					ir_valueset_replace(info->antic_in, trans_value, represent);
				}
#else
				ir_valueset_replace(info->antic_in, trans_value, represent);
#endif
			}
			set_translated(info->trans, expr, represent);
		}

	} else if (n_succ > 1) {
		int         i;
		ir_node    *common     = NULL;
		ir_node    *succ0      = get_Block_cfg_out(block, 0);
		block_info *succ0_info = get_block_info(succ0);

		/* disjoint of antic_ins */
		foreach_valueset(succ0_info->antic_in, value, expr, iter) {
			/* iterate over remaining successors */
			for (i = 1; i < n_succ; ++i) {
				ir_node    *succ      = get_Block_cfg_out(block, i);
				block_info *succ_info = get_block_info(succ);

				/* value in antic_in? */
				common = ir_valueset_lookup(succ_info->antic_in, value);
				if (common == NULL)
					break;
			}

			if (common && is_clean_in_block(expr, block, info->antic_in))
				ir_valueset_replace(info