[Bug libstdc++/112480] New: optional<T>::reset emits inefficient code when T is trivially-destructible

[Bug libstdc++/112480] New: optional<T>::reset emits inefficient code when T is trivially-destructible

[gnu at kosak dot com]

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

            Bug ID: 112480
           Summary: optional<T>::reset emits inefficient code when T is
                    trivially-destructible
           Product: gcc
           Version: 13.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gnu at kosak dot com
  Target Milestone: ---

Created attachment 56556
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56556&action=edit
the .ii file from -save-temps

Hello,

The assembly output of this program shows that the generated code tests whether
a flag is zero, and if not, sets it to zero. This uses a compare and a branch,
when the optimal code could just force the flag to zero unconditionally with
one instruction. The emitted code is going to be non-optimal in this way for
any trivially-destructible T.

```
#include <optional>

void func(std::optional<int> &x) {
    x.reset();
}
```

Relevant assembly on x86_64, invoked with g++ -S -O3 test.cc
```
_Z4funcRSt8optionalIiE:
.LFB266:
        .cfi_startproc
        endbr64
        cmpb    $0, 4(%rdi)
        je      .L1
        movb    $0, 4(%rdi)
.L1:
        ret
        .cfi_endproc
```

The non-optimal code arises because optional<T>::reset() needs to decide
whether or not to call ~T(), and this decision depends on whether or not the
optional is currently holding a value. However, if T is trivially destructible,
~T() is a no-op, so the test and branch is kind of a waste.

One way this could be addressed is via this one-line change to
/usr/include/c++/13/optional:

```
--- optional.ORIG       2023-11-10 19:01:35.843372670 +0000
+++ optional    2023-11-10 19:22:53.525894777 +0000
@@ -314,7 +314,7 @@
       constexpr void
       _M_reset() noexcept
       {
-       if (this->_M_engaged)
+       if (is_trivially_destructible_v<_Tp> || this->_M_engaged)
          _M_destroy();
       }
     };

```
With this change in place, the emitted assembly is
```
_Z4funcRSt8optionalIiE:
.LFB266:
        .cfi_startproc
        endbr64
        movb    $0, 4(%rdi)
        ret
        .cfi_endproc
```

Output from g++ -v:
```
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-linux-gnu/13/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 13.2.0-4ubuntu3'
--with-bugurl=file:///usr/share/doc/gcc-13/README.Bugs
--enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr
--with-gcc-major-version-only --program-suffix=-13
--program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id
--libexecdir=/usr/libexec --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --enable-bootstrap --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-13-XYspKM/gcc-13-13.2.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-13-XYspKM/gcc-13-13.2.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
--with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 13.2.0 (Ubuntu 13.2.0-4ubuntu3)
```

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-11-10
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I feel like the compiler should be able to do that anyway.

_M_destroy() is:

        _M_engaged = false;
        _M_payload._M_value.~_Stored_type();

For a trivially destructible type the second statement is a no-op, so we have:

  if (_M_engaged)
    _M_engaged = false;

The compiler should turn that into _M_engaged = false.

The suggested change is wrong though, because it runs the trivial destructor
unconditionally, even if there is no object within its lifetime. Clang will
diagnose that during constant evaluation (although gcc doesn't, which I think
is a known bug).

For example:

#include <optional>

constexpr bool f()
{
  std::optional<int> opt(1);
  opt = std::nullopt;
  opt = std::nullopt;
  return true;
}

static_assert(f());


opt.cc:10:15: error: static assertion expression is not an integral constant
expression
static_assert(f());
              ^~~
/home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/14.0.0/../../../../include/c++/14.0.0/optional:282:2:
note: destruction of member '_M_value' of union with active member '_M_empty'
is not allowed in a constant expression
        _M_payload._M_value.~_Stored_type();
        ^
/home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/14.0.0/../../../../include/c++/14.0.0/optional:313:4:
note: in call to '&opt._Optional_base::_M_payload->_M_destroy()'
          _M_destroy();
          ^
