expand_vector_divmod only used the power-of-two shift path for positive
divisors; for a negative divisor it cleared use_pow2 and fell back to the
multiply-high sequence. The scalar expand_divmod (expmed.cc) instead
computes op0 / |d| with the round-toward-zero shift idiom and negates the
quotient when d < 0, since x / -2^k == -(x / 2^k). Do the same for vectors.
The analysis loop now accepts a divisor whose absolute value is a power of
two. For TRUNC_DIV it records the sign, which must be the same in every
lane, in negate_p, and negates the quotient when the divisor was negative;
without a vector negate pattern that expands as 0 - q. TRUNC_MOD reuses the
mask path unchanged, for any mix of signs, since x % d == x % |d|. A
mixed-sign division, a target that can neither negate nor subtract vectors,
or the INT_MIN-magnitude divisor (log2 == prec - 1, which has no positive
representation for the shift idiom) fall back to the existing multiply-high
path.
The positive-signed and unsigned paths are unchanged: for those lanes
this_neg is 0, wi::exact_log2 matches the previous tree_log2, and the disable
conditions reduce to the originals.
gcc/ChangeLog:
* tree-vect-generic.cc (expand_vector_divmod): Handle division by
a negative power of two.
gcc/testsuite/ChangeLog:
* gcc.c-torture/execute/vector-div-neg-pow2.c: New test.
* gcc.dg/vect/veclower/vec-div-neg-pow2.c: New test.
Signed-off-by: Igor Shevlyakov <[email protected]>
---
Bootstrapped and regtested on x86_64-pc-linux-gnu (-m32/-m64), no new
regressions.
.../execute/vector-div-neg-pow2.c | 92 +++++++++++++++++++
.../gcc.dg/vect/veclower/vec-div-neg-pow2.c | 38 ++++++++
gcc/tree-vect-generic.cc | 58 ++++++++++--
3 files changed, 179 insertions(+), 9 deletions(-)
create mode 100644 gcc/testsuite/gcc.c-torture/execute/vector-div-neg-pow2.c
create mode 100644 gcc/testsuite/gcc.dg/vect/veclower/vec-div-neg-pow2.c
diff --git a/gcc/testsuite/gcc.c-torture/execute/vector-div-neg-pow2.c
b/gcc/testsuite/gcc.c-torture/execute/vector-div-neg-pow2.c
new file mode 100644
index 00000000000..ece02fbb54c
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/vector-div-neg-pow2.c
@@ -0,0 +1,92 @@
+/* Signed vector division and modulus by negative powers of two. */
+
+typedef int v4si __attribute__ ((vector_size (16)));
+typedef short v8hi __attribute__ ((vector_size (16)));
+typedef long long v2di __attribute__ ((vector_size (16)));
+
+#define SI_MIN (-__INT_MAX__ - 1)
+#define DI_MIN (-__LONG_LONG_MAX__ - 1)
+
+static const long long vals[]
+ = { 0, 1, -1, 2, -2, 7, -7, 31, -31, 32, -32, 33, -33, 1000, -1000,
+ 0x7fff, -0x8000, __INT_MAX__, SI_MIN, __LONG_LONG_MAX__, DI_MIN,
+ -1234567890123LL };
+#define NVALS (sizeof (vals) / sizeof (vals[0]))
+
+__attribute__ ((noipa)) static long long
+sdiv (long long x, long long d)
+{
+ return x / d;
+}
+
+__attribute__ ((noipa)) static long long
+smod (long long x, long long d)
+{
+ return x % d;
+}
+
+/* Divide and take the remainder of rotations of VALS by the constant
+ vector {...}, and check every lane against the scalar result. X / -1
+ is undefined for the minimum value TMIN, so that lane gets 0 instead. */
+#define TEST(T, VT, N, TMIN, NAME, ...)
\
+__attribute__ ((noipa)) static VT \
+q##NAME (VT x) \
+{ \
+ return x / (VT) { __VA_ARGS__ }; \
+} \
+__attribute__ ((noipa)) static VT \
+r##NAME (VT x) \
+{ \
+ return x % (VT) { __VA_ARGS__ }; \
+} \
+static void \
+check##NAME (void) \
+{ \
+ static const T d[N] = { __VA_ARGS__ }; \
+ for (unsigned j = 0; j < NVALS; j++) \
+ { \
+ VT x, q, r; \
+ for (int i = 0; i < N; i++) \
+ { \
+ x[i] = (T) vals[(i + j) % NVALS]; \
+ if (d[i] == -1 && x[i] == TMIN) \
+ x[i] = 0; \
+ } \
+ q = q##NAME (x); \
+ r = r##NAME (x); \
+ for (int i = 0; i < N; i++) \
+ if (q[i] != (T) sdiv (x[i], d[i]) \
+ || r[i] != (T) smod (x[i], d[i])) \
+ __builtin_abort (); \
+ } \
+}
+
+TEST (int, v4si, 4, SI_MIN, si1, -32, -32, -32, -32)
+TEST (int, v4si, 4, SI_MIN, si2, -2, -4, -8, -16)
+TEST (int, v4si, 4, SI_MIN, si3, -2, -2, -2, -(1 << 30))
+TEST (int, v4si, 4, SI_MIN, si4, -4, 4, -4, 4)
+TEST (int, v4si, 4, SI_MIN, si5, -4, -2, -1, -8)
+TEST (int, v4si, 4, SI_MIN, si6, SI_MIN, SI_MIN, SI_MIN, SI_MIN)
+TEST (short, v8hi, 8, -0x8000, hi1, -8, -8, -8, -8, -8, -8, -8, -8)
+TEST (short, v8hi, 8, -0x8000, hi2, -2, -4, -8, -16, -32, -64, -128,
+ -0x4000)
+TEST (long long, v2di, 2, DI_MIN, di1, -8, -8)
+TEST (long long, v2di, 2, DI_MIN, di2, -2, -(1LL << 62))
+TEST (long long, v2di, 2, DI_MIN, di3, DI_MIN, DI_MIN)
+
+int
+main (void)
+{
+ checksi1 ();
+ checksi2 ();
+ checksi3 ();
+ checksi4 ();
+ checksi5 ();
+ checksi6 ();
+ checkhi1 ();
+ checkhi2 ();
+ checkdi1 ();
+ checkdi2 ();
+ checkdi3 ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/vect/veclower/vec-div-neg-pow2.c
b/gcc/testsuite/gcc.dg/vect/veclower/vec-div-neg-pow2.c
new file mode 100644
index 00000000000..7d4757991d5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/veclower/vec-div-neg-pow2.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_shift } */
+/* { dg-require-effective-target vect128 } */
+
+/* Division by a negative power of two is a shift and a negation, and the
+ remainder a mask, as for a positive divisor; no multiply-high. */
+
+typedef int v4si __attribute__ ((vector_size (16)));
+typedef short v8hi __attribute__ ((vector_size (16)));
+
+v4si
+f1 (v4si x)
+{
+ return x / -32;
+}
+
+v8hi
+f2 (v8hi x)
+{
+ return x / -8;
+}
+
+v4si
+f3 (v4si x)
+{
+ return x % -32;
+}
+
+v4si
+f4 (v4si x)
+{
+ return x % (v4si) { -4, 4, -4, 4 };
+}
+
+/* { dg-final { scan-tree-dump-not " h\\* " "veclower21" } } */
+/* Targets with vector division keep it. */
+/* { dg-final { scan-tree-dump-times " = -_| / \{ -" 2 "veclower21" } } */
diff --git a/gcc/tree-vect-generic.cc b/gcc/tree-vect-generic.cc
index 5f9086615e3..79d7bd99550 100644
--- a/gcc/tree-vect-generic.cc
+++ b/gcc/tree-vect-generic.cc
@@ -701,7 +701,11 @@ expand_vector_divmod (gimple_stmt_iterator *gsi, tree
type, tree op0,
{
bool use_pow2 = true;
bool has_vector_shift = true;
+ bool has_vector_negate = true;
bool use_abs_op1 = false;
+ /* For the power-of-two path: 1 if the quotient is negated (all divisors
+ are negative), 0 if not, -1 if undetermined. */
+ int negate_p = -1;
int mode = -1, this_mode;
int pre_shift = -1, post_shift;
unsigned int nunits = nunits_for_known_piecewise_op (type);
@@ -725,6 +729,17 @@ expand_vector_divmod (gimple_stmt_iterator *gsi, tree
type, tree op0,
|| !can_implement_p (op, TYPE_MODE (type)))
has_vector_shift = false;
+ /* expand_unop falls back to 0 - x for a missing vector negation. */
+ op = optab_for_tree_code (NEGATE_EXPR, type, optab_default);
+ if (op == unknown_optab
+ || !can_implement_p (op, TYPE_MODE (type)))
+ {
+ op = optab_for_tree_code (MINUS_EXPR, type, optab_default);
+ if (op == unknown_optab
+ || !can_implement_p (op, TYPE_MODE (type)))
+ has_vector_negate = false;
+ }
+
/* Analysis phase. Determine if all op1 elements are either power
of two and it is possible to expand it using shifts (or for remainder
using masking). Additionally compute the multiplicative constants
@@ -740,16 +755,35 @@ expand_vector_divmod (gimple_stmt_iterator *gsi, tree
type, tree op0,
pre_shifts[i] = 0;
post_shifts[i] = 0;
mulc[i] = 0;
- if (use_pow2
- && (!integer_pow2p (cst) || tree_int_cst_sgn (cst) != 1))
- use_pow2 = false;
if (use_pow2)
{
- shifts[i] = tree_log2 (cst);
- if (shifts[i] != shifts[0]
- && code == TRUNC_DIV_EXPR
- && !has_vector_shift)
+ /* Divide by a negative power of two as by its absolute value and
+ negate the quotient, as expand_divmod does. The quotient needs
+ all elements to have the same sign; the remainder does not
+ depend on the sign, as x % d == x % -d. INT_MIN is excluded,
+ as its magnitude does not fit. */
+ int this_neg = 0;
+ wide_int w = wi::to_wide (cst);
+ if (sign_p == SIGNED && wi::neg_p (w))
+ {
+ this_neg = code == TRUNC_DIV_EXPR;
+ w = wi::neg (w);
+ }
+ int log2 = wi::exact_log2 (w);
+ if (log2 < 0
+ || (sign_p == SIGNED && log2 >= prec - 1)
+ || (this_neg && !has_vector_negate)
+ || (negate_p >= 0 && negate_p != this_neg))
use_pow2 = false;
+ else
+ {
+ negate_p = this_neg;
+ shifts[i] = log2;
+ if (shifts[i] != shifts[0]
+ && code == TRUNC_DIV_EXPR
+ && !has_vector_shift)
+ use_pow2 = false;
+ }
}
if (mode == -2)
continue;
@@ -952,7 +986,8 @@ expand_vector_divmod (gimple_stmt_iterator *gsi, tree type,
tree op0,
else if (addend != NULL_TREE)
{
/* t1 = op0 + addend;
- q = t1 >> shift; */
+ q = t1 >> shift;
+ and, for a negative power-of-two divisor, q = -q. */
op = optab_for_tree_code (PLUS_EXPR, type, optab_default);
if (op != unknown_optab
&& can_implement_p (op, TYPE_MODE (type)))
@@ -960,7 +995,12 @@ expand_vector_divmod (gimple_stmt_iterator *gsi, tree
type, tree op0,
cur_op = gimplify_build2 (gsi, PLUS_EXPR, type, op0, addend);
cur_op = add_shift (gsi, type, cur_op, shifts, RSHIFT_EXPR);
if (cur_op != NULL_TREE)
- return cur_op;
+ {
+ if (negate_p == 1)
+ cur_op = gimplify_build1 (gsi, NEGATE_EXPR, type,
+ cur_op);
+ return cur_op;
+ }
}
}
}
--
2.55.0
