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

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.


	Jakub

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

On Tue, Mar 15, 2011 at 07:12:13PM -0400, Kenneth Zadeck wrote:
> so how much time does this save?

From those 7 minutes back to 16 seconds (--enable-checking=yes,
it was 4 seconds in 4.3 with release checking), DSE{1,2} takes each 1%,
while previously it was together well over 99%.

> I agree that this is a useful simplification, but it seems unlikely
> to be that important in real code.

Maybe, but it doesn't cost us anything, the comparison is just done
at a slughtly different place.

> it seems like the 5000 store test would in general provide a better
> safety valve.

Sure, I can try to implement that tomorrow.

	Jakub

On Mar 15, 2011, at 4:05 PM, Jakub Jelinek wrote:
> --- 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

Long term, I'd welcome a systematic way to test all things like this, but without the expense.

On 03/16/2011 12:12 AM, Kenneth Zadeck wrote:
> 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.

I think having both is a good idea.

Paolo