------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-24 22:16 ------- Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > Still there remain some inefficiences within the scev analysis itself. > > > > Zdenek, have you tried to revert the patch that caches the > instantiation information? This could speed up things a little. > > On a side note, I wonder how many times we're using this instantiation > cache, in other words whether we pay a high price for the scev > analysis for some (probably) rare cases... Adding the instantiation cache was compile time neutral on normal code, so I don't think the effect on scev cost is significant. The problem is that we end up calling the instantiate_parameters_1 function 83214+2453273 (outside + recursive) times (for N=100). We also call analyze_scalar_evolution_1 1146317 times. Many of these calls create POLYNOMIAL_CHREC nodes (2894131 calls to build3_stat). Large part of 5142869 of build_int_cst_wide calls is very likely also due to scev analysis. This is not going to be cheap. Removing the instantiation cache definitely would not decrease the number of instantiate_parameters_1 calls (might increase it, in fact, although I don't know how significantly). One part of the problem is that loop optimizers need to throw away the scev caches after each change to loops, which leads to recounting the information too much. Allowing to invalidate only changed parts helps, but seems to be relatively costly on normal code -- you need to scan the hash table for things that refer to removed or from some other reason invalidated ssa names, which is slow. And to make things worse, this change of course means that most of the information is left in the hash table, i.e. the size of the table grows and these scans get slower and slower. The alternative -- checking the validity of entries only when querying the cache -- is not possible, since we reuse the released ssa names, so we would be unable to recognize the validity of the information. Other part is that scev tries to be too clever. Without need to represent nonaffine induction variables (that we do not use anywhere) we could use more memory efficient representation of ivs. Without need to handle symbolic references (that we also do not use anywhere, we could store evolutions in a fully instantiated form, and we would not need instantiate_parameters/resolve_mixers functions at all. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
