[PATCH] Fix RTL DSE compile time hog (PR rtl-optimization/48141)

[Jakub Jelinek]

Hi!

On the attached testcase we spend > 7 minutes in RTL DSE, as we end up
with active_local_stores chain with up to 100000 entries and we walk
it through on each store.

The following patch fixes it by throwing away from active_local_stores
list stores that don't have any positions needed, but can't be deleted
(I believe such stores aren't helpful at all in the list, we aren't going
to remove them anyway, and they can't be used by replace_read either).
Alternatively (or in addition to this) we might remember the length of the
active_local_stores list and just drop it on the floor when it becomes
too long (say over 5000 stores or something similar, perhaps a param).

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk (and
after a while for 4.6)?

2011-03-15  Jakub Jelinek  <jakub@redhat.com>

	PR rtl-optimization/48141
	* dse.c (record_store): If no positions are needed in an insn
	that cannot be deleted, at least unchain it from active_local_stores.

	* gcc.dg/pr48141.c: New test.

--- gcc/dse.c.jj	2011-02-15 15:42:26.000000000 +0100
+++ gcc/dse.c	2011-03-15 21:25:59.000000000 +0100
@@ -1530,8 +1530,7 @@ record_store (rtx body, bb_info_t bb_inf
 
       /* An insn can be deleted if every position of every one of
 	 its s_infos is zero.  */
-      if (any_positions_needed_p (s_info)
-	  || ptr->cannot_delete)
+      if (any_positions_needed_p (s_info))
 	del = false;
 
       if (del)
@@ -1543,7 +1542,8 @@ record_store (rtx body, bb_info_t bb_inf
 	  else
 	    active_local_stores = ptr->next_local_store;
 
-	  delete_dead_store_insn (insn_to_delete);
+	  if (!insn_to_delete->cannot_delete)
+	    delete_dead_store_insn (insn_to_delete);
 	}
       else
 	last = ptr;
--- gcc/testsuite/gcc.dg/pr48141.c.jj	2011-03-15 21:48:46.000000000 +0100
+++ gcc/testsuite/gcc.dg/pr48141.c	2011-03-15 21:48:27.000000000 +0100
@@ -0,0 +1,17 @@
+/* PR rtl-optimization/48141 */
+/* { dg-do compile } */
+/* { dg-options "-O" } */
+
+#define A i = 0;
+#define B A A A A A A A A A A
+#define C B B B B B B B B B B
+#define D C C C C C C C C C C
+#define E D D D D D D D D D D
+
+int
+foo (void)
+{
+  volatile int i = 0;
+  E E E E E E E E E E E
+  return 0;
+}

	Jakub