From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x131.google.com (mail-lf1-x131.google.com [IPv6:2a00:1450:4864:20::131]) by sourceware.org (Postfix) with ESMTPS id 101D13858D1E for ; Thu, 3 Aug 2023 12:51:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 101D13858D1E Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lf1-x131.google.com with SMTP id 2adb3069b0e04-4fe0eb0ca75so1539424e87.2 for ; Thu, 03 Aug 2023 05:51:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1691067086; x=1691671886; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=Hxmb2qP//rD+ggfFbC58FLwNxFXFtRinQYv3RQ0RnNk=; b=k2sDBgl8chB4LBF30NUSDk4lCKdTnt17R5DMjzEBVEvNxXRoQy9MJVjIw02Q4SbwcD Am9KJOEfEe4xbuU557aPJLYUl5WrAWCfpY9Mw5c9PYyhDOTz5VulnOTMIohRa2Qv+B2F Pc/H1bGQgNcJol48NpvZ5xhjRtwF/KMtU+IKYFmvLjqhedzyfk9wJfCVJ+I3YF4j4SiY Wjcaxj4VNM3ug94+THN2ZhmowJhCt81w17k94TwqeQmOmQWzKgt5ohS+YV2ZS6o+z5Ja fPWdMF97WeZHZmfDDO2gasBf3IV6KOuHniBsgvrtAG8KdYtG5iexUK8tt+x3K1L5q0TL PrVA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691067086; x=1691671886; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Hxmb2qP//rD+ggfFbC58FLwNxFXFtRinQYv3RQ0RnNk=; b=ju6z8A1BEJkUshCiemTTQLx+ufkRp9Fre6Ad5mLX89hVk2NooK7I0vMPgaRSnAM++/ 7TWVTDHj9tVyteK0UL7i4LWO4PO9hsA8iQ+4DXlrcT/voHRxdjFKLCKi2aFLS0HdXj9X g+kDhuSKtJ6ftWUD/AnjdjCW4Gc7uIquVEQdUe1Q7Sp3O82IdbIfd9f+l0DUHy2hTxBD JQflJ7j6I6CCRDKsUNYVO0F2h6btKwqeiwrIoOZm1M+/AelEhsbrFcZdGqL+kME99CRl ax7BKxzYUNKbAv0FaDc0dPzIsIEQ8zV2HzjZfHGOw8nDMke/IttLTqBrV6svRNCd2Z3y m/wQ== X-Gm-Message-State: ABy/qLZt+RvTvP0ncPUKm6tAMyXcFcSm0mS/ZtBvJlxZC8Tw02Yo2cY6 A3JyOtAg+CS4bbsa20p8Rrl24AJCh8yWQBwSCKU= X-Google-Smtp-Source: APBJJlGnW2aksffhfIewsebT4IOSUk/2d762a12q+ZzIOf/BzruTTehvGEMLcAUMqNTvQOFmtV384TM/bShVMiuEB8k= X-Received: by 2002:a2e:998b:0:b0:2b9:ac48:d7fe with SMTP id w11-20020a2e998b000000b002b9ac48d7femr7139596lji.38.1691067085934; Thu, 03 Aug 2023 05:51:25 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Thu, 3 Aug 2023 14:50:26 +0200 Message-ID: Subject: Re: [PATCH] poly_int: Handle more can_div_trunc_p cases To: Richard Sandiford , gcc-patches@gcc.gnu.org, prathamesh.kulkarni@linaro.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,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 List-Id: On Thu, Aug 3, 2023 at 2:46=E2=80=AFPM Richard Sandiford via Gcc-patches 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 =3D b * Q + r > (2) |b * Q| <=3D |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| <=3D |ai| > (3') |ai - bi * Q| <=3D |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| =3D |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| =3D |bi| for all Q, with Q =3D 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 =3D a0 / b0, with various sign conditions. E.g. we now handle: > > (7 + 8x) / (4 + 4x) > > with Q =3D 1 and r =3D 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 conditi= ons. > > 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 =3D=3D 0) > - { > - /* For Q =3D=3D 0 we simply need: (3') |ai| <=3D |bi|. */ > - if (a.coeffs[i] !=3D ICa (0)) > - { > - /* Use negative absolute to avoid overflow, i.e. > - -|ai| >=3D -|bi|. */ > - C neg_abs_a =3D (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coe= ffs[i]); > - C neg_abs_b =3D (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coe= ffs[i]); > - if (neg_abs_a < neg_abs_b) > - return false; > - rem_p =3D true; > - } > - } > + /* The only unconditional arithmetic that we can do on ai, > + bi and Q is ai / bi and ai % bi. (ai =3D=3D minimum int and > + bi =3D=3D -1 would be UB in the caller.) Anything else runs > + the risk of overflow. */ > + auto qi =3D NCa (a.coeffs[i]) / NCb (b.coeffs[i]); > + auto ri =3D NCa (a.coeffs[i]) % NCb (b.coeffs[i]); > + /* (2') and (3') are satisfied when ai /[trunc] bi =3D=3D q. > + So is the stricter condition |ai - bi * Q| < |bi|. */ > + if (qi =3D=3D q) > + rem_p |=3D (ri !=3D 0); > + /* The only other case is when: > + > + |bi * Q| + |bi| =3D |ai| (for (2')) > + and |ai - bi * Q| =3D |bi| (for (3')) > + > + The first is equivalent to |bi|(|Q| + 1) =3D=3D |ai|. > + The second requires ai =3D=3D bi * (Q + 1) or ai =3D=3D bi *= (Q - 1). */ > + else if (ri !=3D 0) > + return false; > + else if (q <=3D 0 && qi < q && qi + 1 =3D=3D q) > + ; > + else if (q >=3D 0 && qi > q && qi - 1 =3D=3D q) > + ; > else > - { > - /* Otherwise just check for the case in which ai / bi =3D= =3D Q. */ > - if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) !=3D q) > - return false; > - if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) !=3D 0) > - rem_p =3D 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 =3D 0; > + ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41), > ph::make (4, 8, 10), > &const_quot), N <=3D 2); > - ASSERT_EQ (const_quot, C (N <=3D 2 ? 3 : 2)); > + ASSERT_EQ (const_quot, C (N <=3D 2 ? 3 : 0)); > ASSERT_EQ (can_div_trunc_p (ph::make (43, 79, 80), > ph::make (4, 8, 10), > &const_quot), N =3D=3D 1); > - ASSERT_EQ (const_quot, C (N =3D=3D 1 ? 10 : N =3D=3D 2 ? 3 : 2)); > + ASSERT_EQ (const_quot, C (N =3D=3D 1 ? 10 : N =3D=3D 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 =3D 0, rem =3D 0; > + ASSERT_EQ (can_div_trunc_p (ph::make (15, 25, 41), > ph::make (4, 8, 10), > &const_quot, &rem), N <=3D 2); > - ASSERT_EQ (const_quot, C (N <=3D 2 ? 3 : 2)); > + ASSERT_EQ (const_quot, C (N <=3D 2 ? 3 : 0)); > if (N <=3D 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 =3D=3D 1); > - ASSERT_EQ (const_quot, C (N =3D=3D 1 ? 10 : N =3D=3D 2 ? 3 : 2)); > + ASSERT_EQ (const_quot, C (N =3D=3D 1 ? 10 : N =3D=3D 2 ? 3 : 0)); > if (N =3D=3D 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 =3D=3D 1); > + if (N =3D=3D 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 <=3D 2); > - ASSERT_EQ (const_quot, C (N <=3D 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 =3D=3D 1); > - ASSERT_EQ (const_quot, C (N =3D=3D 1 ? 11 : N =3D=3D 2 ? 4 : 3)); > + ASSERT_EQ (const_quot, C (N =3D=3D 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 =3D=3D 1); > + if (N =3D=3D 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 =3D=3D 1); > + if (N =3D=3D 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 =3D=3D 1); > + if (N =3D=3D 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 >