So we're failing to DSE

  _13 = pretmp_25 - pretmp_63;
  if (_13 > 4)
    goto <bb 7>; [97.30%]
  else
    goto <bb 6>; [2.70%]

  <bb 6> [local count: 14278734]:
  if (_13 == 4)
    goto <bb 8>; [34.00%]
  else
    goto <bb 9>; [66.00%]

  <bb 7> [local count: 913536322]:
  _23 = (long unsigned int) _13;
  __builtin_memmove (_37, pretmp_63, _23);
  goto <bb 9>; [100.00%]

  <bb 8> [local count: 34511373]:
  _24 = *pretmp_63;
  *_37 = _24;

  <bb 9> [local count: 542742079]:
  operator delete (_37, _49);

because I think the DTOR / overloaded global delete might inspect the vector
contents.  So I'm not sure it would be valid to elide the memmove/store.
When the stores would be elided we'd DCE the new/delete pair as well.

Neither v nor v1 escapes the function, so I don't think operator delete can inspect them.

The destructor doesn't inspect the contents, it just destroys the elements (which is a no-op for int) and then calls operator delete to free the storage.

Ah, maybe the problem is that the library code manually elides destroying the elements, precisely because it's a no-op. So we don't actually destroy the elements, which means the compiler might think they're still initialized and so could be inspected.

If the library explicitly does vec[i].~T() for every i then would that help? The compiler would know there are no valid elements in the storage, and so nothing operator delete could inspect.

We could continue to elide destroying the elements when !defined __OPTIMIZE__ so that we don't run a loop that does nothing, but with optimization enabled rely on the compiler to remove that loop.

(In reply to Jonathan Wakely from comment #3)
> Ah, maybe the problem is that the library code manually elides destroying
> the elements, precisely because it's a no-op. So we don't actually destroy
> the elements, which means the compiler might think they're still initialized
> and so could be inspected.
> 
> If the library explicitly does vec[i].~T() for every i then would that help?
> The compiler would know there are no valid elements in the storage, and so
> nothing operator delete could inspect.
> 
> We could continue to elide destroying the elements when !defined
> __OPTIMIZE__ so that we don't run a loop that does nothing, but with
> optimization enabled rely on the compiler to remove that loop.

I don't think that would help.  The issue is the compiler thinks that

operator delete (_37, _49);

uses the memory at _37 and thus the stores

*_37 = _24;

and

__builtin_memmove (_37, pretmp_63, _23);

are not dead.  IIRC 'operator delete' (_ZdlPvm in this case), can be
overridden by the user and can inspect the memory state before "releasing"
the storage?

This also seems to be a form not handled by fndecl_dealloc_argno
even though it's marked as DECL_IS_OPERATOR_DELETE_P and
DECL_IS_REPLACEABLE_OPERATOR - but the actual call stmt is not marked
as such.  That's to catch a new/delete _expression_ and not a direct
call to the operator - ISTR we need the semantics guaranteed by the
standard for new/delete expressions here.

I see ~_Vector_base uses

 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
 if (__p)
   _Tr::deallocate(_M_impl, __p, __n);

but I fail to trace that further (in the preprocessed source), the
line info on the delete stmt above points to new_allocator.h:168
which is

        _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n));

which looks like a direct invocation of operator delete rather than
a delete expression.  So the compiler rightfully(?) refuses to apply
strict semantics ('delete' is _just_ like free with no other side-effects,
a 'new' / 'delete' pair may be elided).

Indeed in preprocessed source the above expands to

 ::operator delete((__p), (__n) * sizeof(_Tp));

rather than

  delete[] __p;

(or what the correct syntax with explicit size would be).  In theory
we could implement an attribute specifying a operator new or delete
invocation acts like a new or delete expression and use that in the
library and make sure that CALL_FROM_NEW_OR_DELETE_P is set on the
generated CALL_EXPRs.

When I replace the above operator invocation in the library with

  delete[] (char *)__p;

then the dead stores are elided but since I didn't track down the call
to 'operator new' which suffers from a similar problem the new/delete
pair isn't elided yet.

So in the end it seems this is a library/C++ frontend issue.

(In reply to Richard Biener from comment #4)
> (In reply to Jonathan Wakely from comment #3)
> > Ah, maybe the problem is that the library code manually elides destroying
> > the elements, precisely because it's a no-op. So we don't actually destroy
> > the elements, which means the compiler might think they're still initialized
> > and so could be inspected.
> > 
> > If the library explicitly does vec[i].~T() for every i then would that help?
> > The compiler would know there are no valid elements in the storage, and so
> > nothing operator delete could inspect.
> > 
> > We could continue to elide destroying the elements when !defined
> > __OPTIMIZE__ so that we don't run a loop that does nothing, but with
> > optimization enabled rely on the compiler to remove that loop.
> 
> I don't think that would help.  The issue is the compiler thinks that
> 
> operator delete (_37, _49);
> 
> uses the memory at _37 and thus the stores
> 
> *_37 = _24;
> 
> and
> 
> __builtin_memmove (_37, pretmp_63, _23);
> 
> are not dead.

But if the library did _37->~_Tp() to destroy the element at _37 then it would be dead, and accessing the element outside its lifetime would be undefined. The bytes can only be accessed as char, unsigned char or std::byte after that.

> IIRC 'operator delete' (_ZdlPvm in this case), can be
> overridden by the user and can inspect the memory state before "releasing"
> the storage?

That would be insane for operator delete to do that. Maybe possible, but insane.

In any case, the stores to _37 would be dead now, right? So even if operator delete inspects the memory as raw bytes using memcmp or similar, it's reading uninitialized storage, so any value is acceptable. So the stores to _37 should be DSE-able now.

> This also seems to be a form not handled by fndecl_dealloc_argno
> even though it's marked as DECL_IS_OPERATOR_DELETE_P and
> DECL_IS_REPLACEABLE_OPERATOR - but the actual call stmt is not marked
> as such.  That's to catch a new/delete _expression_ and not a direct
> call to the operator - ISTR we need the semantics guaranteed by the
> standard for new/delete expressions here.
> 
> I see ~_Vector_base uses
> 
>  typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
>  if (__p)
>    _Tr::deallocate(_M_impl, __p, __n);
> 
> but I fail to trace that further (in the preprocessed source), the
> line info on the delete stmt above points to new_allocator.h:168
> which is
> 
>         _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n));
> 
> which looks like a direct invocation of operator delete rather than
> a delete expression.  So the compiler rightfully(?) refuses to apply
> strict semantics ('delete' is _just_ like free with no other side-effects,
> a 'new' / 'delete' pair may be elided).
> 
> Indeed in preprocessed source the above expands to
> 
>  ::operator delete((__p), (__n) * sizeof(_Tp));
> 
> rather than
> 
>   delete[] __p;

