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

["rakdver at atrey dot karlin dot mff dot cuni dot cz" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2005-01-25 01:57 -------
Subject: Re:  [4.0 Regression] IV-OPTS is O(N^3)

> >>          * tree-data-ref.c (analyze_overlapping_iterations): chrecs that
> >>          are equal overlap on every iteration.
> >>
> >> This stuff is just simple symbolic differencing, and checking of
> >> invariantness of symbols,
> >> But it is indeed starting to se the symbolic scev info
> >
> > Ugh... OK, if you think it is a right way...  Anyway, I am seriously
> > considering resurrecting the simple iv analysis for purposes of passes
> > that are not interested in this fancy stuff.  Overhead of scev is
> > probably acceptable if it is only used for this type of analysis,
> > but for other purposes it is clearly overkill.
> 
> Uh, almost all high level loop optimizations are going to do very badly in 
> the depth of the loop nest.

Remove "almost" and "high level" from this sentence and I will agree
with you.  This really does not worry me that much.

> The fact that scev doesn't do so well on a 100 deep loop nest doesn't 
> really concern me at all.

Me neither.  Its time and memory consumption on normal testcases however
is not entirely satisfactory (not critical, but there definitely is a
place for improvement), and implementation could (should?) also be
significantly cleaned up.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595