Improve hash_table

[Richard Biener <rguenther at suse dot de>]

I am facing several issues with the current hash_table API while
trying to improve what is currently the scev_info_hash_table_type
in tree-scalar-evolution.c.  The issues with that hashtable are

 1) it allocates GC memory for the entries but their lifetime
    is short (call of instantiate_scev / resolve_mixers)
 2) it performs too many allocation calls

the hashtable is used to both guard against recursion and to
cache already computed results for visited SSA names.

Ideally we'd have a SSA name -> computed result map here,
but a hash_table <tree> and storing just the result there
doesn't work as we cannot recover 'name' from it.  Simply
moving the entries from GC memory to heap to address 1)
worsens 2) as heap allocations have a larger overhead than
GC allocations.  Thus, in trying to address 2) we'd ideally
want to store the small { name, chrec } pair into the
hashtable itself - but that's unfortunately not possible.
So to make the number of allocations log (N) (as it's
for the hashtable itself) I'm using a vec<{name, chrec}>
as storage and store indexes into that vector in the
hash-table (thus, hashing SSA name -> vector index)
(see patch below).  That turns up the issue that
hash_table <uintptr_t> still will have uintptr_t *
as elements and thus either require external storage
for the indexes or reinterpret_cast<>s all over the place
(as in the patch).  Also both the hash and compare
functions are static and have no way to get at the
'storage' vector - thus I need a global variable to
communicate that to them ...

Now, to me the solution seems to be to enhance hash_table
itself to allow embedding the storage - thus not indirect
value_type in hash_table_control but do

template <typename T>
struct hash_table_control
{
  /* Table itself.  */
  T *entries;

instead.  Which requires the controlling traits to provide
an abstraction for HTAB_DELETED_ENTRY and a HTAB_ENTRY_ENTRY.
Simple values in an enum won't do, thus something like

  bool empty_value_p (value_type &);
  void construct_empty_value (value_type &);
  bool deleted_value_p (value_type &);
  void construct_deleted_value (value_type &);

would be required.  That complicates the traits somewhat
so I wonder if we can use some tricks to allow an optional

  typedef <...> slot_type;

that, when available triggers the requirement of the above
abstractions and otherwise uses a default provider with
just

