- pre_env *env = ctx;
- value_entry *entry;
- ir_node *e, *idom, *first_s, *worklist;
- block_info *curr_info, *idom_info;
- int pos, arity = get_irn_intra_arity(block);
- int all_same, by_some, updated;
-
- /* ensure that even the start block has a new_set */
- curr_info = get_block_info(block);
- if (curr_info->new_set)
- del_value_set(curr_info->new_set);
- curr_info->new_set = new_value_set();
-
- if (block == env->start_block)
- return;
-
- idom = get_Block_idom(block);
- idom_info = get_block_info(idom);
-
- /* update the new_sets */
- updated = 0;
- dump_value_set(idom_info->new_set, "[New Set]", idom);
- value_set_foreach(entry, idom_info->new_set) {
- updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value);
- }
- if (updated)
- dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block);
-
- if (arity <= 1)
- return;
-
- /* convert the set into a list. This allows the removal of
- * elements from the set */
- worklist = NULL;
- node_set_foreach(e, curr_info->antic_in) {
- set_irn_link(e, worklist);
- worklist = e;
- }
-
- for (e = worklist; e != NULL; e = get_irn_link(e)) {
- ir_mode *mode;
-
- /* If the value was already computed in the dominator, then
- it is totally redundant. Hence we have nothing to insert. */
- if (value_lookup(idom_info->avail_out, e)) {
-// DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
- continue;
- }
-
- by_some = 0;
- all_same = 1;
- first_s = NULL;
- mode = NULL;
-
- /* for all predecessor blocks */
- for (pos = 0; pos < arity; ++pos) {
- block_info *pred_info;
- ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
- ir_node *e_prime, *v_prime, *e_dprime;
-
- /* ignore bad blocks. */
- if (is_Bad(pred_blk))
- continue;
-
- e_prime = phi_translate(e, block, pos, env);
- v_prime = e_prime;
-
- pred_info = get_block_info(pred_blk);
- e_dprime = value_lookup(pred_info->avail_out, v_prime);
-
- if (e_dprime == NULL) {
- all_same = 0;
- pred_info->avail = e_prime;
- pred_info->not_found = 1;
- }
- else {
- mode = get_irn_mode(e_dprime);
- e_dprime = e_dprime;
- pred_info->avail = e_dprime;
- pred_info->not_found = 0;
- by_some = 1;
- if (first_s == NULL)
- first_s = e_dprime;
- else if (first_s != e_dprime)
- all_same = 0;
-
- DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk));
- } /* if */
- } /* for */
-
- /* If it's not the same value already existing along every predecessor, and
- it's defined by some predecessor, it is partially redundant. */
- if (! all_same && by_some) {
- 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 */
+ pre_env *env = (pre_env*)ctx;
+ int arity = get_irn_arity(block);
+ ir_node *value;
+ ir_node *expr;
+ block_info *info;
+ ir_node *idom;
+ int pos;
+ ir_valueset_iterator_t iter;
+
+ /* only blocks */
+ if (! is_Block(block))
+ return;
+
+ /* ensure that even the start block has a new_set */
+ info = get_block_info(block);
+ if (info->new_set)
+ ir_valueset_del(info->new_set);
+ info->new_set = ir_valueset_new(16);
+
+ if (block == env->start_block)
+ return;
+
+ DB((dbg, LEVEL_2, "Insert operation of %+F\n", block));
+
+ idom = get_Block_idom(block);
+ update_new_set(block, idom);
+
+ /* process only path joining blocks */
+ if (arity < 2) {
+ return;
+ }
+
+ /* This is the main reason antic_in is preverred over antic_out;
+ we may iterate over every anticipated value first and not
+ over the predecessor blocks. */
+ foreach_valueset(info->antic_in, value, expr, iter) {
+ ir_mode *mode;
+ ir_node *phi;
+ ir_node **phi_in;
+
+ /* already done? */
+ if (ir_valueset_lookup(info->antic_done, value))
+ continue;
+
+ /* filter phi nodes from antic_in */
+ if (is_Phi(expr))
+ continue;
+
+ DB((dbg, LEVEL_2, "Insert for %+F (value %+F) in %+F\n", expr, value, block));
+
+ /* A value computed in the dominator is totally redundant.
+ Hence we have nothing to insert. */
+ if (ir_valueset_lookup(get_block_info(idom)->avail_out, value)) {
+ DB((dbg, LEVEL_2, "Fully redundant expr %+F value %+F\n", expr, value));
+ DEBUG_ONLY(inc_stats(gvnpre_stats->fully);)
+
+ ir_valueset_insert(info->antic_done, value, expr);
+ continue;
+ }
+
+ if (is_hoisting_greedy(expr, block)) {
+ DB((dbg, LEVEL_2, "greedy\n"));
+ continue;
+ }
+
+ mode = is_partially_redundant(block, expr, value);
+ if (mode == NULL)
+ continue;
+
+#if LOADS || DIVMODS
+ /* save old mode_M phis to remove keepalive edges later */
+ if (is_memop(expr)) {
+ ir_node *mem = get_memop_mem(expr);
+ if (is_Phi(mem) && get_nodes_block(mem) == get_nodes_block(expr)) {
+ ir_nodeset_insert(env->keeps, mem);
+ }
+ }
+#endif
+
+#ifdef DEBUG_libfirm
+ if (! is_Proj(expr)) {
+ if (env->first_iter)
+ inc_stats(gvnpre_stats->first_iter_found);
+ inc_stats(gvnpre_stats->partially);
+ }
+ if (is_Load(expr) || is_Store(expr))
+ inc_stats(gvnpre_stats->loads);
+ else if (is_Div(expr) || is_Mod(expr))
+ inc_stats(gvnpre_stats->divmods);
+#endif
+
+ phi_in = XMALLOCN(ir_node *, arity);
+
+ /* for each predecessor block */
+ for (pos = 0; pos < arity; ++pos) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, pos);
+ block_info *pred_info;
+
+ pred_info = get_block_info(pred_block);
+
+ if (! pred_info->found) {
+ int i;
+ int node_arity = get_irn_arity(expr);
+ ir_node **in = XMALLOCNZ(ir_node *, node_arity);
+ ir_node *trans;
+ ir_node *new_value, *new_value2;
+ ir_node *target_block = pred_block;
+
+ for (i = 0; i < node_arity; ++i) {
+ ir_node *pred = get_irn_n(expr, i);
+ ir_node *value = identify(pred);
+ ir_node *leader;
+ ir_node *trans;
+ ir_node *trans_val;
+ ir_node *avail;
+
+ /* transform knowledge over the predecessor from
+ anti-leader world into leader world. */
+
+ DB((dbg, LEVEL_3, "pred %+F\n", pred));
+ value = identify(pred);
+
+ /* get leader for pred to lookup its translated value */
+ leader = ir_valueset_lookup(info->antic_in, value);
+ if (! leader)
+ leader = pred;
+ DB((dbg, LEVEL_3, "lead %+F\n", leader));
+
+ trans = get_translated(pred_block, leader);
+ if (!trans)
+ trans = pred;
+ DB((dbg, LEVEL_3, "trans %+F\n", trans));
+
+ /* in case of phi, we are done */
+ if (is_Phi(pred) && get_nodes_block(pred) == block) {
+ in[i] = trans;
+ continue;
+ }
+
+ trans_val = identify(trans);
+ DB((dbg, LEVEL_3, "value %+F\n", trans_val));
+
+ /* constants are always available but not in avail set */
+ if (is_irn_constlike(trans_val)) {
+ in[i] = trans;
+ continue;
+ }
+
+ /* use the leader
+ In case of loads we need to make sure the hoisted
+ loads are found despite their unique value. */
+ avail = ir_valueset_lookup(pred_info->avail_out, trans_val);
+ DB((dbg, LEVEL_3, "avail %+F\n", avail));
+
+ assert(avail && "predecessor has to be available");
+ in[i] = avail;
+ }
+
+ if (is_Proj(expr))
+ target_block = get_nodes_block(in[0]);
+
+ /* Copy node to represent the new value.
+ We use translated nodes as value representatives only.
+ They have anti leaders as predecessors, not leaders!
+ So we have to create a new node using leaders. */
+ trans = new_ir_node(
+ get_irn_dbg_info(expr),
+ environ->graph,
+ target_block,
+ get_irn_op(expr),
+ get_irn_mode(expr),
+ get_irn_arity(expr),
+ in);
+ free(in);
+ /* We need the attribute copy here, because the Hash value of a
+ node might depend on it. */
+ copy_node_attr(environ->graph, expr, trans);
+
+ /* value is now available in target block through trans
+ insert (not replace) because it has not been available */
+ new_value = identify_or_remember(trans);
+ ir_valueset_insert(pred_info->avail_out, new_value, trans);
+ DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value));
+
+ new_value2 = identify(get_translated(pred_block, expr));
+ ir_valueset_insert(pred_info->avail_out, new_value2, trans);
+ DB((dbg, LEVEL_4, "avail%+F+= trans %+F(%+F)\n", pred_block, trans, new_value2));
+
+ DB((dbg, LEVEL_3, "Use new %+F in %+F because %+F(%+F) not available\n", trans, pred_block, expr, value));
+
+ phi_in[pos] = trans;
+ } else {
+ /* value available */
+ phi_in[pos] = pred_info->avail;
+ }
+ DB((dbg, LEVEL_3, "phi_in %+F\n", phi_in[pos]));
+ }
+
+ /* We do not connect tuples as they will be connected automatically
+ by the corresponding projections. */
+ if (get_irn_mode(expr) != mode_T) {
+
+ phi = new_r_Phi(block, arity, phi_in, mode);
+ DB((dbg, LEVEL_3, "New %+F for redundant %+F created\n", phi, expr));
+
+ /* This value is now available through the new phi.
+ insert || replace in avail_out */
+ ir_valueset_replace(info->avail_out, value, phi);
+ ir_valueset_insert(info->new_set, value, phi);
+ }
+ free(phi_in);
+
+ /* already optimized this value in this block */
+ ir_valueset_insert(info->antic_done, value, expr);
+ env->changes |= 1;
+ }
+}
+
+#if HOIST_HIGH
+static void update_new_set_walker(ir_node *block, void *ctx)
+{
+ pre_env *env = (pre_env*)ctx;
+
+ if (! is_Block(block))
+ return;
+ if (block == env->start_block)
+ return;
+
+ update_new_set(block, get_Block_idom(block));
+}