Fix (-A) - B -> (-B) - A optimization in fold_binary_loc (PR tree-optimization/83269)

Message ID 20171214201110.GZ2353@tucnak
State New
Headers show
Series
  • Fix (-A) - B -> (-B) - A optimization in fold_binary_loc (PR tree-optimization/83269)
Related show

Commit Message

Jakub Jelinek Dec. 14, 2017, 8:11 p.m.
Hi!

As the following testcase shows, the (-A) - B -> (-B) - A optimization can't
be done the way it is if the negation of A is performed in type with
wrapping behavior while the subtraction is done in signed type (with the
same precision), as if A is (unsigned) INT_MIN, then (int) -(unsigned) INT_MIN
is INT_MIN and INT_MIN - B is different from (-B) - INT_MIN.
The reason we can see this is because we check that arg0 is NEGATE_EXPR, but
arg0 is STRIP_NOPS from op0.  If the NEGATE_EXPR is already done in signed
type, then it would be already UB if A was INT_MIN and so we can safely do
it.

Whether we perform the subtraction in the unsigned type or just don't
optimize I think doesn't matter that much, at least the only spot during
x86_64-linux and i686-linux bootstraps/regtests this new condition triggered
was the new testcase, nothing else.  So if you instead prefer to punt, I can
tweak the patch, move the negated condition to the if above it.

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

2017-12-14  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/83269
	* fold-const.c (fold_binary_loc): Perform (-A) - B -> (-B) - A
	subtraction in arg0's type if type is signed and arg0 is unsigned.
	Formatting fix.

	* gcc.c-torture/execute/pr83269.c: New test.


	Jakub

Comments

Richard Biener Dec. 15, 2017, 8:38 a.m. | #1
On Thu, 14 Dec 2017, Jakub Jelinek wrote:

> Hi!

> 

> As the following testcase shows, the (-A) - B -> (-B) - A optimization can't

> be done the way it is if the negation of A is performed in type with

> wrapping behavior while the subtraction is done in signed type (with the

> same precision), as if A is (unsigned) INT_MIN, then (int) -(unsigned) INT_MIN

> is INT_MIN and INT_MIN - B is different from (-B) - INT_MIN.

> The reason we can see this is because we check that arg0 is NEGATE_EXPR, but

> arg0 is STRIP_NOPS from op0.  If the NEGATE_EXPR is already done in signed

> type, then it would be already UB if A was INT_MIN and so we can safely do

> it.

> 

> Whether we perform the subtraction in the unsigned type or just don't

> optimize I think doesn't matter that much, at least the only spot during

> x86_64-linux and i686-linux bootstraps/regtests this new condition triggered

> was the new testcase, nothing else.  So if you instead prefer to punt, I can

> tweak the patch, move the negated condition to the if above it.

> 

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


I think a better fix would be to just check TREE_CODE (op0) == NEGATE_EXPR
and use op0, like we do for op1 (probably fixed that earlier).  I'd rather
not complicate the fold-const.c code more at this point.

Richard.

> 2017-12-14  Jakub Jelinek  <jakub@redhat.com>

> 

> 	PR tree-optimization/83269

> 	* fold-const.c (fold_binary_loc): Perform (-A) - B -> (-B) - A

> 	subtraction in arg0's type if type is signed and arg0 is unsigned.

> 	Formatting fix.

> 

> 	* gcc.c-torture/execute/pr83269.c: New test.

> 

> --- gcc/fold-const.c.jj	2017-12-08 00:50:27.000000000 +0100

> +++ gcc/fold-const.c	2017-12-14 17:42:31.221398170 +0100

