[Bug tree-optimization/115033] New: Incorrect optimization of by-reference closure fields by fre1 pass

[Bug tree-optimization/115033] New: Incorrect optimization of by-reference closure fields by fre1 pass

[sleepy.iron2888 at fastmail dot com]

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

            Bug ID: 115033
           Summary: Incorrect optimization of by-reference closure fields
                    by fre1 pass
           Product: gcc
           Version: 12.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sleepy.iron2888 at fastmail dot com
  Target Milestone: ---

## Description

I am seeing a wrong answer produced by code involving a by-reference captured
boolean value in a lambda. The code looks like the following:

```cpp
// Compute result shape
bool resultIsStatic = true;
auto resultShape = llvm::map_to_vector(newShape, [&](int64_t size) {
    // This branch is taken, but the update to resultIsStatic is not
    // propagated to the usage outside of the lambda.
    if (!inputIsStatic) {
      resultIsStatic = false;
      return ShapedType::kDynamic;
    }

        // do something else
});

// This branch is never taken
if (resultIsStatic) {
    // do the right thing
    return;
}

// do the wrong thing
return;
```

In the failing example, a lambda is mapped across a range of values, producing
a new vector-like container. During the map, the `resultIsStatic` value
captured by reference is updated in the lambda, and that updated value is not
reflected in the later usage of `resultIsStatic`.

## Analysis

The attached pre-processed source file is still large, so I just want to narrow
down where I think the problem is. The mal-optimization occurs in the
`inferReshapeExpandedType` function at the end of the pre-processed source
file.

Looking at the dumped IR, I believe the bug is introduced by the `fre1` pass. I
see between `ealias` and `fre1` that the branch on the value of
`resultIsStatic` is eliminated. This seems a likely cause for the bug I am
seeing, but I am not very familiar with GCC's IR.

## GCC Invocation

Full command producing the issue:

```
g++ -O2 -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden
-Werror=date-time -fno-lifetime-dse -Wall -Wextra -Wno-unused-parameter
-Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic
-Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-nonnull
-Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move
-Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment
-Wno-misleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color
-ffunction-sections -fdata-sections -Wundef -O2 -std=c++17  -fno-exceptions
-funwind-tables -fno-rtti -c <source-file>
```

For reference, this bug is affecting parts of LLVM, the pull request with the
workaround and description of the problem can be found here:
https://github.com/llvm/llvm-project/pull/91521

## GCC -v and System Information

This bug is reproducible in GCC 12 and GCC 13. I was unable to reproduce in GCC
11.

The GCC versions below are taken from a NixOS machine used to reproduce the bug
and track it down. It also reproduces on Debian with GCC 12. I can provide that
information as well if it will be helpful.

GCC 12 `-v` output:

```
Using built-in specs.
COLLECT_GCC=/nix/store/7b2bbh09d569jb60j3vc5icjr3wdhw3m-gcc-12.3.0/bin/gcc
COLLECT_LTO_WRAPPER=/nix/store/7b2bbh09d569jb60j3vc5icjr3wdhw3m-gcc-12.3.0/libexec/gcc/x86_64-unknown-linux-gnu/12.3.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../gcc-12.3.0/configure
--prefix=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gcc-12.3.0
--with-gmp-include=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gmp-with-cxx-6.3.0-dev/include
--with-gmp-lib=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gmp-with-cxx-6.3.0/lib
--with-mpfr-include=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-mpfr-4.2.1-dev/include
--with-mpfr-lib=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-mpfr-4.2.1/lib
--with-mpc=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-libmpc-1.3.1
--with-native-system-header-dir=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-glibc-2.39-31-dev/include
--with-build-sysroot=/
--with-gxx-include-dir=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gcc-12.3.0/include/c++/12.3.0/
--program-prefix= --enable-lto --disable-libstdcxx-pch
--without-included-gettext --with-system-zlib --enable-static
--enable-languages=c,c++ --disable-multilib --enable-plugin
--with-isl=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-isl-0.20
--disable-bootstrap --build=x86_64-unknown-linux-gnu
--host=x86_64-unknown-linux-gnu --target=x86_64-unknown-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.3.0 (GCC)
```

GCC 13 `-v` output:

