#include "valueset.h"
#include "irnodemap.h"
#include "irnodeset.h"
+#include "iredges.h"
#include "debug.h"
#include "irgraph_t.h"
*/
static ir_node *add(ir_node *e, ir_node *v)
{
+ if (is_Proj(v)) {
+ ir_node *pred = get_Proj_pred(v);
+ ir_node *v_pred = identify_remember(value_table, pred);
+
+ if (v_pred != pred) {
+ /* must create a new value here */
+ v = new_r_Proj(current_ir_graph, get_nodes_block(v_pred), v_pred, get_irn_mode(v), get_Proj_proj(v));
+ }
+ }
v = identify_remember(value_table, v);
ir_nodemap_insert(&value_map, e, v);
return v;
return NULL;
}
-/**
- * Add or replace a value in a set by an node computing the same
- * value in a dominator block.
- */
-static ir_node *lookup_or_add(ir_node *e)
-{
- ir_node *x = lookup(e);
-
- if (x == NULL) {
- x = add(e, e);
- }
- return x;
-}
-
-
/**
* Return the block info of a block
*/
while (is_Proj(n))
n = get_Proj_pred(n);
- mode = get_irn_mode(n);
- /*
- * FIXME: For now, we cannot handle Div/even if it's movable.
- * That should be fixed.
- */
- if (!mode_is_data(mode))
+ if (get_irn_pinned(n) == op_pin_state_pinned)
return 0;
- return (get_irn_pinned(n) != op_pin_state_pinned);
+ mode = get_irn_mode(n);
+ if (!mode_is_data(mode)) {
+ if (! is_Div(n) && ! is_Mod(n) && ! is_DivMod(n))
+ return 0;
+ if (! is_NoMem(get_fragile_op_mem(n)))
+ return 0;
+ }
+ return 1;
} /* is_nice_value */
#ifdef DEBUG_libfirm
-/**
- * Dump a ir_nodeset_t set.
- */
-static void dump_node_set(ir_nodeset_t *set, char *txt, ir_node *block)
-{
- ir_nodeset_iterator_t iter;
- ir_node *n;
- int i;
-
- DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
- i = 0;
- foreach_ir_nodeset(set, n, iter) {
- if ((i & 3) == 3)
- DB((dbg, LEVEL_2, "\n"));
- DB((dbg, LEVEL_2, " %+F,", n));
- ++i;
- }
- DB((dbg, LEVEL_2, "\n}\n"));
-} /* dump_node_set */
-
/**
* Dump a value set.
*/
DB((dbg, LEVEL_2, "\n}\n"));
} /* dump_value_set */
-
#else
-#define dump_node_set(set, txt, block)
#define dump_value_set(set, txt, block)
#endif /* DEBUG_libfirm */
if (! is_nice_value(irn) || is_irn_constlike(irn))
return;
+ /* Do not put mode_T nodes info the sets, or PhiT will be created
+ (which are not allowed in Firm). Instead, put the Proj's here only. */
+ if (get_irn_mode(irn) == mode_T)
+ return;
+
/* place this node into the set of possible nodes of its block */
block = get_nodes_block(irn);
info = get_block_info(block);
*/
static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
{
- ir_node *nn, *res;
+ ir_node *nn;
int i, arity;
struct obstack *old;
/* check if the node has at least one Phi predecessor */
for (i = 0; i < arity; ++i) {
ir_node *pred = get_irn_intra_n(node, i);
- ir_node *pred_bl = get_nodes_block(pred);
ir_node *leader = lookup(pred);
leader = leader != NULL ? leader : pred;
set_nodes_block(nn, get_nodes_block(node));
for (i = 0; i < arity; ++i) {
ir_node *pred = get_irn_intra_n(node, i);
- ir_node *pred_bl = get_irn_intra_n(pred, -1);
ir_node *leader = lookup(pred);
leader = leader != NULL ? leader : pred;
/* the end block has no successor */
if (block != env->end_block) {
- int n_succ = get_Block_n_cfg_outs(block);
+ int n_succ;
+ /*
+ * This step puts all generated expression from the current
+ * current block into Antic_in.
+ * It is enough to do this in the first iteration only, because
+ * the set info->exp_gen is not changed anymore.
+ */
+ if (env->first_iter) {
+ foreach_valueset(info->exp_gen, value, expr, iter) {
+ ir_valueset_insert(info->antic_in, value, expr);
+ }
+ }
+
+ n_succ = get_Block_n_cfg_outs(block);
if (n_succ == 1) {
int i, pos = -1;
assert(n_succ > 1);
- /*
- * This step puts all generated expression from the current
- * current block into Antic_in.
- * It is enough to do this in the first iteration only, because
- * the set info->exp_gen is not changed anymore.
- */
- if (env->first_iter) {
- foreach_valueset(info->exp_gen, value, expr, iter) {
- ir_valueset_insert(info->antic_in, value, expr);
- }
- }
-
/* 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
ir_node *e_prime = pred_info->avail;
ir_node *nn;
if (!is_Phi(e_prime)) {
+ ir_node *proj_pred = NULL;
+ if (is_Proj(e_prime)) {
+ ir_node *pred = get_Proj_pred(e_prime);
+ mode = get_irn_mode(pred);
+ nn = new_ir_node(
+ get_irn_dbg_info(pred),
+ current_ir_graph, pred_blk,
+ get_irn_op(pred),
+ mode,
+ get_irn_arity(pred),
+ get_irn_in(pred) + 1);
+ copy_node_attr(pred, nn);
+
+ DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
+ proj_pred = nn;
+ }
mode = get_irn_mode(e_prime);
nn = new_ir_node(
get_irn_dbg_info(e_prime),
get_irn_arity(e_prime),
get_irn_in(e_prime) + 1);
copy_node_attr(e_prime, nn);
+ if (proj_pred != NULL) {
+ set_Proj_pred(nn, proj_pred);
+ }
DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
ir_valueset_insert(pred_info->avail_out, add(nn, lookup(expr)), nn);
ir_valueset_insert(curr_info->new_set, value, phi);
free(in);
DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, expr));
+ ir_valueset_remove_iterator(curr_info->antic_in, &iter);
env->changes |= 1;
} /* if */
} /* node_set_foreach */
*/
void do_gvn_pre(ir_graph *irg)
{
- struct obstack obst;
- pre_env a_env;
+ struct obstack obst;
+ pre_env a_env;
optimization_state_t state;
- block_info *bl_info;
- unsigned antic_iter, insert_iter;
+ block_info *bl_info;
+ unsigned antic_iter, insert_iter;
+ ir_node *value, *expr;
/* register a debug mask */
FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
- firm_dbg_set_mask(dbg, SET_LEVEL_2);
/* edges will crash if enabled due to our allocate on other obstack trick */
edges_deactivate(irg);
/* allocate block info for all blocks */
irg_walk_blkwise_graph(irg, NULL, topo_walker, &a_env);
+ /* clean the exp_gen set. Doing this here saves the cleanup in the iteration. */
+ for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
+ ir_valueset_iterator_t iter;
+
+ foreach_valueset(bl_info->exp_gen, value, expr, iter) {
+ if (!is_clean(expr))
+ ir_valueset_remove_iterator(bl_info->exp_gen, &iter);
+ }
+ }
+
/* compute the available value sets for all blocks */
dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
do {
DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
a_env.changes = 0;
- //irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
a_env.first_iter = 0;
DB((dbg, LEVEL_1, "------------------------\n"));
set_irg_loopinfo_inconsistent(irg);
}
- dump_ir_block_graph(irg, "-gvn");
} /* do_gvn_pre */