[Bug libgcc/114397] wrong code with _BitInt() division at -O0

["cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114397

--- Comment #2 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:59b6cece54f33ac4994834d01e18269856576556

commit r14-9592-g59b6cece54f33ac4994834d01e18269856576556
Author: Jakub Jelinek <jakub@redhat.com>
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 >= 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.

    2024-03-21  Jakub Jelinek  <jakub@redhat.com>

            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.