[Bug c++/111019] New: Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[Bug c++/111019] New: Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[boskidialer at gmail dot com]

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

            Bug ID: 111019
           Summary: Optimizer incorrectly assumes variable is not changed
                    while change happens through another pointer
           Product: gcc
           Version: 12.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: boskidialer at gmail dot com
  Target Milestone: ---

Created attachment 55737
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55737&action=edit
Smallest reproduction i managed to create

Hello,

I was investigating one of the tests failures in the product, test failure that
only happens while compiling with -O3 or -O2, but one that does not happen with
-O1 or when not using any optimization.

GCC Version:

dashboard@dashboard-desktop:~$ /usr/bin/g++ -v
Using built-in specs.
COLLECT_GCC=/usr/bin/g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/12/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu
12.3.0-1ubuntu1~23.04' --with-bugurl=file:///usr/share/doc/gcc-12/README.Bugs
--enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr
--with-gcc-major-version-only --program-suffix=-12
--program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug
--enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new
--enable-gnu-unique-object --disable-vtable-verify --enable-plugin
--enable-default-pie --with-system-zlib --enable-libphobos-checking=release
--with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch
--disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64
--with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic
--enable-offload-targets=nvptx-none=/build/gcc-12-DAPbBt/gcc-12-12.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-12-DAPbBt/gcc-12-12.3.0/debian/tmp-gcn/usr
--enable-offload-defaulted --without-cuda-driver --enable-checking=release
--build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.3.0 (Ubuntu 12.3.0-1ubuntu1~23.04)

Reproduction:

/usr/bin/g++ gcc-err.cpp -O3 -o gcc-err.out && ./gcc-err.out

(gcc-err.cpp is provided as the attachment to the bug report).

Issue is that generated output freezes when compiled it under -O3 or -O2 but
not when compiling under -O1 or without any optimizations.

Just in case to verify the issue is not on my end, i pasted the reproduction
code and required compiler flags onto a godbolt:
https://godbolt.org/z/Ez7vrz77W - and it shows that the compiled program times
out. This is a confirmation that the generated output is stuck. After changing
the compiler options on the right side on the godbolt site to -O1, the code
compiles as well but the executable now correctly finishes within time limit
and outputs a single line "test".

Based on the debugging i did on this code, it looks to be related to the
Target::~Target code where there is the `whlie (this->next)` loop where i
suspect compiler or optimizer incorrectly assumes that value of `this->next` is
unchanged between iterations however that is not true because in this case
there is `n` variable set to `this->next` which points to a second item in the
double linked list, which means `n->previous == this` and as such
`n->previous->next = ...` line is effectively changing value of the
`this->next`, but indirectly.

When generating the assembly from the given reproduction using `/usr/bin/g++
-masm=intel gcc-err.cpp -O3 -S -o gcc-err.S`, instructions produced seem to be
incorrect as they are missing the repeated checks if the value of `this->next`
was changed in the next iteration:

.L21:
        mov     rcx, QWORD PTR [rax]
        mov     rdx, QWORD PTR 8[rax]
        test    rcx, rcx
        je      .L19                   // if (n->previous)
        mov     QWORD PTR 8[rcx], rdx
        mov     rdx, QWORD PTR 8[rax]  //   n->previous->next = n->next;
.L19:
        test    rdx, rdx
        je      .L20                   // if (n->next)
        mov     QWORD PTR [rdx], rcx   //   n->next->previous = n->previous;
.L20:
        xor     edx, edx
        movups  XMMWORD PTR [rax], xmm0
        mov     QWORD PTR 16[rax], rdx
        jmp     .L21

