2007-11-05 Nick Clifton <nickc@redhat.com>

	    Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/32540
	PR tree-optimization/33922
	* doc/invoke.texi: Document PARAM_MAX_PARTIAL_ANTIC_LENGTH.
	* tree-ssa-pre.c: Include params.h.
	(compute_partial_antic_aux): Use PARAM_MAX_PARTIAL_ANTIC_LENGTH
	to limit the maximum length of the PA set for a given block.
	* Makefile.in: Add a dependency upon params.h for tree-ssa-pre.c
	* params.def (PARAM_MAX_PARTIAL_ANTIC_LENGTH): New parameter.

	* gcc.dg/tree-ssa/pr32540-1.c: New.
	* gcc.dg/tree-ssa/pr32540-2.c: New.
	* gcc.dg/tree-ssa/pr33922.c: New.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@129901 138bc75d-0d04-0410-961f-82ee72b054a4

9 files changed, 196 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e56299f9f67..0a5f2d89851 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@
+2007-11-05  Nick Clifton  <nickc@redhat.com>
+	    Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR tree-optimization/32540
+	PR tree-optimization/33922
+	* doc/invoke.texi: Document PARAM_MAX_PARTIAL_ANTIC_LENGTH.
+	* tree-ssa-pre.c: Include params.h.
+	(compute_partial_antic_aux): Use PARAM_MAX_PARTIAL_ANTIC_LENGTH
+	to limit the maximum length of the PA set for a given block.
+	* Makefile.in: Add a dependency upon params.h for tree-ssa-pre.c
+	* params.def (PARAM_MAX_PARTIAL_ANTIC_LENGTH): New parameter.
+
 2007-11-05  Nathan Sidwell  <nathan@codesourcery.com>
 
 	* libgcc2.c (__fixunstfDI, __fixunsxfDI, __fixunsdfDI,
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 9cfb6e7d495..85b75680966 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2068,7 +2068,7 @@ tree-ssa-pre.o : tree-ssa-pre.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
    $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) $(CFGLOOP_H) \
    alloc-pool.h $(BASIC_BLOCK_H) bitmap.h $(HASHTAB_H) $(TREE_GIMPLE_H) \
-   $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h
+   $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h $(PARAMS_H)
 tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
    $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) $(CFGLOOP_H) \
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 4de20b66872..5e24ed7d5ee 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -7112,6 +7112,16 @@ mechanism for comparing types in C++ and Objective-C++.  However, if
 bugs in the canonical type system are causing compilation failures,
 set this value to 0 to disable canonical types.
 
+@item max-partial-antic-length
+Maximum length of the partial antic set computed during the tree
+partial redundancy elimination optimization (@option{-ftree-pre}) when
+optimizing at @option{-O3} and above.  For some sorts of source code
+the enhanced partial redundancy elimination optimization can run away,
+consuming all of the memory available on the host machine.  This
+parameter sets a limit on the length of the sets that are computed,
+which prevents the runaway behaviour.  Setting a value of 0 for
+this paramter will allow an unlimited set length.
+
 @end table
 @end table
 
diff --git a/gcc/params.def b/gcc/params.def
index 8973c9ac4e0..fc85c8804eb 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -707,6 +707,12 @@ DEFPARAM (PARAM_USE_CANONICAL_TYPES,
 	  "use-canonical-types",
 	  "Whether to use canonical types",
 	  1, 0, 1)
