diff mbox

Fix fold reassociation (PR c++/55137)

Message ID 20121107125510.GB1881@tucnak.redhat.com
State New
Headers show

Commit Message

Jakub Jelinek Nov. 7, 2012, 12:55 p.m. UTC 
Hi!

The first (C++) testcase is rejected since my SIZEOF_EXPR folding deferral
changes, the problem is that
-1 + (int) (sizeof (int) - 1)
is first changed into
-1 + (int) ((unsigned) sizeof (int) + UINT_MAX)
and then fold_binary_loc reassociates it in int type into
(int) sizeof (int) + [-2(overflow)], thus introducing overflow where
there hasn't been originally.  maybe_const_value then refuses to fold it
into constant due to that.  I've fixed that by the moving the TYPE_OVERFLOW
check from before the operation to a check whether the whole reassociation
doesn't introduce overflows (while previously it was testing solely
for overflow introduced on fold_converted lit0/lit1 being combined
together, not e.g. when overflow was introduced by fold_converting lit0
resp. lit1, or for minus_lit{0,1} constants).
Unfortunately that patch lead to regression on loop-15.c:
+FAIL: gcc.dg/tree-ssa/loop-15.c scan-tree-dump-times optimized "\\\\+" 0
+FAIL: gcc.dg/tree-ssa/loop-15.c scan-tree-dump-times optimized "n_. \\\\* n_." 1
as we were no longer reassociating an expression used in number of
iterations calculation.

Looking at that lead me to the second testcase below, which I hope is
valid C, the overflow happens there in unsigned type, thus with defined
wrapping, then there is implementation defined? conversion to signed type
(but all our targets are two's complement), and associate_trees:
was reassociating it in signed type, thus introducing signed overflow
where there wasn't before.  Fixed by doing the reassociation in the unsigned
type if (at least) one of the operands is of unsigned type.  This fixes
the loop-15.c testcase as well as the new testcase.

CCing Eric as the author of the last changes in that area.

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

2012-11-07  Jakub Jelinek  <jakub@redhat.com>

	PR c++/55137
	* fold-const.c (fold_binary_loc) <associate>: Don't introduce
	TREE_OVERFLOW through reassociation.  If type doesn't have defined
	overflow, but one or both of the operands do, use the wrapping type
	for reassociation and only convert to type at the end.

	* g++.dg/opt/pr55137.C: New test.
	* gcc.c-torture/execute/pr55137.c: New test.


	Jakub

Comments

Eric Botcazou Nov. 8, 2012, 9:37 a.m. UTC | #1 
> The first (C++) testcase is rejected since my SIZEOF_EXPR folding deferral
> changes, the problem is that
> -1 + (int) (sizeof (int) - 1)
> is first changed into
> -1 + (int) ((unsigned) sizeof (int) + UINT_MAX)
> and then fold_binary_loc reassociates it in int type into
> (int) sizeof (int) + [-2(overflow)], thus introducing overflow where
> there hasn't been originally.  maybe_const_value then refuses to fold it
> into constant due to that.  I've fixed that by the moving the TYPE_OVERFLOW
> check from before the operation to a check whether the whole reassociation
> doesn't introduce overflows (while previously it was testing solely
> for overflow introduced on fold_converted lit0/lit1 being combined
> together, not e.g. when overflow was introduced by fold_converting lit0
> resp. lit1, or for minus_lit{0,1} constants).

FWIW, no objections by me.

