[PR,debug/59992,#1/2] avoid quadratic behavior for the removal of useless values

We indirectly call remove_useless_values quite often during
vt_initialize; at least once per extended basic block.  On functions
with thousands of small basic blocks, each adding permanent and
temporary entries to the table, that turns out to be quite expensive:
the permanent entries pile up and trigger the quadratic behavior
mentioned in teh guard of one of the two calls of remove_useless_values.
This patch moves the guard so that it applies to the other as well.

I wasn't entirely sure this wouldn't invalidate assumptions made in
callers of cselib_preserve_only_values (the function called at the end
of each extended basic block), but some analysis, plus comparing before
and after assembly output ;-), made sure it didn't ;-)

This patch alone cut down the vt_initialize time of insn-recog on
generic i686 from more than 1700 seconds (~84% of the total compile
time) to about 500 seconds.

Regstrapped on x86_64-linux-gnu and i686-linux-gnu, along with the other
patch for PR debug/59992 that I'm about to post.


for  gcc/ChangeLog

	PR debug/59992
	* cselib.c (remove_useless_values): Skip to avoid quadratic
	behavior if the condition moved from...
	(cselib_process_insn): ... here holds.
---
 gcc/cselib.c |   16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

On Thu, Feb 27, 2014 at 6:54 AM, Alexandre Oliva <aoliva@redhat.com> wrote:
> We indirectly call remove_useless_values quite often during
> vt_initialize; at least once per extended basic block.  On functions
> with thousands of small basic blocks, each adding permanent and
> temporary entries to the table, that turns out to be quite expensive:
> the permanent entries pile up and trigger the quadratic behavior
> mentioned in teh guard of one of the two calls of remove_useless_values.
> This patch moves the guard so that it applies to the other as well.
>
> I wasn't entirely sure this wouldn't invalidate assumptions made in
> callers of cselib_preserve_only_values (the function called at the end
> of each extended basic block), but some analysis, plus comparing before
> and after assembly output ;-), made sure it didn't ;-)
>
> This patch alone cut down the vt_initialize time of insn-recog on
> generic i686 from more than 1700 seconds (~84% of the total compile
> time) to about 500 seconds.
>
> Regstrapped on x86_64-linux-gnu and i686-linux-gnu, along with the other
> patch for PR debug/59992 that I'm about to post.

Ok.

Thanks,
Richard.

>
> for  gcc/ChangeLog
>
>         PR debug/59992
>         * cselib.c (remove_useless_values): Skip to avoid quadratic
>         behavior if the condition moved from...
>         (cselib_process_insn): ... here holds.
> ---
>  gcc/cselib.c |   16 +++++++++-------
>  1 file changed, 9 insertions(+), 7 deletions(-)
>
> diff --git a/gcc/cselib.c b/gcc/cselib.c
> index 525e717..dabd2d3 100644
> --- a/gcc/cselib.c
> +++ b/gcc/cselib.c
> @@ -662,6 +662,14 @@ remove_useless_values (void)
>  {
>    cselib_val **p, *v;
>
> +  if (n_useless_values <= MAX_USELESS_VALUES
> +      /* remove_useless_values is linear in the hash table size.  Avoid
> +         quadratic behavior for very large hashtables with very few
> +        useless elements.  */
> +      || ((unsigned int)n_useless_values
> +         <= (cselib_hash_table.elements () - n_debug_values) / 4))
> +    return;
> +
>    /* First pass: eliminate locations that reference the value.  That in
>       turn can make more values useless.  */
>    do
> @@ -2693,13 +2701,7 @@ cselib_process_insn (rtx insn)
>
>    cselib_current_insn = NULL_RTX;
>
> -  if (n_useless_values > MAX_USELESS_VALUES
> -      /* remove_useless_values is linear in the hash table size.  Avoid
> -         quadratic behavior for very large hashtables with very few
> -        useless elements.  */
> -      && ((unsigned int)n_useless_values
> -         > (cselib_hash_table.elements () - n_debug_values) / 4))
> -    remove_useless_values ();
> +  remove_useless_values ();
>  }
>
>  /* Initialize cselib for one pass.  The caller must also call
>
> --
> Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
> You must be the change you wish to see in the world. -- Gandhi
> Be Free! -- http://FSFLA.org/   FSF Latin America board member
> Free Software Evangelist     Red Hat Brazil Toolchain Engineer