This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Determine more IVs to be non-overflowing
- From: Richard Biener <rguenther at suse dot de>
- To: Jan Hubicka <hubicka at ucw dot cz>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Tue, 5 Jul 2016 15:52:36 +0200 (CEST)
- Subject: Re: Determine more IVs to be non-overflowing
- Authentication-results: sourceware.org; auth=none
- References: <20160627140938.GF98078@kam.mff.cuni.cz> <alpine.LSU.2.11.1606290934010.29772@t29.fhfr.qr> <20160629080804.GA12114@kam.mff.cuni.cz> <alpine.LSU.2.11.1606291010410.29772@t29.fhfr.qr> <20160629105100.GA17019@kam.mff.cuni.cz> <20160630130301.GA40315@kam.mff.cuni.cz> <alpine.LSU.2.11.1607011330580.29772@t29.fhfr.qr> <20160703104754.GA83834@kam.mff.cuni.cz>
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 <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)