From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by sourceware.org (Postfix) with ESMTPS id E27333857731 for ; Fri, 4 Aug 2023 10:08:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E27333857731 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-wm1-x32d.google.com with SMTP id 5b1f17b1804b1-3fe490c05c9so2420435e9.0 for ; Fri, 04 Aug 2023 03:08:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1691143679; x=1691748479; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=86uWP6i58jppPzzZ3QwD257E9RefAxGlVDEvTx5h0iI=; b=UR2nCgu3YEo/1Przsolsuth4kdeyKZOIXTk6alRq7Kq71Uu7AqLMyKp9cqCS9tu83V aFZN2ZpHk9U+bL8xvL0lJ9NqqrpYDt9clsyFVyZH0J5jAGr8zMhogZy5wcLH33m6zvkx KqCxeAOXr/6k4Ltk6Pmg+oA1L6wVAtv4bVwY77Tz58rnC4tz+Y227IaKHs8ZRWGtWv2o qXCvRzRaOd5AtZAhsAGZv01nasNIYMOHlNln0lmRbLq6xJrDvi0R0F5f47vApBrIjrbu HfRKf9UY4TfCLDPprSdRrh2w783mkq0wAPL6EJhonCPcKvwI5lfsJ3z+vOQ4WVU145DZ FxyA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691143679; x=1691748479; h=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=86uWP6i58jppPzzZ3QwD257E9RefAxGlVDEvTx5h0iI=; b=AAqGsiODbKRFIThvHCutgnBy0ft38Bb/BUmbQ5cIsx6Adq1Bn3U4YCLB66A4wMJ3Aw mFSBm21tqIziFO3ocZmQqRbFGN1nHF46m1DKxMFQC74moRqYlRzWDn+In0HJwXSLpw8m Rve6dS+YZd+89m11tmPyFPapGmsQuBwu4Ay94g9wNFhH3PCE1gvaKr68tbV6B16xx/mB JIs/EfUNfvFdFafEVVQzX2TGYrXTyMHZuBP/zaxgHCs8ZM9VFegdWCFuBV/UpaZ/XUSS 6uO5+3Mrlo28uJkfXz77tWu8yGTAp1O1BGpPyRcjKYm/ywGt72uLoFIxU6c7kcjZH+ZB 4/7A== X-Gm-Message-State: AOJu0Yy3r8C46Q8WSXLiZYdxT66vDdDGX2EbcdXd0Wtd2MhWBklxzRMf bDkjKqf5/McV6mrFguZfJ/AKp2tq9rP3V8EbIVBCi5mqITrvutnt X-Google-Smtp-Source: AGHT+IFvAP+V5CqmVM+l+BM4/rQDXFhm24+XpTchPeOxYZad1feSA1jH9lMZhWhA/lZsUnIzaWrWL0JlQKGE/5i/7hQ= X-Received: by 2002:adf:e8ca:0:b0:313:f3c0:62d8 with SMTP id k10-20020adfe8ca000000b00313f3c062d8mr1263835wrn.21.1691143678809; Fri, 04 Aug 2023 03:07:58 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Prathamesh Kulkarni Date: Fri, 4 Aug 2023 15:37:23 +0530 Message-ID: Subject: Re: [PATCH] poly_int: Handle more can_div_trunc_p cases To: gcc-patches@gcc.gnu.org, prathamesh.kulkarni@linaro.org, richard.sandiford@arm.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP 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, 3 Aug 2023 at 18:15, Richard Sandiford 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 &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 >