Re: libstdc++: Speed up push_back

[Jan Hubicka <hubicka@ucw.cz>]

> > On Sunday, 19 November 2023 22:53:37 CET Jan Hubicka wrote:
> > > Sadly it is really hard to work out this
> > > from IPA passes, since we basically care whether the iterator points to
> > > the same place as the end pointer, which are both passed by reference.
> > > This is inter-procedural value numbering that is quite out of reach.
> > 
> > I've done a fair share of branching on __builtin_constant_p in 
> > std::experimental::simd to improve code-gen. It's powerful! But maybe we 
> > also need the other side of the story to tell the optimizer: "I know you 
> > can't const-prop everything; but this variable / expression, even if you 
> > need to put in a lot of effort, the performance difference will be worth 
> > it."
> > 
> > For std::vector, the remaining capacity could be such a value. The 
> > functions f() and g() are equivalent (their code-gen isn't https://
> > compiler-explorer.com/z/r44ejK1qz):
> > 
> > #include <vector>
> > 
> > auto
> > f()
> > {
> >   std::vector<int> x;
> >   x.reserve(10);
> >   for (int i = 0; i < 10; ++i)
> >     x.push_back(0);
> >   return x;
> > }
> > auto
> > g()
> > { return std::vector<int>(10, 0); }
> 
> With my changes at -O3 we now inline push_back, so we could optimize the
> first loop to the second. However with 
> ~/trunk-install/bin/gcc -O3  auto.C  -S -fdump-tree-all-details -fno-exceptions -fno-store-merging -fno-tree-slp-vectorize
> the fist problem is right at the begining:
> 
>   <bb 2> [local count: 97603128]:
>   MEM[(struct _Vector_impl_data *)x_4(D)]._M_start = 0B;
>   MEM[(struct _Vector_impl_data *)x_4(D)]._M_finish = 0B;
>   MEM[(struct _Vector_impl_data *)x_4(D)]._M_end_of_storage = 0B;
>   _37 = operator new (40);

I also wonder, if default operator new and malloc can be handled as not
reading/modifying anything visible to the user code.  That would help
us to propagate here even if we lose track of points-to information.

We have:

  /* 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 ";
Which informs alias analysis that new returns pointer to memory
not aliasing with anything and that free is not reading anything
from its parameter (but it is modelled as a write to make it clear
that the memory dies).

stmt_kills_ref_p special cases BUILT_IN_FREE but not OPERATOR delete
to make it clear that everything pointed to by it dies.   This is needed
because 'o' only means that some data may be overwritten, but it does
not make it clear that all data dies.

Not handling operator delete seems like an omision, but maybe it is not
too critical since we emit clobbers around destructors that are usually
right before call to delete.  Also ipa-modref kill analysis does not
understand BUILT_IN_FREE nor delete and could.

I wonder if we can handle both as const except for side-effects
described.

Honza
>   _22 = x_4(D)->D.26019._M_impl.D.25320._M_finish;
>   _23 = x_4(D)->D.26019._M_impl.D.25320._M_start;
>   _24 = _22 - _23;
>   if (_24 > 0)
>     goto <bb 3>; [41.48%]
>   else
>     goto <bb 4>; [58.52%]
> 
> So the vector is fist initialized with _M_start=_M_finish=0, but after
> call to new we already are not able to propagate this.
> 
> This is because x is returned and PTA considers it escaping.  This is
> problem discussed in 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112653
> Which shows that it is likely worthwhile to fix PTA to handle this
> correctly.