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

[Richard Biener <rguenther@suse.de>]

On Fri, 19 May 2017, Marek Polacek wrote:

> 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.

Yeah, happens everytime I need to chase a bug in 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?

Ok.

Thanks,
Richard.

> 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
> 
> 

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