On Mon, 25 May 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 maximum VF=8, iterations 0-7 of
> "i >> 6" all evaluate to 0, enabling optimization to broadcast. If the
> offset is uniform at max VF, it is uniform at any smaller VF, so we
> only need to check once. 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
>
> gcc/ChangeLog:
>
> * tree-vect-data-refs.cc (vect_describe_gather_scatter_call): Initialize
> STMT_VINFO_GATHER_UNIFORM_P in stmt_vec_info to false.
> (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): Run the uniformity check, cache by offset
> to avoid recomputing for the same offset, and set
> STMT_VINFO_GATHER_UNIFORM_P.
> * tree-vect-loop.cc (vect_analyze_loop): Compute maximum VF over
> candidate vector modes for the uniformity check.
> * 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 stmt_vec_info to SLP nodes.
> * tree-vectorizer.cc (vec_info_shared::vec_info_shared): Initialize
> max_autovectorize_vf, which is the maximum VF over all candidate
> vector modes.
> (vec_info::new_stmt_vec_info): Initialize gather_offset_uniform_p.
> * tree-vectorizer.h (struct _slp_tree): Add uniformity fields, cache,
> and accessors for emulated gather offset analysis.
> (SLP_TREE_GS_OFFSET_UNIFORM_P): New. Uniformity flag for SLP trees.
> (struct gather_scatter_info): Added STMT_VINFO_GATHER_UNIFORM_P field.
> (STMT_VINFO_GATHER_UNIFORM_P): New. Uniformity flag for stmt_vec_info.
> (gs_offset_uniform_p): New field in _slp_tree for uniformity flag.
>
> ---
> gcc/tree-vect-data-refs.cc | 138 ++++++++++++++++++++++++++++++++++++-
> gcc/tree-vect-loop.cc | 14 ++++
> gcc/tree-vect-slp.cc | 4 ++
> gcc/tree-vect-stmts.cc | 10 +++
> gcc/tree-vectorizer.cc | 5 +-
> gcc/tree-vectorizer.h | 15 ++++
> 6 files changed, 184 insertions(+), 2 deletions(-)
>
> diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
> index da65f1d652c..fe7fc34aeac 100644
> --- a/gcc/tree-vect-data-refs.cc
> +++ b/gcc/tree-vect-data-refs.cc
> @@ -4764,6 +4764,7 @@ void
> vect_describe_gather_scatter_call (stmt_vec_info stmt_info,
> gather_scatter_info *info)
> {
> + STMT_VINFO_GATHER_UNIFORM_P (stmt_info) = false;
> gcall *call = as_a <gcall *> (stmt_info->stmt);
> tree vectype = STMT_VINFO_VECTYPE (stmt_info);
> data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
> @@ -4781,17 +4782,119 @@ vect_describe_gather_scatter_call (stmt_vec_info
> stmt_info,
> info->element_type = TREE_TYPE (vectype);
> info->memory_type = TREE_TYPE (DR_REF (dr));
> }
> +/* Check whether the offset in gather load is uniform across all the VF
> lanes.
> + If true then If uniform, record it in STMT_VINFO_GATHER_UNIFORM_P
> + (stmt_info) so later gather-load lowering can use scalar-load + broadcast
> + instead of full emulated gather. */
> +static bool
> +vect_check_gather_load_offset_uniform (class loop *loop,
> + HOST_WIDE_INT const_vf,
> + tree off)
> +{
> + /* 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 off_scev = analyze_scalar_evolution (loop, off);
> + if (off_scev && off_scev != chrec_dont_know
> + && TREE_CODE (off_scev) != SSA_NAME)
> + off_scev = instantiate_parameters (loop, off_scev);
As you are looking for an 'off' that evaluates to the same value
for N iterations it can never be an affine evolution, so no need
to analyze 'off' itself.
Instead you are looking for BIT_AND_EXPR or TRUNC_DIV_EXPR,
both with a constant 2nd operand.
> + tree chrec1 = NULL_TREE, chrec2 = NULL_TREE;
> + tree_code op_code = ERROR_MARK;
> + tree op_type = TREE_TYPE (off);
> + if (!off_scev || off_scev == chrec_dont_know
> + || TREE_CODE (off_scev) == SSA_NAME)
> + {
> + gimple *def_stmt = SSA_NAME_DEF_STMT (off);
> + if (is_gimple_assign (def_stmt))
> + {
> + op_code = gimple_assign_rhs_code (def_stmt);
> + tree rhs2 = gimple_assign_rhs2 (def_stmt);
> + if (rhs2 && TREE_CODE_CLASS (op_code) == tcc_binary)
> + {
> + tree rhs1 = gimple_assign_rhs1 (def_stmt);
> + chrec1 = analyze_scalar_evolution (loop, rhs1);
so only analyzing RHS1 is required (and RHS2 can be used to
pre-filter interesting cases).
> + chrec2 = analyze_scalar_evolution (loop, rhs2);
> + chrec1 = instantiate_parameters (loop, chrec1);
> + chrec2 = instantiate_parameters (loop, chrec2);
> + if (dump_enabled_p ())
> + {
> + dump_printf_loc (MSG_NOTE, vect_location, "chrec 1: ");
> + dump_generic_expr (MSG_NOTE, TDF_SLIM, chrec1);
> + dump_printf (MSG_NOTE, "\nchrec2: ");
> + dump_generic_expr (MSG_NOTE, TDF_SLIM, chrec2);
> + dump_printf (MSG_NOTE, "\n");
> + }
> + }
> + }
> + }
> + if (!chrec1 || !chrec2 || chrec1 == chrec_dont_know
> + || chrec2 ==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)
> + || TREE_CODE (chrec2) != INTEGER_CST)
> + return false;
> + tree scev_base = CHREC_LEFT (chrec1);
> + tree scev_step = CHREC_RIGHT (chrec1);
> + /* PoC valid for {0, +, 1} induction pattern now.
> + TODO Extend to handle general case. */
> + if ( TREE_CODE (scev_base) != INTEGER_CST
> + || TREE_CODE (scev_step) != INTEGER_CST
> + || !integer_zerop (scev_base) || !integer_onep (scev_step))
> + {
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "returning because of non-zero base or"
> + "non-one step\n");
> + return false;
> + }
> + /* Iterate from scev_base advancing scev_step each lane, for the VF lanes.
> + Then evaluate each operand at the current iteration value,
> + fold and compare. */
> + tree first_val = NULL_TREE;
> + tree scev_end = fold_build2 (PLUS_EXPR, TREE_TYPE (scev_base),
> + scev_base,
> + build_int_cst (TREE_TYPE (scev_base),
> + const_vf));
> + for (tree iter_val = scev_base;
> + tree_int_cst_lt (iter_val, scev_end);
> + iter_val = fold_build2 (PLUS_EXPR, TREE_TYPE (iter_val),
> + iter_val, scev_step))
> + {
> + tree chrec1_at_iter = (TREE_CODE (chrec1) == POLYNOMIAL_CHREC
> + ? chrec_apply (loop->num, chrec1, iter_val)
> + : chrec1);
> + tree concrete_val = fold_build2 (op_code, op_type, chrec1_at_iter,
> + chrec2);
> + if (!first_val)
> + first_val = concrete_val;
> + else if (!operand_equal_p (concrete_val, first_val, 0))
> + return false;
> + if (first_val && TREE_CODE (first_val) == SSA_NAME
> + && !expr_invariant_in_loop_p (loop, first_val))
> + return false;
Uh. I think we want something more "programmatic", given we
have a binop with constant operand and the CHREC_RIGHT is constant
as well we should be able to comptute arithmetically whether
(CHREC_LEFT + N * CHREC_RIGHT) <op> RHS2 is zero for all N in [0, VF].
> + }
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
> + "gather offset is uniform across VF=%d, "
> + "broadcast optimization possible\n",
> + (int) const_vf);
> + return true;
> +}
>
> /* 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. */
> -
> bool
> vect_check_gather_scatter (stmt_vec_info stmt_info, tree vectype,
> loop_vec_info loop_vinfo,
> gather_scatter_info *info, vec<int> *elsvals)
> {
> + STMT_VINFO_GATHER_UNIFORM_P (stmt_info) = false;
please do not record into stmt_info, instead record into ...
> HOST_WIDE_INT scale = 1;
> poly_int64 pbitpos, pbitsize;
> class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
> @@ -5114,6 +5217,39 @@ 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;
... 'info'.
> + /* Check whether uniform gather load for all the vector lanes for
> + maximum VF. */
> + unsigned HOST_WIDE_INT max_vf = loop_vinfo->shared->max_autovectorize_vf;
Not sure why you need a max_vf here, you want to perform the analysis
when 'vectype' is not NULL and for TYPE_VECTOR_SUBPARTS (vectype)
I think.
> + if (max_vf == 0)
> + {
> + /* If not set then skip the uniforme check. */
> + return true;
> + }
> + HOST_WIDE_INT const_vf = (HOST_WIDE_INT) max_vf;
> + bool uniform = false;
> + if (const_vf > 0)
> + {
> + /* If the uniformity is true for one VF, we do not have to try another
> + VF. We always establish uniformity for max_vfs. Uniformity (max_vf)
> + implies uniformity (lower_vfs). So reuse cached result for this offset.
> + re-do the same check. */
> + bool *cached = loop_vinfo->offset_uniformity_cache.get (off);
> + if (cached)
> + uniform = *cached;
> + else
> + {
> + if (dump_enabled_p ())
> + {
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "offset uniformity check at max VF=%wd\n",
> + const_vf);
> + }
> + uniform = vect_check_gather_load_offset_uniform (loop, const_vf, off);
> + loop_vinfo->offset_uniformity_cache.put (off, uniform);
> + }
> + }
> + /* The information is stored in stm_vinfo for subsequent stages. */
> + STMT_VINFO_GATHER_UNIFORM_P (stmt_info) = uniform;
> return true;
> }
>
> diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> index ac7e08cf205..899934306c1 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -2965,6 +2965,20 @@ vect_analyze_loop (class loop *loop, gimple
> *loop_vectorized_call,
> unsigned int autovec_flags
> = targetm.vectorize.autovectorize_vector_modes (&vector_modes,
> loop->simdlen != 0);
> + /* Get the maximum VF from all the vector_modes to use in checking whether
> + offset is uniform. */
> + unsigned HOST_WIDE_INT max_munits = 0;
> + for (unsigned i = 0; i < vector_modes.length (); i++)
> + {
> + machine_mode mode = vector_modes[i];
> + if (mode == VOIDmode)
> + continue;
> + poly_uint64 m_units = GET_MODE_NUNITS (mode);
> + unsigned HOST_WIDE_INT c;
> + if (m_units.is_constant (&c) && c > 0 && c > max_munits)
> + max_munits = c;
> + }
> + shared->max_autovectorize_vf = max_munits;
> bool pick_lowest_cost_p = ((autovec_flags & VECT_COMPARE_COSTS)
> && !unlimited_cost_model (loop));
> machine_mode autodetected_vector_mode = VOIDmode;
> diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
> index ea49c32b780..7224d6c77db 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;
> + this->gs_offset_uniform_p = false;
SLP_TREE_GS_OFFSET_UNIFORM_P
> this->ldst_lanes = false;
> this->avoid_stlf_fail = false;
> SLP_TREE_VECTYPE (this) = NULL_TREE;
> @@ -2809,6 +2810,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)
> @@ -2836,6 +2838,7 @@ out:
> {
> gs_scale = oprnd_info->first_gs_info.scale;
> gs_base = oprnd_info->first_gs_info.base;
> + gs_offset_uniform_p = STMT_VINFO_GATHER_UNIFORM_P (stmt_info);
> }
>
> if (is_a <bb_vec_info> (vinfo)
> @@ -3256,6 +3259,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 da87b329715..b68fc5072af 100644
> --- a/gcc/tree-vect-stmts.cc
> +++ b/gcc/tree-vect-stmts.cc
> @@ -2167,6 +2167,12 @@ get_load_store_type (vec_info *vinfo, stmt_vec_info
> stmt_info,
> }
> else if (STMT_VINFO_GATHER_SCATTER_P (stmt_info))
> {
> + slp_node->gs_offset_uniform_p
> + = STMT_VINFO_GATHER_UNIFORM_P (stmt_info);
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "gs_offset_uniform_p is set to: %d \n",
> + STMT_VINFO_GATHER_UNIFORM_P (stmt_info));
> slp_tree offset_node = SLP_TREE_CHILDREN (slp_node)[0];
> tree offset_vectype = SLP_TREE_VECTYPE (offset_node);
> int scale = SLP_TREE_GS_SCALE (slp_node);
> @@ -2474,6 +2480,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)
> + = STMT_VINFO_GATHER_UNIFORM_P (stmt_info);
> ls->gs.ifn = gs_info.ifn;
> ls->strided_offset_vectype = gs_info.offset_vectype;
> *memory_access_type = VMAT_GATHER_SCATTER_IFN;
> @@ -2488,6 +2496,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)
> + = STMT_VINFO_GATHER_UNIFORM_P (stmt_info);
> 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.cc b/gcc/tree-vectorizer.cc
> index 205a07b0be5..d4c915ddd8b 100644
> --- a/gcc/tree-vectorizer.cc
> +++ b/gcc/tree-vectorizer.cc
> @@ -483,7 +483,9 @@ vec_info::~vec_info ()
> vec_info_shared::vec_info_shared ()
> : datarefs (vNULL),
> datarefs_copy (vNULL),
> - ddrs (vNULL)
> + ddrs (vNULL),
> + max_autovectorize_vf (0)
> +
> {
> }
>
> @@ -718,6 +720,7 @@ vec_info::new_stmt_vec_info (gimple *stmt)
>
> STMT_VINFO_RELEVANT (res) = vect_unused_in_scope;
> STMT_VINFO_VECTORIZABLE (res) = true;
> + STMT_VINFO_GATHER_UNIFORM_P (res) = false;
> STMT_VINFO_REDUC_TYPE (res) = TREE_CODE_REDUCTION;
> STMT_VINFO_REDUC_CODE (res) = ERROR_MARK;
> STMT_VINFO_REDUC_IDX (res) = -1;
> diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
> index 3a01e1be0f1..b2a55f21421 100644
> --- a/gcc/tree-vectorizer.h
> +++ b/gcc/tree-vectorizer.h
> @@ -369,6 +369,8 @@ 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 VF 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
> @@ -474,6 +476,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)
>
> @@ -612,6 +615,10 @@ public:
> /* All data dependences. Freed by free_dependence_relations, so not
> an auto_vec. */
> vec<ddr_p> ddrs;
> +
> + /* Maximum VF over all autovectorize vector modes for the loop. */
> + unsigned HOST_WIDE_INT max_autovectorize_vf;
> +
> };
>
> /* Vectorizer state common between loop and basic-block vectorization. */
> @@ -1117,6 +1124,9 @@ public:
> rhs of the store of the initializer. */
> hash_map<tree, tree> *scan_map;
>
> + /* Cache for uniformity in gather/scatter to avoid recomputation. */
> + hash_map<tree_operand_hash, bool> offset_uniformity_cache;
> +
> /* The factor used to over weight those statements in an inner loop
> relative to the loop being vectorized. */
> unsigned int inner_loop_cost_factor;
> @@ -1595,6 +1605,9 @@ public:
> /* For loads if this is a gather, for stores if this is a scatter. */
> bool gather_scatter_p;
>
> + /* For loads if this is a uniform broadcast. */
> + bool gather_offset_uniform_p;
> +
> /* True if this is an access with loop-invariant stride. */
> bool strided_p;
>
> @@ -1685,6 +1698,7 @@ struct gather_scatter_info {
>
> /* The type of the scalar elements being loaded or stored. */
> tree memory_type;
> +
> };
>
> /* Access Functions. */
> @@ -1695,6 +1709,7 @@ struct gather_scatter_info {
> #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
> #define STMT_VINFO_DATA_REF(S) ((S)->dr_aux.dr + 0)
> #define STMT_VINFO_GATHER_SCATTER_P(S) (S)->gather_scatter_p
> +#define STMT_VINFO_GATHER_UNIFORM_P(S) (S)->gather_offset_uniform_p
> #define STMT_VINFO_STRIDED_P(S) (S)->strided_p
> #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
> #define STMT_VINFO_REDUC_IDX(S) (S)->reduc_idx
>
--
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)
