[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-25 11:29 -------
Subject: Re:  [4.0 Regression] IV-OPTS is O(N^3)

> > (*) 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, 
> 
> It returns to you an evolution that might contain SSA_NAMEs.

Hmm... if this is all you can tell, I start fear even more; this does
not define any semantics at all :-)

More seriously -- which of the possibilities?  If I have loops like

while (...)
  {
    while (...)
      {
        x_1 = something ();
      }
    x_2 = phi (x_1);
    x_3 = x_2 + 1;
  }

What will analyze_scalar_evolutions return for x_3? There are (at least)
three possible valid values:

x_3
x_2 + 1
x_1 + 1

In this example probably the last one will be chosen, but in more
complicated cases you cannot tell (without simulating what scev analysis
does).  It might be better to not export analyze_scalar_evolution at
all and to force it to be used through
instantiate_parameters/resolve_mixers, that have at least a well defined
semantics of return value -- I hope.  Till recently I believed that I
made the functions to behave reasonably in cases when values defined
inside loop are used outside of it (through chain of lcssa phi nodes),
but my attempt to remove the hacks that ensure sane behavior of the
results for ivopts causes misscompilations; I am investigating the cause
now.


-- 


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