Yes, that's correct. Using a delete expression here would be completely wrong.


> (or what the correct syntax with explicit size would be).  In theory
> we could implement an attribute specifying a operator new or delete
> invocation acts like a new or delete expression and use that in the
> library and make sure that CALL_FROM_NEW_OR_DELETE_P is set on the
> generated CALL_EXPRs.
> 
> When I replace the above operator invocation in the library with
> 
>   delete[] (char *)__p;

That would make std::vector incorrect though.

> then the dead stores are elided but since I didn't track down the call
> to 'operator new' which suffers from a similar problem the new/delete
> pair isn't elided yet.
> 
> So in the end it seems this is a library/C++ frontend issue.

Then there's no bug. std::vector is correct, and using a delete[] expression would be a bug.

(In reply to Jonathan Wakely from comment #5)
> (In reply to Richard Biener from comment #4)
> > (In reply to Jonathan Wakely from comment #3)
> > > Ah, maybe the problem is that the library code manually elides destroying
> > > the elements, precisely because it's a no-op. So we don't actually destroy
> > > the elements, which means the compiler might think they're still initialized
> > > and so could be inspected.
> > > 
> > > If the library explicitly does vec[i].~T() for every i then would that help?
> > > The compiler would know there are no valid elements in the storage, and so
> > > nothing operator delete could inspect.
> > > 
> > > We could continue to elide destroying the elements when !defined
> > > __OPTIMIZE__ so that we don't run a loop that does nothing, but with
> > > optimization enabled rely on the compiler to remove that loop.
> > 
> > I don't think that would help.  The issue is the compiler thinks that
> > 
> > operator delete (_37, _49);
> > 
> > uses the memory at _37 and thus the stores
> > 
> > *_37 = _24;
> > 
> > and
> > 
> > __builtin_memmove (_37, pretmp_63, _23);
> > 
> > are not dead.
> 
> But if the library did _37->~_Tp() to destroy the element at _37 then it
> would be dead, and accessing the element outside its lifetime would be
> undefined. The bytes can only be accessed as char, unsigned char or
> std::byte after that.
> 
> > IIRC 'operator delete' (_ZdlPvm in this case), can be
> > overridden by the user and can inspect the memory state before "releasing"
> > the storage?
> 
> That would be insane for operator delete to do that. Maybe possible, but
> insane.

Well, the standard doesn't prohibit "insanity" so we have to generate
correct code even in those cases, no?  After all this is what PR101480
was about ("insane" stuff) done even to new/delete _expressions_.

Would it be correct (by the standards wording) to extend the current
handling of new/delete expressions - which is that 'new' returns a pointer
not aliasing to any other pointer and that 'delete' does not read from
the memory pointed to by the first argument and this pointer also does not
escape to direct calls of operator new/delete?

Basically in gimple.cc:gimple_call_fnspec we currenty do

  /* If the call is to a replaceable operator delete and results
     from a delete expression as opposed to a direct call to
     such operator, then we can treat it as free.  */
  if (fndecl
      && DECL_IS_OPERATOR_DELETE_P (fndecl)
      && DECL_IS_REPLACEABLE_OPERATOR (fndecl)
      && gimple_call_from_new_or_delete (stmt))
    return ". o ";
  /* Similarly operator new can be treated as malloc.  */
  if (fndecl
      && DECL_IS_REPLACEABLE_OPERATOR_NEW_P (fndecl)
      && gimple_call_from_new_or_delete (stmt))
    return "m ";

where the comments do not exactly match the behavior (we also allow
arbitrary side-effects on global memory).  That we model 'delete'
as possibly writing to the released storage is so it serves as barrier for
earlier loads/stores to avoid sinking them across.

> In any case, the stores to _37 would be dead now, right? So even if operator
> delete inspects the memory as raw bytes using memcmp or similar, it's
> reading uninitialized storage, so any value is acceptable. So the stores to
> _37 should be DSE-able now.

There's noting in the IL indicating that though (but I haven't updated
libstd++ a while to create a updated preprocessed source - will do so now).

> > This also seems to be a form not handled by fndecl_dealloc_argno
> > even though it's marked as DECL_IS_OPERATOR_DELETE_P and
> > DECL_IS_REPLACEABLE_OPERATOR - but the actual call stmt is not marked
> > as such.  That's to catch a new/delete _expression_ and not a direct
> > call to the operator - ISTR we need the semantics guaranteed by the
> > standard for new/delete expressions here.
> > 
> > I see ~_Vector_base uses
> > 
> >  typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
> >  if (__p)
> >    _Tr::deallocate(_M_impl, __p, __n);
> > 
> > but I fail to trace that further (in the preprocessed source), the
> > line info on the delete stmt above points to new_allocator.h:168
> > which is
> > 
> >         _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n));
> > 
> > which looks like a direct invocation of operator delete rather than
> > a delete expression.  So the compiler rightfully(?) refuses to apply
> > strict semantics ('delete' is _just_ like free with no other side-effects,
> > a 'new' / 'delete' pair may be elided).
> > 
> > Indeed in preprocessed source the above expands to
> > 
> >  ::operator delete((__p), (__n) * sizeof(_Tp));
> > 
> > rather than
> > 
> >   delete[] __p;
> 
> Yes, that's correct. Using a delete expression here would be completely
> wrong.

