[PATCH][RFC] Make referenced_vars hash table more efficient

[Richard Guenther <rguenther at suse dot de>]

This makes us use the embedded DECL_UID of the stored trees instead of
requiring a separate uid, tree pair for the hashtable.  This should
save at least half of the memory for the referenced vars table (plus
the GC overhead of the pairs) and make the accessors faster by doing
less memory references.

Bootstrapped and tested on x86_64-unknown-linux-gnu.  As this should
improve performance/memory usage it should qualify for 4.3, but I'll
wait a day for comments that say otherwise.  [I'm currently re-writing
the referenced vars representation completely to allow stable walking
of referenced vars, but that's for stage1 definitely]

Thanks,
Richard.

2007-10-17  Richard Guenther  <rguenther@suse.de>

	* tree-flow.h (struct gimple_df): Make referenced_vars
	a uid_decl_map.
	(uid_decl_map_eq): Declare.
	(uid_decl_map_hash): Likewise.
	* tree-ssa.c (uid_decl_map_eq): New function.
	(uid_decl_map_hash): Likewise.
	(init_tree_ssa): Make referenced_vars a uid_decl_map.
	* tree-flow-inline.h (first_referenced_var): Deal with
	the referenced_vars representation change.
	(next_referenced_var): Likewise.
	* tree-dfa.c (referenced_var_lookup): Likewise.
	(referenced_var_check_and_insert): Likewise.
	(remove_referenced_var): Likewise.

Index: gcc/tree-flow-inline.h
===================================================================
*** gcc/tree-flow-inline.h	(revision 129403)
--- gcc/tree-flow-inline.h	(working copy)
*************** next_htab_element (htab_iterator *hti)
*** 151,163 ****
  static inline tree
  first_referenced_var (referenced_var_iterator *iter)
  {
!   struct int_tree_map *itm;
!   itm = (struct int_tree_map *) first_htab_element (&iter->hti,
!                                                     gimple_referenced_vars
! 						    (cfun));
!   if (!itm) 
!     return NULL;
!   return itm->to;
  }
  
  /* Return true if we have hit the end of the referenced variables ITER is
--- 151,158 ----
  static inline tree
  first_referenced_var (referenced_var_iterator *iter)
  {
!   return (tree) first_htab_element (&iter->hti,
! 				    gimple_referenced_vars (cfun));
  }
  
  /* Return true if we have hit the end of the referenced variables ITER is
*************** end_referenced_vars_p (const referenced_
*** 175,185 ****
  static inline tree
  next_referenced_var (referenced_var_iterator *iter)
  {
!   struct int_tree_map *itm;
!   itm = (struct int_tree_map *) next_htab_element (&iter->hti);
!   if (!itm) 
!     return NULL;
!   return itm->to;
  } 
  
  /* Fill up VEC with the variables in the referenced vars hashtable.  */
--- 170,176 ----
  static inline tree
  next_referenced_var (referenced_var_iterator *iter)
  {
!   return (tree) next_htab_element (&iter->hti);
  } 
  
  /* Fill up VEC with the variables in the referenced vars hashtable.  */
Index: gcc/tree-dfa.c
===================================================================
*** gcc/tree-dfa.c	(revision 129403)
--- gcc/tree-dfa.c	(working copy)
*************** find_vars_r (tree *tp, int *walk_subtree
*** 635,648 ****
  tree 
  referenced_var_lookup (unsigned int uid)
  {
!   struct int_tree_map *h, in;
    in.uid = uid;
!   h = (struct int_tree_map *)
! 	htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
    gcc_assert (h || uid == 0);
!   if (h)
!     return h->to;
!   return NULL_TREE;
  }
  
  /* Check if TO is in the referenced_vars hash table and insert it if not.  
--- 635,646 ----
  tree 
  referenced_var_lookup (unsigned int uid)
  {
!   tree h;
!   struct tree_decl_minimal in;
    in.uid = uid;
!   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
    gcc_assert (h || uid == 0);
!   return h;
  }
  
  /* Check if TO is in the referenced_vars hash table and insert it if not.  
*************** referenced_var_lookup (unsigned int uid)
*** 651,679 ****
  bool
  referenced_var_check_and_insert (tree to)
  { 
!   struct int_tree_map *h, in;
!   void **loc;
    unsigned int uid = DECL_UID (to);
  
    in.uid = uid;
!   in.to = to;
!   h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
! 						   &in, uid);
! 
    if (h)
      {
        /* DECL_UID has already been entered in the table.  Verify that it is
  	 the same entry as TO.  See PR 27793.  */
!       gcc_assert (h->to == to);
        return false;
      }
  
!   h = GGC_NEW (struct int_tree_map);
!   h->uid = uid;
!   h->to = to;
!   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun),
! 				  h, uid, INSERT);
!   *(struct int_tree_map **)  loc = h;
    return true;
  }
  
