calculate overflow type in wide int arithmetic

[Richard Biener]

On July 9, 2018 1:16:59 PM GMT+02:00, Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE> wrote:
>Hi Aldy,
>
>> On 07/05/2018 05:50 AM, Richard Biener wrote:
>>> On Thu, Jul 5, 2018 at 9:35 AM Aldy Hernandez <aldyh@redhat.com>
>wrote:
>>>>
>>>> The reason for this patch are the changes showcased in tree-vrp.c.
>>>> Basically I'd like to discourage rolling our own overflow and
>underflow
>>>> calculation when doing wide int arithmetic.  We should have a
>>>> centralized place for this, that is-- in the wide int code itself
>;-).
>>>>
>>>> The only cases I care about are plus/minus, which I have
>implemented,
>>>> but we also get division for free, since AFAICT, division can only
>>>> positive overflow:
>>>>
>>>>          -MIN / -1 => +OVERFLOW
>>>>
>>>> Multiplication OTOH, can underflow, but I've not implemented it
>because
>>>> we have no uses for it.  I have added a note in the code explaining
>this.
>>>>
>>>> Originally I tried to only change plus/minus, but that made code
>that
>>>> dealt with plus/minus in addition to div or mult a lot uglier. 
>You'd
>>>> have to special case "int overflow_for_add_stuff" and "bool
>>>> overflow_for_everything_else".  Changing everything to int, makes
>things
>>>> consistent.
>>>>
>>>> Note: I have left poly-int as is, with its concept of yes/no for
>>>> overflow.  I can adapt this as well if desired.
>>>>
>>>> Tested on x86-64 Linux.
>>>>
>>>> OK for trunk?
>>>
>>> looks all straight-forward but the following:
>>>
>>>     else if (op1)
>>>       {
>>>         if (minus_p)
>>> -       {
>>> -         wi = -wi::to_wide (op1);
>>> -
>>> -         /* Check for overflow.  */
>>> -         if (sgn == SIGNED
>>> -             && wi::neg_p (wi::to_wide (op1))
>>> -             && wi::neg_p (wi))
>>> -           ovf = 1;
>>> -         else if (sgn == UNSIGNED && wi::to_wide (op1) != 0)
>>> -           ovf = -1;
>>> -       }
>>> +       wi = wi::neg (wi::to_wide (op1));
>>>         else
>>>          wi = wi::to_wide (op1);
>>>
>>> you fail to handle - -INT_MIN.
>>
>> Woah, very good catch.  I previously had this implemented as
>wi::sub(0,
>> op1, &ovf) which was calculating overflow correctly but when I
>implemented
>> the overflow type in wi::neg I missed this.  Thanks.
>>
>>>
>>> Given the fact that for multiplication (or others, didn't look too 
>close)
>>> you didn't implement the direction indicator I wonder if it would be
>more
>>> appropriate to do
>>>
>>> enum ovfl { OVFL_NONE = 0, OVFL_UNDERFLOW = -1, OVFL_OVERFLOW = 1,
>>> OVFL_UNKNOWN = 2 };
>>>
>>> and tell us the "truth" here?
>>
>> Excellent idea...though it came with lots of typing :).  Fixed.
>>
>> BTW, if I understand correctly, I've implemented the overflow types
>> correctly for everything but multiplication (which we have no users
>for and
>> I return OVF_UNKNOWN).  I have indicated this in comments.  Also, for
>> division I did nothing special, as we can only +OVERFLOW.
>>
>>>
>>> Hopefully if (overflow) will still work with that.
>>
>> It does.
>>
>>>
>>> Otherwise can you please add a toplevel comment to wide-int.h as to
>what the
>>> overflow result semantically is for a) SIGNED and b) UNSIGNED
>operations?
>>
>> Done.  Let me know if the current comment is what you had in mind.
>>
>> OK for trunk?
>
>this patch broke SPARC bootstrap:
>
>/vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c: In function
>'tree_node* sparc_fold_builtin(tree, int, tree_node**, bool)':
>/vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:11868:52: error:
>no matching function for call to 'neg(wi::tree_to_widest_ref, bool*)'
>        tmp = wi::neg (wi::to_widest (e1), &neg1_ovf);
>                                                    ^
>In file included from
>/vol/gcc/src/hg/trunk/local/gcc/coretypes.h:399:0,
>          from /vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:27:
>/vol/gcc/src/hg/trunk/local/gcc/wide-int.h:2127:1: note: candidate:
>template<class T> typename wi::binary_traits<T, T>::result_type
>wi::neg(const T&)
> wi::neg (const T &x)
> ^~
>/vol/gcc/src/hg/trunk/local/gcc/wide-int.h:2127:1: note:   template
>argument deduction/substitution failed:
>/vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:11868:52: note:  
>candidate expects 1 argument, 2 provided
>        tmp = wi::neg (wi::to_widest (e1), &neg1_ovf);
>                                                    ^
>In file included from
>/vol/gcc/src/hg/trunk/local/gcc/coretypes.h:399:0,
>          from /vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:27:
>/vol/gcc/src/hg/trunk/local/gcc/wide-int.h:2136:1: note: candidate:
>template<class T> typename wi::binary_traits<T, T>::result_type
>wi::neg(const T&, wi::overflow_type*)
> wi::neg (const T &x, overflow_type *overflow)
> ^~
>/vol/gcc/src/hg/trunk/local/gcc/wide-int.h:2136:1: note:   template
>argument deduction/substitution failed:
>/vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:11868:43: note:  
>cannot convert '& neg1_ovf' (type 'bool*') to type 'wi::overflow_type*'
>        tmp = wi::neg (wi::to_widest (e1), &neg1_ovf);
>                                           ^~~~~~~~~
>In file included from
>/vol/gcc/src/hg/trunk/local/gcc/coretypes.h:414:0,
>          from /vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:27:
>/vol/gcc/src/hg/trunk/local/gcc/poly-int.h:1052:1: note: candidate:
>template<unsigned int N, class Ca> poly_int<N, typename
>wi::binary_traits<T2, T2>::result_type> wi::neg(const poly_int_pod<N,
>C>&)
> neg (const poly_int_pod<N, Ca> &a)
> ^~~
>/vol/gcc/src/hg/trunk/local/gcc/poly-int.h:1052:1: note:   template
>argument deduction/substitution failed:
>/vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:11868:52: note:  
>'wi::tree_to_widest_ref {aka const
>generic_wide_int<wi::extended_tree<192> >}' is not derived from 'const
>poly_int_pod<N, C>'
>        tmp = wi::neg (wi::to_widest (e1), &neg1_ovf);
>                                                    ^
>In file included from
>/vol/gcc/src/hg/trunk/local/gcc/coretypes.h:414:0,
>          from /vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:27:
>/vol/gcc/src/hg/trunk/local/gcc/poly-int.h:1063:1: note: candidate:
>template<unsigned int N, class Ca> poly_int<N, typename
>wi::binary_traits<T2, T2>::result_type> wi::neg(const poly_int_pod<N,
>C>&, wi::overflow_type*)
> neg (const poly_int_pod<N, Ca> &a, wi::overflow_type *overflow)
> ^~~
>/vol/gcc/src/hg/trunk/local/gcc/poly-int.h:1063:1: note:   template
>argument deduction/substitution failed:
>/vol/gcc/src/hg/trunk/local/gcc/config/sparc/sparc.c:11868:52: note:  
>'wi::tree_to_widest_ref {aka const
>generic_wide_int<wi::extended_tree<192> >}' is not derived from 'const
>poly_int_pod<N, C>'
>        tmp = wi::neg (wi::to_widest (e1), &neg1_ovf);
>                                                    ^
>
>and several more.  This seems to be the only backend that uses the
>additional bool * argument to wi::neg etc.
>
>Fixed as follows, bootstrapped on sparc-sun-solaris2.11.
>
>Ok for mainline?

OK. 

Richard. 

>	Rainer