Re: [PATCH] Prevent extract_muldiv from introducing an overflow (PR sanitizer/80800)

[Marek Polacek <polacek@redhat.com>]

On Fri, May 19, 2017 at 09:58:45AM +0200, Richard Biener wrote:
> On Fri, 19 May 2017, Marek Polacek wrote:
> 
> > extract_muldiv folds 
> > 
> >   (n * 10000 * z) * 50
> > 
> > to
> > 
> >   (n * 500000) * z
> > 
> > which is a wrong transformation to do, because it may introduce an overflow.
> > This resulted in a ubsan false positive.  So we should just disable this
> > folding altogether.  Does the approach I took make sense?
> > 
> > Bootstrapped/regtested on x86_64-linux, ok for trunk?
> 
> Didn't dig very far to identify extract_muldiv, but I guess it's either
> of the following recursions that trigger?
> 
>       /* If we can extract our operation from the LHS, do so and return a
>          new operation.  Likewise for the RHS from a MULT_EXPR.  
> Otherwise,
>          do something only if the second operand is a constant.  */
>       if (same_p
>           && (t1 = extract_muldiv (op0, c, code, wide_type,
>                                    strict_overflow_p)) != 0)
>         return fold_build2 (tcode, ctype, fold_convert (ctype, t1),
>                             fold_convert (ctype, op1));
>       else if (tcode == MULT_EXPR && code == MULT_EXPR
>                && (t1 = extract_muldiv (op1, c, code, wide_type,
>                                         strict_overflow_p)) != 0)
>         return fold_build2 (tcode, ctype, fold_convert (ctype, op0),
>                             fold_convert (ctype, t1));

Exactly.  extract_muldiv first gets (n * 10000 * z) * 50 so it tries
to fold 50 with (subexpressions) of (n * 10000 * z).  So it then tries
(n * 10000) * 50, and then n * 50 and then 10000 * 50 which finally
works out, so it uses 50000 and removes the outermost multiplication.

> thus I'd simply guard them with TYPE_OVERFLOW_WRAPS ().

That works, too.  I was afraid it'd disable too much folding.

> In the end I think the whole extract_muldiv mess should be truncated
> down to what its name suggest - identifying and removing mul-div
> cancellations.

Would be nice.  I had trouble wrapping my head around it.

> It's for example not clear whether the recursion above assumes
> TYPE_OVERFLOW_UNDEFINED (it passes a wide_type .. widening is only
> ok if there's no overflow).

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

2017-05-19  Marek Polacek  <polacek@redhat.com>

	PR sanitizer/80800
	* fold-const.c (extract_muldiv_1) <case TRUNC_DIV_EXPR>: Add
	TYPE_OVERFLOW_WRAPS checks.

	* c-c++-common/ubsan/pr80800.c: New test.
	* c-c++-common/Wduplicated-branches-1.c: Adjust an expression.


diff --git gcc/fold-const.c gcc/fold-const.c
index 19aa722..736552c 100644
--- gcc/fold-const.c
+++ gcc/fold-const.c
@@ -6281,11 +6281,13 @@ extract_muldiv_1 (tree t, tree c, enum tree_code code, tree wide_type,
 	 new operation.  Likewise for the RHS from a MULT_EXPR.  Otherwise,
 	 do something only if the second operand is a constant.  */
       if (same_p
+	  && TYPE_OVERFLOW_WRAPS (ctype)
 	  && (t1 = extract_muldiv (op0, c, code, wide_type,
 				   strict_overflow_p)) != 0)
 	return fold_build2 (tcode, ctype, fold_convert (ctype, t1),
 			    fold_convert (ctype, op1));
       else if (tcode == MULT_EXPR && code == MULT_EXPR
+	       && TYPE_OVERFLOW_WRAPS (ctype)
 	       && (t1 = extract_muldiv (op1, c, code, wide_type,
 					strict_overflow_p)) != 0)
 	return fold_build2 (tcode, ctype, fold_convert (ctype, op0),
diff --git gcc/testsuite/c-c++-common/Wduplicated-branches-1.c gcc/testsuite/c-c++-common/Wduplicated-branches-1.c
index c0b93fc..7c5062d 100644
--- gcc/testsuite/c-c++-common/Wduplicated-branches-1.c
+++ gcc/testsuite/c-c++-common/Wduplicated-branches-1.c
@@ -89,7 +89,7 @@ f (int i, int *p)
   if (i == 8) /* { dg-warning "this condition has identical branches" } */
     return i * 8 * i * 8;
   else
-    return 8 * i * 8 * i;
+    return i * 8 * i * 8;
 
 
   if (i == 9) /* { dg-warning "this condition has identical branches" } */
diff --git gcc/testsuite/c-c++-common/ubsan/pr80800.c gcc/testsuite/c-c++-common/ubsan/pr80800.c
index e69de29..992c136 100644
--- gcc/testsuite/c-c++-common/ubsan/pr80800.c
+++ gcc/testsuite/c-c++-common/ubsan/pr80800.c
@@ -0,0 +1,25 @@
+/* PR sanitizer/80800 */
+/* { dg-do run } */
+/* { dg-options "-fsanitize=undefined -fsanitize-undefined-trap-on-error" } */
+
+int n = 20000;
+int z = 0;
+
+int
+fn1 (void)
+{
+  return (n * 10000 * z) * 50;
+}
+
+int
+fn2 (void)
+{
+  return (10000 * n * z) * 50;
+}
+
+int
+main ()
+{
+  fn1 ();
+  fn2 ();
+}

	Marek