From: Christopher Bazley <[email protected]>
PR middle-end/125767
When the magnitude of the divisor is known to be bigger
than that of the dividend, the output quotient should be 1
when divisor and dividend have the same sign or -1
when they have opposite signs.
Previously, can_div_away_from_zero_p was overreliant on
can_div_trunc_p: if can_div_trunc_p returned a failure
indication then can_div_away_from_zero_p did likewise.
This matters because can_div_away_from_zero_p is commonly
used to answer questions such as "How many registers does
this value occupy?" If the register has a scalable vector
type, then the answer should be 1 if the number of bits
occupied by the value is known to be not greater than
the minimum number of bits in the vector type (as well as
if the number of bits occupied by the value is known to be
smaller). Previously, can_div_away_from_zero_p had to be
used with care to avoid wrongly concluding that a value of
type V16QI would not fit in a register of type VNx16QI.
That could cause selection of inefficient instruction
sequences or even an ICE in cases where V8QI in VNx16QI
behaved as expected.
Because polynomial division truncated toward zero can
fail to produce a constant quotient in cases where
polynomial division rounded away from zero can produce a
constant quotient, it is not sufficient for the
implementation of can_div_away_from_zero_p to simply adjust
the quotient produced by can_div_trunc_p.
can_div_trunc_p requires |b * Q| <= |a| whereas
can_div_away_from_zero_p requires |b * Q| >= |a|. The
latter can be proven in cases where the former cannot.
For example, when a = 16 + 0i and b = 16 + 16i, |b * Q|
cannot be smaller than |a| unless Q = 0, which would
violate a common requirement that |a - b * Q| < |b|
(because |a| >= 16 and |b| >= 16). In contrast, |b * Q|
is bigger than |a| if Q > 1 or i > 0. Crucially, it's
impossible to know the value of i at compile time, so
can_div_trunc_p must conservatively return false.
Another way of looking at it is:
Q = (16 + 0i) / (16 + 16i)
= 16 / (16 + 16i)
= 1 / (1 + i)
which is not "some constant Q" that these functions must
find in order to return true; however, we can be sure that
whatever the unknowable value of 1 / (1 + i) is, it lies
within the range 0 < Q <= 1. We cannot know whether that
answer should be truncated to zero, but we can know that
it should be rounded to one.
gcc/ChangeLog:
* poly-int.h (can_div_away_from_zero_p):
Exit early if |a| <= |b| instead of calling
can_div_trunc_p and returning false if it
returned false.
gcc/testsuite/ChangeLog:
* gcc.dg/plugin/poly-int-tests.h: New test cases.
Co-authored-by: Richard Sandiford <[email protected]>
---
gcc/poly-int.h | 40 ++++++++++++++++++
gcc/testsuite/gcc.dg/plugin/poly-int-tests.h | 44 ++++++++++++++++++++
2 files changed, 84 insertions(+)
diff --git a/gcc/poly-int.h b/gcc/poly-int.h
index cacd1c21443c..01bc5cc5c170 100644
--- a/gcc/poly-int.h
+++ b/gcc/poly-int.h
@@ -2420,6 +2420,46 @@ inline typename if_nonpoly<Cq, bool>::type
can_div_away_from_zero_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
Cq *quotient)
{
+ /* If both a and b have fixed signs, test 0 < |a| <= |b|. (2) is then
+ satisfied with |Q| == 1. Choose Q as 1 or -1 such that a and b * Q
+ have the same sign. Together, these two conditions guarantee that
+ |b * Q - a| = |b * Q| - |a|. Then:
+
+ |r| = |a - b * Q|
+ = |b * Q - a|
+ = |b * Q| - |a|
+ = |b| - |a|
+ < |b| using 0 < |a| above
+
+ Only negate values that are known to be positive, to avoid signed
+ overflow. */
+ if (known_lt (a, POLY_INT_TYPE (Ca) (0)))
+ {
+ if (known_le (b, a))
+ {
+ *quotient = 1;
+ return true;
+ }
+ if (known_gt (b, POLY_INT_TYPE (Cb) (0)) && known_le (-b, a))
+ {
+ *quotient = -1;
+ return true;
+ }
+ }
+ else if (known_gt (a, POLY_INT_TYPE (Ca) (0)))
+ {
+ if (known_ge (b, a))
+ {
+ *quotient = 1;
+ return true;
+ }
+ if (known_lt (b, POLY_INT_TYPE (Cb) (0)) && known_le (b, -a))
+ {
+ *quotient = -1;
+ return true;
+ }
+ }
+
if (!can_div_trunc_p (a, b, quotient))
return false;
if (maybe_ne (*quotient * b, a))
diff --git a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
index 022ccd69cea5..19a6959d0a10 100644
--- a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
+++ b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
@@ -2161,6 +2161,18 @@ test_can_div_away_from_zero_p ()
ph::make (4, 5, 6),
&const_quot));
ASSERT_EQ (const_quot, C (0));
+ ASSERT_EQ (can_div_away_from_zero_p (ph::make (16, 0, 16),
+ ph::make (16, 16, 15), &const_quot),
+ N <= 2);
+ ASSERT_EQ (const_quot, N <= 2 ? C (1) : C (0));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (16, 0, 0),
+ ph::make (16, 16, 16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (8, 0, 0),
+ ph::make (16, 16, 16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (1));
}
/* Test known_size_p. */
@@ -3388,6 +3400,38 @@ test_signed_can_div_away_from_zero_p ()
ph::make (-8, -4, -5),
&const_quot));
ASSERT_EQ (const_quot, -3);
+ ASSERT_EQ (can_div_away_from_zero_p (ph::make (-16, 0, -16),
+ ph::make (-16, -16, -15), &const_quot),
+ N <= 2);
+ ASSERT_EQ (const_quot, N <= 2 ? C (1) : C (-3));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (-16, 0, 0),
+ ph::make (-16, -16, -16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (-8, 0, 0),
+ ph::make (-16, -16, -16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_EQ (can_div_away_from_zero_p (ph::make (-16, 0, 16),
+ ph::make (16, 16, 15), &const_quot),
+ N <= 2);
+ ASSERT_EQ (const_quot, N <= 2 ? C (-1) : C (1));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (-16, 0, 0),
+ ph::make (16, 16, 16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (-8, 0, 0),
+ ph::make (16, 16, 16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (16, 0, 0),
+ ph::make (-16, -16, -16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (8, 0, 0),
+ ph::make (-16, -16, -16),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (-1));
}
/* Test maybe_in_range_p for signed C. */
--
2.54.0