/home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/14.0.0/../../../../include/c++/14.0.0/optional:465:45:
note: in call to '&opt._Optional_base::_M_payload->_M_reset()'
      { static_cast<_Dp*>(this)->_M_payload._M_reset(); }
                                            ^
/home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/14.0.0/../../../../include/c++/14.0.0/optional:831:8:
note: in call to '&opt->_M_reset()'
        this->_M_reset();
              ^
opt.cc:6:7: note: in call to '&opt->operator=({})'
  opt = std::nullopt;
      ^
opt.cc:10:15: note: in call to 'f()'
static_assert(f());
              ^
1 error generated.


We could do:

      constexpr void
      _M_reset() noexcept
      {
        if constexpr (is_trivially_destructible_v<_Tp>)
          {
            if (!std::__is_constant_evaluated())
              {
                this->_M_engaged = false;
                return;
              }
          }

        if (this->_M_engaged)
          _M_destroy();
      }


Yuck

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[gnu at kosak dot com]

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

--- Comment #2 from Corey Kosak <gnu at kosak dot com> ---
Thanks for the reply and the correction about illegally running the destructor.

As for why the compiler can't do the optimization itself, I don't know, but the
optimization isn't applied here either:

```
void func(bool &b) {
    if (b) {
        b = false;
    }
}
```

However, it seems we can force the optimization to happen if we do the
assignment in both branches of the 'if', as in
```
void func(bool &b) {
    if (b) {
        b = false;
    } else {
        b = false;
    }
}

```

...which suggests that a less Yuck-inducing diff might be

```
--- optional.ORIG       2023-11-10 21:37:00.623586305 +0000
+++ optional    2023-11-10 21:38:54.021199563 +0000
@@ -316,6 +316,8 @@
       {
        if (this->_M_engaged)
          _M_destroy();
+        else
+          this->_M_engaged = false;
       }
     };

```

which produces the desired assembly, but at the cost of looking to the reader
like it's superfluous code.

...with the disclaimer that I don't understand why the "if
(!std::__is_constant_evaluated())" was necessary in your change, so I didn't
mention it here, so I could be missing something still.

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Corey Kosak from comment #2)
> Thanks for the reply and the correction about illegally running the
> destructor.
> 
> As for why the compiler can't do the optimization itself, I don't know, but
> the optimization isn't applied here either:
> 
> ```
> void func(bool &b) {
>     if (b) {
>         b = false;
>     }
> }
> ```


I think that is because that transformation would violate the memory model of
C++.

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> I think that is because that transformation would violate the memory model
> of C++.

Ah yes. It would be safe for another thread to read the same memory location,
as long as they all read false so that no store to that location happens. If we
introduce a store, reads in other threads would conflict and we would have a
data race, i.e. undefined behaviour.

What the compiler doesn't know is that the standard already forbids any
potentially concurrent access, because _M_reset() is a non-const member
function.

So we can force the store to happen, as we know it's ok where the compiler
doesn't.

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[vanyacpp at gmail dot com]

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

Ivan Sorokin <vanyacpp at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vanyacpp at gmail dot com

--- Comment #5 from Ivan Sorokin <vanyacpp at gmail dot com> ---
Perhaps something like this would do the trick?

void _M_reset()
{
    if (_M_engaged)
        _M_destroy();
    else
        _M_engaged = _M_engaged;
}

On one hand _M_engaged = _M_engaged allows merging then and else branches
without introducing new writes, on the other it can be optimized to no-op if
the branches are not merged.

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think I prefer:

--- a/libstdc++-v3/include/std/optional
+++ b/libstdc++-v3/include/std/optional
@@ -311,6 +311,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       {
        if (this->_M_engaged)
          _M_destroy();
+
+       // The following seems redundant but improves codegen, see PR 112480.
+       if constexpr (is_trivially_destructible_v<_Tp>)
+         this->_M_engaged = false;
       }
     };

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[vanyacpp at gmail dot com]

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

