[PATCH] Fix up __builtin_mul_overflow for signed * signed -> unsigned (PR middle-end/91450)

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] Fix up __builtin_mul_overflow for signed * signed -> unsigned (PR middle-end/91450)

Jakub Jelinek
Hi!

This case is correctly described in the comment in expand_mul_overflow:
     s1 * s2 -> ur
        t1 = (s1 & s2) < 0 ? (-(U) s1) : ((U) s1)
        t2 = (s1 & s2) < 0 ? (-(U) s2) : ((U) s2)
        res = t1 * t2
        ovf = (s1 ^ s2) < 0 ? (s1 && s2) : main_ovf (true)  */
where if one of the operands is negative and the other non-negative,
the overflow is whenever both operands are non-zero, so s1 && s2,
but unfortunately the code has been implementing s1 & s2 instead,
which e.g. for the -2 and 1 where (-2 & 1) == 0, but (-2 && 1) != 0
is incorrect.
The second hunk is when we know from VRP that one of the operand (and which
one) is negative and which one is non-negative, obviously the negative
one can't be zero, so we can just compare the non-negative one against zero.
The third hunk is when we don't know this precisely from VRP.  In that case
we used to do essentially
  if ((s1 & s2) == 0)
    goto main_label;
  ovf = 1;
main_label:
  ovf |= __builtin_mul_overflow ((unsigned) s1, (unsigned) s2, &r);
(the fallthrough is ok, because mul_overflow when one of the operands
is zero will just compute zero), this patch changes it to:
  if (s1 == 0)
    goto main_label;
  if (s2 == 0)
    goto main_label;
  ovf = 1;
main_label:
  ovf |= __builtin_mul_overflow ((unsigned) s1, (unsigned) s2, &r);
but as an optimization, if we know from VRP that one of the operands
is negative, we don't bother comparing that operand to 0.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk
and release branches?

2019-11-19  Jakub Jelinek  <[hidden email]>

        PR middle-end/91450
        * internal-fn.c (expand_mul_overflow): For s1 * s2 -> ur, if one
        operand is negative and one non-negative, compare the non-negative
        one against 0 rather than comparing s1 & s2 against 0.  Otherwise,
        don't compare (s1 & s2) == 0, but compare separately both s1 == 0
        and s2 == 0, unless one of them is known to be negative.  Remove
        tem2 variable, use tem where tem2 has been used before.

        * gcc.c-torture/execute/pr91450-1.c: New test.
        * gcc.c-torture/execute/pr91450-2.c: New test.

