[Bug c/108789] New: __builtin_(add|mul)_overflow methods generate duplicate operations if both operands are const

[Bug c/108789] New: __builtin_(add|mul)_overflow methods generate duplicate operations if both operands are const

[dpejesh at yahoo dot com]

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

            Bug ID: 108789
           Summary: __builtin_(add|mul)_overflow methods generate
                    duplicate operations if both operands are const
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dpejesh at yahoo dot com
  Target Milestone: ---

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

bool add(uint8_t *r, const uint8_t *a, const uint8_t *b) {
  return __builtin_add_overflow(*a, *b, r);
}

bool mul(uint8_t *r, const uint8_t *a, const uint8_t *b) {
  return __builtin_mul_overflow(*a, *b, r);
}

int main() {
  uint8_t x;

  /* 64 + 64 should not overflow */
  x = 64;
  if (add(&x, &x, &x))
    printf("false positive: x=%i\n", x);

  /* 4 * 4 should not overflow */
  x = 4;
  if (mul(&x, &x, &x))
    printf("false positive: x=%i\n", x);

  /* 128 + 128 should overflow */
  x = 128;
  if (!add(&x, &x, &x))
    printf("false negative: x=%i\n", x);

  /* 16 * 16 should overflow */
  x = 16;
  if (!mul(&x, &x, &x))
    printf("false negative: x=%i\n", x);

  return 0;
}

$ gcc -g3 -O1 -o test test.c; ./test
false positive: x=128
false positive: x=16
false negative: x=0
false negative: x=0

The generated assembly correctly adds a with b and stores in r but
then it does the operation again before testing for carry and
returning.  If r is also one of the operands then the erroneous
second operation will use the computed value of r in place of the
original operand leading to an incorrect overflow result.

0000000000400895 <add>:
;   return __builtin_add_overflow(*a, *b, r);
  400895: 0f b6 02                      movzbl  (%rdx), %eax
  400898: 02 06                         addb    (%rsi), %al
  40089a: 88 07                         movb    %al, (%rdi)
  40089c: 0f b6 02                      movzbl  (%rdx), %eax  <<
  40089f: 02 06                         addb    (%rsi), %al   <<
  4008a1: 0f 92 c0                      setb    %al
; }
  4008a4: c3                            retq

00000000004008a5 <mul>:
;   return __builtin_mul_overflow(*a, *b, r);
  4008a5: 0f b6 06                      movzbl  (%rsi), %eax
  4008a8: f6 22                         mulb    (%rdx)
  4008aa: 88 07                         movb    %al, (%rdi)
  4008ac: 0f b6 06                      movzbl  (%rsi), %eax  <<
  4008af: f6 22                         mulb    (%rdx)        <<
  4008b1: 0f 90 c0                      seto    %al
; }
  4008b4: c3                            retq

This only seems to be triggered when both a *and* b are const.
Removing const from either or both operands generates the correct
assembly.

0000000000400855 <add>:
;   return __builtin_add_overflow(*a, *b, r);
  400855: 0f b6 02                      movzbl  (%rdx), %eax
  400858: 02 06                         addb    (%rsi), %al
  40085a: 88 07                         movb    %al, (%rdi)
  40085c: 0f 92 c0                      setb    %al
; }
  40085f: c3                            retq

0000000000400860 <mul>:
;   return __builtin_mul_overflow(*a, *b, r);
  400860: 0f b6 06                      movzbl  (%rsi), %eax
  400863: f6 22                         mulb    (%rdx)
  400865: 88 07                         movb    %al, (%rdi)
  400867: 0f 90 c0                      seto    %al
; }
  40086a: c3                            retq

Tested on the following systems:

$ uname -srm; gcc12 --version
FreeBSD 13.1-RELEASE-p2 amd64
gcc12 (FreeBSD Ports Collection) 12.2.0

$ uname -smr; gcc --version
Linux 6.1.2-1-MANJARO-ARM aarch64
gcc (GCC) 12.1.0

$ uname -srm; gcc --version
MINGW64_NT-10.0-22000 3.4.5.x86_64 x86_64
gcc.exe (Rev10, Built by MSYS2 project) 12.2.0

Poking around godbolt indicates this was likely introduced in 9.4.

[Bug middle-end/108789] __builtin_(add|mul)_overflow methods generate duplicate operations if both operands are const

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |middle-end

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The middle-end is not adding a SAVE_EXPR in the const case which causes the
duplication which is not optimized back.

[Bug middle-end/108789] __builtin_(add|mul)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|__builtin_(add|mul)_overflo |__builtin_(add|mul)_overflo
                   |w methods generate          |w methods generate
                   |duplicate operations if     |duplicate operations if
                   |both operands are const     |both operands are const
                   |                            |which in turn causes wrong
                   |                            |code due to overlapping
                   |                            |arguments
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-11-09

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.

The obvious workaround is to use a temporary variables for the arguments of
__builtin_add_overflow .

[Bug middle-end/108789] __builtin_(add|mul)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |cody at tapscott dot me

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 115326 has been marked as a duplicate of this bug. ***

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note the missing SAVE_EXPR issue is similar to PR 52339 (which has a patch
attached to it that would fix the issue here too I think).

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 58336
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58336&action=edit
gcc15-pr108789.patch

Untested fix.

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 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:b8e28381cb5c0cddfe5201faf799d8b27f5d7d6c

commit r15-1009-gb8e28381cb5c0cddfe5201faf799d8b27f5d7d6c
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 12:28:01 2024 +0200

    builtins: Force SAVE_EXPR for __builtin_{add,sub,mul}_overflow and
__builtin{add,sub}c [PR108789]

    The following testcase is miscompiled, because we use save_expr
    on the .{ADD,SUB,MUL}_OVERFLOW call we are creating, but if the first
    two operands are not INTEGER_CSTs (in that case we just fold it right away)
    but are TREE_READONLY/!TREE_SIDE_EFFECTS, save_expr doesn't actually
    create a SAVE_EXPR at all and so we lower it to
    *arg2 = REALPART_EXPR (.ADD_OVERFLOW (arg0, arg1)), \
    IMAGPART_EXPR (.ADD_OVERFLOW (arg0, arg1))
    which evaluates the ifn twice and just hope it will be CSEd back.
    As *arg2 aliases *arg0, that is not the case.
    The builtins are really never const/pure as they store into what
    the third arguments points to, so after handling the
