[Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- 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