} /* equivalent_node_Or */
/**
- * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
+ * Optimize a & 0b1...1 = 0b1...1 & a = a & a = (a|X) & a = a.
*/
static ir_node *equivalent_node_And(ir_node *n) {
ir_node *oldn = n;
if (a == b) {
n = a; /* And has it's own neutral element */
DBG_OPT_ALGSIM0(oldn, n, FS_OPT_AND);
- } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
+ return n;
+ }
+ if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
n = b;
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
- } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
+ return n;
+ }
+ if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
n = a;
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
+ return n;
}
+ if (is_Or(a)) {
+ if (b == get_Or_left(a) || b == get_Or_right(a)) {
+ /* (a|X) & a */
+ n = b;
+ DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
+ return n;
+ }
+ }
+ if (is_Or(b)) {
+ if (a == get_Or_left(b) || a == get_Or_right(b)) {
+ /* a & (a|X) */
+ n = a;
+ DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
+ return n;
+ }
+ }
+
return n;
} /* equivalent_node_And */
#undef CASE
} /* firm_set_default_equivalent_node */
-/**
- * Do node specific optimizations of nodes predecessors.
- */
-static void optimize_preds(ir_node *n) {
- switch (get_irn_opcode(n)) {
-
- case iro_Cmp: { /* We don't want Cast as input to Cmp. */
- ir_node *a = get_Cmp_left(n), *b = get_Cmp_right(n);
-
- if (get_irn_op(a) == op_Cast) {
- a = get_Cast_op(a);
- set_Cmp_left(n, a);
- }
- if (get_irn_op(b) == op_Cast) {
- b = get_Cast_op(b);
- set_Cmp_right(n, b);
- }
- break;
- }
-
- default: break;
- } /* end switch */
-} /* optimize_preds */
-
/**
* Returns non-zero if a node is a Phi node
* with all predecessors constant.
}
}
}
- /* Here we rely on constants be on the RIGHT side */
- if (get_mode_arithmetic(mode) == irma_twos_complement &&
- is_Not(a) && classify_Const(b) == CNST_ONE) {
- /* ~x + 1 = -x */
- ir_node *op = get_Not_op(a);
- ir_node *blk = get_irn_n(n, -1);
- n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph, blk, op, mode);
- DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_PLUS_1);
- return n;
+ if (get_mode_arithmetic(mode) == irma_twos_complement) {
+ /* Here we rely on constants be on the RIGHT side */
+ if (is_Not(a)) {
+ ir_node *op = get_Not_op(a);
+
+ if (classify_Const(b) == CNST_ONE) {
+ /* ~x + 1 = -x */
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph, blk, op, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_PLUS_1);
+ return n;
+ }
+ if (op == b) {
+ /* ~x + x = -1 */
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_r_Const(current_ir_graph, blk, mode, get_mode_minus_one(mode));
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_X_NOT_X);
+ return n;
+ }
+ }
+ if (is_Not(b)) {
+ ir_node *op = get_Not_op(b);
+
+ if (op == a) {
+ /* ~x + x = -1 */
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_r_Const(current_ir_graph, blk, mode, get_mode_minus_one(mode));
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_X_NOT_X);
+ return n;
+ }
+ }
}
}
return n;
} /* transform_node_Add */
/* returns -cnst */
-static ir_node* const_negate(ir_node* cnst)
-{
+static ir_node *const_negate(ir_node *cnst) {
tarval *tv = tarval_neg(get_Const_tarval(cnst));
dbg_info *dbgi = get_irn_dbg_info(cnst);
ir_graph *irg = get_irn_irg(cnst);
add = new_r_Add(current_ir_graph, blk, y, b, mode);
- set_Sub_left(n, x);
- set_Sub_right(n, add);
- DBG_OPT_ALGSIM0(n, n, FS_OPT_SUB_SUB_X_Y_Z);
+ n = new_rd_Sub(get_irn_dbg_info(n), current_ir_graph, blk, x, add, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_SUB_X_Y_Z);
return n;
}
+
+ if (get_mode_arithmetic(mode) == irma_twos_complement) {
+ if (is_Const(a) && is_Not(b)) {
+ /* c - ~X = X + (c+1) */
+ tarval *tv = get_Const_tarval(a);
+
+ tv = tarval_add(tv, get_mode_one(mode));
+ if (tv != tarval_bad) {
+ ir_node *blk = get_irn_n(n, -1);
+ ir_node *c = new_r_Const(current_ir_graph, blk, mode, tv);
+ n = new_rd_Add(get_irn_dbg_info(n), current_ir_graph, blk, get_Not_op(b), c, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_C_NOT_X);
+ return n;
+ }
+ }
+ }
return n;
} /* transform_node_Sub */
set_binop_right(n, c);
}
-
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_SHIFT_AND);
return n;
}
* Transform an And.
*/
static ir_node *transform_node_And(ir_node *n) {
- ir_node *c, *oldn;
+ ir_node *c, *oldn = n;
ir_node *a = get_And_left(n);
ir_node *b = get_And_right(n);
HANDLE_BINOP_PHI(tarval_and, a,b,c);
/* we can evaluate 2 Projs of the same Cmp */
- if(get_irn_mode(n) == mode_b && is_Proj(a) && is_Proj(b)) {
+ if (get_irn_mode(n) == mode_b && is_Proj(a) && is_Proj(b)) {
ir_node *pred_a = get_Proj_pred(a);
ir_node *pred_b = get_Proj_pred(b);
if(pred_a == pred_b) {
new_pnc);
}
}
+ if (is_Or(a)) {
+ if (is_Not(b)) {
+ ir_node *op = get_Not_op(b);
+ if (is_And(op)) {
+ ir_node *ba = get_And_left(op);
+ ir_node *bb = get_And_right(op);
+
+ /* it's enough to test the following cases due to normalization! */
+ if (get_Or_left(a) == ba && get_Or_right(a) == bb) {
+ /* (a|b) & ~(a&b) = a^b */
+ ir_node *block = get_nodes_block(n);
+
+ n = new_rd_Eor(get_irn_dbg_info(n), current_ir_graph, block, ba, bb, get_irn_mode(n));
+ DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_TO_EOR);
+ return n;
+ }
+ }
+ }
+ }
+ if (is_Or(b)) {
+ if (is_Not(a)) {
+ ir_node *op = get_Not_op(a);
+ if (is_And(op)) {
+ ir_node *aa = get_And_left(op);
+ ir_node *ab = get_And_right(op);
+
+ /* it's enough to test the following cases due to normalization! */
+ if (get_Or_left(b) == aa && get_Or_right(b) == ab) {
+ /* (a|b) & ~(a&b) = a^b */
+ ir_node *block = get_nodes_block(n);
+
+ n = new_rd_Eor(get_irn_dbg_info(n), current_ir_graph, block, aa, ab, get_irn_mode(n));
+ DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_TO_EOR);
+ return n;
+ }
+ }
+ }
+
+ }
n = transform_bitwise_distributive(n, transform_node_And);
* Transform a Minus.
* Optimize:
* -(~x) = x + 1
+ * -(a-b) = b - a
*/
static ir_node *transform_node_Minus(ir_node *n) {
ir_node *c, *oldn = n;
HANDLE_UNOP_PHI(tarval_neg,a,c);
mode = get_irn_mode(a);
- if (get_mode_arithmetic(mode) == irma_twos_complement && is_Not(a)) {
- /* -(~x) = x + 1 */
- ir_node *op = get_Not_op(a);
- tarval *tv = get_mode_one(mode);
- ir_node *blk = get_irn_n(n, -1);
- ir_node *c = new_r_Const(current_ir_graph, blk, mode, tv);
- n = new_rd_Add(get_irn_dbg_info(n), current_ir_graph, blk, op, c, mode);
- DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_NOT);
- } else if (is_Sub(a)) {
+ if (get_mode_arithmetic(mode) == irma_twos_complement) {
+ /* the following rules are only to twos-complement */
+ if (is_Not(a)) {
+ /* -(~x) = x + 1 */
+ ir_node *op = get_Not_op(a);
+ tarval *tv = get_mode_one(mode);
+ ir_node *blk = get_irn_n(n, -1);
+ ir_node *c = new_r_Const(current_ir_graph, blk, mode, tv);
+ n = new_rd_Add(get_irn_dbg_info(n), current_ir_graph, blk, op, c, mode);
+ DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_NOT);
+ return n;
+ }
+ if (is_Shr(a)) {
+ ir_node *c = get_Shr_right(a);
+
+ if (is_Const(c)) {
+ tarval *tv = get_Const_tarval(c);
+
+ if (tarval_is_long(tv) && get_tarval_long(tv) == get_mode_size_bits(mode) - 1) {
+ /* -(a >>u (size-1)) = a >>s (size-1) */
+ ir_node *v = get_Shr_left(a);
+
+ n = new_rd_Shrs(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1), v, c, mode);
+ DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_PREDICATE);
+ return n;
+ }
+ }
+ }
+ if (is_Shrs(a)) {
+ ir_node *c = get_Shrs_right(a);
+
+ if (is_Const(c)) {
+ tarval *tv = get_Const_tarval(c);
+
+ if (tarval_is_long(tv) && get_tarval_long(tv) == get_mode_size_bits(mode) - 1) {
+ /* -(a >>s (size-1)) = a >>u (size-1) */
+ ir_node *v = get_Shrs_left(a);
+
+ n = new_rd_Shr(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1), v, c, mode);
+ DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_PREDICATE);
+ return n;
+ }
+ }
+ }
+ }
+ if (is_Sub(a)) {
/* - (a-b) = b - a */
ir_node *la = get_Sub_left(a);
ir_node *ra = get_Sub_right(a);
n = new_rd_Sub(get_irn_dbg_info(n), current_ir_graph, blk, ra, la, mode);
DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_SUB);
+ return n;
}
return n;
/* Remove unnecessary conversions */
/* TODO handle constants */
if (is_Conv(left) && is_Conv(right)) {
- ir_mode* mode = get_irn_mode(left);
- ir_node* op_left = get_Conv_op(left);
- ir_node* op_right = get_Conv_op(right);
- ir_mode* mode_left = get_irn_mode(op_left);
- ir_mode* mode_right = get_irn_mode(op_right);
+ ir_mode *mode = get_irn_mode(left);
+ ir_node *op_left = get_Conv_op(left);
+ ir_node *op_right = get_Conv_op(right);
+ ir_mode *mode_left = get_irn_mode(op_left);
+ ir_mode *mode_right = get_irn_mode(op_right);
if (smaller_mode(mode_left, mode) && smaller_mode(mode_right, mode)) {
- ir_graph* irg = current_ir_graph;
- ir_node* block = get_nodes_block(n);
- ir_node* new_left;
- ir_node* new_right;
+ ir_graph *irg = current_ir_graph;
+ ir_node *block = get_nodes_block(n);
if (mode_left == mode_right) {
- new_left = op_left;
- new_right = op_right;
+ left = op_left;
+ right = op_right;
+ changed |= 1;
} else if (smaller_mode(mode_left, mode_right)) {
- new_left = new_r_Conv(irg, block, op_left, mode_right);
- new_right = op_right;
+ left = new_r_Conv(irg, block, op_left, mode_right);
+ right = op_right;
+ changed |= 1;
} else if (smaller_mode(mode_right, mode_left)) {
- new_left = op_left;
- new_right = new_r_Conv(irg, block, op_right, mode_left);
- } else {
- goto no_remove_conv;
+ left = op_left;
+ right = new_r_Conv(irg, block, op_right, mode_left);
+ changed |= 1;
}
- left = new_left;
- right = new_right;
- set_Cmp_left( n, left);
- set_Cmp_right(n, right);
-no_remove_conv:;
+ }
+ }
+
+ /* remove Casts */
+ if (is_Cast(left))
+ left = get_Cast_op(left);
+ if (is_Cast(right))
+ right = get_Cast_op(right);
+
+ /* remove operation of both sides if possible */
+ if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
+ ir_opcode lop = get_irn_opcode(left);
+
+ if (lop == get_irn_opcode(right)) {
+ ir_node *ll, *lr, *rl, *rr;
+
+ /* same operation on both sides, try to remove */
+ switch (lop) {
+ case iro_Not:
+ case iro_Minus:
+ /* ~a CMP ~b => a CMP b, -a CMP -b ==> a CMP b */
+ left = get_unop_op(left);
+ right = get_unop_op(right);
+ changed |= 1;
+ break;
+ case iro_Add:
+ ll = get_Add_left(left);
+ lr = get_Add_right(left);
+ rl = get_Add_left(right);
+ rr = get_Add_right(right);
+
+ if (ll == rl) {
+ /* X + a CMP X + b ==> a CMP b */
+ left = lr;
+ right = rr;
+ changed |= 1;
+ } else if (ll == rr) {
+ /* X + a CMP b + X ==> a CMP b */
+ left = lr;
+ right = rl;
+ changed |= 1;
+ } else if (lr == rl) {
+ /* a + X CMP X + b ==> a CMP b */
+ left = ll;
+ right = rr;
+ changed |= 1;
+ } else if (lr == rr) {
+ /* a + X CMP b + X ==> a CMP b */
+ left = ll;
+ right = rl;
+ changed |= 1;
+ }
+ break;
+ case iro_Sub:
+ ll = get_Sub_left(left);
+ lr = get_Sub_right(left);
+ rl = get_Sub_left(right);
+ rr = get_Sub_right(right);
+
+ if (ll == rl) {
+ /* X - a CMP X - b ==> a CMP b */
+ left = lr;
+ right = rr;
+ changed |= 1;
+ } else if (lr == rr) {
+ /* a - X CMP b - X ==> a CMP b */
+ left = ll;
+ right = rl;
+ changed |= 1;
+ }
+ break;
+ case iro_Rot:
+ if (get_Rot_right(left) == get_Rot_right(right)) {
+ /* a ROT X CMP b ROT X */
+ left = get_Rot_left(left);
+ right = get_Rot_left(right);
+ changed |= 1;
+ }
+ break;
+ default:
+ break;
+ }
+
}
}
if (get_irn_mode(left) == mode_b) {
- ir_graph* irg = current_ir_graph;
- ir_node* block = get_nodes_block(n);
+ ir_graph *irg = current_ir_graph;
+ ir_node *block = get_nodes_block(n);
switch (proj_nr) {
case pn_Cmp_Le: return new_r_Or( irg, block, new_r_Not(irg, block, left, mode_b), right, mode_b);
/*
* First step: normalize the compare op
- * by placing the constant on the right site
+ * by placing the constant on the right side
* or moving the lower address node to the left.
* We ignore the case that both are constants
* this case should be optimized away.
*/
- if (get_irn_op(right) == op_Const) {
+ if (is_Const(right)) {
c = right;
- } else if (get_irn_op(left) == op_Const) {
+ } else if (is_Const(left)) {
c = left;
left = right;
right = c;
* be optimized, see this:
* -MININT < 0 =/=> MININT > 0 !!!
*/
- if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
+ if (is_Minus(left) &&
(!mode_overflow_on_unary_Minus(mode) ||
(mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
- left = get_Minus_op(left);
tv = tarval_neg(tv);
if (tv != tarval_bad) {
+ left = get_Minus_op(left);
proj_nr = get_inversed_pnc(proj_nr);
changed |= 2;
}
+ } else if (is_Not(left) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)) {
+ tv = tarval_not(tv);
+
+ if (tv != tarval_bad) {
+ left = get_Not_op(left);
+ changed |= 2;
+ }
}
/* for integer modes, we have more */
if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
/* a-b == 0 ==> a == b, a-b != 0 ==> a != b */
- if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
- right = get_Sub_right(left);
+ if (classify_tarval(tv) == TV_CLASSIFY_NULL && is_Sub(left)) {
+ right =get_Sub_right(left);
left = get_Sub_left(left);
tv = value_of(right);
- if (tv != tarval_bad) {
- changed = 1;
- }
+ changed = 1;
}
if (tv != tarval_bad) {
*
* if C is a single Bit constant.
*/
- if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) &&
- (get_irn_op(left) == op_And)) {
+ if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) && is_And(left)) {
if (tarval_is_single_bit(tv)) {
/* check for Constant's match. We have check hare the tarvals,
because our const might be changed */
right = new_Const(mode, tv);
/* create a new compare */
- n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
- left, right);
+ n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block, left, right);
set_Proj_pred(proj, n);
set_Proj_proj(proj, proj_nr);
(iro == iro_Block) ) /* Flags tested local. */
n = equivalent_node(n);
- optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
-
/* Common Subexpression Elimination.
*
* Checks whether n is already available.
(iro == iro_Block) ) /* Flags tested local. */
n = equivalent_node(n);
- optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
-
/** common subexpression elimination **/
/* Checks whether n is already available. */
/* The block input is used to distinguish different subexpressions. Right