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(-)
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