> @@ -9098,8 +9098,8 @@ expr_not_equal_to (tree t, const wide_in

>     return NULL_TREE.  */

>  

>  tree

> -fold_binary_loc (location_t loc,

> -	     enum tree_code code, tree type, tree op0, tree op1)

> +fold_binary_loc (location_t loc, enum tree_code code, tree type,

> +		 tree op0, tree op1)

>  {

>    enum tree_code_class kind = TREE_CODE_CLASS (code);

>    tree arg0, arg1, tem;

> @@ -9770,10 +9770,34 @@ fold_binary_loc (location_t loc,

>        /* (-A) - B -> (-B) - A  where B is easily negated and we can swap.  */

>        if (TREE_CODE (arg0) == NEGATE_EXPR

>  	  && negate_expr_p (op1))

> -	return fold_build2_loc (loc, MINUS_EXPR, type,

> -				negate_expr (op1),

> -				fold_convert_loc (loc, type,

> -						  TREE_OPERAND (arg0, 0)));

> +	{

> +	  /* If arg0 is e.g. unsigned int and type is int, then we need to

> +	     perform the subtraction in arg0's type, because if A is

> +	     INT_MIN at runtime, the original expression can be well defined

> +	     while the latter is not.  See PR83269.  */

> +	  if (ANY_INTEGRAL_TYPE_P (type)

> +	      && TYPE_OVERFLOW_UNDEFINED (type)

> +	      && ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg0))

> +	      && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0)))

> +	    {

> +	      /* Don't do this when sanitizing, as by doing the subtraction

> +		 in unsigned type we won't notice if the original program

> +		 has been buggy.  */

> +	      if (!TYPE_OVERFLOW_SANITIZED (type))

> +		{

> +		  tem = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (arg0),

> +					 fold_convert_loc (loc,

> +							   TREE_TYPE (arg0),

> +							   negate_expr (op1)),

> +					 TREE_OPERAND (arg0, 0));

> +		  return fold_convert_loc (loc, type, tem);

> +		}

> +	    }

> +	  else

> +	    return fold_build2_loc (loc, MINUS_EXPR, type, negate_expr (op1),

> +				    fold_convert_loc (loc, type,

> +						      TREE_OPERAND (arg0, 0)));

> +	}

>  

>        /* Fold __complex__ ( x, 0 ) - __complex__ ( 0, y ) to

>  	 __complex__ ( x, -y ).  This is not the same for SNaNs or if

> --- gcc/testsuite/gcc.c-torture/execute/pr83269.c.jj	2017-12-14 17:43:24.534710997 +0100

> +++ gcc/testsuite/gcc.c-torture/execute/pr83269.c	2017-12-14 17:43:10.000000000 +0100

> @@ -0,0 +1,14 @@

> +/* PR tree-optimization/83269 */

> +

> +int

> +main ()

> +{

> +#if __SIZEOF_INT__ == 4 && __SIZEOF_LONG_LONG__ > 4 && __CHAR_BIT__ == 8

> +  volatile unsigned char a = 1;

> +  long long b = 0x80000000L;

> +  int c = -((int)(-b) - (-0x7fffffff * a));

> +  if (c != 1)

> +    __builtin_abort ();

> +#endif

> +  return 0;

> +}

> 

> 	Jakub

> 

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)
Jakub Jelinek Dec. 15, 2017, 8:59 a.m. | #2
On Fri, Dec 15, 2017 at 09:38:52AM +0100, Richard Biener wrote:
> On Thu, 14 Dec 2017, Jakub Jelinek wrote:

> 

> > Hi!

> > 

> > As the following testcase shows, the (-A) - B -> (-B) - A optimization can't

> > be done the way it is if the negation of A is performed in type with

> > wrapping behavior while the subtraction is done in signed type (with the

> > same precision), as if A is (unsigned) INT_MIN, then (int) -(unsigned) INT_MIN

> > is INT_MIN and INT_MIN - B is different from (-B) - INT_MIN.

> > The reason we can see this is because we check that arg0 is NEGATE_EXPR, but

> > arg0 is STRIP_NOPS from op0.  If the NEGATE_EXPR is already done in signed

> > type, then it would be already UB if A was INT_MIN and so we can safely do

> > it.

> > 

> > Whether we perform the subtraction in the unsigned type or just don't

> > optimize I think doesn't matter that much, at least the only spot during

> > x86_64-linux and i686-linux bootstraps/regtests this new condition triggered

> > was the new testcase, nothing else.  So if you instead prefer to punt, I can

