Message ID | 20200618093620.GP8462@tucnak |
---|---|
State | New |
Headers | show |
Series | phiopt: Improve minmax optimization [PR95699] | expand |
On Thu, 18 Jun 2020, Jakub Jelinek wrote: > Hi! > > As discussed in the PR, the > x < 0x80000000U to (int) x >= 0 > optimization stands in the way of minmax_replacement optimization, > so for comparisons with most of the constants it works well, but when the > above mentioned optimization triggers, it is unable to do it. > The match.pd (cond (cmp (convert? x) c1) (op x c2) c3) -> (op (minmax x c1) c2) > optimization is able to look through that and this patch > teaches minmax_replacement about it too. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? OK. I wonder if we can leverage gimple_build or gimple_match_op::resimplify to move the actual pattern matching to match.pd completely in at least part of phiopt? We'd feed a COND_EXPR to the matcher and similar to maybe_fold_comparisons_from_match_pd we'd need one "on stack" GIMPLE stmt for the comparison to avoid building it as GENERIC tree (which for COND_EXPR would of course also work up to now). Thanks, Richard. > 2020-06-18 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/95699 > * tree-ssa-phiopt.c (minmax_replacement): Treat (signed int)x < 0 > as x > INT_MAX and (signed int)x >= 0 as x <= INT_MAX. Move variable > declarations to the statements that set them where possible. > > * gcc.dg/tree-ssa/pr95699.c: New test. > > --- gcc/tree-ssa-phiopt.c.jj 2020-06-05 10:42:40.792893013 +0200 > +++ gcc/tree-ssa-phiopt.c 2020-06-17 13:36:20.600659487 +0200 > @@ -1363,22 +1363,21 @@ minmax_replacement (basic_block cond_bb, > edge e0, edge e1, gimple *phi, > tree arg0, tree arg1) > { > - tree result, type, rhs; > - gcond *cond; > + tree result; > edge true_edge, false_edge; > - enum tree_code cmp, minmax, ass_code; > - tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false; > + enum tree_code minmax, ass_code; > + tree smaller, larger, arg_true, arg_false; > gimple_stmt_iterator gsi, gsi_from; > > - type = TREE_TYPE (PHI_RESULT (phi)); > + tree type = TREE_TYPE (PHI_RESULT (phi)); > > /* The optimization may be unsafe due to NaNs. */ > if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type)) > return false; > > - cond = as_a <gcond *> (last_stmt (cond_bb)); > - cmp = gimple_cond_code (cond); > - rhs = gimple_cond_rhs (cond); > + gcond *cond = as_a <gcond *> (last_stmt (cond_bb)); > + enum tree_code cmp = gimple_cond_code (cond); > + tree rhs = gimple_cond_rhs (cond); > > /* Turn EQ/NE of extreme values to order comparisons. */ > if ((cmp == NE_EXPR || cmp == EQ_EXPR) > @@ -1401,8 +1400,8 @@ minmax_replacement (basic_block cond_bb, > > /* This transformation is only valid for order comparisons. Record which > operand is smaller/larger if the result of the comparison is true. */ > - alt_smaller = NULL_TREE; > - alt_larger = NULL_TREE; > + tree alt_smaller = NULL_TREE; > + tree alt_larger = NULL_TREE; > if (cmp == LT_EXPR || cmp == LE_EXPR) > { > smaller = gimple_cond_lhs (cond); > @@ -1463,6 +1462,50 @@ minmax_replacement (basic_block cond_bb, > else > return false; > > + /* Handle the special case of (signed_type)x < 0 being equivalent > + to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent > + to x <= MAX_VAL(signed_type). */ > + if ((cmp == GE_EXPR || cmp == LT_EXPR) > + && INTEGRAL_TYPE_P (type) > + && TYPE_UNSIGNED (type) > + && integer_zerop (rhs)) > + { > + tree op = gimple_cond_lhs (cond); > + if (TREE_CODE (op) == SSA_NAME > + && INTEGRAL_TYPE_P (TREE_TYPE (op)) > + && !TYPE_UNSIGNED (TREE_TYPE (op))) > + { > + gimple *def_stmt = SSA_NAME_DEF_STMT (op); > + if (gimple_assign_cast_p (def_stmt)) > + { > + tree op1 = gimple_assign_rhs1 (def_stmt); > + if (INTEGRAL_TYPE_P (TREE_TYPE (op1)) > + && TYPE_UNSIGNED (TREE_TYPE (op1)) > + && (TYPE_PRECISION (TREE_TYPE (op)) > + == TYPE_PRECISION (TREE_TYPE (op1))) > + && useless_type_conversion_p (type, TREE_TYPE (op1))) > + { > + wide_int w1 = wi::max_value (TREE_TYPE (op)); > + wide_int w2 = wi::add (w1, 1); > + if (cmp == LT_EXPR) > + { > + larger = op1; > + smaller = wide_int_to_tree (TREE_TYPE (op1), w1); > + alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2); > + alt_larger = NULL_TREE; > + } > + else > + { > + smaller = op1; > + larger = wide_int_to_tree (TREE_TYPE (op1), w1); > + alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2); > + alt_smaller = NULL_TREE; > + } > + } > + } > + } > + } > + > /* We need to know which is the true edge and which is the false > edge so that we know if have abs or negative abs. */ > extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); > --- gcc/testsuite/gcc.dg/tree-ssa/pr95699.c.jj 2020-06-17 13:45:31.308686080 +0200 > +++ gcc/testsuite/gcc.dg/tree-ssa/pr95699.c 2020-06-17 13:44:29.715577853 +0200 > @@ -0,0 +1,39 @@ > +/* PR tree-optimization/95699 */ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */ > +/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */ > +/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */ > +/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */ > + > +unsigned long long > +f1 (unsigned long long x) > +{ > + if (x < 0x7fffffffffffffffULL) > + x = 0x7fffffffffffffffULL; > + return x; > +} > + > +unsigned long long > +f2 (unsigned long long x) > +{ > + if (x < 0x8000000000000000ULL) > + x = 0x8000000000000000ULL; > + return x; > +} > + > +unsigned long long > +f3 (unsigned long long x) > +{ > + if (x >= 0x7fffffffffffffffULL) > + x = 0x7fffffffffffffffULL; > + return x; > +} > + > +unsigned long long > +f4 (unsigned long long x) > +{ > + if (x >= 0x8000000000000000ULL) > + x = 0x8000000000000000ULL; > + return x; > +} > > Jakub > >
--- gcc/tree-ssa-phiopt.c.jj 2020-06-05 10:42:40.792893013 +0200 +++ gcc/tree-ssa-phiopt.c 2020-06-17 13:36:20.600659487 +0200 @@ -1363,22 +1363,21 @@ minmax_replacement (basic_block cond_bb, edge e0, edge e1, gimple *phi, tree arg0, tree arg1) { - tree result, type, rhs; - gcond *cond; + tree result; edge true_edge, false_edge; - enum tree_code cmp, minmax, ass_code; - tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false; + enum tree_code minmax, ass_code; + tree smaller, larger, arg_true, arg_false; gimple_stmt_iterator gsi, gsi_from; - type = TREE_TYPE (PHI_RESULT (phi)); + tree type = TREE_TYPE (PHI_RESULT (phi)); /* The optimization may be unsafe due to NaNs. */ if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type)) return false; - cond = as_a <gcond *> (last_stmt (cond_bb)); - cmp = gimple_cond_code (cond); - rhs = gimple_cond_rhs (cond); + gcond *cond = as_a <gcond *> (last_stmt (cond_bb)); + enum tree_code cmp = gimple_cond_code (cond); + tree rhs = gimple_cond_rhs (cond); /* Turn EQ/NE of extreme values to order comparisons. */ if ((cmp == NE_EXPR || cmp == EQ_EXPR) @@ -1401,8 +1400,8 @@ minmax_replacement (basic_block cond_bb, /* This transformation is only valid for order comparisons. Record which operand is smaller/larger if the result of the comparison is true. */ - alt_smaller = NULL_TREE; - alt_larger = NULL_TREE; + tree alt_smaller = NULL_TREE; + tree alt_larger = NULL_TREE; if (cmp == LT_EXPR || cmp == LE_EXPR) { smaller = gimple_cond_lhs (cond); @@ -1463,6 +1462,50 @@ minmax_replacement (basic_block cond_bb, else return false; + /* Handle the special case of (signed_type)x < 0 being equivalent + to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent + to x <= MAX_VAL(signed_type). */ + if ((cmp == GE_EXPR || cmp == LT_EXPR) + && INTEGRAL_TYPE_P (type) + && TYPE_UNSIGNED (type) + && integer_zerop (rhs)) + { + tree op = gimple_cond_lhs (cond); + if (TREE_CODE (op) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (op)) + && !TYPE_UNSIGNED (TREE_TYPE (op))) + { + gimple *def_stmt = SSA_NAME_DEF_STMT (op); + if (gimple_assign_cast_p (def_stmt)) + { + tree op1 = gimple_assign_rhs1 (def_stmt); + if (INTEGRAL_TYPE_P (TREE_TYPE (op1)) + && TYPE_UNSIGNED (TREE_TYPE (op1)) + && (TYPE_PRECISION (TREE_TYPE (op)) + == TYPE_PRECISION (TREE_TYPE (op1))) + && useless_type_conversion_p (type, TREE_TYPE (op1))) + { + wide_int w1 = wi::max_value (TREE_TYPE (op)); + wide_int w2 = wi::add (w1, 1); + if (cmp == LT_EXPR) + { + larger = op1; + smaller = wide_int_to_tree (TREE_TYPE (op1), w1); + alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2); + alt_larger = NULL_TREE; + } + else + { + smaller = op1; + larger = wide_int_to_tree (TREE_TYPE (op1), w1); + alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2); + alt_smaller = NULL_TREE; + } + } + } + } + } + /* We need to know which is the true edge and which is the false edge so that we know if have abs or negative abs. */ extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); --- gcc/testsuite/gcc.dg/tree-ssa/pr95699.c.jj 2020-06-17 13:45:31.308686080 +0200 +++ gcc/testsuite/gcc.dg/tree-ssa/pr95699.c 2020-06-17 13:44:29.715577853 +0200 @@ -0,0 +1,39 @@ +/* PR tree-optimization/95699 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */ +/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */ +/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */ +/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */ + +unsigned long long +f1 (unsigned long long x) +{ + if (x < 0x7fffffffffffffffULL) + x = 0x7fffffffffffffffULL; + return x; +} + +unsigned long long +f2 (unsigned long long x) +{ + if (x < 0x8000000000000000ULL) + x = 0x8000000000000000ULL; + return x; +} + +unsigned long long +f3 (unsigned long long x) +{ + if (x >= 0x7fffffffffffffffULL) + x = 0x7fffffffffffffffULL; + return x; +} + +unsigned long long +f4 (unsigned long long x) +{ + if (x >= 0x8000000000000000ULL) + x = 0x8000000000000000ULL; + return x; +}