------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-25 01:52 ------- Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> Do remember that this bug is about bad behavior with deeply nested loops > and we already have other algorithms that are quadratic in the loop nest > depth. So I really wouldn't consider this to be a very serious problem, > but rather something that could be improved. > > It is a shame that Seb has so far not commented on the behavior of his > scev algorithm with respect to the loop nest depth. Is it expected to > be cubic in the loop nest depth? Perhaps he can improve the algorithm? the algorithm itself is not cubic with loop depth, but worst case linear (per query) (*). This time complexity is acceptable, IMHO. (*) I hope; scev is a mess of mutualy recursive functions -- analyze_scalar_evolution calling number_of_iterations calling instantiate_parameters calling analyze_scalar_evolution again, with instantiate_parameters hacked so that the infinite cycle cannot occur is my favourite one. Nobody can say anything sure about behavior of scev -- it is not even well defined what analyze_scalar_evolutions will return to you, unless you call instantiate_parameters or resolve_mixers on the result. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
