[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@gcc.gnu.org>]

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

> > Other part is that scev tries to be too clever.  Without need to
> > represent nonaffine induction variables (that we do not use anywhere)
> > we could use more memory efficient representation of ivs.
> > Without need to handle symbolic references (that we also do not use
> > anywhere, we could store evolutions in a fully instantiated form, and
> > we would not need instantiate_parameters/resolve_mixers functions atall.
> 
> Uh, symbolic references are or will be used to do data dependence when 
> MEM_REF and ARRAY_REF couldn't be generated from the pointers.

How?  If the reference is left in symbolic form, it means that you know
nothing about its value, so the only thing you can do with it is to
check its equality/inequality, in code like

while (...)
  {
    i = something_weird ();

    a[i] = ...;  (a)
    a[i+1] = ...;  (b)
    a[i] = ...;  (c)
  }

to find that (b) is independent on (a) and (c) and to find the
dependence between (a) and (c), but you do not need scev for this --
value numbering info is enough.


-- 


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