  typedef value_type *slot_type;

If I were to implement this I'd probably try to use SFINAE
here and wrap uses of the traits type in hash_table like

template <typename Descriptor,
          template <typename Type> class Allocator = xcallocator>
class hash_table
{
...
  hash_table_control <slot_traits <Descriptor>::slot_type> *htab;

and have

template <typename Descritor>
struct has_slot_type
{
  char test (typename Descritpor::slot_type *);
  int test (...);
  enum { value = sizeof(test<Descritor>(0) == sizeof (char) };
};

template <typename Descriptor, bool sl>
struct slot_traits_impl;

template <typename Descriptor>
struct slot_traits_impl <false>
{
  typedef typename Descriptor::value_type *slot_type;
...
};

template <typename Descriptor>
struct slot_traits_impl <true>
{
  typedef typename Descriptor::slot_type slot_type;
...
};

template <typename Descriptor>
struct slot_traits : slot_traits_impl <has_slot_type <Descriptor>::value>
{
...

with appropriate deleted/empty entry implementations and forwarding.

Can you think of a simpler way?  Would you do it entirely different?

Thanks,
Richard.


Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c	(revision 198441)
+++ gcc/tree-scalar-evolution.c	(working copy)
@@ -319,9 +319,11 @@ new_scev_info_str (basic_block instantia
 /* Computes a hash function for database element ELT.  */
 
 static inline hashval_t
-hash_scev_info (const void *elt)
+hash_scev_info (const void *elt_)
 {
-  return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
+  const struct scev_info_str *elt = (const struct scev_info_str *) elt_;
+  return iterative_hash_hashval_t (SSA_NAME_VERSION (elt->var),
+				   elt->instantiated_below->index);
 }
 
 /* Compares database elements E1 and E2.  */
@@ -344,38 +346,6 @@ del_scev_info (void *e)
   ggc_free (e);
 }
 
-/* Hashtable helpers.  */
-
-struct scev_info_hasher
-{
-  typedef scev_info_str value_type;
-  typedef scev_info_str compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
-  static inline void remove (value_type *);
-};
-
-inline hashval_t
-scev_info_hasher::hash (const value_type *elt)
-{
-  return hash_scev_info (elt);
-}
-
-inline bool
-scev_info_hasher::equal (const value_type *elt1, const compare_type *elt2)
-{
-  return eq_scev_info (elt1, elt2);
-}
-
-/* Deletes database element E.  */
-
-inline void
-scev_info_hasher::remove (value_type *e)
-{
-  del_scev_info (e);
-}
-
-typedef hash_table <scev_info_hasher> scev_info_hash_table_type;
 
 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
    A first query on VAR returns chrec_not_analyzed_yet.  */
@@ -2078,43 +2048,87 @@ analyze_scalar_evolution_in_loop (struct
     }
 }
 
-/* Returns from CACHE the value for VERSION instantiated below
-   INSTANTIATED_BELOW block.  */
 
-static tree
-get_instantiated_value (scev_info_hash_table_type cache,
-			basic_block instantiated_below, tree version)
+/* Hashtable helpers for a temporary hash-table used when
+   instantiating a CHREC or resolving mixers.  For this use
+   instantiated_below is always the same.  */
+
+struct instantiate_cache_entry
 {
-  struct scev_info_str *info, pattern;
+  tree name;
+  tree chrec;
+};
 
-  pattern.var = version;
-  pattern.instantiated_below = instantiated_below;
-  info = cache.find (&pattern);
+struct instantiate_cache_entry_hasher : typed_noop_remove <uintptr_t>
+{
+  typedef uintptr_t value_type;
+  typedef instantiate_cache_entry compare_type;
+  static inline hashval_t hash (const value_type *);
+  static inline bool equal (const value_type *, const compare_type *);
+};
 
-  if (info)
-    return info->chrec;
-  else
-    return NULL_TREE;
+struct instantiate_cache_type
+{
+  hash_table <instantiate_cache_entry_hasher> htab;
+  vec<instantiate_cache_entry> entries;
+
+  ~instantiate_cache_type();
+};
+
+instantiate_cache_type::~instantiate_cache_type ()
+{
+  if (htab.is_created ())
+    {
+      htab.dispose ();
+      entries.release ();
+    }
 }
 
-/* Sets in CACHE the value of VERSION instantiated below basic block
-   INSTANTIATED_BELOW to VAL.  */
+static instantiate_cache_type *ctbl;
 
-static void
-set_instantiated_value (scev_info_hash_table_type cache,
-			basic_block instantiated_below, tree version, tree val)
+inline hashval_t
+instantiate_cache_entry_hasher::hash (const value_type *idx)
 {
-  struct scev_info_str *info, pattern;
-  scev_info_str **slot;
+  instantiate_cache_entry *elt
+    = &ctbl->entries[reinterpret_cast <uintptr_t> (idx) - 2];
+  return SSA_NAME_VERSION (elt->name);
+}
 
-  pattern.var = version;
-  pattern.instantiated_below = instantiated_below;
-  slot = cache.find_slot (&pattern, INSERT);
+inline bool
+instantiate_cache_entry_hasher::equal (const value_type *idx1,
+				       const compare_type *elt2)
+{
+  compare_type *elt1 = &ctbl->entries[reinterpret_cast <uintptr_t> (idx1) - 2];
+  return elt1->name == elt2->name;
+}
 
+/* Returns from CACHE a pointer to the cached chrec for NAME.  */
+
+static tree *
+get_instantiated_value_entry (instantiate_cache_type &cache, tree name)
+{
+  struct instantiate_cache_entry e;
+  uintptr_t **slot;
+
+  if (!cache.htab.is_created ())
+    {
+      cache.htab.create (10);
+      cache.entries.create (10);
+    }
+
+  ctbl = &cache;
+
+  e.name = name;
+  slot = cache.htab.find_slot_with_hash (&e, SSA_NAME_VERSION (name), INSERT);
   if (!*slot)
-    *slot = new_scev_info_str (instantiated_below, version);
-  info = *slot;
-  info->chrec = val;
+    {
+      e.chrec = chrec_not_analyzed_yet;
+      cache.entries.safe_push (e);
+      *slot = reinterpret_cast <uintptr_t *>
+	  ((uintptr_t) cache.entries.length () + 1);
+    }
+
+  return &cache.entries[reinterpret_cast <uintptr_t> (*slot) - 2].chrec;
 }
 
 /* Return the closed_loop_phi node for VAR.  If there is none, return
@@ -2148,7 +2162,7 @@ loop_closed_phi_def (tree var)
 }
 
 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
-				tree, bool, scev_info_hash_table_type, int);
+				tree, bool, instantiate_cache_type &, int);
 
 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    and EVOLUTION_LOOP, that were left under a symbolic form.
@@ -2168,7 +2182,7 @@ static tree
 instantiate_scev_name (basic_block instantiate_below,
 		       struct loop *evolution_loop, struct loop *inner_loop,
 		       tree chrec,
-		       bool fold_conversions, scev_info_hash_table_type cache,
+		       bool fold_conversions, instantiate_cache_type &cache,
 		       int size_expr)
 {
   tree res;
@@ -2191,12 +2205,13 @@ instantiate_scev_name (basic_block insta
 
      | a_2 -> {0, +, 1, +, a_2}_1  */
 
-  res = get_instantiated_value (cache, instantiate_below, chrec);
-  if (res)
-    return res;
+  tree *si;
+  si = get_instantiated_value_entry (cache, chrec);
+  if (*si != chrec_not_analyzed_yet)
+    return *si;
 
-  res = chrec_dont_know;
-  set_instantiated_value (cache, instantiate_below, chrec, res);
+  /* On recursion return chrec_dont_know.  */
+  *si = chrec_dont_know;
 
