This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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)


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]