Speeding up C++ at -O0 (Was: GCC 3.5 Status (2004-08-29))

["Giovanni Bajo" <giovannibajo at libero dot it>]

Matt Austern wrote:

> You are not the only person who cares about C++ compilation times at
> -O0.  This is a major concern for Apple, and I expect that improving
> C++ -O0 compilation time will be my primary activity for some time.  I
> don't think the current status it too awful, actually, but we do still
> have a way to go.

Yes, and comparing GCC with other compilers (say, MSVC or EDG) shows how long
this way to go is.


> Do you have any suggestions for improving -O0 compile speed?

(1) Enable basic optimizers at O0 to cleanup the initial RTL we generate. This
also comprehends:
  (a) Fixing up DCE/CCP as explained by Steven so that it does not destroy user
variables
  (b) Checking whether entering and exiting SSA form is too much of a slowdown,
and see if we can have a DCE/CCP which don't require SSA and it's still fast
enough for our needs.

(2) Lazy processing of classes, delaying things as much as possible to their
first use. For instance, building the builtin constructor, copy constructor,
operator= can be delayed until they are really necessary (if ever). I believe
Mark already did part of this, so following up his work could be good.

(3) It looks to me that partial ordering of function templates and class
templates is always recomputed any time we need it. For instance,
most_specialized first processes all specializations looking for the ones which
are valid for the given call/instantiation/whatever (a call to get_bindings for
each specialization), and then partial-order among them. This could be
optimized in two ways:
  (a) keeping a hash table where the key is a pair of specializations and the
data is -1,0,1. This is trivial to implement, but still causes us to always try
to call get_bindings for all the specializations.
  (b) keeping specializations sorted in a tree with the invariant property "a
node is always less specialized than any of its children". You can then have a
special visit algorithm starting from the leaves which will call get_bindings
starting from the most specialized up to the less, and repeating the same for
each subtree (to find ambigouities). I have the full algorithm in my mind (but
I am not sure it is correct either - just an idea), so I can give you more
details if you are interested.
To be fair, I don't know if this is worth the hassle - I have no idea how much
partial ordering affects C++ compilation, but it certainly looks non-trivial to
me.

(4) The tentative parsing idiom in the parser is of course necessary, but it is
very costy. Plus, it looks like it is abused right now (for simple lines of
code, we end up trying to match the same rule for the same tokens two or three
times, in different tentative parsing attempts). There was a stopgap put by
Mark as some point to the worst offenders (cp_parser_template_id,
cp_nested_name_specifier) which replaces the parsed tokens with a special
internal token, already representing the given node. An additional speedup
would be to flag each token from which matching a certain grammar rule failed.
For instance, if we try to cp_parse_class_name from token #12 and fail, we
could flag a bit in token #12 saying that "from this token, attempts to parse
class names will always fail", so that we can error out immediatly in case of
subsequent attempts. Also, this optimization can be scaled up very easily to
cover most of the common rules in the grammar (just add more bits, and couples
of paired calls to common functions to test/set the bits).

Notice that this is not my personal todo list - actually, I doubt to have time
to personally work on any of the above points. I am failry positive there also
is some non-trivial caching/optimization that could be performed in
name-lookup, but I don't know that part of the FE enough.

Do you have other plans/ideas?

Giovanni Bajo