Fix up __builtin_mul_overflow for signed * signed -> unsigned (PR middle-end/91450)
diff mbox series

Message ID 20191119084203.GB4650@tucnak
State New
Headers show
Series
  • Fix up __builtin_mul_overflow for signed * signed -> unsigned (PR middle-end/91450)
Related show

Commit Message

Jakub Jelinek Nov. 19, 2019, 8:42 a.m. UTC
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  <jakub@redhat.com>

	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.


	Jakub

Comments

Richard Biener Nov. 19, 2019, 9:13 a.m. UTC | #1
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  <jakub@redhat.com>
> 
> 	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
> 
>

Patch
diff mbox series

--- 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;
+}