On Mon, 22 Jun 2026, Dipesh Sharma wrote:
> ---
>
> Hi GCC Team,
>
> This RFC proposes to combines multiple independent
> horizontal reductions (.REDUC_PLUS / IFN_REDUC_PLUS) found in a single
> basic block into one shared intra-lane reduction sequence followed by a
> narrowing path.
>
> On wide vectors a single horizontal reduction expands into a
> chain of cross-lane extract+add steps (512 -> 256 -> 128 -> 64 -> 32).
> When N such reductions sit in the same epilogue, this expensive
> cross-lane work is repeated N times.
>
> Rather than reducing each vector to a scalar independently, interleaves
> the lanes of the grouped reduction vectors using unpack-lo / unpack-hi + add.
> This places the partial sums of all the reductions side by side, after which
> a single narrowing path brings the data down to one 128-bit lane.
> Each reduction's scalar result is read out separately. The cross-lane
> narrowing
> is thus shared across the whole group instead of being repeated per reduction.
>
> Example:
>
> int A[128], B0[128], B1[128], B2[128], B3[128];
> int C[4];
> void reduc (void) {
> int s0 = 0, s1 = 0, s2 = 0, s3 = 0;
> for (int k = 0; k < 128; ++k) {
> int a = A[k];
> s0 += a * B0[k]; s1 += a * B1[k];
> s2 += a * B2[k]; s3 += a * B3[k];
> }
> C[0] = s0; C[1] = s1; C[2] = s2; C[3] = s3;
> }
>
> At -O3 -mavx512f each accumulator is a vector(16) int and the epilogue
> emits four independent .REDUC_PLUS calls:
>
> _77 = .REDUC_PLUS (vect_s0);
> _66 = .REDUC_PLUS (vect_s1);
> _10 = .REDUC_PLUS (vect_s2);
> _35 = .REDUC_PLUS (vect_s3);
>
> The pass replaces them with one shared unpack/add tree, a single
> narrowing path to 128 bits, and four scalar extracts:
>
> /* interleave + add, shared by all four reductions */
> _124 = unpack_lo (s1, s0) + unpack_hi (s1, s0);
> _159 = unpack_lo (s3, s2) + unpack_hi (s3, s2);
> _194 = unpack_lo (_124, _159) + unpack_hi (_124, _159);
> /* single narrowing path 512 -> 256 -> 128, giving vector(4) int */
> ... _247 ...
> /* per-reduction scalar extraction */
> _77 = BIT_FIELD_REF <_247, 32, 0>;
> _35 = BIT_FIELD_REF <_247, 32, 32>;
> _66 = BIT_FIELD_REF <_247, 32, 64>;
> _10 = BIT_FIELD_REF <_247, 32, 96>;
>
> On x86 this lowers the epilogue from four independent
> vextracti*/vpsrldq/vpaddd chains (~28 insns) to a single shared
> vpunpckldq/vpunpckhdq/vpaddd sequence plus vpextrd extracts
> (~17 insns).
Rather than implementing this as a separate pass I'd like to
see this done on the vectorizer side, esp. since it seems that
targets that don't go the .REDUC_PLUS way would also benefit
and we can profit from better cost modeling.
The main benefit is that we can use wider operations in the
initial steps, covering what we otherwise do in narrower
modes with more instructions in total. So even if we'd
just have two V16SI accumulators it's worth doing the
initial unpack pair?
Thanks,
Richard.
> Bootstrapped and tested on x86.
>
> Please let me know if any modifications are needed.
>
> Thank you,
> Dipesh
>
> gcc/ChangeLog:
>
> * Makefile.in:
> * common.opt:
> * opts.cc:
> * passes.def:
> * timevar.def (TV_TREE_COMBINE_REDUC_PLUS_OPT):
> * tree-pass.h (make_pass_combine_reduc_plus_opt):
> * tree-combine-reduc-plus-opt.cc: New file.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/vect/vect-reduc-plus-1.c: New test.
>
>
> gcc/Makefile.in | 1 +
> gcc/common.opt | 4 +
> gcc/opts.cc | 1 +
> gcc/passes.def | 3 +
> gcc/testsuite/gcc.dg/vect/vect-reduc-plus-1.c | 211 ++++++
> gcc/timevar.def | 1 +
> gcc/tree-combine-reduc-plus-opt.cc | 662 ++++++++++++++++++
> gcc/tree-pass.h | 1 +
> 8 files changed, 884 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/vect/vect-reduc-plus-1.c
> create mode 100644 gcc/tree-combine-reduc-plus-opt.cc
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 536e2faaaf8..432750d86fc 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1843,6 +1843,7 @@ OBJS = \
> tree-vect-slp.o \
> tree-vect-slp-patterns.o \
> tree-vectorizer.o \
> + tree-combine-reduc-plus-opt.o \
> tree-vector-builder.o \
> tree-vrp.o \
> tree.o \
> diff --git a/gcc/common.opt b/gcc/common.opt
> index 218dddf5dfe..49d981fb2dc 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -3527,6 +3527,10 @@ ftree-slp-vectorize
> Common Var(flag_tree_slp_vectorize) Optimization EnabledBy(ftree-vectorize)
> Enable basic block vectorization (SLP) on trees.
>
> +ftree-combine-reduc-plus-opt
> +Common Var(flag_tree_combine_reduc_plus_opt) Optimization
> EnabledBy(ftree-vectorize)
> +Enable GIMPLE pass that optimizes REDUC_PLUS patterns.
> +
> fvect-cost-model=
> Common Joined RejectNegative Enum(vect_cost_model) Var(flag_vect_cost_model)
> Init(VECT_COST_MODEL_DEFAULT) Optimization
> -fvect-cost-model=[unlimited|dynamic|cheap|very-cheap] Specifies the
> cost model for vectorization.
> diff --git a/gcc/opts.cc b/gcc/opts.cc
> index 342517528e8..102b73443e5 100644
> --- a/gcc/opts.cc
> +++ b/gcc/opts.cc
> @@ -690,6 +690,7 @@ static const struct default_options
> default_options_table[] =
> REORDER_BLOCKS_ALGORITHM_STC },
> { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_ftree_loop_vectorize, NULL, 1 },
> { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_ftree_slp_vectorize, NULL, 1 },
> + { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_ftree_combine_reduc_plus_opt, NULL,
> 1 },
> { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_fopenmp_target_simd_clone_, NULL,
> OMP_TARGET_SIMD_CLONE_NOHOST },
> #ifdef INSN_SCHEDULING
> diff --git a/gcc/passes.def b/gcc/passes.def
> index 1fc867fae51..af6233dd188 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -331,6 +331,8 @@ along with GCC; see the file COPYING3. If not see
> NEXT_PASS (pass_dse);
> POP_INSERT_PASSES ()
> NEXT_PASS (pass_slp_vectorize);
> + /* Optimize .REDUC_PLUS patterns after vectorizer prologue/epilogue.
> */
> + NEXT_PASS (pass_combine_reduc_plus_opt);
> NEXT_PASS (pass_loop_prefetch);
> /* Run IVOPTs after the last pass that uses data-reference analysis
> as that doesn't handle TARGET_MEM_REFs. */
> @@ -343,6 +345,7 @@ along with GCC; see the file COPYING3. If not see
> NEXT_PASS (pass_tree_no_loop);
> PUSH_INSERT_PASSES_WITHIN (pass_tree_no_loop)
> NEXT_PASS (pass_slp_vectorize);
> + NEXT_PASS (pass_combine_reduc_plus_opt);
> POP_INSERT_PASSES ()
> NEXT_PASS (pass_simduid_cleanup);
> NEXT_PASS (pass_lower_vector_ssa);
> diff --git a/gcc/testsuite/gcc.dg/vect/vect-reduc-plus-1.c
> b/gcc/testsuite/gcc.dg/vect/vect-reduc-plus-1.c
> new file mode 100644
> index 00000000000..67536b462d5
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vect/vect-reduc-plus-1.c
> @@ -0,0 +1,211 @@
> +/* { dg-do compile } */
> +/* { dg-require-effective-target vect_int } */
> +/* { dg-additional-options "-O3 -mavx512f -fdump-tree-reduc_plus_opt1" {
> target
> + * { x86_64-*-* i?86-*-* } } } */
> +
> +/*
> + Test contiguous .REDUC_PLUS chains for the reduc_plus_opt pass.
> + Each kernel produces a specific number of back-to-back REDUC_PLUS
> + IFN calls that the optimization can merge via unpack-interleave + add.
> +
> + With 512-bit SIMD (AVX-512):
> + i32: vector(16) int -> 4 parallel reductions (4 contiguous
> .REDUC_PLUS)
> + i64: vector(8) long -> 4 parallel reductions (4 contiguous
> .REDUC_PLUS)
> + i16: vector(32) short -> 8 parallel reductions (8 contiguous
> .REDUC_PLUS)
> + i8: vector(64) char -> 16 parallel reductions (16 contiguous
> + .REDUC_PLUS)
> +
> + For i16/i8 kernels the accumulators are int (not short/char) to prevent
> + the vectorizer from inserting narrow casts between each .REDUC_PLUS,
> + which would break the contiguity required by verify_contiguous_reduction.
> +*/
> +
> +#define N 128
> +
> +/* ------- i32 x 16 vector, 4 contiguous REDUC_PLUS ------- */
> +
> +int A32[N], B32_0[N], B32_1[N], B32_2[N], B32_3[N];
> +int C32[7];
> +
> +__attribute__ ((noinline)) void
> +reduc_plus_i32_v16_r4 (void)
> +{
> + int s0 = 0, s1 = 0, s2 = 0, s3 = 0;
> + for (int k = 0; k < N; ++k)
> + {
> + int a = A32[k];
> + s0 += a * B32_0[k];
> + s1 += a * B32_1[k];
> + s2 += a * B32_2[k];
> + s3 += a * B32_3[k];
> + }
> + C32[0] = s0;
> + C32[1] = s1;
> + C32[2] = s2;
> + C32[3] = s3;
> +}
> +
> +/* ------- i32 x 16 vector, 7 contiguous REDUC_PLUS ------- */
> +/* ------- 4 are convertes to unpack trees and rest three are not------- */
> +
> +int B32_4[N], B32_5[N], B32_6[N];
> +__attribute__ ((noinline)) void
> +reduc_plus_i32_v16_r7 (void)
> +{
> + int s0 = 0, s1 = 0, s2 = 0, s3 = 0, s4 = 0, s5 = 0, s6 = 0;
> + for (int k = 0; k < N; ++k)
> + {
> + int a = A32[k];
> + s0 += a * B32_0[k];
> + s1 += a * B32_1[k];
> + s2 += a * B32_2[k];
> + s3 += a * B32_3[k];
> + s4 += a * B32_4[k];
> + s5 += a * B32_5[k];
> + s6 += a * B32_6[k];
> + }
> + C32[0] = s0;
> + C32[1] = s1;
> + C32[2] = s2;
> + C32[3] = s3;
> + C32[4] = s4;
> + C32[5] = s5;
> + C32[6] = s6;
> +}
> +
> +/* ------- i64 x 8 vector, 4 contiguous REDUC_PLUS ------- */
> +
> +long long A64[N], B64_0[N], B64_1[N], B64_2[N], B64_3[N];
> +long long C64[4];
> +
> +__attribute__ ((noinline)) void
> +reduc_plus_i64_v8_r4 (void)
> +{
> + long long s0 = 0, s1 = 0, s2 = 0, s3 = 0;
> + for (int k = 0; k < N; ++k)
> + {
> + long long a = A64[k];
> + s0 += a * B64_0[k];
> + s1 += a * B64_1[k];
> + s2 += a * B64_2[k];
> + s3 += a * B64_3[k];
> + }
> + C64[0] = s0;
> + C64[1] = s1;
> + C64[2] = s2;
> + C64[3] = s3;
> +}
> +
> +/* ------- i16 x 32 vector, 8 contiguous REDUC_PLUS ------- */
> +
> +short A16[N], B16_0[N], B16_1[N], B16_2[N], B16_3[N];
> +short B16_4[N], B16_5[N], B16_6[N], B16_7[N];
> +short C16[8];
> +
> +__attribute__ ((noinline)) void
> +reduc_plus_i16_v32_r8 (void)
> +{
> + int s0 = 0, s1 = 0, s2 = 0, s3 = 0;
> + int s4 = 0, s5 = 0, s6 = 0, s7 = 0;
> + for (int k = 0; k < N; ++k)
> + {
> + int a = A16[k];
> + s0 += a * B16_0[k];
> + s1 += a * B16_1[k];
> + s2 += a * B16_2[k];
> + s3 += a * B16_3[k];
> + s4 += a * B16_4[k];
> + s5 += a * B16_5[k];
> + s6 += a * B16_6[k];
> + s7 += a * B16_7[k];
> + }
> + C16[0] = s0;
> + C16[1] = s1;
> + C16[2] = s2;
> + C16[3] = s3;
> + C16[4] = s4;
> + C16[5] = s5;
> + C16[6] = s6;
> + C16[7] = s7;
> +}
> +
> +/* ------- i8 x 64 vector, 16 contiguous REDUC_PLUS ------- */
> +
> +signed char A8[N];
> +signed char B8_0[N], B8_1[N], B8_2[N], B8_3[N];
> +signed char B8_4[N], B8_5[N], B8_6[N], B8_7[N];
> +signed char B8_8[N], B8_9[N], B8_10[N], B8_11[N];
> +signed char B8_12[N], B8_13[N], B8_14[N], B8_15[N];
> +signed char C8[16];
> +
> +__attribute__ ((noinline)) void
> +reduc_plus_i8_v64_r16 (void)
> +{
> + int s0 = 0, s1 = 0, s2 = 0, s3 = 0;
> + int s4 = 0, s5 = 0, s6 = 0, s7 = 0;
> + int s8 = 0, s9 = 0, s10 = 0, s11 = 0;
> + int s12 = 0, s13 = 0, s14 = 0, s15 = 0;
> + for (int k = 0; k < N; ++k)
> + {
> + int a = A8[k];
> + s0 += a * B8_0[k];
> + s1 += a * B8_1[k];
> + s2 += a * B8_2[k];
> + s3 += a * B8_3[k];
> + s4 += a * B8_4[k];
> + s5 += a * B8_5[k];
> + s6 += a * B8_6[k];
> + s7 += a * B8_7[k];
> + s8 += a * B8_8[k];
> + s9 += a * B8_9[k];
> + s10 += a * B8_10[k];
> + s11 += a * B8_11[k];
> + s12 += a * B8_12[k];
> + s13 += a * B8_13[k];
> + s14 += a * B8_14[k];
> + s15 += a * B8_15[k];
> + }
> + C8[0] = s0;
> + C8[1] = s1;
> + C8[2] = s2;
> + C8[3] = s3;
> + C8[4] = s4;
> + C8[5] = s5;
> + C8[6] = s6;
> + C8[7] = s7;
> + C8[8] = s8;
> + C8[9] = s9;
> + C8[10] = s10;
> + C8[11] = s11;
> + C8[12] = s12;
> + C8[13] = s13;
> + C8[14] = s14;
> + C8[15] = s15;
> +}
> +
> +/* Scan the reduc_plus_opt1 dump for the expected chains.
> +
> + The vect.exp harness compiles at -O2 with -fno-vect-cost-model.
> + With AVX-512 (512-bit vectors) the vectorizer uses vector(16) int
> + for most kernels (i16/i8 widen to int accumulators). The pass
> + groups contiguous REDUC_PLUS by vector type and builds unpack trees
> + in groups of lane_elts (= 128 / elt_bits) elements.
> +
> + i32 r4: 4 REDUC_PLUS -> 1 group -> 1 "Reduced to single lane"
> + i32 r7: 7 REDUC_PLUS -> 1 group -> 1 "Reduced to single lane", 3
> + .REDUC_PLUS remain i64 r4: 4 REDUC_PLUS -> 2 groups -> 2 "Reduced to
> single
> + lane" i16 r8: 8 REDUC_PLUS -> 2 groups -> 2 "Reduced to single lane" i8
> + r16: 16 REDUC_PLUS -> 4 groups -> 4 "Reduced to single lane" Total at -O2:
> + 10 "Reduced to single lane", 39 "Adding REDUC_PLUS", 3 remaining
> .REDUC_PLUS
> + (from the r7 leftover).
> +
> + The transformation replaces REDUC_PLUS with VEC_PERM_EXPR + PLUS_EXPR. */
> +
> +/* { dg-final { scan-tree-dump-times "Reduced to single lane" 10
> + * "reduc_plus_opt1" { target { x86_64-*-* i?86-*-* } } } } */
> +/* { dg-final { scan-tree-dump-times ". = .REDUC_PLUS (." 3
> "reduc_plus_opt1" {
> + * target { x86_64-*-* i?86-*-* } } } } */
> +/* { dg-final { scan-tree-dump-times "Adding REDUC_PLUS stmt to chain" 39
> + * "reduc_plus_opt1" { target { x86_64-*-* i?86-*-* } } } } */
> +/* { dg-final { scan-tree-dump "VEC_PERM_EXPR" "reduc_plus_opt1" { target {
> + * x86_64-*-* i?86-*-* } } } } */
> diff --git a/gcc/timevar.def b/gcc/timevar.def
> index 588d987ec35..265f80e4f03 100644
> --- a/gcc/timevar.def
> +++ b/gcc/timevar.def
> @@ -207,6 +207,7 @@ DEFTIMEVAR (TV_SCALAR_CLEANUP , "scalar cleanup")
> DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops")
> DEFTIMEVAR (TV_TREE_VECTORIZATION , "tree vectorization")
> DEFTIMEVAR (TV_TREE_SLP_VECTORIZATION, "tree slp vectorization")
> +DEFTIMEVAR (TV_TREE_COMBINE_REDUC_PLUS_OPT, "tree combine reduc_plus
> optimization")
> DEFTIMEVAR (TV_GRAPHITE , "Graphite")
> DEFTIMEVAR (TV_GRAPHITE_TRANSFORMS , "Graphite loop transforms")
> DEFTIMEVAR (TV_GRAPHITE_DATA_DEPS , "Graphite data dep analysis")
> diff --git a/gcc/tree-combine-reduc-plus-opt.cc
> b/gcc/tree-combine-reduc-plus-opt.cc
> new file mode 100644
> index 00000000000..6114e8baf54
> --- /dev/null
> +++ b/gcc/tree-combine-reduc-plus-opt.cc
> @@ -0,0 +1,662 @@
> +/* GIMPLE pass: optimize REDUC_PLUS patterns after vectorization.
> + Copyright (C) 2026 Free Software Foundation, Inc.
> +
> + This file is part of GCC.
> +
> + GCC is free software; you can redistribute it and/or modify it under
> + the terms of the GNU General Public License as published by the Free
> + Software Foundation; either version 3, or (at your option) any later
> + version.
> +
> + GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> + WARRANTY; without even the implied warranty of MERCHANTABILITY or
> + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
> + for more details.
> +
> + You should have received a copy of the GNU General Public License
> + along with GCC; see the file COPYING3. If not see
> + <http://www.gnu.org/licenses/>. */
> +
> +/* This pass runs after the vectorizer has finished prologue and epilogue
> + loop vectorization (i.e. after pass_vectorize and pass_slp_vectorize).
> + It detects and optimizes REDUC_PLUS (IFN_REDUC_PLUS) patterns on
> + GIMPLE. Pattern detection and transformation can be implemented in
> + reduc_plus_opt::execute and the helper functions below. */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "backend.h"
> +#include "tree.h"
> +#include "gimple.h"
> +#include "tree-pass.h"
> +#include "ssa.h"
> +#include "fold-const.h"
> +#include "tree-cfg.h"
> +#include "tree-into-ssa.h"
> +#include "tree-ssa.h"
> +#include "cfgloop.h"
> +#include "gimple-iterator.h"
> +#include "internal-fn.h"
> +#include "cfg.h"
> +#include "hash-map.h"
> +#include "hash-traits.h"
> +#include "vec.h"
> +#include "vec-perm-indices.h"
> +#include "tree-vectorizer.h"
> +#include "optabs-query.h"
> +
> +namespace
> +{
> +
> +#define LANE_WIDTH_BITS 128
> +typedef int_hash<int, -1, -2> reduc_int_hash_t;
> +
> +/* Unpack node for GIMPLE: binary tree node representing one or more
> + REDUC_PLUS operations that can be optimized together via unpack
> + (interleave low/high) and add. */
> +struct unpack_node
> +{
> + bool leaf_node;
> + auto_vec<int> red_map; /* Reduction index mapping. */
> + auto_vec<gimple *> red_values;
> + unpack_node *left;
> + unpack_node *right;
> +
> + unpack_node () : leaf_node (true), left (nullptr), right (nullptr) {}
> +
> + ~unpack_node ()
> + {
> + delete left;
> + delete right;
> + }
> +
> + unpack_node (unpack_node *left, unpack_node *right)
> + {
> + gcc_assert (left != nullptr && right != nullptr && left != right);
> + this->leaf_node = false;
> + this->left = left;
> + this->right = right;
> + unsigned left_size = left->red_map.length ();
> + unsigned right_size = right->red_map.length ();
> + unsigned max_sz = std::max (left_size, right_size);
> + this->red_map.safe_grow_cleared (2 * max_sz);
> + for (auto val : left->red_values)
> + this->red_values.safe_push (val);
> + for (auto val : right->red_values)
> + this->red_values.safe_push (val);
> + for (unsigned i = 0; i < max_sz; i++)
> + {
> + this->red_map[2 * i] = left->red_map[i % left_size];
> + this->red_map[2 * i + 1]
> + = left->red_values.length () + right->red_map[i % right_size];
> + }
> + }
> +
> + /* Return a map from reduction index to vector of positions in red_map.
> + Keys are indices into red_values (invariant: every value stored in
> + red_map is a valid index into red_values, maintained by the merging
> + constructor which concatenates left/right red_values and offsets
> + right's red_map entries by left->red_values.length()). */
> + hash_map<reduc_int_hash_t, auto_vec<int> > *
> + get_reduction_index ()
> + {
> + gcc_assert (this->red_map.length () > 0);
> + int max_elt = this->red_map[0];
> + for (unsigned i = 1; i < this->red_map.length (); i++)
> + if (this->red_map[i] > max_elt)
> + max_elt = this->red_map[i];
> + gcc_assert (
> + max_elt + 1 >= 2 && max_elt + 1 <= 16
> + && "Maximum number of elements in a lane must be 2, 4, 8 or 16");
> + hash_map<reduc_int_hash_t, auto_vec<int> > *result
> + = new hash_map<reduc_int_hash_t, auto_vec<int> > ();
> + for (unsigned i = 0; i < this->red_map.length (); i++)
> + result->get_or_insert (this->red_map[i]).safe_push (i);
> + return result;
> + }
> +};
> +
> +/* Build vec_perm masks for unpack lo and unpack hi of two vectors Va, Vb.
> + Va has indices 0..nunits-1, Vb has nunits..2*nunits-1.
> + We use groups of 4 lanes:
> + - Unpack lo: out = Va[0],Vb[0],Va[1],Vb[1], Va[4],Vb[4],Va[5],Vb[5], ...
> + - Unpack hi: out = Va[2],Vb[2],Va[3],Vb[3], Va[6],Vb[6],Va[7],Vb[7], ...
> + Return true if the target supports both permutations; then MASK_LO and
> + MASK_HI are set to the VECTOR_CST mask trees for use in VEC_PERM_EXPR. */
> +static bool
> +build_unpack_lo_hi_masks (tree vectype, poly_uint64 nunits, tree *mask_lo,
> + tree *mask_hi)
> +{
> + unsigned HOST_WIDE_INT n;
> + unsigned int elt_bits = TYPE_PRECISION (TREE_TYPE (vectype));
> + unsigned int lane_elts = LANE_WIDTH_BITS / elt_bits;
> + if (!nunits.is_constant (&n) || (n % lane_elts) != 0)
> + return false;
> + unsigned int ngroups = n / lane_elts;
> + machine_mode mode = TYPE_MODE (vectype);
> +
> + /* Builder: nunits elements, lane_elts interleaved patterns,
> + ngroups groups per pattern. */
> + vec_perm_builder sel_lo (nunits, lane_elts, ngroups);
> + vec_perm_builder sel_hi (nunits, lane_elts, ngroups);
> + for (unsigned int e = 0; e < ngroups; e++)
> + {
> + for (unsigned int i = 0; i < lane_elts / 2; i++)
> + {
> + sel_lo.quick_push (e * lane_elts + i);
> + sel_lo.quick_push (n + e * lane_elts + i);
> + }
> + for (unsigned int i = lane_elts / 2; i < lane_elts; i++)
> + {
> + sel_hi.quick_push (e * lane_elts + i);
> + sel_hi.quick_push (n + e * lane_elts + i);
> + }
> + }
> + vec_perm_indices indices_lo (sel_lo, 2, nunits);
> + vec_perm_indices indices_hi (sel_hi, 2, nunits);
> + if (!can_vec_perm_const_p (mode, mode, indices_lo)
> + || !can_vec_perm_const_p (mode, mode, indices_hi))
> + return false;
> + *mask_lo = vect_gen_perm_mask_checked (vectype, indices_lo);
> + *mask_hi = vect_gen_perm_mask_checked (vectype, indices_hi);
> + return true;
> +}
> +
> +/* Return true if STMT is a REDUC_PLUS internal call. */
> +static bool
> +is_reduc_plus_call (gimple *stmt)
> +{
> + if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt))
> + return false;
> + return gimple_call_internal_fn (stmt) == IFN_REDUC_PLUS;
> +}
> +
> +/* Collect REDUC_PLUS stmts in BB and group them by vector type into CHAINS.
> + Each leaf unpack_node holds one REDUC_PLUS stmt. */
> +static void
> +detect_reduction_for_bb (basic_block bb,
> + hash_map<tree, auto_vec<unpack_node *> > *chains)
> +{
> + gimple_stmt_iterator gsi;
> + gimple *prev = nullptr;
> + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + gimple *stmt = gsi_stmt (gsi);
> + if (!is_reduc_plus_call (stmt))
> + continue;
> + if (prev != nullptr && prev->next != stmt)
> + continue;
> + prev = stmt;
> + gcc_assert (gimple_call_num_args (stmt) == 1);
> + tree arg = gimple_call_arg (stmt, 0);
> + /* Group by full VECTOR_TYPE (element type and lane count). */
> + tree vectype = TREE_TYPE (arg);
> + if (!VECTOR_TYPE_P (vectype))
> + continue;
> + unpack_node *node = new unpack_node ();
> + node->red_values.safe_push (stmt);
> + node->red_map.safe_push (0);
> + chains->get_or_insert (vectype).safe_push (node);
> + if (dump_file)
> + {
> + fprintf (dump_file, "Adding REDUC_PLUS stmt to chain with type %d\n",
> + TREE_CODE (vectype));
> + dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
> + }
> + }
> +}
> +
> +/* Iterating on the unpack binary tree recursively and building a
> + sequence of vec_perm and add statements for each node in the unpack
> + tree to SEQ for the unpacking of two vectors Va, Vb for a node.
> + VEC_PERM_EXPR (Va, Vb, mask_lo) -> low_half
> + VEC_PERM_EXPR (Va, Vb, mask_hi) -> high_half
> + PLUS_EXPR (low_half, high_half) -> sum = low_half + high_half
> + Return the sum vector. */
> +static tree
> +prepare_vec_perm_seq (unpack_node *node, tree vectype, gimple_seq *seq)
> +{
> + if (node->leaf_node)
> + {
> + gimple *stmt = node->red_values[0];
> + gcc_assert (node->red_values.length () == 1
> + && gimple_call_num_args (stmt) == 1);
> + return gimple_call_arg (stmt, 0);
> + }
> + gimple_seq left_seq = NULL;
> + gimple_seq right_seq = NULL;
> + tree left = prepare_vec_perm_seq (node->left, vectype, &left_seq);
> + tree right = prepare_vec_perm_seq (node->right, vectype, &right_seq);
> + if (left == NULL_TREE || right == NULL_TREE)
> + {
> + gimple_seq_discard (left_seq);
> + gimple_seq_discard (right_seq);
> + return NULL_TREE;
> + }
> + poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (vectype);
> + tree mask_lo = NULL_TREE, mask_hi = NULL_TREE;
> + /* Build the vec_perm masks for the unpacking of the low and high
> + halves of the vectors. */
> + if (!build_unpack_lo_hi_masks (vectype, nunits, &mask_lo, &mask_hi))
> + {
> + gimple_seq_discard (left_seq);
> + gimple_seq_discard (right_seq);
> + return NULL_TREE;
> + }
> + /* Add the sequences for the left and right children to the current
> + sequence. */
> + gimple_seq_add_seq (seq, left_seq);
> + gimple_seq_add_seq (seq, right_seq);
> + tree unpack_lo_result = make_ssa_name (vectype);
> + gimple *perm_lo = gimple_build_assign (unpack_lo_result, VEC_PERM_EXPR,
> left,
> + right, mask_lo);
> + gimple_seq_add_stmt (seq, perm_lo);
> + tree unpack_hi_result = make_ssa_name (vectype);
> + gimple *perm_hi = gimple_build_assign (unpack_hi_result, VEC_PERM_EXPR,
> left,
> + right, mask_hi);
> + gimple_seq_add_stmt (seq, perm_hi);
> + tree output = make_ssa_name (vectype);
> + gimple *add_stmt = gimple_build_assign (output, PLUS_EXPR,
> unpack_lo_result,
> + unpack_hi_result);
> + gimple_seq_add_stmt (seq, add_stmt);
> + return output;
> +}
> +
> +/* Reduce the vector from wide (e.g. ZMM) down to 128-bit lane by
> + repeatedly extracting low/high halves and adding them. E.g.
> + V16int32 -> extract low V8int32 and high V8int32, add -> V8int32;
> + then V8int32 -> V4int32; stop at 128 bits (V4int32 for 32-bit
> + elements). Appends generated statements to SEQ and returns the
> + final vector (single 128-bit lane). */
> +static tree
> +reduce_to_single_lane (tree vec_result, gimple_seq *seq)
> +{
> + tree vectype = TREE_TYPE (vec_result);
> + tree elt_type = TREE_TYPE (vectype);
> + unsigned elt_bits = TYPE_PRECISION (elt_type);
> + poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (vectype);
> + unsigned HOST_WIDE_INT n;
> + if (!nunits.is_constant (&n) || n < 2)
> + return vec_result;
> +
> + unsigned total_bits = n * elt_bits;
> + if (total_bits <= LANE_WIDTH_BITS)
> + return vec_result;
> +
> + tree current = vec_result;
> +
> + while (true)
> + {
> + nunits = TYPE_VECTOR_SUBPARTS (vectype);
> + if (!nunits.is_constant (&n) || n < 2)
> + break;
> + total_bits = n * elt_bits;
> + if (total_bits <= LANE_WIDTH_BITS)
> + break;
> +
> + unsigned half_n = n / 2;
> + tree half_vectype = build_vector_type (elt_type, half_n);
> + machine_mode full_mode = TYPE_MODE (vectype);
> + machine_mode half_mode = TYPE_MODE (half_vectype);
> +
> + vec_perm_builder sel_lo (half_n, 1, half_n);
> + vec_perm_builder sel_hi (half_n, 1, half_n);
> + for (unsigned i = 0; i < half_n; i++)
> + {
> + sel_lo.quick_push (i);
> + sel_hi.quick_push (half_n + i);
> + }
> + vec_perm_indices indices_lo (sel_lo, 1, n);
> + vec_perm_indices indices_hi (sel_hi, 1, n);
> +
> + if (!can_vec_extract (full_mode, half_mode))
> + return NULL_TREE;
> +
> + tree mask_lo = vect_gen_perm_mask_checked (half_vectype, indices_lo);
> + tree mask_hi = vect_gen_perm_mask_checked (half_vectype, indices_hi);
> +
> + tree low_half = make_ssa_name (half_vectype);
> + gimple *g_lo = gimple_build_assign (low_half, VEC_PERM_EXPR, current,
> + current, mask_lo);
> + gimple_seq_add_stmt (seq, g_lo);
> +
> + tree high_half = make_ssa_name (half_vectype);
> + gimple *g_hi = gimple_build_assign (high_half, VEC_PERM_EXPR, current,
> + current, mask_hi);
> + gimple_seq_add_stmt (seq, g_hi);
> +
> + tree sum = make_ssa_name (half_vectype);
> + gimple *g_add
> + = gimple_build_assign (sum, PLUS_EXPR, low_half, high_half);
> + gimple_seq_add_stmt (seq, g_add);
> + current = sum;
> + vectype = half_vectype;
> + }
> + if (dump_file)
> + fprintf (dump_file, "Reduced to single lane\n");
> + return current;
> +}
> +
> +/* Return true if the target supports whole-vector shifts for MODE,
> + either via vec_shr_optab or via vec_perm_const for every needed
> + shift amount. Mirrors have_whole_vector_shift in tree-vect-loop.cc. */
> +static bool
> +have_whole_vector_shift (machine_mode mode)
> +{
> + if (can_implement_p (vec_shr_optab, mode))
> + return true;
> +
> + unsigned int nelt;
> + if (!GET_MODE_NUNITS (mode).is_constant (&nelt))
> + return false;
> +
> + for (unsigned int i = nelt / 2; i >= 1; i /= 2)
> + {
> + /* Build the shift-by-i permutation mask:
> + a single stepped pattern {i, i+1, i+2}. */
> + vec_perm_builder sel (nelt, 1, 3);
> + for (unsigned int j = 0; j < 3; j++)
> + sel.quick_push (j + i);
> + vec_perm_indices indices (sel, 2, nelt);
> + if (!can_vec_perm_const_p (mode, mode, indices, false))
> + return false;
> + }
> + return true;
> +}
> +
> +/* Estimate the target cost of the replacement sequence SEQ. The vectype
> + for costing each stmt is derived from its LHS so that lane-reduction
> + stmts (which operate on narrower vectors) are costed correctly. */
> +static int
> +estimate_seq_cost (gimple_seq seq)
> +{
> + int cost = 0;
> + for (gimple_stmt_iterator si = gsi_start (seq); !gsi_end_p (si);
> + gsi_next (&si))
> + {
> + gimple *stmt = gsi_stmt (si);
> + if (!is_gimple_assign (stmt))
> + continue;
> + tree lhs = gimple_assign_lhs (stmt);
> + tree stmt_type = TREE_TYPE (lhs);
> + tree cost_vectype = VECTOR_TYPE_P (stmt_type) ? stmt_type : NULL_TREE;
> + enum tree_code code = gimple_assign_rhs_code (stmt);
> + if (code == VEC_PERM_EXPR)
> + cost += builtin_vectorization_cost (vec_perm, cost_vectype, 0);
> + else if (code == BIT_FIELD_REF)
> + cost += builtin_vectorization_cost (vec_to_scalar, cost_vectype, 0);
> + else
> + cost += builtin_vectorization_cost (vector_stmt, cost_vectype, 0);
> + }
> + return cost;
> +}
> +
> +/* Estimate the target cost of N_REDUCTIONS original REDUC_PLUS stmts.
> + Each horizontal reduction is lowered as a series of halving steps
> + (extract-high, extract-low, add) on progressively narrower vector
> + types, followed by a final scalar extract. Cost each step at its
> + actual vector width so targets where narrower ops are cheaper get
> + an accurate estimate. */
> +static int
> +estimate_orig_reduc_cost (unsigned n_reductions, tree vectype)
> +{
> + tree elt_type = TREE_TYPE (vectype);
> + unsigned elt_bits = TYPE_PRECISION (elt_type);
> + poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (vectype);
> + unsigned HOST_WIDE_INT n;
> + if (!nunits.is_constant (&n) || n < 2)
> + return 0;
> +
> + int per_reduc = 0;
> + tree cur_vectype = vectype;
> + unsigned cur_n = n;
> +
> + unsigned lane_elts = LANE_WIDTH_BITS / elt_bits;
> +
> + /* Cross-lane halving: reduce from full width down to a single
> + 128-bit lane. Each step extracts low/high halves (two vec_perm
> + at the current width) and adds them (one vector_stmt at the
> + narrower width). */
> + while (cur_n > lane_elts && cur_n >= 2)
> + {
> + unsigned half_n = cur_n / 2;
> + tree half_vectype = build_vector_type (elt_type, half_n);
> + per_reduc += 2 * builtin_vectorization_cost (vec_perm, cur_vectype, 0);
> + per_reduc += builtin_vectorization_cost (vector_stmt, half_vectype, 0);
> + cur_vectype = half_vectype;
> + cur_n = half_n;
> + }
> +
> + /* Intra-lane reduction within the 128-bit lane. */
> + if (cur_n >= 2)
> + {
> + machine_mode mode = TYPE_MODE (cur_vectype);
> + if (VECTOR_MODE_P (mode) && have_whole_vector_shift (mode))
> + {
> + int nshifts = exact_log2 (cur_n);
> + per_reduc
> + += nshifts * 2
> + * builtin_vectorization_cost (vector_stmt, cur_vectype, 0);
> + per_reduc
> + += builtin_vectorization_cost (vec_to_scalar, cur_vectype, 0);
> + }
> + else
> + per_reduc
> + += (2 * cur_n - 1)
> + * builtin_vectorization_cost (vector_stmt, cur_vectype, 0);
> + }
> +
> + return n_reductions * per_reduc;
> +}
> +
> +bool
> +may_build_unpack_tree (auto_vec<unpack_node *> &UnpackBinTree, tree vectype)
> +{
> + /* Trim trailing reductions so the count is a multiple of lane
> + elements. Dropped nodes are not optimized; their original
> + REDUC_PLUS stmts remain untouched in the BB. */
> + int elt_bits = TYPE_PRECISION (TREE_TYPE (vectype));
> + int num_elts = LANE_WIDTH_BITS / elt_bits;
> + int max_h = floor_log2 (num_elts);
> + int tree_height = 0;
> + while (UnpackBinTree.length () % num_elts != 0
> + && UnpackBinTree.length () > 2)
> + {
> + if (dump_file)
> + fprintf (dump_file,
> + "Dropping trailing REDUC_PLUS to align count"
> + " to %d-element lane boundary (%u remaining)\n",
> + num_elts, UnpackBinTree.length () - 1);
> + delete UnpackBinTree.pop ();
> + }
> + if (dump_file)
> + {
> + fprintf (dump_file, "eltsize: %d, num_elts: %d, max_h: %d\n", elt_bits,
> + num_elts, max_h);
> + fprintf (
> + dump_file,
> + "number of reductions %d must be multiple of lane elements %d\n",
> + UnpackBinTree.length (), num_elts);
> + }
> + if (num_elts < 2 || UnpackBinTree.length () % num_elts != 0
> + || UnpackBinTree.length () < 2)
> + {
> + for (auto node : UnpackBinTree)
> + delete node;
> + return false;
> + }
> + auto_vec<unpack_node *> TempUnpackBinTree;
> + while (true)
> + {
> + if (UnpackBinTree.length () == 1)
> + {
> + TempUnpackBinTree.safe_push (UnpackBinTree.pop ());
> + }
> + if (UnpackBinTree.length () == 0)
> + {
> + UnpackBinTree = TempUnpackBinTree.copy ();
> + TempUnpackBinTree.release ();
> + if (++tree_height >= max_h || UnpackBinTree.length () == 1)
> + break;
> + continue;
> + }
> + unpack_node *left = UnpackBinTree.pop ();
> + unpack_node *right = UnpackBinTree.pop ();
> + TempUnpackBinTree.safe_push (new unpack_node (left, right));
> + }
> + return true;
> +}
> +
> +/* Main pass execution: detect REDUC_PLUS chains per BB,
> + build unpack tree. */
> +static unsigned int
> +efficient_multiple_reduction (function *fun)
> +{
> + basic_block bb;
> + FOR_EACH_BB_FN (bb, fun)
> + {
> + hash_map<tree, auto_vec<unpack_node *> > reduction_groups;
> + /* Collect the REDUC_PLUS stmts in the BB and group them by vector
> + type. */
> + detect_reduction_for_bb (bb, &reduction_groups);
> + for (auto reduction : reduction_groups)
> + {
> + tree vectype = reduction.first;
> + auto_vec<unpack_node *> &UnpackBinTree = reduction.second;
> + if (!may_build_unpack_tree (UnpackBinTree, vectype))
> + continue;
> + for (auto node : UnpackBinTree)
> + {
> + if (node->leaf_node)
> + continue;
> + gimple_seq seq = NULL;
> + /* Build the sequence of vec_perm and add statements for
> + the unpacking of the low and high halves. */
> + tree reduced_output = prepare_vec_perm_seq (node, vectype, &seq);
> + if (reduced_output == NULL_TREE)
> + continue;
> + /* Reduce the vector from wide (e.g. ZMM) down to
> + 128-bit lane by repeatedly halving. */
> + tree single_lane = reduce_to_single_lane (reduced_output, &seq);
> + if (single_lane == NULL_TREE || seq == NULL)
> + {
> + gimple_seq_discard (seq);
> + continue;
> + }
> + hash_map<reduc_int_hash_t, auto_vec<int> > *idx_map
> + = node->get_reduction_index ();
> + /* Need to skip the get_reduc_index map logic. Can we avoid
> + using hashmap? Generate the extracts of reduced value
> + from the reduced lane vector. */
> + for (auto idx : *idx_map)
> + {
> + auto_vec<int> &idx_list = idx.second;
> + gcc_assert (idx.first >= 0
> + && (unsigned)idx.first
> + < node->red_values.length ());
> + gcc_assert (idx_list.length () >= 1);
> + gimple *reduc_stmt = node->red_values[idx.first];
> + tree reduc_lhs = gimple_call_lhs (reduc_stmt);
> + tree elt_type = TREE_TYPE (vectype);
> + int elt_bits = TYPE_PRECISION (elt_type);
> + tree size_bits = bitsize_int (elt_bits);
> + tree offset_bits = bitsize_int (idx_list[0] * elt_bits);
> + tree bf_ref = build3 (BIT_FIELD_REF, elt_type, single_lane,
> + size_bits, offset_bits);
> + gimple *extract_result
> + = gimple_build_assign (reduc_lhs, bf_ref);
> + gimple_seq_add_stmt (&seq, extract_result);
> + }
> + /* Estimate the cost of new sequence to be replaced
> + for the target. */
> + int new_cost = estimate_seq_cost (seq);
> + /* Estimate the cost of the original REDUC_PLUS stmts. */
> + int orig_cost = estimate_orig_reduc_cost (
> + node->red_values.length (), vectype);
> + if (dump_file)
> + fprintf (dump_file,
> + "Costing: seq_cost=%d, orig_cost=%d (%u reductions)\n",
> + new_cost, orig_cost, node->red_values.length ());
> + /* If the new sequence is not cheaper than the original,
> + skip the replacement. */
> + if (new_cost >= orig_cost)
> + {
> + if (dump_file)
> + fprintf (dump_file,
> + " -> not profitable, skipping replacement\n");
> + gimple_seq_discard (seq);
> + delete idx_map;
> + continue;
> + }
> + if (dump_file)
> + fprintf (dump_file, " -> profitable, applying replacement\n");
> + /* Insert the new sequence of gimple statements after
> + the last REDUC_PLUS stmt. */
> + gimple *last_reduc
> + = node->red_values[node->red_values.length () - 1];
> + gimple_stmt_iterator gsi = gsi_for_stmt (last_reduc);
> + gsi_insert_seq_after (&gsi, seq, GSI_SAME_STMT);
> + /* Delete the original REDUC_PLUS stmts. */
> + for (unsigned i = node->red_values.length (); i > 0; i--)
> + {
> + gimple *reduc_stmt = node->red_values[i - 1];
> + gsi = gsi_for_stmt (reduc_stmt);
> + gsi_remove (&gsi, true);
> + }
> + delete idx_map;
> + }
> + /* Cleaning up the memory for allocated nodes. */
> + for (auto node : UnpackBinTree)
> + delete node;
> + }
> + }
> + return 0;
> +}
> +
> +const pass_data pass_data_combine_reduc_plus_opt = {
> + GIMPLE_PASS,
> + "combine_reduc_plus_opt",
> + OPTGROUP_LOOP | OPTGROUP_VEC,
> + TV_TREE_COMBINE_REDUC_PLUS_OPT,
> + (PROP_cfg | PROP_ssa),
> + 0,
> + 0,
> + 0,
> + TODO_update_ssa,
> +};
> +
> +class pass_combine_reduc_plus_opt : public gimple_opt_pass
> +{
> +public:
> + pass_combine_reduc_plus_opt (gcc::context *ctxt)
> + : gimple_opt_pass (pass_data_combine_reduc_plus_opt, ctxt)
> + {
> + }
> +
> + opt_pass *
> + clone () final override
> + {
> + return new pass_combine_reduc_plus_opt (m_ctxt);
> + }
> +
> + bool
> + gate (function *) final override
> + {
> + return flag_tree_combine_reduc_plus_opt;
> + }
> +
> + unsigned int
> + execute (function *fun) final override
> + {
> + return efficient_multiple_reduction (fun);
> + }
> +};
> +
> +} // anon namespace
> +
> +gimple_opt_pass *
> +make_pass_combine_reduc_plus_opt (gcc::context *ctxt)
> +{
> + return new pass_combine_reduc_plus_opt (ctxt);
> +}
> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> index b3c97658a8f..d4f11a86771 100644
> --- a/gcc/tree-pass.h
> +++ b/gcc/tree-pass.h
> @@ -393,6 +393,7 @@ extern gimple_opt_pass *make_pass_crc_optimization
> (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_slp_vectorize (gcc::context *ctxt);
> +extern gimple_opt_pass *make_pass_combine_reduc_plus_opt (gcc::context
> *ctxt);
> extern gimple_opt_pass *make_pass_complete_unroll (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_complete_unrolli (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_pre_slp_scalar_cleanup (gcc::context
> *ctxt);
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
