------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-25 11:14 ------- Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> rakdver at atrey dot karlin dot mff dot cuni dot cz wrote: > > Adding the instantiation cache was compile time neutral on normal code, > > so I don't think the effect on scev cost is significant. > > > > How that? You end up querying and caching an evolution for every > instantiation of an SSA_NAME! which is pretty cheap (constant time operation); note that we do an equivalent lookup in the analyze_scalar_evolution call in any case, also without causing any compile time problems. I haven't measured any slowdown on normal testcases. > I will quantify the number of queries wrt the number of times this > information is useful. I think that with my patch, the instantiation > cache information is used zero times on a bootstrap. I don't think so. Please come up with some numbers, otherwise this discussion is pointless. > > 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). > > > > This also could be a bad use of the scev analysis. partly -- see the analysis at the PR. However one O(n) per query comes from scev itself. > For Steven: you can have a O(N**3) algorithm very simply: > > loop O(N) times > loop O(N) times > algorithm in O(N) > > > 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. > > Just set the SSA_NAME to not_analyzed_yet or NULL_TREE, and the next time > you'll ask for the evolution of this SSA_NAME you'll analyze the > evolution from scratch. This does not work, of course. When the ssa name is removed, you must remove all references to it from the cache. Otherwise you will ICE when you try to process the relevant entry in (say) instantiate_parameters. What's worse, the ssa name may get reused by ssa name management, thus causing you not even be able to note the change, and thus possibly to misscompilations. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
