* [PATCH] poly_int: Handle more can_div_trunc_p cases
@ 2023-08-03 12:45 Richard Sandiford
2023-08-03 12:50 ` Richard Biener
2023-08-04 10:07 ` Prathamesh Kulkarni
0 siblings, 2 replies; 3+ messages in thread
From: Richard Sandiford @ 2023-08-03 12:45 UTC (permalink / raw)
To: gcc-patches; +Cc: prathamesh.kulkarni
can_div_trunc_p (a, b, &Q, &r) tries to compute a Q and r that
satisfy the usual conditions for truncating division:
(1) a = b * Q + r
(2) |b * Q| <= |a|
(3) |r| < |b|
We can compute Q using the constant component (the case when
all indeterminates are zero). Since |r| < |b| for the constant
case, the requirements for indeterminate xi with coefficients
ai (for a) and bi (for b) are:
(2') |bi * Q| <= |ai|
(3') |ai - bi * Q| <= |bi|
(See the big comment for more details, restrictions, and reasoning).
However, the function works on abstract arithmetic types, and so
it has to be careful not to introduce new overflow. The code
therefore only handled the extreme for (3'), that is:
|ai - bi * Q| = |bi|
for the case where Q is zero.
Looking at it again, the overflow issue is a bit easier to handle than
I'd originally thought (or so I hope). This patch therefore extends the
code to handle |ai - bi * Q| = |bi| for all Q, with Q = 0 no longer
being a separate case.
The net effect is to allow the function to succeed for things like:
(a0 + b1 (Q+1) x) / (b0 + b1 x)
where Q = a0 / b0, with various sign conditions. E.g. we now handle:
(7 + 8x) / (4 + 4x)
with Q = 1 and r = 3 + 4x,
Tested on aarch64-linux-gnu. OK to install?
Richard
gcc/
* poly-int.h (can_div_trunc_p): Succeed for more boundary conditions.
gcc/testsuite/
* gcc.dg/plugin/poly-int-tests.h (test_can_div_trunc_p_const)
(test_can_div_trunc_p_const): Add more tests.
---
gcc/poly-int.h | 45 ++++++-----
gcc/testsuite/gcc.dg/plugin/poly-int-tests.h | 85 +++++++++++++++++---
2 files changed, 98 insertions(+), 32 deletions(-)
diff --git a/gcc/poly-int.h b/gcc/poly-int.h
index 12571455081..7bff5e5ad26 100644
--- a/gcc/poly-int.h
+++ b/gcc/poly-int.h
@@ -2355,28 +2355,31 @@ can_div_trunc_p (const poly_int_pod<N, Ca> &a,
}
else
{
- if (q == 0)
- {
- /* For Q == 0 we simply need: (3') |ai| <= |bi|. */
- if (a.coeffs[i] != ICa (0))
- {
- /* Use negative absolute to avoid overflow, i.e.
- -|ai| >= -|bi|. */
- C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]);
- C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]);
- if (neg_abs_a < neg_abs_b)
- return false;
- rem_p = true;
- }
- }
+ /* The only unconditional arithmetic that we can do on ai,
+ bi and Q is ai / bi and ai % bi. (ai == minimum int and
+ bi == -1 would be UB in the caller.) Anything else runs
+ the risk of overflow. */
+ auto qi = NCa (a.coeffs[i]) / NCb (b.coeffs[i]);
+ auto ri = NCa (a.coeffs[i]) % NCb (b.coeffs[i]);
+ /* (2') and (3') are satisfied when ai /[trunc] bi == q.
+ So is the stricter condition |ai - bi * Q| < |bi|. */
+ if (qi == q)
+ rem_p |= (ri != 0);
+ /* The only other case is when:
+
+ |bi * Q| + |bi| = |ai| (for (2'))
+ and |ai - bi * Q| = |bi| (for (3'))
+
+ The first is equivalent to |bi|(|Q| + 1) == |ai|.
+ The second requires ai == bi * (Q + 1) or ai == bi * (Q - 1). */
+ else if (ri != 0)
+ return false;
+ else if (q <= 0 && qi < q && qi + 1 == q)
+ ;
+ else if (q >= 0 && qi > q && qi - 1 == q)
+ ;
else
- {
- /* Otherwise just check for the case in which ai / bi == Q. */
- if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q)
- return false;
- if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0)
- rem_p = true;
- }
+ return false;
}
}
diff --git a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
index 0b89acd91cd..7af98595a5e 100644
--- a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
+++ b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
@@ -1899,14 +1899,19 @@ test_can_div_trunc_p_const ()
ph::make (4, 8, 12),
&const_quot));
ASSERT_EQ (const_quot, C (2));
- ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 40),
+ ASSERT_TRUE (can_div_trunc_p (ph::make (15, 25, 40),
+ ph::make (4, 8, 10),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (3));
+ const_quot = 0;
+ ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41),
ph::make (4, 8, 10),
&const_quot), N <= 2);
- ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 2));
+ ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 0));
ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80),
ph::make (4, 8, 10),
&const_quot), N == 1);
- ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 2));
+ ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 0));
ASSERT_TRUE (can_div_trunc_p (ph::make (3, 4, 5),
ph::make (4, 5, 6),
&const_quot));
@@ -1964,16 +1969,22 @@ test_can_div_trunc_p_const ()
&const_quot, &rem));
ASSERT_EQ (const_quot, C (2));
ASSERT_KNOWN_EQ (rem, ph::make (1, 7, 6));
- ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 40),
+ ASSERT_TRUE (can_div_trunc_p (ph::make (15, 25, 40),
+ ph::make (4, 8, 10),
+ &const_quot, &rem));
+ ASSERT_EQ (const_quot, C (3));
+ ASSERT_KNOWN_EQ (rem, ph::make (3, 1, 10));
+ const_quot = 0, rem = 0;
+ ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41),
ph::make (4, 8, 10),
&const_quot, &rem), N <= 2);
- ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 2));
+ ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 0));
if (N <= 2)
ASSERT_KNOWN_EQ (rem, ph::make (3, 1, 0));
ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80),
ph::make (4, 8, 10),
&const_quot, &rem), N == 1);
- ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 2));
+ ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 0));
if (N == 1)
ASSERT_KNOWN_EQ (rem, ch::make (3));
ASSERT_TRUE (can_div_trunc_p (ph::make (3, 4, 5),
@@ -2024,6 +2035,19 @@ test_can_div_trunc_p_const ()
&const_quot, &rem));
ASSERT_EQ (const_quot, C (0));
ASSERT_KNOWN_EQ (rem, ch::make (0));
+ ASSERT_TRUE (can_div_trunc_p (ph::make (9, 10, 20),
+ ph::make (5, 5, 20),
+ &const_quot, &rem));
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_KNOWN_EQ (rem, ph::make (4, 5, 0));
+ ASSERT_EQ (can_div_trunc_p (ph::make (9, 11, 20),
+ ph::make (5, 5, 20),
+ &const_quot, &rem), N == 1);
+ if (N == 1)
+ {
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_KNOWN_EQ (rem, C (4));
+ }
}
/* Test the form of can_div_trunc_p that returns a polynomail quotient,
@@ -2093,14 +2117,14 @@ test_can_div_away_from_zero_p ()
ph::make (4, 8, 12),
&const_quot));
ASSERT_EQ (const_quot, C (3));
- ASSERT_EQ (can_div_away_from_zero_p (ph::make (15, 25, 40),
- ph::make (4, 8, 10),
- &const_quot), N <= 2);
- ASSERT_EQ (const_quot, C (N <= 2 ? 4 : 3));
+ ASSERT_TRUE (can_div_away_from_zero_p (ph::make (15, 25, 40),
+ ph::make (4, 8, 10),
+ &const_quot));
+ ASSERT_EQ (const_quot, C (4));
ASSERT_EQ (can_div_away_from_zero_p (ph::make (43, 79, 80),
ph::make (4, 8, 10),
&const_quot), N == 1);
- ASSERT_EQ (const_quot, C (N == 1 ? 11 : N == 2 ? 4 : 3));
+ ASSERT_EQ (const_quot, C (N == 1 ? 11 : 4));
ASSERT_TRUE (can_div_away_from_zero_p (ph::make (3, 4, 5),
ph::make (4, 5, 6),
&const_quot));
@@ -3232,6 +3256,45 @@ test_signed_can_div_trunc_p_const ()
&const_quot, &rem));
ASSERT_EQ (const_quot, -2);
ASSERT_KNOWN_EQ (rem, ph::make (2, 1, 3));
+ ASSERT_TRUE (can_div_trunc_p (ph::make (-9, -10, -20),
+ ph::make (-5, -5, -20),
+ &const_quot, &rem));
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_KNOWN_EQ (rem, ph::make (-4, -5, 0));
+ ASSERT_EQ (can_div_trunc_p (ph::make (-9, -11, -20),
+ ph::make (-5, -5, -20),
+ &const_quot, &rem), N == 1);
+ if (N == 1)
+ {
+ ASSERT_EQ (const_quot, C (1));
+ ASSERT_KNOWN_EQ (rem, C (-4));
+ }
+ ASSERT_TRUE (can_div_trunc_p (ph::make (9, 10, 20),
+ ph::make (-5, -5, -20),
+ &const_quot, &rem));
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_KNOWN_EQ (rem, ph::make (4, 5, 0));
+ ASSERT_EQ (can_div_trunc_p (ph::make (9, 11, 20),
+ ph::make (-5, -5, -20),
+ &const_quot, &rem), N == 1);
+ if (N == 1)
+ {
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_KNOWN_EQ (rem, C (4));
+ }
+ ASSERT_TRUE (can_div_trunc_p (ph::make (-9, -10, -20),
+ ph::make (5, 5, 20),
+ &const_quot, &rem));
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_KNOWN_EQ (rem, ph::make (-4, -5, 0));
+ ASSERT_EQ (can_div_trunc_p (ph::make (-9, -11, -20),
+ ph::make (5, 5, 20),
+ &const_quot, &rem), N == 1);
+ if (N == 1)
+ {
+ ASSERT_EQ (const_quot, C (-1));
+ ASSERT_KNOWN_EQ (rem, C (-4));
+ }
}
/* Test the form of can_div_trunc_p that returns a poly_int, for signed C. */
--
2.25.1
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] poly_int: Handle more can_div_trunc_p cases
2023-08-03 12:45 [PATCH] poly_int: Handle more can_div_trunc_p cases Richard Sandiford
@ 2023-08-03 12:50 ` Richard Biener
2023-08-04 10:07 ` Prathamesh Kulkarni
1 sibling, 0 replies; 3+ messages in thread
From: Richard Biener @ 2023-08-03 12:50 UTC (permalink / raw)
To: Richard Sandiford, gcc-patches, prathamesh.kulkarni
On Thu, Aug 3, 2023 at 2:46 PM Richard Sandiford via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> can_div_trunc_p (a, b, &Q, &r) tries to compute a Q and r that
> satisfy the usual conditions for truncating division:
>
> (1) a = b * Q + r
> (2) |b * Q| <= |a|
> (3) |r| < |b|
>
> We can compute Q using the constant component (the case when
> all indeterminates are zero). Since |r| < |b| for the constant
> case, the requirements for indeterminate xi with coefficients
> ai (for a) and bi (for b) are:
>
> (2') |bi * Q| <= |ai|
> (3') |ai - bi * Q| <= |bi|
>
> (See the big comment for more details, restrictions, and reasoning).
>
> However, the function works on abstract arithmetic types, and so
> it has to be careful not to introduce new overflow. The code
> therefore only handled the extreme for (3'), that is:
>
> |ai - bi * Q| = |bi|
>
> for the case where Q is zero.
>
> Looking at it again, the overflow issue is a bit easier to handle than
> I'd originally thought (or so I hope). This patch therefore extends the
> code to handle |ai - bi * Q| = |bi| for all Q, with Q = 0 no longer
> being a separate case.
>
> The net effect is to allow the function to succeed for things like:
>
> (a0 + b1 (Q+1) x) / (b0 + b1 x)
>
> where Q = a0 / b0, with various sign conditions. E.g. we now handle:
>
> (7 + 8x) / (4 + 4x)
>
> with Q = 1 and r = 3 + 4x,
>
> Tested on aarch64-linux-gnu. OK to install?
OK.
Richard.
> Richard
>
>
> gcc/
> * poly-int.h (can_div_trunc_p): Succeed for more boundary conditions.
>
> gcc/testsuite/
> * gcc.dg/plugin/poly-int-tests.h (test_can_div_trunc_p_const)
> (test_can_div_trunc_p_const): Add more tests.
> ---
> gcc/poly-int.h | 45 ++++++-----
> gcc/testsuite/gcc.dg/plugin/poly-int-tests.h | 85 +++++++++++++++++---
> 2 files changed, 98 insertions(+), 32 deletions(-)
>
> diff --git a/gcc/poly-int.h b/gcc/poly-int.h
> index 12571455081..7bff5e5ad26 100644
> --- a/gcc/poly-int.h
> +++ b/gcc/poly-int.h
> @@ -2355,28 +2355,31 @@ can_div_trunc_p (const poly_int_pod<N, Ca> &a,
> }
> else
> {
> - if (q == 0)
> - {
> - /* For Q == 0 we simply need: (3') |ai| <= |bi|. */
> - if (a.coeffs[i] != ICa (0))
> - {
> - /* Use negative absolute to avoid overflow, i.e.
> - -|ai| >= -|bi|. */
> - C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]);
> - C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]);
> - if (neg_abs_a < neg_abs_b)
> - return false;
> - rem_p = true;
> - }
> - }
> + /* The only unconditional arithmetic that we can do on ai,
> + bi and Q is ai / bi and ai % bi. (ai == minimum int and
> + bi == -1 would be UB in the caller.) Anything else runs
> + the risk of overflow. */
> + auto qi = NCa (a.coeffs[i]) / NCb (b.coeffs[i]);
> + auto ri = NCa (a.coeffs[i]) % NCb (b.coeffs[i]);
> + /* (2') and (3') are satisfied when ai /[trunc] bi == q.
> + So is the stricter condition |ai - bi * Q| < |bi|. */
> + if (qi == q)
> + rem_p |= (ri != 0);
> + /* The only other case is when:
> +
> + |bi * Q| + |bi| = |ai| (for (2'))
> + and |ai - bi * Q| = |bi| (for (3'))
> +
> + The first is equivalent to |bi|(|Q| + 1) == |ai|.
> + The second requires ai == bi * (Q + 1) or ai == bi * (Q - 1). */
> + else if (ri != 0)
> + return false;
> + else if (q <= 0 && qi < q && qi + 1 == q)
> + ;
> + else if (q >= 0 && qi > q && qi - 1 == q)
> + ;
> else
> - {
> - /* Otherwise just check for the case in which ai / bi == Q. */
> - if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q)
> - return false;
> - if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0)
> - rem_p = true;
> - }
> + return false;
> }
> }
>
> diff --git a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> index 0b89acd91cd..7af98595a5e 100644
> --- a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> +++ b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> @@ -1899,14 +1899,19 @@ test_can_div_trunc_p_const ()
> ph::make (4, 8, 12),
> &const_quot));
> ASSERT_EQ (const_quot, C (2));
> - ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 40),
> + ASSERT_TRUE (can_div_trunc_p (ph::make (15, 25, 40),
> + ph::make (4, 8, 10),
> + &const_quot));
> + ASSERT_EQ (const_quot, C (3));
> + const_quot = 0;
> + ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41),
> ph::make (4, 8, 10),
> &const_quot), N <= 2);
> - ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 0));
> ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80),
> ph::make (4, 8, 10),
> &const_quot), N == 1);
> - ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 0));
> ASSERT_TRUE (can_div_trunc_p (ph::make (3, 4, 5),
> ph::make (4, 5, 6),
> &const_quot));
> @@ -1964,16 +1969,22 @@ test_can_div_trunc_p_const ()
> &const_quot, &rem));
> ASSERT_EQ (const_quot, C (2));
> ASSERT_KNOWN_EQ (rem, ph::make (1, 7, 6));
> - ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 40),
> + ASSERT_TRUE (can_div_trunc_p (ph::make (15, 25, 40),
> + ph::make (4, 8, 10),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (3));
> + ASSERT_KNOWN_EQ (rem, ph::make (3, 1, 10));
> + const_quot = 0, rem = 0;
> + ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41),
> ph::make (4, 8, 10),
> &const_quot, &rem), N <= 2);
> - ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 0));
> if (N <= 2)
> ASSERT_KNOWN_EQ (rem, ph::make (3, 1, 0));
> ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80),
> ph::make (4, 8, 10),
> &const_quot, &rem), N == 1);
> - ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 0));
> if (N == 1)
> ASSERT_KNOWN_EQ (rem, ch::make (3));
> ASSERT_TRUE (can_div_trunc_p (ph::make (3, 4, 5),
> @@ -2024,6 +2035,19 @@ test_can_div_trunc_p_const ()
> &const_quot, &rem));
> ASSERT_EQ (const_quot, C (0));
> ASSERT_KNOWN_EQ (rem, ch::make (0));
> + ASSERT_TRUE (can_div_trunc_p (ph::make (9, 10, 20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, ph::make (4, 5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (9, 11, 20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, C (4));
> + }
> }
>
> /* Test the form of can_div_trunc_p that returns a polynomail quotient,
> @@ -2093,14 +2117,14 @@ test_can_div_away_from_zero_p ()
> ph::make (4, 8, 12),
> &const_quot));
> ASSERT_EQ (const_quot, C (3));
> - ASSERT_EQ (can_div_away_from_zero_p (ph::make (15, 25, 40),
> - ph::make (4, 8, 10),
> - &const_quot), N <= 2);
> - ASSERT_EQ (const_quot, C (N <= 2 ? 4 : 3));
> + ASSERT_TRUE (can_div_away_from_zero_p (ph::make (15, 25, 40),
> + ph::make (4, 8, 10),
> + &const_quot));
> + ASSERT_EQ (const_quot, C (4));
> ASSERT_EQ (can_div_away_from_zero_p (ph::make (43, 79, 80),
> ph::make (4, 8, 10),
> &const_quot), N == 1);
> - ASSERT_EQ (const_quot, C (N == 1 ? 11 : N == 2 ? 4 : 3));
> + ASSERT_EQ (const_quot, C (N == 1 ? 11 : 4));
> ASSERT_TRUE (can_div_away_from_zero_p (ph::make (3, 4, 5),
> ph::make (4, 5, 6),
> &const_quot));
> @@ -3232,6 +3256,45 @@ test_signed_can_div_trunc_p_const ()
> &const_quot, &rem));
> ASSERT_EQ (const_quot, -2);
> ASSERT_KNOWN_EQ (rem, ph::make (2, 1, 3));
> + ASSERT_TRUE (can_div_trunc_p (ph::make (-9, -10, -20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, ph::make (-4, -5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (-9, -11, -20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, C (-4));
> + }
> + ASSERT_TRUE (can_div_trunc_p (ph::make (9, 10, 20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, ph::make (4, 5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (9, 11, 20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, C (4));
> + }
> + ASSERT_TRUE (can_div_trunc_p (ph::make (-9, -10, -20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, ph::make (-4, -5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (-9, -11, -20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, C (-4));
> + }
> }
>
> /* Test the form of can_div_trunc_p that returns a poly_int, for signed C. */
> --
> 2.25.1
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] poly_int: Handle more can_div_trunc_p cases
2023-08-03 12:45 [PATCH] poly_int: Handle more can_div_trunc_p cases Richard Sandiford
2023-08-03 12:50 ` Richard Biener
@ 2023-08-04 10:07 ` Prathamesh Kulkarni
1 sibling, 0 replies; 3+ messages in thread
From: Prathamesh Kulkarni @ 2023-08-04 10:07 UTC (permalink / raw)
To: gcc-patches, prathamesh.kulkarni, richard.sandiford
On Thu, 3 Aug 2023 at 18:15, Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> can_div_trunc_p (a, b, &Q, &r) tries to compute a Q and r that
> satisfy the usual conditions for truncating division:
>
> (1) a = b * Q + r
> (2) |b * Q| <= |a|
> (3) |r| < |b|
>
> We can compute Q using the constant component (the case when
> all indeterminates are zero). Since |r| < |b| for the constant
> case, the requirements for indeterminate xi with coefficients
> ai (for a) and bi (for b) are:
>
> (2') |bi * Q| <= |ai|
> (3') |ai - bi * Q| <= |bi|
>
> (See the big comment for more details, restrictions, and reasoning).
>
> However, the function works on abstract arithmetic types, and so
> it has to be careful not to introduce new overflow. The code
> therefore only handled the extreme for (3'), that is:
>
> |ai - bi * Q| = |bi|
>
> for the case where Q is zero.
>
> Looking at it again, the overflow issue is a bit easier to handle than
> I'd originally thought (or so I hope). This patch therefore extends the
> code to handle |ai - bi * Q| = |bi| for all Q, with Q = 0 no longer
> being a separate case.
>
> The net effect is to allow the function to succeed for things like:
>
> (a0 + b1 (Q+1) x) / (b0 + b1 x)
>
> where Q = a0 / b0, with various sign conditions. E.g. we now handle:
>
> (7 + 8x) / (4 + 4x)
>
> with Q = 1 and r = 3 + 4x,
>
> Tested on aarch64-linux-gnu. OK to install?
Hi Richard,
Thanks for the fix! With this patch, I can confirm we correctly select arg1,
when a pattern in sel has len = 4 + 4x, a1 = 5 + 4x and ae = 7 + 8x.
Thanks,
Prathamesh
>
> Richard
>
>
> gcc/
> * poly-int.h (can_div_trunc_p): Succeed for more boundary conditions.
>
> gcc/testsuite/
> * gcc.dg/plugin/poly-int-tests.h (test_can_div_trunc_p_const)
> (test_can_div_trunc_p_const): Add more tests.
> ---
> gcc/poly-int.h | 45 ++++++-----
> gcc/testsuite/gcc.dg/plugin/poly-int-tests.h | 85 +++++++++++++++++---
> 2 files changed, 98 insertions(+), 32 deletions(-)
>
> diff --git a/gcc/poly-int.h b/gcc/poly-int.h
> index 12571455081..7bff5e5ad26 100644
> --- a/gcc/poly-int.h
> +++ b/gcc/poly-int.h
> @@ -2355,28 +2355,31 @@ can_div_trunc_p (const poly_int_pod<N, Ca> &a,
> }
> else
> {
> - if (q == 0)
> - {
> - /* For Q == 0 we simply need: (3') |ai| <= |bi|. */
> - if (a.coeffs[i] != ICa (0))
> - {
> - /* Use negative absolute to avoid overflow, i.e.
> - -|ai| >= -|bi|. */
> - C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]);
> - C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]);
> - if (neg_abs_a < neg_abs_b)
> - return false;
> - rem_p = true;
> - }
> - }
> + /* The only unconditional arithmetic that we can do on ai,
> + bi and Q is ai / bi and ai % bi. (ai == minimum int and
> + bi == -1 would be UB in the caller.) Anything else runs
> + the risk of overflow. */
> + auto qi = NCa (a.coeffs[i]) / NCb (b.coeffs[i]);
> + auto ri = NCa (a.coeffs[i]) % NCb (b.coeffs[i]);
> + /* (2') and (3') are satisfied when ai /[trunc] bi == q.
> + So is the stricter condition |ai - bi * Q| < |bi|. */
> + if (qi == q)
> + rem_p |= (ri != 0);
> + /* The only other case is when:
> +
> + |bi * Q| + |bi| = |ai| (for (2'))
> + and |ai - bi * Q| = |bi| (for (3'))
> +
> + The first is equivalent to |bi|(|Q| + 1) == |ai|.
> + The second requires ai == bi * (Q + 1) or ai == bi * (Q - 1). */
> + else if (ri != 0)
> + return false;
> + else if (q <= 0 && qi < q && qi + 1 == q)
> + ;
> + else if (q >= 0 && qi > q && qi - 1 == q)
> + ;
> else
> - {
> - /* Otherwise just check for the case in which ai / bi == Q. */
> - if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q)
> - return false;
> - if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0)
> - rem_p = true;
> - }
> + return false;
> }
> }
>
> diff --git a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> index 0b89acd91cd..7af98595a5e 100644
> --- a/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> +++ b/gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> @@ -1899,14 +1899,19 @@ test_can_div_trunc_p_const ()
> ph::make (4, 8, 12),
> &const_quot));
> ASSERT_EQ (const_quot, C (2));
> - ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 40),
> + ASSERT_TRUE (can_div_trunc_p (ph::make (15, 25, 40),
> + ph::make (4, 8, 10),
> + &const_quot));
> + ASSERT_EQ (const_quot, C (3));
> + const_quot = 0;
> + ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41),
> ph::make (4, 8, 10),
> &const_quot), N <= 2);
> - ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 0));
> ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80),
> ph::make (4, 8, 10),
> &const_quot), N == 1);
> - ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 0));
> ASSERT_TRUE (can_div_trunc_p (ph::make (3, 4, 5),
> ph::make (4, 5, 6),
> &const_quot));
> @@ -1964,16 +1969,22 @@ test_can_div_trunc_p_const ()
> &const_quot, &rem));
> ASSERT_EQ (const_quot, C (2));
> ASSERT_KNOWN_EQ (rem, ph::make (1, 7, 6));
> - ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 40),
> + ASSERT_TRUE (can_div_trunc_p (ph::make (15, 25, 40),
> + ph::make (4, 8, 10),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (3));
> + ASSERT_KNOWN_EQ (rem, ph::make (3, 1, 10));
> + const_quot = 0, rem = 0;
> + ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41),
> ph::make (4, 8, 10),
> &const_quot, &rem), N <= 2);
> - ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N <= 2 ? 3 : 0));
> if (N <= 2)
> ASSERT_KNOWN_EQ (rem, ph::make (3, 1, 0));
> ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80),
> ph::make (4, 8, 10),
> &const_quot, &rem), N == 1);
> - ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 2));
> + ASSERT_EQ (const_quot, C (N == 1 ? 10 : N == 2 ? 3 : 0));
> if (N == 1)
> ASSERT_KNOWN_EQ (rem, ch::make (3));
> ASSERT_TRUE (can_div_trunc_p (ph::make (3, 4, 5),
> @@ -2024,6 +2035,19 @@ test_can_div_trunc_p_const ()
> &const_quot, &rem));
> ASSERT_EQ (const_quot, C (0));
> ASSERT_KNOWN_EQ (rem, ch::make (0));
> + ASSERT_TRUE (can_div_trunc_p (ph::make (9, 10, 20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, ph::make (4, 5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (9, 11, 20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, C (4));
> + }
> }
>
> /* Test the form of can_div_trunc_p that returns a polynomail quotient,
> @@ -2093,14 +2117,14 @@ test_can_div_away_from_zero_p ()
> ph::make (4, 8, 12),
> &const_quot));
> ASSERT_EQ (const_quot, C (3));
> - ASSERT_EQ (can_div_away_from_zero_p (ph::make (15, 25, 40),
> - ph::make (4, 8, 10),
> - &const_quot), N <= 2);
> - ASSERT_EQ (const_quot, C (N <= 2 ? 4 : 3));
> + ASSERT_TRUE (can_div_away_from_zero_p (ph::make (15, 25, 40),
> + ph::make (4, 8, 10),
> + &const_quot));
> + ASSERT_EQ (const_quot, C (4));
> ASSERT_EQ (can_div_away_from_zero_p (ph::make (43, 79, 80),
> ph::make (4, 8, 10),
> &const_quot), N == 1);
> - ASSERT_EQ (const_quot, C (N == 1 ? 11 : N == 2 ? 4 : 3));
> + ASSERT_EQ (const_quot, C (N == 1 ? 11 : 4));
> ASSERT_TRUE (can_div_away_from_zero_p (ph::make (3, 4, 5),
> ph::make (4, 5, 6),
> &const_quot));
> @@ -3232,6 +3256,45 @@ test_signed_can_div_trunc_p_const ()
> &const_quot, &rem));
> ASSERT_EQ (const_quot, -2);
> ASSERT_KNOWN_EQ (rem, ph::make (2, 1, 3));
> + ASSERT_TRUE (can_div_trunc_p (ph::make (-9, -10, -20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, ph::make (-4, -5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (-9, -11, -20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (1));
> + ASSERT_KNOWN_EQ (rem, C (-4));
> + }
> + ASSERT_TRUE (can_div_trunc_p (ph::make (9, 10, 20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, ph::make (4, 5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (9, 11, 20),
> + ph::make (-5, -5, -20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, C (4));
> + }
> + ASSERT_TRUE (can_div_trunc_p (ph::make (-9, -10, -20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem));
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, ph::make (-4, -5, 0));
> + ASSERT_EQ (can_div_trunc_p (ph::make (-9, -11, -20),
> + ph::make (5, 5, 20),
> + &const_quot, &rem), N == 1);
> + if (N == 1)
> + {
> + ASSERT_EQ (const_quot, C (-1));
> + ASSERT_KNOWN_EQ (rem, C (-4));
> + }
> }
>
> /* Test the form of can_div_trunc_p that returns a poly_int, for signed C. */
> --
> 2.25.1
>
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-08-04 10:08 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-08-03 12:45 [PATCH] poly_int: Handle more can_div_trunc_p cases Richard Sandiford
2023-08-03 12:50 ` Richard Biener
2023-08-04 10:07 ` Prathamesh Kulkarni
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).