On Tue, 6 Oct 2026, [email protected] wrote:
> From: Reshma Roy <[email protected]>
>
> Implement analysis using SCEV information to detect when gather/scatter
> offset expressions evaluate to the same value for all vector lanes within
> each vector iteration. For example, if VF=8, iterations 0-7 of
> "i >> 6" all evaluate to 0, enabling optimization to broadcast. The uniformity
> information is propagated to SLP nodes for use in the transformation phase.
>
> Example: For "M[i >> 6]" with VF=8:
> - Iterations 0-7: i >> 6 = 0 (uniform)
> - Iterations 64-71: i >> 6 = 1 (uniform)
> Here we can optimize each vector iteration to load once + broadcast
>
> v4 changes
> - Analyze the offset SCEV in its defining loop and require the chrec to
> evolve in the vectorized loop (outer-loop vectorization).
> - Allow a non-zero constant base {B, +, 1} when B >= 0 and B % VF == 0.
> - Disable the uniform flag for multi-lane SLP gather groups.
> - Compute 2^k only for RSHIFT_EXPR and drop redundant checks.
> - Move and reword the dump messages; remove the verbose
> get_load_store_type dump.
>
> TODO: Handle arbitrary step beyond {B,+,1} where B is the arbitrary base.
>
> gcc/ChangeLog:
>
> * tree-vect-data-refs.cc (vect_check_gather_load_offset_uniform): New.
> Return whether the gather offset is the same for every lane at the
> given VF.
> (vect_check_gather_scatter): Call vect_check_gather_load_offset_uniform
> and record the result in gather_scatter_info::offset_uniform.
> * tree-vect-slp.cc (_slp_tree::_slp_tree): Initialize and propagate
> gs_offset_uniform_p on SLP trees.
> * tree-vect-stmts.cc (get_load_store_type): Copy gather uniform
> flag from gather_scatter_info to SLP nodes.
> * tree-vectorizer.h (struct _slp_tree): Add gs_offset_uniform_p field.
> (SLP_TREE_GS_OFFSET_UNIFORM_P): New macro.
> (struct gather_scatter_info): New field offset_uniform for flagging
> uniformity.
> ---
>
> Hi Richard,
> All the comments were addressed and the details are given below:
>
> 1. Non-zero base: Removed the zero-base requirement. The step is still
> required to be 1. A constant base B is accepted when B >= 0 and B % VF == 0,
> so each vector chunk still has the {0, +, 1} shape. A negative base is
> rejected
> because truncating division rounds toward zero.
>
> 2. Outer loop gather: Inner-loop references are not gathers while the
> outer loop is vectorized (vect_analyze_data_refs requires
> !nested_in_vect_loop_p).
> A gather in the outer-loop body can still reach here. The helper analyzes the
> offset in the loop that defines it and requires CHREC_VARIABLE == loop->num,
> so
> an inner-loop evolution is rejected. instantiate_parameters then interprets
> that chrec in the vectorized loop.
>
> 3. SLP Group: Gated on group_size == 1, so a multi-lane group does not
> keep the flag from the first statement. No combined field on oprnd_info,
> because that case no longer claims uniformity. vect_get_and_check_slp_defs
> does
> not compare offset_uniform: the flag only enables an optimization and must
> not fail SLP discovery.
>
> Thanks,
> Reshma Roy
>
> gcc/tree-vect-data-refs.cc | 145 ++++++++++++++++++++++++++++++++++++-
> gcc/tree-vect-slp.cc | 12 +++
> gcc/tree-vect-stmts.cc | 4 +
> gcc/tree-vectorizer.h | 8 ++
> 4 files changed, 168 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
> index 23235875fa2..f2b3ae02c25 100644
> --- a/gcc/tree-vect-data-refs.cc
> +++ b/gcc/tree-vect-data-refs.cc
> @@ -4704,11 +4704,143 @@ vect_describe_gather_scatter_call (stmt_vec_info
> stmt_info,
> info->memory_type = TREE_TYPE (DR_REF (dr));
> }
>
> +/* Check whether the offset in gather load is uniform across each lane in a
> + vector iteration. If true then, record it in gather_scatter_info so later
> + gather-load lowering can use scalar-load + broadcast instead of full
> + emulated gather.
> + For example, consider a loop with induction variable i = {0, +, 1} that
> + loads a[i >> 2] and a vectorization factor (number of lanes) of 4:
> +
> + for (i = 0; i < n; i++)
> + sum += a[i >> 2];
> +
> + Here the offset within each 4-lane vector chunk is uniform:
> + chunk 0: i = {0,1,2,3} -> i >> 2 = {0,0,0,0}
> + chunk 1: i = {4,5,6,7} -> i >> 2 = {1,1,1,1}
> + Every lane in a chunk accesses the same element, so instead of emitting a
> + full (emulated) gather we can perform a single scalar load and broadcast
> + it across the vector. This holds precisely when N - 1 < 2^k (here
> + 4 - 1 < 2^2), which is the condition checked below for RSHIFT_EXPR (and
> the
> + analogous conditions for TRUNC_DIV_EXPR and BIT_AND_EXPR).
> +
> + Let VF refers to number of lanes in a vector iterations which is a power
> + of 2 with the SCEV of the induction variable i is {B,+,1} with B >= 0 and
> + B % VF == 0, and N refers the vector chunk:
> + * When operator is i >> k (k >= 0) . All lanes in every vector chunk have
> a
> + uniform index if and only if: VF ??? 1 < 2^k.
> + * When the operator is division i / k, all lanes in every vector chunk
> + have a uniform index if and only if VF divides k, i.e. k % VF == 0.
> + Note that VF - 1 < k is NOT sufficient for a non-power-of-two divisor
> + (e.g VF=4, k=5: chunk {4,5,6,7} is not uniform).
> + * When the operator is i & k then all lanes in every vector chunk have a
> + uniform index if and only if (N - 1) & k = 0. For i & k, with i = N*VF
> + + j (j in[0, VF-1]) and VF = 2^m: the low m = log2 (VF) bits of i hold j
> + and VARY across the lanes, while the higher bits hold N and stay
> + CONSTANT within the chunk. E.g VF=8, chunk N=5 gives i in
> + {40 to 47} = 101_000 to 101_111 : the top bits (101 = N) are fixed,
> + only the low 3 bits (= j) change. So i & k is the same on every lane
> + iff k has no bit set in those low m bits, i.e. (k & (VF - 1)) == 0. */
add one line vertical space
> +static bool
> +vect_check_gather_load_offset_uniform (class loop *loop,
> + HOST_WIDE_INT const_nunits,
> + tree off)
> +{
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "offset uniformity check at vector nunits=%wd\n",
> + const_nunits);
> + /* Check ensures that the offset is an SSA_NAME which is qualified for
> + uniform detection. */
> + if (!off || TREE_CODE (off) != SSA_NAME)
> + return false;
> + tree chrec1 = NULL_TREE, rhs1 = NULL_TREE, rhs2 = NULL_TREE;
> + gimple *def_stmt = SSA_NAME_DEF_STMT (off);
> + if (!is_gimple_assign (def_stmt))
> + return false;
> + tree_code op_code = ERROR_MARK;
> + op_code = gimple_assign_rhs_code (def_stmt);
> + if (op_code != BIT_AND_EXPR && op_code != TRUNC_DIV_EXPR
> + && op_code != RSHIFT_EXPR)
> + return false;
> + rhs1 = gimple_assign_rhs1 (def_stmt);
> + rhs2 = gimple_assign_rhs2 (def_stmt);
> + /* Strict check for operand 2 to be constant. */
> + if (TREE_CODE (rhs2) != INTEGER_CST)
> + return false;
> + if (TREE_CODE (rhs1) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (rhs1))
> + return false;
> + chrec1 = analyze_scalar_evolution
> + (gimple_bb (SSA_NAME_DEF_STMT (rhs1))->loop_father, rhs1);
> + chrec1 = instantiate_parameters (loop, chrec1);
> + if (!chrec1 || chrec1 == chrec_dont_know)
> + return false;
> + /* Strict check for operand 1 to be poly rec and
> + operand 2 to be constant. */
> + if (TREE_CODE (chrec1) != POLYNOMIAL_CHREC
> + || CHREC_VARIABLE (chrec1) != (unsigned) loop->num)
> + return false;
> + tree scev_base = CHREC_LEFT (chrec1);
> + tree scev_step = CHREC_RIGHT (chrec1);
> + /* Valid for {B, +, 1} induction pattern now.
> + TODO Extend to handle general case. */
> + if (TREE_CODE (scev_base) != INTEGER_CST
> + || TREE_CODE (scev_step) != INTEGER_CST
> + || !integer_onep (scev_step)
> + || tree_int_cst_sgn (scev_base) < 0)
> + {
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "cannot determine uniformity"
> + " because of non-constant or negative base or non-one"
> + " step\n");
> + return false;
> + }
> + /* Convert SCEV components and operands to wide_int for uniformity
> analysis.
> + These values are used to determine if the gather load offset is uniform
> + across vector lanes based on the operation type (RSHIFT, TRUNC_DIV, or
> + BIT_AND) and the relationship between the vector number of lanes and the
> + operand. */
> + wide_int rhs_wi = wi::to_wide (rhs2);
> + unsigned prec = TYPE_PRECISION (TREE_TYPE (rhs2));
> + unsigned int base_prec = TYPE_PRECISION (TREE_TYPE (scev_base));
> + wide_int base_wi = wi::to_wide (scev_base);
> + wide_int vf_m1 = wi::uhwi (const_nunits - 1, prec);
> + wide_int vf_base = wi::uhwi (const_nunits, base_prec);
> + /* {B,+,1} has the {0,+,1} chunk shape iff B is a multiple of VF.
> + All three operators need this, so reject once. */
> + if (!wi::eq_p (wi::umod_trunc (base_wi, vf_base), wi::zero (base_prec)))
> + return false;
> + bool is_uniform = false;
> + if (op_code == RSHIFT_EXPR)
> + {
> + wide_int pow2_k = wi::lshift (wi::one (prec), rhs_wi);
> + if (wi::ltu_p (vf_m1, pow2_k))
> + is_uniform = true;
> + }
> + else if (op_code == TRUNC_DIV_EXPR)
> + {
> + wide_int vf_wi = wi::uhwi (const_nunits, prec);
> + if (wi::eq_p (wi::umod_trunc (rhs_wi, vf_wi), wi::zero (prec)))
> + is_uniform = true;
> + }
> + else if (op_code == BIT_AND_EXPR)
> + {
> + wide_int mask_m1 = wi::bit_and (rhs_wi, vf_m1);
> + if (wi::eq_p (mask_m1, wi::zero (prec)))
> + is_uniform = true;
> + }
> + if (is_uniform && dump_enabled_p ())
> + dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
> + "gather offset is uniform across %d vector lanes, "
> + "broadcast optimization possible\n",
> + (int) const_nunits);
> + return is_uniform;
> +}
> +
> /* Return true if a non-affine read or write in STMT_INFO is suitable for a
> gather load or scatter store with VECTYPE. Describe the operation in
> *INFO
> if so. If it is suitable and ELSVALS is nonzero store the supported else
> values in the vector it points to. */
> -
please do not remove this vertical space
The patch is OK with this change. Note I have not seen 2/2, it might
have gone missed?
Thanks,
Richard.
> bool
> vect_check_gather_scatter (stmt_vec_info stmt_info, tree vectype,
> loop_vec_info loop_vinfo,
> @@ -5036,6 +5168,17 @@ vect_check_gather_scatter (stmt_vec_info stmt_info,
> tree vectype,
> info->scale = scale;
> info->element_type = TREE_TYPE (vectype);
> info->memory_type = memory_type;
> + /* Record whether the gather offset is uniform across the lanes. A ref
> nested
> + in an inner loop is never a gather while the outer loop is vectorized
> (see
> + vect_analyze_data_refs). A gather in the outer-loop body still reaches
> + here; the helper analyzes the offset in the loop that defines it and
> + instantiates that chrec in LOOP. */
> + unsigned HOST_WIDE_INT nunits;
> + bool uniform = false;
> + if (TYPE_VECTOR_SUBPARTS (vectype).is_constant (&nunits))
> + uniform = vect_check_gather_load_offset_uniform (loop, nunits, off);
> + /* The information is stored in gather_scatter_info for subsequent stages.
> */
> + info->offset_uniform = uniform;
> return true;
> }
>
> diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
> index 12b1abe3d78..4a97c2de21d 100644
> --- a/gcc/tree-vect-slp.cc
> +++ b/gcc/tree-vect-slp.cc
> @@ -123,6 +123,7 @@ _slp_tree::_slp_tree ()
> SLP_TREE_CODE (this) = ERROR_MARK;
> SLP_TREE_GS_SCALE (this) = 0;
> SLP_TREE_GS_BASE (this) = NULL_TREE;
> + SLP_TREE_GS_OFFSET_UNIFORM_P (this) = false;
> this->ldst_lanes = false;
> this->avoid_stlf_fail = false;
> SLP_TREE_VECTYPE (this) = NULL_TREE;
> @@ -932,6 +933,9 @@ vect_get_and_check_slp_defs (vec_info *vinfo, tree
> vectype, unsigned char swap,
> "Build SLP failed: different gather base\n");
> return 1;
> }
> + /* Do not compare offset_uniform. It only enables an optimization
> + and must not make SLP discovery fail; the flag is dropped for
> + multi-lane nodes in vect_build_slp_tree_2. */
> if (oprnd_info->first_gs_info.scale != gs_info.scale)
> {
> if (dump_enabled_p ())
> @@ -2949,6 +2953,7 @@ out:
> int reduc_idx = -1;
> int gs_scale = 0;
> tree gs_base = NULL_TREE;
> + bool gs_offset_uniform_p = false;
>
> /* Create SLP_TREE nodes for the definition node/s. */
> FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info)
> @@ -2980,6 +2985,12 @@ out:
> {
> gs_scale = oprnd_info->first_gs_info.scale;
> gs_base = oprnd_info->first_gs_info.base;
> + /* Offset uniformity is computed per scalar stmt. With more than
> + one lane the vector interleaves the offsets of different stmts,
> + so a single scalar load plus broadcast is not valid even if each
> + stmt is uniform. Only keep the flag for a single-lane node. */
> + gs_offset_uniform_p = (group_size == 1
> + && oprnd_info->first_gs_info.offset_uniform);
> }
>
> if (is_a <bb_vec_info> (vinfo)
> @@ -3423,6 +3434,7 @@ fail:
> SLP_TREE_CHILDREN (node).splice (children);
> SLP_TREE_GS_SCALE (node) = gs_scale;
> SLP_TREE_GS_BASE (node) = gs_base;
> + SLP_TREE_GS_OFFSET_UNIFORM_P (node) = gs_offset_uniform_p;
> if (reduc_idx != -1)
> {
> gcc_assert (STMT_VINFO_REDUC_IDX (stmt_info) != -1
> diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
> index 18d0dd8ff3a..72decdc50c5 100644
> --- a/gcc/tree-vect-stmts.cc
> +++ b/gcc/tree-vect-stmts.cc
> @@ -2486,6 +2486,8 @@ get_load_store_type (vec_info *vinfo, stmt_vec_info
> stmt_info,
>
> SLP_TREE_GS_SCALE (slp_node) = gs_info.scale;
> SLP_TREE_GS_BASE (slp_node) = error_mark_node;
> + SLP_TREE_GS_OFFSET_UNIFORM_P (slp_node)
> + = gs_info.offset_uniform;
> ls->gs.ifn = gs_info.ifn;
> ls->strided_offset_vectype = gs_info.offset_vectype;
> *memory_access_type = VMAT_GATHER_SCATTER_IFN;
> @@ -2500,6 +2502,8 @@ get_load_store_type (vec_info *vinfo, stmt_vec_info
> stmt_info,
> {
> SLP_TREE_GS_SCALE (slp_node) = gs_info.scale;
> SLP_TREE_GS_BASE (slp_node) = error_mark_node;
> + SLP_TREE_GS_OFFSET_UNIFORM_P (slp_node)
> + = gs_info.offset_uniform;
> grouped_gather_fallback = *memory_access_type;
> *memory_access_type = VMAT_GATHER_SCATTER_IFN;
> ls->gs.ifn = gs_info.ifn;
> diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
> index abd9edc2743..224be46bfd8 100644
> --- a/gcc/tree-vectorizer.h
> +++ b/gcc/tree-vectorizer.h
> @@ -389,6 +389,9 @@ struct _slp_tree {
> /* For gather/scatter memory operations the scale each offset element
> should be multiplied by before being added to the base. */
> int gs_scale;
> + /* For gather/scatter, when the offset is uniform across each individual
> + vector number of lanes iterations. */
> + bool gs_offset_uniform_p;
> /* For gather/scatter memory operations the loop-invariant base value. */
> tree gs_base;
> /* Whether uses of this load or feeders of this store are suitable
> @@ -495,6 +498,7 @@ public:
> #define SLP_TREE_TYPE(S) (S)->type
> #define SLP_TREE_GS_SCALE(S) (S)->gs_scale
> #define SLP_TREE_GS_BASE(S) (S)->gs_base
> +#define SLP_TREE_GS_OFFSET_UNIFORM_P(S) (S)->gs_offset_uniform_p
> #define SLP_TREE_REDUC_IDX(S)
> (S)->cycle_info.reduc_idx
> #define SLP_TREE_PERMUTE_P(S) ((S)->code ==
> VEC_PERM_EXPR)
>
> @@ -1718,6 +1722,10 @@ struct gather_scatter_info {
>
> /* The type of the scalar elements being loaded or stored. */
> tree memory_type;
> +
> + /* The field to record if the offset is uniform each individual vector
> + number of lanes iterations. */
> + bool offset_uniform;
> };
>
> /* Access Functions. */
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
