[Bug c++/98474] New: incorrect results using __uint128_t

[Bug c++/98474] New: incorrect results using __uint128_t

[jeffhurchalla at gmail dot com]

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

            Bug ID: 98474
           Summary: incorrect results using __uint128_t
           Product: gcc
           Version: 10.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jeffhurchalla at gmail dot com
  Target Milestone: ---

g++ version: g++-10 (Ubuntu 10.1.0-2ubuntu1~18.04) 10.1.0
x64 CPU: Intel(R) Core(TM) i5-4570S CPU @ 2.90GH

Compile command used:
g++-10 -O3 -std="gnu++11" -v -save-temps -fsanitize=undefined -Wall -Wextra
-fno-strict-aliasing -fwrapv -fno-aggressive-loop-optimizations test.cpp -o
testbug

It compiles cleanly for me, with no warnings or errors.  After compiling, I use
the following commands:
./testbug
echo $?

Echo prints 2 for me, but the result should be 0.
The preprocessed version of test.cpp is the same as the non-preprocessed
version.  It follows here:

__attribute__ ((noinline))
__uint128_t foo(__uint128_t& x)
{
    return x;
}

int main()
{
    using T = __uint128_t;
    T two65 = static_cast<T>(1) << 65;
    T two65_copy = two65;

    foo(two65_copy);
    T n = two65_copy;

    while (n >= two65)
        n -= two65;

    return static_cast<int>(n >> 64);
}

[Bug c++/98474] incorrect results using __uint128_t

[jeffhurchalla at gmail dot com]

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

--- Comment #1 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
If I change only the optimization level in the compile command to -O1, then
echo prints the correct result 0.

I have a non-minimal (but still very small) test file on godbolt at
https://godbolt.org/z/4oqnYn
The godbolt link goes to two separate tests which produce the incorrect results
- you can toggle between them with the "#if 1".

There are two interesting things about the godbolt tests:
1. I get correct results when I choose "x86_64 gcc 4.9.3" and incorrect results
when I choose "x86_64 gcc 5.1".  The few earlier versions than 4.9.3 that I
tried were correct also, and the few later versions than 5.1 (including trunk)
that I tried were incorrect also.
2. Using "x86_64 gcc 10.2" (and I'd suspect any version >= 5.1), the tests
print to stdout
"inside 'if'"
but they do not print
"inside 'while'"
This should be impossible.

[Bug tree-optimization/98474] [8/9/10/11 Regression] incorrect results using __uint128_t

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|incorrect results using     |[8/9/10/11 Regression]
                   |__uint128_t                 |incorrect results using
                   |                            |__uint128_t
                 CC|                            |jakub at gcc dot gnu.org
          Component|c++                         |tree-optimization
   Target Milestone|---                         |8.5

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r5-424-g807e902eea17f3132488c256c963823976b2348c
C testcase that just needs -O2:
__attribute__ ((noipa)) void
foo (__uint128_t *x)
{
  asm volatile ("" : : "r" (x) : "memory");
}

int
main ()
{
  __uint128_t a = ((__uint128_t) 1) << 65;
  __uint128_t b = a;
  __uint128_t n;
  foo (&b);
  n = b;
  while (n >= a)
    n -= a;
  if ((int) (n >> 64) != 0)
    __builtin_abort ();
  return 0;
}

Works fine with unsigned long long instead of __uint128_t and 33 instead of 65
and 32 instead of 64, so either a wide-int bug or number of loop iterations
bug.
On the ullong testcase, e.g. profile_estimate prints:
Analyzing # of iterations of loop 1
  exit condition 8589934591 < [n_8, + , 18446744065119617024]
  bounds on difference of bases: -8589934591 ... 18446744065119617024
  result:
    # of iterations n_8 / 8589934592, bounded by 2147483647
but on the uint128_t testcase it prints:
Analyzing # of iterations of loop 1
  exit condition 0x1ffffffffffffffff < [n_8, + ,
0xfffffffffffffffe0000000000000000]
  bounds on difference of bases: -36893488147419103231 ...
-18446744073709551616
  result:
    # of iterations n_8 / 0x20000000000000000, bounded by 0

[Bug tree-optimization/98474] [8/9/10/11 Regression] incorrect results using __uint128_t

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-12-29
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED

[Bug tree-optimization/98474] [8/9/10/11 Regression] incorrect results using __uint128_t

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49858
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49858&action=edit
gcc11-pr98474.patch

Untested fix.

[Bug tree-optimization/98474] [8/9/10/11 Regression] incorrect results using __uint128_t

[jeffhurchalla at gmail dot com]

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

--- Comment #4 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
Thanks for your fix.
I built/installed gcc from the latest git sources, and prior to applying your
patch, as expected the test cases in this report produced incorrect results. 
After I applied your patch, all my tests passed.  This includes the test case
in my first post here, the two godbolt tests I mentioned, and my unit tests for
my github library where I first ran into the problem.

Since it's not quick for me to understand the patched code, could you let me
know if there is a way to avoid the regression with __uint128_t in gcc versions
prior to this patch?  Right now I'm just making the pessimistic assumption that
__uint128_t can't be safely used with gcc versions between 5.1 and the upcoming
version with the patch.  Is that assumption really necessary?

[Bug tree-optimization/98474] [8/9/10/11 Regression] incorrect results using __uint128_t

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS 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:9e603837f7ad886df62e02ac0cd395ec17b7d587

commit r11-6376-g9e603837f7ad886df62e02ac0cd395ec17b7d587
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Dec 31 11:06:56 2020 +0100

    wide-int: Fix wi::to_mpz [PR98474]

    The following testcase is miscompiled, because niter analysis miscomputes
    the number of iterations to 0.
    The problem is that niter analysis uses mpz_t (wonder why, wouldn't
    widest_int do the same job?) and when wi::to_mpz is called e.g. on the
    TYPE_MAX_VALUE of __uint128_t, it initializes the mpz_t result with wrong
    value.
    wi::to_mpz has code to handle negative wide_ints in signed types by
    inverting all bits, importing to mpz and complementing it, which is fine,
    but doesn't handle correctly the case when the wide_int's len (times
    HOST_BITS_PER_WIDE_INT) is smaller than precision when wi::neg_p.
    E.g. the 0xffffffffffffffffffffffffffffffff TYPE_MAX_VALUE is represented
    in wide_int as 0xffffffffffffffff len 1, and wi::to_mpz would create
    0xffffffffffffffff mpz_t value from that.
    This patch handles it by adding the needed -1 host wide int words (and has
    also code to deal with precision that aren't multiple of
    HOST_BITS_PER_WIDE_INT).

    2020-12-31  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98474
            * wide-int.cc (wi::to_mpz): If wide_int has MSB set, but type
            is unsigned and excess negative, append set bits after len until
            precision.

            * gcc.c-torture/execute/pr98474.c: New test.

[Bug tree-optimization/98474] [8/9/10 Regression] incorrect results using __uint128_t

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10/11 Regression]      |[8/9/10 Regression]
                   |incorrect results using     |incorrect results using
                   |__uint128_t                 |__uint128_t

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk so far.