> > tweak the patch, move the negated condition to the if above it.

> > 

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

> 

> I think a better fix would be to just check TREE_CODE (op0) == NEGATE_EXPR

> and use op0, like we do for op1 (probably fixed that earlier).  I'd rather

> not complicate the fold-const.c code more at this point.


That would regress the case when type is unsigned.  If you don't want to
complicate fold-const.c, my preference would be to add the extra && !, it
isn't that much.

Of course, a question is why this optimization hasn't been moved to match.pd
when others had been.

2017-12-15  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/83269
	* fold-const.c (fold_binary_loc): Perform (-A) - B -> (-B) - A
	subtraction in arg0's type if type is signed and arg0 is unsigned.
	Formatting fix.

	* gcc.c-torture/execute/pr83269.c: New test.

--- gcc/fold-const.c.jj	2017-12-08 00:50:27.000000000 +0100
+++ gcc/fold-const.c	2017-12-14 17:42:31.221398170 +0100
@@ -9098,8 +9098,8 @@ expr_not_equal_to (tree t, const wide_in
    return NULL_TREE.  */
 
 tree
-fold_binary_loc (location_t loc,
-	     enum tree_code code, tree type, tree op0, tree op1)
+fold_binary_loc (location_t loc, enum tree_code code, tree type,
+		 tree op0, tree op1)
 {
   enum tree_code_class kind = TREE_CODE_CLASS (code);
   tree arg0, arg1, tem;
@@ -9769,11 +9769,18 @@ fold_binary_loc (location_t loc,
 
       /* (-A) - B -> (-B) - A  where B is easily negated and we can swap.  */
       if (TREE_CODE (arg0) == NEGATE_EXPR
-	  && negate_expr_p (op1))
-	return fold_build2_loc (loc, MINUS_EXPR, type,
-				negate_expr (op1),
-				fold_convert_loc (loc, type,
-						  TREE_OPERAND (arg0, 0)));
+	  && negate_expr_p (op1)
+	  /* If arg0 is e.g. unsigned int and type is int, then this could
+	     introduce UB, because if A is INT_MIN at runtime, the original
+	     expression can be well defined while the latter is not.
+	     See PR83269.  */
+	  && !(ANY_INTEGRAL_TYPE_P (type)
+	       && TYPE_OVERFLOW_UNDEFINED (type)
+	       && ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+	       && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))))
+	return fold_build2_loc (loc, MINUS_EXPR, type, negate_expr (op1),
+			        fold_convert_loc (loc, type,
+						  TREE_OPERAND (arg0, 0)));
 
       /* Fold __complex__ ( x, 0 ) - __complex__ ( 0, y ) to
 	 __complex__ ( x, -y ).  This is not the same for SNaNs or if
--- gcc/testsuite/gcc.c-torture/execute/pr83269.c.jj	2017-12-14 17:43:24.534710997 +0100
+++ gcc/testsuite/gcc.c-torture/execute/pr83269.c	2017-12-14 17:43:10.000000000 +0100
@@ -0,0 +1,14 @@
+/* PR tree-optimization/83269 */
+
+int
+main ()
+{
+#if __SIZEOF_INT__ == 4 && __SIZEOF_LONG_LONG__ > 4 && __CHAR_BIT__ == 8
+  volatile unsigned char a = 1;
+  long long b = 0x80000000L;
+  int c = -((int)(-b) - (-0x7fffffff * a));
+  if (c != 1)
+    __builtin_abort ();
+#endif
+  return 0;
+}


	Jakub
Richard Biener Dec. 15, 2017, 9:11 a.m. | #3
On Fri, 15 Dec 2017, Jakub Jelinek wrote:

> On Fri, Dec 15, 2017 at 09:38:52AM +0100, Richard Biener wrote:

> > On Thu, 14 Dec 2017, Jakub Jelinek wrote:

> > 

> > > Hi!

> > > 

> > > As the following testcase shows, the (-A) - B -> (-B) - A optimization can't

> > > be done the way it is if the negation of A is performed in type with

