From: Jonathan Wakely <jwakely@redhat.com>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: Matthias Kretz <m.kretz@gsi.de>,
rguenther@suse.de, libstdc++@gcc.gnu.org,
gcc-patches@gcc.gnu.org
Subject: Re: libstdc++: Speed up push_back
Date: Thu, 23 Nov 2023 16:20:52 +0000 [thread overview]
Message-ID: <CACb0b4nQ57Y14nLYjFWF1SSE6GJLznd8EOxUckk6mBfGC0HdPg@mail.gmail.com> (raw)
In-Reply-To: <ZV9w5RCqdLTyYJtV@kam.mff.cuni.cz>
On Thu, 23 Nov 2023 at 15:34, Jan Hubicka <hubicka@ucw.cz> wrote:
>
> > > 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.
No, there's no way to know if the default operator new is being used.
A replacement operator new could be provided at link-time.
That's why we need -fsane-operator-new
> 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).
But this only applies to new T[n] not to operator new(n * sizeof(T)).
So it's not relevant to std::vector.
> 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.
>
next prev parent reply other threads:[~2023-11-23 16:21 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-19 21:53 Jan Hubicka
2023-11-20 12:09 ` Jonathan Wakely
2023-11-20 15:44 ` Jan Hubicka
2023-11-20 16:46 ` Jonathan Wakely
2023-11-21 12:50 ` Jan Hubicka
2023-11-21 13:07 ` Jonathan Wakely
2023-11-23 8:15 ` Matthias Kretz
2023-11-23 15:07 ` Jan Hubicka
2023-11-23 15:33 ` Jan Hubicka
2023-11-23 15:43 ` Jan Hubicka
2023-11-23 16:26 ` Jonathan Wakely
2023-11-23 16:20 ` Jonathan Wakely [this message]
2023-11-24 10:21 ` Martin Jambor
2023-11-24 10:23 ` Richard Biener
2023-11-24 19:45 ` Marc Glisse
2023-11-24 20:07 ` Jan Hubicka
2023-11-24 21:55 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CACb0b4nQ57Y14nLYjFWF1SSE6GJLznd8EOxUckk6mBfGC0HdPg@mail.gmail.com \
--to=jwakely@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=libstdc++@gcc.gnu.org \
--cc=m.kretz@gsi.de \
--cc=rguenther@suse.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).