[PATCH] Implement cond and induction cond reduction w/o REDUC_MAX_EXPR

[Richard Biener]

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?

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.

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)