X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firarch.c;h=d72fbe951f57e6173fb3f8e01adb1785c5d49ed0;hb=69d11aa49aa17358468bbb2f5506ef5f009514e9;hp=93472026ed1ef8b6184b9637b8ae3326b33babc6;hpb=838a6e5160c6eb4595d414742d8a1efa83b67d2a;p=libfirm

diff --git a/ir/ir/irarch.c b/ir/ir/irarch.c
index 93472026e..d72fbe951 100644
--- a/ir/ir/irarch.c
+++ b/ir/ir/irarch.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -27,14 +27,9 @@
  * Implements "Strenght Reduction of Multiplications by Integer Constants" by Youfeng Wu.
  * Implements Division and Modulo by Consts from "Hackers Delight",
  */
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
-
-#ifdef HAVE_STDLIB_H
-# include <stdlib.h>
-#endif
+#include "config.h"
 
+#include <stdlib.h>
 #include <assert.h>
 
 #include "irnode_t.h"
@@ -52,6 +47,7 @@
 #include "ircons.h"
 #include "irarch.h"
 #include "irflag.h"
+#include "error.h"
 
 #undef DEB
 
@@ -70,47 +66,15 @@ static const ir_settings_arch_dep_t *params = NULL;
 /** The bit mask, which optimizations to apply. */
 static arch_dep_opts_t opts;
 
-/* we need this new pseudo op */
-static ir_op *op_Mulh = NULL;
-
-/**
- * construct a Mulh: Mulh(a,b) = (a * b) >> w, w is the with in bits of a, b
- */
-static ir_node *
-new_rd_Mulh (dbg_info *db, ir_graph *irg, ir_node *block,
-       ir_node *op1, ir_node *op2, ir_mode *mode) {
-	ir_node *in[2];
-	ir_node *res;
-
-	in[0] = op1;
-	in[1] = op2;
-	res = new_ir_node(db, irg, block, op_Mulh, mode, 2, in);
-	res = optimize_node(res);
-	IRN_VRFY_IRG(res, irg);
-	return res;
-}
-
-ir_op *get_op_Mulh(void)  { return op_Mulh; }
-
 void arch_dep_init(arch_dep_params_factory_t factory) {
 	opts = arch_dep_none;
 
 	if (factory != NULL)
 		params = factory();
-
-	if (! op_Mulh) {
-		int mulh_opc = get_next_ir_opcode();
-
-		/* create the Mulh operation */
-		op_Mulh = new_ir_op(mulh_opc, "Mulh",  op_pin_state_floats, irop_flag_commutative, oparity_binary, 0, 0, NULL);
-	}
 }
 
 void arch_dep_set_opts(arch_dep_opts_t the_opts) {
 	opts = the_opts;
-
-	if (opts & arch_dep_mul_to_shift)
-		set_opt_arch_dep_running(1);
 }
 
 /** check, whether a mode allows a Mulh instruction. */
