Re: [patch] for PR 19224

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

Jeffrey A Law wrote:
> On Mon, 2005-01-03 at 00:17 +0100, Zdenek Dvorak wrote:
> > 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.

In my opinion, the cache mechanism implemented by Zdenek serves only
the case when the result of analyze_scalar_evolution is a symbolic
expression.  When analyze_scalar_evolution leads to an evolution with
no symbols, the result is stored in the scev database and any
subsequent query from instantiate_parameters end in constant time.

Sebastian