```
Using built-in specs.
COLLECT_GCC=/nix/store/9hgsinpfgyvsd92v0wlvmxv9wnaal68r-gcc-13.2.0/bin/gcc
COLLECT_LTO_WRAPPER=/nix/store/9hgsinpfgyvsd92v0wlvmxv9wnaal68r-gcc-13.2.0/libexec/gcc/x86_64-unknown-linux-gnu/13.2.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../gcc-13.2.0/configure
--prefix=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gcc-13.2.0
--with-gmp-include=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gmp-6.3.0-dev/include
--with-gmp-lib=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gmp-6.3.0/lib
--with-mpfr-include=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-mpfr-4.2.1-dev/include
--with-mpfr-lib=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-mpfr-4.2.1/lib
--with-mpc=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-libmpc-1.3.1
--with-native-system-header-dir=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-glibc-2.39-31-dev/include
--with-build-sysroot=/
--with-gxx-include-dir=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-gcc-13.2.0/include/c++/13.2.0/
--program-prefix= --enable-lto --disable-libstdcxx-pch
--without-included-gettext --with-system-zlib --enable-static
--enable-languages=c,c++ --disable-multilib --enable-plugin --disable-libcc1
--with-isl=/nix/store/eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee-isl-0.20
--disable-bootstrap --build=x86_64-unknown-linux-gnu
--host=x86_64-unknown-linux-gnu --target=x86_64-unknown-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.2.0 (GCC)
```

[Bug tree-optimization/115033] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-05-10
             Status|UNCONFIRMED                 |WAITING
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Please attach the preprocessed source rather than just a snippet of code.

[Bug tree-optimization/115033] Incorrect optimization of by-reference closure fields by fre1 pass

[sleepy.iron2888 at fastmail dot com]

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

--- Comment #2 from Spenser <sleepy.iron2888 at fastmail dot com> ---
Created attachment 58178
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58178&action=edit
Pre-processed C++ reproducer

[Bug tree-optimization/115033] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|1                           |0
             Status|WAITING                     |UNCONFIRMED

[Bug tree-optimization/115033] Incorrect optimization of by-reference closure fields by fre1 pass

[sleepy.iron2888 at fastmail dot com]

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

