[Bug analyzer/98447] New: incorrect -Wanalyzer-shift-count-overflow warning

[Bug analyzer/98447] New: incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

            Bug ID: 98447
           Summary: incorrect -Wanalyzer-shift-count-overflow warning
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: vincent-gcc at vinc17 dot net
  Target Milestone: ---

Consider the following code on a platform with a 64-bit unsigned long:

void f (unsigned long *p, int r, int i)
{
  int b = 63, n = r % 16;

  while (i >= 0)
    {
      if (n > b)
        {
          p[i--] = b + 1 >= 64 ? 0UL : 1UL << (b + 1);
          b += 64;
        }
      b -= n;
    }
}

The "1UL << (b + 1)" can be executed only if b + 1 < 64, so that the shift
count is always strictly less than 64.

But I get the following incorrect warning.

zira:~> gcc-snapshot -O2 -fanalyzer -c tst.c
tst.c: In function 'f':
tst.c:9:38: warning: shift by count ('64') >= precision of type ('64')
[-Wanalyzer-shift-count-overflow]
    9 |           p[i--] = b + 1 >= 64 ? 0UL : 1UL << (b + 1);
      |                    ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
  'f': events 1-5
    |
    |    5 |   while (i >= 0)
    |      |          ~~^~~~
    |      |            |
    |      |            (1) following 'true' branch (when 'i >= 0')...
    |    6 |     {
    |    7 |       if (n > b)
    |      |          ~  
    |      |          |
    |      |          (2) ...to here
    |      |          (3) following 'true' branch (when 'b < n')...
    |    8 |         {
    |    9 |           p[i--] = b + 1 >= 64 ? 0UL : 1UL << (b + 1);
    |      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |                                      |           |
    |      |                                      |           (4) ...to here
    |      |                                      (5) shift by count '64' here
    |

with

gcc (Debian 20201224-1) 11.0.0 20201224 (experimental) [master revision
085fd2a46e5:21536a75ed4:168be2b3afddd41d4575ed55439231812bc3e7c9]

Note: This is a simplified testcase obtained from GNU MPFR's tests/random2.c
file, on which I got this issue.

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #1 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
This is probably due to commit 5e00ad3ffbfb4df7242c313a0d836f5b538eb2fb (where
this warning was introduced, as requested by PR97424).

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #2 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
Note: The warning occurs when the compiler knows that b < 63 in the "if" case
(it occurs up to "n = r % 64", but not with "n = r % 65") so that the condition
"b + 1 >= 64" is always false. I suppose that the p[i--] line has already been
simplified to something equivalent to

  p[i--] = 1UL << (b + 1);

but the analyzer doesn't see that b has restricted values in the "if" case.

      if (n > b)
        {
          p[i--] = 1UL << (b + 1);
          b += 64;
        }

triggers the warning, but not

      if (63 > b)
        {
          p[i--] = 1UL << (b + 1);
          b += 64;
        }

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #3 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
And the warning is triggered with the initial "b = 63", but not "b = 62" and
smaller values.

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #4 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
So this can be simplified to

void f (unsigned long *p, int r, int i)
{
  int b = 64, n = r % 64;

  while (i >= 0 && b >= 0)
    {
      if (b <= n)
        p[i--] = 1UL << b;
      b -= n;
    }
}

Here, due to the "n = r % 64", one has n <= 63, so that "1UL << b" can be
executed only when b <= 63, and the shift is necessarily valid (no overflow).

This could be part of a more general bug: I also get the
-Wanalyzer-shift-count-overflow warning if I replace "n = r % 64" by "n = r".
While with the initial code, one is certain that the shift is valid, now this
depends on the value of r. But since the compiler doesn't know the condition
under which this function will be called, it should not assume that r may have
any value.

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #5 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
This is still failing (trunk). The test on godbolt:
https://godbolt.org/z/Yx7b1d

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #6 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
On the test on godbolt, this is still failing with:
gcc (Compiler-Explorer-Build) 12.0.0 20210420 (experimental)

[Bug analyzer/98447] incorrect -Wanalyzer-shift-count-overflow warning

[vincent-gcc at vinc17 dot net]

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

--- Comment #7 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
On https://godbolt.org/z/Yx7b1d this still fails with "x86-64 gcc (trunk)".
Moreover, several releases are affected: 11.1, 11.2, 11.3, 12.1, 12.2.