@@ -138,7 +102,7 @@ struct instruction {
 typedef struct _mul_env {
 	struct obstack obst;       /**< an obstack for local space. */
 	ir_mode        *mode;      /**< the mode of the multiplication constant */
-	int            bits;       /**< number of bits in the mode */
+	unsigned       bits;       /**< number of bits in the mode */
 	unsigned       max_S;      /**< the maximum LEA shift value. */
 	instruction    *root;      /**< the root of the instruction tree */
 	ir_node        *op;        /**< the operand that is multiplied */
@@ -152,9 +116,12 @@ typedef struct _mul_env {
 } mul_env;
 
 /**
- * Some kind of default evaluator.
+ * Some kind of default evaluator. Return the cost of
+ * instructions.
  */
 static int default_evaluate(insn_kind kind, tarval *tv) {
+	(void) tv;
+
 	if (kind == MUL)
 		return 13;
 	return 1;
@@ -258,8 +225,8 @@ static unsigned char *value_to_condensed(mul_env *env, tarval *tv, int *pr) {
  * Calculate the gain when using the generalized complementary technique
  */
 static int calculate_gain(unsigned char *R, int r) {
-	int max_gain = -1;
-	int idx, i;
+	int max_gain = 0;
+	int idx = -1, i;
 	int gain;
 
 	/* the gain for r == 1 */
@@ -273,9 +240,7 @@ static int calculate_gain(unsigned char *R, int r) {
 			idx = i;
 		}
 	}
-	if (max_gain > 0)
-		return idx;
-	return -1;
+	return idx;
 }
 
 /**
@@ -348,17 +313,23 @@ static instruction *basic_decompose_mul(mul_env *env, unsigned char *R, int r, t
 static instruction *decompose_simple_cases(mul_env *env, unsigned char *R, int r, tarval *N) {
 	instruction *ins, *ins2;
 
+	(void) N;
 	if (r == 1) {
 		return emit_SHIFT(env, env->root, R[0]);
 	} else {
 		assert(r == 2);
 
 		ins = env->root;
+		if (R[1] <= env->max_S) {
+			ins = emit_LEA(env, ins, ins, R[1]);
+			if (R[0] != 0) {
+				ins = emit_SHIFT(env, ins, R[0]);
+			}
+			return ins;
+		}
 		if (R[0] != 0) {
 			ins = emit_SHIFT(env, ins, R[0]);
 		}
-		if (R[1] <= env->max_S)
-			return emit_LEA(env, ins, ins, R[1]);
 
 		ins2 = emit_SHIFT(env, env->root, R[0] + R[1]);
 		return emit_LEA(env, ins, ins2, 0);
@@ -474,12 +445,12 @@ static ir_node *build_graph(mul_env *env, instruction *inst) {
 	case LEA:
 		l = build_graph(env, inst->in[0]);
 		r = build_graph(env, inst->in[1]);
-		c = new_r_Const(current_ir_graph, env->blk, env->shf_mode, new_tarval_from_long(inst->shift_count, env->shf_mode));
+		c = new_Const_long(env->shf_mode, inst->shift_count);
 		r = new_rd_Shl(env->dbg, current_ir_graph, env->blk, r, c, env->mode);
 		return inst->irn = new_rd_Add(env->dbg, current_ir_graph, env->blk, l, r, env->mode);
 	case SHIFT:
 		l = build_graph(env, inst->in[0]);
-		c = new_r_Const(current_ir_graph, env->blk, env->shf_mode, new_tarval_from_long(inst->shift_count, env->shf_mode));
+		c = new_Const_long(env->shf_mode, inst->shift_count);
 		return inst->irn = new_rd_Shl(env->dbg, current_ir_graph, env->blk, l, c, env->mode);
 	case SUB:
 		l = build_graph(env, inst->in[0]);
@@ -490,9 +461,9 @@ static ir_node *build_graph(mul_env *env, instruction *inst) {
 		r = build_graph(env, inst->in[1]);
 		return inst->irn = new_rd_Add(env->dbg, current_ir_graph, env->blk, l, r, env->mode);
 	case ZERO:
-		return inst->irn = new_r_Const(current_ir_graph, env->blk, env->mode, get_mode_null(env->mode));
+		return inst->irn = new_Const(get_mode_null(env->mode));
 	default:
-		assert(0);
+		panic("Unsupported instruction kind");
 		return NULL;
 	}
 }
@@ -532,16 +503,17 @@ static int evaluate_insn(mul_env *env, instruction *inst) {
 	case ZERO:
 		inst->costs = costs = env->evaluate(inst->kind, NULL);
 		return costs;
-	default:
-		assert(0);
-		return 0;
+	case MUL:
+	case ROOT:
+		break;
 	}
+	panic("Unsupported instruction kind");
 }
 
 /**
  * Evaluate the replacement instructions and build a new graph
  * if faster than the Mul.
- * returns the root of the new graph then or irn otherwise.
+ * Returns the root of the new graph then or irn otherwise.
  *
  * @param irn      the Mul operation
  * @param operand  the multiplication operand
@@ -559,7 +531,7 @@ static ir_node *do_decomposition(ir_node *irn, ir_node *operand, tarval *tv) {
 
 	obstack_init(&env.obst);
 	env.mode     = get_tarval_mode(tv);
-	env.bits     = get_mode_size_bits(env.mode);
+	env.bits     = (unsigned)get_mode_size_bits(env.mode);
 	env.max_S    = 3;
 	env.root     = emit_ROOT(&env, operand);
 	env.fail     = 0;
@@ -570,7 +542,7 @@ static ir_node *do_decomposition(ir_node *irn, ir_node *operand, tarval *tv) {
 	inst = decompose_mul(&env, R, r, tv);
 
 	/* the paper suggests 70% here */
-	mul_costs = (env.evaluate(MUL, tv) * 7) / 10;
+	mul_costs = (env.evaluate(MUL, tv) * 7 + 5) / 10;
 	if (evaluate_insn(&env, inst) <= mul_costs && !env.fail) {
 		env.op       = operand;
 		env.blk      = get_nodes_block(irn);
@@ -595,31 +567,34 @@ ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn) {
 	if (params == NULL || (opts & arch_dep_mul_to_shift) == 0)
 		return irn;
 
-	if (is_Mul(irn) && mode_is_int(mode)) {
-		ir_node *block   = get_nodes_block(irn);
-		ir_node *left    = get_binop_left(irn);
-		ir_node *right   = get_binop_right(irn);
-		tarval *tv       = NULL;
-		ir_node *operand = NULL;
-
-		/* Look, if one operand is a constant. */
-		if (is_Const(left)) {
-			tv = get_Const_tarval(left);
-			operand = right;
-		} else if (is_Const(right)) {
-			tv = get_Const_tarval(right);
-			operand = left;
-		}
+	set_arch_dep_running(1);
+	{
+		if (is_Mul(irn) && mode_is_int(mode)) {
+			ir_node *left    = get_binop_left(irn);
+			ir_node *right   = get_binop_right(irn);
+			tarval *tv       = NULL;
+			ir_node *operand = NULL;
+
+			/* Look, if one operand is a constant. */
+			if (is_Const(left)) {
+				tv = get_Const_tarval(left);
+				operand = right;
+			} else if (is_Const(right)) {
+				tv = get_Const_tarval(right);
+				operand = left;
+			}
 
-		if (tv != NULL) {
-			res = do_decomposition(irn, operand, tv);
+			if (tv != NULL) {
+				res = do_decomposition(irn, operand, tv);
 
-			if (res != irn) {
-				hook_arch_dep_replace_mul_with_shifts(irn);
-				exchange(irn, res);
+				if (res != irn) {
+					hook_arch_dep_replace_mul_with_shifts(irn);
+					exchange(irn, res);
+				}
 			}
 		}
 	}
+	//set_arch_dep_running(0);
 
 	return res;
 }
@@ -656,7 +631,7 @@ static int tv_ld2(tarval *tv, int bits) {
 #define SHL(a, b) tarval_shl(a, b)
 #define SHR(a, b) tarval_shr(a, b)
 #define ADD(a, b) tarval_add(a, b)
-#define SUB(a, b) tarval_sub(a, b)
+#define SUB(a, b) tarval_sub(a, b, NULL)
 #define MUL(a, b) tarval_mul(a, b)
 #define DIV(a, b) tarval_div(a, b)
 #define MOD(a, b) tarval_mod(a, b)
@@ -847,7 +822,7 @@ static ir_node *replace_div_by_mulh(ir_node *div, tarval *tv) {
 		struct ms mag = magic(tv);
 
 		/* generate the Mulh instruction */
-		c = new_r_Const(current_ir_graph, block, mode, mag.M);
+		c = new_Const(mag.M);
 		q = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);
 
 		/* do we need an Add or Sub */
@@ -858,12 +833,12 @@ static ir_node *replace_div_by_mulh(ir_node *div, tarval *tv) {
 
 		/* Do we need the shift */
 		if (mag.s > 0) {
-			c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s);
-			q    = new_rd_Shrs(dbg, current_ir_graph, block, q, c, mode);
+			c = new_Const_long(mode_Iu, mag.s);
+			q = new_rd_Shrs(dbg, current_ir_graph, block, q, c, mode);
 		}
 
 		/* final */
-		c = new_r_Const_long(current_ir_graph, block, mode_Iu, bits-1);
+		c = new_Const_long(mode_Iu, bits - 1);
 		t = new_rd_Shr(dbg, current_ir_graph, block, q, c, mode);
 
 		q = new_rd_Add(dbg, current_ir_graph, block, q, t, mode);
@@ -872,27 +847,27 @@ static ir_node *replace_div_by_mulh(ir_node *div, tarval *tv) {
 		ir_node *c;
 
 		/* generate the Mulh instruction */
-		c = new_r_Const(current_ir_graph, block, mode, mag.M);
-		q    = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);
+		c = new_Const(mag.M);
+		q = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);
 
 		if (mag.need_add) {
 			if (mag.s > 0) {
 				/* use the GM scheme */
 				t = new_rd_Sub(dbg, current_ir_graph, block, n, q, mode);
 
-				c = new_r_Const(current_ir_graph, block, mode_Iu, get_mode_one(mode_Iu));
+				c = new_Const(get_mode_one(mode_Iu));
 				t = new_rd_Shr(dbg, current_ir_graph, block, t, c, mode);
 
 				t = new_rd_Add(dbg, current_ir_graph, block, t, q, mode);
 
-				c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s-1);
+				c = new_Const_long(mode_Iu, mag.s - 1);
 				q = new_rd_Shr(dbg, current_ir_graph, block, t, c, mode);
 			} else {
 				/* use the default scheme */
 				q = new_rd_Add(dbg, current_ir_graph, block, q, n, mode);
 			}
 		} else if (mag.s > 0) { /* default scheme, shift needed */
-			c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s);
+			c = new_Const_long(mode_Iu, mag.s);
 			q = new_rd_Shr(dbg, current_ir_graph, block, q, c, mode);
 		}
 	}
@@ -908,7 +883,7 @@ ir_node *arch_dep_replace_div_by_const(ir_node *irn) {
 	if (params == NULL || (opts & arch_dep_div_by_const) == 0)
 		return irn;
 
-	if (get_irn_opcode(irn) == iro_Div) {
+	if (is_Div(irn)) {
 		ir_node *c = get_Div_right(irn);
 		ir_node *block, *left;
 		ir_mode *mode;
@@ -917,13 +892,13 @@ ir_node *arch_dep_replace_div_by_const(ir_node *irn) {
 		int n, bits;
 		int k, n_flag;
 
-		if (get_irn_op(c) != op_Const)
+		if (! is_Const(c))
 			return irn;
 
 		tv = get_Const_tarval(c);
 
 		/* check for division by zero */
-		if (classify_tarval(tv) == TV_CLASSIFY_NULL)
+		if (tarval_is_null(tv))
 			return irn;
 
 		left  = get_Div_left(irn);
@@ -952,29 +927,34 @@ ir_node *arch_dep_replace_div_by_const(ir_node *irn) {
 				ir_node *k_node;
 				ir_node *curr = left;
 
-				if (k != 1) {
-					k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
-					curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
-				}
+				/* 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_Const_long(mode_Iu, k - 1);
+						curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
+					}
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
-				curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
+					k_node = new_Const_long(mode_Iu, bits - k);
+					curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 
-				curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
+					curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
+				} else {
+					k_node = left;
+				}
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
+				k_node = new_Const_long(mode_Iu, k);
 				res    = new_rd_Shrs(dbg, current_ir_graph, block, curr, k_node, mode);
 
 				if (n_flag) { /* negate the result */
 					ir_node *k_node;
 
-					k_node = new_r_Const(current_ir_graph, block, mode, get_mode_null(mode));
+					k_node = new_Const(get_mode_null(mode));
 					res = new_rd_Sub(dbg, current_ir_graph, block, k_node, res, mode);
 				}
 			} else {      /* unsigned case */
 				ir_node *k_node;
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
+				k_node = new_Const_long(mode_Iu, k);
 				res    = new_rd_Shr(dbg, current_ir_graph, block, left, k_node, mode);
 			}
 		} else {
@@ -999,7 +979,7 @@ ir_node *arch_dep_replace_mod_by_const(ir_node *irn) {
 	if (params == NULL || (opts & arch_dep_mod_by_const) == 0)
 		return irn;
 
-	if (get_irn_opcode(irn) == iro_Mod) {
+	if (is_Mod(irn)) {
 		ir_node *c = get_Mod_right(irn);
 		ir_node *block, *left;
 		ir_mode *mode;
@@ -1008,13 +988,13 @@ ir_node *arch_dep_replace_mod_by_const(ir_node *irn) {
 		int n, bits;
 		int k;
 
-		if (get_irn_op(c) != op_Const)
+		if (! is_Const(c))
 			return irn;
 
 		tv = get_Const_tarval(c);
 
 		/* check for division by zero */
-		if (classify_tarval(tv) == TV_CLASSIFY_NULL)
+		if (tarval_is_null(tv))
 			return irn;
 
 		left  = get_Mod_left(irn);
@@ -1044,23 +1024,23 @@ ir_node *arch_dep_replace_mod_by_const(ir_node *irn) {
 				ir_node *curr = left;
 
 				if (k != 1) {
-					k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
+					k_node = new_Const_long(mode_Iu, k - 1);
 					curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 				}
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
+				k_node = new_Const_long(mode_Iu, bits - k);
 				curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 
 				curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode, (-1) << k);
+				k_node = new_Const_long(mode, (-1) << k);
 				curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);
 
 				res    = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
 			} else {      /* unsigned case */
 				ir_node *k_node;
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode, (1 << k) - 1);
+				k_node = new_Const_long(mode, (1 << k) - 1);
 				res    = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
 			}
 		} else {
@@ -1093,7 +1073,7 @@ void arch_dep_replace_divmod_by_const(ir_node **div, ir_node **mod, ir_node *irn
 		((opts & (arch_dep_div_by_const|arch_dep_mod_by_const)) != (arch_dep_div_by_const|arch_dep_mod_by_const)))
 		return;
 
-	if (get_irn_opcode(irn) == iro_DivMod) {
+	if (is_DivMod(irn)) {
 		ir_node *c = get_DivMod_right(irn);
 		ir_node *block, *left;
 		ir_mode *mode;
@@ -1102,13 +1082,13 @@ void arch_dep_replace_divmod_by_const(ir_node **div, ir_node **mod, ir_node *irn
 		int n, bits;
 		int k, n_flag;
 
-		if (get_irn_op(c) != op_Const)
+		if (! is_Const(c))
 			return;
 
 		tv = get_Const_tarval(c);
 
 		/* check for division by zero */
-		if (classify_tarval(tv) == TV_CLASSIFY_NULL)
+		if (tarval_is_null(tv))
 			return;
 
 		left  = get_DivMod_left(irn);
@@ -1138,37 +1118,37 @@ void arch_dep_replace_divmod_by_const(ir_node **div, ir_node **mod, ir_node *irn
 				ir_node *curr = left;
 
 				if (k != 1) {
-					k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
+					k_node = new_Const_long(mode_Iu, k - 1);
 					curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 				}
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
+				k_node = new_Const_long(mode_Iu, bits - k);
 				curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 
 				curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 
-				c_k    = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
+				c_k    = new_Const_long(mode_Iu, k);
 
 				*div   = new_rd_Shrs(dbg, current_ir_graph, block, curr, c_k, mode);
 
 				if (n_flag) { /* negate the div result */
 					ir_node *k_node;
 
-					k_node = new_r_Const(current_ir_graph, block, mode, get_mode_null(mode));
+					k_node = new_Const(get_mode_null(mode));
 					*div = new_rd_Sub(dbg, current_ir_graph, block, k_node, *div, mode);
 				}
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode, (-1) << k);
+				k_node = new_Const_long(mode, (-1) << k);
 				curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);
 
 				*mod   = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
 			} else {      /* unsigned case */
 				ir_node *k_node;
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
+				k_node = new_Const_long(mode_Iu, k);
 				*div   = new_rd_Shr(dbg, current_ir_graph, block, left, k_node, mode);
 
-				k_node = new_r_Const_long(current_ir_graph, block, mode, (1 << k) - 1);
+				k_node = new_Const_long(mode, (1 << k) - 1);
 				*mod   = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
 			}
 		} else {
@@ -1196,6 +1176,7 @@ static const ir_settings_arch_dep_t default_params = {
 	1,  /* also use subs */
 	4,  /* maximum shifts */
 	31, /* maximum shift amount */
+	default_evaluate,  /* default evaluator */
 
 	0,  /* allow Mulhs */
 	0,  /* allow Mulus */