INTEGER_CST+INTEGER_CST
    case, I think we should just always use SAVE_EXPR.  Just building SAVE_EXPR
    by hand and setting TREE_SIDE_EFFECTS on it doesn't work, because
    c_fully_fold optimizes it away again, so the following patch marks the
    ifn calls as TREE_SIDE_EFFECTS (but doesn't do it for the
    __builtin_{add,sub,mul}_overflow_p case which were designed for use
    especially in constant expressions and don't really evaluate the
    realpart side, so we don't really need a SAVE_EXPR in that case).

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/108789
            * builtins.cc (fold_builtin_arith_overflow): For ovf_only,
            don't call save_expr and don't build REALPART_EXPR, otherwise
            set TREE_SIDE_EFFECTS on call before calling save_expr.
            (fold_builtin_addc_subc): Set TREE_SIDE_EFFECTS on call before
            calling save_expr.

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

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 15.1+ so far.

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r14-10279-gf9af4a05e027a8b797628f1a2c39ef0b28dc36d9
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 12:28:01 2024 +0200

    builtins: Force SAVE_EXPR for __builtin_{add,sub,mul}_overflow and
__builtin{add,sub}c [PR108789]

    The following testcase is miscompiled, because we use save_expr
    on the .{ADD,SUB,MUL}_OVERFLOW call we are creating, but if the first
    two operands are not INTEGER_CSTs (in that case we just fold it right away)
    but are TREE_READONLY/!TREE_SIDE_EFFECTS, save_expr doesn't actually
    create a SAVE_EXPR at all and so we lower it to
    *arg2 = REALPART_EXPR (.ADD_OVERFLOW (arg0, arg1)), \
    IMAGPART_EXPR (.ADD_OVERFLOW (arg0, arg1))
    which evaluates the ifn twice and just hope it will be CSEd back.
    As *arg2 aliases *arg0, that is not the case.
    The builtins are really never const/pure as they store into what
    the third arguments points to, so after handling the
INTEGER_CST+INTEGER_CST
    case, I think we should just always use SAVE_EXPR.  Just building SAVE_EXPR
    by hand and setting TREE_SIDE_EFFECTS on it doesn't work, because
    c_fully_fold optimizes it away again, so the following patch marks the
    ifn calls as TREE_SIDE_EFFECTS (but doesn't do it for the
    __builtin_{add,sub,mul}_overflow_p case which were designed for use
    especially in constant expressions and don't really evaluate the
    realpart side, so we don't really need a SAVE_EXPR in that case).

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/108789
            * builtins.cc (fold_builtin_arith_overflow): For ovf_only,
            don't call save_expr and don't build REALPART_EXPR, otherwise
            set TREE_SIDE_EFFECTS on call before calling save_expr.
            (fold_builtin_addc_subc): Set TREE_SIDE_EFFECTS on call before
            calling save_expr.

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

    (cherry picked from commit b8e28381cb5c0cddfe5201faf799d8b27f5d7d6c)

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r13-8836-gf9db8b0571348adfcc98204ea7be787058af85cd
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 12:28:01 2024 +0200

    builtins: Force SAVE_EXPR for __builtin_{add,sub,mul}_overflow [PR108789]

    The following testcase is miscompiled, because we use save_expr
    on the .{ADD,SUB,MUL}_OVERFLOW call we are creating, but if the first
    two operands are not INTEGER_CSTs (in that case we just fold it right away)
    but are TREE_READONLY/!TREE_SIDE_EFFECTS, save_expr doesn't actually
    create a SAVE_EXPR at all and so we lower it to
    *arg2 = REALPART_EXPR (.ADD_OVERFLOW (arg0, arg1)), \
    IMAGPART_EXPR (.ADD_OVERFLOW (arg0, arg1))
    which evaluates the ifn twice and just hope it will be CSEd back.
    As *arg2 aliases *arg0, that is not the case.
    The builtins are really never const/pure as they store into what
    the third arguments points to, so after handling the
INTEGER_CST+INTEGER_CST
    case, I think we should just always use SAVE_EXPR.  Just building SAVE_EXPR
    by hand and setting TREE_SIDE_EFFECTS on it doesn't work, because
    c_fully_fold optimizes it away again, so the following patch marks the
    ifn calls as TREE_SIDE_EFFECTS (but doesn't do it for the
    __builtin_{add,sub,mul}_overflow_p case which were designed for use
    especially in constant expressions and don't really evaluate the
    realpart side, so we don't really need a SAVE_EXPR in that case).

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/108789
            * builtins.cc (fold_builtin_arith_overflow): For ovf_only,
            don't call save_expr and don't build REALPART_EXPR, otherwise
            set TREE_SIDE_EFFECTS on call before calling save_expr.

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

    (cherry picked from commit b8e28381cb5c0cddfe5201faf799d8b27f5d7d6c)

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:91a371254494934e191e3060ae2a86905eb4b2b2

commit r12-10532-g91a371254494934e191e3060ae2a86905eb4b2b2
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 12:28:01 2024 +0200

    builtins: Force SAVE_EXPR for __builtin_{add,sub,mul}_overflow [PR108789]

    The following testcase is miscompiled, because we use save_expr
    on the .{ADD,SUB,MUL}_OVERFLOW call we are creating, but if the first
    two operands are not INTEGER_CSTs (in that case we just fold it right away)
    but are TREE_READONLY/!TREE_SIDE_EFFECTS, save_expr doesn't actually
    create a SAVE_EXPR at all and so we lower it to
    *arg2 = REALPART_EXPR (.ADD_OVERFLOW (arg0, arg1)), \
    IMAGPART_EXPR (.ADD_OVERFLOW (arg0, arg1))
    which evaluates the ifn twice and just hope it will be CSEd back.
    As *arg2 aliases *arg0, that is not the case.
    The builtins are really never const/pure as they store into what
    the third arguments points to, so after handling the
INTEGER_CST+INTEGER_CST
    case, I think we should just always use SAVE_EXPR.  Just building SAVE_EXPR
    by hand and setting TREE_SIDE_EFFECTS on it doesn't work, because
    c_fully_fold optimizes it away again, so the following patch marks the
    ifn calls as TREE_SIDE_EFFECTS (but doesn't do it for the
    __builtin_{add,sub,mul}_overflow_p case which were designed for use
    especially in constant expressions and don't really evaluate the
    realpart side, so we don't really need a SAVE_EXPR in that case).

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/108789
            * builtins.cc (fold_builtin_arith_overflow): For ovf_only,
            don't call save_expr and don't build REALPART_EXPR, otherwise
            set TREE_SIDE_EFFECTS on call before calling save_expr.

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

    (cherry picked from commit b8e28381cb5c0cddfe5201faf799d8b27f5d7d6c)

[Bug middle-end/108789] __builtin_(add|mul|sub)_overflow methods generate duplicate operations if both operands are const which in turn causes wrong code due to overlapping arguments

[jakub at gcc dot gnu.org]

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Should be fixed for 12.4+, 13.4+ and 14.2+ too.