[apologies if this is a dupe; I accidentally hit the send keystroke
before adding the last paragraph, and I'm not sure I was quick enough
to cancel it]
The first patch for PR debug/59992 cut down vt_initialize time in
insn-recog to less than 1/3, by avoiding quadratic behavior in
remove_useless_values, but the affected calls were always followed by
cselib_reset_table, which would also iterate over the entire table
looking for non-constant non-permanent values to remove. That was not
just redundant, but quadratic as well.
What's worse is that, unlike remove_useless_values, this is a cleanup
that we really have to do at the end of extended basic blocks, but for
large functions, most of the entries in the table are going to be
preserved values that we're going to visit over and over, but never
remove.
Instead of creating a list of recently-created values to revisit, I
figured it would be smarter to move the preserved values to a separate
table, that won't have to be cleaned up till we're through with the
function. Lookups first search the permanent table (if it's enabled,
i.e., only in var-tracking), always without insertion (we only insert in
the original table), and that's all it took to make it work, again
without any change to the asm output for i686 insn-recog.
The patch turned out to be quite easy and safe, and it cut down
vt_initialize time in i686 insn-recog from 500 seconds to only 5
seconds.
Regstrapped on x86_64-linux-gnu and i686-linux-gnu, along with the other
patch for PR debug/59992. Ok to install?
for gcc/ChangeLog
PR debug/59992
* cselib.c (cselib_hasher::equal): Special-case VALUE lookup.
(cselib_preserved_hash_table): New.
(preserve_constants_and_equivs): Move preserved vals to it.
(cselib_find_slot): Look it up first.
(cselib_init): Initialize it.
(cselib_finish): Release it.
(dump_cselib_table): Dump it.
---
gcc/cselib.c | 34 ++++++++++++++++++++++++++++++----
1 file changed, 30 insertions(+), 4 deletions(-)
diff --git a/gcc/cselib.c b/gcc/cselib.c
index dabd2d3..0fcfe28 100644
--- a/gcc/cselib.c
+++ b/gcc/cselib.c
@@ -132,6 +132,9 @@ cselib_hasher::equal (const value_type *v, const
compare_type *x_arg)
|| GET_CODE (XEXP (x, 0)) == CONST_FIXED))
x = XEXP (x, 0);
+ if (GET_CODE (x) == VALUE)
+ return x == v->val_rtx;
+
/* We don't guarantee that distinct rtx's have different hash values,
so we need to do a comparison. */
for (l = v->locs; l; l = l->next)
@@ -147,6 +150,9 @@ cselib_hasher::equal (const value_type *v, const
compare_type *x_arg)
/* A table that enables us to look up elts by their value. */
static hash_table <cselib_hasher> cselib_hash_table;
+/* A table to hold preserved values. */
+static hash_table <cselib_hasher> cselib_preserved_hash_table;
+
/* This is a global so we don't have to pass this through every function.
It is used in new_elt_loc_list to set SETTING_INSN. */
static rtx cselib_current_insn;
@@ -490,8 +496,17 @@ preserve_constants_and_equivs (cselib_val **x, void *info
ATTRIBUTE_UNUSED)
{
cselib_val *v = *x;
- if (!invariant_or_equiv_p (v))
- cselib_hash_table.clear_slot (x);
+ if (invariant_or_equiv_p (v))
+ {
+ cselib_val **slot
+ = cselib_preserved_hash_table.find_slot_with_hash (v->val_rtx,
+ v->hash, INSERT);
+ gcc_assert (!*slot);
+ *slot = v;
+ }
+
+ cselib_hash_table.clear_slot (x);
+
return 1;
}
@@ -565,9 +580,13 @@ static cselib_val **
cselib_find_slot (rtx x, hashval_t hash, enum insert_option insert,
enum machine_mode memmode)
{
- cselib_val **slot;
+ cselib_val **slot = NULL;
find_slot_memmode = memmode;
- slot = cselib_hash_table.find_slot_with_hash (x, hash, insert);
+ if (cselib_preserve_constants)
+ slot = cselib_preserved_hash_table.find_slot_with_hash (x, hash,
+ NO_INSERT);
+ if (!slot)
+ slot = cselib_hash_table.find_slot_with_hash (x, hash, insert);
find_slot_memmode = VOIDmode;
return slot;
}
@@ -2742,6 +2761,8 @@ cselib_init (int record_what)
used_regs = XNEWVEC (unsigned int, cselib_nregs);
n_used_regs = 0;
cselib_hash_table.create (31);
+ if (cselib_preserve_constants)
+ cselib_preserved_hash_table.create (31);
next_uid = 1;
}
@@ -2750,6 +2771,7 @@ cselib_init (int record_what)
void
cselib_finish (void)
{
+ bool preserved = cselib_preserve_constants;
cselib_discard_hook = NULL;
cselib_preserve_constants = false;
cselib_any_perm_equivs = false;
@@ -2761,6 +2783,8 @@ cselib_finish (void)
free_alloc_pool (value_pool);
cselib_clear_table ();
cselib_hash_table.dispose ();
+ if (preserved)
+ cselib_preserved_hash_table.dispose ();
free (used_regs);
used_regs = 0;
n_useless_values = 0;
@@ -2850,6 +2874,8 @@ dump_cselib_table (FILE *out)
{
fprintf (out, "cselib hash table:\n");
cselib_hash_table.traverse <FILE *, dump_cselib_val> (out);
+ fprintf (out, "cselib preserved hash table:\n");
+ cselib_preserved_hash_table.traverse <FILE *, dump_cselib_val> (out);
if (first_containing_mem != &dummy_val)
{
fputs ("first mem ", out);
--
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
