+ 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 i;
+ int arity;
+ ir_node **in;
+ ir_node *pred_block = get_Block_cfgpred_block(block, pos);
+ ir_node *nn;
+ 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)). */
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_irn_n(node, i);
+ 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. */
+ nn = new_ir_node(
+ get_irn_dbg_info(node),
+ environ->graph,
+ pred_block,
+ get_irn_op(node),
+ get_irn_mode(node),
+ arity,
+ in);
+ /* We need the attribute copy here, because the Hash value of a
+ node might depend on it. */
+ copy_node_attr(environ->graph, node, nn);
+ /* 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->antic_in, value, expr);
+ }
+ }
+
+
+ DEBUG_ONLY(dump_value_set(info->antic_in, "Antic_in", block);)
+
+ if (size != ir_valueset_size(info->antic_in))
+ env->changes |= 1;
+}
+
+/* --------------------------------------------------------
+ * Main algorithm Avail_out
+ * --------------------------------------------------------
+ */