On Sun, 3 Jul 2016, Jan Hubicka wrote: > Hi, > this is updated version of patch. I finally convinced myself to read bit of > wide-int.h and learnt some new things, like that they exists in multiple > precisions. I always tought of wide-int as wider version of HOST_WIDE_INT > that > can hold all of target data types with not-so handy API because it lacks the > signed flag :) > > The version bellow stay in type's precision and use the overflow flags. If > step's range is positive it check that: > > step_max * nit <= type_max-base_max > > in unsigned arithmetic (all values are positive). The right hand side can not > overflow (INT_MAX-INT_MIN is representable as unsigned int) and for left hand > side I use the unsigned mult with overflow check. > > If step can be also negative I also check: > > step_min * (-nit) <= base_min-type_min > > Clearly this path triggers only for signed types with defined overflow (as > otherwise nowrap_type returns true and iv_can_overflow_p is neve rused). It is > not very important right now. It will make more sense once ivopts is updated > to > use no-wrap flag rather htan no-overflow and we will be able to have unsgined > IVs going down. > > I also added sanity check that base's range is representable in the type's > range. > This is only because some uses of IVs weems bit sloppy WRT nops and it may > cause the right hand side of the comparsion to underflow. > > For loop infrastructure it would be very useful to have a helper which can > determine value range of an expression based on value range of individual > SSA_NAMEs in it. Would that be easy to get out of tree-vrp? > > Bootstrapped/regtested x86_64-linux, OK? > > * gcc.dg/tree-ssa/scev-14.c: new testcase. > > * tree-scalar-evolution.c (iv_can_overflow_p): New function. > (simple_iv): Use it; use nowrap_type_p to check if type can overflow. > * tree-ssa-loop-niter.c (nowrap_type_p): Use ANY_INTEGRAL_TYPE_P. > Index: testsuite/gcc.dg/tree-ssa/scev-14.c > =================================================================== > --- testsuite/gcc.dg/tree-ssa/scev-14.c (revision 0) > +++ testsuite/gcc.dg/tree-ssa/scev-14.c (working copy) > @@ -0,0 +1,11 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ > +int a[100]; > +void t(unsigned int n) > +{ > + unsigned int i; > + for (i=0; i<n; i++) > + a[i]++; > +} > +/* { dg-final { scan-tree-dump "Overflowness wrto loop niter: > No-overflow" "ivopts" } } */ > +/* { dg-final { scan-tree-dump-not "Overflowness wrto loop niter: > Overflow" "ivopts" } } */ > Index: tree-scalar-evolution.c > =================================================================== > --- tree-scalar-evolution.c (revision 237908) > +++ tree-scalar-evolution.c (working copy) > @@ -3309,6 +3309,89 @@ scev_reset (void) > } > } > > +/* Return true if the IV calculation in TYPE can overflow based on the > knowledge > + of the upper bound on the number of iterations of LOOP, the BASE and STEP > + of IV. > + > + We do not use information whether TYPE can overflow so it is safe to > + use this test even for derived IVs not computed every iteration or > + hypotetical IVs to be inserted into code. */ > + > +static bool > +iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) > +{ > + widest_int nit; > + wide_int base_min, base_max, step_min, step_max, type_min, type_max; > + signop sgn = TYPE_SIGN (type); > + > + if (integer_zerop (step)) > + return false; > + > + if (TREE_CODE (base) == INTEGER_CST) > + base_min = base_max = base; > + else if (TREE_CODE (base) == SSA_NAME > + && INTEGRAL_TYPE_P (TREE_TYPE (base)) > + && get_range_info (base, &base_min, &base_max) == VR_RANGE) > + ; > + else > + return true; > + > + if (TREE_CODE (step) == INTEGER_CST) > + step_min = step_max = step; > + else if (TREE_CODE (step) == SSA_NAME > + && INTEGRAL_TYPE_P (TREE_TYPE (step)) > + && get_range_info (step, &step_min, &step_max) == VR_RANGE) > + ; > + else > + return true; > + > + if (!get_max_loop_iterations (loop, &nit)) > + return true; > + > + type_min = wi::min_value (type); > + type_max = wi::max_value (type); > + > + /* Just sanity check that we don't see values out of the range of the type. > + In this case the arithmetics bellow would overflow. */ > + gcc_checking_assert (wi::ge_p (base_min, type_min, sgn) > + && wi::le_p (base_max, type_max, sgn)); > + > + /* Account the possible increment in the last ieration. */ > + nit = nit + 1;
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. Otherwise the patch looks ok now - thanks for the extensive comments ;) 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 <rguent...@suse.de> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)