[PATCH] Allow non-overflow ops in vect_is_simple_reduction_1

[Tom de Vries]

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.  */
...
?

> +  /* 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);
...
?

> +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.
>

Done.

OK for trunk if bootstrap and reg-test succeeds?

Thanks,
- Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Allow-non-overflow-ops-in-reductions.patch
Type: text/x-patch
Size: 10841 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150729/f7bdaf5b/attachment.bin>