[Bug tree-optimization/98474] [8/9/10 Regression] incorrect results using __uint128_t

[jeffhurchalla at gmail dot com]

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

--- Comment #7 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
Thanks for the info.  After reading your comment and after reading the
description of wide_int at the top of wide-int.h, the newly patched function
wi::to_mpz() makes sense to me and it looks correct.

I'm curious though why the particular constant from the original test case
(_uint128_t a = ((__uint128_t) 1) << 65;) would have caused any trouble for
wi::to_mpz prior to patching.  My understanding of wide_int is that this
particular constant in wide_int representation would not be
sign-extended/compressed - i.e. len times
HOST_BITS_PER_WIDE_INT would be greater than precision for this constant. 
During this test case, does niter analysis receive some other wide_int that was
being incorrectly converted to mpz?

It's not that important I expect, but it's all that's unclear to me.

[Bug tree-optimization/98474] [8/9/10 Regression] incorrect results using __uint128_t

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P2
      Known to work|                            |11.0

[Bug tree-optimization/98474] [8/9/10 Regression] incorrect results using __uint128_t

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:a4d191d08c6acb24034af4182b3524e6ef97546c

commit r10-9224-ga4d191d08c6acb24034af4182b3524e6ef97546c
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Dec 31 11:06:56 2020 +0100

    wide-int: Fix wi::to_mpz [PR98474]

    The following testcase is miscompiled, because niter analysis miscomputes
    the number of iterations to 0.
    The problem is that niter analysis uses mpz_t (wonder why, wouldn't
    widest_int do the same job?) and when wi::to_mpz is called e.g. on the
    TYPE_MAX_VALUE of __uint128_t, it initializes the mpz_t result with wrong
    value.
    wi::to_mpz has code to handle negative wide_ints in signed types by
    inverting all bits, importing to mpz and complementing it, which is fine,
    but doesn't handle correctly the case when the wide_int's len (times
    HOST_BITS_PER_WIDE_INT) is smaller than precision when wi::neg_p.
    E.g. the 0xffffffffffffffffffffffffffffffff TYPE_MAX_VALUE is represented
    in wide_int as 0xffffffffffffffff len 1, and wi::to_mpz would create
    0xffffffffffffffff mpz_t value from that.
    This patch handles it by adding the needed -1 host wide int words (and has
    also code to deal with precision that aren't multiple of
    HOST_BITS_PER_WIDE_INT).

    2020-12-31  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98474
            * wide-int.cc (wi::to_mpz): If wide_int has MSB set, but type
            is unsigned and excess negative, append set bits after len until
            precision.

            * gcc.c-torture/execute/pr98474.c: New test.

    (cherry picked from commit 9e603837f7ad886df62e02ac0cd395ec17b7d587)

