From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 67F3B3858C31; Thu, 21 Mar 2024 12:08:46 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 67F3B3858C31 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1711022926; bh=Oemy8V7BSizt71MOgKWdXPiOoNSvELlxYzzNqvDXXWY=; h=From:To:Subject:Date:In-Reply-To:References:From; b=d/Lht7LpxTyaILofBjd8D2sFGx7DTbtInGwRHhlrhbx73IY3qJ6791L6dGKxf5hbK ZQA9zqWZn2NPG6fetygI8pBnHOCxs+9wD4nfO7wGPsDmIVq6YXwmvJZCTS9yDhU4iC r4W4akMje727icVuQuMK/IcXpCztdq1epiWROPR8= From: "cvs-commit at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug libgcc/114397] wrong code with _BitInt() division at -O0 Date: Thu, 21 Mar 2024 12:08:45 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libgcc X-Bugzilla-Version: 14.0 X-Bugzilla-Keywords: wrong-code X-Bugzilla-Severity: normal X-Bugzilla-Who: cvs-commit at gcc dot gnu.org X-Bugzilla-Status: ASSIGNED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: jakub at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D114397 --- Comment #2 from GCC Commits --- The master branch has been updated by Jakub Jelinek : https://gcc.gnu.org/g:59b6cece54f33ac4994834d01e18269856576556 commit r14-9592-g59b6cece54f33ac4994834d01e18269856576556 Author: Jakub Jelinek Date: Thu Mar 21 13:07:50 2024 +0100 libgcc: Fix up bitint division [PR114397] 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 >=3D N (if M =3D=3D 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. 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 =3D=3D vn w= here 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.=