> Looking at that lead me to the second testcase below, which I hope is
> valid C, the overflow happens there in unsigned type, thus with defined
> wrapping, then there is implementation defined? conversion to signed type
> (but all our targets are two's complement), and associate_trees:
> was reassociating it in signed type, thus introducing signed overflow
> where there wasn't before.  Fixed by doing the reassociation in the unsigned
> type if (at least) one of the operands is of unsigned type.

I guess the natural question is then: if we start to change the type of the 
operation, why not always reassociate in the unsigned version of the type?

int
foo (int x, int y)
{
  return (x + 1) + (int) (y + 1);
}

int
bar (int x, unsigned int y)
{
  return (x + 1) + (int) (y + 1);
}
Jakub Jelinek Nov. 8, 2012, 10:18 a.m. UTC | #2 
On Thu, Nov 08, 2012 at 10:37:00AM +0100, Eric Botcazou wrote:
> I guess the natural question is then: if we start to change the type of the 
> operation, why not always reassociate in the unsigned version of the type?
> 
> int
> foo (int x, int y)
> {
>   return (x + 1) + (int) (y + 1);
> }

I was afraid of preventing optimizations based on the assumption that
the operations don't overflow.  Perhaps we could do that just
if with signed atype a TREE_OVERFLOW would be introduced (i.e.
when my current patch returns NULL:
+             /* Don't introduce overflows through reassociation.  */                                                                              
+             if (!any_overflows                                                                                                                   
+                 && ((lit0 && TREE_OVERFLOW (lit0))                                                                                               
+                     || (minus_lit0 && TREE_OVERFLOW (minus_lit0))))                                                                              
+               return NULL_TREE;                                                                                                                  
it could instead for INTEGER_TYPE_P (atype) do
  atype = build_nonstandard_integer_type (TYPE_PRECISION (type), 1);
and retry (can be done also by
atype = build_nonstandard_integer_type (TYPE_PRECISION (type), 1);
return fold_convert_loc (loc, type, fold_binary_loc (loc, code, atype, fold_convert (atype, arg0), fold_convert (atype, arg1)));
).
E.g. for
int
foo (int x, int y)
{
  return (x + __INT_MAX__) + (int) (y + __INT_MAX__);
}
where __INT_MAX__ + __INT_MAX__ overflows, but if say
x and y are (- __INT_MAX__ / 4 * 3), then there is no
overflow originally.  But we'd give up on this already because there are
two different variables.  So perhaps better
int
foo (int x)
{
  return (x + __INT_MAX__) + (int) (x + __INT_MAX__);
}
And similarly the retry with unsigned type could be done for
the var0 && var1 case where it sets ok = false;.
> 
> int
> bar (int x, unsigned int y)
> {
>   return (x + 1) + (int) (y + 1);
> }

	Jakub
Sebastian Huber Nov. 9, 2012, 3:17 p.m. UTC | #3 
Hello Jakub,

with your patch and 4.8.0 20121109 the problem in PR55137 vanishes and I am 
able to run the RTEMS testsuite on PowerPC again.  Thanks.
diff mbox

Patch

--- gcc/fold-const.c.jj	2012-11-07 09:16:41.929494183 +0100
+++ gcc/fold-const.c	2012-11-07 09:47:12.227710542 +0100
@@ -10337,6 +10337,7 @@  fold_binary_loc (location_t loc,
 	{
 	  tree var0, con0, lit0, minus_lit0;
 	  tree var1, con1, lit1, minus_lit1;
+	  tree atype = type;
 	  bool ok = true;
 
 	  /* Split both trees into variables, constants, and literals.  Then
@@ -10352,11 +10353,25 @@  fold_binary_loc (location_t loc,
 	  if (code == MINUS_EXPR)
 	    code = PLUS_EXPR;
 
-	  /* With undefined overflow we can only associate constants with one
-	     variable, and constants whose association doesn't overflow.  */
+	  /* With undefined overflow prefer doing association in a type
+	     which wraps on overflow, if that is one of the operand types.  */
 	  if ((POINTER_TYPE_P (type) && POINTER_TYPE_OVERFLOW_UNDEFINED)
 	      || (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type)))
 	    {
+	      if (INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+		  && TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0)))
+		atype = TREE_TYPE (arg0);
+	      else if (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
+		       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg1)))
+		atype = TREE_TYPE (arg1);
+	      gcc_assert (TYPE_PRECISION (atype) == TYPE_PRECISION (type));
+	    }
+
+	  /* With undefined overflow we can only associate constants with one
+	     variable, and constants whose association doesn't overflow.  */
+	  if ((POINTER_TYPE_P (atype) && POINTER_TYPE_OVERFLOW_UNDEFINED)
+	      || (INTEGRAL_TYPE_P (atype) && !TYPE_OVERFLOW_WRAPS (atype)))
+	    {
 	      if (var0 && var1)
 		{
 		  tree tmp0 = var0;
@@ -10367,14 +10382,14 @@  fold_binary_loc (location_t loc,
 		  if (CONVERT_EXPR_P (tmp0)
 		      && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (tmp0, 0)))
 		      && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (tmp0, 0)))
-			  <= TYPE_PRECISION (type)))
+			  <= TYPE_PRECISION (atype)))
 		    tmp0 = TREE_OPERAND (tmp0, 0);
 		  if (TREE_CODE (tmp1) == NEGATE_EXPR)
 		    tmp1 = TREE_OPERAND (tmp1, 0);
 		  if (CONVERT_EXPR_P (tmp1)
 		      && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (tmp1, 0)))
 		      && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (tmp1, 0)))
