Re: [PATCH] Fix PR66313

[Richard Biener <rguenther at suse dot de>]

On Tue, 27 Oct 2015, Joseph Myers wrote:

> On Tue, 27 Oct 2015, Richard Biener wrote:
> 
> > When factoring a*b + a*c to (b + c)*a we have to guard against the
> > case of a == 0 as after the factoring b + c might overflow in that
> > case.  Fixed by doing the addition in an unsigned type if required.
> 
> The same applies to a == -1 (consider b and c equal to -(INT_MIN/2), when 
> a*b + a*c is INT_MIN but b+c overflows).  In that case, if you avoid b+c 
> overflowing using an unsigned type, but convert back to signed for the 
> multiplication, you get a spurious overflow from the multiplication 
> instead.

Indeed.  So the following is as good as I can get it.

We still regress gcc.dg/tree-ssa/tailrecursion-6.c with it though.
There we have

int
foo (int a)
{
        if (a)
                return a * (2 * (foo (a - 1))) + a + 1;
        else
                return 0;
}

and tailrecursion detection requires the expression to be
in the form (2 * (foo (a - 1)) + 1) * a + 1 but folding
can't see that (2 * (foo (a - 1)) + 1) might not be INT_MIN
when a is -1.  Well, I can't trivially either, maybe its
just because of the recursion or maybe it's because here
we are sure that C in C * A is odd (2 * sth + 1) or
simply because we know that C in (B + C)*A is positive
and non-zero?

But I guess for the isolated view of the
a * (2 * X) + a expression we can't factor it using signed
arithmetic because of the a == 0 case as then the sum
might trivially overflow (of course here a is not zero
because of the guard...)

Bootstrap / regtest in progress on x86_64-unknown-linux-gnu.

More hole-punching appreciated.  Meanwhile I found PR68142...

Richard.

2015-10-27  Richard Biener  <rguenther@suse.de>

	PR middle-end/66313
	* fold-const.c (fold_plusminus_mult_expr): If the factored
	factor may be zero use a wrapping type for the inner operation.

	* c-c++-common/ubsan/pr66313.c: New testcase.

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c.orig	2015-10-29 09:27:42.942302445 +0100
+++ gcc/fold-const.c	2015-10-29 10:35:42.794378063 +0100
@@ -6916,10 +6916,11 @@ fold_plusminus_mult_expr (location_t loc
     }
   same = NULL_TREE;
 
-  if (operand_equal_p (arg01, arg11, 0))
-    same = arg01, alt0 = arg00, alt1 = arg10;
-  else if (operand_equal_p (arg00, arg10, 0))
+  /* Prefer factoring a common non-constant.  */
+  if (operand_equal_p (arg00, arg10, 0))
     same = arg00, alt0 = arg01, alt1 = arg11;
+  else if (operand_equal_p (arg01, arg11, 0))
+    same = arg01, alt0 = arg00, alt1 = arg10;
   else if (operand_equal_p (arg00, arg11, 0))
     same = arg00, alt0 = arg01, alt1 = arg10;
   else if (operand_equal_p (arg01, arg10, 0))
@@ -6974,14 +6975,36 @@ fold_plusminus_mult_expr (location_t loc
 	}
     }
 
-  if (same)
+  if (!same)
+    return NULL_TREE;
+
+  if (! INTEGRAL_TYPE_P (type)
+      || TYPE_OVERFLOW_WRAPS (type)
+      /* We are neither factoring zero nor minus one.  */
+      || TREE_CODE (same) == INTEGER_CST)
     return fold_build2_loc (loc, MULT_EXPR, type,
 			fold_build2_loc (loc, code, type,
 				     fold_convert_loc (loc, type, alt0),
 				     fold_convert_loc (loc, type, alt1)),
 			fold_convert_loc (loc, type, same));
 
-  return NULL_TREE;
+  /* Same may be zero and thus the operation 'code' may overflow.  Likewise
+     same may be minus one and thus the multiplication may overflow.  Perform
+     the operations in an unsigned type.  */
+  tree utype = unsigned_type_for (type);
+  tree tem = fold_build2_loc (loc, code, utype,
+			      fold_convert_loc (loc, utype, alt0),
+			      fold_convert_loc (loc, utype, alt1));
+  /* If the sum evaluated to a constant that is not -INF the multiplication
+     cannot overflow.  */
+  if (TREE_CODE (tem) == INTEGER_CST
+      && ! wi::eq_p (tem, wi::min_value (TYPE_PRECISION (utype), SIGNED)))
+    return fold_build2_loc (loc, MULT_EXPR, type,
+			    fold_convert (type, tem), same);
+
+  return fold_convert_loc (loc, type,
+			   fold_build2_loc (loc, MULT_EXPR, utype, tem,
+					    fold_convert_loc (loc, utype, same)));
 }
 
 /* Subroutine of native_encode_expr.  Encode the INTEGER_CST
@@ -7835,6 +7858,7 @@ fold_unary_loc (location_t loc, enum tre
 
     case VIEW_CONVERT_EXPR:
       if (TREE_CODE (op0) == MEM_REF)
+	/* ???  Bogus for aligned types.  */
 	return fold_build2_loc (loc, MEM_REF, type,
 				TREE_OPERAND (op0, 0), TREE_OPERAND (op0, 1));
 
Index: gcc/testsuite/c-c++-common/ubsan/pr66313.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/testsuite/c-c++-common/ubsan/pr66313.c	2015-10-29 10:37:11.256355126 +0100
@@ -0,0 +1,26 @@
+/* { dg-do run } */
+/* { dg-options "-fsanitize=undefined -fsanitize-undefined-trap-on-error" } */
+
+int __attribute__((noinline,noclone))
+f(int a, int b, int c)
+{
+  return a * b + a * c;
+}
+int __attribute__((noinline,noclone))
+g(int a)
+{
+  return a * (__INT_MAX__/2) + a * (__INT_MAX__/2 + 2);
+}
+int __attribute__((noinline,noclone))
+h(int a, int b)
+{
+  return a * (__INT_MAX__/2 + 1) + b * (__INT_MAX__/2 + 1);
+}
+int main()
+{
+  volatile int tem = f(0, __INT_MAX__, __INT_MAX__);
+  tem = f(-1, __INT_MAX__/2 + 1, __INT_MAX__/2 + 1);
+  tem = g(-1);
+  tem = h(-1, -1);
+  return 0;
+}
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-15.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-15.c.orig	2015-06-09 15:45:27.035343301 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-15.c	2015-10-29 09:29:19.591367630 +0100
@@ -19,8 +19,8 @@ int bla(void)
 }
 
 /* Since the loop is removed, there should be no addition.  */
-/* { dg-final { scan-tree-dump-times "\\+" 0 "optimized" } } */
-/* { dg-final { scan-tree-dump-times "n_. \\* n_." 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\+ " 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\* " 1 "optimized" } } */
 
 /* The if from the loop header copying remains in the code.  */
 /* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */