PATCH: More CSE memory reduction
Jeffrey A Law
Fri Mar 31 09:58:00 GMT 2000
In message < 20000331083915Y.email@example.com >you write:
> This patch removes the N^2 memory usage in CSE, but doesn't fix the
> N^2 time complexity, which seems considerably harder. However, this
> patch does significantly reduce the constant, and I can see how more
> could be done as well.
An FYI -- Vlad Makarov has another round of potential changes to CSE which
should help the time complexity.
Basically it saves some state for re-use during the skip-blocks and
follow-jumps phase of CSE. I'd expect this increases memory usage, but
I don't know by how much. The impact on compile times is drastic -- for
Cygnus's favorite plumhall tests we're looking at cutting the total compile
for those files at -O2 by around 60%. For building GCC itself (cc1) the
times improve by 7-10% based on the platform in use.
Vlad originally posted the change internally -- we haven't had a chance to
review it at all. I'd be more than happy to post it here for folks to beat
> Again, I'm working in a tree where a bzero call gets expanded to
> several thousand sets in a single basic block -- that shouldn't
> happen, but it's a good approximation to cases that really do happen.
Right. FWIW, this was bug in Kenner's recent bit vs byte alignment
changes and has been fixed.
> The basic issue was that alias.c's canon_rtx generates new RTL in some
> cases. But, it's always the same RTL, so it makes sense to cache the
Yup. I've always wanted to make some changes in the aliasing code basically
to avoid consing up too many hunks of RTL.
Consider that it's relatively common to need to have to check one MEM
against a list of other MEMs for aliasing -- this happens now in flow &
loop and in my code to tie in alias analysis to gcse. Creating a first
class interface for that kind of operation could avoid a lot of useless calls
to canon_rtx by only canonicalizing the invariant MEM once and it would
be more obvious than forcing the callers to canon & cache the invariant
More information about the Gcc-patches