[PATCH] Fix quadraticness in simplify_using_initial_condition

[Ian Lance Taylor]

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.

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