diff mbox

[PR,debug/59992,#2/2] preserve permanent values in a separate table

Message ID oreh2pxf1y.fsf@livre.home
State New
Headers show

Commit Message

Alexandre Oliva Feb. 27, 2014, 6:09 a.m. UTC 
[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(-)

Comments

Richard Henderson Feb. 27, 2014, 8:04 p.m. UTC | #1 
On 02/26/2014 10:09 PM, Alexandre Oliva wrote:
> 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.

Ok.


r~
diff mbox

Patch

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