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
On Tue, 20 Jun 2006, Ian Lance Taylor wrote:
> Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:
>
> > > 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.
>
> 8 is OK, then. Thanks.
This is what I committed.
Richard.
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c (revision 114839)
+++ tree-ssa-loop-niter.c (revision 114840)
@@ -886,7 +886,12 @@ tree_simplify_using_condition (tree cond
return tree_simplify_using_condition_1 (cond, expr);
}
-
+
+/* The maximum number of dominator BBs we search for conditions
+ of loop header copies we use for simplifying a conditional
+ expression. */
+#define MAX_DOMINATORS_TO_WALK 8
+
/* Tries to simplify EXPR using the conditions on entry to LOOP.
Record the conditions used for simplification to CONDS_USED.
Returns the simplified expression (or EXPR unchanged, if no
@@ -899,12 +904,16 @@ simplify_using_initial_conditions (struc
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;
+ bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
if (!single_pred_p (bb))
@@ -926,6 +935,7 @@ simplify_using_initial_conditions (struc
cond);
expr = exp;
+ ++cnt;
}
return expr;
Index: ChangeLog
===================================================================
--- ChangeLog (revision 114839)
+++ ChangeLog (revision 114840)
@@ -1,3 +1,8 @@
+2006-06-21 Richrad Guenther <rguenther@suse.de>
+
+ * tree-ssa-loop-niter.c (simplify_using_initial_conditions):
+ Limit iteration over the dominators.
+
2006-06-20 Roger Sayle <roger@eyesopen.com>
* config/mips/iris6.h (LIB_SPEC): Add support for -pthread.