--- gcc/internal-fn.c.jj 2019-11-08 11:33:48.000000000 +0100
+++ gcc/internal-fn.c 2019-11-18 14:41:48.247381649 +0100
@@ -1408,7 +1408,7 @@ expand_mul_overflow (location_t loc, tre
   /* s1 * s2 -> ur  */
   if (!uns0_p && !uns1_p && unsr_p)
     {
-      rtx tem, tem2;
+      rtx tem;
       switch (pos_neg0 | pos_neg1)
  {
  case 1: /* Both operands known to be non-negative.  */
@@ -1438,10 +1438,8 @@ expand_mul_overflow (location_t loc, tre
       ops.op2 = NULL_TREE;
       ops.location = loc;
       res = expand_expr_real_2 (&ops, NULL_RTX, mode, EXPAND_NORMAL);
-      tem = expand_binop (mode, and_optab, op0, op1, NULL_RTX, false,
-  OPTAB_LIB_WIDEN);
-      do_compare_rtx_and_jump (tem, const0_rtx, EQ, true, mode,
-       NULL_RTX, NULL, done_label,
+      do_compare_rtx_and_jump (pos_neg0 == 1 ? op0 : op1, const0_rtx, EQ,
+       true, mode, NULL_RTX, NULL, done_label,
        profile_probability::very_likely ());
       goto do_error_label;
     }
@@ -1472,16 +1470,23 @@ expand_mul_overflow (location_t loc, tre
   arg1 = error_mark_node;
   emit_jump (do_main_label);
   emit_label (after_negate_label);
-  tem2 = expand_binop (mode, xor_optab, op0, op1, NULL_RTX, false,
-       OPTAB_LIB_WIDEN);
-  do_compare_rtx_and_jump (tem2, const0_rtx, GE, false, mode, NULL_RTX,
-   NULL, do_main_label, profile_probability::very_likely ());
+  tem = expand_binop (mode, xor_optab, op0, op1, NULL_RTX, false,
+      OPTAB_LIB_WIDEN);
+  do_compare_rtx_and_jump (tem, const0_rtx, GE, false, mode, NULL_RTX,
+   NULL, do_main_label,
+   profile_probability::very_likely ());
   /* One argument is negative here, the other positive.  This
      overflows always, unless one of the arguments is 0.  But
      if e.g. s2 is 0, (U) s1 * 0 doesn't overflow, whatever s1
      is, thus we can keep do_main code oring in overflow as is.  */
-  do_compare_rtx_and_jump (tem, const0_rtx, EQ, true, mode, NULL_RTX,
-   NULL, do_main_label, profile_probability::very_likely ());
+  if (pos_neg0 != 2)
+    do_compare_rtx_and_jump (op0, const0_rtx, EQ, true, mode, NULL_RTX,
+     NULL, do_main_label,
+     profile_probability::very_unlikely ());
+  if (pos_neg1 != 2)
+    do_compare_rtx_and_jump (op1, const0_rtx, EQ, true, mode, NULL_RTX,
+     NULL, do_main_label,
+     profile_probability::very_unlikely ());
   expand_arith_set_overflow (lhs, target);
   emit_label (do_main_label);
   goto do_main;
--- gcc/testsuite/gcc.c-torture/execute/pr91450-1.c.jj 2019-11-18 14:32:04.156108293 +0100
+++ gcc/testsuite/gcc.c-torture/execute/pr91450-1.c 2019-11-18 14:39:28.693466446 +0100
@@ -0,0 +1,88 @@
+/* PR middle-end/91450 */
+
+__attribute__((noipa)) unsigned long long
+foo (int a, int b)
+{
+  unsigned long long r;
+  if (!__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  return r;
+}
+
+__attribute__((noipa)) unsigned long long
+bar (int a, int b)
+{
+  unsigned long long r;
+  if (a >= 0)
+    return 0;
+  if (!__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  return r;
+}
+
+__attribute__((noipa)) unsigned long long
+baz (int a, int b)
+{
+  unsigned long long r;
+  if (b >= 0)
+    return 0;
+  if (!__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  return r;
+}
+
+__attribute__((noipa)) unsigned long long
+qux (int a, int b)
+{
+  unsigned long long r;
+  if (a >= 0)
+    return 0;
+  if (b < 0)
+    return 0;
+  if (!__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  return r;
+}
+
+__attribute__((noipa)) unsigned long long
+quux (int a, int b)
+{
+  unsigned long long r;
+  if (a < 0)
+    return 0;
+  if (b >= 0)
+    return 0;
+  if (!__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  return r;
+}
+
+int
+main ()
+{
+  if (foo (-4, 2) != -8ULL)
+    __builtin_abort ();
+  if (foo (2, -4) != -8ULL)
+    __builtin_abort ();
+  if (bar (-4, 2) != -8ULL)
+    __builtin_abort ();
+  if (baz (2, -4) != -8ULL)
+    __builtin_abort ();
+  if (qux (-4, 2) != -8ULL)
+    __builtin_abort ();
+  if (quux (2, -4) != -8ULL)
+    __builtin_abort ();
+  if (foo (-2, 1) != -2ULL)
+    __builtin_abort ();
+  if (foo (1, -2) != -2ULL)
+    __builtin_abort ();
+  if (bar (-2, 1) != -2ULL)
+    __builtin_abort ();
+  if (baz (1, -2) != -2ULL)
+    __builtin_abort ();
+  if (qux (-2, 1) != -2ULL)
+    __builtin_abort ();
+  if (quux (1, -2) != -2ULL)
+    __builtin_abort ();
+  return 0;
+}
--- gcc/testsuite/gcc.c-torture/execute/pr91450-2.c.jj 2019-11-18 14:32:12.204987999 +0100
+++ gcc/testsuite/gcc.c-torture/execute/pr91450-2.c 2019-11-18 14:33:37.881707491 +0100
@@ -0,0 +1,76 @@
+/* PR middle-end/91450 */
+
+__attribute__((noipa)) void
+foo (int a, int b)
+{
+  unsigned long long r;
+  if (__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  if (r != 0)
+    __builtin_abort ();
+}
+
+__attribute__((noipa)) void
+bar (int a, int b)
+{
+  unsigned long long r;
+  if (a >= 0)
+    return;
+  if (__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  if (r != 0)
+    __builtin_abort ();
+}
+
+__attribute__((noipa)) void
+baz (int a, int b)
+{
+  unsigned long long r;
+  if (b >= 0)
+    return;
+  if (__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  if (r != 0)
+    __builtin_abort ();
+}
+
+__attribute__((noipa)) void
+qux (int a, int b)
+{
+  unsigned long long r;
+  if (a >= 0)
+    return;
+  if (b < 0)
+    return;
+  if (__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  if (r != 0)
+    __builtin_abort ();
+}
+
+__attribute__((noipa)) void
+quux (int a, int b)
+{
+  unsigned long long r;
+  if (a < 0)
+    return;
+  if (b >= 0)
+    return;
+  if (__builtin_mul_overflow (a, b, &r))
+    __builtin_abort ();
+  if (r != 0)
+    __builtin_abort ();
+}
+
+int
+main ()
+{
+  foo (-4, 0);
+  foo (0, -4);
+  foo (0, 0);
+  bar (-4, 0);
+  baz (0, -4);
+  qux (-4, 0);
+  quux (0, -4);
+  return 0;
+}

        Jakub

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Fix up __builtin_mul_overflow for signed * signed -> unsigned (PR middle-end/91450)

Richard Biener
On Tue, 19 Nov 2019, Jakub Jelinek wrote:

> Hi!
>
> This case is correctly described in the comment in expand_mul_overflow:
>      s1 * s2 -> ur
>         t1 = (s1 & s2) < 0 ? (-(U) s1) : ((U) s1)
>         t2 = (s1 & s2) < 0 ? (-(U) s2) : ((U) s2)
>         res = t1 * t2
>         ovf = (s1 ^ s2) < 0 ? (s1 && s2) : main_ovf (true)  */
> where if one of the operands is negative and the other non-negative,
> the overflow is whenever both operands are non-zero, so s1 && s2,
> but unfortunately the code has been implementing s1 & s2 instead,
> which e.g. for the -2 and 1 where (-2 & 1) == 0, but (-2 && 1) != 0
> is incorrect.
> The second hunk is when we know from VRP that one of the operand (and which
> one) is negative and which one is non-negative, obviously the negative
> one can't be zero, so we can just compare the non-negative one against zero.
> The third hunk is when we don't know this precisely from VRP.  In that case
> we used to do essentially
>   if ((s1 & s2) == 0)
>     goto main_label;
>   ovf = 1;
> main_label:
>   ovf |= __builtin_mul_overflow ((unsigned) s1, (unsigned) s2, &r);
> (the fallthrough is ok, because mul_overflow when one of the operands
> is zero will just compute zero), this patch changes it to:
>   if (s1 == 0)
>     goto main_label;
>   if (s2 == 0)
>     goto main_label;
>   ovf = 1;
> main_label:
>   ovf |= __builtin_mul_overflow ((unsigned) s1, (unsigned) s2, &r);
> but as an optimization, if we know from VRP that one of the operands
> is negative, we don't bother comparing that operand to 0.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk
> and release branches?
OK.

Thanks,
Richard.
 

> 2019-11-19  Jakub Jelinek  <[hidden email]>
>
> PR middle-end/91450
> * internal-fn.c (expand_mul_overflow): For s1 * s2 -> ur, if one
> operand is negative and one non-negative, compare the non-negative
> one against 0 rather than comparing s1 & s2 against 0.  Otherwise,
> don't compare (s1 & s2) == 0, but compare separately both s1 == 0
> and s2 == 0, unless one of them is known to be negative.  Remove
> tem2 variable, use tem where tem2 has been used before.
>
> * gcc.c-torture/execute/pr91450-1.c: New test.
> * gcc.c-torture/execute/pr91450-2.c: New test.
>
> --- gcc/internal-fn.c.jj 2019-11-08 11:33:48.000000000 +0100
> +++ gcc/internal-fn.c 2019-11-18 14:41:48.247381649 +0100
> @@ -1408,7 +1408,7 @@ expand_mul_overflow (location_t loc, tre
>    /* s1 * s2 -> ur  */
>    if (!uns0_p && !uns1_p && unsr_p)
>      {
> -      rtx tem, tem2;
> +      rtx tem;
>        switch (pos_neg0 | pos_neg1)
>   {
>   case 1: /* Both operands known to be non-negative.  */
> @@ -1438,10 +1438,8 @@ expand_mul_overflow (location_t loc, tre
>        ops.op2 = NULL_TREE;
>        ops.location = loc;
>        res = expand_expr_real_2 (&ops, NULL_RTX, mode, EXPAND_NORMAL);
> -      tem = expand_binop (mode, and_optab, op0, op1, NULL_RTX, false,
> -  OPTAB_LIB_WIDEN);
> -      do_compare_rtx_and_jump (tem, const0_rtx, EQ, true, mode,
> -       NULL_RTX, NULL, done_label,
> +      do_compare_rtx_and_jump (pos_neg0 == 1 ? op0 : op1, const0_rtx, EQ,
> +       true, mode, NULL_RTX, NULL, done_label,
>         profile_probability::very_likely ());
>        goto do_error_label;
>      }
> @@ -1472,16 +1470,23 @@ expand_mul_overflow (location_t loc, tre
>    arg1 = error_mark_node;
>    emit_jump (do_main_label);
>    emit_label (after_negate_label);
> -  tem2 = expand_binop (mode, xor_optab, op0, op1, NULL_RTX, false,
> -       OPTAB_LIB_WIDEN);
> -  do_compare_rtx_and_jump (tem2, const0_rtx, GE, false, mode, NULL_RTX,
> -   NULL, do_main_label, profile_probability::very_likely ());
> +  tem = expand_binop (mode, xor_optab, op0, op1, NULL_RTX, false,
> +      OPTAB_LIB_WIDEN);
> +  do_compare_rtx_and_jump (tem, const0_rtx, GE, false, mode, NULL_RTX,
> +   NULL, do_main_label,
> +   profile_probability::very_likely ());
>    /* One argument is negative here, the other positive.  This
>       overflows always, unless one of the arguments is 0.  But
>       if e.g. s2 is 0, (U) s1 * 0 doesn't overflow, whatever s1
>       is, thus we can keep do_main code oring in overflow as is.  */
> -  do_compare_rtx_and_jump (tem, const0_rtx, EQ, true, mode, NULL_RTX,
> -   NULL, do_main_label, profile_probability::very_likely ());
> +  if (pos_neg0 != 2)
> +    do_compare_rtx_and_jump (op0, const0_rtx, EQ, true, mode, NULL_RTX,
> +     NULL, do_main_label,
> +     profile_probability::very_unlikely ());
> +  if (pos_neg1 != 2)
> +    do_compare_rtx_and_jump (op1, const0_rtx, EQ, true, mode, NULL_RTX,
> +     NULL, do_main_label,
> +     profile_probability::very_unlikely ());
>    expand_arith_set_overflow (lhs, target);
>    emit_label (do_main_label);
>    goto do_main;
> --- gcc/testsuite/gcc.c-torture/execute/pr91450-1.c.jj 2019-11-18 14:32:04.156108293 +0100
> +++ gcc/testsuite/gcc.c-torture/execute/pr91450-1.c 2019-11-18 14:39:28.693466446 +0100
> @@ -0,0 +1,88 @@
> +/* PR middle-end/91450 */
> +
> +__attribute__((noipa)) unsigned long long
> +foo (int a, int b)
> +{
> +  unsigned long long r;
> +  if (!__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  return r;
> +}
> +
> +__attribute__((noipa)) unsigned long long
> +bar (int a, int b)
> +{
> +  unsigned long long r;
> +  if (a >= 0)
> +    return 0;
> +  if (!__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  return r;
> +}
> +
> +__attribute__((noipa)) unsigned long long
> +baz (int a, int b)
> +{
> +  unsigned long long r;
> +  if (b >= 0)
> +    return 0;
> +  if (!__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  return r;
> +}
> +
> +__attribute__((noipa)) unsigned long long
> +qux (int a, int b)
> +{
> +  unsigned long long r;
> +  if (a >= 0)
> +    return 0;
> +  if (b < 0)
> +    return 0;
> +  if (!__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  return r;
> +}
> +
> +__attribute__((noipa)) unsigned long long
> +quux (int a, int b)
> +{
> +  unsigned long long r;
> +  if (a < 0)
> +    return 0;
> +  if (b >= 0)
> +    return 0;
> +  if (!__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  return r;
> +}
> +
> +int
> +main ()
> +{
> +  if (foo (-4, 2) != -8ULL)
> +    __builtin_abort ();
> +  if (foo (2, -4) != -8ULL)
> +    __builtin_abort ();
> +  if (bar (-4, 2) != -8ULL)
> +    __builtin_abort ();
> +  if (baz (2, -4) != -8ULL)
> +    __builtin_abort ();
> +  if (qux (-4, 2) != -8ULL)
> +    __builtin_abort ();
> +  if (quux (2, -4) != -8ULL)
> +    __builtin_abort ();
> +  if (foo (-2, 1) != -2ULL)
> +    __builtin_abort ();
> +  if (foo (1, -2) != -2ULL)
> +    __builtin_abort ();
> +  if (bar (-2, 1) != -2ULL)
> +    __builtin_abort ();
> +  if (baz (1, -2) != -2ULL)
> +    __builtin_abort ();
> +  if (qux (-2, 1) != -2ULL)
> +    __builtin_abort ();
> +  if (quux (1, -2) != -2ULL)
> +    __builtin_abort ();
> +  return 0;
> +}
> --- gcc/testsuite/gcc.c-torture/execute/pr91450-2.c.jj 2019-11-18 14:32:12.204987999 +0100
> +++ gcc/testsuite/gcc.c-torture/execute/pr91450-2.c 2019-11-18 14:33:37.881707491 +0100
> @@ -0,0 +1,76 @@
> +/* PR middle-end/91450 */
> +
> +__attribute__((noipa)) void
> +foo (int a, int b)
> +{
> +  unsigned long long r;
> +  if (__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  if (r != 0)
> +    __builtin_abort ();
> +}
> +
> +__attribute__((noipa)) void
> +bar (int a, int b)
> +{
> +  unsigned long long r;
> +  if (a >= 0)
> +    return;
> +  if (__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  if (r != 0)
> +    __builtin_abort ();
> +}
> +
> +__attribute__((noipa)) void
> +baz (int a, int b)
> +{
> +  unsigned long long r;
> +  if (b >= 0)
> +    return;
> +  if (__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  if (r != 0)
> +    __builtin_abort ();
> +}
> +
> +__attribute__((noipa)) void
> +qux (int a, int b)
> +{
> +  unsigned long long r;
> +  if (a >= 0)
> +    return;
> +  if (b < 0)
> +    return;
> +  if (__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  if (r != 0)
> +    __builtin_abort ();
> +}
> +
> +__attribute__((noipa)) void
> +quux (int a, int b)
> +{
> +  unsigned long long r;
> +  if (a < 0)
> +    return;
> +  if (b >= 0)
> +    return;
> +  if (__builtin_mul_overflow (a, b, &r))
> +    __builtin_abort ();
> +  if (r != 0)
> +    __builtin_abort ();
> +}
> +
> +int
> +main ()
> +{
> +  foo (-4, 0);
> +  foo (0, -4);
> +  foo (0, 0);
> +  bar (-4, 0);
> +  baz (0, -4);
> +  qux (-4, 0);
> +  quux (0, -4);
> +  return 0;
> +}
>
> Jakub
>
>
--
Richard Biener <[hidden email]>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)