From: Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org>
To: gcc-patches@gcc.gnu.org, prathamesh.kulkarni@linaro.org,
richard.sandiford@arm.com
Subject: Re: [PATCH] poly_int: Handle more can_div_trunc_p cases
Date: Fri, 4 Aug 2023 15:37:23 +0530 [thread overview]
Message-ID: <CAAgBjMm9GkxboatkLjcrWBRUpUTpRN0HwYi4eBEw13p3ztcXDA@mail.gmail.com> (raw)
In-Reply-To: <mptmsz82t1q.fsf@arm.com>
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
>
prev parent reply other threads:[~2023-08-04 10:08 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-08-03 12:45 Richard Sandiford
2023-08-03 12:50 ` Richard Biener
2023-08-04 10:07 ` Prathamesh Kulkarni [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAAgBjMm9GkxboatkLjcrWBRUpUTpRN0HwYi4eBEw13p3ztcXDA@mail.gmail.com \
--to=prathamesh.kulkarni@linaro.org \
--cc=gcc-patches@gcc.gnu.org \
--cc=richard.sandiford@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).