> > > wrapping behavior while the subtraction is done in signed type (with the

> > > same precision), as if A is (unsigned) INT_MIN, then (int) -(unsigned) INT_MIN

> > > is INT_MIN and INT_MIN - B is different from (-B) - INT_MIN.

> > > The reason we can see this is because we check that arg0 is NEGATE_EXPR, but

> > > arg0 is STRIP_NOPS from op0.  If the NEGATE_EXPR is already done in signed

> > > type, then it would be already UB if A was INT_MIN and so we can safely do

> > > it.

> > > 

> > > Whether we perform the subtraction in the unsigned type or just don't

> > > optimize I think doesn't matter that much, at least the only spot during

> > > x86_64-linux and i686-linux bootstraps/regtests this new condition triggered

> > > was the new testcase, nothing else.  So if you instead prefer to punt, I can

> > > tweak the patch, move the negated condition to the if above it.

> > > 

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

> > 

> > I think a better fix would be to just check TREE_CODE (op0) == NEGATE_EXPR

> > and use op0, like we do for op1 (probably fixed that earlier).  I'd rather

> > not complicate the fold-const.c code more at this point.

> 

> That would regress the case when type is unsigned.  If you don't want to

> complicate fold-const.c, my preference would be to add the extra && !, it

> isn't that much.


Ok, that works for me.

> Of course, a question is why this optimization hasn't been moved to match.pd

> when others had been.


Mostly laziness and the "fear" of match.pd negate_expr_p not being
powerful enough (it isn't recursive as the fold-const.c one and it
doesn't have all the complicated cases).

Thanks,
Richard.

> 2017-12-15  Jakub Jelinek  <jakub@redhat.com>

> 

> 	PR tree-optimization/83269

> 	* fold-const.c (fold_binary_loc): Perform (-A) - B -> (-B) - A

> 	subtraction in arg0's type if type is signed and arg0 is unsigned.

> 	Formatting fix.

> 

> 	* gcc.c-torture/execute/pr83269.c: New test.

> 

> --- gcc/fold-const.c.jj	2017-12-08 00:50:27.000000000 +0100

> +++ gcc/fold-const.c	2017-12-14 17:42:31.221398170 +0100

> @@ -9098,8 +9098,8 @@ expr_not_equal_to (tree t, const wide_in

>     return NULL_TREE.  */

>  

>  tree

> -fold_binary_loc (location_t loc,

> -	     enum tree_code code, tree type, tree op0, tree op1)

> +fold_binary_loc (location_t loc, enum tree_code code, tree type,

> +		 tree op0, tree op1)

>  {

>    enum tree_code_class kind = TREE_CODE_CLASS (code);

>    tree arg0, arg1, tem;

> @@ -9769,11 +9769,18 @@ fold_binary_loc (location_t loc,

>  

>        /* (-A) - B -> (-B) - A  where B is easily negated and we can swap.  */

>        if (TREE_CODE (arg0) == NEGATE_EXPR

> -	  && negate_expr_p (op1))

> -	return fold_build2_loc (loc, MINUS_EXPR, type,

> -				negate_expr (op1),

> -				fold_convert_loc (loc, type,

> -						  TREE_OPERAND (arg0, 0)));

> +	  && negate_expr_p (op1)

> +	  /* If arg0 is e.g. unsigned int and type is int, then this could

> +	     introduce UB, because if A is INT_MIN at runtime, the original

> +	     expression can be well defined while the latter is not.

> +	     See PR83269.  */

> +	  && !(ANY_INTEGRAL_TYPE_P (type)

> +	       && TYPE_OVERFLOW_UNDEFINED (type)

> +	       && ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg0))

> +	       && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))))

> +	return fold_build2_loc (loc, MINUS_EXPR, type, negate_expr (op1),

> +			        fold_convert_loc (loc, type,

> +						  TREE_OPERAND (arg0, 0)));

>  

