From d1f024102cea81017877ff94ca27a0840b76fcb3 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Mon, 30 May 2011 23:18:31 +0200 Subject: [PATCH] move integer abs optimisation from backend to the middleend --- ir/be/betranshlp.c | 59 ------------------ ir/be/betranshlp.h | 8 --- ir/be/ia32/bearch_ia32.c | 2 +- ir/be/ia32/ia32_transform.c | 34 +++-------- ir/be/sparc/sparc_transform.c | 21 ------- ir/ir/iropt.c | 109 ++++++++++++++++++++++++++++++++-- ir/ir/iropt_t.h | 6 ++ 7 files changed, 119 insertions(+), 120 deletions(-) diff --git a/ir/be/betranshlp.c b/ir/be/betranshlp.c index 085ab7420..09d65fd90 100644 --- a/ir/be/betranshlp.c +++ b/ir/be/betranshlp.c @@ -433,62 +433,3 @@ void be_transform_graph(ir_graph *irg, arch_pretrans_nodes *func) edges_deactivate(irg); edges_activate(irg); } - -int be_mux_is_abs(ir_node *sel, ir_node *mux_true, ir_node *mux_false) -{ - ir_node *cmp_left; - ir_node *cmp_right; - ir_mode *mode; - ir_relation relation; - - if (!is_Cmp(sel)) - return 0; - - /** - * Note further that these optimization work even for floating point - * with NaN's because -NaN == NaN. - * However, if +0 and -0 is handled differently, we cannot use the Abs/-Abs - * transformations. - */ - mode = get_irn_mode(mux_true); - if (mode_honor_signed_zeros(mode)) - return 0; - - /* must be <, <=, >=, > */ - relation = get_Cmp_relation(sel); - if ((relation & ir_relation_less_greater) == 0) - return 0; - - if (!ir_is_negated_value(mux_true, mux_false)) - return 0; - - /* must be x cmp 0 */ - cmp_right = get_Cmp_right(sel); - if (!is_Const(cmp_right) || !is_Const_null(cmp_right)) - return 0; - - cmp_left = get_Cmp_left(sel); - if (cmp_left == mux_false) { - if (relation & ir_relation_less) { - return 1; - } else { - assert(relation & ir_relation_greater); - return -1; - } - } else if (cmp_left == mux_true) { - if (relation & ir_relation_less) { - return -1; - } else { - assert(relation & ir_relation_greater); - return 1; - } - } - - return 0; -} - -ir_node *be_get_abs_op(ir_node *sel) -{ - ir_node *cmp_left = get_Cmp_left(sel); - return cmp_left; -} diff --git a/ir/be/betranshlp.h b/ir/be/betranshlp.h index 9db5b156b..f31f05fd0 100644 --- a/ir/be/betranshlp.h +++ b/ir/be/betranshlp.h @@ -85,12 +85,4 @@ void be_enqueue_preds(ir_node *node); */ void be_transform_graph(ir_graph *irg, arch_pretrans_nodes *func); -/** - * If Mux(sel, t, f) represents an Abs return 1, if it represents -Abs return - * -1, otherwise 0 - */ -int be_mux_is_abs(ir_node *sel, ir_node *mux_true, ir_node *mux_false); - -ir_node *be_get_abs_op(ir_node *sel); - #endif diff --git a/ir/be/ia32/bearch_ia32.c b/ir/be/ia32/bearch_ia32.c index d2780f31c..090e243fc 100644 --- a/ir/be/ia32/bearch_ia32.c +++ b/ir/be/ia32/bearch_ia32.c @@ -1952,7 +1952,7 @@ static int ia32_is_mux_allowed(ir_node *sel, ir_node *mux_false, if (get_mode_size_bits(mode) > 32) return false; /* we can handle Abs for all modes and compares (except 64bit) */ - if (be_mux_is_abs(sel, mux_true, mux_false) != 0) + if (ir_mux_is_abs(sel, mux_true, mux_false) != 0) return true; /* we can't handle MuxF yet */ if (mode_is_float(mode)) diff --git a/ir/be/ia32/ia32_transform.c b/ir/be/ia32/ia32_transform.c index 71fcf09bc..7732598b7 100644 --- a/ir/be/ia32/ia32_transform.c +++ b/ir/be/ia32/ia32_transform.c @@ -1998,30 +1998,6 @@ static ir_node *create_abs(dbg_info *dbgi, ir_node *block, ir_node *op, SET_IA32_ORIG_NODE(new_node, node); } } - } else { - ir_node *xorn; - ir_node *sign_extension; - - if (get_mode_size_bits(mode) == 32) { - new_op = be_transform_node(op); - } else { - new_op = create_I2I_Conv(mode, mode_Is, dbgi, block, op, node); - } - - sign_extension = create_sex_32_64(dbgi, new_block, new_op, node); - - xorn = new_bd_ia32_Xor(dbgi, new_block, noreg_GP, noreg_GP, - nomem, new_op, sign_extension); - SET_IA32_ORIG_NODE(xorn, node); - - if (negate) { - new_node = new_bd_ia32_Sub(dbgi, new_block, noreg_GP, noreg_GP, - nomem, sign_extension, xorn); - } else { - new_node = new_bd_ia32_Sub(dbgi, new_block, noreg_GP, noreg_GP, - nomem, xorn, sign_extension); - } - SET_IA32_ORIG_NODE(new_node, node); } return new_node; @@ -3475,9 +3451,15 @@ static ir_node *gen_Mux(ir_node *node) assert(get_irn_mode(sel) == mode_b); - is_abs = be_mux_is_abs(sel, mux_true, mux_false); + is_abs = ir_mux_is_abs(sel, mux_true, mux_false); if (is_abs != 0) { - return create_abs(dbgi, block, be_get_abs_op(sel), is_abs < 0, node); + if (ia32_mode_needs_gp_reg(mode)) { + ir_fprintf(stderr, "Optimisation warning: Integer abs %+F not transformed\n", + node); + } else { + ir_node *op = ir_get_abs_op(sel, mux_true, mux_false); + return create_abs(dbgi, block, op, is_abs < 0, node); + } } /* Note: a Mux node uses a Load two times IFF it's used in the compare AND in the result */ diff --git a/ir/be/sparc/sparc_transform.c b/ir/be/sparc/sparc_transform.c index 36a98639f..669c05be2 100644 --- a/ir/be/sparc/sparc_transform.c +++ b/ir/be/sparc/sparc_transform.c @@ -784,27 +784,6 @@ static ir_node *gen_Div(ir_node *node) return res; } -#if 0 -static ir_node *gen_Abs(ir_node *node) -{ - ir_mode *const mode = get_irn_mode(node); - - if (mode_is_float(mode)) { - return gen_helper_unfpop(node, mode, new_bd_sparc_fabs_s, - new_bd_sparc_fabs_d, new_bd_sparc_fabs_q); - } else { - ir_node *const block = be_transform_node(get_nodes_block(node)); - dbg_info *const dbgi = get_irn_dbg_info(node); - ir_node *const op = get_Abs_op(node); - ir_node *const new_op = be_transform_node(op); - ir_node *const sra = new_bd_sparc_Sra_imm(dbgi, block, new_op, NULL, 31); - ir_node *const xor = new_bd_sparc_Xor_reg(dbgi, block, new_op, sra); - ir_node *const sub = new_bd_sparc_Sub_reg(dbgi, block, xor, sra); - return sub; - } -} -#endif - /** * Transforms a Not node. * diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c index dc2907678..af862a246 100644 --- a/ir/ir/iropt.c +++ b/ir/ir/iropt.c @@ -5306,20 +5306,119 @@ int ir_is_negated_value(const ir_node *a, const ir_node *b) return false; } +static const ir_node *skip_upconv(const ir_node *node) +{ + while (is_Conv(node)) { + ir_mode *mode = get_irn_mode(node); + const ir_node *op = get_Conv_op(node); + ir_mode *op_mode = get_irn_mode(op); + if (!smaller_mode(op_mode, mode)) + break; + node = op; + } + return node; +} + +int ir_mux_is_abs(const ir_node *sel, const ir_node *mux_true, + const ir_node *mux_false) +{ + ir_node *cmp_left; + ir_node *cmp_right; + ir_mode *mode; + ir_relation relation; + + if (!is_Cmp(sel)) + return 0; + + /** + * Note further that these optimization work even for floating point + * with NaN's because -NaN == NaN. + * However, if +0 and -0 is handled differently, we cannot use the Abs/-Abs + * transformations. + */ + mode = get_irn_mode(mux_true); + if (mode_honor_signed_zeros(mode)) + return 0; + + /* must be <, <=, >=, > */ + relation = get_Cmp_relation(sel); + if ((relation & ir_relation_less_greater) == 0) + return 0; + + if (!ir_is_negated_value(mux_true, mux_false)) + return 0; + + mux_true = skip_upconv(mux_true); + mux_false = skip_upconv(mux_false); + + /* must be x cmp 0 */ + cmp_right = get_Cmp_right(sel); + if (!is_Const(cmp_right) || !is_Const_null(cmp_right)) + return 0; + + cmp_left = get_Cmp_left(sel); + if (cmp_left == mux_false) { + if (relation & ir_relation_less) { + return 1; + } else { + assert(relation & ir_relation_greater); + return -1; + } + } else if (cmp_left == mux_true) { + if (relation & ir_relation_less) { + return -1; + } else { + assert(relation & ir_relation_greater); + return 1; + } + } + + return 0; +} + +ir_node *ir_get_abs_op(const ir_node *sel, ir_node *mux_true, + ir_node *mux_false) +{ + ir_node *cmp_left = get_Cmp_left(sel); + return cmp_left == skip_upconv(mux_false) ? mux_false : mux_true; +} + /** * Optimize a Mux into some simpler cases. */ static ir_node *transform_node_Mux(ir_node *n) { - ir_node *oldn = n, *sel = get_Mux_sel(n); - ir_mode *mode = get_irn_mode(n); - ir_node *t = get_Mux_true(n); - ir_node *f = get_Mux_false(n); - ir_graph *irg = get_irn_irg(n); + ir_node *oldn = n; + ir_node *sel = get_Mux_sel(n); + ir_mode *mode = get_irn_mode(n); + ir_node *t = get_Mux_true(n); + ir_node *f = get_Mux_false(n); + ir_graph *irg = get_irn_irg(n); if (is_irg_state(irg, IR_GRAPH_STATE_KEEP_MUX)) return n; + /* implement integer abs: abs(x) = x^(x >>s 31) - (x >>s 31) */ + if (get_mode_arithmetic(mode) == irma_twos_complement) { + int abs = ir_mux_is_abs(sel, t, f); + if (abs != 0) { + dbg_info *dbgi = get_irn_dbg_info(n); + ir_node *block = get_nodes_block(n); + ir_node *op = ir_get_abs_op(sel, t, f); + int bits = get_mode_size_bits(mode); + ir_node *shiftconst = new_r_Const_long(irg, mode_Iu, bits-1); + ir_node *sext = new_rd_Shrs(dbgi, block, op, shiftconst, mode); + ir_node *xorn = new_rd_Eor(dbgi, block, op, sext, mode); + ir_node *res; + if (abs > 0) { + res = new_rd_Sub(dbgi, block, xorn, sext, mode); + } else { + res = new_rd_Sub(dbgi, block, sext, xorn, mode); + } + return res; + } + } + if (is_Mux(t)) { ir_node* block = get_nodes_block(n); ir_node* c0 = sel; diff --git a/ir/ir/iropt_t.h b/ir/ir/iropt_t.h index af41f0208..dd7964888 100644 --- a/ir/ir/iropt_t.h +++ b/ir/ir/iropt_t.h @@ -136,4 +136,10 @@ bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode); */ ir_op_ops *firm_set_default_operations(unsigned code, ir_op_ops *ops); +int ir_mux_is_abs(const ir_node *sel, const ir_node *mux_true, + const ir_node *mux_false); + +ir_node *ir_get_abs_op(const ir_node *sel, ir_node *mux_true, + ir_node *mux_false); + #endif -- 2.20.1