match.pd: Avoid introducing UB in the ((X /[ex] C1) +- C2) * (C1 * C3) simplification [PR117692]
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-arm |
fail
|
Patch failed to apply
|
| linaro-tcwg-bot/tcwg_gcc_check--master-aarch64 |
success
|
Test passed
|
Commit Message
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?
2024-11-27 Jakub Jelinek <jakub@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.
Jakub
Comments
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 <jakub@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
>
>
@@ -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)
@@ -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); }
@@ -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" } } */
@@ -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;
+}