Re: [PATCH] Allow non-overflow ops in vect_is_simple_reduction_1

[Richard Biener <richard dot guenther at gmail dot com>]

On Wed, Jul 29, 2015 at 7:18 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 29/07/15 14:00, Richard Biener wrote:
>>
>> On Wed, Jul 29, 2015 at 1:22 PM, Tom de Vries <Tom_deVries@mentor.com>
>> wrote:
>>>
>>> On 29/07/15 10:09, Richard Biener wrote:
>>>>
>>>>
>>>> On Tue, Jul 28, 2015 at 2:08 PM, Tom de Vries <Tom_deVries@mentor.com>
>>>> wrote:
>>>>>
>>>>>
>>>>> On 28/07/15 09:59, Richard Biener wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Fri, Jul 24, 2015 at 4:39 PM, Tom de Vries <Tom_deVries@mentor.com>
>>>>>>
>>>>>>
>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> this patch allows parallelization and vectorization of reduction
>>>>>>> operators
>>>>>>> that are guaranteed to not overflow (such as min and max operators),
>>>>>>> independent of the overflow behaviour of the type.
>>>>>>>
>>>>>>> Bootstrapped and reg-tested on x86_64.
>>>>>>>
>>>>>>> OK for trunk?
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> Hmm, I don't like that no_overflow_tree_code function.  We have a much
>>>>>> more
>>>>>> clear understanding which codes may overflow or trap.  Thus please add
>>>>>> a operation specific variant of TYPE_OVERFLOW_{TRAPS,WRAPS,UNDEFINED}
>>>>>> like
>>>>>>
>>>>>
>>>>> Done.
>>>>>
>>>>>> bool
>>>>>> operation_overflow_traps (tree type, enum tree_code code)
>>>>>> {
>>>>>>      if (!ANY_INTEGRAL_TYPE_P (type)
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> I've changed this test into a gcc_checking_assert.
>>>>>
>>>>>
>>>>>>         || !TYPE_OVERFLOW_TRAPS (type))
>>>>>>        return false;
>>>>>>      switch (code)
>>>>>>        {
>>>>>>        case PLUS_EXPR:
>>>>>>        case MINUS_EXPR:
>>>>>>        case MULT_EXPR:
>>>>>>        case LSHIFT_EXPR:
>>>>>>           /* Can overflow in various ways */
>>>>>>        case TRUNC_DIV_EXPR:
>>>>>>        case EXACT_DIV_EXPR:
>>>>>>        case FLOOR_DIV_EXPR:
>>>>>>        case CEIL_DIV_EXPR:
>>>>>>           /* For INT_MIN / -1 */
>>>>>>        case NEGATE_EXPR:
>>>>>>        case ABS_EXPR:
>>>>>>           /* For -INT_MIN */
>>>>>>           return true;
>>>>>>        default:
>>>>>>           return false;
>>>>>>       }
>>>>>> }
>>>>>>
>>>>>> and similar variants for _wraps and _undefined.  I think we decided at
>>>>>> some point
>>>>>> the compiler should not take advantage of the fact that lshift or
>>>>>> *_div have undefined
>>>>>> behavior on signed integer overflow, similar we only take advantage of
>>>>>> integral-type
>>>>>> overflow behavior, not vector or complex.  So we could reduce the
>>>>>> number of cases
>>>>>> the functions return true if we document that it returns true only for
>>>>>> the cases where
>>>>>> the compiler needs to / may assume wrapping behavior does not take
>>>>>> place.
>>>>>> As for _traps for example we only have optabs and libfuncs for
>>>>>> plus,minus,mult,negate
>>>>>> and abs.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> I've tried to capture all of this in the three new functions:
>>>>> - operation_overflows_and_traps
>>>>> - operation_no_overflow_or_wraps
>>>>> - operation_overflows_and_undefined (unused atm)
>>>>>
>>>>> I've also added the graphite bit.
>>>>>
>>>>> OK for trunk, if bootstrap and reg-test succeeds?
>>>>
>>>>
>>>>
>>>> +/* Returns true if CODE operating on operands of type TYPE can
>>>> overflow,
>>>> and
>>>> +   fwrapv generates trapping insns for CODE.  */
>>>>
>>>> ftrapv
>>>>
>>>
>>> Done.
>>>
>>>> +bool
>>>> +operation_overflows_and_traps (tree type, enum tree_code code)
>>>> +{
>>>>
>>>> operation_overflow_traps
>>>>
>>>> is better wording.  Meaning that when the operation overflows then it
>>>> traps.
>>>>
>>>
>>> AFAIU, the purpose of the function is to enable optimizations when it
>>> returns false, that is:
>>> - if the operation doesn't overflow, or
>>> - if the operation overflows, but doesn't trap.
>>>
>>> The name operation_overflow_traps does not make clear what it returns
>>> when
>>> the operation doesn't overflow. If the name doesn't make it clear, you
>>> need
>>> to be conservative, that is, return true. Which defies the purpose of the
>>> function.
>>>
>>> I've changed the name to operation_no_trapping_overflow (and inverted
>>> logic
>>> in the function).
>>>
>>> But perhaps you want operation_overflow_traps with a conservative return
>>> for
>>> non-overflow operations, and use it like this:
>>> ...
>>>    else if (INTEGRAL_TYPE_P (type) && check_reduction)
>>>      {
>>>        if (operation_overflows (type, code)
>>>            && operation_overflow_traps (type, code))
>>>          {
>>>            /* Changing the order of operations changes the semantics.  */
>>> ...
>>> ?
>>
>>
>> I think operation_no_trapping_overflow has the same wording issue as
>> operation_overflow_traps but I'm not a native speaker
>
>
> Hmm, I'm also not a native speaker. I think I understand what you mean, if
> operation_no_trapping_overflow is read with stress on 'trapping', we have
> the same ambiguity issue.
>
> [ Possibility: a more verbose variant, but I hope no ambiguity:
> operation_can_overflow_and_trap ? ]

I'd say we choose a small name and simply refer to documentation.

>
>> so I'll take your
>>
>> word that operation_no_trapping_overflow is non-ambiguous iff the
>> operation cannot overflow.
>>
>> And no, I didn't mean to use it in combination with operation_overflows.
>>
>>>> +  /* We don't take advantage of integral type overflow behaviour for
>>>> complex and
>>>> +     vector types.  */
>>>>
>>>> We don't generate instructions that trap on overflow for complex or
>>>> vector
>>>> types
>>>>
>>>
>>> Done.
>>>
>>>> +  if (!INTEGRAL_TYPE_P (type))
>>>> +    return true;
>>>>
>>>> +  switch (code)
>>>> +    {
>>>> +    case PLUS_EXPR:
>>>> +    case MINUS_EXPR:
>>>> +    case MULT_EXPR:
>>>> +    case LSHIFT_EXPR:
>>>> +      /* Can overflow in various ways.  */
>>>>
>>>> we don't have a trapping optab for lshift
>>>>
>>>> +    case TRUNC_DIV_EXPR:
>>>> +    case EXACT_DIV_EXPR:
>>>> +    case FLOOR_DIV_EXPR:
>>>> +    case CEIL_DIV_EXPR:
>>>>
>>>> nor division.  See optabs.c:optab_for_tree_code.  I suggest to only
>>>> return
>>>> true
>>>> for those.
>>>>
>>>
>>> Before the logic inversion, we return false for these (And also for
>>> operators that do not overflow).
>>>
>>>> +/* Returns true if CODE operating on operands of type TYPE cannot
>>>> overflow, or
>>>> +   wraps on overflow.  */
>>>> +
>>>> +bool
>>>> +operation_no_overflow_or_wraps (tree type, enum tree_code code)
>>>> +{
>>>> +  gcc_checking_assert (ANY_INTEGRAL_TYPE_P (type));
>>>>
>>>> operation_overflow_wraps ()
>>>>
>>>> is still my preferred name.
>>>>
>>>
>>> The name operation_overflow_wraps doesn't make clear what it returns if
>>> the
>>> operation doesn't overflow. And I didn't manage to come up with a better
>>> name sofar.
>>>
>>> Btw, I wonder about something like vector max operation. The current
>>> implementation of operation_no_overflow_or_wraps returns false. Could we
>>> do:
>>> ...
>>>   /* We don't take advantage of integral type overflow behaviour for
>>>      complex and vector types.  */
>>>    if (!INTEGRAL_TYPE_P (type))
>>>      return !operation_overflows (type, code);
>>> ...
>>> ?
>>
>>
>> Yes, we can use operation_overflows and the existing overflow macros as
>> well:
>>
>>    if (!INTEGRAL_TYPE_P (type)
>>       || TYPE_OVERFLOW_WRAPS (type)
>>       || !operation_overflows (type, code))
>>
>
> For an unsigned vector add, this would evaluate to true.

Yes, so?

> You remarked "similar we only take advantage of integral-type overflow
> behavior, not vector or complex". Was that remark then limited to exploiting
> undefined behaviour?

Yes, but it's also not documented anywhere.

>> and get rid of operation_overflow_{wraps,undefined}
>
>
> That's not what I meant, but ok.
>
>> unless we want to take
>>
>> advantage of the cases the compiler doesn't take advantage of the overflow
>> behavior.
>
>
> I thought the purpose of the functions was to specify in one location and
> clearly documented the situations that the compiler is allowed to take
> advantage of the overflow behavior.

Yeah, but we're iterating over names here and that's not good progress ;)

We can always followup with that.

>>  I think keeping the traps variant separate makes sense because
>> of the clear facts on what trapping optabs we implement.
>>
>>>> +bool
>>>> +operation_overflow_and_undefined (tree type, enum tree_code code)
>>>> +{
>>>> +  gcc_checking_assert (ANY_INTEGRAL_TYPE_P (type));
>>>> +
>>>>
>>>> operation_overflow_undefined ()
>>>>
>>>
>>> The name operation_overflow_undefined doesn't make clear what it returns
>>> if
>>> the operation doesn't overflow. I've changed it into
>>> operation_undefined_overflow.
>>>
>>>> If you like to keep an explicit operation_can_overflow then there is the
>>>> opportunity to split out the switch statement from
>>>> operation_overflow_wraps
>>>> and operation_overflow_undefined.
>>>>
>>
>> Why 'operation_overflows' ...  it's operation_can_overflow, it clearly
>> doesn't
>> always overflow...
>
>
> Done.
>
>> Also it doesn't need its type argument (the assert
>> doesn't make much sense, for example fixed-point types can overflow
>> as well, likewise real types).
>
>
> Done.
>
>>
>> I'm fine with operation_no_trapping_overflow as in the patch, likewise
>> with operation_overflows apart from its name.
>>
>> operation_no_overflow_or_wraps can be replaced by
>> ANY_INTEGRAL_TYPE_P ()
>> && (TYPE_OVERFLOW_WRAPS () || !operation_can_overflows (code))
>>
>> conservatively operation_undefined_overflow could be treated the same
>> and I'd prefer to do it that way for now.
>>
>
> Dropped wrap/undefined functions.
>
> OK like this?

Ok.

Thanks,
Richard.

> Thanks,
> - Tom