On Wed, 27 Nov 2024, Jakub Jelinek wrote:
> Hi!
>
> As the pr117692.c testcase shows, the generalized pattern can introduce
> UB when there wasn't any.
> The old pattern was I believe correct, it is as if in the new
> pattern C3 was always 1 and I don't see how that could have introduced
> UB.
> But if type is signed and C3 (aka factor) isn't 1 and for + X and C2
> could have different sign or for - X and C2 could have the same sign,
> when doing the addition/subtraction first the absolute value could
> decrease, while if first multiplying by C3 we could invoke UB already
> during that multiplication.
>
> The following patch fixes it by going through the casts to utype if
> ranger (get_range_pos_neg) detects the sign compared to sign of C2
> (INTEGER_CST) could be the same or could be different depending on op
> because then the absolute value will not increase.
>
> Other possibility (perhaps as another check if this check doesn't succeed)
> would be to test whether X * C3 could actually overflow.
> vr-values.cc has check_for_binary_op_overflow (currently not exported)
> which I think does what we'd need to check, if it returns true and sets
> ovf to false.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
As improvement, if required we could do the range evaluation or
perform the simplified arithmetic in an unsigned type and cast back.
Thanks,
Richard.
> 2024-11-27 Jakub Jelinek <ja...@redhat.com>
>
> PR tree-optimization/117692
> * tree.cc (get_range_pos_neg): Adjust function comment, use
> non-negative instead of positive.
> * match.pd
> (((X /[ex] C1) +- C2) * (C1 * C3) -> (X * C3) +- (C1 * C2 * C3)):
> Use casts to utype if type is signed, factor isn't 1 and
> C1 and C2 could have different sign for + or could have the
> same sign for -.
>
> * gcc.dg/tree-ssa/mulexactdiv-5.c: Expect 8 nop_exprs.
> * gcc.dg/tree-ssa/pr117692.c: New test.
>
> --- gcc/tree.cc.jj 2024-11-23 13:00:31.615980802 +0100
> +++ gcc/tree.cc 2024-11-26 13:50:45.910803860 +0100
> @@ -14510,8 +14510,8 @@ verify_type (const_tree t)
>
>
> /* Return 1 if ARG interpreted as signed in its precision is known to be
> - always positive or 2 if ARG is known to be always negative, or 3 if
> - ARG may be positive or negative. */
> + always non-negative or 2 if ARG is known to be always negative, or 3 if
> + ARG may be non-negative or negative. */
>
> int
> get_range_pos_neg (tree arg)
> --- gcc/match.pd.jj 2024-11-26 09:37:32.563906412 +0100
> +++ gcc/match.pd 2024-11-26 18:36:33.037742888 +0100
> @@ -5577,7 +5577,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && TREE_CODE (@3) == INTEGER_CST
> && (mul = wi::mul (wi::to_wide (@2), wi::to_wide (@3),
> TYPE_SIGN (type), &overflow),
> - !overflow))
> + !overflow)
> + && (TYPE_UNSIGNED (type)
> + /* Not using unsigned arithmetics is unsafe if factor
> + isn't 1 and if for op plus @0 and @2 could have different
> + sign or for op minus @0 and @2 could have the same sign. */
> + || known_eq (factor, 1)
> + || (get_range_pos_neg (@0)
> + | (((op == PLUS_EXPR) ^ (tree_int_cst_sgn (@2) < 0))
> + ? 1 : 2)) != 3))
> (op (mult @0 { wide_int_to_tree (type, factor); })
> { wide_int_to_tree (type, mul); })
> (with { tree utype = unsigned_type_for (type); }
> --- gcc/testsuite/gcc.dg/tree-ssa/mulexactdiv-5.c.jj 2024-10-24
> 18:53:41.438042287 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/mulexactdiv-5.c 2024-11-26
> 14:25:07.507313308 +0100
> @@ -18,7 +18,7 @@ TEST_CMP (f4, 8, 4, 200)
>
> /* { dg-final { scan-tree-dump-not {<[a-z]*_div_expr,} "optimized" } } */
> /* { dg-final { scan-tree-dump-not {<rshift_expr,} "optimized" } } */
> -/* { dg-final { scan-tree-dump-not {<nop_expr,} "optimized" } } */
> +/* { dg-final { scan-tree-dump-times {<nop_expr,} 8 "optimized" } } */
> /* { dg-final { scan-tree-dump {<mult_expr, [^,]*, [^,]*, 3,} "optimized" }
> } */
> /* { dg-final { scan-tree-dump {<mult_expr, [^,]*, [^,]*, 5,} "optimized" }
> } */
> /* { dg-final { scan-tree-dump {<mult_expr, [^,]*, [^,]*, 20,} "optimized" }
> } */
> --- gcc/testsuite/gcc.dg/tree-ssa/pr117692.c.jj 2024-11-26
> 14:16:46.689274363 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr117692.c 2024-11-26 14:18:55.161491240
> +0100
> @@ -0,0 +1,17 @@
> +/* PR tree-optimization/117692 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp1" } */
> +/* { dg-final { scan-tree-dump " \\\* 25;" "vrp1" } } */
> +/* { dg-final { scan-tree-dump " \\\+ 800;" "vrp1" } } */
> +/* { dg-final { scan-tree-dump " = \\\(unsigned int\\\) " "vrp1" } } */
> +/* { dg-final { scan-tree-dump " = \\\(int\\\) " "vrp1" } } */
> +
> +int
> +foo (int x)
> +{
> + if (x & 7)
> + __builtin_unreachable ();
> + x /= 8;
> + x += 4;
> + return x * 200;
> +}
>
> Jakub
>
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
