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
Then transform uniform gather operations into optimized scalar load + broadcast
instead of emulated gather with N individual scalar loads.
BEFORE (Emulated Gather - 8 loads for VF=8):
for each lane i in 0..7:
offset[i] = BIT_FIELD_REF<offset_vector, i>
addr[i] = base + offset[i] * scale
result[i] = MEM[addr[i]]
result_vector = {result[0], ..., result[7]}
AFTER (Broadcast - 1 load):
offset = BIT_FIELD_REF<offset_vector, 0>
addr = base + offset * scale
scalar_val = MEM[addr]
result_vector = {scalar_val, scalar_val,...}
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
gs_offset_uniform_p.
(vect_get_and_check_slp_defs): Add a comment on why offset_uniform is
not compared.
(vect_build_slp_tree_2): Set gs_offset_uniform_p for single-lane gather
nodes.
* tree-vect-stmts.cc (get_load_store_type): Copy gather uniform
flag from gather_scatter_info to SLP nodes.
(vectorizable_load): Generate broadcast for uniform gather offsets.
* 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.
gcc/testsuite/ChangeLog:
* g++.dg/vect/vect-uniform-broadcast-and.c: New test.
* g++.dg/vect/vect-uniform-broadcast-neg-and.c: New test.
* g++.dg/vect/vect-uniform-broadcast-neg.c: New test.
* g++.dg/vect/vect-uniform-broadcast-op2-var.c: New test.
* g++.dg/vect/vect-uniform-broadcast.c: New test.
* gcc.dg/vect/vect-gather-uniform-slp-1.c: New test.
* gcc.dg/vect/vect-gather-uniform-slp-2.c: New test.
---
Hi Richard,
I have addressed all your comments. The following are the changes in this
v5 patch:
- Squashed the detection and transformation patches. The detection part
is unchanged from the approved v4 1/2 apart from the vertical space fix.
- Used SLP_TREE_GS_OFFSET_UNIFORM_P and reused (*ctor_elts)[0].value.
- For the test cases dropped -march=znver5, -O3, -std=c++11 and
-fdump-tree-vect-details, and used only -mprefer-vector-width=128 with x86 only
restriction. Also, added dumps check whether the loop is vectorized before other
scan dump checks.
Notes on the testcases:
- your two suggested loops do not form an SLP group, so I used
table[i & 4] and table[i & 8]. These form one SLP node with two
lanes, and no broadcast is used there. vect-gather-uniform-slp-1.c is a run
test.
- vect-uniform-broadcast.c, -neg.c and -op2-var.c i have used -mavx2 since
the loop has a conditional store, which needs a masked store. Loop was not
vectorized without mavx2.
- vect-uniform-broadcast-neg-and.c uses int instead of short. With short and
without -march=znver5 the loop was not vectorized.
- op2-var.c checks for the emulated gather by its BIT_FIELD_REF lane extracts
since there was no dump for the gather.
- The tests are still in g++.dg/vect. I can add a costmodel/x86_64 test if
you want.
Thanks,
Reshma
.../g++.dg/vect/vect-uniform-broadcast-and.c | 33 ++++
.../vect/vect-uniform-broadcast-neg-and.c | 40 +++++
.../g++.dg/vect/vect-uniform-broadcast-neg.c | 33 ++++
.../vect/vect-uniform-broadcast-op2-var.c | 41 +++++
.../g++.dg/vect/vect-uniform-broadcast.c | 31 ++++
.../gcc.dg/vect/vect-gather-uniform-slp-1.c | 41 +++++
.../gcc.dg/vect/vect-gather-uniform-slp-2.c | 39 +++++
gcc/tree-vect-data-refs.cc | 145 ++++++++++++++++++
gcc/tree-vect-slp.cc | 12 ++
gcc/tree-vect-stmts.cc | 93 +++++++----
gcc/tree-vectorizer.h | 8 +
11 files changed, 487 insertions(+), 29 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-and.c
create mode 100644 gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg-and.c
create mode 100644 gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg.c
create mode 100644 gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-op2-var.c
create mode 100644 gcc/testsuite/g++.dg/vect/vect-uniform-broadcast.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-2.c
diff --git a/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-and.c
b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-and.c
new file mode 100644
index 00000000000..98831be7b56
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-and.c
@@ -0,0 +1,33 @@
+/* { dg-do compile { target { x86_64-*-* i?86-*-* } } } */
+/* { dg-additional-options "-mprefer-vector-width=128" { target { x86_64-*-*
i?86-*-* } } } */
+/* Gather load table[i & 4]: mask 4 affects only bit 2, so (4 & (N - 1)) == 0
+ when N = 4. -mprefer-vector-width=128 encourages 4-wide int vectors on
+ x86 so i & 4 is uniform per vector chunk and broadcast is possible. */
+
+#include <stdio.h>
+
+#define N 32
+
+int block_values[8] = {10, 20, 30, 40, 50, 60, 70, 80};
+int result[N];
+
+void
+tile_fill (int *__restrict out, int *__restrict table, int n,
+ int *__restrict in)
+{
+ for (int i = 0; i < n; i++)
+ {
+ out[i] = table[i & 4];
+ in[i] = out[i] + 10;
+ }
+}
+
+void
+use_tile_fill (void)
+{
+ tile_fill (result, block_values, N, result);
+ __asm__ volatile ("" : : "r" (result) : "memory");
+}
+
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* { dg-final { scan-tree-dump "computing cost for broadcast" "vect" } } */
diff --git a/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg-and.c
b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg-and.c
new file mode 100644
index 00000000000..e28f4fb874e
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg-and.c
@@ -0,0 +1,40 @@
+/* { dg-do compile { target { x86_64-*-* i?86-*-* } } } */
+/* Negative test: the offset must NOT be reported as uniform for ANY candidate
+ vector size the vectorizer tries.
+
+ NOTE: a right-shift offset (i >> k) cannot be used for a negative test here.
+ The vectorizer analyzes every candidate vector size (32, 16, 8, 4, 2), and
+ for a right shift the offset is uniform per chunk iff N - 1 < 2^k. At the
+ smallest candidate N = 2 this is 1 < 2^k, which holds for every k >= 1, so
+ *some* candidate always reports "uniform" and scan-tree-dump-not would fail.
+
+ For BIT_AND the offset is uniform iff (k & (N - 1)) == 0. With an odd mask
+ (k = 1) bit 0 is set, and N - 1 has bit 0 set for every N >= 2, so the
+ offset is non-uniform for ALL candidate vector sizes. The broadcast
+ optimization must never trigger. */
+
+#include <stdio.h>
+
+#define N 512
+
+int block_values[64];
+int result[N];
+
+void
+tile_fill (int *__restrict out, int *__restrict table, int n)
+{
+ for (int i = 0; i < n; i++)
+ out[i] = table[i & 1];
+}
+
+void
+use_tile_fill (void)
+{
+ tile_fill (result, block_values, N);
+ __asm__ volatile ("" : : "r" (result) : "memory");
+}
+
+/* The offset is not uniform across the vector lanes, so no broadcast should be
+ reported. */
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* { dg-final { scan-tree-dump-not "computing cost for broadcast" "vect" } } */
diff --git a/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg.c
b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg.c
new file mode 100644
index 00000000000..d6a98dc38aa
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-neg.c
@@ -0,0 +1,33 @@
+/* { dg-do compile { target { x86_64-*-* i?86-*-* } } } */
+/* The conditional store needs a masked store, so enable AVX2. */
+/* { dg-additional-options "-mavx2 -mprefer-vector-width=128" } */
+/* Negative test: the loop starts at i = 1, so the SCEV of i is {1, +, 1}.
+ A non-zero base B is only accepted when B is a multiple of the number of
+ vector lanes, and 1 is not. A vector chunk can then span two bitset
+ words (e.g. i = 61..64), so the word offset i / 64 is not uniform across
+ the lanes and no broadcast must be generated. */
+#include <bitset>
+#include <vector>
+class Foo
+{
+ public:
+ void fun (unsigned boardsize, bool check);
+ std::vector<int> m_mcowner;
+};
+void Foo::fun (unsigned boardsize, bool check)
+{
+ std::bitset<21*21> blacksq;
+ __asm__ ("" : "+g" (blacksq));
+ for (int i = 0; i < boardsize; i++) {
+ if (i % 2 == 0)
+ blacksq[i] = true;
+ }
+ unsigned int i = 1;
+ do {
+ if (blacksq[i])
+ m_mcowner[i]++;
+ } while (++i < blacksq.size ());
+}
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* { dg-final { scan-tree-dump-not "computing cost for broadcast" "vect" } } */
+
diff --git a/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-op2-var.c
b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-op2-var.c
new file mode 100644
index 00000000000..bbbf46c4163
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast-op2-var.c
@@ -0,0 +1,41 @@
+/* { dg-do compile { target { x86_64-*-* i?86-*-* } } } */
+/* The conditional store needs a masked store, so enable AVX2. */
+/* { dg-additional-options "-mavx2 -mprefer-vector-width=128" } */
+/* Gather load with PLUS (hi, lo). The second operand of the offset PLUS is a
+ variable, hence the offset is not uniform and no broadcast is generated.
+ The inner loop still vectorizes as a normal gather. */
+
+#include <vector>
+
+class Foo
+{
+ public:
+ void fun (unsigned boardsize);
+ std::vector<int> m_mcowner;
+};
+
+void
+Foo::fun (unsigned boardsize)
+{
+ unsigned nwords = (21 * 21 + 63) / 64 + 2;
+ std::vector<unsigned long> words (nwords, 0);
+ __asm__ ("" : "+g" (words));
+ for (unsigned i = 0; i < boardsize; i++)
+ if (i % 2 == 0)
+ words[i / 64] |= 1UL << (i % 64);
+ unsigned int i = 0;
+ do
+ {
+ unsigned hi = i / 64;
+ unsigned lo = i & 1u;
+ /* the second operand is ensured to be loop-varying by the SCEV path */
+ if (words[hi + lo])
+ m_mcowner[i]++;
+ }
+ while (++i < 21 * 21);
+}
+
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* The emulated gather extracts each lane of the offset vector. */
+/* { dg-final { scan-tree-dump "BIT_FIELD_REF <vect_" "vect" } } */
+/* { dg-final { scan-tree-dump-not "computing cost for broadcast" "vect" } } */
diff --git a/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast.c
b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast.c
new file mode 100644
index 00000000000..92c4eb7cff4
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-uniform-broadcast.c
@@ -0,0 +1,31 @@
+/* { dg-do compile { target { x86_64-*-* i?86-*-* } } } */
+/* The conditional store needs a masked store, so enable AVX2. */
+/* { dg-additional-options "-mavx2 -mprefer-vector-width=128" } */
+/* Test case for generating uniform broadcast instead of gather
+ when there is uniform value accross the vector lane */
+#include <bitset>
+#include <vector>
+class Foo
+{
+ public:
+ void fun (unsigned boardsize, bool check);
+ std::vector<int> m_mcowner;
+};
+void Foo::fun( unsigned boardsize, bool check)
+{
+ std::bitset<21*21> blacksq;
+ __asm__ ("" : "+g" (blacksq));
+ for (int i = 0; i < boardsize; i++) {
+ if(i%2 == 0)
+ blacksq[i] = true;
+ }
+ unsigned int i = 0;
+ do{
+ if (blacksq[i])
+ m_mcowner[i]++;
+ }while(++i < blacksq.size());
+
+}
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* { dg-final { scan-tree-dump "computing cost for broadcast" "vect" } } */
+
diff --git a/gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-1.c
b/gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-1.c
new file mode 100644
index 00000000000..4f8b1bc716a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-1.c
@@ -0,0 +1,41 @@
+#include "tree-vect.h"
+
+#define N 64
+
+int table[16] = { 1, 2, 3, 4, 5, 6, 7, 8,
+ 9, 10, 11, 12, 13, 14, 15, 16 };
+int y[N * 2];
+
+/* Two gathers from the same base that form one SLP group. i & 4 and
+ i & 8 are each uniform per 4-lane chunk, but the group's vector
+ interleaves the offsets of both statements, so it must not be turned
+ into a broadcast. */
+
+void __attribute__((noipa))
+f (int *restrict y, int *restrict t, int n)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ y[i * 2] = t[i & 4] + 1;
+ y[i * 2 + 1] = t[i & 8] + 2;
+ }
+}
+
+int
+main (void)
+{
+ check_vect ();
+
+ f (y, table, N);
+#pragma GCC novector
+ for (int i = 0; i < N; ++i)
+ if (y[i * 2] != table[i & 4] + 1
+ || y[i * 2 + 1] != table[i & 8] + 2)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Loop contains only SLP stmts" "vect" } } */
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* { dg-final { scan-tree-dump-not "computing cost for broadcast" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-2.c
b/gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-2.c
new file mode 100644
index 00000000000..25bf7888f05
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-gather-uniform-slp-2.c
@@ -0,0 +1,39 @@
+#include "tree-vect.h"
+
+#define N 64
+
+int table[16] = { 1, 2, 3, 4, 5, 6, 7, 8,
+ 9, 10, 11, 12, 13, 14, 15, 16 };
+int y[N];
+
+/* Two gathers with offsets i & 4 and (i + 1) & 4, i stepping by two.
+ They are not uniform (the step is two) and are not grouped; this
+ checks that the result is correct. */
+
+void __attribute__((noipa))
+f (int *restrict y, int *restrict t, int n)
+{
+ for (int i = 0; i < n; i += 2)
+ {
+ y[i] = t[i & 4];
+ y[i + 1] = t[(i + 1) & 4];
+ }
+}
+
+int
+main (void)
+{
+ check_vect ();
+
+ f (y, table, N);
+#pragma GCC novector
+ for (int i = 0; i < N; ++i)
+ if (y[i] != table[i & 4])
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Loop contains only SLP stmts" "vect" } } */
+/* { dg-final { scan-tree-dump "loop vectorized" "vect" } } */
+/* { dg-final { scan-tree-dump-not "computing cost for broadcast" "vect" } } */
diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
index 23235875fa2..d3da0bf081f 100644
--- a/gcc/tree-vect-data-refs.cc
+++ b/gcc/tree-vect-data-refs.cc
@@ -4704,6 +4704,140 @@ 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
@@ -5036,6 +5170,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..447bad5fef6 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;
@@ -11237,18 +11241,39 @@ vectorizable_load (vec_info *vinfo,
unsigned HOST_WIDE_INT const_nunits = nunits.to_constant ();
if (costing_p)
{
- /* For emulated gathers N offset vector element
- offset add is consumed by the load). */
- inside_cost = record_stmt_cost (cost_vec, 1, vec_deconstruct,
- slp_node, 0, vect_body);
- /* N scalar loads plus gathering them into a
- vector. */
- inside_cost
- = record_stmt_cost (cost_vec, const_nunits, scalar_load,
- slp_node, 0, vect_body);
- inside_cost
- = record_stmt_cost (cost_vec, 1, vec_construct,
- slp_node, 0, vect_body);
+ if (SLP_TREE_GS_OFFSET_UNIFORM_P (slp_node))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "computing cost for broadcast\n");
+ /* Broadcast optimization: 1 extract + 1 load
+ + 1 broadcast. */
+ inside_cost = record_stmt_cost (cost_vec, 1,
+ vec_to_scalar, slp_node,
+ 0, vect_body);
+ inside_cost += record_stmt_cost (cost_vec, 1, scalar_load,
+ slp_node, 0, vect_body);
+ inside_cost += record_stmt_cost (cost_vec, 1,
+ scalar_to_vec, slp_node,
+ 0, vect_body);
+ }
+ else
+ {
+
+ /* For emulated gathers N offset vector element
+ offset add is consumed by the load). */
+ inside_cost = record_stmt_cost (cost_vec, 1,
+ vec_deconstruct, slp_node,
+ 0, vect_body);
+ /* N scalar loads plus gathering them into a
+ vector. */
+ inside_cost
+ = record_stmt_cost (cost_vec, const_nunits, scalar_load,
+ slp_node, 0, vect_body);
+ inside_cost
+ = record_stmt_cost (cost_vec, 1, vec_construct,
+ slp_node, 0, vect_body);
+ }
continue;
}
tree offset_vectype = TREE_TYPE (vec_offsets[0]);
@@ -11268,23 +11293,33 @@ vectorizable_load (vec_info *vinfo,
tree ltype = build_aligned_type (TREE_TYPE (vectype), align);
for (unsigned k = 0; k < const_nunits; ++k)
{
- tree boff = size_binop (MULT_EXPR, TYPE_SIZE (idx_type),
- bitsize_int (k + elt_offset));
- tree idx = gimple_build (&stmts, BIT_FIELD_REF, idx_type,
- vec_offset, TYPE_SIZE (idx_type),
- boff);
- idx = gimple_convert (&stmts, sizetype, idx);
- idx = gimple_build (&stmts, MULT_EXPR, sizetype, idx, scale);
- tree ptr = gimple_build (&stmts, PLUS_EXPR,
- TREE_TYPE (dataref_ptr),
- dataref_ptr, idx);
- ptr = gimple_convert (&stmts, ptr_type_node, ptr);
- tree elt = make_ssa_name (TREE_TYPE (vectype));
- tree ref = build2 (MEM_REF, ltype, ptr,
- build_int_cst (ref_type, 0));
- new_stmt = gimple_build_assign (elt, ref);
- gimple_set_vuse (new_stmt, gimple_vuse (gsi_stmt (*gsi)));
- gimple_seq_add_stmt (&stmts, new_stmt);
+ tree elt;
+ /* If all lanes are uniform then generate broadcast otherwise
+ emulated gathers. */
+ if (SLP_TREE_GS_OFFSET_UNIFORM_P (slp_node) && k > 0)
+ elt = (*ctor_elts)[0].value;
+ else
+ {
+
+ tree boff = size_binop (MULT_EXPR, TYPE_SIZE (idx_type),
+ bitsize_int (k + elt_offset));
+ tree idx = gimple_build (&stmts, BIT_FIELD_REF, idx_type,
+ vec_offset, TYPE_SIZE (idx_type),
+ boff);
+ idx = gimple_convert (&stmts, sizetype, idx);
+ idx = gimple_build (&stmts, MULT_EXPR, sizetype, idx,
+ scale);
+ tree ptr = gimple_build (&stmts, PLUS_EXPR,
+ TREE_TYPE (dataref_ptr),
+ dataref_ptr, idx);
+ ptr = gimple_convert (&stmts, ptr_type_node, ptr);
+ elt = make_ssa_name (TREE_TYPE (vectype));
+ tree ref = build2 (MEM_REF, ltype, ptr,
+ build_int_cst (ref_type, 0));
+ new_stmt = gimple_build_assign (elt, ref);
+ gimple_set_vuse (new_stmt, gimple_vuse (gsi_stmt (*gsi)));
+ gimple_seq_add_stmt (&stmts, new_stmt);
+ }
CONSTRUCTOR_APPEND_ELT (ctor_elts, NULL_TREE, elt);
}
gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
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
