[Bug tree-optimization/96758] New: strncmp miscompiles as memcmp

[Bug tree-optimization/96758] New: strncmp miscompiles as memcmp

[gcc-bugs at vgkmb dot com]

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

            Bug ID: 96758
           Summary: strncmp miscompiles as memcmp
           Product: gcc
           Version: 10.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gcc-bugs at vgkmb dot com
  Target Milestone: ---

Created attachment 49106
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49106&action=edit
strncmp test program

strncmp(x, y, n) == 0 generates the wrong code under -O2 when:
- n is a constant power of two
- x is a non-constant buffer of size > n with runtime content
- y is "c ? a : b" where
- c is a non-constant condition
- and a and b are constant strings with lengths < n

Actual code: equivalent to memcmp(x, y, n) == 0 but is incorrect since neither
string is guaranteed to be at least n characters long.

Expected code: strncmp library call or inlined equivalent.

Host/target: x86_64-pc-linux-gnu
OS: Fedora 32 Linux 5.7.16-200.fc32.x86_64

Reduced from case found in smartmontools-7.1 compiled by the distro provided
compiler gcc (GCC) 10.2.1 20200723 (Red Hat 10.2.1-1).

#include <string.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
    const char *s = argc > 0 ? "a" : "b";
    char x[5];
    char y[5] = "a\0a";
    memcpy(x, y, sizeof(y));
    printf("%d\n", !strncmp(x, s, 4));
    return 0;
}

Compiled as "gcc -O2 test.c" this prints "0" but should print "1" (and does
without -O2).

I confirmed via gcc.godbolt.org that it was OK in 9.3 but broken in 10 onward:
https://gcc.godbolt.org/z/e37fsP

I reproduced locally on the same system with latest main branch at 87c753ac
configured and built with defaults.

Then I bisected from tag releases/gcc-9.3.0 on and found the first bad commit
27c14dbc6b (SVN r277076) whose title seems related:

    PR tree-optimization/91996 - fold non-constant strlen relational
expressions

For the bisects I configured with --enable-languages=c --disable-multilib
--disable-bootstrap to speed up testing.

Please find attached preprocessed repro source for the case above. Expected
output is "1" (confirmed by compiling without -O2).

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-08-24
      Known to work|                            |9.3.0
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |marxin at gcc dot gnu.org,
                   |                            |msebor at gcc dot gnu.org
     Ever confirmed|0                           |1
           Keywords|                            |wrong-code
            Summary|strncmp miscompiles as      |[10/11 Regression] strncmp
                   |memcmp                      |miscompiles as memcmp since
                   |                            |r10-3920-g27c14dbc6b01d5b7
      Known to fail|                            |10.2.0, 11.0
             Status|UNCONFIRMED                 |NEW
           Priority|P3                          |P1

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Thank you for the report. It really started with r10-3920-g27c14dbc6b01d5b7.

Slightly modified test-case:

$ cat pr96758.c
int main(int argc, char *argv[]) {
    const char *s = argc > 0 ? "a" : "b";
    char x[5];
    char y[5] = "a\0a";
    __builtin_memcpy(x, y, sizeof(y));
    if (__builtin_strncmp(x, s, 4) != 0)
      __builtin_abort ();
    return 0;
}

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |10.3
           Priority|P1                          |P2
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[jakub at gcc dot gnu.org]

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

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

Untested fix.  cmpsiz has been computed incorrectly and while the code had the
intent to handle the case where both strings have known constant string length,
that case actually wasn't handled.  That part IMHO shouldn't be backported.

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[gcc-bugs at vgkmb dot com]

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

--- Comment #3 from R. Evans <gcc-bugs at vgkmb dot com> ---
Thanks for the quick patch! Applied to head (87c753ac) and confirmed that it
passes the test case and fixes the problem with smartmontools-7.1.

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 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:f982a6ec9b6d98f5f37114b1d7455c54ce5056b8

