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