From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 4194B3858403 for ; Thu, 21 Mar 2024 08:35:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4194B3858403 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 4194B3858403 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711010153; cv=none; b=Q1NIJW+kHihv4DdWhoWwwLiKk87SY7CTiIuN3SxstyTHp8SG+HTM2mfSrxUarTB67FvN8a6WTo/K/NA4x+CirEO/0/JdY8xbw64BZb5yuT0IAnIPMhJNJrz0mhA5NW+I3f7DtiWSlXkft7WK0KFWF2LzyJbQaaMyTVpl2J8wdYA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711010153; c=relaxed/simple; bh=ria09e6IMEnSBn9NYkeWKUmVnA/ku6uykvT5U4e8hPQ=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:Message-ID:MIME-Version; b=HmPr2EAtIuzvoGKYb5mnluFg3Ka4M8Hxqzvd15ACQa8ZUJpMCbFmuz/t6nyKO6mHNEFfy3VuIpUxPC+pldHFl8poUxnS7Dhvdaolo93ST0X20tE3zPf9G/fHe9rbYCjOPo0DDJBC6nFLxKkX35hdz4CnfzAY+heiFWOlfvIFWQg= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.168.4.150] (unknown [10.168.4.150]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 234EA3532E; Thu, 21 Mar 2024 08:35:45 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1711010145; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=rJUriCL1Lv+KrjdHg2aPX5xJYaXvpqFpBO/3thXm1hA=; b=fa7OPnDeE6WEGa81JPyWtFgthmU/mV6uaYew1PM3jg9rgddV8L7sLS/ROY45pKeV+aUpkt 5Y7gWHuiM4VDWIBa+FZqyHQSmUVUaPtVln7TZ3bLE6gjqbXUIbD8H8jkUB41DifIpSqePH eIKTVJNEs9y1dhjoJwh1JyzABTWQGI8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1711010145; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=rJUriCL1Lv+KrjdHg2aPX5xJYaXvpqFpBO/3thXm1hA=; b=LKyzEByFPVjrxq7RRPVwgNrgRSTIFyQhlLAgL8c2ciS9N2RyNjUoiP+csNuVI64R08qgvb pXzxLIKXka9wu9BA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1711010145; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=rJUriCL1Lv+KrjdHg2aPX5xJYaXvpqFpBO/3thXm1hA=; b=fa7OPnDeE6WEGa81JPyWtFgthmU/mV6uaYew1PM3jg9rgddV8L7sLS/ROY45pKeV+aUpkt 5Y7gWHuiM4VDWIBa+FZqyHQSmUVUaPtVln7TZ3bLE6gjqbXUIbD8H8jkUB41DifIpSqePH eIKTVJNEs9y1dhjoJwh1JyzABTWQGI8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1711010145; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=rJUriCL1Lv+KrjdHg2aPX5xJYaXvpqFpBO/3thXm1hA=; b=LKyzEByFPVjrxq7RRPVwgNrgRSTIFyQhlLAgL8c2ciS9N2RyNjUoiP+csNuVI64R08qgvb pXzxLIKXka9wu9BA== Date: Thu, 21 Mar 2024 09:35:45 +0100 (CET) From: Richard Biener To: Jakub Jelinek cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] libgcc: Fix up bitint division [PR114397] In-Reply-To: Message-ID: <1np0pos0-s307-0q5o-6959-q63n4rnn9op6@fhfr.qr> References: MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Score: -4.30 X-Spamd-Result: default: False [-4.30 / 50.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000]; MIME_GOOD(-0.10)[text/plain]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-0.987]; RCPT_COUNT_TWO(0.00)[2]; DBL_BLOCKED_OPENRESOLVER(0.00)[suse.de:email]; FUZZY_BLOCKED(0.00)[rspamd.com]; RCVD_COUNT_ZERO(0.00)[0]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; BAYES_HAM(-3.00)[100.00%] X-Spam-Level: Authentication-Results: smtp-out1.suse.de; none X-Spam-Status: No, score=-4.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,KAM_LOTSOFHASH,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, 21 Mar 2024, Jakub Jelinek wrote: > Hi! > > The Knuth's division algorithm relies on the number of dividend limbs > to be greater ore equal to number of divisor limbs, which is why > I've added a special case for un < vn at the start of __divmodbitint4. > Unfortunately, my assumption that it then implies abs(v) > abs(u) and > so quotient must be 0 and remainder same as dividend is incorrect. > This is because this check is done before negation of the operands. > While bitint_reduce_prec reduces precision from clearly useless limbs, > the problematic case is when the dividend is unsigned or non-negative > and divisor is negative. We can have limbs (from MS to LS): > dividend: 0 M ?... > divisor: -1 -N ?... > where M has most significant bit set and M >= N (if M == N then it > also the following limbs matter) and the most significant limbs can > be even partial. In this case, the quotient should be -1 rather than > 0. bitint_reduce_prec will reduce the precision of the dividend so > that M is the most significant limb, but can't reduce precision of the > divisor to more than having the -1 as most significant limb, because > -N doesn't have the most significant bit set. > > The following patch fixes it by detecting this problematic case in the > un < vn handling, and instead of assuming q is 0 and r is u will > decrease vn by 1 because it knows the later code will negate the divisor > and it can be then expressed after negation in one fewer limbs. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? OK. Richard. > 2024-03-21 Jakub Jelinek > > PR libgcc/114397 > * libgcc2.c (__divmodbitint4): Don't assume un < vn always means > abs(v) > abs(u), check for a special case of un + 1 == vn where > u is non-negative and v negative and after v's negation vn could > be reduced by 1. > > * gcc.dg/torture/bitint-65.c: New test. > > --- libgcc/libgcc2.c.jj 2024-03-15 19:04:27.000000000 +0100 > +++ libgcc/libgcc2.c 2024-03-20 18:23:51.956879521 +0100 > @@ -1707,44 +1707,67 @@ __divmodbitint4 (UBILtype *q, SItype qpr > USItype vp = avprec % W_TYPE_SIZE; > if (__builtin_expect (un < vn, 0)) > { > - /* If abs(v) > abs(u), then q is 0 and r is u. */ > - if (q) > - __builtin_memset (q, 0, qn * sizeof (UWtype)); > - if (r == NULL) > - return; > -#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__ > - r += rn - 1; > - u += un - 1; > -#endif > - if (up) > - --un; > - if (rn < un) > - un = rn; > - for (rn -= un; un; --un) > + /* If abs(v) > abs(u), then q is 0 and r is u. > + Unfortunately un < vn doesn't always mean abs(v) > abs(u). > + If uprec > 0 and vprec < 0 and vn == un + 1, if the > + top limb of v is all ones and the second most significant > + limb has most significant bit clear, then just decrease > + vn/avprec/vp and continue, after negation both numbers > + will have the same number of limbs. */ > + if (un + 1 == vn > + && uprec >= 0 > + && vprec < 0 > + && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0)) > + == (UWtype) -1) > + && (Wtype) v[BITINT_END (1, vn - 2)] >= 0) > { > - *r = *u; > - r += BITINT_INC; > - u += BITINT_INC; > + vp = 0; > + --vn; > +#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__ > + ++v; > +#endif > } > - if (!rn) > - return; > - if (up) > + else > { > - if (uprec > 0) > - *r = *u & (((UWtype) 1 << up) - 1); > - else > - *r = *u | ((UWtype) -1 << up); > - r += BITINT_INC; > - if (!--rn) > + /* q is 0 and r is u. */ > + if (q) > + __builtin_memset (q, 0, qn * sizeof (UWtype)); > + if (r == NULL) > return; > +#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__ > + r += rn - 1; > + u += un - 1; > +#endif > + if (up) > + --un; > + if (rn < un) > + un = rn; > + for (rn -= un; un; --un) > + { > + *r = *u; > + r += BITINT_INC; > + u += BITINT_INC; > + } > + if (!rn) > + return; > + if (up) > + { > + if (uprec > 0) > + *r = *u & (((UWtype) 1 << up) - 1); > + else > + *r = *u | ((UWtype) -1 << up); > + r += BITINT_INC; > + if (!--rn) > + return; > + } > + UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0; > + for (; rn; --rn) > + { > + *r = c; > + r += BITINT_INC; > + } > + return; > } > - UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0; > - for (; rn; --rn) > - { > - *r = c; > - r += BITINT_INC; > - } > - return; > } > USItype qn2 = un - vn + 1; > if (qn >= qn2) > --- gcc/testsuite/gcc.dg/torture/bitint-65.c.jj 2024-03-20 18:41:38.026311007 +0100 > +++ gcc/testsuite/gcc.dg/torture/bitint-65.c 2024-03-20 18:40:18.604397871 +0100 > @@ -0,0 +1,44 @@ > +/* PR libgcc/114397 */ > +/* { dg-do run { target bitint } } */ > +/* { dg-options "-std=c23" } */ > +/* { dg-skip-if "" { ! run_expensive_tests } { "*" } { "-O0" "-O2" } } */ > +/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */ > + > +#if __BITINT_MAXWIDTH__ >= 129 > +int > +foo (unsigned _BitInt (128) a, _BitInt (129) b) > +{ > + return a / b; > +} > +#endif > + > +#if __BITINT_MAXWIDTH__ >= 192 > +int > +bar (unsigned _BitInt (128) a, _BitInt (192) b) > +{ > + return a / b; > +} > +#endif > + > +int > +main () > +{ > +#if __BITINT_MAXWIDTH__ >= 129 > + if (foo (336225022742818342628768636932743029911uwb, > + -336225022742818342628768636932743029911wb) != -1 > + || foo (336225022742818342628768636932743029912uwb, > + -336225022742818342628768636932743029911wb) != -1 > + || foo (336225022742818342628768636932743029911uwb, > + -336225022742818342628768636932743029912wb) != 0) > + __builtin_abort (); > +#endif > +#if __BITINT_MAXWIDTH__ >= 192 > + if (bar (336225022742818342628768636932743029911uwb, > + -336225022742818342628768636932743029911wb) != -1 > + || bar (336225022742818342628768636932743029912uwb, > + -336225022742818342628768636932743029911wb) != -1 > + || bar (336225022742818342628768636932743029911uwb, > + -336225022742818342628768636932743029912wb) != 0) > + __builtin_abort (); > +#endif > +} > > Jakub > > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)