This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix quadraticness in simplify_using_initial_condition
- From: Ian Lance Taylor <iant at google dot com>
- To: Richard Guenther <rguenther at suse dot de>
- Cc: gcc-patches at gcc dot gnu dot org, Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Date: 20 Jun 2006 10:01:59 -0700
- Subject: Re: [PATCH] Fix quadraticness in simplify_using_initial_condition
- References: <Pine.LNX.4.64.0606151721050.4318@nyjnma.fhfr.qr>
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