return tarval_bad;
} /* computed_value_Not */
+/**
+ * Tests wether a shift shifts more bits than available in the mode
+ */
+static bool is_oversize_shift(const ir_node *n)
+{
+ ir_node *count = get_binop_right(n);
+ ir_mode *mode = get_irn_mode(n);
+ ir_tarval *tv = value_of(count);
+ long modulo_shift;
+ long shiftval;
+ if (tv == tarval_bad)
+ return false;
+ if (!tarval_is_long(tv))
+ return false;
+ shiftval = get_tarval_long(tv);
+ modulo_shift = get_mode_modulo_shift(mode);
+ if (shiftval < 0 || (modulo_shift > 0 && shiftval >= modulo_shift))
+ return false;
+
+ return shiftval >= (long)get_mode_size_bits(mode);
+}
+
/**
* Return the value of a Shl.
*/
if ((ta != tarval_bad) && (tb != tarval_bad)) {
return tarval_shl(ta, tb);
}
+
+ if (is_oversize_shift(n))
+ return get_mode_null(get_irn_mode(n));
+
return tarval_bad;
} /* computed_value_Shl */
if ((ta != tarval_bad) && (tb != tarval_bad)) {
return tarval_shr(ta, tb);
}
+ if (is_oversize_shift(n))
+ return get_mode_null(get_irn_mode(n));
+
return tarval_bad;
} /* computed_value_Shr */
return tarval_bad;
} /* computed_value_Rotl */
+bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
+{
+ ir_mode *mode = get_irn_mode(node);
+ if (get_mode_arithmetic(mode) != irma_twos_complement
+ || get_mode_arithmetic(dest_mode) != irma_twos_complement)
+ return false;
+
+ if (is_Shl(node)) {
+ ir_node *count = get_Shl_right(node);
+ if (is_Const(count)) {
+ ir_tarval *tv = get_Const_tarval(count);
+ if (tarval_is_long(tv)) {
+ long shiftval = get_tarval_long(tv);
+ long destbits = get_mode_size_bits(dest_mode);
+ if (shiftval >= destbits
+ && shiftval < (long)get_mode_modulo_shift(mode))
+ return true;
+ }
+ }
+ }
+ if (is_And(node)) {
+ ir_node *right = get_And_right(node);
+ if (is_Const(right)) {
+ ir_tarval *tv = get_Const_tarval(right);
+ ir_tarval *conved = tarval_convert_to(tv, dest_mode);
+ return tarval_is_null(conved);
+ }
+ }
+ return false;
+}
+
/**
* Return the value of a Conv.
*/
static ir_tarval *computed_value_Conv(const ir_node *n)
{
- ir_node *a = get_Conv_op(n);
- ir_tarval *ta = value_of(a);
+ ir_node *a = get_Conv_op(n);
+ ir_tarval *ta = value_of(a);
+ ir_mode *mode = get_irn_mode(n);
if (ta != tarval_bad)
return tarval_convert_to(ta, get_irn_mode(n));
+ if (ir_zero_when_converted(a, mode))
+ return get_mode_null(mode);
+
return tarval_bad;
} /* computed_value_Conv */
#undef CASE
} /* firm_set_default_computed_value */
-/**
- * Returns a equivalent block for another block.
- * If the block has only one predecessor, this is
- * the equivalent one. If the only predecessor of a block is
- * the block itself, this is a dead block.
- *
- * If both predecessors of a block are the branches of a binary
- * Cond, the equivalent block is Cond's block.
- *
- * If all predecessors of a block are bad or lies in a dead
- * block, the current block is dead as well.
- */
-static ir_node *equivalent_node_Block(ir_node *n)
-{
- ir_node *oldn = n;
- int n_preds;
- ir_graph *irg;
-
- /* don't optimize labeled blocks */
- if (has_Block_entity(n))
- return n;
- if (!get_Block_matured(n))
- return n;
-
- n_preds = get_Block_n_cfgpreds(n);
-
- irg = get_irn_irg(n);
-
- /* Straightening: a single entry Block following a single exit Block
- * can be merged. */
- if (n_preds == 1) {
- ir_node *pred = get_Block_cfgpred(n, 0);
-
- if (is_Jmp(pred)) {
- ir_node *pred_block = get_nodes_block(pred);
- DBG_OPT_STG(n, pred_block);
- return pred_block;
- }
- } else if (n_preds == 2) {
- /* Test whether Cond jumps twice to this block
- * The more general case which more than 2 predecessors is handles
- * in optimize_cf(), we handle only this special case for speed here.
- */
- ir_node *a = get_Block_cfgpred(n, 0);
- ir_node *b = get_Block_cfgpred(n, 1);
-
- if (is_Proj(a) && is_Proj(b)) {
- ir_node *cond = get_Proj_pred(a);
-
- if (cond == get_Proj_pred(b) && is_Cond(cond) &&
- get_irn_mode(get_Cond_selector(cond)) == mode_b) {
- /* Also a single entry Block following a single exit Block.
- * Phis have twice the same operand and will be optimized away.
- */
- n = get_nodes_block(cond);
- DBG_OPT_IFSIM1(oldn, a, b, n);
- }
- }
- }
-
- return n;
-} /* equivalent_node_Block */
-
-/* We do not evaluate Cond here as we replace it by a new node, a Jmp.
- See transform_node_Proj_Cond(). */
-
/**
* Optimize operations that are commutative and have neutral 0,
* so a op 0 = 0 op a = a.
break
switch (code) {
- CASE(Block);
CASE(Eor);
CASE(Add);
CASE(Shl);
/* the following reassociations work only for == and != */
if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
-
-#if 0 /* Might be not that good in general */
- /* a-b == 0 ==> a == b, a-b != 0 ==> a != b */
- if (tarval_is_null(tv) && is_Sub(left)) {
- right = get_Sub_right(left);
- left = get_Sub_left(left);
-
- tv = value_of(right);
- changed = 1;
- DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
- }
-#endif
-
if (tv != tarval_bad) {
/* a-c1 == c2 ==> a == c2+c1, a-c1 != c2 ==> a != c2+c1 */
if (is_Sub(left)) {
return proj;
} /* transform_node_Proj */
+static bool is_block_unreachable(const ir_node *block)
+{
+ const ir_graph *irg = get_irn_irg(block);
+ if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK))
+ return false;
+ return get_Block_dom_depth(block) < 0;
+}
+
static ir_node *transform_node_Block(ir_node *block)
{
- ir_graph *irg = get_irn_irg(block);
+ ir_graph *irg = get_irn_irg(block);
+ int arity = get_irn_arity(block);
+ ir_node *bad = NULL;
+ int i;
if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK))
return block;
- /* don't optimize labeled blocks */
- if (has_Block_entity(block))
- return block;
- if (!get_Block_matured(block))
- return block;
-
- /* remove blocks with only Bad inputs (or no inputs) */
- {
- int i;
- int n_cfgpreds = get_Block_n_cfgpreds(block);
- for (i = 0; i < n_cfgpreds; ++i) {
- ir_node *pred = get_Block_cfgpred(block, i);
- if (!is_Bad(pred))
- break;
- }
- /* only bad unreachable inputs? It's unreachable code (unless it is the
- * start or end block) */
- if (i >= n_cfgpreds && block != get_irg_start_block(irg)
- && block != get_irg_end_block(irg)) {
- return new_r_Bad(irg, mode_BB);
- }
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_Block_cfgpred(block, i);
+ ir_node *pred_block = get_nodes_block(pred);
+ if (!is_Bad(pred) && !is_block_unreachable(pred_block))
+ continue;
+ if (bad == NULL)
+ bad = new_r_Bad(irg, mode_X);
+ set_irn_n(block, i, bad);
}
+
return block;
}
/* Set phi-operands for bad-block inputs to bad */
for (i = 0; i < n; ++i) {
ir_node *pred = get_Block_cfgpred(block, i);
- if (!is_Bad(pred))
- continue;
- if (bad == NULL)
- bad = new_r_Bad(irg, mode);
- set_irn_n(phi, i, bad);
+ if (is_Bad(pred) || is_block_unreachable(get_nodes_block(pred))) {
+ if (bad == NULL)
+ bad = new_r_Bad(irg, mode);
+ set_irn_n(phi, i, bad);
+ }
}
/* Move Confirms down through Phi nodes. */
{
ir_node *left, *right;
ir_mode *mode;
+ ir_mode *count_mode;
ir_tarval *tv1, *tv2, *res;
ir_node *in[2], *irn, *block;
ir_graph *irg;
+ int modulo_shf;
left = get_binop_left(n);
return n;
right = get_binop_right(n);
- tv1 = value_of(right);
+ tv1 = value_of(right);
if (tv1 == tarval_bad)
return n;
if (tv2 == tarval_bad)
return n;
- res = tarval_add(tv1, tv2);
- mode = get_irn_mode(n);
- irg = get_irn_irg(n);
+ count_mode = get_tarval_mode(tv1);
+ if (get_tarval_mode(tv2) != count_mode) {
+ /* TODO: search bigger mode or something and convert... */
+ return n;
+ }
- /* beware: a simple replacement works only, if res < modulo shift */
- if (!is_Rotl(n)) {
- int modulo_shf = get_mode_modulo_shift(mode);
- if (modulo_shf > 0) {
- ir_tarval *modulo = new_tarval_from_long(modulo_shf,
- get_tarval_mode(res));
+ mode = get_irn_mode(n);
+ modulo_shf = get_mode_modulo_shift(mode);
- assert(modulo_shf >= (int) get_mode_size_bits(mode));
+ if (modulo_shf > 0) {
+ ir_tarval *modulo_mask = new_tarval_from_long(modulo_shf-1, count_mode);
- /* shifting too much */
- if (!(tarval_cmp(res, modulo) & ir_relation_less)) {
- if (is_Shrs(n)) {
- ir_node *block = get_nodes_block(n);
- dbg_info *dbgi = get_irn_dbg_info(n);
- ir_mode *smode = get_irn_mode(right);
- ir_node *cnst = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1);
- return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode);
- }
+ /* I'm not so sure what happens in one complement... */
+ assert(get_mode_arithmetic(count_mode) == irma_twos_complement);
+ /* modulo shifts should always be a power of 2 (otherwise modulo_mask
+ * above will be invalid) */
+ assert(modulo_shf<=0 || is_po2(modulo_shf));
- return new_r_Const(irg, get_mode_null(mode));
+ tv1 = tarval_and(tv1, modulo_mask);
+ tv2 = tarval_and(tv2, modulo_mask);
+ }
+ res = tarval_add(tv1, tv2);
+ irg = get_irn_irg(n);
+
+ /* beware: a simple replacement works only, if res < modulo shift */
+ if (is_Rotl(n)) {
+ int bits = get_mode_size_bits(mode);
+ ir_tarval *modulo = new_tarval_from_long(bits, count_mode);
+ res = tarval_mod(res, modulo);
+ } else {
+ long bits = get_mode_size_bits(mode);
+ ir_tarval *mode_size = new_tarval_from_long(bits, count_mode);
+
+ /* shifting too much */
+ if (!(tarval_cmp(res, mode_size) & ir_relation_less)) {
+ if (is_Shrs(n)) {
+ ir_node *block = get_nodes_block(n);
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_mode *smode = get_irn_mode(right);
+ ir_node *cnst = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1);
+ return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode);
}
+
+ return new_r_Const(irg, get_mode_null(mode));
}
- } else {
- res = tarval_mod(res, new_tarval_from_long(get_mode_size_bits(mode), get_tarval_mode(res)));
}
/* ok, we can replace it */
+ assert(modulo_shf >= (int) get_mode_size_bits(mode));
block = get_nodes_block(n);
in[0] = get_binop_left(left);
DBG_OPT_ALGSIM0(n, irn, FS_OPT_REASSOC_SHIFT);
return transform_node(irn);
-} /* transform_node_shift */
+}
/**
* normalisation: (x & c1) >> c2 to (x >> c2) & (c1 >> c2)
ir_node *b = get_Shrs_right(n);
ir_mode *mode = get_irn_mode(n);
+ if (is_oversize_shift(n)) {
+ ir_node *block = get_nodes_block(n);
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_mode *cmode = get_irn_mode(b);
+ long val = get_mode_size_bits(cmode)-1;
+ ir_graph *irg = get_irn_irg(n);
+ ir_node *cnst = new_r_Const_long(irg, cmode, val);
+ return new_rd_Shrs(dbgi, block, a, cnst, mode);
+ }
+
HANDLE_BINOP_PHI((eval_func) tarval_shrs, a, b, c, mode);
n = transform_node_shift(n);
for (i = j = 0; i < n_keepalives; ++i) {
ir_node *ka = get_End_keepalive(n, i);
- if (is_Bad(ka)) {
- /* no need to keep Bad */
+ ir_node *block;
+ /* no need to keep Bad */
+ if (is_Bad(ka))
+ continue;
+ /* dont keep unreachable code */
+ block = is_Block(ka) ? ka : get_nodes_block(ka);
+ if (is_block_unreachable(block))
continue;
- }
in[j++] = ka;
}
if (j != n_keepalives)
current_ir_graph = rem;
} /* visit_all_identities */
-static bool is_unreachable(ir_node *node)
-{
- ir_op *op = get_irn_op(node);
-
- /* Code in "Bad" blocks is unreachable and can be replaced by Bad */
- if (op != op_Block && is_Bad(get_nodes_block(node))) {
- return true;
- }
-
- return false;
-}
-
/**
* These optimizations deallocate nodes from the obstack.
* It can only be called if it is guaranteed that no other nodes
/* Always optimize Phi nodes: part of the construction. */
if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
- /* Remove nodes with dead (Bad) input.
- Run always for transformation induced Bads. */
- if (is_unreachable(n)) {
- ir_mode *mode = get_irn_mode(n);
- edges_node_deleted(n);
- irg_kill_node(irg, n);
- return new_r_Bad(irg, mode);
- }
-
/* constant expression evaluation / constant folding */
if (get_opt_constant_folding()) {
/* neither constants nor Tuple values can be evaluated */
if (iro == iro_Deleted)
return n;
- /* Remove nodes with dead (Bad) input.
- Run always for transformation induced Bads. */
- if (is_unreachable(n)) {
- ir_graph *irg = get_irn_irg(n);
- ir_mode *mode = get_irn_mode(n);
- return new_r_Bad(irg, mode);
- }
-
/* constant expression evaluation / constant folding */
if (get_opt_constant_folding()) {
/* neither constants nor Tuple values can be evaluated */