Re: VRP: undefined shifting calculation should not need sign bit

[Aldy Hernandez <aldyh at redhat dot com>]

On 10/17/18 6:52 AM, Richard Sandiford wrote:
> Aldy Hernandez <aldyh@redhat.com> writes:
> > On 9/13/18 3:33 AM, Richard Sandiford wrote:
> > > Aldy Hernandez <aldyh@redhat.com> writes:
> > > > On 09/12/2018 12:57 PM, Richard Sandiford wrote:
> > > > > Aldy Hernandez <aldyh@redhat.com> writes:
> > > > > > diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
> > > > > > index 589fdea4df6..e9ee418e5b2 100644
> > > > > > --- a/gcc/wide-int-range.h
> > > > > > +++ b/gcc/wide-int-range.h
> > > > > > @@ -131,7 +131,7 @@ extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
> > > > > >     /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */
> > > > > >     
> > > > > >     inline bool
> > > > > > -wide_int_range_shift_undefined_p (signop sign, unsigned prec,
> > > > > > +wide_int_range_shift_undefined_p (unsigned prec,
> > > > > >     				  const wide_int &min, const wide_int &max)
> > > > > >     {
> > > > > >       /* ?? Note: The original comment said this only applied to
> > > > > > @@ -142,7 +142,7 @@ wide_int_range_shift_undefined_p (signop sign, unsigned prec,
> > > > > >          behavior from the shift operation.  We cannot even trust
> > > > > >          SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
> > > > > >          shifts, and the operation at the tree level may be widened.  */
> > > > > > -  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
> > > > > > +  return wi::sign_mask (min) || wi::ge_p (max, prec, UNSIGNED);
> > > > >
> > > > > I don't think this is a good idea.  Logically the comparison should
> > > > > be done relative to the TYPE_SIGN of the type, so I think the original
> > > > > code was correct.
> > > >
> > > > The operation to calculate undefinedness must be done with the type of
> > > > the RHS, as opposed to the type of the entire operation.  This can be
> > > > confusing, as most operations use the same type for all operands as well
> > > > as for the type of the entire operation.  For example, AFAICT, the
> > > > following is valid gimple:
> > > >
> > > > 	UINT64 = UINT64 << INT32
> > > >
> > > > The original code was doing this (correctly), but since it was confusing
> > > > to remember which type to pass, I rewrote the above function to not need
> > > > the sign of the RHS.  This came about because in my ranger work, I
> > > > passed the wrong type which took forever to find ;-).  My patch avoids
> > > > further confusion.
> > > >
> > > > Am I missing a subtle incorrectness in my approach?
> > >
> > > The problem is with things like UINT256 << UINT8 vs. UINT256 << INT8.
> > > A range of [128, 131] on the UINT8 would be represented using the same
> > > wide_ints as a range of [-128, -125] on the INT8, but the former is
> > > well-defined while the latter isn't.  Only the TYPE_SIGN tells you
> > > which applies.
> > >
> > > The original code got this right, but the new code effectively assumes
> > > all shift amounts are signed, and so would treat UINT8 like INT8.
> > >
> > > OK, so no current target actually supports UINT256 AFAIK, so it might
> > > be academic.  But the original point of wide-int.h was to support such
> > > wide types, so they could become a thing in future.
> > >
> > > Thanks,
> > > Richard
> >
> > As promised.  Here is the reversal of the bits you suggested.
>
> Thanks!
>
> > I think this is an obvious patch, but would appreciate a sanity peek.
> >
> > Aldy
> >
> > commit 38a335af9aa5d72778fbacba247ab2219672da7b
> > Author: Aldy Hernandez <aldyh@redhat.com>
> > Date:   Wed Oct 17 11:25:21 2018 +0200
> >
> >              * wide-int-range.h (wide_int_range_shift_undefined_p): Adjust to
> >              use sign as argument.
> >              * tree-vrp.c (extract_range_from_binary_expr_1): Pass sign to
> >              wide_int_range_shift_undefined_p.
> >
> > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> > index cbc2ea2f26b..c519613bb28 100644
> > --- a/gcc/tree-vrp.c
> > +++ b/gcc/tree-vrp.c
> > @@ -1521,7 +1521,8 @@ extract_range_from_binary_expr_1 (value_range *vr,
> >   	   || code == LSHIFT_EXPR)
> >       {
> >         if (range_int_cst_p (&vr1)
> > -	  && !wide_int_range_shift_undefined_p (prec,
> > +	  && !wide_int_range_shift_undefined_p (TYPE_SIGN (TREE_TYPE (vr1.min)),
> > +						prec,
> >   						wi::to_wide (vr1.min),
> >   						wi::to_wide (vr1.max)))
> >   	{
> > diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
> > index e9ee418e5b2..589fdea4df6 100644
> > --- a/gcc/wide-int-range.h
> > +++ b/gcc/wide-int-range.h
> > @@ -131,7 +131,7 @@ extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
> >   /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */
> >   
> >   inline bool
> > -wide_int_range_shift_undefined_p (unsigned prec,
> > +wide_int_range_shift_undefined_p (signop sign, unsigned prec,
> >   				  const wide_int &min, const wide_int &max)
>
> Need to add SIGN back to the comment, maybe something like:
>
>    /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior,
>       interpreting MIN and MAX according to SIGN.  */
>
> (or whatever you think's best).

Done.

Committed.

Thanks.
Aldy