Re: [PATCH] Fix PR67783, quadraticness in IPA inline analysis

[Jan Hubicka <hubicka@ucw.cz>]

> On Thu, 1 Oct 2015, Richard Biener wrote:
> 
> > 
> > The following avoids quadraticness in the loop depth by only considering
> > loop header defs as IVs for the analysis of the loop_stride predicate.
> > This will miss cases like
> > 
> > foo (int inv)
> > {
> >  for (i = inv; i < n; ++i)
> >   {
> >     int derived_iv = i + i * inv;
> >     ...
> >   }
> > }
> > 
> > but I doubt that's important in practice.  Another way would be to
> > just consider the containing loop when analyzing the IV, thus iterate
> > over outermost loop bodies only, replacing the
> > 
> >   simple_iv (loop, loop_containing_stmt (stmt), use, &iv, true)
> > 
> > check with
> > 
> >   simple_iv (loop_containing_stmt (stmt), loop_containing_stmt (stmt), 
> > use, &iv, true);
> > 
> > but doing all this analysis for each stmt is already quite expensive,
> > esp. as we are doing it for all uses instead of all defs ...
> > 
> > Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> > 
> > Honza, is this ok or did you do the current way on purpose (rather
> > than for completeness as it was easy to do?)
> 
> Applied as r228472.

Ah, sorry. I wrote you a reply but apparently did not send.  Yes, the patch looks
resonable - it is a heuristics after all.  Lets watch if the change make any difference
on polyhedron and other benchmarks.

Honza