- pre_env *env = ctx;
- block_info *succ_info;
- block_info *info = get_block_info(block);
- ir_node *succ;
- int size;
-
- /* no need for computations in start block */
- if (block == env->start_block)
- return;
-
- size = pset_count(info->antic_in);
-
- /* the root has no dominator */
- if (block != env->end_block) {
- int n_succ = get_Block_n_cfg_outs(block);
-
- if (n_succ == 1) {
- ir_node *node;
- int i, pos = -1;
- pset *nodes = new_value_set();
-
- value_union(nodes, info->nodes);
-
- /* find blocks position in succ's block predecessors */
- succ = get_Block_cfg_out(block, 0);
- for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
- if (get_Block_cfgpred_block(succ, i) == block) {
- pos = i;
- break;
- }
- }
- assert(pos >= 0);
-
- succ_info = get_block_info(succ);
- for (node = pset_first(succ_info->antic_in);
- node;
- node = pset_next(succ_info->antic_in)) {
- ir_node *trans = phi_translate(node, succ, pos, env);
-
- value_add(nodes, trans);
-
- /* add all predecessors of node */
- for (i = get_irn_arity(node) - 1; i >= 0; --i) {
- ir_node *pred = get_irn_n(node, i);
- ir_node *trans = phi_translate(pred, succ, pos, env);
-
- if (is_nice_value(trans))
- value_add(nodes, trans);
- }
- }
- /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
- value_union(info->antic_in, nodes);
- del_value_set(nodes);
- }
- else {
- ir_node *n, *succ0;
- block_info *succ0_info;
- int i;
-
- assert(n_succ > 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);
- for (n = pset_first(succ0_info->antic_in);
- n;
- n = pset_next(succ0_info->antic_in)) {
- /* 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 (lookup(succ_info->antic_in, n) == NULL)
- break;
- }
- if (i >= n_succ) {
- /* we found a node that is common in all Antic_in(succ(b)),
- put it in Antic_in(b) */
- value_add(info->antic_in, n);
- }
- }
- /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
- value_union(info->antic_in, info->nodes);
- }
- }
-
- if (size != pset_count(info->antic_in)) {
- /* the Antic_in set has changed */
- env->changes |= 1;
- dump_set(info->antic_in, "Antic_in", block);
- }
-} /* compute_antic */
-
-/**
- * allocate a block info
- */
-static void alloc_blk_info(ir_node *block, void *ctx)
-{
- int i;
- pre_env *env = ctx;
- block_info *info = obstack_alloc(env->obst, sizeof(block_info));
-
- set_irn_link(block, info);
- info->nodes = new_value_set();
- info->antic_in = new_value_set();
- info->avail_out = new_value_set();
- info->avail = NULL;
- info->not_found = 0;
- info->new_set = NULL;
- info->next = env->list;
- env->list = info->next;
-
- /* fill the nodes set, we will need it later */
- for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
- ir_node *n = get_irn_out(block, i);
-
- /* clear the link field here, we need it later */
- set_irn_link(n, NULL);
-
- /* we cannot optimize pinned nodes, so do not remember them */
- if (is_nice_value(n))
- value_add(info->nodes, n);
- else if (is_Phi(n) && get_irn_mode(n) != mode_M) {
- /*
- * Phis are "temporaries" and must be handled special:
- * They are avail, but are not in Antic_in
- */
- value_add(info->avail_out, n);
- }
- }
-}
-
-/**
- * Compare two nodes for equal operands.
- */
-static int operands_equal(ir_node *n1, ir_node *n2)
-{
- int i, arity;
-
- if (n1 == n2)
- return 1;
-
- arity = get_irn_arity(n1);
- assert(n1->op == n2->op && arity == get_irn_arity(n2));
- for (i = 0; i < arity; ++i)
- if (! operands_equal(get_irn_n(n1, i), get_irn_n(n2, i)))
- return 0;
- return 1;
-}
-
-/**
- * Replace a value in a set by an node computing the same
- * value in a dominator block.
+ 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
+ * --------------------------------------------------------
+ */
+
+/**
+ * Computes Avail_out(block):
+ *
+ * Avail_in(block) = Avail_out(dom(block))
+ * Avail_out(block) = Avail_in(block) \/ Nodes(block)
+ *
+ * Precondition:
+ * This function must be called in the top-down topological order:
+ * Then it computes Leader(Nodes(block)) instead of Nodes(block) !
+ *
+ * @param block the block
+ * @param ctx walker context
+ */
+static void compute_avail_top_down(ir_node *block, void *ctx)
+{
+ pre_env *env = (pre_env*)ctx;
+ block_info *info;
+
+ if (block == env->end_block)
+ return;
+
+ info = get_block_info(block);
+
+ /* Add all nodes from the immediate dominator.
+ This ensures that avail_out contains the leader. */
+ if (block != env->start_block) {
+ ir_node *dom_block = get_Block_idom(block);
+ block_info *dom_info = get_block_info(dom_block);
+ ir_node *value;
+ ir_node *expr;
+ ir_valueset_iterator_t iter;
+
+ foreach_valueset(dom_info->avail_out, value, expr, iter)
+ /* replace: use the leader from dominator, not local exp_gen */
+ ir_valueset_replace(info->avail_out, value, expr);
+ }
+
+ DEBUG_ONLY(dump_value_set(info->avail_out, "Avail_out", block);)
+}
+
+/* --------------------------------------------------------
+ * Main algorithm redundancy detection
+ * --------------------------------------------------------
+ */
+
+/**
+ * Returns a valid mode if the value of expr is a partially redundant value.
+ *
+ * @param block the block
+ * @param expr the expression
+ *
+ * @return mode of the expression if it is partially redundant else NULL
+ */
+static ir_mode *is_partially_redundant(ir_node *block, ir_node *expr, ir_node *value)
+{
+ ir_node *first_avail = NULL;
+ int pos;
+ int arity = get_irn_arity(block);
+ int fully_redundant = 1;
+ int partially_redundant = 0;
+ ir_mode *mode = NULL;
+
+ DB((dbg, LEVEL_3, "is partially redundant %+F(%+F) of %+F\n", expr, value, block));
+
+ /* for each predecessor blocks */
+ for (pos = 0; pos < arity; ++pos) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, pos);
+ block_info *pred_info;
+ ir_node *trans_expr;
+ ir_node *trans_value;
+ ir_node *avail_expr;
+
+ pred_info = get_block_info(pred_block);
+ trans_expr = get_translated(pred_block, expr);
+ trans_value = identify(trans_expr);
+
+ if (is_Const(trans_expr))
+ avail_expr = trans_expr;
+ else
+ avail_expr = (ir_node*)ir_valueset_lookup(pred_info->avail_out, trans_value);
+
+ /* value might be available through a not yet existing constant */
+ if (avail_expr == NULL && is_Const(trans_expr)) {
+ /* limit range of new constants */
+ ir_mode *cmode = get_irn_mode(trans_expr);
+ ir_tarval *upper = new_tarval_from_long(127, cmode);
+ ir_tarval *lower = new_tarval_from_long(-127, cmode);
+ ir_tarval *c = get_Const_tarval(trans_expr);
+
+ /* tarval within range? */
+ if (tarval_cmp(lower, c) == ir_relation_less_equal &&
+ tarval_cmp(c, upper) == ir_relation_less_equal) {
+ avail_expr = trans_expr;
+ } else {
+ avail_expr = NULL;
+ }
+ }
+
+ DB((dbg, LEVEL_3, "avail_expr %+F trans_expr %+F\n", avail_expr, trans_expr));
+
+ if (avail_expr == NULL) {
+ pred_info->avail = trans_expr;
+ pred_info->found = 0;
+ fully_redundant = 0;
+ } else {
+ /* expr is available, use the leader */
+ 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 different expressions are available,
+ This is why we need no cut over avail_out sets. */
+ fully_redundant = 0;
+
+ DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, avail_expr, pred_block));
+ }
+ }
+
+ /* 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 (! partially_redundant || fully_redundant)
+ return NULL;
+ return mode;
+}
+
+/**
+ * Updates the new_set of a block by adding the new_set of
+ * the immediate dominating block.