--- Comment #7 from Ivan Sorokin <vanyacpp at gmail dot com> ---
(In reply to Jonathan Wakely from comment #6)

> +       // The following seems redundant but improves codegen, see PR 112480.
> +       if constexpr (is_trivially_destructible_v<_Tp>)
> +         this->_M_engaged = false;
>        }


In theory non-trivial destructors that are optimizible to no-op can also
benefit from the same optimization.

I don't know how often non-trivial no-op destructors occur in practice. Perhaps
we can ignore such case.

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Good point, it looks like we get the same codegen improvement for ~T(){} even
at -O1 if we don't restrict it to trivially destructible types.

There seems to be no difference in codegen for _M_engaged=false or
_M_engaged=_M_engaged (which isn't too surprising, since we know that either it
was already false, or we're setting it to false). Given that, I think I prefer
explicitly setting to false.

So I'll test this:

--- a/libstdc++-v3/include/std/optional
+++ b/libstdc++-v3/include/std/optional
@@ -311,6 +311,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       {
        if (this->_M_engaged)
          _M_destroy();
+       else // This seems redundant but improves codegen, see PR 112480.
+         this->_M_engaged = false;
       }
     };

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:2c492f99fc1fcb5f598286c3f3a21a05bca69d9e

commit r14-5421-g2c492f99fc1fcb5f598286c3f3a21a05bca69d9e
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Sat Nov 11 00:35:18 2023 +0000

    libstdc++: Micro-optimization for std::optional [PR112480]

    This small change removes a branch when clearing a std::optional<T> for
    types with no-op destructors. For types where the destructor can be
    optimized away (e.g. because it's trivial, or empty and can be inlined)
    the _M_destroy() function does nothing but set _M_engaged to false.
    Setting _M_engaged=false unconditionally is cheaper than only doing it
    when initially true, because it allows the compiler to remove a branch.

    The compiler thinks it would be incorrect to unconditionally introduce a
    store there, because it could conflict with reads in other threads, so
    it won't do that optimization itself. We know it's safe to do because
    we're in a non-const member function, so the standard forbids any
    potentially concurrent calls to other member functions of the same
    object. Making the store unconditional can't create a data race that
    isn't already present in the program.

    libstdc++-v3/ChangeLog:

            PR libstdc++/112480
            * include/std/optional (_Optional_payload_base::_M_reset): Set
            _M_engaged to false unconditionally.

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:866870c51d58881819db6db76dcdfe3f43d89903

commit r13-8132-g866870c51d58881819db6db76dcdfe3f43d89903
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Sat Nov 11 00:35:18 2023 +0000

    libstdc++: Micro-optimization for std::optional [PR112480]

    This small change removes a branch when clearing a std::optional<T> for
    types with no-op destructors. For types where the destructor can be
    optimized away (e.g. because it's trivial, or empty and can be inlined)
    the _M_destroy() function does nothing but set _M_engaged to false.
    Setting _M_engaged=false unconditionally is cheaper than only doing it
    when initially true, because it allows the compiler to remove a branch.

    The compiler thinks it would be incorrect to unconditionally introduce a
    store there, because it could conflict with reads in other threads, so
    it won't do that optimization itself. We know it's safe to do because
    we're in a non-const member function, so the standard forbids any
    potentially concurrent calls to other member functions of the same
    object. Making the store unconditional can't create a data race that
    isn't already present in the program.

    libstdc++-v3/ChangeLog:

            PR libstdc++/112480
            * include/std/optional (_Optional_payload_base::_M_reset): Set
            _M_engaged to false unconditionally.

    (cherry picked from commit 2c492f99fc1fcb5f598286c3f3a21a05bca69d9e)

[Bug libstdc++/112480] optional<T>::reset emits inefficient code when T is trivially-destructible

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED
   Target Milestone|---                         |13.3

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 13.3, thanks for the report and analysis of the codegen.