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
v3 changes
- Prove offset uniformity with a direct formula instead of a per-lane loop.
Currently handled RSHIFT_EXPR, TRUNKC_DIV_EXPR and BIT_AND_EXPR.
- Rename variables to reflect vector lane count and drop redundant checks.
- Simplify the control flow and use early returns.
- Fix comment wording and remove stray whitespace changes.
TODO: Handle arbitrary base/step beyond {0,+,1}.
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, general base and step, were addressed and
the patch is updated. The detailed description are added inline.
Bootstrapped and tested on x86_64
Original Message-----
> From: Richard Biener <[email protected]>
> Sent: Tuesday, June 30, 2026 5:55 PM
> To: Roy, Reshma <[email protected]>
> Cc: [email protected]; Kumar, Venkataramanan
> <[email protected]>
> Subject: Re: [PATCH v2 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 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.
The logic is changed such that we use arithmetic equations to prove uniformity
for
rshift, trunc_di and bit_and.
>
> > Ideally we should prove the uniformity for all the vector chunks which
> > is what LLVM also does.
> > https://github.com/llvm/llvm-project/commit/572cfa3fde5433c889b339e9cf
> > a6dfaa23e5f2ee 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
Done.
>
> > + {
> > + 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;
>
Done.
> > + 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)
>
> !=
Done.
>
> > + || TREE_CODE (rhs2) != INTEGER_CST)
> > + return false;
>
> this check should be done before doing the SCEV analysis because it's cheaper
>
Done.
> > + 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.
>
Currently its not done, its in the TODO.
> > + {
> > + 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.
We have a formal proof now and its described in the patch.
>
> > + }
> > + 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.
>
We need to know the number of vector lanes chosen and check uniformity for
each. Changed
the name.
> > + {
> > + const_vf = (HOST_WIDE_INT) nunits;
>
> Not sure why you need both.
>
Removed redundant checks.
> > + }
> > + 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.
>
Done.
> > + 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
>
Done.
> > };
> >
> > /* 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 }
>
Done.
> > };
> >
> > /* 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)
Thanks,
Reshma Roy
gcc/tree-vect-data-refs.cc | 136 ++++++++++++++++++++++++++++++++++++-
gcc/tree-vect-slp.cc | 4 ++
gcc/tree-vect-stmts.cc | 8 +++
gcc/tree-vectorizer.h | 8 +++
4 files changed, 155 insertions(+), 1 deletion(-)
diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
index 0e0754769ae..457b04f60cc 100644
--- a/gcc/tree-vect-data-refs.cc
+++ b/gcc/tree-vect-data-refs.cc
@@ -4818,12 +4818,129 @@ 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 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 {0,+,1} 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. */
+static bool
+vect_check_gather_load_offset_uniform (class loop *loop,
+ HOST_WIDE_INT const_nunits,
+ 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;
+ 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;
+ chrec1 = analyze_scalar_evolution (loop, 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))
+ return false;
+ tree scev_base = CHREC_LEFT (chrec1);
+ tree scev_step = CHREC_RIGHT (chrec1);
+ /* 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;
+ }
+ if (TREE_CODE (scev_base) != INTEGER_CST
+ && TREE_CODE (scev_step) != INTEGER_CST)
+ 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));
+ wide_int pow2_k = wi::lshift (wi::one (prec), rhs_wi);
+ wide_int vf_m1 = wi::uhwi (const_nunits - 1, prec);
+ bool is_uniform = false;
+ if (op_code == RSHIFT_EXPR)
+ {
+ 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 vector lanes=%d, "
+ "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. */
-
bool
vect_check_gather_scatter (stmt_vec_info stmt_info, tree vectype,
loop_vec_info loop_vinfo,
@@ -5151,6 +5268,23 @@ 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 across each individual vector number
+ of lanes iterations. */
+ unsigned HOST_WIDE_INT nunits;
+ bool uniform = false;
+ if (TYPE_VECTOR_SUBPARTS (vectype).is_constant (&nunits) && nunits > 0)
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "offset uniformity check at vector nunits=%wd\n",
+ 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 ff11b392305..07aff94f822 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;
@@ -2818,6 +2819,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)
@@ -2849,6 +2851,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)
@@ -3293,6 +3296,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 76e24b2c169..c1776f78f53 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 2e4756926f2..9cc4494a1d9 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -372,6 +372,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
@@ -477,6 +480,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)
@@ -1700,6 +1704,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. */
--
2.34.1
