fold-const: Punt on MULT_EXPR in extract_muldiv MIN/MAX_EXPR case [PR111151]
Commit Message
Hi!
As I've tried to explain in the comments, the extract_muldiv_1
MIN/MAX_EXPR optimization is wrong for code == MULT_EXPR.
If the multiplication is done in unsigned type or in signed
type with -fwrapv, it is fairly obvious that max (a, b) * c
in many cases isn't equivalent to max (a * c, b * c) (or min if c is
negative) due to overflows, but even for signed with undefined overflow,
the optimization could turn something without UB in it (where
say a * c invokes UB, but max (or min) picks the other operand where
b * c doesn't).
As for division/modulo, I think it is in most cases safe, except if
the problematic INT_MIN / -1 case could be triggered, but we can
just punt for MAX_EXPR because for MIN_EXPR if one operand is INT_MIN,
we'd pick that operand already. It is just for completeness, match.pd
already has an optimization which turns x / -1 into -x, so the division
by zero is mostly theoretical. That is also why in the testcase the
i case isn't actually miscompiled without the patch, while the c and f
cases are.
Bootstrapped/regtested on x86_64-linux and i686-linux, additionally
bootstrapped/regtested on x86_64-linux with statistics gathering when
the patch changes behavior and it is solely on the new testcase and
nothing else during the bootstrap/regtest. Ok for trunk?
2024-03-26 Jakub Jelinek <jakub@redhat.com>
PR middle-end/111151
* fold-const.cc (extract_muldiv_1) <case MAX_EXPR>: Punt for
MULT_EXPR altogether, or for MAX_EXPR if c is -1.
* gcc.c-torture/execute/pr111151.c: New test.
Jakub
Comments
On Tue, 26 Mar 2024, Jakub Jelinek wrote:
> Hi!
>
> As I've tried to explain in the comments, the extract_muldiv_1
> MIN/MAX_EXPR optimization is wrong for code == MULT_EXPR.
> If the multiplication is done in unsigned type or in signed
> type with -fwrapv, it is fairly obvious that max (a, b) * c
> in many cases isn't equivalent to max (a * c, b * c) (or min if c is
> negative) due to overflows, but even for signed with undefined overflow,
> the optimization could turn something without UB in it (where
> say a * c invokes UB, but max (or min) picks the other operand where
> b * c doesn't).
> As for division/modulo, I think it is in most cases safe, except if
> the problematic INT_MIN / -1 case could be triggered, but we can
> just punt for MAX_EXPR because for MIN_EXPR if one operand is INT_MIN,
> we'd pick that operand already. It is just for completeness, match.pd
> already has an optimization which turns x / -1 into -x, so the division
> by zero is mostly theoretical. That is also why in the testcase the
> i case isn't actually miscompiled without the patch, while the c and f
> cases are.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, additionally
> bootstrapped/regtested on x86_64-linux with statistics gathering when
> the patch changes behavior and it is solely on the new testcase and
> nothing else during the bootstrap/regtest. Ok for trunk?
OK.
Thanks,
Richard.
> 2024-03-26 Jakub Jelinek <jakub@redhat.com>
>
> PR middle-end/111151
> * fold-const.cc (extract_muldiv_1) <case MAX_EXPR>: Punt for
> MULT_EXPR altogether, or for MAX_EXPR if c is -1.
>
> * gcc.c-torture/execute/pr111151.c: New test.
>
> --- gcc/fold-const.cc.jj 2024-03-11 09:42:04.544588951 +0100
> +++ gcc/fold-const.cc 2024-03-25 11:48:12.133625285 +0100
> @@ -7104,6 +7104,27 @@ extract_muldiv_1 (tree t, tree c, enum t
> if (TYPE_UNSIGNED (ctype) != TYPE_UNSIGNED (type))
> break;
>
> + /* Punt for multiplication altogether.
> + MAX (1U + INT_MAX, 1U) * 2U is not equivalent to
> + MAX ((1U + INT_MAX) * 2U, 1U * 2U), the former is
> + 0U, the latter is 2U.
> + MAX (INT_MIN / 2, 0) * -2 is not equivalent to
> + MIN (INT_MIN / 2 * -2, 0 * -2), the former is
> + well defined 0, the latter invokes UB.
> + MAX (INT_MIN / 2, 5) * 5 is not equivalent to
> + MAX (INT_MIN / 2 * 5, 5 * 5), the former is
> + well defined 25, the latter invokes UB. */
> + if (code == MULT_EXPR)
> + break;
> + /* For division/modulo, punt on c being -1 for MAX, as
> + MAX (INT_MIN, 0) / -1 is not equivalent to
> + MIN (INT_MIN / -1, 0 / -1), the former is well defined
> + 0, the latter invokes UB (or for -fwrapv is INT_MIN).
> + MIN (INT_MIN, 0) / -1 already invokes UB, so the
> + transformation won't make it worse. */
> + else if (tcode == MAX_EXPR && integer_minus_onep (c))
> + break;
> +
> /* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
> sub_strict_overflow_p = false;
> if ((t1 = extract_muldiv (op0, c, code, wide_type,
> --- gcc/testsuite/gcc.c-torture/execute/pr111151.c.jj 2024-03-25 11:50:27.199744988 +0100
> +++ gcc/testsuite/gcc.c-torture/execute/pr111151.c 2024-03-26 10:41:51.003384032 +0100
> @@ -0,0 +1,21 @@
> +/* PR middle-end/111151 */
> +
> +int
> +main ()
> +{
> + unsigned a = (1U + __INT_MAX__) / 2U;
> + unsigned b = 1U;
> + unsigned c = (a * 2U > b * 2U ? a * 2U : b * 2U) * 2U;
> + if (c != 0U)
> + __builtin_abort ();
> + int d = (-__INT_MAX__ - 1) / 2;
> + int e = 10;
> + int f = (d * 2 > e * 5 ? d * 2 : e * 5) * 6;
> + if (f != 120)
> + __builtin_abort ();
> + int g = (-__INT_MAX__ - 1) / 2;
> + int h = 0;
> + int i = (g * 2 > h * 5 ? g * 2 : h * 5) / -1;
> + if (i != 0)
> + __builtin_abort ();
> +}
>
> Jakub
>
>
@@ -7104,6 +7104,27 @@ extract_muldiv_1 (tree t, tree c, enum t
if (TYPE_UNSIGNED (ctype) != TYPE_UNSIGNED (type))
break;
+ /* Punt for multiplication altogether.
+ MAX (1U + INT_MAX, 1U) * 2U is not equivalent to
+ MAX ((1U + INT_MAX) * 2U, 1U * 2U), the former is
+ 0U, the latter is 2U.
+ MAX (INT_MIN / 2, 0) * -2 is not equivalent to
+ MIN (INT_MIN / 2 * -2, 0 * -2), the former is
+ well defined 0, the latter invokes UB.
+ MAX (INT_MIN / 2, 5) * 5 is not equivalent to
+ MAX (INT_MIN / 2 * 5, 5 * 5), the former is
+ well defined 25, the latter invokes UB. */
+ if (code == MULT_EXPR)
+ break;
+ /* For division/modulo, punt on c being -1 for MAX, as
+ MAX (INT_MIN, 0) / -1 is not equivalent to
+ MIN (INT_MIN / -1, 0 / -1), the former is well defined
+ 0, the latter invokes UB (or for -fwrapv is INT_MIN).
+ MIN (INT_MIN, 0) / -1 already invokes UB, so the
+ transformation won't make it worse. */
+ else if (tcode == MAX_EXPR && integer_minus_onep (c))
+ break;
+
/* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
sub_strict_overflow_p = false;
if ((t1 = extract_muldiv (op0, c, code, wide_type,
@@ -0,0 +1,21 @@
+/* PR middle-end/111151 */
+
+int
+main ()
+{
+ unsigned a = (1U + __INT_MAX__) / 2U;
+ unsigned b = 1U;
+ unsigned c = (a * 2U > b * 2U ? a * 2U : b * 2U) * 2U;
+ if (c != 0U)
+ __builtin_abort ();
+ int d = (-__INT_MAX__ - 1) / 2;
+ int e = 10;
+ int f = (d * 2 > e * 5 ? d * 2 : e * 5) * 6;
+ if (f != 120)
+ __builtin_abort ();
+ int g = (-__INT_MAX__ - 1) / 2;
+ int h = 0;
+ int i = (g * 2 > h * 5 ? g * 2 : h * 5) / -1;
+ if (i != 0)
+ __builtin_abort ();
+}