poly_span_traits fixes (PR 84811)

This patch fixes incorrect results for HOST_WIDE_INT positions
at opposite extremes when used with HOST_WIDE_INT sizes.  It also
fixes UB when comparing such positions with unsigned HOST_WIDE_INT
sizes (although the results in that case were wrapv-correct).

Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Richard


2018-03-21  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/84811
	* poly-int.h (poly_span_traits): Remove the T3 parameter and
	promote HOST_WIDE_INT T2 - T1 results to unsigned HOST_WIDE_INT.
	(maybe_in_range_p, known_in_range_p, ranges_known_overlap_p):
	(known_subrange_p): Update accordingly.  Cast each value involved
	in the size comparison, rather than casting the result of the
	subtraction.

gcc/testsuite/
	PR tree-optimization/84811
	* gcc.dg/torture/pr84811.c: New test.

On Wed, Mar 21, 2018 at 9:31 AM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> This patch fixes incorrect results for HOST_WIDE_INT positions

> at opposite extremes when used with HOST_WIDE_INT sizes.  It also

> fixes UB when comparing such positions with unsigned HOST_WIDE_INT

> sizes (although the results in that case were wrapv-correct).

>

> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?


OK.

Richard.

> Richard

>

>

> 2018-03-21  Richard Sandiford  <richard.sandiford@linaro.org>

>

> gcc/

>         PR tree-optimization/84811

>         * poly-int.h (poly_span_traits): Remove the T3 parameter and

>         promote HOST_WIDE_INT T2 - T1 results to unsigned HOST_WIDE_INT.

>         (maybe_in_range_p, known_in_range_p, ranges_known_overlap_p):

>         (known_subrange_p): Update accordingly.  Cast each value involved

>         in the size comparison, rather than casting the result of the

>         subtraction.

>

> gcc/testsuite/

>         PR tree-optimization/84811

>         * gcc.dg/torture/pr84811.c: New test.

>

> Index: gcc/poly-int.h

> ===================================================================

> --- gcc/poly-int.h      2018-01-14 08:42:44.497155977 +0000

> +++ gcc/poly-int.h      2018-03-21 08:28:14.656720617 +0000

> @@ -2399,30 +2399,34 @@ print_dec (const poly_int_pod<N, C> &val

>              poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED);

>  }

>

> -/* Helper for correctly comparing Pos - Start with Size in cases where

> -   known_ge (Pos, Start), Pos and Start are potentially signed, and Size is

> -   potentially unsigned.  Applying the cast function to the result of

> -   Pos - Start gives the value that should be compared with the size.

> -

> -   Try to avoid doing any unnecessary arithmetic or copying.  */

> -template<typename Pos, typename Start, typename Size,

> -        typename Diff = POLY_BINARY_COEFF (Start, Pos),

> -        typename Res = POLY_BINARY_COEFF (Size, Diff)>

> +/* Helper for calculating the distance between two points P1 and P2,

> +   in cases where known_le (P1, P2).  T1 and T2 are the types of the

> +   two positions, in either order.  The coefficients of P2 - P1 have

> +   type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2

> +   have C++ primitive type, otherwise P2 - P1 has its usual

> +   wide-int-based type.

> +

> +   The actual subtraction should look something like this:

> +

> +     typedef poly_span_traits<T1, T2> span_traits;

> +     span_traits::cast (P2) - span_traits::cast (P1)

> +

> +   Applying the cast before the subtraction avoids undefined overflow

> +   for signed T1 and T2.

> +

> +   The implementation of the cast tries to avoid unnecessary arithmetic

> +   or copying.  */

> +template<typename T1, typename T2,

> +        typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),

> +                                          unsigned HOST_WIDE_INT)>

>  struct poly_span_traits

>  {

> -  /* Assume no cast is needed.  We'll get a warning about signed vs.

> -     unsigned comparisons if the assumption is wrong.  */

>    template<typename T>

>    static const T &cast (const T &x) { return x; }

>  };

>

> -/* The only case a change in type is needed is this one, in which the

> -   subtraction would give a HOST_WIDE_INT-based result if done on poly_ints

> -   and adding a zero size would give an unsigned HOST_WIDE_INT-based

> -   result.  Since we know known_ge (Pos, Start), it is safe to treat

> -   Pos - Start as an unsigned HOST_WIDE_INT.  */

> -template<typename T1, typename T2, typename T3>

> -struct poly_span_traits<T1, T2, T3, HOST_WIDE_INT, unsigned HOST_WIDE_INT>

> +template<typename T1, typename T2>

> +struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>

>  {

>    template<typename T>

>    static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type

> @@ -2451,7 +2455,8 @@ known_size_p (const T &a)

>  inline bool

>  maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)

