From patchwork Thu Aug 3 12:45:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1816431 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=jXsk+pEN; dkim-atps=neutral Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4RGpVf6t3rz1yYC for ; Thu, 3 Aug 2023 22:46:02 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B8A893858002 for ; Thu, 3 Aug 2023 12:46:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B8A893858002 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1691066760; bh=PDNlzqHc83e92pIL8pdGv+dusPtdJZrBtxwniwhGvw8=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=jXsk+pEN8XAYS8YiVkeB+WHiqCGtlQfe008fleO5yGD8jynYlasg4v7jRkIB6+VEY 7X2Z7sFpYXkw/l8XH6L6dr+vkdY15zTYcAky4NqHOYlKr/MT7KxZdKXvyXHgjvpiAm c8Tg+6SJZs7IvuPvSuDj9IHRQgFwA4Yc+ed5kx7k= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 4254D3858D1E for ; Thu, 3 Aug 2023 12:45:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4254D3858D1E Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id D35E7113E; Thu, 3 Aug 2023 05:46:21 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.110.72]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 65C1E3F6C4; Thu, 3 Aug 2023 05:45:38 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, prathamesh.kulkarni@linaro.org, richard.sandiford@arm.com Cc: prathamesh.kulkarni@linaro.org Subject: [PATCH] poly_int: Handle more can_div_trunc_p cases Date: Thu, 03 Aug 2023 13:45:37 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-26.2 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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 &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. */