>        /* Fold __complex__ ( x, 0 ) - __complex__ ( 0, y ) to

>  	 __complex__ ( x, -y ).  This is not the same for SNaNs or if

> --- gcc/testsuite/gcc.c-torture/execute/pr83269.c.jj	2017-12-14 17:43:24.534710997 +0100

> +++ gcc/testsuite/gcc.c-torture/execute/pr83269.c	2017-12-14 17:43:10.000000000 +0100

> @@ -0,0 +1,14 @@

> +/* PR tree-optimization/83269 */

> +

> +int

> +main ()

> +{

> +#if __SIZEOF_INT__ == 4 && __SIZEOF_LONG_LONG__ > 4 && __CHAR_BIT__ == 8

> +  volatile unsigned char a = 1;

> +  long long b = 0x80000000L;

> +  int c = -((int)(-b) - (-0x7fffffff * a));

> +  if (c != 1)

> +    __builtin_abort ();

> +#endif

> +  return 0;

> +}

> 

> 

> 	Jakub

> 

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Patch

--- gcc/fold-const.c.jj	2017-12-08 00:50:27.000000000 +0100
+++ gcc/fold-const.c	2017-12-14 17:42:31.221398170 +0100
@@ -9098,8 +9098,8 @@  expr_not_equal_to (tree t, const wide_in
    return NULL_TREE.  */
 
 tree
-fold_binary_loc (location_t loc,
-	     enum tree_code code, tree type, tree op0, tree op1)
+fold_binary_loc (location_t loc, enum tree_code code, tree type,
+		 tree op0, tree op1)
 {
   enum tree_code_class kind = TREE_CODE_CLASS (code);
   tree arg0, arg1, tem;
@@ -9770,10 +9770,34 @@  fold_binary_loc (location_t loc,
       /* (-A) - B -> (-B) - A  where B is easily negated and we can swap.  */
       if (TREE_CODE (arg0) == NEGATE_EXPR
 	  && negate_expr_p (op1))
-	return fold_build2_loc (loc, MINUS_EXPR, type,
-				negate_expr (op1),
-				fold_convert_loc (loc, type,
-						  TREE_OPERAND (arg0, 0)));
+	{
+	  /* If arg0 is e.g. unsigned int and type is int, then we need to
+	     perform the subtraction in arg0's type, because if A is
+	     INT_MIN at runtime, the original expression can be well defined
+	     while the latter is not.  See PR83269.  */
+	  if (ANY_INTEGRAL_TYPE_P (type)
+	      && TYPE_OVERFLOW_UNDEFINED (type)
+	      && ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+	      && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0)))
+	    {
+	      /* Don't do this when sanitizing, as by doing the subtraction
+		 in unsigned type we won't notice if the original program
+		 has been buggy.  */
+	      if (!TYPE_OVERFLOW_SANITIZED (type))
+		{
+		  tem = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (arg0),
+					 fold_convert_loc (loc,
+							   TREE_TYPE (arg0),
+							   negate_expr (op1)),
+					 TREE_OPERAND (arg0, 0));
+		  return fold_convert_loc (loc, type, tem);
+		}
+	    }
+	  else
+	    return fold_build2_loc (loc, MINUS_EXPR, type, negate_expr (op1),
+				    fold_convert_loc (loc, type,
+						      TREE_OPERAND (arg0, 0)));
+	}
 
       /* Fold __complex__ ( x, 0 ) - __complex__ ( 0, y ) to
 	 __complex__ ( x, -y ).  This is not the same for SNaNs or if
--- gcc/testsuite/gcc.c-torture/execute/pr83269.c.jj	2017-12-14 17:43:24.534710997 +0100
+++ gcc/testsuite/gcc.c-torture/execute/pr83269.c	2017-12-14 17:43:10.000000000 +0100
@@ -0,0 +1,14 @@ 
+/* PR tree-optimization/83269 */
+
+int
+main ()
+{
+#if __SIZEOF_INT__ == 4 && __SIZEOF_LONG_LONG__ > 4 && __CHAR_BIT__ == 8
+  volatile unsigned char a = 1;
+  long long b = 0x80000000L;
+  int c = -((int)(-b) - (-0x7fffffff * a));
+  if (c != 1)
+    __builtin_abort ();
+#endif
+  return 0;
+}