On Wed, Sep 16, 2026 at 2:24 PM Konstantinos Eleftheriou <[email protected]> wrote: > > 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.
It feels anything else than elegant -- the pair should be tracked more uniformly, in particular vect_reduc_info is supposed to track all the reduction meta now, not the SLP instance or stmt_infos. The stmt_infos are where the scalar info resides but after SLP build it should be all in vect_reduc_info. I didn't check all cases, but do you handle the case when both the index and the value are live at the end of the loop? That said, vect_owning_reduc_instance should not exist, vect_create_epilog_for_reduction should not need to re-analyze (store the information). There is a bit too much analysis done at vect_is_simple_reduction time IMO. If we'd do the vect_reduc_info assignment early and also for stmt_vec_info we could queue the "stmts using a reduction" and identify and record pairs afterwards. Thanks for tackling this difficult PR. Richard. > 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 >
