[PATCH] Allow non-overflow ops in vect_is_simple_reduction_1
Tom de Vries
Tom_deVries@mentor.com
Wed Jul 29 17:29:00 GMT 2015
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 ? ]
> 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.
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?
> 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.
> 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?
Thanks,
- Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Allow-non-overflow-ops-in-reductions.patch
Type: text/x-patch
Size: 8868 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150729/8c663573/attachment.bin>
More information about the Gcc-patches
mailing list