re PR tree-optimization/43415 (Consumes large amounts of memory and time in PRE at -O3)

2010-03-19  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/43415
	* tree-ssa-pre.c (phi_translate): Split out worker to ...
	(phi_translate_1): ... this.
	(phi_translate): Move all caching here.  Cache all NARY
	and REFERENCE translations.

	* gcc.c-torture/compile/pr43415.c: New testcase.

From-SVN: r157562

4 files changed, 92 insertions, 25 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b59a4da..ce98eb4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2010-03-19  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/43415
+	* tree-ssa-pre.c (phi_translate): Split out worker to ...
+	(phi_translate_1): ... this.
+	(phi_translate): Move all caching here.  Cache all NARY
+	and REFERENCE translations.
+
 2010-03-19  David S. Miller  <davem@davemloft.net>
 
 	With help from Eric Botcazou.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 7d5b8d0..09f644d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2010-03-19  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/43415
+	* gcc.c-torture/compile/pr43415.c: New testcase.
+
 2010-03-19  Eric Botcazou  <ebotcazou@adacore.com>
 
 	PR ada/43106
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr43415.c b/gcc/testsuite/gcc.c-torture/compile/pr43415.c
new file mode 100644
index 0000000..c00e1c4
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr43415.c
@@ -0,0 +1,36 @@
+int main()                                                                      
+{                                                                               
+  unsigned long long table[256];                                          
+  unsigned int i;
+  for (i=0; i<256; ++i) {
+      unsigned long long j;
+      unsigned char x=i;
+      for (j=0; j<5; ++j) {
+	  x += x<<1;
+	  x ^= x>>1;
+      }
+      for (j=0; j<5; ++j) {
+	  x += x<<1;
+	  x ^= x>>1;
+      }
+      for (j=0; j<5; ++j) {
+	  x += x<<1;
+	  x ^= x>>1;
+      }
+      for (j=0; j<5; ++j) {
+	  x += x<<1;
+	  x ^= x>>1;
+      }
+      for (j=0; j<5; ++j) {
+	  x += x<<1;
+	  x ^= x>>1;
+      }
+      table[i] ^= (((unsigned long long)x)<<16);
+  }
+  for (i=0; i<256; ++i) {
+      if ((table[i]&0xff)==i)
+	return 1;
+  }
+  return 0;
+}
+
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 684484f..ecade3d 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -1471,32 +1471,18 @@ get_representative_for (const pre_expr e)
 
 
 
+static pre_expr
+phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+	       basic_block pred, basic_block phiblock);
 
 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
    the phis in PRED.  Return NULL if we can't find a leader for each part
    of the translated expression.  */
 
 static pre_expr
-phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
-	       basic_block pred, basic_block phiblock)
+phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+		 basic_block pred, basic_block phiblock)
 {
-  pre_expr oldexpr = expr;
-  pre_expr phitrans;
-
-  if (!expr)
-    return NULL;
-
-  /* Constants contain no values that need translation.  */
-  if (expr->kind == CONSTANT)
-    return expr;
-
-  if (value_id_constant_p (get_expr_value_id (expr)))
-    return expr;
-
-  phitrans = phi_trans_lookup (expr, pred);
-  if (phitrans)
-    return phitrans;
-
   switch (expr->kind)
     {
     case NARY:
@@ -1584,7 +1570,6 @@ phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
 	      }
 	    add_to_value (new_val_id, expr);
 	  }
-	phi_trans_add (oldexpr, expr, pred);
 	return expr;
       }
       break;
@@ -1765,7 +1750,6 @@ phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
 	    add_to_value (new_val_id, expr);
 	  }
 	VEC_free (vn_reference_op_s, heap, newoperands);
-	phi_trans_add (oldexpr, expr, pred);
 	return expr;
       }
       break;
@@ -1811,6 +1795,44 @@ phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
     }
 }
 
+/* Wrapper around phi_translate_1 providing caching functionality.  */
+
+static pre_expr
+phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+	       basic_block pred, basic_block phiblock)
+{
+  pre_expr phitrans;
+
+  if (!expr)
+    return NULL;
+
+  /* Constants contain no values that need translation.  */
+  if (expr->kind == CONSTANT)
+    return expr;
+
+  if (value_id_constant_p (get_expr_value_id (expr)))
+    return expr;
+
+  if (expr->kind != NAME)
+    {
+      phitrans = phi_trans_lookup (expr, pred);
+      if (phitrans)
+	return phitrans;
+    }
+
+  /* Translate.  */
+  phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
+
+  /* Don't add empty translations to the cache.  Neither add
+     translations of NAMEs as those are cheap to translate.  */
+  if (phitrans
+      && expr->kind != NAME)
+    phi_trans_add (expr, phitrans, pred);
+
+  return phitrans;
+}
+
+
 /* For each expression in SET, translate the values through phi nodes
    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
    expressions in DEST.  */
@@ -1834,13 +1856,9 @@ phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
     {
       pre_expr translated;
       translated = phi_translate (expr, set, NULL, pred, phiblock);
-
-      /* Don't add empty translations to the cache  */
       if (!translated)
 	continue;
 
-      phi_trans_add (expr, translated, pred);
-
       /* We might end up with multiple expressions from SET being
 	 translated to the same value.  In this case we do not want
 	 to retain the NARY or REFERENCE expression but prefer a NAME