------- Comment #13 from sebpop at gmail dot com 2007-11-03 05:19 -------
Subject: Re: [4.3 Regression] Exponential time behavior in PRE
> Yes, the heuristics can sometimes generate a very large number of
> copies to eliminate a single redundancy.
> This is jsut the way the standard PRE heuristics work.
> If you want to try to come up with a better one, you are welcome to :)
>
What about stopping the computation when we see that there are too
many values that are anticipable? Here is a patch that restores the
compile time on all the reported testcases. The constant should be a
param, and the default value should be higher probably.
Index: tree-ssa-pre.c
===================================================================
--- tree-ssa-pre.c (revision 129775)
+++ tree-ssa-pre.c (working copy)
@@ -1847,6 +1847,13 @@ compute_partial_antic_aux (basic_block b
if (block_has_abnormal_pred_edge)
goto maybe_dump_sets;
+ /* If there are too many partially anticipatable values in the
+ block, phi_translate_set can take an exponential time: stop
+ before the translation starts. */
+ if (single_succ_p (block)
+ && bitmap_count_bits (PA_IN (single_succ (block))->expressions) > 10)
+ goto maybe_dump_sets;
+
old_PA_IN = PA_IN (block);
PA_OUT = bitmap_set_new ();
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
