This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] for PR 19224
Hello,
> > > instantiate_parameters_1 may have exponential time complexity, since it may
> > > get called recursively several times for a single ssa name if it occurs in
> > > one expression, which in turn may cause it to be called several times for
> > > other ssa name, etc. This patch fixes the problem by caching the
> > > results.
> > >
> > > Bootstrapped & regtested on i686 and ia64.
> > >
> > > Zdenek
> > >
> > > PR tree-optimization/19224
> > > * tree-scalar-evolution.c (get_instantiated_value,
> > > set_instantiated_value): New functions.
> > > (instantiate_parameters_1): Cache the results.
> > > (instantiate_parameters, resolve_mixers): Initialize and free
> > > the cache.
> > This is fine. Please install if you haven't done so already.
> >
> >
>
> Jeffrey, I think that the patch proposed by Zdenek for solving PR
> tree-optimization/19224 is not the right fix. The patch that I have
> proposed <http://gcc.gnu.org/ml/gcc-patches/2005-01/msg00399.html> is
> enough for fixing the exponential behavior, without increasing the
> memory usage by using a cache.
>
> Here are Zdenek's comments from the PR with which I disagree now:
> > not really (well, maybe in this particular case, but not in
> > general). Your patch definitely helps (and you should submit it
> > anyway), but yhe problem is that even with your patch it may happen
> > that instantiate_parameters is called recursively several times for
> > one ssa name if the expression contains it several times, and if
> > this happens for several expressions in a row, you get the
> > exponential complexity.
>
> Here is my analysis of the problem:
>
> The bug occurs only when analyze_scalar_evolution is unable to produce
> a determined evolution, in which case a symbolic expression is stored
> in the scev database. When instantiate_parameters obtains a symbolic
> expression by querying the scev database, it will try to instantiate
> the missing information, leading to some huge instantiation calls,
> before the patch applied by Zdenek.
>
> The aim of the patch that I have proposed is to cut the instantiation
> tree after the first symbol that is determined unknown. Thus, if the
> same symbol that lead to unknown evolution occurs several times in the
> same expression to be instantiated, it is analyzed only once, after
> which the instantiation ends.
I agree that your patch should be applied as well, since it handles the
common case more efficiently. I however think that my fix is useful as well
anyway, since it may happen that by instantiation of symbol gives
an expression that is not unknown, and that this symbol is instantiated
several times within one expression.
Zdenek