* @brief Machine dependent Firm optimizations.
* @date 28.9.2004
* @author Sebastian Hack, Michael Beck
- * @version $Id$
*
* Implements "Strength Reduction of Multiplications by Integer Constants"
* by Youfeng Wu.
ir_tarval *tv;
const ir_settings_arch_dep_t *params = be_get_backend_param()->dep_param;
-
/* If the architecture dependent optimizations were not initialized
or this optimization was not enabled. */
if (params == NULL || (opts & arch_dep_mul_to_shift) == 0)
- return irn;
+ return res;
- if (!is_Mul(irn) || !mode_is_int(mode))
+ assert(is_Mul(irn));
+ if (!mode_is_int(mode))
return res;
/* we should never do the reverse transformations again
(like x+x -> 2*x) */
irg = get_irn_irg(irn);
- set_irg_state(irg, IR_GRAPH_STATE_ARCH_DEP);
+ add_irg_constraints(irg, IR_GRAPH_CONSTRAINT_ARCH_DEP);
left = get_binop_left(irn);
right = get_binop_right(irn);
operand = left;
}
+ /* multiplications with 0 are a special case which we leave for
+ * equivalent_node_Mul because the code here can't handle them */
+ if (tv == get_mode_null(mode))
+ return res;
+
if (tv != NULL) {
res = do_decomposition(irn, operand, tv);
ir_node *block = get_irn_n(div, -1);
ir_mode *mode = get_irn_mode(n);
int bits = get_mode_size_bits(mode);
- ir_node *q, *t, *c;
+ ir_node *q;
/* Beware: do not transform bad code */
if (is_Bad(n) || is_Bad(block))
struct ms mag = magic(tv);
/* generate the Mulh instruction */
- c = new_r_Const(irg, mag.M);
+ ir_node *c = new_r_Const(irg, mag.M);
+ ir_node *t;
q = new_rd_Mulh(dbg, block, n, c, mode);
/* do we need an Add or Sub */
q = new_rd_Add(dbg, block, q, t, mode);
} else {
struct mu mag = magicu(tv);
- ir_node *c;
ir_graph *irg = get_irn_irg(div);
/* generate the Mulh instruction */
- c = new_r_Const(irg, mag.M);
+ ir_node *c = new_r_Const(irg, mag.M);
q = new_rd_Mulh(dbg, block, n, c, mode);
if (mag.need_add) {
if (mag.s > 0) {
/* use the GM scheme */
- t = new_rd_Sub(dbg, block, n, q, mode);
+ ir_node *t = new_rd_Sub(dbg, block, n, q, mode);
c = new_r_Const(irg, get_mode_one(mode_Iu));
t = new_rd_Shr(dbg, block, t, c, mode);
ir_node *res = irn;
/* If the architecture dependent optimizations were not initialized
- or this optimization was not enabled. */
+ or this optimization was not enabled. */
if (params == NULL || (opts & arch_dep_div_by_const) == 0)
return irn;
- if (is_Div(irn)) {
- ir_node *c = get_Div_right(irn);
- ir_node *block, *left;
- ir_mode *mode;
- ir_tarval *tv, *ntv;
- dbg_info *dbg;
- int n, bits;
- int k;
- int n_flag = 0;
-
- if (! is_Const(c))
- return irn;
+ if (!is_Div(irn))
+ return irn;
- tv = get_Const_tarval(c);
+ ir_node *c = get_Div_right(irn);
+ ir_node *block, *left;
+ ir_mode *mode;
+ ir_tarval *tv, *ntv;
+ dbg_info *dbg;
+ int n, bits;
+ int k;
+ int n_flag = 0;
- /* check for division by zero */
- if (tarval_is_null(tv))
- return irn;
+ if (! is_Const(c))
+ return irn;
- left = get_Div_left(irn);
- mode = get_irn_mode(left);
+ tv = get_Const_tarval(c);
- /* can only handle integer Div's */
- if (!mode_is_int(mode))
- return irn;
+ /* check for division by zero */
+ if (tarval_is_null(tv))
+ return irn;
- block = get_irn_n(irn, -1);
- dbg = get_irn_dbg_info(irn);
+ left = get_Div_left(irn);
+ mode = get_irn_mode(left);
- bits = get_mode_size_bits(mode);
- n = (bits + 7) / 8;
+ /* can only handle integer Div's */
+ if (!mode_is_int(mode))
+ return irn;
- k = -1;
- if (mode_is_signed(mode)) {
- /* for signed divisions, the algorithm works for a / -2^k by negating the result */
- ntv = tarval_neg(tv);
- n_flag = 1;
- k = tv_ld2(ntv, n);
- }
+ block = get_irn_n(irn, -1);
+ dbg = get_irn_dbg_info(irn);
- if (k < 0) {
- n_flag = 0;
- k = tv_ld2(tv, n);
- }
+ bits = get_mode_size_bits(mode);
+ n = (bits + 7) / 8;
- if (k >= 0) { /* division by 2^k or -2^k */
- ir_graph *irg = get_irn_irg(irn);
- if (mode_is_signed(mode)) {
- ir_node *k_node;
- ir_node *curr = left;
+ k = -1;
+ if (mode_is_signed(mode)) {
+ /* for signed divisions, the algorithm works for a / -2^k by negating the result */
+ ntv = tarval_neg(tv);
+ n_flag = 1;
+ k = tv_ld2(ntv, n);
+ }
- /* create the correction code for signed values only if there might be a remainder */
- if (! get_Div_no_remainder(irn)) {
- if (k != 1) {
- k_node = new_r_Const_long(irg, mode_Iu, k - 1);
- curr = new_rd_Shrs(dbg, block, left, k_node, mode);
- }
+ if (k < 0) {
+ n_flag = 0;
+ k = tv_ld2(tv, n);
+ }
- k_node = new_r_Const_long(irg, mode_Iu, bits - k);
- curr = new_rd_Shr(dbg, block, curr, k_node, mode);
+ if (k > 0) { /* division by 2^k or -2^k */
+ ir_graph *irg = get_irn_irg(irn);
+ if (mode_is_signed(mode)) {
+ ir_node *k_node;
+ ir_node *curr = left;
- curr = new_rd_Add(dbg, block, left, curr, mode);
- } else {
- k_node = left;
+ /* create the correction code for signed values only if there might be a remainder */
+ if (! get_Div_no_remainder(irn)) {
+ if (k != 1) {
+ k_node = new_r_Const_long(irg, mode_Iu, k - 1);
+ curr = new_rd_Shrs(dbg, block, left, k_node, mode);
}
- k_node = new_r_Const_long(irg, mode_Iu, k);
- res = new_rd_Shrs(dbg, block, curr, k_node, mode);
+ k_node = new_r_Const_long(irg, mode_Iu, bits - k);
+ curr = new_rd_Shr(dbg, block, curr, k_node, mode);
+ /* curr is now 2^(k-1) in case left < 0
+ * or 0 in case left >= 0
+ *
+ * For an example, where this fixup is necessary consider -3 / 2,
+ * which should compute to -1,
+ * but simply shifting right by one computes -2.
+ */
- if (n_flag) { /* negate the result */
- ir_node *k_node;
+ curr = new_rd_Add(dbg, block, left, curr, mode);
+ }
- k_node = new_r_Const(irg, get_mode_null(mode));
- res = new_rd_Sub(dbg, block, k_node, res, mode);
- }
- } else { /* unsigned case */
- ir_node *k_node;
+ k_node = new_r_Const_long(irg, mode_Iu, k);
+ res = new_rd_Shrs(dbg, block, curr, k_node, mode);
- k_node = new_r_Const_long(irg, mode_Iu, k);
- res = new_rd_Shr(dbg, block, left, k_node, mode);
+ if (n_flag) { /* negate the result */
+ k_node = new_r_Const(irg, get_mode_null(mode));
+ res = new_rd_Sub(dbg, block, k_node, res, mode);
}
- } else {
- /* other constant */
- if (allow_Mulh(params, mode))
- res = replace_div_by_mulh(irn, tv);
+ } else { /* unsigned case */
+ ir_node *k_node;
+
+ k_node = new_r_Const_long(irg, mode_Iu, k);
+ res = new_rd_Shr(dbg, block, left, k_node, mode);
}
+ } else if (k != 0) {
+ /* other constant */
+ if (allow_Mulh(params, mode))
+ res = replace_div_by_mulh(irn, tv);
+ } else { /* k == 0 i.e. division by 1 */
+ res = left;
}
if (res != irn)
k = tv_ld2(tv, n);
}
- if (k >= 0) {
+ /* k == 0 i.e. modulo by 1 */
+ if (k == 0) {
+ ir_graph *irg = get_irn_irg(irn);
+
+ res = new_r_Const(irg, get_mode_null(mode));
+ }
+ else if (k > 0) {
ir_graph *irg = get_irn_irg(irn);
/* division by 2^k or -2^k:
* we use "modulus" here, so x % y == x % -y that's why is no difference between the case 2^k and -2^k