>  {

> -  typedef poly_span_traits<T1, T2, T3> span;

> +  typedef poly_span_traits<T1, T2> start_span;

> +  typedef poly_span_traits<T3, T3> size_span;

>    if (known_lt (val, pos))

>      return false;

>    if (!known_size_p (size))

> @@ -2462,7 +2467,8 @@ maybe_in_range_p (const T1 &val, const T

>      /* In this case we don't know whether VAL >= POS is true at compile

>         time, so we can't prove that VAL >= POS + SIZE.  */

>      return true;

> -  return maybe_lt (span::cast (val - pos), size);

> +  return maybe_lt (start_span::cast (val) - start_span::cast (pos),

> +                  size_span::cast (size));

>  }

>

>  /* Return true if range [POS, POS + SIZE) is known to include VAL.

> @@ -2473,10 +2479,12 @@ maybe_in_range_p (const T1 &val, const T

>  inline bool

>  known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)

>  {

> -  typedef poly_span_traits<T1, T2, T3> span;

> +  typedef poly_span_traits<T1, T2> start_span;

> +  typedef poly_span_traits<T3, T3> size_span;

>    return (known_size_p (size)

>           && known_ge (val, pos)

> -         && known_lt (span::cast (val - pos), size));

> +         && known_lt (start_span::cast (val) - start_span::cast (pos),

> +                      size_span::cast (size)));

>  }

>

>  /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)

> @@ -2504,8 +2512,9 @@ ranges_maybe_overlap_p (const T1 &pos1,

>  ranges_known_overlap_p (const T1 &pos1, const T2 &size1,

>                         const T3 &pos2, const T4 &size2)

>  {

> -  typedef poly_span_traits<T1, T3, T2> span1;

> -  typedef poly_span_traits<T1, T3, T4> span2;

> +  typedef poly_span_traits<T1, T3> start_span;

> +  typedef poly_span_traits<T2, T2> size1_span;

> +  typedef poly_span_traits<T4, T4> size2_span;

>    /* known_gt (POS1 + SIZE1, POS2)                         [infinite precision]

>       --> known_gt (SIZE1, POS2 - POS1)                     [infinite precision]

>       --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]

> @@ -2520,8 +2529,12 @@ ranges_known_overlap_p (const T1 &pos1,

>       which the indeterminate is zero (the minimum value).  */

>    return (known_size_p (size1)

>           && known_size_p (size2)

> -         && known_lt (span1::cast (pos2 - lower_bound (pos1, pos2)), size1)

> -         && known_lt (span2::cast (pos1 - lower_bound (pos1, pos2)), size2));

> +         && known_lt (start_span::cast (pos2)

> +                      - start_span::cast (lower_bound (pos1, pos2)),

> +                      size1_span::cast (size1))

> +         && known_lt (start_span::cast (pos1)

> +                      - start_span::cast (lower_bound (pos1, pos2)),

> +                      size2_span::cast (size2)));

>  }

>

>  /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of

> @@ -2534,15 +2547,16 @@ known_subrange_p (const T1 &pos1, const

>                   const T3 &pos2, const T4 &size2)

>  {

>    typedef typename poly_int_traits<T2>::coeff_type C2;

> -  typedef POLY_BINARY_COEFF (T2, T4) size_diff_type;

> -  typedef poly_span_traits<T1, T3, size_diff_type> span;

> +  typedef poly_span_traits<T1, T3> start_span;

> +  typedef poly_span_traits<T2, T4> size_span;

>    return (known_gt (size1, POLY_INT_TYPE (T2) (0))

>           && (poly_coeff_traits<C2>::signedness > 0

>               || known_size_p (size1))

>           && known_size_p (size2)

>           && known_ge (pos1, pos2)

>           && known_le (size1, size2)

> -         && known_le (span::cast (pos1 - pos2), size2 - size1));

> +         && known_le (start_span::cast (pos1) - start_span::cast (pos2),

> +                      size_span::cast (size2) - size_span::cast (size1)));

>  }

>

>  /* Return true if the endpoint of the range [POS, POS + SIZE) can be

> Index: gcc/testsuite/gcc.dg/torture/pr84811.c

> ===================================================================

> --- /dev/null   2018-03-17 08:19:33.716019995 +0000

> +++ gcc/testsuite/gcc.dg/torture/pr84811.c      2018-03-21 08:28:14.660640089 +0000

> @@ -0,0 +1,20 @@

> +/* { dg-do compile { target lp64 } } */

> +

> +int a;

> +long b[1][9];

> +typedef long V __attribute__((vector_size (16), may_alias));

> +

> +void

> +foo ()

> +{

> +  V *c = (V *) ((char *) b + -9060696663385964544);

> +  *c = (V) { 1, 1 };

> +  c++;

> +  *c = (V) { 1, 1 };

> +  c++;

> +  *c = (V) { 1, 1 };

> +  c++;

> +  *c = (V) { 1, 1 };

> +  long __attribute__((may_alias)) *d = (long *) ((char *) b + 162675373468811328);

> +  *d = 1;

> +}