From 3d41a5712c4314bf5946fba7f1666742788d2be7 Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Wed, 6 Oct 2004 16:23:03 +0000 Subject: [PATCH] Added Mod/DivMod optimizations [r4064] --- ir/ir/irarch.c | 164 +++++++++++++++++++++++++++++++++++++++++++++++++ ir/ir/irarch.h | 39 +++++++++++- 2 files changed, 202 insertions(+), 1 deletion(-) diff --git a/ir/ir/irarch.c b/ir/ir/irarch.c index fbfbbafd9..ddc240258 100644 --- a/ir/ir/irarch.c +++ b/ir/ir/irarch.c @@ -372,6 +372,170 @@ ir_node *arch_dep_replace_div_with_shifts(ir_node *irn) return res; } +ir_node *arch_dep_replace_mod_with_shifts(ir_node *irn) +{ + ir_node *res = irn; + + /* If the architecture dependent optimizations were not initialized + or this optimization was not enabled. */ + if (params == NULL || (opts & arch_dep_mod_to_shift) == 0) + return irn; + + if (get_irn_opcode(irn) == iro_Mod) { + ir_node *c = get_Mod_right(irn); + ir_node *block, *left; + ir_mode *mode; + tarval *tv; + dbg_info *dbg; + int n, bits; + int i, k, num; + + if (get_irn_op(c) != op_Const) + return irn; + + left = get_Mod_left(irn); + mode = get_irn_mode(left); + block = get_nodes_block(irn); + dbg = get_irn_dbg_info(irn); + tv = get_Const_tarval(c); + + bits = get_mode_size_bits(mode); + n = (bits + 7) / 8; + + for (num = i = 0; i < n; ++i) { + unsigned char v = get_tarval_sub_bits(tv, i); + + if (v) { + int j; + + for (j = 0; j < 8; ++j) + if ((1 << j) & v) { + ++num; + k = 8 * i + j; + } + } + } + + if (num == 1) { /* remainder by 2^k */ + + if (mode_is_signed(mode)) { + ir_node *k_node; + ir_node *curr = left; + + if (k != 1) { + k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k - 1, mode_Iu)); + curr = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode); + } + + k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(bits - k, mode_Iu)); + 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(current_ir_graph, block, mode, new_tarval_from_long((-1) << k, mode)); + 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(current_ir_graph, block, mode, new_tarval_from_long((1 << k) - 1, mode)); + res = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode); + } + } + } + + if (res != irn) + stat_arch_dep_replace_mod_with_shifts(irn); + + return res; +} + +void arch_dep_replace_divmod_with_shifts(ir_node **div, ir_node **mod, ir_node *irn) +{ + *div = *mod = NULL; + + /* If the architecture dependent optimizations were not initialized + or this optimization was not enabled. */ + if (params == NULL || (opts & arch_dep_mod_to_shift) == 0) + return; + + if (get_irn_opcode(irn) == iro_DivMod) { + ir_node *c = get_DivMod_right(irn); + ir_node *block, *left; + ir_mode *mode; + tarval *tv; + dbg_info *dbg; + int n, bits; + int i, k, num; + + if (get_irn_op(c) != op_Const) + return; + + left = get_DivMod_left(irn); + mode = get_irn_mode(left); + block = get_nodes_block(irn); + dbg = get_irn_dbg_info(irn); + tv = get_Const_tarval(c); + + bits = get_mode_size_bits(mode); + n = (bits + 7) / 8; + + for (num = i = 0; i < n; ++i) { + unsigned char v = get_tarval_sub_bits(tv, i); + + if (v) { + int j; + + for (j = 0; j < 8; ++j) + if ((1 << j) & v) { + ++num; + k = 8 * i + j; + } + } + } + + if (num == 1) { /* division & remainder by 2^k */ + + if (mode_is_signed(mode)) { + ir_node *k_node; + ir_node *curr = left; + + if (k != 1) { + k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k - 1, mode_Iu)); + curr = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode); + } + + k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(bits - k, mode_Iu)); + 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(current_ir_graph, block, mode_Iu, new_tarval_from_long(k, mode_Iu)); + *div = new_rd_Shrs(dbg, current_ir_graph, block, curr, k_node, mode); + + k_node = new_r_Const(current_ir_graph, block, mode, new_tarval_from_long((-1) << k, mode)); + 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(current_ir_graph, block, mode_Iu, new_tarval_from_long(k, mode_Iu)); + *div = new_rd_Shl(dbg, current_ir_graph, block, left, k_node, mode); + + k_node = new_r_Const(current_ir_graph, block, mode, new_tarval_from_long((1 << k) - 1, mode)); + *mod = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode); + } + } + } + + if (*div) + stat_arch_dep_replace_DivMod_with_shifts(irn); +} + static const arch_dep_params_t default_params = { 1, /* also use subs */ diff --git a/ir/ir/irarch.h b/ir/ir/irarch.h index 95ba5e972..6b733ed4c 100644 --- a/ir/ir/irarch.h +++ b/ir/ir/irarch.h @@ -45,7 +45,8 @@ const arch_dep_params_t *arch_dep_default_factory(void); typedef enum { arch_dep_none = 0, arch_dep_mul_to_shift = 1, /**< optimize Mul into Shift/Add/Sub */ - arch_dep_div_to_shift = 2 /**< optimize Div into Shift/Add/Mul */ + arch_dep_div_to_shift = 2, /**< optimize Div into Shift/Add/Mul */ + arch_dep_mod_to_shift = 4 /**< optimize Mod into Shift/Add/Mul */ } arch_dep_opts_t; /** @@ -97,4 +98,40 @@ ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn); */ ir_node *arch_dep_replace_div_with_shifts(ir_node *irn); +/** + * Replace Mods with Shifts and Add/Subs. + * This function is driven by the 3 parameters: + * - also_use_subs + * - maximum_shifts + * - highest_shift_amount + * + * If irn is a Div with a Const, The constant is inspected, if it meets the + * requirements of the three variables stated above. If a Shl/Add/Sub + * sequence can be generated, that meets these requirements, this expression + * is returned. In each other case, irn is returned unmodified. + * + * @param irn The Firm node to inspect. + * @return A replacement expression for irn. + */ +ir_node *arch_dep_replace_mod_with_shifts(ir_node *irn); + +/** + * Replace Mods with Shifts and Add/Subs. + * This function is driven by the 3 parameters: + * - also_use_subs + * - maximum_shifts + * - highest_shift_amount + * + * If irn is a Div with a Const, The constant is inspected, if it meets the + * requirements of the three variables stated above. If a Shl/Add/Sub + * sequence can be generated, that meets these requirements, this expression + * is returned. In each other case, irn is returned unmodified. + * + * @param div After call contains the Firm node div result or NULL. + * @param mod After call contains the Firm node mod result or NULL. + * @param irn The Firm node to inspect. + * @return A replacement expression for irn. + */ +void arch_dep_replace_divmod_with_shifts(ir_node **div, ir_node **mod, ir_node *irn); + #endif -- 2.20.1