[Bug libstdc++/94295] New: use __builtin_operator_new and __builtin_operator_delete when available

[Bug libstdc++/94295] New: use __builtin_operator_new and __builtin_operator_delete when available

[richard-gccbugzilla at metafoo dot co.uk]

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

            Bug ID: 94295
           Summary: use __builtin_operator_new and
                    __builtin_operator_delete when available
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: richard-gccbugzilla at metafoo dot co.uk
  Target Milestone: ---

See https://bugs.llvm.org/show_bug.cgi?id=45287 for some background.

The C++ language rules do not permit optimization (eg, deletion) of direct
calls to 'operator new' and 'operator delete'. libstdc++ uses such calls to
implement std::allocator:

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/ext/new_allocator.h#L112

As a consequence, allocations performed by libstdc++'s containers are not
optimizable.

Clang provides a pair of builtin functions to work around this issue:
https://clang.llvm.org/docs/LanguageExtensions.html#builtin-operator-new-and-builtin-operator-delete

__builtin_operator_new(args) is equivalent to ::operator new(args) except that
it permits optimizations.
__builtin_operator_delete(args) is equivalent to ::operator delete(args) except
that it permits optimizations.

You can detect support for these builtins with

#ifdef __has_builtin
#if __has_builtin(__builtin_operator_new) >= 201802L
// ...
#endif
#endif

(Note that __has_builtin(...) returned 1 for an older version of the builtins
that didn't support placement forms, and so couldn't be used for aligned
allocation and sized delete. It's probably not worth your time dealing with
those.)

