[vect] Support min/max + index pattern

[Richard Biener]

On Wed, 5 May 2021, Joel Hutton wrote:

> Hi all,
> 
> looking for some feedback on this, one thing I would like to draw 
> attention to is the fact that this pattern requires 2 separate dependent 
> reductions in the epilogue. The accumulator vector for the 
> maximum/minimum elements can be reduced to a scalar result trivially 
> with a min/max, but getting the index from accumulator vector of indices 
> is more complex and requires using the position of the maximum/minimum 
> scalar result value within the accumulator vector to create a mask.
> 
> The given solution works but it's slightly messy. 
> vect_create_epilogue_for_reduction creates the epilogue for one 
> vectorized scalar stmt at a time. This modification makes one invocation 
> create the epilogue for both related stmts and marks the other as 
> 'done'. Alternate suggestions are welcome.

So I'm not looking at the very details in the patch but I think
a concept of "dependent" reductions might be useful (there might
be related patterns that could be vectorized).  So during
reduction discovery detect unhandled multi-uses and queue those
for later re-evaluation (in case we analyze the value reduction
first).  Discover the index reduction as regular reduction.
Upon re-analyzing the value reduction allow multi-uses that are
reductions themselves and note the dependence in some new stmt_vinfo
field.

Then during reduction analysis we can verify if we handle
a particular dependence and during code-gen we can ensure
to only code-gen one epilogue and have access to the other part.

That said, I'd make the thing a bit more generic in appearance
but otherwise yes, we do need to handle this together somehow.

+  /* For handling multi phi reductions.  */
+  tree scalar_result;
+  stmt_vec_info reduc_multi_use_related_stmt;
+  gimple* reduc_multi_use_result;
+  tree induc_val;
+  tree initial_def;
+  bool is_minmax_index;
+  bool is_minmax;
+  bool epilog_finished;

which should ideally reduce to a single field then.

Oh, and make sure an SLP variant is supported.

  for (int i = 0; i < n; i++) {
    if (data[2*i] < best1) {
      best1 = data[2*i];
      best_i1 = 2*i;
    }
    if (data[2*i+1] < best2) {
      best2 = data[2*i+1];
      best_i2 = 2*i;
    }
  }

Richard.

> Joel
> 
> [vect] Support min/max + index pattern
> 
> Add the capability to vect-loop to support the following pattern.
> 
> for (int i = 0; i < n; i ++)
> {
>     if (data[i] < best)
>     {
>         best = data[i];
>         best_i = i;
>     }
> }
> 
> gcc/ChangeLog:
> 
> 	* tree-vect-loop.c (vect_reassociating_reduction_simple_p): New                                                                                          
> 	function.                                                                                                                                                        
> 	(vect_recog_minmax_index_pattern): New function.                                                                                                             
> 	(vect_is_simple_reduction): Add multi_use_reduction case.                                                                                                    
> 	(vect_create_epilog_for_reduction): Add minmax+index epilogue handling.
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)