Re: [var-tracking] small speed-ups

[Dimitrios Apostolou]

Hi jakub,

On Mon, 22 Aug 2011, Jakub Jelinek wrote:
On Mon, Aug 22, 2011 at 01:30:33PM +0300, Dimitrios Apostolou wrote:
@@ -1191,7 +1189,7 @@ dv_uid2hash (dvuid uid)
 static inline hashval_t
 dv_htab_hash (decl_or_value dv)
 {
-  return dv_uid2hash (dv_uid (dv));
+  return (hashval_t) (dv_uid (dv));
 }

Why?  dv_uid2hash is an inline that does exactly that.

@@ -1202,7 +1200,7 @@ variable_htab_hash (const void *x)
 {
   const_variable const v = (const_variable) x;

-  return dv_htab_hash (v->dv);
+  return (hashval_t) (dv_uid (v->dv));
 }

Why?

 /* Compare the declaration of variable X with declaration Y.  */
@@ -1211,9 +1209,8 @@ static int
 variable_htab_eq (const void *x, const void *y)
 {
   const_variable const v = (const_variable) x;
-  decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);

-  return (dv_as_opaque (v->dv) == dv_as_opaque (dv));
+  return (v->dv) == y;
 }

Why?

I was hoping you'd ask so I'll ask back :-) Why are we doing it that way? 
Why so much indirection in the first place? Why create inline functions 
just to typecast and why do we need this CONST_CAST2 ugliness in C code. I 
bet there are things I don't understand so I'd be happy to listen...

The reason I did this (and many more I didn't publish) simplifications 
within var-tracking is because it hurt my brains to follow the 
logic. Even with the help of TAGS I have a specific stack depth before I 
forget where I begun diving into TAG declarations. Well in var-tracking 
this limit was surpassed by much...


@@ -1397,19 +1398,40 @@ shared_var_p (variable var, shared_hash
          || shared_hash_shared (vars));
 }

+/* Copy all variables from hash table SRC to hash table DST without rehashing
+   any values.  */
+
+static htab_t
+htab_dup (htab_t src)
+{
+  htab_t dst;
+
+  dst = (htab_t) xmalloc (sizeof (*src));
+  memcpy (dst, src, sizeof (*src));
+  dst->entries = (void **) xmalloc (src->size * sizeof (*src->entries));
+  memcpy (dst->entries, src->entries,
+         src->size * sizeof (*src->entries));
+  return dst;
+}
+

This certainly doesn't belong here, it should go into libiberty/hashtab.c
and prototype into include/hashtab.h.  It relies on hashtab.c
implementation details.

OK I'll do that in the future. Should I also move some other htab 
functions I saw in var-tracking and rtl? FOR_EACH_HTAB_ELEMENT comes to 
mind, probably other too.


@@ -2034,7 +2041,8 @@ val_resolve (dataflow_set *set, rtx val,
 static void
 dataflow_set_init (dataflow_set *set)
 {
-  init_attrs_list_set (set->regs);
+  /* Initialize the set (array) SET of attrs to empty lists.  */
+  memset (set->regs, 0, sizeof (set->regs));
   set->vars = shared_hash_copy (empty_shared_hash);
   set->stack_adjust = 0;
   set->traversed_vars = NULL;

I'd say you should instead just implement init_attrs_list_set inline using
memset.

It's used only once, that's why I deleted the function. I'll bring it back 
if you think it helps.


   dst->vars = (shared_hash) pool_alloc (shared_hash_pool);
   dst->vars->refcount = 1;
   dst->vars->htab
-    = htab_create (MAX (src1_elems, src2_elems), variable_htab_hash,
+    = htab_create (2 * MAX (src1_elems, src2_elems), variable_htab_hash,
                   variable_htab_eq, variable_htab_free);

This looks wrong, 2 * max is definitely too much.

For a hash table to fit N elements, it has to have at least 4/3*N 
slots, or 2*N slots if htab has the 50% load factor I was proposing.

@@ -8996,11 +9006,13 @@ vt_finalize (void)

   FOR_ALL_BB (bb)
     {
-      dataflow_set_destroy (&VTI (bb)->in);
-      dataflow_set_destroy (&VTI (bb)->out);
+      /* The "false" do_free parameter means to not bother to iterate and free
+        all hash table elements, since we'll destroy the pools. */
+      dataflow_set_destroy (&VTI (bb)->in, false);
+      dataflow_set_destroy (&VTI (bb)->out, false);
       if (VTI (bb)->permp)
        {
-         dataflow_set_destroy (VTI (bb)->permp);
+         dataflow_set_destroy (VTI (bb)->permp, false);
          XDELETE (VTI (bb)->permp);
        }
     }


How much does this actually speed things up (the not freeing pool allocated
stuff during finalizaqtion)?  Is it really worth it?

In total for dataflow_set_destroy I can see that calls to 
attrs_list_clear() have been reduced from 500K to 250K, and I can also see 
a reduction of free() calls from htab_delete(), from 30K to 10K. I'm 
willing to bet that much of this is because of this change, I have kept 
only the ones that showed difference and remember clearly that 
var-tracking is iterating over hash tables too much, either directly or 
from htab_traverse()/htab_delete().


Thanks,
Dimitris