[Bug tree-optimization/98474] [8/9 Regression] incorrect results using __uint128_t

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10 Regression]         |[8/9 Regression] incorrect
                   |incorrect results using     |results using __uint128_t
                   |__uint128_t                 |

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 10.3+ too.

[Bug tree-optimization/98474] [8/9 Regression] incorrect results using __uint128_t

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:a750dcc2f404d1785597848c166a1932739def7f

commit r9-9404-ga750dcc2f404d1785597848c166a1932739def7f
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Dec 31 11:06:56 2020 +0100

    wide-int: Fix wi::to_mpz [PR98474]

    The following testcase is miscompiled, because niter analysis miscomputes
    the number of iterations to 0.
    The problem is that niter analysis uses mpz_t (wonder why, wouldn't
    widest_int do the same job?) and when wi::to_mpz is called e.g. on the
    TYPE_MAX_VALUE of __uint128_t, it initializes the mpz_t result with wrong
    value.
    wi::to_mpz has code to handle negative wide_ints in signed types by
    inverting all bits, importing to mpz and complementing it, which is fine,
    but doesn't handle correctly the case when the wide_int's len (times
    HOST_BITS_PER_WIDE_INT) is smaller than precision when wi::neg_p.
    E.g. the 0xffffffffffffffffffffffffffffffff TYPE_MAX_VALUE is represented
    in wide_int as 0xffffffffffffffff len 1, and wi::to_mpz would create
    0xffffffffffffffff mpz_t value from that.
    This patch handles it by adding the needed -1 host wide int words (and has
    also code to deal with precision that aren't multiple of
    HOST_BITS_PER_WIDE_INT).

    2020-12-31  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98474
            * wide-int.cc (wi::to_mpz): If wide_int has MSB set, but type
            is unsigned and excess negative, append set bits after len until
            precision.

            * gcc.c-torture/execute/pr98474.c: New test.

    (cherry picked from commit a4d191d08c6acb24034af4182b3524e6ef97546c)

[Bug tree-optimization/98474] [8/9 Regression] incorrect results using __uint128_t

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-8 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:8cbe9fc12453026f7efc02dad569c6270d595427

commit r8-10872-g8cbe9fc12453026f7efc02dad569c6270d595427
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Dec 31 11:06:56 2020 +0100

    wide-int: Fix wi::to_mpz [PR98474]

    The following testcase is miscompiled, because niter analysis miscomputes
    the number of iterations to 0.
    The problem is that niter analysis uses mpz_t (wonder why, wouldn't
    widest_int do the same job?) and when wi::to_mpz is called e.g. on the
    TYPE_MAX_VALUE of __uint128_t, it initializes the mpz_t result with wrong
    value.
    wi::to_mpz has code to handle negative wide_ints in signed types by
    inverting all bits, importing to mpz and complementing it, which is fine,
    but doesn't handle correctly the case when the wide_int's len (times
    HOST_BITS_PER_WIDE_INT) is smaller than precision when wi::neg_p.
    E.g. the 0xffffffffffffffffffffffffffffffff TYPE_MAX_VALUE is represented
    in wide_int as 0xffffffffffffffff len 1, and wi::to_mpz would create
    0xffffffffffffffff mpz_t value from that.
    This patch handles it by adding the needed -1 host wide int words (and has
    also code to deal with precision that aren't multiple of
    HOST_BITS_PER_WIDE_INT).

    2020-12-31  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98474
            * wide-int.cc (wi::to_mpz): If wide_int has MSB set, but type
            is unsigned and excess negative, append set bits after len until
            precision.

            * gcc.c-torture/execute/pr98474.c: New test.

    (cherry picked from commit a4d191d08c6acb24034af4182b3524e6ef97546c)

[Bug tree-optimization/98474] [8/9 Regression] incorrect results using __uint128_t

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.