Vectorize the argmax/argmin idiom: a min/max reduction whose update also
drives the compare of a second reduction tracking the index of the winning
element.
vect_detect_minmax_index_pattern recognizes it from the index side. The
index reduction is a loop header PHI, so the header PHI list is the
candidate set, and the chain index PHI -> COND_EXPR -> compare is followed
through single SSA definitions. It starts as a COND_REDUCTION and is
reclassified to MINMAX_INDEX_REDUCTION.
The epilogue reduces the min/max accumulator, broadcasts it, and masks
every index lane that does not hold it to TYPE_MAX_VALUE, so a REDUC_MIN
over the index vector yields the winning index.
Bootstrapped/regtested on AArch64 and x86-64.
PR tree-optimization/88259
gcc/ChangeLog:
* tree-vect-loop.cc (vect_find_minmax_instance): New function.
(check_reduction_path): Take the coupled compare to skip.
(vect_minmax_lanes_ok_p): New function.
(vect_minmax_update_cmp_p): New function.
(vect_index_arm_is_iv_p): New function.
(vect_minmax_folded_operand): New function.
(vect_detect_minmax_index_pattern): New function.
(vect_is_simple_reduction): Classify and stash the coupling, and
refuse it when the reduction has a use the pattern does not
account for.
(vect_model_reduction_cost): Account for the coupled epilogue.
(vect_create_epilog_for_reduction): Emit the coupled epilogue.
(vect_slp_node_on_reduc_chain_p): New function.
(vect_owning_reduc_instance): New function.
(vectorizable_reduction): Verify SLP_TREE_LANES, and fix up a
shared root's SLP_TREE_TYPE for a coupled reduction.
(vect_transform_cycle_phi): Handle the coupled PHIs.
(vectorizable_live_operation): Coupled-reduction live-out lookup.
* tree-vect-patterns.cc (vect_recog_bool_pattern): Skip the coupled
minmax+index update COND_EXPR.
(vect_recog_mask_conversion_pattern): Likewise.
* tree-vectorizer.h (enum vect_reduction_type): Add
MINMAX_INDEX_REDUCTION.
(VECT_REDUC_INFO_COUPLED_MINMAX_PHI): New macro.
gcc/testsuite/ChangeLog:
* gcc.dg/vect/vect-minmax-index-1.c: New test.
* gcc.dg/vect/vect-minmax-index-2.c: New test.
* gcc.dg/vect/vect-minmax-index-3.c: New test.
* gcc.dg/vect/vect-minmax-index-4.c: New test.
* gcc.dg/vect/vect-minmax-index-5.c: New test.
* gcc.dg/vect/vect-minmax-index-6.c: New test.
* gcc.target/aarch64/vect-minmax-index-epilogue.c: New test.
* gcc.target/aarch64/vect-minmax-index-sve.c: New test.
Co-authored-by: Philipp Tomsich <[email protected]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
.../gcc.dg/vect/vect-minmax-index-1.c | 134 ++++
.../gcc.dg/vect/vect-minmax-index-2.c | 57 ++
.../gcc.dg/vect/vect-minmax-index-3.c | 46 ++
.../gcc.dg/vect/vect-minmax-index-4.c | 219 ++++++
.../gcc.dg/vect/vect-minmax-index-5.c | 49 ++
.../gcc.dg/vect/vect-minmax-index-6.c | 101 +++
.../aarch64/vect-minmax-index-epilogue.c | 25 +
.../aarch64/vect-minmax-index-sve.c | 24 +
gcc/tree-vect-loop.cc | 679 +++++++++++++++++-
gcc/tree-vect-patterns.cc | 12 +
gcc/tree-vectorizer.h | 20 +
11 files changed, 1357 insertions(+), 9 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-minmax-index-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-minmax-index-2.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-minmax-index-3.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-minmax-index-4.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-minmax-index-5.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-minmax-index-6.c
create mode 100644
gcc/testsuite/gcc.target/aarch64/vect-minmax-index-epilogue.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/vect-minmax-index-sve.c
diff --git a/gcc/testsuite/gcc.dg/vect/vect-minmax-index-1.c
b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-1.c
new file mode 100644
index 000000000000..663340a00250
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-1.c
@@ -0,0 +1,134 @@
+/* { dg-do run } */
+
+/* The min/max+index reduction over an integer index: both directions, ties,
+ the value live out alongside the index, and two couplings in one loop. */
+
+#include "tree-vect.h"
+
+#define N 128
+
+int __attribute__((noipa))
+find_max_index (int *arr, int n)
+{
+ int max_val = arr[0], max_idx = 0;
+ for (int i = 1; i < n; i++)
+ if (arr[i] > max_val)
+ {
+ max_val = arr[i];
+ max_idx = i;
+ }
+ return max_idx;
+}
+
+int __attribute__((noipa))
+find_min_index (int *arr, int n)
+{
+ int min_val = arr[0], min_idx = 0;
+ for (int i = 1; i < n; i++)
+ if (arr[i] < min_val)
+ {
+ min_val = arr[i];
+ min_idx = i;
+ }
+ return min_idx;
+}
+
+/* The value is live out too, so it gets its own reduction beside the index.
*/
+void __attribute__((noipa))
+find_max_and_index (int *arr, int n, int *out_val, int *out_idx)
+{
+ int max_val = arr[0], max_idx = 0;
+ for (int i = 1; i < n; i++)
+ if (arr[i] > max_val)
+ {
+ max_val = arr[i];
+ max_idx = i;
+ }
+ *out_val = max_val;
+ *out_idx = max_idx;
+}
+
+/* Two couplings in one loop. Each cross-instance lookup the epilogue makes
+ is a search over every instance, so it only has to pick the right one when
+ there is more than one candidate. */
+void __attribute__((noipa))
+find_both_indices (int *arr, int n, int *out_max, int *out_min)
+{
+ int max_val = arr[0], min_val = arr[0], max_idx = 0, min_idx = 0;
+ for (int i = 1; i < n; i++)
+ {
+ if (arr[i] > max_val)
+ {
+ max_val = arr[i];
+ max_idx = i;
+ }
+ if (arr[i] < min_val)
+ {
+ min_val = arr[i];
+ min_idx = i;
+ }
+ }
+ *out_max = max_idx;
+ *out_min = min_idx;
+}
+
+int arr[N];
+
+int main ()
+{
+ check_vect ();
+
+ for (int i = 0; i < N; i++)
+ arr[i] = (i * 37 + 13) % 100;
+ arr[42] = 200;
+ if (find_max_index (arr, N) != 42)
+ __builtin_abort ();
+
+ int val, idx;
+ find_max_and_index (arr, N, &val, &idx);
+ if (val != 200 || idx != 42)
+ __builtin_abort ();
+
+ for (int i = 0; i < N; i++)
+ arr[i] = (i * 37 + 13) % 100 + 10;
+ arr[73] = -5;
+ if (find_min_index (arr, N) != 73)
+ __builtin_abort ();
+
+ /* Strict > leaves the index alone on a tie, so the first one wins. */
+ for (int i = 0; i < N; i++)
+ arr[i] = i % 10;
+ arr[27] = 200;
+ arr[53] = 200;
+ arr[99] = 200;
+ if (find_max_index (arr, N) != 27)
+ __builtin_abort ();
+
+ /* Both couplings at once. The spikes are odd on purpose: a coupled
+ epilogue agrees with the scalar loop at every position that is a
+ multiple of the vectorization factor. */
+ for (int i = 0; i < N; i++)
+ arr[i] = (i * 37 + 13) % 100;
+ arr[45] = 200;
+ arr[101] = -50;
+ int hi, lo;
+ find_both_indices (arr, N, &hi, &lo);
+ if (hi != 45 || lo != 101)
+ __builtin_abort ();
+
+ /* Neither test ever fires, so both indices keep their initial value. */
+ for (int i = 0; i < N; i++)
+ arr[i] = 7;
+ find_both_indices (arr, N, &hi, &lo);
+ if (hi != 0 || lo != 0)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* The detection note fires once per vector mode tried, and twice over for
+ the kernel with two couplings, so only the loop count can be counted. The
+ count also carries the target-reduction gate, since vectorizing needs the
+ reductions the epilogue is built from and detecting does not. */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 4 "vect" { target {
vect_int && vect_max_reduc } } } } */
+/* { dg-final { scan-tree-dump "detected minmax\\+index compound reduction"
"vect" { target vect_int } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-minmax-index-2.c
b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-2.c
new file mode 100644
index 000000000000..182bedebe734
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-2.c
@@ -0,0 +1,57 @@
+/* { dg-do run } */
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_int } */
+
+/* If-conversion refuses this loop before the recognizer sees it, so the
+ scan-not alone would be vacuous; both refusals are scanned. It runs
+ because a wrong coupling here would give a wrong answer, not a missed
+ optimization. */
+
+#include "tree-vect.h"
+
+#define N 128
+
+int __attribute__((noipa))
+find_max_index_early_break (int *arr, int n, int sentinel)
+{
+ int max_val = arr[0], max_idx = 0;
+ for (int i = 1; i < n; i++)
+ {
+ if (arr[i] == sentinel)
+ break;
+ if (arr[i] > max_val)
+ {
+ max_val = arr[i];
+ max_idx = i;
+ }
+ }
+ return max_idx;
+}
+
+int arr[N];
+
+int
+main (void)
+{
+ check_vect ();
+
+ for (int i = 0; i < N; i++)
+ arr[i] = i % 50;
+
+ /* The maximum before the break is at 49; the larger value past it must
+ not be seen. */
+ arr[60] = -1;
+ arr[70] = 900;
+ if (find_max_index_early_break (arr, N, -1) != 49)
+ __builtin_abort ();
+
+ /* Without a matching sentinel the whole range is scanned. */
+ if (find_max_index_early_break (arr, N, -999) != 70)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "unsupported control flow in loop" "vect" } } */
+/* { dg-final { scan-tree-dump-not "detected minmax\\+index compound
reduction" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-minmax-index-3.c
b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-3.c
new file mode 100644
index 000000000000..da54cae54470
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-3.c
@@ -0,0 +1,46 @@
+/* { dg-do run } */
+/* { dg-require-effective-target vect_float } */
+/* { dg-additional-options "-O3 -ffast-math" } */
+
+/* Test minmax+index with float values and int index. With -ffast-math the
+ float comparison becomes a MAX_EXPR, which is what the compound reduction
+ is detected from. The target may or may not support IFN_REDUC_MAX on
+ float vectors, so only detection is required everywhere. */
+
+#include "tree-vect.h"
+
+#define N 128
+
+int __attribute__((noipa))
+find_fmax_index (float *arr, int n)
+{
+ float max_val = arr[0];
+ int max_idx = 0;
+ for (int i = 1; i < n; i++)
+ if (arr[i] > max_val)
+ {
+ max_val = arr[i];
+ max_idx = i;
+ }
+ return max_idx;
+}
+
+int main ()
+{
+ check_vect ();
+ float arr[N];
+ for (int i = 0; i < N; i++)
+ arr[i] = (float)((i * 37 + 13) % 100);
+ arr[42] = 200.0f; /* known maximum */
+
+ int idx = find_fmax_index (arr, N);
+ if (idx != 42)
+ __builtin_abort ();
+ return 0;
+}
+
+/* The compound pattern should be detected with -ffast-math. */
+/* { dg-final { scan-tree-dump "detected minmax\\+index compound reduction"
"vect" } } */
+/* The epilogue this exercises needs a target reduction on both vectors, so
+ the vectorization half is gated where the detection half is not. */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" { target { vect_float
&& vect_max_reduc } } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-minmax-index-4.c
b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-4.c
new file mode 100644
index 000000000000..1fb1f643223a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-4.c
@@ -0,0 +1,219 @@
+/* { dg-do run } */
+/* { dg-additional-options "-O3" } */
+
+/* Shapes the coupled reduction has to refuse, one per kernel below.
+
+ Spike positions are odd on purpose: a coupled epilogue agrees with the
+ scalar loop at every position that is a multiple of the vectorization
+ factor, so an even one passes even on a broken compiler. */
+
+#include "tree-vect.h"
+
+#define N 256
+
+/* Non-strict argmax: on ties, scalar semantics keep the LAST index. */
+int __attribute__((noipa))
+argmax_ge (int *arr, int n)
+{
+ int max_val = arr[0], max_idx = 0;
+ for (int i = 1; i < n; i++)
+ if (arr[i] >= max_val)
+ {
+ max_val = arr[i];
+ max_idx = i;
+ }
+ return max_idx;
+}
+
+/* Non-strict argmin: on ties, scalar semantics keep the LAST index. */
+int __attribute__((noipa))
+argmin_le (int *arr, int n)
+{
+ int min_val = arr[0], min_idx = 0;
+ for (int i = 1; i < n; i++)
+ if (arr[i] <= min_val)
+ {
+ min_val = arr[i];
+ min_idx = i;
+ }
+ return min_idx;
+}
+
+/* The update test reads B, so the index it selects is not one the max-of-A
+ reduction decides. */
+int __attribute__((noipa))
+cross_argmax (int *a, int *b, int n)
+{
+ int max = a[0], idx = 0;
+ for (int i = 1; i < n; i++)
+ {
+ if (max < b[i])
+ idx = i;
+ max = max > a[i] ? max : a[i];
+ }
+ return idx;
+}
+
+/* Inverted arms: the index is kept when the max updates and takes the
+ position when it does not. */
+int __attribute__((noipa))
+inv_argmax (int *a, int n)
+{
+ int max = a[0], idx = 0;
+ for (int i = 1; i < n; i++)
+ if (a[i] > max)
+ max = a[i];
+ else
+ idx = i;
+ return idx;
+}
+
+/* Three second consumers of the update test. Each returns the index as well,
+ so that the coupling is attempted at all rather than the index folding
+ away. */
+
+int __attribute__((noipa))
+argmax_count (int *a, int n)
+{
+ int max = a[0], idx = 0, count = 0;
+ for (int i = 1; i < n; i++)
+ if (a[i] > max)
+ {
+ max = a[i];
+ idx = i;
+ count++;
+ }
+ return idx * 1000 + count;
+}
+
+int __attribute__((noipa))
+argmax_two_idx (int *a, int n)
+{
+ int max = a[0], idx = 0, scaled = 0;
+ for (int i = 1; i < n; i++)
+ if (a[i] > max)
+ {
+ max = a[i];
+ idx = i;
+ scaled = 3 * i + 1;
+ }
+ return idx * 1000 + scaled;
+}
+
+int __attribute__((noipa))
+argmax_with_data (int *a, int n)
+{
+ int max = a[0], idx = 0, data = 0;
+ for (int i = 1; i < n; i++)
+ if (a[i] > max)
+ {
+ max = a[i];
+ idx = i;
+ data = a[i] + 7;
+ }
+ return idx * 1000 + data;
+}
+
+int main ()
+{
+ check_vect ();
+
+ int arr[N], brr[N];
+
+ /* MAX with three tied maxima: expect the LAST one. */
+ for (int i = 0; i < N; i++)
+ arr[i] = 0;
+ arr[10] = 99;
+ arr[51] = 99;
+ arr[250] = 99;
+ if (argmax_ge (arr, N) != 250)
+ __builtin_abort ();
+
+ /* MAX with two tied maxima at non-symmetric positions. */
+ for (int i = 0; i < N; i++)
+ arr[i] = -7;
+ arr[5] = 130;
+ arr[131] = 130;
+ if (argmax_ge (arr, N) != 131)
+ __builtin_abort ();
+
+ /* MIN with two tied minima: expect the LAST one. */
+ for (int i = 0; i < N; i++)
+ arr[i] = 500;
+ arr[60] = 110;
+ arr[110] = 110;
+ if (argmin_le (arr, N) != 110)
+ __builtin_abort ();
+
+ /* A rises, so the test holds only at B's spikes. */
+ for (int i = 0; i < N; i++)
+ {
+ arr[i] = i;
+ brr[i] = 0;
+ }
+ brr[101] = 1000;
+ if (cross_argmax (arr, brr, N) != 101)
+ __builtin_abort ();
+
+ /* Several spikes: the index is overwritten, so the LAST one wins. */
+ brr[37] = 1000;
+ brr[199] = 1000;
+ if (cross_argmax (arr, brr, N) != 199)
+ __builtin_abort ();
+
+ /* None of them: the index keeps its initial value. */
+ for (int i = 0; i < N; i++)
+ brr[i] = -1;
+ if (cross_argmax (arr, brr, N) != 0)
+ __builtin_abort ();
+
+ /* Descending: the max never updates, so the inverted arm runs every
+ iteration and the index ends at the last one. */
+ for (int i = 0; i < N; i++)
+ arr[i] = N - i;
+ if (inv_argmax (arr, N) != N - 1)
+ __builtin_abort ();
+
+ /* Ascending: the max updates every iteration, so the index is never
+ touched. */
+ for (int i = 0; i < N; i++)
+ arr[i] = i;
+ if (inv_argmax (arr, N) != 0)
+ __builtin_abort ();
+
+ /* Flat, then a strictly rising tail. */
+ for (int i = 0; i < N; i++)
+ arr[i] = i > 101 ? i : 0;
+ if (inv_argmax (arr, N) != 101)
+ __builtin_abort ();
+
+ /* One value the rest never reaches, then a rise below it: the max improves
+ once, a per-lane maximum on almost every iteration. A flat or a rising
+ array would make the two counts agree. */
+ for (int i = 0; i < N; i++)
+ arr[i] = i;
+ arr[1] = 500;
+ if (argmax_count (arr, N) != 1 * 1000 + 1)
+ __builtin_abort ();
+ if (argmax_two_idx (arr, N) != 1 * 1000 + 3 * 1 + 1)
+ __builtin_abort ();
+ if (argmax_with_data (arr, N) != 1 * 1000 + 500 + 7)
+ __builtin_abort ();
+
+ /* Descending: the max never improves, so every second consumer keeps its
+ initial value. */
+ for (int i = 0; i < N; i++)
+ arr[i] = N - i;
+ if (argmax_count (arr, N) != 0
+ || argmax_two_idx (arr, N) != 0
+ || argmax_with_data (arr, N) != 0)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* No kernel may be coupled. If one were, the cases above would abort. */
+/* { dg-final { scan-tree-dump-not "detected minmax\\+index compound
reduction" "vect" } } */
+/* The count fails if the vectorizer never analyzed these loops, which the
+ scan above would not. */
+/* { dg-final { scan-tree-dump-times "reduction used in loop" 7 "vect" {
target vect_int } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-minmax-index-5.c
b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-5.c
new file mode 100644
index 000000000000..ad791b025598
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-5.c
@@ -0,0 +1,49 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-Ofast" } */
+
+/* Two shapes the coupled min/max+index reduction has to refuse.
+
+ The epilogue masks the index vector lane-by-lane with the value compare,
+ so the two need the same lane count: a double value gives 2 lanes per
+ 128-bit vector against an int32 index's 4.
+
+ The min/max value may feed the coupled index compare and nothing else.
+ A second in-loop consumer leaves a vect_reduction_def used by an ordinary
+ statement. */
+
+int
+argmax_double (const double *a, int n)
+{
+ int idx = -1;
+ double best = -1e300;
+ for (int k = 0; k < n; k++)
+ if (best < a[k])
+ {
+ best = a[k];
+ idx = k;
+ }
+ return idx;
+}
+
+int
+argmax_int_stored (const int *a, int *out, int n)
+{
+ int best = a[0], idx = 0;
+ for (int k = 1; k < n; k++)
+ {
+ if (a[k] > best)
+ {
+ best = a[k];
+ idx = k;
+ }
+ out[k] = best;
+ }
+ return idx;
+}
+
+/* Both scans assume double and int32 vectors differ in lane count: that is
+ what refuses the first kernel, and so what makes the count 2 rather than 1.
+ The guard also keeps the first from matching a target where double has no
+ vector type at all. */
+/* { dg-final { scan-tree-dump "minmax\\+index: no value/index vector types
with equal lane counts" "vect" { target { vect_double && vect_int } } } } */
+/* { dg-final { scan-tree-dump-times "reduction used in loop" 2 "vect" {
target { vect_double && vect_int } } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-minmax-index-6.c
b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-6.c
new file mode 100644
index 000000000000..0410d4397bf5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-minmax-index-6.c
@@ -0,0 +1,101 @@
+/* { dg-do run } */
+/* { dg-additional-options "-O3 -fopenmp-simd" } */
+
+/* Constraints on what the coupled index may be.
+
+ The epilogue masks losing lanes with TYPE_MAX_VALUE, so the index must be
+ an index, not data that could equal it. An OpenMP conditional lastprivate
+ selects a loaded value, so coupling it drops a payload of INT_MAX.
+
+ It recovers the winner with a REDUC_MIN, so the index must also grow with
+ the iteration order. An unsigned arm with a large step wraps, and a later
+ iteration then holds a smaller index than an earlier one. */
+
+#include <limits.h>
+#include "tree-vect.h"
+
+#define N 128
+
+int __attribute__((noipa))
+last_nonzero (int *a, int n)
+{
+ int x = 5;
+ #pragma omp simd lastprivate (conditional: x)
+ for (int i = 0; i < n; i++)
+ if (a[i])
+ x = a[i];
+ return x;
+}
+
+/* 3000000000u * 2 wraps to less than 3000000000u, so this index falls as
+ often as it rises. */
+unsigned __attribute__((noipa))
+wrapping_index (int *a, int n)
+{
+ unsigned idx = 0;
+ int max = a[0];
+ for (int i = 1; i < n; i++)
+ if (a[i] > max)
+ {
+ max = a[i];
+ idx = (unsigned) i * 3000000000u;
+ }
+ return idx;
+}
+
+int a[N];
+
+int
+main (void)
+{
+ check_vect ();
+
+ /* A single update, with the sentinel value as the payload. */
+ for (int i = 0; i < N; i++)
+ a[i] = 0;
+ a[100] = INT_MAX;
+ if (last_nonzero (a, N) != INT_MAX)
+ abort ();
+
+ /* The sentinel value as the LAST of several updates. */
+ for (int i = 0; i < N; i++)
+ a[i] = 0;
+ a[40] = 7;
+ a[100] = INT_MAX;
+ if (last_nonzero (a, N) != INT_MAX)
+ abort ();
+
+ /* An ordinary payload, and the no-update case. */
+ for (int i = 0; i < N; i++)
+ a[i] = 0;
+ a[100] = 42;
+ if (last_nonzero (a, N) != 42)
+ abort ();
+
+ for (int i = 0; i < N; i++)
+ a[i] = 0;
+ if (last_nonzero (a, N) != 5)
+ abort ();
+
+ /* Tied maxima: the strict compare keeps the FIRST, whose wrapped index
+ value is the larger of the two, so a REDUC_MIN over them would answer
+ with the second. */
+ for (int i = 0; i < N; i++)
+ a[i] = 0;
+ a[1] = 9;
+ a[2] = 9;
+ if (wrapping_index (a, N) != 3000000000u)
+ __builtin_abort ();
+
+ for (int i = 0; i < N; i++)
+ a[i] = 0;
+ a[5] = 9;
+ a[6] = 9;
+ if (wrapping_index (a, N) != 2115098112u)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* The payload is data, not an index, so the coupling must not be applied. */
+/* { dg-final { scan-tree-dump-not "detected minmax\\+index compound
reduction" "vect" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/vect-minmax-index-epilogue.c
b/gcc/testsuite/gcc.target/aarch64/vect-minmax-index-epilogue.c
new file mode 100644
index 000000000000..3b0ce66a1f14
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/vect-minmax-index-epilogue.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -ffast-math" } */
+
+/* The recognizer refuses a value that honors NaNs, so some lane always
+ matches the reduced value and the epilogue needs no reduction over the
+ compare mask. Only the value reduction (fmaxnmv) and the index reduction
+ (sminv) are left. */
+
+int
+argmax_f (float *a, int n)
+{
+ float max = a[0];
+ int idx = 0;
+ for (int i = 1; i < n; i++)
+ if (a[i] > max)
+ {
+ max = a[i];
+ idx = i;
+ }
+ return idx;
+}
+
+/* { dg-final { scan-assembler "fmaxnmv" } } */
+/* { dg-final { scan-assembler "sminv" } } */
+/* { dg-final { scan-assembler-not "smaxv" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/vect-minmax-index-sve.c
b/gcc/testsuite/gcc.target/aarch64/vect-minmax-index-sve.c
new file mode 100644
index 000000000000..08d81e86ba94
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/vect-minmax-index-sve.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -march=armv8.2-a+sve -fdump-tree-vect-details" } */
+
+/* A second value updated under the min/max test is refused. SVE is where
+ that matters: Advanced SIMD rejects the shape earlier, so only here does
+ a detection reach vectorizable_condition. */
+
+int a[200], b[200];
+
+int
+argmax_stored (int n)
+{
+ int m = a[0], k = 0;
+ for (int i = 1; i < n; i++)
+ if (a[i] > m)
+ {
+ m = a[i];
+ k = i;
+ b[i] = 1;
+ }
+ return k;
+}
+
+/* { dg-final { scan-tree-dump-not "detected minmax\\+index compound
reduction" "vect" } } */
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 4a0492381422..faee78623fd4 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -2140,6 +2140,29 @@ vect_determine_partial_vectors_and_peeling
(loop_vec_info loop_vinfo,
return opt_result::success ();
}
+/* Find the SLP instance holding the min/max accumulator of a coupled
+ min/max+index reduction, whose reduction PHI is MINMAX_PHI_INFO. Store it
+ in *OUT_INST and its PHI node in *OUT_PHIS, either of which may be NULL
+ when only the answer is wanted, and return true on success. */
+
+static bool
+vect_find_minmax_instance (loop_vec_info loop_vinfo,
+ stmt_vec_info minmax_phi_info,
+ slp_instance *out_inst, slp_tree *out_phis)
+{
+ for (auto inst : LOOP_VINFO_SLP_INSTANCES (loop_vinfo))
+ if (inst->reduc_phis
+ && SLP_TREE_REPRESENTATIVE (inst->reduc_phis) == minmax_phi_info)
+ {
+ if (out_inst)
+ *out_inst = inst;
+ if (out_phis)
+ *out_phis = inst->reduc_phis;
+ return true;
+ }
+ return false;
+}
+
/* Function vect_analyze_loop_2.
Apply a set of analyses on LOOP specified by LOOP_VINFO, the different
@@ -2371,6 +2394,28 @@ start_over:
goto again;
}
+ /* A coupled min/max+index epilogue reads the accumulator out of the other
+ instance. Every reduction instance has its reduc_phis by this point;
+ this is the earliest the min/max one can be looked for. */
+ for (auto inst : LOOP_VINFO_SLP_INSTANCES (loop_vinfo))
+ {
+ if (!inst->reduc_phis)
+ continue;
+ vect_reduc_info ri = info_for_reduction (loop_vinfo, inst->reduc_phis);
+ if (!ri || VECT_REDUC_INFO_TYPE (ri) != MINMAX_INDEX_REDUCTION)
+ continue;
+ if (!vect_find_minmax_instance (loop_vinfo,
+ VECT_REDUC_INFO_COUPLED_MINMAX_PHI (ri),
+ NULL, NULL))
+ {
+ ok = opt_result::failure_at
+ (vect_location,
+ "not vectorized: no instance holds the min/max side of"
+ " the coupled reduction.\n");
+ goto again;
+ }
+ }
+
/* For now, we don't expect to mix both masking and length approaches for one
loop, disable it if both are recorded. */
if (LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P (loop_vinfo)
@@ -3458,7 +3503,8 @@ static bool
check_reduction_path (dump_user_location_t loc, loop_p loop, gphi *phi,
tree loop_arg, code_helper *code,
vec<std::pair<ssa_op_iter, use_operand_p> > &path,
- bool inner_loop_of_double_reduc)
+ bool inner_loop_of_double_reduc,
+ gimple *coupled_cmp = NULL)
{
auto_bitmap visited;
tree lookfor = PHI_RESULT (phi);
@@ -3634,6 +3680,11 @@ pop:
cnt++;
}
}
+ else if (op_use_stmt == coupled_cmp)
+ /* The min/max value of a coupled min/max+index reduction also
+ drives the index compare. That use belongs to the pattern,
+ so it does not count against the reduction. */
+ ;
else if (!is_gimple_debug (op_use_stmt)
&& ((*code != ERROR_MARK || inner_loop_of_double_reduc)
|| flow_bb_inside_loop_p (loop,
@@ -3662,6 +3713,218 @@ check_reduction_path (dump_user_location_t loc, loop_p
loop, gphi *phi,
}
+/* Return true when the coupled index (scalar type IDX_SCALAR) and the min/max
+ value (scalar type VAL_SCALAR) map to vector types with the same lane count,
+ so the MINMAX_INDEX epilogue can apply the value-compare mask to the index
+ vector lane-by-lane. A double value (2 lanes/128b) cannot couple with an
+ int32 index (4 lanes/128b). */
+
+static bool
+vect_minmax_lanes_ok_p (vec_info *vinfo, tree val_scalar, tree idx_scalar)
+{
+ /* The index is reduced as an integer. */
+ if (!INTEGRAL_TYPE_P (idx_scalar))
+ return false;
+ tree val_vt = get_vectype_for_scalar_type (vinfo, val_scalar);
+ tree idx_vt = get_vectype_for_scalar_type (vinfo, idx_scalar);
+ return (val_vt
+ && idx_vt
+ && known_eq (TYPE_VECTOR_SUBPARTS (val_vt),
+ TYPE_VECTOR_SUBPARTS (idx_vt)));
+}
+
+/* Return true when CMP_STMT is the update test of a min/max reduction whose
+ PHI result is PHI_NAME and whose update code is CODE: "new > max" for
+ MAX_EXPR, "new < min" for MIN_EXPR, in either operand order. The test must
+ compare PHI_NAME against VALUE, the operand the min/max folds. A test on
+ anything else decides the index from a value the reduction never selects.
+ Only strict tests are sound. The epilogue takes the FIRST lane holding the
+ min/max, while ">=" and "<=", which update on equality, would keep the LAST
+ tied index. */
+
+static bool
+vect_minmax_update_cmp_p (gimple *cmp_stmt, tree phi_name, tree value,
+ tree_code code)
+{
+ if (!is_gimple_assign (cmp_stmt))
+ return false;
+ tree_code cmp_code = gimple_assign_rhs_code (cmp_stmt);
+ if (cmp_code != GT_EXPR && cmp_code != LT_EXPR)
+ return false;
+
+ /* Normalize to the PHI's perspective: "a[i] > max" (PHI on the rhs) is
+ "max < a[i]". */
+ tree other;
+ if (gimple_assign_rhs2 (cmp_stmt) == phi_name)
+ {
+ cmp_code = swap_tree_comparison (cmp_code);
+ other = gimple_assign_rhs1 (cmp_stmt);
+ }
+ else if (gimple_assign_rhs1 (cmp_stmt) == phi_name)
+ other = gimple_assign_rhs2 (cmp_stmt);
+ else
+ return false;
+
+ if (other != value)
+ return false;
+
+ return ((code == MAX_EXPR && cmp_code == LT_EXPR)
+ || (code == MIN_EXPR && cmp_code == GT_EXPR));
+}
+
+/* Return true when ARM is an affine induction variable of LOOP with a
+ positive constant step that cannot wrap. Two things follow from how the
+ minmax+index epilogue works. It masks losing lanes with TYPE_MAX_VALUE, so
+ the coupled reduction must track an index rather than data that could equal
+ it. And it recovers the winner with a REDUC_MIN, which needs the index to
+ grow with the iteration order; a wrapping arm lets a later iteration hold a
+ smaller index than an earlier one. */
+
+static bool
+vect_index_arm_is_iv_p (class loop *loop, tree arm)
+{
+ if (TREE_CODE (arm) != SSA_NAME)
+ return false;
+ tree chrec = analyze_scalar_evolution (loop, arm);
+ if (chrec_contains_undetermined (chrec))
+ return false;
+ chrec = instantiate_scev (loop_preheader_edge (loop), loop, chrec);
+ if (TREE_CODE (chrec) != POLYNOMIAL_CHREC
+ || CHREC_VARIABLE (chrec) != (unsigned) loop->num
+ || TREE_CODE (CHREC_RIGHT (chrec)) != INTEGER_CST
+ || tree_int_cst_sgn (CHREC_RIGHT (chrec)) <= 0)
+ return false;
+ return !scev_probably_wraps_p (arm, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
+ NULL, loop, true);
+}
+
+/* Return the operand DEF_STMT folds with the reduction PHI result PHI_NAME,
+ provided it varies across iterations, which is what a min/max reduction
+ does. Return NULL_TREE otherwise, rejecting IV saturations such as
+ MAX_EXPR <invariant, iv>, which would build a malformed reduction. */
+
+static tree
+vect_minmax_folded_operand (gimple *def_stmt, tree phi_name, class loop *loop)
+{
+ tree op0 = gimple_assign_rhs1 (def_stmt);
+ tree op1 = gimple_assign_rhs2 (def_stmt);
+ tree other;
+ if (op0 == phi_name)
+ other = op1;
+ else if (op1 == phi_name)
+ other = op0;
+ else
+ return NULL_TREE;
+ return expr_invariant_in_loop_p (loop, other) ? NULL_TREE : other;
+}
+
+/* Detect a min/max+index compound reduction. PHI_INFO is the min/max
+ reduction PHI, DEF_STMT_INFO its latch def, which must be a
+ MIN_EXPR/MAX_EXPR. The index side is a second header PHI whose latch value
+ is a COND_EXPR conditioned on the min/max update test.
+
+ Returns the stmt_vec_info of that COND_EXPR if found, NULL otherwise. */
+
+static stmt_vec_info
+vect_detect_minmax_index_pattern (loop_vec_info loop_info,
+ stmt_vec_info phi_info,
+ stmt_vec_info def_stmt_info)
+{
+ /* The epilogue reduces the accumulators the vector loop ends with, which
+ answers the scalar loop only if it ran to its trip count. If-conversion
+ stops an early-break loop before this point today; the refusal does not
+ depend on that. */
+ if (LOOP_VINFO_EARLY_BREAKS (loop_info))
+ return NULL;
+
+ gimple *def_stmt = def_stmt_info->stmt;
+ if (!is_gimple_assign (def_stmt))
+ return NULL;
+
+ tree_code code = gimple_assign_rhs_code (def_stmt);
+ if (code != MAX_EXPR && code != MIN_EXPR)
+ return NULL;
+
+ gphi *phi = as_a <gphi *> (phi_info->stmt);
+ tree phi_name = PHI_RESULT (phi);
+ class loop *loop = (gimple_bb (phi))->loop_father;
+
+ /* Everything that consumes the coupling reads it off LOOP_VINFO_LOOP, so
+ the pattern has to live there. The inner loop of a double reduction
+ reaches this with the outer loop_vec_info and its own header. */
+ if (loop != LOOP_VINFO_LOOP (loop_info))
+ return NULL;
+
+ /* The epilogue reads the index off the lanes that compare equal to the
+ reduced min/max. A value that does not compare equal to itself leaves
+ every lane masked, and the REDUC_MIN then returns the sentinel. */
+ if (HONOR_NANS (TREE_TYPE (phi_name)))
+ return NULL;
+
+ tree minmax_value = vect_minmax_folded_operand (def_stmt, phi_name, loop);
+ if (!minmax_value)
+ return NULL;
+
+ edge latch_e = loop_latch_edge (loop);
+ for (gphi_iterator gsi = gsi_start_phis (loop->header);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *idx_phi = gsi.phi ();
+ if (idx_phi == phi || virtual_operand_p (PHI_RESULT (idx_phi)))
+ continue;
+
+ /* The index must be updated on the latch edge by an in-loop COND_EXPR
+ whose condition is the min/max update test. The test must drive
+ nothing else: it holds per lane in the vector loop, and only the
+ coupled index has an epilogue that accounts for that. */
+ tree latch_def = PHI_ARG_DEF_FROM_EDGE (idx_phi, latch_e);
+ if (TREE_CODE (latch_def) != SSA_NAME)
+ continue;
+ gimple *cond_stmt = SSA_NAME_DEF_STMT (latch_def);
+ if (!is_gimple_assign (cond_stmt)
+ || gimple_assign_rhs_code (cond_stmt) != COND_EXPR
+ || !flow_bb_inside_loop_p (loop, gimple_bb (cond_stmt)))
+ continue;
+ tree cond = gimple_assign_rhs1 (cond_stmt);
+ if (TREE_CODE (cond) != SSA_NAME
+ || !has_single_use (cond)
+ || !vect_minmax_update_cmp_p (SSA_NAME_DEF_STMT (cond), phi_name,
+ minmax_value, code))
+ continue;
+
+ /* The update must take a position in the iteration space when the test
+ holds and keep the index PHI otherwise. The reverse pair records where
+ the min/max did not update, and a strict test means it is never the
+ inverted spelling of an argmax. */
+ tree idx_res = PHI_RESULT (idx_phi);
+ tree win = gimple_assign_rhs2 (cond_stmt);
+ tree lose = gimple_assign_rhs3 (cond_stmt);
+ if (lose != idx_res || !vect_index_arm_is_iv_p (loop, win))
+ continue;
+
+ stmt_vec_info cond_info = loop_info->lookup_stmt (cond_stmt);
+ if (!cond_info)
+ continue;
+
+ /* Lane-count gate: value and index vectors must match in
+ lane count; the epilogue masks the index vector lane-by-lane. */
+ if (!vect_minmax_lanes_ok_p (loop_info, TREE_TYPE (phi_name),
+ TREE_TYPE (PHI_RESULT (idx_phi))))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "minmax+index: no value/index vector types with "
+ "equal lane counts\n");
+ return NULL;
+ }
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "detected minmax+index compound reduction\n");
+ return cond_info;
+ }
+
+ return NULL;
+}
/* Function vect_is_simple_reduction
@@ -3811,13 +4074,32 @@ vect_is_simple_reduction (loop_vec_info loop_info,
stmt_vec_info phi_info,
/* If this isn't a nested cycle or if the nested cycle reduction value
is used outside of the inner loop we cannot handle uses of the reduction
- value. */
+ value. Try to detect a compound min/max+index pattern before
+ rejecting. */
+ stmt_vec_info coupled_cond_stmt = NULL;
if (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1)
{
- if (dump_enabled_p ())
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "reduction used in loop.\n");
- return NULL;
+ coupled_cond_stmt = vect_detect_minmax_index_pattern (loop_info,
+ phi_info,
+ def_stmt_info);
+ if (!coupled_cond_stmt)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "reduction used in loop.\n");
+ return NULL;
+ }
+
+ /* The pattern justifies one use beyond the reduction chain, the
+ index compare on the PHI result. The latch value keeps only its
+ backedge use. */
+ if (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 2)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "reduction used in loop.\n");
+ return NULL;
+ }
}
/* If DEF_STMT is a phi node itself, we expect it to have a single argument
@@ -3863,8 +4145,18 @@ vect_is_simple_reduction (loop_vec_info loop_info,
stmt_vec_info phi_info,
/* Look for the expression computing latch_def from then loop PHI result. */
auto_vec<std::pair<ssa_op_iter, use_operand_p> > path;
code_helper code;
+ /* The coupled pattern lets the min/max value drive the index compare in
+ addition to its own reduction, so check_reduction_path takes that
+ compare and allows it as the one use outside the chain. */
+ gimple *coupled_cmp = NULL;
+ if (coupled_cond_stmt)
+ {
+ tree cond = gimple_assign_rhs1 (coupled_cond_stmt->stmt);
+ if (TREE_CODE (cond) == SSA_NAME)
+ coupled_cmp = SSA_NAME_DEF_STMT (cond);
+ }
if (check_reduction_path (vect_location, loop, phi, latch_def, &code,
- path, inner_loop_of_double_reduc))
+ path, inner_loop_of_double_reduc, coupled_cmp))
{
STMT_VINFO_REDUC_CODE (phi_info) = code;
if (code == COND_EXPR && !nested_in_vect_loop)
@@ -3889,6 +4181,15 @@ vect_is_simple_reduction (loop_vec_info loop_info,
stmt_vec_info phi_info,
= path[i].second->use - gimple_call_arg_ptr (call, 0);
}
}
+
+ /* Link the two halves of the pattern to each other, so either side
+ can reach the other in vectorizable_reduction. */
+ if (coupled_cond_stmt)
+ {
+ phi_info->coupled_minmax_peer = coupled_cond_stmt;
+ coupled_cond_stmt->coupled_minmax_peer = phi_info;
+ }
+
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
"reduction: detected reduction\n");
@@ -4804,6 +5105,23 @@ vect_model_reduction_cost (loop_vec_info loop_vinfo,
scalar_to_vec, node, 0,
vect_epilogue);
}
+ else if (reduction_type == MINMAX_INDEX_REDUCTION)
+ {
+ /* Two reductions to scalar, a broadcast, then the compare
+ and select over the vectors. If the min/max value is also
+ live out it gets its own reduction; one vec_to_scalar is then
+ counted twice, and CSE drops the duplicate. */
+ epilogue_cost += record_stmt_cost (cost_vec, 2,
+ vec_to_scalar, node, 0,
+ vect_epilogue);
+ epilogue_cost += record_stmt_cost (cost_vec, 1,
+ scalar_to_vec, node, 0,
+ vect_epilogue);
+ epilogue_cost += record_stmt_cost (cost_vec, 2,
+ vector_stmt, node, 0,
+ vect_epilogue);
+
+ }
else
{
epilogue_cost += record_stmt_cost (cost_vec, 1, vector_stmt,
@@ -5837,6 +6155,115 @@ vect_create_epilog_for_reduction (loop_vec_info
loop_vinfo,
/* 2.3 Create the reduction code, using one of the three schemes described
above. In SLP we simply need to extract all the elements from the
vector (without reducing them), so we use scalar shifts. */
+ else if (VECT_REDUC_INFO_TYPE (reduc_info) == MINMAX_INDEX_REDUCTION)
+ {
+ /* Coupled min/max+index epilogue: reduce the coupled min/max
+ accumulator, then recover the index from the first lane holding
+ that value. */
+
+ /* vectorizable_reduction rejects ncopies > 1; there is a single
+ vector group here. */
+ gcc_assert (reduc_inputs.length () == 1);
+
+ /* vect_find_reusable_accumulator only reuses accumulators of a
+ TREE_CODE_REDUCTION, so a coupled reduction never has one. */
+ gcc_assert (!VECT_REDUC_INFO_REUSED_ACCUMULATOR (reduc_info));
+
+ stmt_vec_info minmax_phi_info
+ = VECT_REDUC_INFO_COUPLED_MINMAX_PHI (reduc_info);
+
+ /* The min/max accumulator lives in its own SLP instance, not this
+ one. Analysis established it is findable. */
+ slp_tree minmax_reduc_phis = NULL;
+ slp_instance minmax_inst = NULL;
+ bool found = vect_find_minmax_instance (loop_vinfo, minmax_phi_info,
+ &minmax_inst,
+ &minmax_reduc_phis);
+ gcc_assert (found);
+
+ /* Take the accumulator from the instance root, the MIN/MAX_EXPR,
+ not from the PHI: the PHI holds the value before each update and
+ the root the value after it. Reading it needs that instance
+ scheduled, which holds because the index cycle depends on the
+ min/max PHI, so vect_schedule_scc completes the min/max SCC, root
+ included, before this one. */
+ slp_tree minmax_root = SLP_INSTANCE_TREE (minmax_inst);
+ gcc_assert (SLP_TREE_VEC_DEFS (minmax_root).length () == 1);
+ tree minmax_vec_def = vect_get_slp_vect_def (minmax_root, 0);
+
+ /* Preserve loop-closed form for the min/max accumulator too, as the
+ epilogue reads it outside the loop; the index side was closed above.
+ The recognizer refuses an early break, hence the single exit. */
+ gcc_checking_assert (LOOP_VINFO_MAIN_EXIT (loop_vinfo) == loop_exit);
+ tree minmax_exit_def = copy_ssa_name (minmax_vec_def);
+ gphi *minmax_exit_phi = create_phi_node (minmax_exit_def,
+ loop_exit->dest);
+ SET_PHI_ARG_DEF (minmax_exit_phi, loop_exit->dest_idx, minmax_vec_def);
+
+ tree minmax_vectype = TREE_TYPE (minmax_exit_def);
+ tree minmax_scalar_type = TREE_TYPE (minmax_vectype);
+
+ /* Determine whether this is MAX+index or MIN+index. */
+ vect_reduc_info minmax_ri
+ = info_for_reduction (loop_vinfo, minmax_reduc_phis);
+ code_helper minmax_code = VECT_REDUC_INFO_CODE (minmax_ri);
+ internal_fn val_reduc_fn;
+ if (minmax_code == MAX_EXPR)
+ val_reduc_fn = IFN_REDUC_MAX;
+ else
+ {
+ gcc_assert (minmax_code == MIN_EXPR);
+ val_reduc_fn = IFN_REDUC_MIN;
+ }
+
+ /* 1. Reduce min/max vector to scalar. */
+ tree scalar_minmax = make_ssa_name (minmax_scalar_type);
+ gcall *reduce_stmt = gimple_build_call_internal (val_reduc_fn, 1,
+ minmax_exit_def);
+ gimple_call_set_lhs (reduce_stmt, scalar_minmax);
+ gsi_insert_before (&exit_gsi, reduce_stmt, GSI_SAME_STMT);
+
+ /* 2. Broadcast to vector. */
+ tree bcast_vec = make_ssa_name (minmax_vectype);
+ gimple *bcast_stmt
+ = gimple_build_assign (bcast_vec,
+ build_vector_from_val (minmax_vectype,
+ scalar_minmax));
+ gsi_insert_before (&exit_gsi, bcast_stmt, GSI_SAME_STMT);
+
+ /* 3. Compare: which lanes hold the min/max value? The mask is built
+ from the value vectype and applied to the index vector below, a
+ select vectorizable_reduction checked for. */
+ tree cmp_type = truth_type_for (minmax_vectype);
+ tree cmp_result = make_ssa_name (cmp_type);
+ gimple *cmp_stmt
+ = gimple_build_assign (cmp_result, EQ_EXPR, minmax_exit_def,
+ bcast_vec);
+ gsi_insert_before (&exit_gsi, cmp_stmt, GSI_SAME_STMT);
+
+ /* 4. Mask index vector: TYPE_MAX_VALUE where no match. A lane fails to
+ match only when the reduced value does not compare equal to itself,
+ which the recognizer refuses, so some lane always wins and the mask
+ is never empty. */
+ tree idx_max = TYPE_MAX_VALUE (scalar_type);
+ tree idx_max_vec = build_vector_from_val (vectype, idx_max);
+ tree masked_idx = make_ssa_name (vectype);
+ gimple *mask_stmt
+ = gimple_build_assign (masked_idx, VEC_COND_EXPR, cmp_result,
+ reduc_inputs[0], idx_max_vec);
+ gsi_insert_before (&exit_gsi, mask_stmt, GSI_SAME_STMT);
+
+ /* 5. Reduce masked indices with REDUC_MIN. */
+ tree scalar_idx = make_ssa_name (scalar_type);
+ gcall *idx_reduce
+ = gimple_build_call_internal (IFN_REDUC_MIN, 1, masked_idx);
+ gimple_call_set_lhs (idx_reduce, scalar_idx);
+ gsi_insert_before (&exit_gsi, idx_reduce, GSI_SAME_STMT);
+
+ new_temp = scalar_idx;
+
+ scalar_results.safe_push (new_temp);
+ }
else if (reduc_fn != IFN_LAST && (!slp_reduc || group_size == 1))
{
tree tmp;
@@ -6960,6 +7387,77 @@ vectorizable_lane_reducing (loop_vec_info loop_vinfo,
stmt_vec_info stmt_info,
STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (vinfo, TREE_TYPE (X))
does *NOT* necessarily hold for reduction patterns. */
+/* Walk from the root of INST following REDUC_IDX edges and return true
+ if TARGET is reachable (i.e., it lies on the reduction chain of INST). */
+
+static bool
+vect_slp_node_on_reduc_chain_p (slp_instance inst, slp_tree target)
+{
+ slp_tree t = SLP_INSTANCE_TREE (inst);
+ while (t && t != target)
+ {
+ int ri = SLP_TREE_REDUC_IDX (t);
+ if (ri < 0 || ri >= (int) SLP_TREE_CHILDREN (t).length ())
+ return false;
+ t = SLP_TREE_CHILDREN (t)[ri];
+ }
+ return t == target;
+}
+
+/* Return the instance whose reduction chain contains SLP_NODE, which is
+ CURRENT when it already does. SLP nodes are shared: a reduction PHI can
+ sit in another instance's tree as an operand. In a coupled
+ minmax+index reduction the compare on the index side reaches the min/max
+ PHI, which the value side owns. With FIX_CYCLE_INFO, also give the nodes
+ along the chain SLP_NODE's cycle id, which a shared node may be missing.
+ Return NULL if no instance owns SLP_NODE. */
+
+static slp_instance
+vect_owning_reduc_instance (loop_vec_info loop_vinfo, slp_tree slp_node,
+ slp_instance current,
+ bool fix_cycle_info = false)
+{
+ if (vect_slp_node_on_reduc_chain_p (current, slp_node))
+ return current;
+
+ /* Search all reduction instances for the owning one. */
+ slp_instance inst;
+ unsigned j;
+ FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), j, inst)
+ {
+ if (inst == current
+ || SLP_INSTANCE_KIND (inst) != slp_inst_kind_reduc_group
+ || !vect_slp_node_on_reduc_chain_p (inst, slp_node))
+ continue;
+
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "reduction PHI belongs to a different "
+ "SLP instance\n");
+ /* Propagate cycle_info.id from the PHI back through the chain. */
+ if (fix_cycle_info)
+ {
+ int phi_cycle_id = slp_node->cycle_info.id;
+ if (phi_cycle_id != -1)
+ {
+ slp_tree fix = SLP_INSTANCE_TREE (inst);
+ while (fix && fix != slp_node)
+ {
+ if (fix->cycle_info.id == -1)
+ fix->cycle_info.id = phi_cycle_id;
+ int ri = SLP_TREE_REDUC_IDX (fix);
+ if (ri < 0
+ || ri >= (int) SLP_TREE_CHILDREN (fix).length ())
+ break;
+ fix = SLP_TREE_CHILDREN (fix)[ri];
+ }
+ }
+ }
+ return inst;
+ }
+ return NULL;
+}
+
bool
vectorizable_reduction (loop_vec_info loop_vinfo,
stmt_vec_info stmt_info, slp_tree slp_node,
@@ -7050,6 +7548,25 @@ vectorizable_reduction (loop_vec_info loop_vinfo,
double_reduc = true;
}
+ /* Only a coupled min/max+index reduction shares its PHI with another
+ instance's tree, so only it can have been handed an instance that does
+ not own the node. */
+ if (stmt_info->coupled_minmax_peer)
+ {
+ slp_instance owner
+ = vect_owning_reduc_instance (loop_vinfo, slp_node,
+ slp_node_instance, true);
+ if (!owner)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "reduction PHI not reachable from any "
+ "instance root.\n");
+ return false;
+ }
+ slp_node_instance = owner;
+ }
+
const bool reduc_chain = reduc_info->is_reduc_chain;
slp_node_instance->reduc_phis = slp_node;
/* ??? We're leaving slp_node to point to the PHIs, we only
@@ -7292,6 +7809,48 @@ vectorizable_reduction (loop_vec_info loop_vinfo,
}
enum vect_reduction_type reduction_type = VECT_REDUC_INFO_TYPE (reduc_info);
+
+ /* Find the coupled min/max PHI, if this is the index side of the
+ pattern. STMT_INFO is the SLP representative and need not be the
+ index-update COND_EXPR that holds the link, so fall back to the latch
+ definition of PHI_INFO, which is always the reduction PHI. */
+ stmt_vec_info minmax_phi_info = stmt_info->coupled_minmax_peer;
+ if (!minmax_phi_info && is_a <gphi *> (phi_info->stmt))
+ {
+ gphi *idx_phi = as_a <gphi *> (phi_info->stmt);
+ class loop *idx_loop = gimple_bb (idx_phi)->loop_father;
+ tree latch = PHI_ARG_DEF_FROM_EDGE (idx_phi,
+ loop_latch_edge (idx_loop));
+ if (TREE_CODE (latch) == SSA_NAME)
+ if (stmt_vec_info ldef = loop_vinfo->lookup_def (latch))
+ minmax_phi_info = ldef->coupled_minmax_peer;
+ }
+ /* The link is symmetric, so on the min/max side the peer is the index
+ COND_EXPR. Only a PHI names the coupled min/max reduction. */
+ if (minmax_phi_info && !is_a <gphi *> (minmax_phi_info->stmt))
+ minmax_phi_info = NULL;
+ if (reduction_type == COND_REDUCTION && minmax_phi_info != NULL)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "converting coupled index COND_REDUCTION to "
+ "MINMAX_INDEX_REDUCTION\n");
+ reduction_type = MINMAX_INDEX_REDUCTION;
+ VECT_REDUC_INFO_TYPE (reduc_info) = reduction_type;
+ VECT_REDUC_INFO_COUPLED_MINMAX_PHI (reduc_info) = minmax_phi_info;
+ }
+
+ /* The minmax+index epilogue only handles single-lane SLP groups. */
+ if (reduction_type == MINMAX_INDEX_REDUCTION
+ && SLP_TREE_LANES (slp_node) != 1)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "minmax+index reduction requires single-lane "
+ "SLP group.\n");
+ return false;
+ }
+
/* If we have a condition reduction, see if we can simplify it further. */
if (reduction_type == COND_REDUCTION)
{
@@ -7505,7 +8064,8 @@ vectorizable_reduction (loop_vec_info loop_vinfo,
if ((reduction_type == COND_REDUCTION
|| reduction_type == INTEGER_INDUC_COND_REDUCTION
|| reduction_type == CONST_COND_REDUCTION
- || reduction_type == EXTRACT_LAST_REDUCTION)
+ || reduction_type == EXTRACT_LAST_REDUCTION
+ || reduction_type == MINMAX_INDEX_REDUCTION)
&& ncopies > 1)
{
if (dump_enabled_p ())
@@ -7603,6 +8163,60 @@ vectorizable_reduction (loop_vec_info loop_vinfo,
OPTIMIZE_FOR_SPEED))
reduc_fn = IFN_REDUC_MAX;
}
+ else if (reduction_type == MINMAX_INDEX_REDUCTION)
+ {
+ /* The epilogue reduces the index vector with IFN_REDUC_MIN and the
+ value vector with IFN_REDUC_MAX or MIN. VECTYPE_OUT is the index
+ type, so the value's vectype has to be derived here. */
+ stmt_vec_info minmax_phi = VECT_REDUC_INFO_COUPLED_MINMAX_PHI
+ (reduc_info);
+ tree val_scalar_type
+ = TREE_TYPE (gimple_phi_result (minmax_phi->stmt));
+ tree val_vectype
+ = get_vectype_for_scalar_type (loop_vinfo, val_scalar_type);
+ if (!val_vectype)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "no vector type for the minmax+index value.\n");
+ return false;
+ }
+
+ /* The VEC_COND_EXPR in the epilogue requires the value and index
+ vectors to have the same number of elements so the mask applies
+ lane-by-lane. The recognizer refuses that already; this catches a
+ vectype that changed between detection and here. */
+ if (maybe_ne (TYPE_VECTOR_SUBPARTS (vectype_out),
+ TYPE_VECTOR_SUBPARTS (val_vectype)))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "index and value vector types have different "
+ "lane counts for minmax+index reduction.\n");
+ return false;
+ }
+
+ /* The lane-count check above does not cover the select: without mask
+ registers truth_type_for returns a same-sized boolean vector, so the
+ index and value vectypes must agree in size as well. */
+ if (direct_internal_fn_supported_p (IFN_REDUC_MIN, vectype_out,
+ OPTIMIZE_FOR_SPEED)
+ && direct_internal_fn_supported_p (IFN_REDUC_MAX, val_vectype,
+ OPTIMIZE_FOR_SPEED)
+ && direct_internal_fn_supported_p (IFN_REDUC_MIN, val_vectype,
+ OPTIMIZE_FOR_SPEED)
+ && expand_vec_cond_expr_p (vectype_out,
+ truth_type_for (val_vectype)))
+ reduc_fn = IFN_REDUC_MIN;
+ else
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "target does not support REDUC_MIN/MAX for "
+ "minmax+index reduction.\n");
+ return false;
+ }
+ }
VECT_REDUC_INFO_FN (reduc_info) = reduc_fn;
if (reduction_type != EXTRACT_LAST_REDUCTION
@@ -7863,7 +8477,24 @@ vectorizable_reduction (loop_vec_info loop_vinfo,
stmt_vec_info tem
= SLP_TREE_REPRESENTATIVE (SLP_INSTANCE_TREE (slp_node_instance));
if (!single_defuse_cycle && reduction_type != FOLD_LEFT_REDUCTION)
- STMT_VINFO_DEF_TYPE (tem) = vect_internal_def;
+ {
+ STMT_VINFO_DEF_TYPE (tem) = vect_internal_def;
+ /* SLP nodes are shared: the root may have been visited before this
+ PHI and left set to reduc_vec_info_type. It goes through
+ vectorizable_operation now, which recomputes what it needs. */
+ slp_tree root = SLP_INSTANCE_TREE (slp_node_instance);
+ stmt_vec_info reduc_phi
+ = STMT_VINFO_REDUC_DEF (vect_orig_stmt (stmt_info));
+ if (reduc_phi && reduc_phi->coupled_minmax_peer
+ && SLP_TREE_TYPE (root) == reduc_vec_info_type)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "fixing SLP_TREE_TYPE from reduc_vec_info_type "
+ "to op_vec_info_type for reduction op\n");
+ SLP_TREE_TYPE (root) = op_vec_info_type;
+ }
+ }
else
{
STMT_VINFO_DEF_TYPE (tem) = vect_reduction_def;
@@ -8291,6 +8922,15 @@ vect_transform_cycle_phi (loop_vec_info loop_vinfo,
stmt_vec_info stmt_info,
slp_tree slp_node, slp_instance slp_node_instance)
{
+ /* A coupled minmax+index PHI is pulled into the other instance's tree as
+ a dependency, so re-find its owner. Analysis already established one
+ exists, hence no check here. */
+ if (stmt_info->coupled_minmax_peer)
+ if (slp_instance owner
+ = vect_owning_reduc_instance (loop_vinfo, slp_node,
+ slp_node_instance))
+ slp_node_instance = owner;
+
tree vectype_out = SLP_TREE_VECTYPE (slp_node);
class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
int i;
@@ -10203,6 +10843,27 @@ vectorizable_live_operation (vec_info *vinfo,
stmt_vec_info stmt_info,
SLP_TREE_LIVE_LANES (slp_node).safe_push (slp_index);
return true;
}
+
+ /* A shared node can arrive here with the wrong instance. The epilogue
+ needs the instance this node roots, which is a different question
+ from the containment vect_owning_reduc_instance answers. */
+ stmt_vec_info live_reduc_phi
+ = STMT_VINFO_REDUC_DEF (vect_orig_stmt (stmt_info));
+ if ((stmt_info->coupled_minmax_peer
+ || (live_reduc_phi && live_reduc_phi->coupled_minmax_peer))
+ && SLP_INSTANCE_TREE (slp_node_instance) != slp_node)
+ {
+ slp_instance inst;
+ unsigned j;
+ FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), j, inst)
+ if (SLP_INSTANCE_TREE (inst) == slp_node
+ && SLP_INSTANCE_KIND (inst) == slp_inst_kind_reduc_group)
+ {
+ slp_node_instance = inst;
+ break;
+ }
+ }
+
/* For SLP reductions we vectorize the epilogue for all involved stmts
together. For SLP reduction chains we only get here once. */
if (SLP_INSTANCE_KIND (slp_node_instance) == slp_inst_kind_reduc_group
diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
index 5fcc37f053c7..bb38306598f7 100644
--- a/gcc/tree-vect-patterns.cc
+++ b/gcc/tree-vect-patterns.cc
@@ -6095,6 +6095,12 @@ vect_recog_bool_pattern (vec_info *vinfo,
if (!is_gimple_assign (last_stmt))
return NULL;
+ /* Do not rewrite the index-update COND_EXPR of a coupled min/max+index
+ reduction into a masked select: it is the reduction operation and must
+ stay a reduction stmt for the MINMAX_INDEX path to handle. */
+ if (stmt_vinfo->coupled_minmax_peer != NULL)
+ return NULL;
+
var = gimple_assign_rhs1 (last_stmt);
lhs = gimple_assign_lhs (last_stmt);
rhs_code = gimple_assign_rhs_code (last_stmt);
@@ -6364,6 +6370,12 @@ vect_recog_mask_conversion_pattern (vec_info *vinfo,
tree vectype1, vectype2;
stmt_vec_info pattern_stmt_info;
+ /* Leave the index-update COND_EXPR of a coupled min/max+index reduction
+ alone: it is the reduction operation, handled directly by the
+ MINMAX_INDEX path. */
+ if (stmt_vinfo->coupled_minmax_peer != NULL)
+ return NULL;
+
/* Check for MASK_LOAD and MASK_STORE as well as COND_OP calls requiring mask
conversion. */
if (is_gimple_call (last_stmt)
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 7ce13828c0a2..5abf8231cf16 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -96,6 +96,14 @@ enum vect_reduction_type {
INTEGER_INDUC_COND_REDUCTION,
CONST_COND_REDUCTION,
+ /* A conditional index reduction that is coupled to a MIN/MAX reduction.
+ The index tracks the position of the min/max value, as in the argmax
+ idiom where "a[i] > max" both updates the running maximum and
+ records the index that produced it. The index reduction is
+ vectorized alongside its paired min/max and reduced via masking in
+ the epilogue. */
+ MINMAX_INDEX_REDUCTION,
+
/* Retain a scalar phi and use a FOLD_EXTRACT_LAST within the loop
to implement:
@@ -903,6 +911,11 @@ public:
and we have decided to reuse this accumulator from the main loop. */
struct vect_reusable_accumulator *reused_accumulator;
+ /* For MINMAX_INDEX_REDUCTION: the stmt_vec_info of the coupled min/max
+ reduction's PHI. Used in the epilogue to find the accumulator of the
+ paired min/max vector. NULL if not part of a coupled pair. */
+ stmt_vec_info coupled_minmax_phi;
+
/* If the vector code is performing N scalar reductions in parallel,
this variable gives the initial scalar values of those N reductions. */
auto_vec<tree> reduc_initial_values;
@@ -927,6 +940,7 @@ typedef class vect_reduc_info_s *vect_reduc_info;
#define VECT_REDUC_INFO_EPILOGUE_ADJUSTMENT(I) ((I)->reduc_epilogue_adjustment)
#define VECT_REDUC_INFO_VECTYPE(I) ((I)->reduc_vectype)
#define VECT_REDUC_INFO_VECTYPE_FOR_MASK(I) ((I)->reduc_vectype_for_mask)
+#define VECT_REDUC_INFO_COUPLED_MINMAX_PHI(I) ((I)->coupled_minmax_phi)
#define VECT_REDUC_INFO_FORCE_SINGLE_CYCLE(I) ((I)->force_single_cycle)
#define VECT_REDUC_INFO_RESULT_POS(I) ((I)->reduc_result_pos)
#define VECT_REDUC_INFO_NEUTRAL_OP(I) ((I)->neutral_op)
@@ -1672,6 +1686,12 @@ public:
/* True if this is only suitable for SLP vectorization. */
bool slp_vect_only_p;
+
+ /* For a compound min/max+index reduction, the other half of the pair: on
+ the min/max PHI this is the index COND_EXPR, and on that COND_EXPR it is
+ the min/max PHI. Set during vect_is_simple_reduction, consumed by
+ vectorizable_reduction. */
+ stmt_vec_info coupled_minmax_peer;
};
/* Information about a gather/scatter call. */
--
2.55.0
