Re: Out-of-sight compile times for calculate_loop_depth

[Michael Hayes <m dot hayes at elec dot canterbury dot ac dot nz>]

Brad Lucier writes:
 > I think that code like this is reasonable, but we've differed on this
 > point before ...

Lets's say that is atypical---it is certainly several standard
deviations from the mean program.

I had to run the compiler overnight on your testcase to get to the bit
that interested me.  This is what I found:  

19990 basic blocks
34889 edges
6595  natural loops  (max loop nesting 3)

What kills the performance natural loop detection code is that there
are 4940 disjoint loops all sharing the same loop header and a basic
block having 7866 edges.  Thus while most of the loops only have 3
nodes, they have 7865 exits each!

I'm gonna have to ponder this for a while.  I can see methods for
improving the natural loop analysis for a nasty CFG like this but I
fear that it will penalise the common cases and the readability of the
code.  I think I'll implement some more statistics gathering first.

We probably need a bailout mechanism if we detect a CFG with many
shared loop headers.  These will never be optimised very well anyway.
Ideally these shared loops should all be merged.

Michael.