[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE

[sebpop at gmail dot com]

------- 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