Re: Determine more IVs to be non-overflowing

[Jan Hubicka <hubicka at ucw dot cz>]

> 
> This can overflow for __uint128_t IV iterating to UINT128_MAX I think
> given widest_int has only precision of TImode on x86_64?  An 
> after-the-fact check like
> 
>    if (nit == 0)
>      return true;
> 
> does the trick I guess.

OK, I suppose we need to review niter and related code for similar overflow possibilities.
This approximation of infinite math precision is bit iffy :))

I wonder if widest int should not trap on overflows with checking enabled.
> 
> Otherwise the patch looks ok now - thanks for the extensive comments ;)

Thanks for the patience! :)

Honza
> 
> Richard.
> 
> > +
> > +  /* NIT is typeless and can exceed the precision of the type.  In this case
> > +     overflow is always possible, because we know STEP is non-zero.  */
> > +  if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
> > +    return true;
> > +  wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
> > +
> > +
> > +  /* If step can be positive, check that nit*step <= type_max-base.
> > +     This can be done by unsigned arithmetic and we only need to watch overflow
> > +     in the multiplication. The right hand side can always be represented in
> > +     the type.  */
> > +  if (sgn == UNSIGNED || !wi::neg_p (step_max))
> > +    {
> > +      bool overflow = false;
> > +      if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
> > +		     type_max - base_max)
> > +	  || overflow)
> > +	return true;
> > +    }
> > +  /* If step can be negative, check that nit*(-step) <= base_min-type_min.  */
> > +  if (sgn == SIGNED && wi::neg_p (step_min))
> > +    {
> > +      bool overflow = false, overflow2 = false;
> > +      if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
> > +		     nit2, UNSIGNED, &overflow),
> > +		     base_min - type_min)
> > +	  || overflow || overflow2)
> > +        return true;
> > +    }
> > +
> > +  return false;
> > +}
> > +
> >  /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
> >     respect to WRTO_LOOP and returns its base and step in IV if possible
> >     (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
> > @@ -3375,8 +3458,12 @@ simple_iv (struct loop *wrto_loop, struc
> >    if (tree_contains_chrecs (iv->base, NULL))
> >      return false;
> >  
> > -  iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
> > -		     && TYPE_OVERFLOW_UNDEFINED (type));
> > +  iv->no_overflow = !folded_casts && nowrap_type_p (type);
> > +
> > +  if (!iv->no_overflow
> > +      && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
> > +    iv->no_overflow = true;
> > +
> >  
> >    /* Try to simplify iv base:
> >  
> > Index: tree-ssa-loop-niter.c
> > ===================================================================
> > --- tree-ssa-loop-niter.c	(revision 237908)
> > +++ tree-ssa-loop-niter.c	(working copy)
> > @@ -4105,7 +4105,7 @@ n_of_executions_at_most (gimple *stmt,
> >  bool
> >  nowrap_type_p (tree type)
> >  {
> > -  if (INTEGRAL_TYPE_P (type)
> > +  if (ANY_INTEGRAL_TYPE_P (type)
> >        && TYPE_OVERFLOW_UNDEFINED (type))
> >      return true;
> >  
> > 
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)