This bug requests that libstdc++ uses these builtins when available.
(Separately, it'd be great if GCC considered supporting them too.)

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Smith from comment #0)
> The C++ language rules do not permit optimization (eg, deletion) of direct
> calls to 'operator new' and 'operator delete'.

I thought that was considered a bug?
Gcc does optimize those, like it does malloc/free...

> This bug requests that libstdc++ uses these builtins when available.

So just in std::allocator, or are there other places?

> (Separately, it'd be great if GCC considered supporting them too.)

IIRC (would need to dig up the conversation), when the optimization for
new/delete pairs was added in gcc, the builtin option was rejected.

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[richard-gccbugzilla at metafoo dot co.uk]

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

--- Comment #2 from Richard Smith <richard-gccbugzilla at metafoo dot co.uk> ---
(In reply to Marc Glisse from comment #1)
> (In reply to Richard Smith from comment #0)
> > The C++ language rules do not permit optimization (eg, deletion) of direct
> > calls to 'operator new' and 'operator delete'.
> 
> I thought that was considered a bug?

No, it's intentional: if the user directly calls '::operator new(42)' and
they've replaced that function, the replacement function is guaranteed to be
called. In this regard, 'operator new' is just a regular function with a funny
name.

To be clear, the implicit call to 'operator new' produced by, say, 'new int'
*is* optimizable, but a direct explicit call to 'operator new(sizeof(int))' is
not.

> Gcc does optimize those, like it does malloc/free...

That sounds like non-conforming behavior.

> > This bug requests that libstdc++ uses these builtins when available.
> 
> So just in std::allocator, or are there other places?

std::allocator's specification has an explicit provision to permit these
optimizations, see [allocator.members]/4:

"The storage for the array is obtained by calling ::operator new (17.6.2), but
it is unspecified when or how often this function is called."

In Clang + libc++ at least, we interpret that as meaning we can call
'::operator new' zero times if we don't need the storage, just like for a
new-expression, and the LWG members I've talked to about this have agreed that
that's in line with the intent.

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Smith from comment #2)
> (In reply to Marc Glisse from comment #1)
> > (In reply to Richard Smith from comment #0)
> > > The C++ language rules do not permit optimization (eg, deletion) of direct
> > > calls to 'operator new' and 'operator delete'.
> > 
> > I thought that was considered a bug?
> 
> No, it's intentional: if the user directly calls '::operator new(42)' and
> they've replaced that function, the replacement function is guaranteed to be
> called. In this regard, 'operator new' is just a regular function with a
> funny name.
> 
> To be clear, the implicit call to 'operator new' produced by, say, 'new int'
> *is* optimizable, but a direct explicit call to 'operator new(sizeof(int))'
> is not.
> 
> > Gcc does optimize those, like it does malloc/free...
> 
> That sounds like non-conforming behavior.


PR 23383 is where part of the discussion was done.

In fact GCC implements the optimization without the builtin:
https://gcc.gnu.org/legacy-ml/gcc-patches/2019-07/msg00136.html

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[richard-gccbugzilla at metafoo dot co.uk]

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

--- Comment #4 from Richard Smith <richard-gccbugzilla at metafoo dot co.uk> ---
(In reply to Andrew Pinski from comment #3)
> PR 23383 is where part of the discussion was done.
> 
> In fact GCC implements the optimization without the builtin:
> https://gcc.gnu.org/legacy-ml/gcc-patches/2019-07/msg00136.html

Yep, looks like GCC miscompiles direct calls to operator new / operator delete
since that patch landed: https://godbolt.org/z/dK99Rz

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[glisse at gcc dot gnu.org]

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

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Smith from comment #2)
> (In reply to Marc Glisse from comment #1)
> > (In reply to Richard Smith from comment #0)
> > > The C++ language rules do not permit optimization (eg, deletion) of direct
> > > calls to 'operator new' and 'operator delete'.
> > 
> > I thought that was considered a bug?
> 
> No, it's intentional: if the user directly calls '::operator new(42)' and
> they've replaced that function, the replacement function is guaranteed to be
> called. In this regard, 'operator new' is just a regular function with a
> funny name.
> 
> To be clear, the implicit call to 'operator new' produced by, say, 'new int'
> *is* optimizable, but a direct explicit call to 'operator new(sizeof(int))'
> is not.

Ah, since you are here, and you appeared as an author of N3664 but not N3537
(precisely when this subtlety happened), could you explain why? It isn't
discussed in the paper, complicates the design, and I cannot think of any use
for this distinction (there are workarounds if people don't want their explicit
call elided).

This of course doesn't at all prevent from adding a __builtin_operator_new
option in std::allocator, it only affects how motivated we should be to fix the
non-conformance.

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[richard-gccbugzilla at metafoo dot co.uk]

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

--- Comment #6 from Richard Smith <richard-gccbugzilla at metafoo dot co.uk> ---
(In reply to Marc Glisse from comment #5)
> Ah, since you are here, and you appeared as an author of N3664 but not N3537
> (precisely when this subtlety happened), could you explain why? It isn't
> discussed in the paper, complicates the design, and I cannot think of any
> use for this distinction

It isn't discussed in the paper because it wasn't part of the original plan /
design, but was added due to committee push-back. People want some guarantees:

 * If they write a test for their global 'operator new' (particularly, testing
failure cases, mallinfo, the effect of configuration parameters on its
behavior, ...), that test should still work in the presence of the language
change.

 * A direct function call to a user-defined function should behave as a direct
function call to that user-defined function. Even if it has a non-identifier
name.

In the end, the language and user model we found to be most satisfying, given
the above, is: new-expressions, like std::allocator, may obtain storage by
calling 'operator new', but it's unspecified how often it's called and with
what arguments. And the language rules are an approximation of that idea.


(In reply to Marc Glisse from comment #5)
> This of course doesn't at all prevent from adding a __builtin_operator_new
> option in std::allocator, it only affects how motivated we should be to fix
> the non-conformance.

Well, in case it helps your analysis, LLVM once did what GCC does now (before
there were standard rules in place), and in practice we saw it break some stuff
(largely, tests for allocators, but also weird things like using 'operator
new((size_t)-1)' as a way to throw bad_alloc from code that can't '#include
<exception>').

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2020-03-26
           Severity|normal                      |enhancement
     Ever confirmed|0                           |1

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Richard S., is there any reason to use the built-ins for the constant
evaluation case? I assume not. Currently std::allocator does:

      [[nodiscard,__gnu__::__always_inline__]]
      constexpr _Tp*
      allocate(size_t __n)
      {
#ifdef __cpp_lib_is_constant_evaluated
        if (std::is_constant_evaluated())
          return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
#endif
        return __allocator_base<_Tp>::allocate(__n, 0);
      }

and my assumption is that there is no reason to change this code, because the
benefits of __builtin_operator_new are only for run-time uses.

The calls to ::operator new in __allocator_base<_Tp>::allocate can use the
built-in though e.g.

--- a/libstdc++-v3/include/ext/new_allocator.h
+++ b/libstdc++-v3/include/ext/new_allocator.h
@@ -97,6 +97,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return std::__addressof(__x); }
 #endif

+#if __has_builtin(__builtin_operator_new) >= 201802L
+# define _GLIBCXX_OPERATOR_NEW __builtin_operator_new
+# define _GLIBCXX_OPERATOR_DELETE __builtin_operator_delete
+#else
+# define _GLIBCXX_OPERATOR_NEW ::operator new
+# define _GLIBCXX_OPERATOR_DELETE ::operator delete
+#endif
+
       // NB: __n is permitted to be 0.  The C++ standard says nothing
       // about what the return value is when __n == 0.
       _GLIBCXX_NODISCARD _Tp*
@@ -121,34 +129,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
          {
            std::align_val_t __al = std::align_val_t(alignof(_Tp));
-           return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), __al));
+           return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp),
+                                                          __al));
          }
 #endif
-       return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
+       return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp)));
       }

       // __p is not permitted to be a null pointer.
       void
       deallocate(_Tp* __p, size_type __t __attribute__ ((__unused__)))
       {
+#if __cpp_sized_deallocation
+# define _GLIBCXX_SIZED_DEALLOC(p) p, __t * sizeof(_Tp)
+#else
+# define _GLIBCXX_SIZED_DEALLOC(p) p
+#endif
+
 #if __cpp_aligned_new
        if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
          {
-           ::operator delete(__p,
-# if __cpp_sized_deallocation
-                             __t * sizeof(_Tp),
-# endif
-                             std::align_val_t(alignof(_Tp)));
+           _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p),
+                                    std::align_val_t(alignof(_Tp)));
            return;
          }
 #endif
