On Thu, Feb 27, 2014 at 6:54 AM, Alexandre Oliva <aol...@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
