------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 10:32 -------
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!
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.
> 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.
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.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