--- Comment #3 from Spenser <sleepy.iron2888 at fastmail dot com> ---
(In reply to Andrew Pinski from comment #1)
> Please attach the preprocessed source rather than just a snippet of code.

Sorry about that. Thought I added it when submitting the report, but I think
the file was too large. I've stripped out some of the dead code and reattached.

[Bug tree-optimization/115033] Incorrect optimization of by-reference closure fields by fre1 pass

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
                 CC|                            |hubicka at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

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

  resultIsStatic = 1;
  D.39198.__inputIsStatic = &inputIsStatic;
  D.39198.__resultIsStatic = &resultIsStatic;
  D.39198.__newShape = &newShape;
  D.39198.__totalSize = &totalSize;
  resultShape = llvm::map_to_vector<llvm::ArrayRef<long int>&,
inferReshapeExpandedType(llvm::ArrayRef<long int>, llvm::ArrayRef<long
int>)::<lambda(int64_t)> > (&newShape, &D.39198); [return slot optimization]
  D.39198 ={v} {CLOBBER(eol)};
  inputIsStatic.3_7 = inputIsStatic;
  _8 = ~inputIsStatic.3_7;
  if (inputIsStatic.3_7 != 0)
    goto <bb 14>; [INV]
  else
    goto <bb 10>; [INV]

  <bb 10> :
  resultIsStatic.4_9 = resultIsStatic;

I don't see how llvm::map_to_vector modifies 'resultIsStatic' so it seems
like a correct optimization to assume it is 1?  Or maybe I am misunderstanding
the call.  We end up in

struct SmallVector llvm::map_to_vector<llvm::ArrayRef<long int>&,
inferReshapeExpandedType(llvm::ArrayRef<long int>, llvm::ArrayRef<long
int>)::<lambda(int64_t)> > (struct ArrayRef & C, struct ._anon_81 & F)

where I can see a struct .anon_81 (that's from the lambda I guess).

The source seems to be

  bool resultIsStatic = true;
  auto resultShape = llvm::map_to_vector(newShape, [&](int64_t size) -> int64_t
{

    if (size >= 0)
      return size;

    if (!inputIsStatic) {
      resultIsStatic = false;
      return kDynamic;
...

so it might be interesting to try reducing it further.  I'll note that
using -fno-ipa-modref avoids FRE doing the CSE but -fno-strict-aliasing
doesn't.  So maybe it's a genuine modref bug.  IIRC there are some
that might be fixed in GCC 14 but not yet earlier.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.4
            Summary|Incorrect optimization of   |[12/13/14/15 Regression]
                   |by-reference closure fields |Incorrect optimization of
                   |by fre1 pass                |by-reference closure fields
                   |                            |by fre1 pass

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, GCC 14 was just released and the bug seems to reproduce there, too (if it
is a bug).

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.4                        |12.5

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 12.4 is being released, retargeting bugs to GCC 12.5.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Trying to reduce it ...

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58489
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58489&action=edit
First step at reducing

Keeps map_to_vector the same, changes the lamdba just to set resultIsStatic to
false and removes the rest of the function. (also removes some unused code
too).
Changes the to use __built_trap after the function call to make it easier to
test it.

The bug is still hit.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
If I manually inline map_range into map_to_vector, it works ...

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #9)
> If I manually inline map_range into map_to_vector, it works ...

I take that back, it still fails. I must have been testing something else.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #58489|0                           |1
        is obsolete|                            |

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58490
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58490&action=edit
Further

Removed SmallVector and ArrayRef.
Should have a run time test soon.

Note for this code, I need to add `-fno-early-inlining` to get the failure.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #58178|0                           |1
        is obsolete|                            |
  Attachment #58490|0                           |1
        is obsolete|                            |

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58491
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58491&action=edit
Runtime testcase

Works at -O0 and -O2 but fails at `-O2 -fno-early-inlining`.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2024-05-10 00:00:00         |2024-06-23
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed with my reduced testcase.

Note the header files are still needed, I didn't try to get rid of std::move or
std::forward just yet.
The other 2 header files are just for uint64_t/int64_t/size_t .

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58493
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58493&action=edit
Reduced all the way, removing std::forward/std::move

This now fails at -O2 (since I marked the functions that needed not to be
inlined).

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[pinskia at gcc dot gnu.org]

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

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58494
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58494&action=edit
Removing the lamdba and making it C

This is an alternative which removes the lamdba and makes it a GNU C testcase.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass

[sjames at gcc dot gnu.org]

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

Sam James <sjames at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=108250

--- Comment #16 from Sam James <sjames at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> so it might be interesting to try reducing it further.  I'll note that
> using -fno-ipa-modref avoids FRE doing the CSE but -fno-strict-aliasing
> doesn't.  So maybe it's a genuine modref bug.  IIRC there are some
> that might be fixed in GCC 14 but not yet earlier.

It also looks similar to one of the tblgen issues we had before but couldn't
make standalone.

[Bug tree-optimization/115033] [12/13/14/15 Regression] Incorrect optimization of by-reference closure fields by fre1 pass since r12-5113-gd70ef65692fced

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> ---
  int resultIsStatic = 1;
  func t ={&resultIsStatic};
  map_to_vector(&t);

  if (resultIsStatic)

we disambiguate the call against the load via modref data.  The call summary
for early modref at -O1 is

  loads:
      Base 0: alias set 0
        Ref 0: alias set 0
          access: Parm 0 param offset:0 offset:0 size:64 max_size:64
  stores:
    Every base
  Global memory written
  parm 0 flags: no_direct_clobber no_indirect_clobber no_direct_escape
no_indirect_escape no_indirect_read

where obviously no_{indirect,}_clobber isn't correct(?).  Note this seems
to result in PTA computing a stmt call clobber set that's

$20 = {anything = 0, nonlocal = 1, escaped = 1, ipa_escaped = 0, null = 0, 
  const_pool = 0, vars_contains_nonlocal = 0, vars_contains_escaped = 0, 
  vars_contains_escaped_heap = 0, vars_contains_restrict = 0, 
  vars_contains_interposable = 0, vars = 0x7ffff71b7b80}

which relies on us having 't' as escaped, but it's not (due to modref).

While modref analysis doesn't do the disambiguation the last resort check
of the call clobber set does.  In particular we create constaints:

t = &resultIsStatic
callescape(12) = &NONLOCAL
CALLUSED(13) = callescape(12)
callarg(15) = &t
callarg(15) = callarg(15) + UNKNOWN
CALLUSED(13) = callarg(15)
resultIsStatic.0_1 = resultIsStatic

so points-to doesn't consider anything call clobbered or escaped.

In particular this looks at gimpl_call_arg_flags which is computed to
EAF_NO_INDIRECT_READ | EAF_NO_DIRECT_ESCAPE | EAF_NO_INDIRECT_ESCAPE
| EAF_NO_DIRECT_CLOBBER | EAF_NO_INDIRECT_CLOBBER which again is wrong
since indirect clobber should be here.

I think the analysis of map_to_vector goes wrong:

 - Analyzing store: t
   - Read-only or local, ignoring.
 - Analyzing load: *F_2(D)
   - Recording base_set=0 ref_set=0  Parm 0 param offset:0 offset:0 size:64
max_size:64
 - Analyzing call:t = map_iterator (*F_2(D));
 - ECF_CONST | ECF_NOVOPS, ignoring all stores and all loads except for args.
^^^^
 - Analyzing call:ff (&t.F);
 - Merging side effects of ff/0
   Parm map: -5
 - Analyzing store: t
   - Read-only or local, ignoring.

missing that the t = map_iterator stmt copies *F to t, making t to contain
references to non-local vars which ff indirectly clobbers.


Honza?