-       ::operator delete(__p
-#if __cpp_sized_deallocation
-                         , __t * sizeof(_Tp)
-#endif
-                        );
+       _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p));
       }

+#undef _GLIBCXX_SIZED_DEALLOC
+#undef _GLIBCXX_OPERATOR_DELETE
+#undef _GLIBCXX_OPERATOR_NEW
+
 #if __cplusplus <= 201703L
       size_type
       max_size() const _GLIBCXX_USE_NOEXCEPT



I see no benefit to using __builtin_operator_new in
std::pmr::new_delete_resource either, because  that will usually be used
through virtual calls to std::pmr::memory_resource::do_allocate, and the actual
call to ::operator new is inside libstdc++.so, not visible to the compiler.

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[richard-gccbugzilla at metafoo dot co.uk]

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

--- Comment #8 from Richard Smith <richard-gccbugzilla at metafoo dot co.uk> ---
(In reply to Jonathan Wakely from comment #7)
> Richard S., is there any reason to use the built-ins for the constant
> evaluation case?

No, Clang's constant evaluator treats the built-ins and calls to replaceable
global [de]allocation functions identically. (The built-ins might be
*marginally* more efficient, but it's not worth an #ifdef.)

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[redi at gcc dot gnu.org]

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

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Thanks

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[jason at gcc dot gnu.org]

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

--- Comment #10 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Richard Smith from comment #4)
> Yep, looks like GCC miscompiles direct calls to operator new / operator
> delete since that patch landed: https://godbolt.org/z/dK99Rz

Note that this is true only of GCC 10.x.

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[redi at gcc dot gnu.org]

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

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

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

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Patches posted:
https://gcc.gnu.org/pipermail/gcc-patches/2021-July/575675.html

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 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:c9ca352186226ae757688e160e7c6f394c9f26aa

commit r12-2470-gc9ca352186226ae757688e160e7c6f394c9f26aa
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jul 22 14:38:34 2021 +0100

    libstdc++: Use __builtin_operator_new when available [PR94295]

    Clang provides __builtin_operator_new and __builtin_operator_delete,
    which have the same semantics as ::operator new and ::operator delete
    except that the compiler is allowed to elide calls to them. This changes
    std::allocator to use those built-in functions so that memory allocated
    by std::allocator can be optimized away when using Clang. This avoids an
    abstraction penalty for using std::allocator to allocate storage rather
    than a new-expression.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/94295
            * include/ext/new_allocator.h (_GLIBCXX_OPERATOR_NEW)
            (_GLIBCXX_OPERATOR_DELETE, _GLIBCXX_SIZED_DEALLOC): Define.
            (allocator::allocate, allocator::deallocate): Use new macros.

[Bug libstdc++/94295] use __builtin_operator_new and __builtin_operator_delete when available

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Done for GCC 12.