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

[Kenneth Zadeck]

so how much time does this save?

I agree that this is a useful simplification, but it seems unlikely to 
be that important in real code.
it seems like the 5000 store test would in general provide a better 
safety valve.

Kenny

On 03/15/2011 07:05 PM, Jakub Jelinek wrote:
> 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