--- 649,671 ----
  bool
  referenced_var_check_and_insert (tree to)
  { 
!   tree h, *loc;
!   struct tree_decl_minimal in;
    unsigned int uid = DECL_UID (to);
  
    in.uid = uid;
!   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
    if (h)
      {
        /* DECL_UID has already been entered in the table.  Verify that it is
  	 the same entry as TO.  See PR 27793.  */
!       gcc_assert (h == to);
        return false;
      }
  
!   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
! 					   &in, uid, INSERT);
!   *loc = to;
    return true;
  }
  
*************** void
*** 774,780 ****
  remove_referenced_var (tree var)
  {
    var_ann_t v_ann;
!   struct int_tree_map in;
    void **loc;
    unsigned int uid = DECL_UID (var);
  
--- 766,772 ----
  remove_referenced_var (tree var)
  {
    var_ann_t v_ann;
!   struct tree_decl_minimal in;
    void **loc;
    unsigned int uid = DECL_UID (var);
  
*************** remove_referenced_var (tree var)
*** 784,793 ****
    var->base.ann = NULL;
    gcc_assert (DECL_P (var));
    in.uid = uid;
-   in.to = var;
    loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
  				  NO_INSERT);
-   ggc_free (*loc);
    htab_clear_slot (gimple_referenced_vars (cfun), loc);
  }
  
--- 776,783 ----
Index: gcc/tree-ssa.c
===================================================================
*** gcc/tree-ssa.c	(revision 129403)
--- gcc/tree-ssa.c	(working copy)
*************** int_tree_map_hash (const void *item)
*** 774,779 ****
--- 774,797 ----
    return ((const struct int_tree_map *)item)->uid;
  }
  
+ /* Return true if the DECL_UID in both trees are equal.  */
+ 
+ int
+ uid_decl_map_eq (const void *va, const void *vb)
+ {
+   const_tree a = (const_tree) va;
+   const_tree b = (const_tree) vb;
+   return (a->decl_minimal.uid == b->decl_minimal.uid);
+ }
+ 
+ /* Hash a tree in a uid_decl_map.  */
+ 
+ unsigned int
+ uid_decl_map_hash (const void *item)
+ {
+   return ((const_tree)item)->decl_minimal.uid;
+ }
+ 
  /* Return true if the uid in both int tree maps are equal.  */
  
  static int
*************** void
*** 799,806 ****
  init_tree_ssa (void)
  {
    cfun->gimple_df = GGC_CNEW (struct gimple_df);
!   cfun->gimple_df->referenced_vars = htab_create_ggc (20, int_tree_map_hash, 
! 				     		      int_tree_map_eq, NULL);
    cfun->gimple_df->default_defs = htab_create_ggc (20, int_tree_map_hash, 
  				                   int_tree_map_eq, NULL);
    cfun->gimple_df->var_anns = htab_create_ggc (20, var_ann_hash, 
--- 817,824 ----
  init_tree_ssa (void)
  {
    cfun->gimple_df = GGC_CNEW (struct gimple_df);
!   cfun->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash, 
! 				     		      uid_decl_map_eq, NULL);
    cfun->gimple_df->default_defs = htab_create_ggc (20, int_tree_map_hash, 
  				                   int_tree_map_eq, NULL);
    cfun->gimple_df->var_anns = htab_create_ggc (20, var_ann_hash, 
Index: gcc/tree-flow.h
===================================================================
*** gcc/tree-flow.h	(revision 129403)
--- gcc/tree-flow.h	(working copy)
*************** struct mem_ref_stats_d GTY(())
*** 120,126 ****
  struct gimple_df GTY(())
  {
    /* Array of all variables referenced in the function.  */
!   htab_t GTY((param_is (struct int_tree_map))) referenced_vars;
  
    /* A list of all the noreturn calls passed to modify_stmt.
       cleanup_control_flow uses it to detect cases where a mid-block
--- 120,126 ----
  struct gimple_df GTY(())
  {
    /* Array of all variables referenced in the function.  */
!   htab_t GTY((param_is (union tree_node))) referenced_vars;
  
    /* A list of all the noreturn calls passed to modify_stmt.
       cleanup_control_flow uses it to detect cases where a mid-block
*************** struct int_tree_map GTY(())
*** 561,566 ****
--- 561,569 ----
  extern unsigned int int_tree_map_hash (const void *);
  extern int int_tree_map_eq (const void *, const void *);
  
+ extern unsigned int uid_decl_map_hash (const void *);
+ extern int uid_decl_map_eq (const void *, const void *);
+ 
  typedef struct 
  {
    htab_iterator hti;