This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Implement cond and induction cond reduction w/o REDUC_MAX_EXPR
On June 22, 2017 6:20:57 PM GMT+02:00, Alan Hayward <Alan.Hayward@arm.com> wrote:
>
>> On 22 Jun 2017, at 12:54, Richard Biener <rguenther@suse.de> wrote:
>>
>> On Thu, 22 Jun 2017, Alan Hayward wrote:
>>
>>>
>>>> On 22 Jun 2017, at 09:52, Richard Biener <rguenther@suse.de> wrote:
>>>>
>>>> On Thu, 22 Jun 2017, Richard Biener wrote:
>>>>
>>>>> On Wed, 21 Jun 2017, Richard Biener wrote:
>>>>>
>>>>>>
>>>>>> During my attempt to refactor reduction vectorization I ran
>across
>>>>>> the special casing of inital values for
>INTEGER_INDUC_COND_REDUCTION
>>>>>> and tried to see what it is about. So I ended up implementing
>>>>>> cond reduction support for targets w/o REDUC_MAX_EXPR by simply
>>>>>> doing the reduction in scalar code -- while that results in an
>>>>>> expensive epilogue the vector loop should be reasonably fast.
>>>>>>
>>>>>> I still didn't run into any exec FAILs in vect.exp with removing
>>>>>> the INTEGER_INDUC_COND_REDUCTION special case thus the following
>>>>>> patch.
>>>>>>
>>>>>> Alan -- is there a testcase (maybe full bootstrap & regtest will
>>>>>> unconver one) that shows how this is necessary?
>>>>>
>>>>> Testing has some fallout and I discovered what this special-case
>is
>>>>> about. I'll commit the below testcase to exercise the case.
>>>>
>>>> After fixing the typo (sorry) the testcase also shows a latent
>>>> wrong-code bug. We use an induction vector starting at index 1
>>>> for COND_REDUCTION to allow for a special value of zero but it
>>>> seems the INTEGER_INDUC_COND_REDUCTION special-casing of the
>>>> default value relies on the value of zero being special but
>>>> in the testcase it is meaningful…
>>>>
>>>
>>> Yes, looks like you’re right. Apologies.
>>>
>>>
>>>> In fact, given that for INTEGER_INDUC_COND_REDUCTION the
>>>> values, while based on an induction variable, do not have to
>>>> match 1:1, we can modify the testcase to use last = 2*i; or
>>>> last = i - 1; Which means we have to add a second vector
>>>> to specify whether a lane was set or not, basically use
>>>> the COND_REDUCTION code?
>>>>
>>>
>>> We could only allow loops that start from 1, but that would exclude
>the
>>> most common uses.
>>>
>>> I was wondering if we could special case “-1” as the default value
>index,
>>> but that would break the max operation in the epilogue.
>>>
>>> How about, in the loop the vectcond, instead of storing index, could
>store
>>> index+offset where offset is the value required to get the loop
>initial
>>> value to 1.
>>> Then in the epilogue, the result is:
>>> “If max == 0 ? default : max - offset"
>>>
>>> Using offset would also allow loops that start negative -
>>> for (int i = -2; i < N; i++) would have offset set to 3.
>>>
>>> is_nonwrapping_integer_induction() would have to be updated too.
>>
>> What for
>>
>> last = -i;
>>
>> then? Or non-constant step?
>
>is_nonwrapping_integer_induction currently rejects those,
>and I wouldn’t suggest changing that.
>It requires that a loop be positive increments with a fixed integer
>base and step and will not overflow.
>
>If that fails, the standard COND_REDUCTION will kick in instead.
Ah, OK. I'll see to that tomorrow if you don't beat me to it.
Richard.
>>
>> I guess we can look at the scalar evolution of the value
>> stored and simply use a variable special value, like,
>> for constant step, use CHREC_LEFT + (sign-of-CHREC_RIGHT * -1)
>> if that value is < CHREC_LEFT (hmm, so only for positive
>> constant CHREC_RIGHT).
>>
>> The easiest fix is probably to use an extra induction variable
>> and the same code as in the COND_REDUCTION case.
>>
>> Or simply use a "flag" vector that is set to -1 when the condition
>> is true, thus precompute the final != 0 vector compare value as IV.
>
>Wouldn’t this result in similar code to the COND_REDUCTION case?
>
>The INTEGER_INDUC_COND_REDUCTION cases will work fine with the
>COND_REDUCTION code. Just need to disable the initial “condition
>expression based on integer induction” in vectorise_reduciton.
>
>
>>
>> So a quick fix would be to change is_nonwrapping_integer_induction
>> to reject any CHREC that might become zero during the loop
>evaluation.
>> But it will probably disable the most interesting cases...
>>
>> Richard.
>>
>>>
>>> Alan.
>>>
>>>
>>>> Richard.
>>>>
>>>>> Richard.
>>>>>
>>>>> 2017-06-22 Richard Biener <rguenther@suse.de>
>>>>>
>>>>> * gcc.dg/vect/pr65947-14.c: New testcase.
>>>>>
>>>>> Index: gcc/testsuite/gcc.dg/vect/pr65947-14.c
>>>>>
>===================================================================
>>>>> --- gcc/testsuite/gcc.dg/vect/pr65947-14.c (nonexistent)
>>>>> +++ gcc/testsuite/gcc.dg/vect/pr65947-14.c (working copy)
>>>>> @@ -0,0 +1,44 @@
>>>>> +/* { dg-require-effective-target vect_condition } */
>>>>> +
>>>>> +#include "tree-vect.h"
>>>>> +
>>>>> +extern void abort (void) __attribute__ ((noreturn));
>>>>> +
>>>>> +#define N 27
>>>>> +
>>>>> +/* Condition reduction with matches only in even lanes at
>runtime. */
>>>>> +
>>>>> +int
>>>>> +condition_reduction (int *a, int min_v)
>>>>> +{
>>>>> + int last = N + 96;
>>>>> +
>>>>> + for (int i = 0; i < N; i++)
>>>>> + if (a[i] > min_v)
>>>>> + last = i;
>>>>> +
>>>>> + return last;
>>>>> +}
>>>>> +
>>>>> +int
>>>>> +main (void)
>>>>> +{
>>>>> + int a[N] = {
>>>>> + 47, 12, 13, 14, 15, 16, 17, 18, 19, 20,
>>>>> + 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
>>>>> + 21, 22, 23, 24, 25, 26, 27
>>>>> + };
>>>>> +
>>>>> + check_vect ();
>>>>> +
>>>>> + int ret = condition_reduction (a, 46);
>>>>> +
>>>>> + /* loop should have found a value of 0, not default N + 96. */
>>>>> + if (ret != 0)
>>>>> + abort ();
>>>>> +
>>>>> + return 0;
>>>>> +}
>>>>> +
>>>>> +/* { dg-final { scan-tree-dump-times "LOOP VECTORIZED" 2 "vect" {
>xfail { ! vect_max_reduc } } } */
>>>>> +/* { dg-final { scan-tree-dump-times "condition expression based
>on integer induction." 4 "vect" } } */
>>>>>
>>>>
>>>> --
>>>> Richard Biener <rguenther@suse.de>
>>>> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham
>Norton, HRB 21284 (AG Nuernberg)
>>>
>>>
>>
>> --
>> Richard Biener <rguenther@suse.de>
>> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham
>Norton, HRB 21284 (AG Nuernberg)