C++ compile and execution times

[Roger Sayle]

> The first I can give (see below). In summary, garbage collection,
> expand, and loop analysis become slower, but it's not that one part
> is entirely dominating. I think the latter I leave to those with
> more experience (also experience what to look for).

I have a suggestion that I think may help speed up GCC's "expand".
I've not mentioned it earlier, because I didn't think that "expand"
was one of the more time consuming passes of GCC...

The problem I've noticed is that the recursion in "fold" appears
to be O(n^2) instead of O(n).  Basically, the function "fold"
first calls "fold" on all of a node's children, and then attempts
to transform the node itself.  Many of these final node modifying
transformations can lead to further simplifications, and so they
recursively call fold on their result.  The problem is that
this then results in repeated calls to "fold" on the node's children,
their children and so on.  In a deep tree, "fold" may called on the
same leaf node repeatedly.

A possible solution is that we use a bit in the "tree" to indicate
that an expression has already been folded.  This is initially set to
false when the node is created, but set to true on return from "fold".
Then if "fold" is ever called with an already folded tree, it can return
immediately.  Provided that all modifications to a tree clear this bit,
we save a huge amount of recomputation, and needless tree traversals.

I believe the tree-ssa branch may already have a similar approach with
a bit to indicate that a tree is in gimple-form.  From my limited
experience so far, simplify_rtx doesn't appear to suffer from this
problem, but may also benefit from a similar scheme.

Does this sound like a reasonable approach?  Are there any free bits?


Alternatively, fold could be reorganized/renamed such that it takes
an additional "bool" parameter indicating whether all of the node's
children have already been folded.  This "fold2" could then be wrapped
by "fold" to preserve the original middle-end API.  The time consuming
recursive calls could then indicate that only the top-level of the
tree needs re-folding.


Can anyone confirm whether its "fold" thats taking a significant
amount of time in "expand", or something else entirely?

Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833