commit r11-2839-gf982a6ec9b6d98f5f37114b1d7455c54ce5056b8
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Aug 25 13:47:10 2020 +0200

    strlen: Fix handle_builtin_string_cmp [PR96758]

    The following testcase is miscompiled, because handle_builtin_string_cmp
    sees a strncmp call with constant last argument 4, where one of the strings
    has an upper bound of 5 bytes (due to it being an array of that size) and
    the other has a known string length of 1 and the result is used only in
    equality comparison.
    It is folded into __builtin_strncmp_eq (str1, str2, 4), which is
    incorrect, because that means reading 4 bytes from both strings and
    comparing that.  When one of the strings has known strlen of 1, we want to
    compare just 2 bytes, not 4, as strncmp shouldn't compare any bytes beyond
    the null.
    So, the last argument to __builtin_strncmp_eq should be the minimum of the
    provided strncmp last argument and the known string length + 1 (assuming
    the other string has only a known upper bound due to array size).

    Besides that, I've noticed the code has been written with the intent to
also
    support the case where we know exact string length of both strings (but not
    the string content, so we can't compute it at compile time).  In that case,
    both cstlen1 and cstlen2 are non-negative and both arysiz1 and arysiz2 are
    negative.  We wouldn't optimize that, cmpsiz would be either the strncmp
    last argument, or for strcmp the first string length, but varsiz would be
    -1 and thus cmpsiz would be never < varsiz.  The patch fixes it by using
the
    correct length, in that case using the minimum of the two and for strncmp
    also the last argument.

    2020-08-25  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/96758
            * tree-ssa-strlen.c (handle_builtin_string_cmp): If both cstlen1
            and cstlen2 are set, set cmpsiz to their minimum, otherwise use the
            one that is set.  If bound is used and smaller than cmpsiz, set
cmpsiz
            to bound.  If both cstlen1 and cstlen2 are set, perform the
optimization.

            * gcc.dg/strcmpopt_12.c: New test.

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:0dbfa88edafbe913a7a9099246041e0190aa3948

commit r10-8670-g0dbfa88edafbe913a7a9099246041e0190aa3948
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Aug 25 13:47:10 2020 +0200

    strlen: Fix handle_builtin_string_cmp [PR96758]

    The following testcase is miscompiled, because handle_builtin_string_cmp
    sees a strncmp call with constant last argument 4, where one of the strings
    has an upper bound of 5 bytes (due to it being an array of that size) and
    the other has a known string length of 1 and the result is used only in
    equality comparison.
    It is folded into __builtin_strncmp_eq (str1, str2, 4), which is
    incorrect, because that means reading 4 bytes from both strings and
    comparing that.  When one of the strings has known strlen of 1, we want to
    compare just 2 bytes, not 4, as strncmp shouldn't compare any bytes beyond
    the null.
    So, the last argument to __builtin_strncmp_eq should be the minimum of the
    provided strncmp last argument and the known string length + 1 (assuming
    the other string has only a known upper bound due to array size).

    Besides that, I've noticed the code has been written with the intent to
also
    support the case where we know exact string length of both strings (but not
    the string content, so we can't compute it at compile time).  In that case,
    both cstlen1 and cstlen2 are non-negative and both arysiz1 and arysiz2 are
    negative.  We wouldn't optimize that, cmpsiz would be either the strncmp
    last argument, or for strcmp the first string length, but varsiz would be
    -1 and thus cmpsiz would be never < varsiz.  The patch fixes it by using
the
    correct length, in that case using the minimum of the two and for strncmp
    also the last argument.

    2020-08-25  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/96758
            * tree-ssa-strlen.c (handle_builtin_string_cmp): If both cstlen1
            and cstlen2 are set, set cmpsiz to their minimum, otherwise use the
            one that is set.  If bound is used and smaller than cmpsiz, set
cmpsiz
            to bound.  If both cstlen1 and cstlen2 are set, perform the
optimization.

            * gcc.dg/strcmpopt_12.c: New test.

    (cherry picked from commit f982a6ec9b6d98f5f37114b1d7455c54ce5056b8)

[Bug tree-optimization/96758] [10/11 Regression] strncmp miscompiles as memcmp since r10-3920-g27c14dbc6b01d5b7

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 10.3+ and 11+.