On Wed, 24 Jun 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
>
> v2 changes
> - Pattern-match offset defs instead of SCEV on off
> - SCEV only RHS1; RHS2 is constant
> - Store uniformity in gather_scatter_info
> - Use TYPE_VECTOR_SUBPARTS(vectype) for VF
> - Drop max_autovectorize_vf and offset cache
> - Update SLP/stmt paths to read gs_info.offset_uniform
>
> TODO: Replace per-lane simulation with arithmetic reasoning
>
> 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,
>
> The suggested comments except one were addressed and the patch is updated.
> The detailed description are added inline.
>
> Thanks,
> Reshma Roy
>
> Original Message-----
> > From: Richard Biener <[email protected]>
> > Sent: Tuesday, June 9, 2026 7:24 PM
> > To: Roy, Reshma <[email protected]>
> > Cc: [email protected]; Kumar, Venkataramanan
> > <[email protected]>
> > Subject: Re: [PATCH 1/2] Loop Vectorizer: Detect uniform gather offsets
> > using
> > SCEV analysis
> >
> > Caution: This message originated from an External Source. Use proper caution
> > when opening attachments, clicking links, or responding.
> >
> >
> > 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.
> Done.
> >
> > > + 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).
> Done.
> >
> > > + 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].
> >
> I am a bit unclear here. Could you please elaborate on this ?
We can only handle constant CHREC_LEFT and CHREC_RIGHT, so you
can do the computation on wide_ints? That said, I believe
using chrec_apply is a bit of overkill for computing
base + const_vf * step ...
> On separate note, our further analysis revealed that the uniformity
> check is only done for the lanes in the first vector chunk.
What's a vector chunk?
But sure, you want to know whether { base, +, step } OP CST is
equal for iterations [0, VF - 1], [VF, 2*VF - 1], ... but since
SCEV cannot tell you that given the whole expression isn't affine
you have to prove this in other ways. But I think for division
and shift this is provable by induction but it depends on both
base and step.
> Ideally we should prove the uniformity for all the vector chunks
> which is what LLVM also does.
> https://github.com/llvm/llvm-project/commit/572cfa3fde5433c889b339e9cfa6dfaa23e5f2ee
> It looks like llvm does check the subsequent chunks as well implicitly by
> changing
> the chrec to reflect the VF as well in the step.
> i.e., if chrec is {0,+,1} then chrec is rewritten as {0,+,VF} and then
> check uniformity for all N in [0, VF-1]
> Do we need to go in that direction as well ?
> > > + }
> > > + 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'.
> Done.
> >
> > > + /* 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.
> The max_vf was used here in order to avoid redundant computation of uniformity
> checks for all vector factors. Rather find the uniformity for the maximum
> vector factor and cache the result to reuse while trying multiple VF.
> The reason being that if uniformity is true for the maximum possible
> vector factor then its true for lower, not vice versa.
> I have removed the caching here and try to recompute for each VF.
> >
> > > + 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
> Done.
> >
> > > 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)
>
>
>
>
>
> gcc/tree-vect-data-refs.cc | 121 ++++++++++++++++++++++++++++++++++++-
> gcc/tree-vect-slp.cc | 4 ++
> gcc/tree-vect-stmts.cc | 8 +++
> gcc/tree-vectorizer.h | 8 +++
> 4 files changed, 140 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
> index 3b27beb9c5b..0beeef5306c 100644
> --- a/gcc/tree-vect-data-refs.cc
> +++ b/gcc/tree-vect-data-refs.cc
> @@ -4818,12 +4818,105 @@ 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 gather_scatter_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 chrec1 = NULL_TREE, rhs1 = NULL_TREE, rhs2 = NULL_TREE;
> + tree_code op_code = ERROR_MARK;
> + tree op_type = TREE_TYPE (off);
> + gimple *def_stmt = SSA_NAME_DEF_STMT (off);
> + if (is_gimple_assign (def_stmt))
> + {
> + op_code = gimple_assign_rhs_code (def_stmt);
> + if (op_code == BIT_AND_EXPR || op_code == TRUNC_DIV_EXPR
> + || op_code == RSHIFT_EXPR)
line up || on new lines
> + {
> + rhs1 = gimple_assign_rhs1 (def_stmt);
> + rhs2 = gimple_assign_rhs2 (def_stmt);
> + chrec1 = analyze_scalar_evolution (loop, rhs1);
> + chrec1 = instantiate_parameters (loop, chrec1);
> + }
> + else
> + return false;
> + 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, "\n");
> + }
> + }
> + else
> + return false;
It's easier to follow
if (!is_gimple_assign (def_stmt))
return false;
> + 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)
!=
> + || TREE_CODE (rhs2) != INTEGER_CST)
> + return false;
this check should be done before doing the SCEV analysis
because it's cheaper
> + 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))
I'll note that in the end we want to handle different bases/steps,
not only to prove that the validation code is robust.
> + {
> + 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,
> + rhs2);
> + 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;
As said I'd like to see a more formal proof, given - as you say - we
have to prove this holds not only for [0, VF-1] but to all iterations.
> + }
> + 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,
> @@ -5151,6 +5244,32 @@ 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;
> + /* Check whether uniform gather load for all the vector lanes for
> + VF. */
> + HOST_WIDE_INT const_vf = 0;
> + unsigned HOST_WIDE_INT nunits;
> + if (TYPE_VECTOR_SUBPARTS (vectype).is_constant (&nunits))
Ah, so it's not the vectorization factor you are looking at. Please
use const_nunits then.
> + {
> + const_vf = (HOST_WIDE_INT) nunits;
Not sure why you need both.
> + }
> + if (const_vf == 0)
> + {
> + /* If not set then skip the uniforme check. */
?
> + return true;
> + }
> + bool uniform = false;
> + if (const_vf > 0)
?
> + {
> + if (dump_enabled_p ())
> + {
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "offset uniformity check at VF=%wd\n",
> + const_vf);
> + }
> + uniform = vect_check_gather_load_offset_uniform (loop, const_vf, off);
> + }
> + /* The information is stored in stm_vinfo for subsequent stages. */
> + info->offset_uniform = uniform;
> return true;
> }
>
> diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
> index 2250f6f74a1..315cd683fab 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;
> @@ -2815,6 +2816,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)
> @@ -2846,6 +2848,7 @@ out:
> {
> gs_scale = oprnd_info->first_gs_info.scale;
> gs_base = oprnd_info->first_gs_info.base;
> + gs_offset_uniform_p = oprnd_info->first_gs_info.offset_uniform;
> }
>
> if (is_a <bb_vec_info> (vinfo)
> @@ -3290,6 +3293,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 e991e861525..afd5109c9f7 100644
> --- a/gcc/tree-vect-stmts.cc
> +++ b/gcc/tree-vect-stmts.cc
> @@ -2168,6 +2168,10 @@ get_load_store_type (vec_info *vinfo, stmt_vec_info
> stmt_info,
> }
> else if (STMT_VINFO_GATHER_SCATTER_P (stmt_info))
> {
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_NOTE, vect_location,
> + "gs_offset_uniform_p is set to: %d\n",
> + SLP_TREE_GS_OFFSET_UNIFORM_P (slp_node));
> 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);
> @@ -2475,6 +2479,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;
> @@ -2489,6 +2495,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 0b646d6b29e..24a19aff606 100644
> --- a/gcc/tree-vectorizer.h
> +++ b/gcc/tree-vectorizer.h
> @@ -372,6 +372,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. */
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
> @@ -477,6 +479,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)
>
> @@ -615,6 +618,7 @@ public:
> /* All data dependences. Freed by free_dependence_relations, so not
> an auto_vec. */
> vec<ddr_p> ddrs;
> +
please avoid spurious whitespace changes
> };
>
> /* Vectorizer state common between loop and basic-block vectorization. */
> @@ -1693,6 +1697,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 accross VF. */
> + bool offset_uniform;
> +
likewise - no extra vertial space before }
> };
>
> /* Access Functions. */
>
--
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)