I see.  That's unfortunate (we'll never be able to elide the actual
allocation then).

> > (or what the correct syntax with explicit size would be).  In theory
> > we could implement an attribute specifying a operator new or delete
> > invocation acts like a new or delete expression and use that in the
> > library and make sure that CALL_FROM_NEW_OR_DELETE_P is set on the
> > generated CALL_EXPRs.
> > 
> > When I replace the above operator invocation in the library with
> > 
> >   delete[] (char *)__p;
> 
> That would make std::vector incorrect though.
> 
> > then the dead stores are elided but since I didn't track down the call
> > to 'operator new' which suffers from a similar problem the new/delete
> > pair isn't elided yet.
> > 
> > So in the end it seems this is a library/C++ frontend issue.
> 
> Then there's no bug. std::vector is correct, and using a delete[] expression
> would be a bug.

OK, then how do we arrange things so the compiler knows it can completely
elide the unused std::vector?  Or do you say it's not valid to do that?

(In reply to Richard Biener from comment #6)
> (In reply to Jonathan Wakely from comment #5)
> > (In reply to Richard Biener from comment #4)
> > > (In reply to Jonathan Wakely from comment #3)
> > > > Ah, maybe the problem is that the library code manually elides destroying
> > > > the elements, precisely because it's a no-op. So we don't actually destroy
> > > > the elements, which means the compiler might think they're still initialized
> > > > and so could be inspected.
> > > > 
> > > > If the library explicitly does vec[i].~T() for every i then would that help?
> > > > The compiler would know there are no valid elements in the storage, and so
> > > > nothing operator delete could inspect.
> > > > 
> > > > We could continue to elide destroying the elements when !defined
> > > > __OPTIMIZE__ so that we don't run a loop that does nothing, but with
> > > > optimization enabled rely on the compiler to remove that loop.
> > > 
> > > I don't think that would help.  The issue is the compiler thinks that
> > > 
> > > operator delete (_37, _49);
> > > 
> > > uses the memory at _37 and thus the stores
> > > 
> > > *_37 = _24;
> > > 
> > > and
> > > 
> > > __builtin_memmove (_37, pretmp_63, _23);
> > > 
> > > are not dead.
> > 
> > But if the library did _37->~_Tp() to destroy the element at _37 then it
> > would be dead, and accessing the element outside its lifetime would be
> > undefined. The bytes can only be accessed as char, unsigned char or
> > std::byte after that.
> > 
> > > IIRC 'operator delete' (_ZdlPvm in this case), can be
> > > overridden by the user and can inspect the memory state before "releasing"
> > > the storage?
> > 
> > That would be insane for operator delete to do that. Maybe possible, but
> > insane.
> 
> Well, the standard doesn't prohibit "insanity" so we have to generate
> correct code even in those cases, no? 

Indeed.

> After all this is what PR101480
> was about ("insane" stuff) done even to new/delete _expressions_.
> 
> Would it be correct (by the standards wording) to extend the current
> handling of new/delete expressions - which is that 'new' returns a pointer
> not aliasing to any other pointer and that 'delete' does not read from
> the memory pointed to by the first argument and this pointer also does not
> escape to direct calls of operator new/delete?

No, I don't think so. The [expr.new] p13 permission to elide calls to operator new seems to only apply to new expressions and not direct calls to operator new.


> Basically in gimple.cc:gimple_call_fnspec we currenty do
> 
>   /* If the call is to a replaceable operator delete and results
>      from a delete expression as opposed to a direct call to
>      such operator, then we can treat it as free.  */
>   if (fndecl
>       && DECL_IS_OPERATOR_DELETE_P (fndecl)
>       && DECL_IS_REPLACEABLE_OPERATOR (fndecl)
>       && gimple_call_from_new_or_delete (stmt))
>     return ". o ";
>   /* Similarly operator new can be treated as malloc.  */
>   if (fndecl
>       && DECL_IS_REPLACEABLE_OPERATOR_NEW_P (fndecl)
>       && gimple_call_from_new_or_delete (stmt))
>     return "m ";
> 
> where the comments do not exactly match the behavior (we also allow
> arbitrary side-effects on global memory).  That we model 'delete'
> as possibly writing to the released storage is so it serves as barrier for
> earlier loads/stores to avoid sinking them across.
> 
> > In any case, the stores to _37 would be dead now, right? So even if operator
> > delete inspects the memory as raw bytes using memcmp or similar, it's
> > reading uninitialized storage, so any value is acceptable. So the stores to
> > _37 should be DSE-able now.
> 
> There's noting in the IL indicating that though (but I haven't updated
> libstd++ a while to create a updated preprocessed source - will do so now).

I'm talking about a potential change to libstdc++ to add _37->~_Tp() so you won't see it in the IL now.

What I meant in comment 3 is that libstdc++ uses template metaprogramming to manually elide destroying the elements, because trivial types like 'int' have no destructor. See libstdc++-v3/include/bits/stl_construct.h lines 155-197:

  template<bool>
    struct _Destroy_aux
    {
      template<typename _ForwardIterator>
	static _GLIBCXX20_CONSTEXPR void
	__destroy(_ForwardIterator __first, _ForwardIterator __last)
	{
	  for (; __first != __last; ++__first)
	    std::_Destroy(std::__addressof(*__first));
	}
    };

  template<>
    struct _Destroy_aux<true>
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator, _ForwardIterator) { }
    };

For vector<int> we use the _Destroy_aux<true> specialization, which is a no-op. So the compiler thinks that the elements of the std::vector<int> are still alive when we free the storage.

I'm suggesting that if we actually ended the lifetime of the int elements, then the compiler would see that any stores to _37 are now dead, because we clobber them before calling operator delete.

e.g. something like:

--- a/libstdc++-v3/include/bits/stl_construct.h
+++ b/libstdc++-v3/include/bits/stl_construct.h
@@ -181,6 +181,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _GLIBCXX20_CONSTEXPR inline void
     _Destroy(_ForwardIterator __first, _ForwardIterator __last)
     {
+#ifdef __OPTIMIZE__
+      // Rely on the compiler to optimize the loop away for trivial types.
+      return _Destroy_aux<false>::__destroy(__first, __last);
+#else
       typedef typename iterator_traits<_ForwardIterator>::value_type
                        _Value_type;
 #if __cplusplus >= 201103L
@@ -194,6 +198,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
       std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
        __destroy(__first, __last);
+#endif
     }
 
   template<bool>

But this doesn't change the generated code ¯\_(ツ)_/¯

 
> OK, then how do we arrange things so the compiler knows it can completely
> elide the unused std::vector?  Or do you say it's not valid to do that?

I think it's valid in theory. I don't know if it's possible for GCC to do it in practice. There doesn't seem to be anything the library can do to help, so WONTFIX.

(In reply to Jonathan Wakely from comment #7)
> I think it's valid in theory. I don't know if it's possible for GCC to do it
> in practice. There doesn't seem to be anything the library can do to help,
> so WONTFIX.

I think it's valid in theory because the implementation of std::vector is opaque. It's not required to actually call operator new and operator delete to obtain its storage, and so if the library and compiler collaborate to provide storage some other way (e.g. using a stack buffer) then that's allowed.

But in practice it's hard to do that.

Maybe it could be done with a new __builtin_elidable_operator_new and __builtin_elidable_operator_delete pair that the library could use, or attributes like you suggested in comment 4. That would allow the library to say "I'm calling operator new and operator delete because I need to obtain memory, but **these particular invocations** are not required to be visible to the user, and therefore can be elided in the same way as new expressions and delete expressions".

In fact Clang's __builtin_operator_new already has exactly those semantics:

https://clang.llvm.org/docs/LanguageExtensions.html#builtin-operator-new-and-builtin-operator-delete

And we already use those builtins if available, see PR 94295.

So maybe what we need is to implement those.

(In reply to Jonathan Wakely from comment #8)
> (In reply to Jonathan Wakely from comment #7)
> > I think it's valid in theory. I don't know if it's possible for GCC to do it
> > in practice. There doesn't seem to be anything the library can do to help,
> > so WONTFIX.
> 
> I think it's valid in theory because the implementation of std::vector is
> opaque. It's not required to actually call operator new and operator delete
> to obtain its storage, and so if the library and compiler collaborate to
> provide storage some other way (e.g. using a stack buffer) then that's
> allowed.
> 
> But in practice it's hard to do that.
> 
> Maybe it could be done with a new __builtin_elidable_operator_new and
> __builtin_elidable_operator_delete pair that the library could use, or
> attributes like you suggested in comment 4. That would allow the library to
> say "I'm calling operator new and operator delete because I need to obtain
> memory, but **these particular invocations** are not required to be visible
> to the user, and therefore can be elided in the same way as new expressions
> and delete expressions".
> 
> In fact Clang's __builtin_operator_new already has exactly those semantics:
> 
> https://clang.llvm.org/docs/LanguageExtensions.html#builtin-operator-new-and-
> builtin-operator-delete
> 
> And we already use those builtins if available, see PR 94295.
> 
> So maybe what we need is to implement those.

Yep, looking at that link this is exactly what would be needed.  Note
that in the middle-end we already see the calls to
DECL_IS_REPLACEABLE_OPERATOR_NEW_P and replaceable operator delete.  We
just restrict all optimizations to calls emitted from new/delete expressions.
I'm not sure the clang builtin is exactly providing the new/delete
expression semantics resolving to replaceable operator new/delete or if
there's other details.  That is, I'm curious whether __builtin_operator_new
provides more guarantees than a new/delete expression - the builtin semantics
isn't very well defined unfortunately.  It might be safer to go our own
way here.

I suppose the standard library could as well use malloc/free?  Or is the
standard library required to perform allocation with "replaceable operator new/delete"?  (I suppose it helps not open-coding the exceptional cases)

(In reply to Richard Biener from comment #9)
> Yep, looking at that link this is exactly what would be needed.  Note
> that in the middle-end we already see the calls to
> DECL_IS_REPLACEABLE_OPERATOR_NEW_P and replaceable operator delete.  We
> just restrict all optimizations to calls emitted from new/delete expressions.
> I'm not sure the clang builtin is exactly providing the new/delete
> expression semantics resolving to replaceable operator new/delete or if
> there's other details.  That is, I'm curious whether __builtin_operator_new
> provides more guarantees than a new/delete expression - the builtin semantics
> isn't very well defined unfortunately.  It might be safer to go our own
> way here.

I would prefer if we don't deviate, and get Clang to clarify things instead of reinventing something that looks similar but isn't.

> I suppose the standard library could as well use malloc/free?

No. std::allocator is required to use operator new and operator delete to obtain memory, but it's unspecified when or how often it calls them. So it's OK to call them once at startup to obtain ALL THE MEMORY that any std::allocator will ever need for the duration of the program, or to merge allocations, or to elide them completely. But it's not OK to use malloc.

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

(In reply to Jonathan Wakely from comment #10)
> I would prefer if we don't deviate, and get Clang to clarify things instead
> of reinventing something that looks similar but isn't.

I suppose as long as the common subset of semantics that the library cares about works the same way, it's OK.

It would be bad if the library needs to use extra checks beyond __has_builtin to discover which "flavour" of __builtin_operator_new is present.

On Wed, 12 Apr 2023, redi at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109442
> 
> --- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
> (In reply to Jonathan Wakely from comment #10)
> > I would prefer if we don't deviate, and get Clang to clarify things instead
> > of reinventing something that looks similar but isn't.
> 
> I suppose as long as the common subset of semantics that the library cares
> about works the same way, it's OK.
> 
> It would be bad if the library needs to use extra checks beyond __has_builtin
> to discover which "flavour" of __builtin_operator_new is present.

So if we can get clarification that __builtin_operator_new/delete
allow at least all transforms as if using a new or delete expression
then we can use the same representation as that in the middle-end
for now (just set the CALL_FROM_NEW_OR_DELETE_P flag).

If the builtins provide _additional_ guarantees then we can make use
of those only when we extend things on the middle-end side.

Now we then only need to make the C++ frontend "mangle" the
__builtin_operator_new/delete calls to the "correct" allocation function.
I suppose the goal is to resolve to exactly the same symbols as
when not using the builtins.

@zygoloid, are you the right person to ask about __builtin_operator_new semantics? See the previous comment (comment 12)

If I understand correctly, you're looking for documentation that

  __builtin_operator_new(size)

has the exact same semantics and permits the same optimizations as `::new T` for a trivially-constructible non-array type `T` whose size is `size` and that

  __builtin_operator_delete(p)

has the exact same semantics and permits the same optimizations as `::delete p` for a trivially-destructible non-array type `T` whose size is `size`, with `p` of type `T*` -- and similarly for the other (aligned, nothrow) variants?

That is the intent; I can look into getting Clang's documentation updated to say that more explicitly if that's useful to you.

(In reply to Richard Smith from comment #14)
> If I understand correctly, you're looking for documentation that
> 
>   __builtin_operator_new(size)
> 
> has the exact same semantics and permits the same optimizations as `::new T`
> for a trivially-constructible non-array type `T` whose size is `size` and
> that
> 
>   __builtin_operator_delete(p)
> 
> has the exact same semantics and permits the same optimizations as `::delete
> p` for a trivially-destructible non-array type `T` whose size is `size`,
> with `p` of type `T*` -- and similarly for the other (aligned, nothrow)
> variants?
> 
> That is the intent; I can look into getting Clang's documentation updated to
> say that more explicitly if that's useful to you.

I was specifically looking at C++20 7.6.2.7/10 to /14 (but maybe also
others and of course the relevant parts of the delete expression).  In
particular the extra leeway the standard provides to new/delete _expressions_
vs. calls of the global replaceable operators directly - do the
__builtin_operator_{new,delete} in this regard behave like new/delete
_expressions_ or like direct calls to the operators?

Do the builtins call one of the replaceable global new/delete operators
and thus users can reliably override them?

How do the builtins behave during constexpr evaluation?  new/delete
expressions have their behavior documented in the standard.

(In reply to Richard Biener from comment #15)
> I was specifically looking at C++20 7.6.2.7/10 to /14 (but maybe also
> others and of course the relevant parts of the delete expression).  In
> particular the extra leeway the standard provides to new/delete _expressions_
> vs. calls of the global replaceable operators directly - do the
> __builtin_operator_{new,delete} in this regard behave like new/delete
> _expressions_ or like direct calls to the operators?

They permit the same optimizations as new/delete expressions. The sections of the C++ standard that you referred to are what the documentation for the builtins means when it says:

"[__builtin_operator_new] allows certain optimizations that the C++ standard does not permit for a direct function call to ::operator new (in particular, removing new / delete pairs and merging allocations)"

> Do the builtins call one of the replaceable global new/delete operators
> and thus users can reliably override them?

If the implementation doesn't provide storage in some other way, optimize away the allocation, or merge it with another allocation, then yes, the storage is obtained by calling the corresponding replaceable global new/delete operators. Per the documentation:

"A call to __builtin_operator_new(args) is exactly the same as a call to ::operator new(args), except that [text quoted above]"

> How do the builtins behave during constexpr evaluation?  new/delete
> expressions have their behavior documented in the standard.

They behave exactly like a direct call to the replaceable global allocation function.

In Clang's implementation, direct calls to ::operator new and ::operator delete are permitted within calls to std::allocator<T>::allocate and std::allocator<T>::deallocate during constant evaluation, and are treated as allocating or deallocating arrays of T; consequently, calls to __builtin_operator_new and __builtin_operator_delete are permitted in the same contexts. In all other contexts, Clang rejects such calls, because the callee is not declared `constexpr`.

With recent changes in libc++ (https://reviews.llvm.org/D147741) clang optimizes away the new-delete pair. https://godbolt.org/z/a6PG54Pvb

$ clang++ -O3 -stdlib=libc++ -fno-exceptions

vat1(std::__1::vector<int, std::__1::allocator<int> >): # @vat1(std::__1::vector<int, std::__1::allocator<int> >)
  sub rsp, 24
  xorps xmm0, xmm0
  movaps xmmword ptr [rsp], xmm0
  mov qword ptr [rsp + 16], 0
  mov rax, qword ptr [rdi + 8]
  sub rax, qword ptr [rdi]
  je .LBB0_2
  js .LBB0_3
.LBB0_2:
  mov eax, 10
  add rsp, 24
  ret
.LBB0_3:
  mov rdi, rsp
  call std::__1::vector<int, std::__1::allocator<int> >::__throw_length_error[abi:v170000]() const
.L.str:
  .asciz "vector"

.L.str.1:
  .asciz "length_error was thrown in -fno-exceptions mode with message \"%s\""


Previously clang couldn't even convert the copy to a memmove and would generate a raw loop e.g., https://godbolt.org/z/G8ax1o5bc

.LBB0_6: # =>This Inner Loop Header: Depth=1
  movups xmm0, xmmword ptr [r15 + 4*rdi]
  movups xmm1, xmmword ptr [r15 + 4*rdi + 16]
  movups xmmword ptr [rax + 4*rdi], xmm0
  movups xmmword ptr [rax + 4*rdi + 16], xmm1
  add rdi, 8
  cmp rsi, rdi
  jne .LBB0_6
  cmp rbx, rsi
  jne .LBB0_8
  jmp .LBB0_9
.LBB0_3:

*** Bug 115037 has been marked as a duplicate of this bug. ***

Note that the testcase from PR115037 also shows that we are not able to optimize out dead stores to the vector, which is another quite noticeable problem.

void
test()
{
        std::vector<int> test;
        test.push_back (1);
}

We alocate the block, store 1 and immediately delete it.
void test ()
{
  int * test$D25839$_M_impl$D25146$_M_start;
  struct vector test;
  int * _61;

  <bb 2> [local count: 1073741824]:
  _61 = operator new (4);

  <bb 3> [local count: 1063439392]:
  *_61 = 1;
  operator delete (_61, 4);
  test ={v} {CLOBBER};
  test ={v} {CLOBBER(eol)};
  return;

  <bb 4> [count: 0]:
<L1>:
  test ={v} {CLOBBER};
  resx 2

}

So my understanding is that we decided to not optimize away the dead stores since the particular operator delete does not pass test:

  /* If the call is to a replaceable operator delete and results
     from a delete expression as opposed to a direct call to
     such operator, then we can treat it as free.  */
  if (fndecl
      && DECL_IS_OPERATOR_DELETE_P (fndecl)
      && DECL_IS_REPLACEABLE_OPERATOR (fndecl)
      && gimple_call_from_new_or_delete (stmt))
    return ". o ";

This is because we believe that operator delete may be implemented in an insane way that inspects the values stored in the block being freed.

I can sort of see that one can write standard conforming code that allocates some data that is POD and inspects it in destructor.
However for std::vector this argument is not really applicable. Standard does specify that new/delete is used to allocate/deallocate the memory but does not say how the memory is organized or what happens before deallocation.
(i.e. it is probably valid for std::vector to memset the block just before deallocating it).

Similar argument can IMO be used for eliding unused memory allocations. It is kind of up to std::vector implementation on how many allocations/deallocations it does, right?

So we need a way to annotate the new/delete calls in the standard library as safe for such optimizations (i.e. implement clang's __bulitin_operator_new/delete?)

How clang manages to optimize this out without additional hinting?

(In reply to Jan Hubicka from comment #19)
> Similar argument can IMO be used for eliding unused memory allocations. It
> is kind of up to std::vector implementation on how many
> allocations/deallocations it does, right?

It's up to std::allocator, which is not required to call operator new every time memory is needed. 


> So we need a way to annotate the new/delete calls in the standard library as
> safe for such optimizations (i.e. implement clang's
> __bulitin_operator_new/delete?)

Yes, see PR 110137.

> How clang manages to optimize this out without additional hinting?

It supports __builtin_operator_{new,delete} and libstdc++ uses that when compiled with clang.

Created attachment 58206 [details]
newdelete

This patch attempts to add __builtin_operator_new/delete. So far they
are not optimized, which will need to be done by extra flag of BUILT_IN_
code.  also the decl.cc code can be refactored to be less of cut&paste
and I guess has_builtin hack to return proper value needs to be moved
to C++ FE.

However the immediate problem I run into is that libstdc++ testuiste
fails due to lack of std::nothrow overrides.  I wonder how to get that
working?

*** Bug 116651 has been marked as a duplicate of this bug. ***

with Jakub's builtion_operator_new patch and https://gcc.gnu.org/pipermail/gcc-patches/2024-November/667834.html
on the original testcase we now optimize away allocation and produce

int vat1 (struct vector & v1)
{
  unsigned long _9;
  int * _13;
  int * _14;
  long int _15;

  <bb 2> [local count: 1073741824]:
  _13 = MEM[(const struct vector *)v1_2(D)].D.34245._M_impl.D.33558._M_finish;
  _14 = MEM[(const struct vector *)v1_2(D)].D.34245._M_impl.D.33558._M_start;
  _15 = _13 - _14;
  _9 = (unsigned long) _15;
  if (_9 > 9223372036854775804)
    goto <bb 3>; [54.67%]
  else
    goto <bb 4>; [45.33%]

  <bb 3> [local count: 587014656]:
  std::__throw_bad_array_new_length ();

  <bb 4> [local count: 1015040358]:
  return 10;

}

So I guess we are missing somewhere __builtin_assert that the length of vector copied is allways smaller then half of address space...

(In reply to Jan Hubicka from comment #23)
> So I guess we are missing somewhere __builtin_assert that the length of
> vector copied is allways smaller then half of address space...

Or the compiler could conclude that the result of subtracting two pointers (which must point into the same array) is always small enough.

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109442
> 
> --- Comment #24 from Jason Merrill <jason at gcc dot gnu.org> ---
> (In reply to Jan Hubicka from comment #23)
> > So I guess we are missing somewhere __builtin_assert that the length of
> > vector copied is allways smaller then half of address space...
> 
> Or the compiler could conclude that the result of subtracting two pointers
> (which must point into the same array) is always small enough.

Sounds like missed VRP, so I am adding Andrew.   

We may also remove conditional guarding __builtin_unreachable and having
values otherwise unused as useless at some point. This can be done
easily by DCE. However They may be stil used if the conditional is
optimized, so I am not sure this is desrable.

Honza

After some more checking we need help from libstdc++ here. Problem is that size does the pointer subtraction which is always positive, but we do not know it, and then converts it to size_type.

The following makes us to optimize the size check out.

libstdc++-v3/ChangeLog:

        * include/bits/stl_vector.h: Vector size is never negative.

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index df48ba3377f..59c9348724a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1114,7 +1114,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
       size_type
       size() const _GLIBCXX_NOEXCEPT
-      { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
+      {
+       ptrdiff_t __dif = this->_M_impl._M_finish - this->_M_impl._M_start;
+       if (__dif < 0)
+          __builtin_unreachable ();
+       return size_type(__dif);
+      }

       /**  Returns the size() of the largest possible %vector.  */
       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

vector::size() is called **very often** so needs to be as fast as possible. Does this still inline identically?

I tried something like that in r14-1452-gfb409a15d9babc and reverted it in r14-1470-gb7b255e77a2719, but my _M_invariant() function was more complicated.

Maybe the other part of my _M_invariant() function could be added directly to capacity()

--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1201,8 +1201,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       size_type
       capacity() const _GLIBCXX_NOEXCEPT
       {
-       return size_type(this->_M_impl._M_end_of_storage
-                          - this->_M_impl._M_start);
+       ptrdiff_t __dif
+         = this->_M_impl._M_end_of_storage - this->_M_impl._M_start;
+       if (__dir < 0)
+         __builtin_unreachable();
+       return size_type(__dif);
       }
 
       /**

> vector::size() is called **very often** so needs to be as fast as possible.
> Does this still inline identically?

Last year I made patch for inliner to ignore conditions guarding
__builtin_unreachable. Richi convinced me I should extend it to also
handle computations feeding the conditions.  I have WIP patch for that
and then those check should become noop for inlining decisions.
> 
> I tried something like that in r14-1452-gfb409a15d9babc and reverted it in
> r14-1470-gb7b255e77a2719, but my _M_invariant() function was more complicated.
> 
> Maybe the other part of my _M_invariant() function could be added directly to
> capacity()
> 
> --- a/libstdc++-v3/include/bits/stl_vector.h
> +++ b/libstdc++-v3/include/bits/stl_vector.h
> @@ -1201,8 +1201,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>        size_type
>        capacity() const _GLIBCXX_NOEXCEPT
>        {
> -       return size_type(this->_M_impl._M_end_of_storage
> -                          - this->_M_impl._M_start);
> +       ptrdiff_t __dif
> +         = this->_M_impl._M_end_of_storage - this->_M_impl._M_start;
> +       if (__dir < 0)
> +         __builtin_unreachable();
> +       return size_type(__dif);

If inliner handles those as noop, I think we could give it a try.
There will be some compile time costs, but hopefully not extreme. It
seems that adding the range check optimizes out quite a lot of calls
that inliner needs to do when dealing with vectors.

Honza

The master branch has been updated by Jan Hubicka <hubicka@gcc.gnu.org>:

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

commit r15-5336-gcee7d080d5c2a5fb8125878998b742c040ec88b4
Author: Jan Hubicka <hubicka@ucw.cz>
Date:   Sat Nov 16 14:04:32 2024 +0100

    Ignore conditions guarding __builtin_unreachable in inliner metrics
    
    This extends my last year attempt to make inliner metric ignore
    conditionals guarding __builtin_unreachable.  Compared to previous
    patch, this one implements a "mini-dce" in ipa-fnsummary to avoid
    accounting all statements that are only used to determine conditionals
    guarding __builtin_unnecesary.  These will be removed later once value
    ranges are determined.
    
    While working on this, I noticed that we do have a lot of dead code while
    computing fnsummary for early inline. Those are only used to apply
    large-function growth, but it seems there is enough dead code to make this
    valud kind of irrelevant.  Also there seems to be quite a lot of const/pure
    calls that can be cheaply removed before we inline them.  So I wonder if we
    want to run one DCE before early inlining.
    
    gcc/ChangeLog:
    
            PR tree-optimization/109442
            * ipa-fnsummary.cc (builtin_unreachable_bb_p): New function.
            (guards_builtin_unreachable): New function.
            (STMT_NECESSARY): New macro.
            (mark_stmt_necessary): New function.
            (mark_operand_necessary): New function.
            (find_necessary_statements): New function.
            (analyze_function_body): Use it.
    
    gcc/testsuite/ChangeLog:
    
            * gcc.dg/ipa/fnsummary-1.c: New test.

Created attachment 59610 [details]
patch for non-negative checks in std::vector::size and std::vector::capacity

This patch adds non-negativity checks to size and capacity.  With the patch to ipa-fnsummary it should not have effect on inlining decisions and I would say that any code quality regressions caused by the extra conditional should be fixed at middle-end side.

I tested clang build.  Looking for throw_bad calls there are only 3 called considerably often (bad_allloc, bad_array_new_length and function_callv).
The patch seems to reduce bad_alloc and bad_array_new_length calls considerably:

bad_alloc 380->147
bad_array_new_length 832->128

I will test the _M_invariant patch same way.  While it should not have effect on inliner (I will double-check), I am not sure it is a good idea.  It adds a lot of loads to often uses size accessor which will take some effort for middle-end to handle.

(In reply to Jan Hubicka from comment #30)
> I will test the _M_invariant patch same way.  While it should not have
> effect on inliner (I will double-check), I am not sure it is a good idea. 
> It adds a lot of loads to often uses size accessor which will take some
> effort for middle-end to handle.

Yeah, good point. So better to go with your separate checks in size() and capacity() which only load the values that those functions need anyway.

That patch is OK for trunk if you're happy with its codegen.

thanks. I think codegen should be fine, so I will commit the patch so we get it tested by LNT.

We may get bit better here.
Applying the reverted _M_invariant patch (r14-1452-gfb409a15d9babc) gets me 133 bad_alloc and 128 bad_array_new_length calls.

I will try a version that adds the extra size <= capacity check to capacity() that I think is used less.  Also it seems at some places size is computed directly instead of calling size function which may be reason for remaining bad allocs.

The master branch has been updated by Jan Hubicka <hubicka@gcc.gnu.org>:

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

commit r15-5361-gaac5c57ee167230cea466064951daf06e42197b9
Author: Jan Hubicka <hubicka@ucw.cz>
Date:   Sun Nov 17 01:21:04 2024 +0100

    Add __builtion_unreachable to vector::size(), vector::capacity()
    
    This patch makes it clear that vector sizes and capacities are not
    negative.  With recent change to ipa-fnsummary this should not affect
    inlining and improves codegen of some vector manipulation functions.
    
    I tested clang build.  Looking for throw_bad calls there are only 3
    called considerably often (bad_allloc, bad_array_new_length and
    function_callv).
    The patch seems to reduce bad_alloc and bad_array_new_length calls
    considerably:
    
    bad_alloc 380->147
    bad_array_new_length 832->128
    
    libstdc++-v3/ChangeLog:
    
            PR tree-optimization/109442
            * include/bits/stl_vector.h: (vector::size(),
            vector::capacity()): Add __builtin_unreachable call to announce
            that size and capacity are non-negative.
    
    gcc/testsuite/ChangeLog:
    
            PR tree-optimization/109442
            * g++.dg/tree-ssa/pr109442.C: New test.

The memory allocation is still not elided for a sample from duplicate ticket 116651:

bool test1(const std::vector<int>& in) {
    return in == std::vector<int>{42};
}


My naiive expectation is that the `test1` function would be optimized to an equivalent of:


bool test2(const std::vector<int>& in) {
    return in.size() == 1 && in[0] == 42;
}


Godbolt playground https://godbolt.org/z/sn5Gzq1P6

On 

#include <vector>
bool test1(const std::vector<int>& in) {
    return in == std::vector<int>{42};
}


we produce:
bool test1 (const struct vector & in)
{
  bool _12;
  int * _13;
  int * _14;
  long int _24;
  unsigned int _43;
  int * _50;
  unsigned int _64;
  bool iftmp.5_69;

  <bb 2> [local count: 1073741824]:
  _50 = operator new (4);
  MEM <unsigned int> [(char * {ref-all})_50] = 42;
  _13 = MEM[(int * *)in_6(D)];
  _14 = MEM[(int * *)in_6(D) + 8B];
  _24 = _14 - _13;
  if (_24 == 4)
    goto <bb 3>; [34.00%]
  else
    goto <bb 4>; [66.00%]

  <bb 3> [local count: 182536112]:
  _43 = MEM <unsigned int> [(char * {ref-all})_13];
  _64 = MEM <unsigned int> [(char * {ref-all})_50];
  _12 = _43 == _64;

  <bb 4> [local count: 1073741824]:
  # iftmp.5_69 = PHI <_12(3), 0(2)>
  operator delete (_50, 4);
  return iftmp.5_69;

}

Allocation is not removed because we store 42 to the block:
  MEM <unsigned int> [(char * {ref-all})_50] = 42;
and later read it again
  _64 = MEM <unsigned int> [(char * {ref-all})_50];

I think this is pass ordering issue.  At PRE time we have
  _61 = __builtin_memcmp (_13, _50, 4);
eventually it is taken away by strlen pass, but there is no another FRE to handle this scheduled after strlen.

I believe strlen_pass::handle_builtin_memcmp should eventually move to forwprop
(fold_stmt may not inspect immediate uses).  That would help this particular
case.

Note that in general value-numbering could be improved to handle some memory
builtins - we now have robust infrastructure to query known bytes for a
memory area (even if only sparse).  The question is whether it's worth the
cost of course - the examples look quite artificial.

Unfortunately the examples are not artificial. People do write business logic code as `vector_variable == std::vector<std::string>{"*"}`. That particular example is taken from our codebase and I easily find 4 exact matches of `!= std::vector<std::string>{"*"}` in production code.

I also find 35 matches of `== std::vector<` in tensorflow project, and more than 500 matches in tests of different projects that we use (looks like there's more than 1000 of matches, unfortunately the output is limited to 500 matches)

That doesn't mean it has to be fast though. If people want to write slow code, they get slow programs!

(In reply to Antony Polukhin from comment #37)
> Unfortunately the examples are not artificial. People do write business
> logic code as `vector_variable == std::vector<std::string>{"*"}`. That
> particular example is taken from our codebase and I easily find 4 exact
> matches of `!= std::vector<std::string>{"*"}` in production code.

This seems like somebody should write a utility function that expresses the business logic ("not wildcard" or whatever it means) and then make sure that's implemented efficiently, and replace all the inefficient code.

> That doesn't mean it has to be fast though.

Indeed. Alas, people write sub-optimal code, especially when pressed for time or when compatibility with old versions of the C++ standard is required. It would be nice to have those cases optimized if they do not add maintenance burden for GCC.

I re-opened PR 116651 for the other missed optimizations that was mentioned dealing with `vector::operator==`; I have some ideas on how to fix that one (there are some generic optimizations missing too).

So the original bug report is fixed for GCC 15.

The new test has regressed for arm (PR 125741) due to the libstdc++ change r17-987-g14617bda37f8c7 - if any middle end experts are able to help understand that we would be grateful.