---
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).
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);
--
2.34.1