-			  <= TYPE_PRECISION (type)))
+			  <= TYPE_PRECISION (atype)))
 		    tmp1 = TREE_OPERAND (tmp1, 0);
 		  /* The only case we can still associate with two variables
 		     is if they are the same, modulo negation and bit-pattern
@@ -10382,16 +10397,6 @@  fold_binary_loc (location_t loc,
 		  if (!operand_equal_p (tmp0, tmp1, 0))
 		    ok = false;
 		}
-
-	      if (ok && lit0 && lit1)
-		{
-		  tree tmp0 = fold_convert (type, lit0);
-		  tree tmp1 = fold_convert (type, lit1);
-
-		  if (!TREE_OVERFLOW (tmp0) && !TREE_OVERFLOW (tmp1)
-		      && TREE_OVERFLOW (fold_build2 (code, type, tmp0, tmp1)))
-		    ok = false;
-		}
 	    }
 
 	  /* Only do something if we found more than two objects.  Otherwise,
@@ -10402,10 +10407,16 @@  fold_binary_loc (location_t loc,
 		       + (lit0 != 0) + (lit1 != 0)
 		       + (minus_lit0 != 0) + (minus_lit1 != 0))))
 	    {
-	      var0 = associate_trees (loc, var0, var1, code, type);
-	      con0 = associate_trees (loc, con0, con1, code, type);
-	      lit0 = associate_trees (loc, lit0, lit1, code, type);
-	      minus_lit0 = associate_trees (loc, minus_lit0, minus_lit1, code, type);
+	      bool any_overflows = false;
+	      if (lit0) any_overflows |= TREE_OVERFLOW (lit0);
+	      if (lit1) any_overflows |= TREE_OVERFLOW (lit1);
+	      if (minus_lit0) any_overflows |= TREE_OVERFLOW (minus_lit0);
+	      if (minus_lit1) any_overflows |= TREE_OVERFLOW (minus_lit1);
+	      var0 = associate_trees (loc, var0, var1, code, atype);
+	      con0 = associate_trees (loc, con0, con1, code, atype);
+	      lit0 = associate_trees (loc, lit0, lit1, code, atype);
+	      minus_lit0 = associate_trees (loc, minus_lit0, minus_lit1,
+					    code, atype);
 
 	      /* Preserve the MINUS_EXPR if the negative part of the literal is
 		 greater than the positive part.  Otherwise, the multiplicative
@@ -10419,38 +10430,45 @@  fold_binary_loc (location_t loc,
 		      && tree_int_cst_lt (lit0, minus_lit0))
 		    {
 		      minus_lit0 = associate_trees (loc, minus_lit0, lit0,
-						    MINUS_EXPR, type);
+						    MINUS_EXPR, atype);
 		      lit0 = 0;
 		    }
 		  else
 		    {
 		      lit0 = associate_trees (loc, lit0, minus_lit0,
-					      MINUS_EXPR, type);
+					      MINUS_EXPR, atype);
 		      minus_lit0 = 0;
 		    }
 		}
+
+	      /* Don't introduce overflows through reassociation.  */
+	      if (!any_overflows
+		  && ((lit0 && TREE_OVERFLOW (lit0))
+		      || (minus_lit0 && TREE_OVERFLOW (minus_lit0))))
+		return NULL_TREE;
+
 	      if (minus_lit0)
 		{
 		  if (con0 == 0)
 		    return
 		      fold_convert_loc (loc, type,
 					associate_trees (loc, var0, minus_lit0,
-							 MINUS_EXPR, type));
+							 MINUS_EXPR, atype));
 		  else
 		    {
 		      con0 = associate_trees (loc, con0, minus_lit0,
-					      MINUS_EXPR, type);
+					      MINUS_EXPR, atype);
 		      return
 			fold_convert_loc (loc, type,
 					  associate_trees (loc, var0, con0,
-							   PLUS_EXPR, type));
+							   PLUS_EXPR, atype));
 		    }
 		}
 
-	      con0 = associate_trees (loc, con0, lit0, code, type);
+	      con0 = associate_trees (loc, con0, lit0, code, atype);
 	      return
 		fold_convert_loc (loc, type, associate_trees (loc, var0, con0,
-							      code, type));
+							      code, atype));
 	    }
 	}
 
--- gcc/testsuite/g++.dg/opt/pr55137.C.jj	2012-11-07 09:31:45.027160654 +0100
+++ gcc/testsuite/g++.dg/opt/pr55137.C	2012-11-07 09:31:45.028160649 +0100
@@ -0,0 +1,4 @@ 
+// PR c++/55137
+// { dg-do compile }
+
+enum E { F = -1 + (int) (sizeof (int) - 1) };
--- gcc/testsuite/gcc.c-torture/execute/pr55137.c.jj	2012-11-07 09:44:11.226768063 +0100
+++ gcc/testsuite/gcc.c-torture/execute/pr55137.c	2012-11-07 09:44:24.380691303 +0100
@@ -0,0 +1,30 @@ 
+/* PR c++/55137 */
+
+extern void abort (void);
+
+int
+foo (unsigned int x)
+{
+  return ((int) (x + 1U) + 1) < (int) x;
+}
+
+int
+bar (unsigned int x)
+{
+  return (int) (x + 1U) + 1;
+}
+
+int
+baz (unsigned int x)
+{
+  return x + 1U;
+}
+
+int
+main ()
+{
+  if (foo (__INT_MAX__) != (bar (__INT_MAX__) < __INT_MAX__)
+      || foo (__INT_MAX__) != ((int) baz (__INT_MAX__) + 1 < __INT_MAX__))
+    abort ();
+  return 0;
+}