On Tue, 14 Jul 2026, [email protected] wrote: > From: Reshma Roy <[email protected]> > > Implement analysis using SCEV information to detect when gather/scatter > offset expressions evaluate to the same value for all vector lanes within > each vector iteration. For example, if VF=8, iterations 0-7 of > "i >> 6" all evaluate to 0, enabling optimization to broadcast. The uniformity > information is propagated to SLP nodes for use in the transformation phase. > > Example: For "M[i >> 6]" with VF=8: > - Iterations 0-7: i >> 6 = 0 (uniform) > - Iterations 64-71: i >> 6 = 1 (uniform) > Here we can optimize each vector iteration to load once + broadcast > > 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}.
Review below - for future re-spins please post without the previous reviews quoted inbetween. > 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)); > } vertical space missing > +/* 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); with outer loop vectorization 'loop' might not be correct, in general you'd want to analyze rhs1 with respect to the loop it is defined in, thus add if (TREE_CODE (rhs1) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (rhs1)) return false; chrec1 = analyze_scalar_evolution (gimple_bb (SSA_NAME_DEF_STMT (rhs1))->loop_father, rhs1)); > + chrec1 = instantiate_parameters (loop, chrec1); and this correctly interprets it with respect to the outer loop. > + 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; Note that there should not be any evolution in the inner loop for outer loop vectorization, so CHREC_VARIABLE should be loop->num > + 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)) while it could be argued the integer_onep requirement for scev_step is OK please eliminate the initial value requirement. > + { > + if (dump_enabled_p ()) > + dump_printf_loc (MSG_NOTE, vect_location, > + "returning because of non-zero base or" > + "non-one step\n"); that's a non-informative message, better "cannot determine uniformity 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; you have already checked this. > + /* 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); please compute this only for RSHIFT_EXPR > + 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, " uniform across %d vector lanes, > + "broadcast optimization possible\n", > + (int) const_nunits); > + return is_uniform; > +} > > /* Return true if a non-affine read or write in STMT_INFO is suitable for a > gather load or scatter store with VECTYPE. Describe the operation in > *INFO > if so. If it is suitable and ELSVALS is nonzero store the supported else > values in the vector it points to. */ > - > 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; Do we handle gathers in outer loop vectorization? > + if (TYPE_VECTOR_SUBPARTS (vectype).is_constant (&nunits) && nunits > 0) nunits is never 0, but I suppose for nunits == 1 it's always uniform (but maybe not too useful) > + { > + if (dump_enabled_p ()) > + { > + dump_printf_loc (MSG_NOTE, vect_location, > + "offset uniformity check at vector nunits=%wd\n", > + nunits); > + } please move this dump to vect_check_gather_load_offset_uniform. > + 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; I think uniformity breaks down once you have a SLP group of gathers, thus blindly using oprnd_info->first_gs_info.offset_uniform here looks wrong. Either gate on SLP_TREE_LANES / group_size == 1 or think of what exactly happens. vect_get_and_check_slp_defs compares gs_info.base and gs_info.scale, it at least needs a comment on why we do not compare gs_info.offset_uniform (the whole group could be demoted, so using first_gs_info would be wrong and we'd instead add a field to oprnd_info to store the "combined" value). > } > > 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)); This just adds needless verbosity > 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 > > -- Richard Biener <[email protected]> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