+
+DEFPARAM (PARAM_MAX_PARTIAL_ANTIC_LENGTH,
+	  "max-partial-antic-length",
+	  "Maximum length of partial antic set when performing tree pre optimization",
+	  100, 0, 0)
+
 /*
 Local variables:
 mode:c
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 12dd3509259..6f505ed7a9a 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,12 @@
+2007-11-05  Nick Clifton  <nickc@redhat.com>
+	    Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR tree-optimization/32540
+	PR tree-optimization/33922
+	* gcc.dg/tree-ssa/pr32540-1.c: New.
+	* gcc.dg/tree-ssa/pr32540-2.c: New.
+	* gcc.dg/tree-ssa/pr33922.c: New.
+
 2007-11-05  Douglas Gregor  <doug.gregor@gmail.com>
 
 	PR c++/33939
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr32540-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr32540-1.c
new file mode 100644
index 00000000000..ce8e0ae824f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr32540-1.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -ftree-pre" } */
+
+int f(void);
+void acceptloop_th(int *t) {
+   int options = 0;
+   if (f()) options |= 0x1 << 1;
+   if (f()) options |= 0x1 << 2;
+   if (f()) options |= 0x1 << 3;
+   if (f()) options |= 0x1 << 4;
+   if (f()) options |= 0x1 << 5;
+   if (f()) options |= 0x1 << 6;
+   if (f()) options |= 0x1 << 7;
+   if (f()) options |= 0x1 << 8;
+   if (f()) options |= 0x1 << 9;
+   if (f()) options |= 0x1 << 10;
+   if (f()) options |= 0x1 << 11;
+   if (f()) options |= 0x1 << 12;
+   if (f()) options |= 0x1 << 13;
+   if (f()) options |= 0x1 << 14;
+   if (f()) options |= 0x1 << 15;
+   if (f()) options |= 0x1 << 16;
+   if (f()) options |= 0x1 << 17;
+   if (f()) options |= 0x1 << 18;
+   if (f()) options |= 0x1 << 19;
+   if (f()) options |= 0x1 << 20;
+   if (f()) options |= 0x1 << 21;
+   if (f()) options |= 0x1 << 22;
+   if (f()) options |= 0x1 << 23;
+   if (f()) options |= 0x1 << 24;
+   if (f()) options |= 0x1 << 25;
+   if (f()) options |= 0x1 << 26;
+   if (f()) *t = options;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr32540-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr32540-2.c
new file mode 100644
index 00000000000..29a5e3c55d0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr32540-2.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -ftree-pre" } */
+
+int f(void);
+void acceptloop_th(int *t, int options) {
+    if (f()) options |= 0x1 << 0;
+    if (f()) options |= 0x1 << 1;
+    if (f()) options |= 0x1 << 2;
+    if (f()) options |= 0x1 << 3;
+    if (f()) options |= 0x1 << 4;
+    if (f()) options |= 0x1 << 5;
+    if (f()) options |= 0x1 << 6;
+    if (f()) options |= 0x1 << 7;
+    if (f()) options |= 0x1 << 8;
+    if (f()) options |= 0x1 << 9;
+    if (f()) options |= 0x1 << 10;
+    if (f()) options |= 0x1 << 11;
+    if (f()) options |= 0x1 << 12;
+    if (f()) options |= 0x1 << 13;
+    if (f()) options |= 0x1 << 14;
+    if (f()) options |= 0x1 << 15;
+    if (f()) options |= 0x1 << 16;
+    if (f()) options |= 0x1 << 17;
+    if (f()) options |= 0x1 << 18;
+    if (f()) options |= 0x1 << 19;
+    if (f()) options |= 0x1 << 20;
+    if (f()) options |= 0x1 << 21;
+    if (f()) options |= 0x1 << 22;
+    if (f()) options |= 0x1 << 23;
+    if (f()) options |= 0x1 << 24;
+    if (f()) options |= 0x1 << 25;
+    if (f()) options |= 0x1 << 26;
+    if (f()) *t = options;
+}
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr33922.c b/gcc/testsuite/gcc.dg/tree-ssa/pr33922.c
new file mode 100644
index 00000000000..7429eb161e6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr33922.c
@@ -0,0 +1,79 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -ftree-pre" } */
+
+typedef enum
+{
+  ST_TiemanStyle,
+}
+BrailleDisplay;
+static int pendingCommand;
+static int currentModifiers;
+typedef struct
+{
+  int (*updateKeys) (BrailleDisplay * brl, int *keyPressed);
+}
+ProtocolOperations;
+static const ProtocolOperations *protocol;
+brl_readCommand (BrailleDisplay * brl)
+{
+  unsigned long int keys;
+  int command;
+  int keyPressed;
+  unsigned char routingKeys[200];
+  int routingKeyCount;
+  signed char rightVerticalSensor;
+  if (pendingCommand != (-1))
+    {
+      return command;
+    }
+  if (!protocol->updateKeys (brl, &keyPressed))
+    {
+      if (rightVerticalSensor >= 0)
+        keys |= 1;
+      if ((routingKeyCount == 0) && keys)
+        {
+          if (currentModifiers)
+            {
+            doChord:switch (keys);
+            }
+          else
+            {
+            doCharacter:
+              command = 0X2200;
+              if (keys & 0X01UL)
+                command |= 0001;
+              if (keys & 0X02UL)
+                command |= 0002;
+              if (keys & 0X04UL)
+                command |= 0004;
+              if (keys & 0X08UL)
+                command |= 0010;
+              if (keys & 0X10UL)
+                command |= 0020;
+              if (keys & 0X20UL)
+                command |= 0040;
+              if (currentModifiers & (0X0010 | 0X0200))
+                command |= 0100;
+              if (currentModifiers & 0X0040)
+                command |= 0200;
+              if (currentModifiers & 0X0100)
+                command |= 0X020000;
+              if (currentModifiers & 0X0400)
+                command |= 0X080000;
+              if (currentModifiers & 0X0800)
+                command |= 0X040000;
+            }
+          unsigned char key1 = routingKeys[0];
+          if (key1 == 0)
+            {
+            }
+          if (key1 == 1)
+            if (keys)
+              {
+                currentModifiers |= 0X0010;
+                goto doCharacter;
+              }
+        }
+    }
+  return command;
+}
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 620346789a5..59396fd09ce 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "langhooks.h"
 #include "cfgloop.h"
 #include "tree-ssa-sccvn.h"
+#include "params.h"
 
 /* TODO:
 
@@ -1839,6 +1840,7 @@ compute_partial_antic_aux (basic_block block,
   bitmap_set_t PA_OUT;
   edge e;
   edge_iterator ei;
+  unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
 
   old_PA_IN = PA_OUT = NULL;
 
@@ -1847,6 +1849,14 @@ compute_partial_antic_aux (basic_block block,
   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 (max_pa
+      && single_succ_p (block)
+      && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa)
+    goto maybe_dump_sets;
+
   old_PA_IN = PA_IN (block);
   PA_OUT = bitmap_set_new ();