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

[Alexander Monakov <amonakov@ispras.ru>]

On Fri, 19 May 2017, Richard Biener wrote:

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

I think it's possible to keep this folding, note that it's valid to transform to

    (n * 1 * z) * 500000

(i.e. accumulate multiplications on the outermost factor)

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

so would it be possible to adjust things here to remove the innermost
multiplication instead?

Alexander