   def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
 
@@ -2249,7 +2264,7 @@ instantiate_scev_name (basic_block insta
     }
 
   /* Store the correct value to the cache.  */
-  set_instantiated_value (cache, instantiate_below, chrec, res);
+  *si = res;
   return res;
 }
 
@@ -2271,7 +2286,7 @@ static tree
 instantiate_scev_poly (basic_block instantiate_below,
 		       struct loop *evolution_loop, struct loop *,
 		       tree chrec,
-		       bool fold_conversions, scev_info_hash_table_type cache,
+		       bool fold_conversions, instantiate_cache_type &cache,
 		       int size_expr)
 {
   tree op1;
@@ -2318,7 +2333,8 @@ instantiate_scev_binary (basic_block ins
 			 struct loop *evolution_loop, struct loop *inner_loop,
 			 tree chrec, enum tree_code code,
 			 tree type, tree c0, tree c1,
-			 bool fold_conversions, scev_info_hash_table_type cache,
+			 bool fold_conversions,
+			 instantiate_cache_type &cache,
 			 int size_expr)
 {
   tree op1;
@@ -2378,7 +2394,7 @@ static tree
 instantiate_array_ref (basic_block instantiate_below,
 		       struct loop *evolution_loop, struct loop *inner_loop,
 		       tree chrec,
-		       bool fold_conversions, scev_info_hash_table_type cache,
+		       bool fold_conversions, instantiate_cache_type &cache,
 		       int size_expr)
 {
   tree res;
@@ -2419,7 +2435,7 @@ instantiate_scev_convert (basic_block in
 			  tree chrec,
 			  tree type, tree op,
 			  bool fold_conversions,
-			  scev_info_hash_table_type cache, int size_expr)
+			  instantiate_cache_type &cache, int size_expr)
 {
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
 				 inner_loop, op,
@@ -2468,7 +2484,7 @@ instantiate_scev_not (basic_block instan
 		      struct loop *evolution_loop, struct loop *inner_loop,
 		      tree chrec,
 		      enum tree_code code, tree type, tree op,
-		      bool fold_conversions, scev_info_hash_table_type cache,
+		      bool fold_conversions, instantiate_cache_type &cache,
 		      int size_expr)
 {
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
@@ -2518,7 +2534,7 @@ static tree
 instantiate_scev_3 (basic_block instantiate_below,
 		    struct loop *evolution_loop, struct loop *inner_loop,
 		    tree chrec,
-		    bool fold_conversions, scev_info_hash_table_type cache,
+		    bool fold_conversions, instantiate_cache_type &cache,
 		    int size_expr)
 {
   tree op1, op2;
@@ -2567,7 +2583,7 @@ static tree
 instantiate_scev_2 (basic_block instantiate_below,
 		    struct loop *evolution_loop, struct loop *inner_loop,
 		    tree chrec,
-		    bool fold_conversions, scev_info_hash_table_type cache,
+		    bool fold_conversions, instantiate_cache_type &cache,
 		    int size_expr)
 {
   tree op1;
@@ -2608,7 +2624,7 @@ static tree
 instantiate_scev_1 (basic_block instantiate_below,
 		    struct loop *evolution_loop, struct loop *inner_loop,
 		    tree chrec,
-		    bool fold_conversions, scev_info_hash_table_type cache,
+		    bool fold_conversions, instantiate_cache_type &cache,
 		    int size_expr)
 {
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
@@ -2642,7 +2658,7 @@ static tree
 instantiate_scev_r (basic_block instantiate_below,
 		    struct loop *evolution_loop, struct loop *inner_loop,
 		    tree chrec,
-		    bool fold_conversions, scev_info_hash_table_type cache,
+		    bool fold_conversions, instantiate_cache_type &cache,
 		    int size_expr)
 {
   /* Give up if the expression is larger than the MAX that we allow.  */
@@ -2749,8 +2765,7 @@ instantiate_scev (basic_block instantiat
 		  tree chrec)
 {
   tree res;
-  scev_info_hash_table_type cache;
-  cache.create (10);
+  instantiate_cache_type cache;
 
   if (dump_file && (dump_flags & TDF_SCEV))
     {
@@ -2772,8 +2787,6 @@ instantiate_scev (basic_block instantiat
       fprintf (dump_file, "))\n");
     }
 
-  cache.dispose ();
-
   return res;
 }
 
@@ -2785,11 +2798,9 @@ instantiate_scev (basic_block instantiat
 tree
 resolve_mixers (struct loop *loop, tree chrec)
 {
-  scev_info_hash_table_type cache;
-  cache.create (10);
+  instantiate_cache_type cache;
   tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
 				 chrec, true, cache, 0);
-  cache.dispose ();
   return ret;
 }