X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firarch.c;h=04a3aeb2b178001302122c9822429dde55f6f211;hb=8f355cb9b3d20c10f71d1b1e17cbf59a51ced83b;hp=4684d5057ee8f391969481d6409d54a7b8228ced;hpb=ae91f67c6a657866c2c7581e024cad4748b90775;p=libfirm diff --git a/ir/ir/irarch.c b/ir/ir/irarch.c index 4684d5057..04a3aeb2b 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. * @@ -51,6 +51,7 @@ #include "irhooks.h" #include "ircons.h" #include "irarch.h" +#include "irflag.h" #undef DEB @@ -69,40 +70,11 @@ 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) { @@ -123,7 +95,7 @@ typedef struct instruction instruction; struct instruction { insn_kind kind; /**< the instruction kind */ instruction *in[2]; /**< the ins */ - int shift_count; /**< shift count for LEA and SHIFT */ + unsigned shift_count; /**< shift count for LEA and SHIFT */ ir_node *irn; /**< the generated node for this instruction if any. */ int costs; /**< the costs for this instruction */ }; @@ -134,7 +106,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 */ @@ -148,9 +120,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; @@ -159,7 +134,7 @@ static int default_evaluate(insn_kind kind, tarval *tv) { /** * emit a LEA (or an Add) instruction */ -static instruction *emit_LEA(mul_env *env, instruction *a, instruction *b, int shift) { +static instruction *emit_LEA(mul_env *env, instruction *a, instruction *b, unsigned shift) { instruction *res = obstack_alloc(&env->obst, sizeof(*res)); res->kind = shift > 0 ? LEA : ADD; res->in[0] = a; @@ -171,11 +146,17 @@ static instruction *emit_LEA(mul_env *env, instruction *a, instruction *b, int s } /** - * emit a SHIFT (or an Add) instruction + * emit a SHIFT (or an Add or a Zero) instruction */ -static instruction *emit_SHIFT(mul_env *env, instruction *a, int shift) { +static instruction *emit_SHIFT(mul_env *env, instruction *a, unsigned shift) { instruction *res = obstack_alloc(&env->obst, sizeof(*res)); - if (shift != 1) { + if (shift == env->bits) { + /* a 2^bits with bits resolution is a zero */ + res->kind = ZERO; + res->in[0] = NULL; + res->in[1] = NULL; + res->shift_count = 0; + } else if (shift != 1) { res->kind = SHIFT; res->in[0] = a; res->in[1] = NULL; @@ -248,8 +229,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 */ @@ -263,9 +244,7 @@ static int calculate_gain(unsigned char *R, int r) { idx = i; } } - if (max_gain > 0) - return idx; - return -1; + return idx; } /** @@ -338,17 +317,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); @@ -370,7 +355,7 @@ static instruction *decompose_mul(mul_env *env, unsigned char *R, int r, tarval if (gain > 0) { instruction *instr1, *instr2; unsigned char *R1, *R2; - int r1, r2, i, k; + int r1, r2, i, k, j; R1 = complement_condensed(env, R, r, gain, &r1); r2 = r - gain + 1; @@ -382,8 +367,15 @@ static instruction *decompose_mul(mul_env *env, unsigned char *R, int r, tarval } R2[0] = k; R2[1] = R[gain] - 1; - for (i = gain; i < r; ++i) { - R2[i] = R[i]; + j = 2; + if (R2[1] == 0) { + /* Two identical bits: normalize */ + ++R2[0]; + --j; + --r2; + } + for (i = gain + 1; i < r; ++i) { + R2[j++] = R[i]; } instr1 = decompose_mul(env, R1, r1, NULL); @@ -414,6 +406,8 @@ static instruction *decompose_mul(mul_env *env, unsigned char *R, int r, tarval return basic_decompose_mul(env, R, r, N); } +#define IMAX(a,b) ((a) > (b) ? (a) : (b)) + /** * basic decomposition routine */ @@ -422,7 +416,7 @@ static instruction *basic_decompose_mul(mul_env *env, unsigned char *R, int r, t unsigned t; if (R[0] == 0) { /* Case 1 */ - t = R[1] > max(env->max_S, R[1]); + t = R[1] > IMAX(env->max_S, R[1]); R[1] -= t; Ns = decompose_mul(env, &R[1], r - 1, N); return emit_LEA(env, env->root, Ns, t); @@ -470,6 +464,8 @@ static ir_node *build_graph(mul_env *env, instruction *inst) { l = build_graph(env, inst->in[0]); 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)); default: assert(0); return NULL; @@ -508,6 +504,9 @@ static int evaluate_insn(mul_env *env, instruction *inst) { costs += env->evaluate(inst->kind, NULL); inst->costs = costs; return costs; + case ZERO: + inst->costs = costs = env->evaluate(inst->kind, NULL); + return costs; default: assert(0); return 0; @@ -535,7 +534,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; @@ -571,31 +570,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; } @@ -899,7 +901,7 @@ ir_node *arch_dep_replace_div_by_const(ir_node *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); @@ -990,7 +992,7 @@ ir_node *arch_dep_replace_mod_by_const(ir_node *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); @@ -1084,7 +1086,7 @@ void arch_dep_replace_divmod_by_const(ir_node **div, ir_node **mod, ir_node *irn 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); @@ -1172,6 +1174,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 */