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 <rguent...@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" } } */
