[PATCH] Fix quadraticness in simplify_using_initial_condition

[Zdenek Dvorak]

Hello,

> Richard Guenther <rguenther@suse.de> writes:
> 
> > Index: tree-ssa-loop-niter.c
> > ===================================================================
> > *** tree-ssa-loop-niter.c	(revision 114674)
> > --- tree-ssa-loop-niter.c	(working copy)
> > *************** simplify_using_initial_conditions (struc
> > *** 899,910 ****
> >     edge e;
> >     basic_block bb;
> >     tree exp, cond;
> >   
> >     if (TREE_CODE (expr) == INTEGER_CST)
> >       return expr;
> >   
> >     for (bb = loop->header;
> > !        bb != ENTRY_BLOCK_PTR;
> >          bb = get_immediate_dominator (CDI_DOMINATORS, bb))
> >       {
> >         if (!single_pred_p (bb))
> > --- 899,914 ----
> >     edge e;
> >     basic_block bb;
> >     tree exp, cond;
> > +   int cnt = 0;
> >   
> >     if (TREE_CODE (expr) == INTEGER_CST)
> >       return expr;
> >   
> > +   /* Limit walking the dominators to avoid quadraticness in
> > +      the number of BBs times the number of loops in degenerate
> > +      cases.  */
> >     for (bb = loop->header;
> > !        bb != ENTRY_BLOCK_PTR && cnt < 8;
> >          bb = get_immediate_dominator (CDI_DOMINATORS, bb))
> >       {
> >         if (!single_pred_p (bb))
> > *************** simplify_using_initial_conditions (struc
> > *** 926,931 ****
> > --- 930,936 ----
> >   				   cond);
> >   
> >         expr = exp;
> > +       ++cnt;
> >       }
> >   
> >     return expr;
> 
> 
> Well, of course you knew somebody was going to say that magic numbers
> like "8" are a little troubling.  I don't like to make busy work, but
> it seems like maybe this should be a parameter.  Or, if not a
> parameter, maybe it should at least be a #define constant.
> 
> And 8 seems just a little small to me; I can imagine 8 nested loops
> after inlining (insert Han Solo quote here).  Maybe it should be, say,
> 32, which seems really unlikely.

in fact this is not about nested loops; what we want to handle are
conditions created by loop header copying.  The relevant conditions
are almost always directly before the loop, and basically the only
reason why it is good to have greater depth than one is for cases the
exit condition is a conjunction of several conditions.  So I think 8 is
more than enough.

Zdenek

> I'll approve the patch with a #define constant of 32.  But please wait
> 24 hours before committing in case this prods anybody else to comment.
> 
> Thanks.
> 
> :REVIEWMAIL:
> 
> Ian