When any external function calls, barrier instructions (like 'asm
volatile("":::"memory")') or more complex code is added, the loop produces the
correct code:

.L18:
        mov     rax, QWORD PTR 8[rbx]
        test    rax, rax
        je      .L74                   // quits the loop if `this->next ==
nullptr`
        mov     rcx, QWORD PTR [rax]
        mov     rdx, QWORD PTR 8[rax]
        test    rcx, rcx
        je      .L19                   // if (n->previous)
        mov     QWORD PTR 8[rcx], rdx
        mov     rdx, QWORD PTR 8[rax]  //   n->previous->next = n->next;
.L19:
        test    rdx, rdx
        je      .L20                   // if (n->next)
        mov     QWORD PTR [rdx], rcx   //   n->next->previous = n->previous;
.L20:
        xor     edx, edx
        movups  XMMWORD PTR [rax], xmm0
        mov     QWORD PTR 16[rax], rdx

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.4
     Ever confirmed|0                           |1
            Summary|Optimizer incorrectly       |[12/13/14 Regression]
                   |assumes variable is not     |Optimizer incorrectly
                   |changed while change        |assumes variable is not
                   |happens through another     |changed while change
                   |pointer                     |happens through another
                   |                            |pointer
           Keywords|                            |alias, needs-bisection,
                   |                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-08-15

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
I can confirm this with -O3 (but not -O2), even when adding
-fno-tree-loop-optimize.  -fno-strict-aliasing avoids the issue (but I can't
see anything
obviously wrong in the sources).  The requirement for the bug to show up
is inlining Target::~Target, marking it always_inline makes the bug
appear at -O2 or -O1 -fstrict-aliasing as well.  The bug is we endlessly
loop in the Target::~Target loop.

Needs further analysis, bisection might help.

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppalka at gcc dot gnu.org
           Keywords|needs-bisection             |

--- Comment #2 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Bisection points to r12-4319-g09a0affdb0598a

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenther at suse dot de]

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

--- Comment #3 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 15 Aug 2023, ppalka at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111019
> 
> Patrick Palka <ppalka at gcc dot gnu.org> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |ppalka at gcc dot gnu.org
>            Keywords|needs-bisection             |
> 
> --- Comment #2 from Patrick Palka <ppalka at gcc dot gnu.org> ---
> Bisection points to r12-4319-g09a0affdb0598a

Huh, that should make us optimize less ... (it was also backported
to GCC 11).  Having a good/bad rev should make it easier to analyze
though - thanks.

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[boskidialer at gmail dot com]

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

--- Comment #4 from Sławomir Fraś <boskidialer at gmail dot com> ---
Not sure if that hints at the possible cause, when i extracted `this` variable
out of the loop to something like this (https://godbolt.org/z/8ebb5E1qG):

    Target* first = this;
    while (first->next)
    {
      Base* n = first->next;

Then the code behaves the same as faulty code, but when i changed it into this
(https://godbolt.org/z/7o58Y4fEq):

    Base* first = this; // only change: Target -> Base
    while (first->next)
    {
      Base* n = first->next;

Then the code works fine even with the `always_inline` on the destructor. In
this case it looks like write to `Base::next` member is not considered as
invalidating value of `Target::next` in register even when it should since
Target derives from the Base class.

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will investigate further.

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #3)
> On Tue, 15 Aug 2023, ppalka at gcc dot gnu.org wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111019
> > 
> > Patrick Palka <ppalka at gcc dot gnu.org> changed:
> > 
> >            What    |Removed                     |Added
> > ----------------------------------------------------------------------------
> >                  CC|                            |ppalka at gcc dot gnu.org
> >            Keywords|needs-bisection             |
> > 
> > --- Comment #2 from Patrick Palka <ppalka at gcc dot gnu.org> ---
> > Bisection points to r12-4319-g09a0affdb0598a
> 
> Huh, that should make us optimize less ... (it was also backported
> to GCC 11).  Having a good/bad rev should make it easier to analyze
> though - thanks.

Indeed it does, optimizing more simply avoids the bug somehow.

The bug is that we think this->next is invariant in the loop, thus
n->next = nullptr cannot possibly clobber it.  LIM2 hoists it out of
the loop.

The accesses are

  [t.C:18:18] # PT = nonlocal escaped null { D.43517 D.43765 D.53227 D.53358
D.53446 } (escaped, escaped heap)
  _77 = [t.C:18:18] __MEM <struct Target> ((struct Target *)_26).D_43475.next;

vs.

  [t.C:27:15] [t.C:27:10] _170->next = _Literal (struct Base *) 0;

where _170 is of type (struct Base *). and

  # PT = nonlocal escaped null { D.43517 D.43765 D.53227 D.53358 D.53446 }
(escaped, escaped heap)
  _170 = __PHI ([t.C:18:18] __BB46: _77, [t.C:18:18] __BB45: _20);

-fno-tree-loop-im fixes this at any optimization level.

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
And what in the end disambiguates this in LIM is aliasing_component_refs_p.
Note that LIM feeds it canonicalized __MEM <struct Target> ((struct Target
*)_26).D_43475.next, it instead uses MEM[(struct Base * *)_26 + 8B].

I think it goes wrong because LIM canonicalizes _26->...next which is a
ref at offset 8 to MEM[_26 + 8] _at offset 8_, the base is actually
recorded as MEM[_26] but get_ref_base_and_extent wouldn't get 8 out of
MEM[_26 + 8] and aliasing_matching_component_refs_p re-does that to adjust
the offset which in the end leads to some inconsistency.

What LIM tries to do is find a canonical representation for the ref which
is MEM[_26 + 8B], it also tries to preserve the base which is MEM[_26],
but that's somewhat in conflict here.  It works for LIMs purposes but as
can be seen it doesn't work here.

The bad thing is that there isn't a consistent representation for this,
but also aliasing_matching_component_refs_p relying on this is bad?

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
So really caused by r9-4993-g1c852d1d7096a8 plus all the followups that went
into this code.  One triggering fact is that operand_equal_p
of MEM[(struct Target *)_26].D.43475.next with itself is false ...

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #8)
> So really caused by r9-4993-g1c852d1d7096a8 plus all the followups that went
> into this code.  One triggering fact is that operand_equal_p
> of MEM[(struct Target *)_26].D.43475.next with itself is false ...

Ah, because one has BASE/CLIQUE and one does not.

[Bug c++/111019] [12/13/14 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:745ec2135aabfbe2c0fb7780309837d17e8986d4

commit r14-3325-g745ec2135aabfbe2c0fb7780309837d17e8986d4
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Aug 17 15:21:33 2023 +0200

    tree-optimization/111019 - invariant motion and aliasing

    The following fixes a bad choice in representing things to the alias
    oracle by LIM which while correct in pieces is inconsistent with itself.
    When canonicalizing a ref to a bare deref instead of leaving the base
    object and the extracted offset the same and just substituting an
    alternate ref the following replaces the base and the offset as well,
    avoiding the confusion that otherwise will arise in
    aliasing_matching_component_refs_p.

            PR tree-optimization/111019
            * tree-ssa-loop-im.cc (gather_mem_refs_stmt): When canonicalizing
            also scrap base and offset in case the ref is indirect.

            * g++.dg/torture/pr111019.C: New testcase.

[Bug c++/111019] [12/13 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12/13/14 Regression]       |[12/13 Regression]
                   |Optimizer incorrectly       |Optimizer incorrectly
                   |assumes variable is not     |assumes variable is not
                   |changed while change        |changed while change
                   |happens through another     |happens through another
                   |pointer                     |pointer
      Known to work|                            |14.0

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.  The change picks to the GCC 12 branch just fine, can you
maybe validate the change on the complete testcase?

[Bug c++/111019] [12/13 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[boskidialer at gmail dot com]

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

--- Comment #12 from Sławomir Fraś <boskidialer at gmail dot com> ---
$ /opt/gcc-745ec1/bin/g++ -v
Using built-in specs.
COLLECT_GCC=/opt/gcc-745ec1/bin/g++
COLLECT_LTO_WRAPPER=/opt/gcc-745ec1/libexec/gcc/x86_64-pc-linux-gnu/14.0.0/lto-w
                                                                             
rapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc/configure --prefix=/opt/gcc-745ec1
--enable-languages=c,                                                          
                    c++,fortran,go --disable-multilib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 14.0.0 20230818 (experimental) (GCC)

With the above version i was unable to reproduce the issue using the full tests
suite, in that sense i am considering this issue to be resolved.

Only issue that i was facing here was caused by the usage of gcc 14.0 instead
of gcc 12.3 so i had to suppress following warning:

/home/dashboard/factorio/libraries/Agui/GenericTargetable.hpp:55:18: error:
storing the address of local variable ‘helper’ in
‘*&this_5(D)->D.195240.D.130047.D.129358.agui::GenericTargetable::agui::GenericTargetBase.agui::GenericTargetBase::next’
[-Werror=dangling-pointer=]

Basically we are using local variables which are registering in some heap
allocated classes temporarily but they are aware of that so in the destructor
they correctly unlink themselves to avoid heap allocated objects from having
pointers to deallocated local variables. This check is a false positive that
does not work in our project so i had to suppress it. I think this may be a
separate thing so in order to not pollute this bug report i wont provide more
details unless you want more of it.

[Bug c++/111019] [12/13 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

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

commit r13-7753-gc1b5514124ab7a8aceec1ae4a82d2149fc687ecf
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Aug 17 15:21:33 2023 +0200

    tree-optimization/111019 - invariant motion and aliasing

    The following fixes a bad choice in representing things to the alias
    oracle by LIM which while correct in pieces is inconsistent with itself.
    When canonicalizing a ref to a bare deref instead of leaving the base
    object and the extracted offset the same and just substituting an
    alternate ref the following replaces the base and the offset as well,
    avoiding the confusion that otherwise will arise in
    aliasing_matching_component_refs_p.

            PR tree-optimization/111019
            * tree-ssa-loop-im.cc (gather_mem_refs_stmt): When canonicalizing
            also scrap base and offset in case the ref is indirect.

            * g++.dg/torture/pr111019.C: New testcase.

    (cherry picked from commit 745ec2135aabfbe2c0fb7780309837d17e8986d4)

[Bug tree-optimization/111019] [12 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

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

commit r12-10010-gb66fd93a60d429f97ca5fdfb9a88f291c605d002
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Aug 17 15:21:33 2023 +0200

    tree-optimization/111019 - invariant motion and aliasing

    The following fixes a bad choice in representing things to the alias
    oracle by LIM which while correct in pieces is inconsistent with itself.
    When canonicalizing a ref to a bare deref instead of leaving the base
    object and the extracted offset the same and just substituting an
    alternate ref the following replaces the base and the offset as well,
    avoiding the confusion that otherwise will arise in
    aliasing_matching_component_refs_p.

            PR tree-optimization/111019
            * tree-ssa-loop-im.cc (gather_mem_refs_stmt): When canonicalizing
            also scrap base and offset in case the ref is indirect.

            * g++.dg/torture/pr111019.C: New testcase.

    (cherry picked from commit 745ec2135aabfbe2c0fb7780309837d17e8986d4)

[Bug tree-optimization/111019] [12 Regression] Optimizer incorrectly assumes variable is not changed while change happens through another pointer

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
      Known to work|                            |12.3.1

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.