This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

PATCH to TYPE_HASH


As previously mentioned, the canonical type hash table doesn't work very
well with PCH because the hash codes are based on tree addresses which
are not consistent over PCH save and load.  This patch changes TYPE_HASH to
use TYPE_UID instead of the address.

This change turned up a number of places that were using TYPE_HASH on
things which are not, in fact types; I've fixed the ones in the type
hashing code, and introduced a new macro TREE_HASH for other cases, which
seem to be related to hash tables which don't need to survive PCH.

Tested x86_64-pc-linux-gnu, applied to trunk.

2004-03-05  Jason Merrill  <jason@redhat.com>

	* tree.h (TYPE_HASH): Use TYPE_UID.
	(TREE_HASH): New macro with old definition of TYPE_HASH.
	* tree.c (build_type_attribute_variant): Use iterative_hash_object.
	(build_array_type, build_function_type): Likewise.
	(build_method_type_directly): Likewise.
	(build_offset_type, build_complex_type): Likewise.
	(type_hash_list, attribute_hash_list): Likewise. Now static.
	* except.c: s/TYPE_HASH/TREE_HASH/.

*** ./gcc/cp/tree.c.~1~	2004-03-01 17:40:51.000000000 -0500
--- ./gcc/cp/tree.c	2004-03-05 12:53:21.000000000 -0500
*************** list_hash_pieces (tree purpose, tree val
*** 692,705 ****
    hashval_t hashcode = 0;
    
    if (chain)
!     hashcode += TYPE_HASH (chain);
    
    if (value)
!     hashcode += TYPE_HASH (value);
    else
      hashcode += 1007;
    if (purpose)
!     hashcode += TYPE_HASH (purpose);
    else
      hashcode += 1009;
    return hashcode;
--- 692,705 ----
    hashval_t hashcode = 0;
    
    if (chain)
!     hashcode += TREE_HASH (chain);
    
    if (value)
!     hashcode += TREE_HASH (value);
    else
      hashcode += 1007;
    if (purpose)
!     hashcode += TREE_HASH (purpose);
    else
      hashcode += 1009;
    return hashcode;
*** ./gcc/tree.c.~1~	2004-03-04 10:06:56.000000000 -0500
--- ./gcc/tree.c	2004-03-04 17:11:56.000000000 -0500
*************** static hashval_t type_hash_hash (const v
*** 107,112 ****
--- 107,114 ----
  static void print_type_hash_statistics (void);
  static void finish_vector_type (tree);
  static int type_hash_marked_p (const void *);
+ static unsigned int type_hash_list (tree, hashval_t);
+ static unsigned int attribute_hash_list (tree, hashval_t);
  
  tree global_trees[TI_MAX];
  tree integer_types[itk_none];
*************** build_type_attribute_variant (tree ttype
*** 2720,2727 ****
  {
    if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
      {
!       unsigned int hashcode;
        tree ntype;
  
        ntype = copy_node (ttype);
  
--- 2722,2730 ----
  {
    if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
      {
!       hashval_t hashcode = 0;
        tree ntype;
+       enum tree_code code = TREE_CODE (ttype);
  
        ntype = copy_node (ttype);
  
*************** build_type_attribute_variant (tree ttype
*** 2734,2756 ****
        TYPE_NEXT_VARIANT (ntype) = 0;
        set_type_quals (ntype, TYPE_UNQUALIFIED);
  
!       hashcode = (TYPE_HASH (TREE_CODE (ntype))
! 		  + TYPE_HASH (TREE_TYPE (ntype))
! 		  + attribute_hash_list (attribute));
  
        switch (TREE_CODE (ntype))
  	{
  	case FUNCTION_TYPE:
! 	  hashcode += TYPE_HASH (TYPE_ARG_TYPES (ntype));
  	  break;
  	case ARRAY_TYPE:
! 	  hashcode += TYPE_HASH (TYPE_DOMAIN (ntype));
  	  break;
  	case INTEGER_TYPE:
! 	  hashcode += TYPE_HASH (TYPE_MAX_VALUE (ntype));
  	  break;
  	case REAL_TYPE:
! 	  hashcode += TYPE_HASH (TYPE_PRECISION (ntype));
  	  break;
  	default:
  	  break;
--- 2737,2768 ----
        TYPE_NEXT_VARIANT (ntype) = 0;
        set_type_quals (ntype, TYPE_UNQUALIFIED);
  
!       hashcode = iterative_hash_object (code, hashcode);
!       if (TREE_TYPE (ntype))
! 	hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
! 					  hashcode);
!       hashcode = attribute_hash_list (attribute, hashcode);
  
        switch (TREE_CODE (ntype))
  	{
  	case FUNCTION_TYPE:
! 	  hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
  	  break;
  	case ARRAY_TYPE:
! 	  hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
! 					    hashcode);
  	  break;
  	case INTEGER_TYPE:
! 	  hashcode = iterative_hash_object
! 	    (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
! 	  hashcode = iterative_hash_object
! 	    (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
  	  break;
  	case REAL_TYPE:
! 	  {
! 	    unsigned int precision = TYPE_PRECISION (ntype);
! 	    hashcode = iterative_hash_object (precision, hashcode);
! 	  }
  	  break;
  	default:
  	  break;
*************** build_type_copy (tree type)
*** 3051,3063 ****
     of the individual types.  */
  
  unsigned int
! type_hash_list (tree list)
  {
-   unsigned int hashcode;
    tree tail;
  
!   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
!     hashcode += TYPE_HASH (TREE_VALUE (tail));
  
    return hashcode;
  }
--- 3063,3076 ----
     of the individual types.  */
  
  unsigned int
! type_hash_list (tree list, hashval_t hashcode)
  {
    tree tail;
  
!   for (tail = list; tail; tail = TREE_CHAIN (tail))
!     if (TREE_VALUE (tail) != error_mark_node)
!       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
! 					hashcode);
  
    return hashcode;
  }
*************** type_hash_hash (const void *item)
*** 3106,3112 ****
     If one is found, return it.  Otherwise return 0.  */
  
  tree
! type_hash_lookup (unsigned int hashcode, tree type)
  {
    struct type_hash *h, in;
  
--- 3119,3125 ----
     If one is found, return it.  Otherwise return 0.  */
  
  tree
! type_hash_lookup (hashval_t hashcode, tree type)
  {
    struct type_hash *h, in;
  
*************** type_hash_lookup (unsigned int hashcode,
*** 3127,3133 ****
     for a type TYPE whose hash code is HASHCODE.  */
  
  void
! type_hash_add (unsigned int hashcode, tree type)
  {
    struct type_hash *h;
    void **loc;
--- 3140,3146 ----
     for a type TYPE whose hash code is HASHCODE.  */
  
  void
! type_hash_add (hashval_t hashcode, tree type)
  {
    struct type_hash *h;
    void **loc;
*************** print_type_hash_statistics (void)
*** 3207,3220 ****
     by adding the hash codes of the individual attributes.  */
  
  unsigned int
! attribute_hash_list (tree list)
  {
-   unsigned int hashcode;
    tree tail;
  
!   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
      /* ??? Do we want to add in TREE_VALUE too? */
!     hashcode += TYPE_HASH (TREE_PURPOSE (tail));
    return hashcode;
  }
  
--- 3220,3233 ----
     by adding the hash codes of the individual attributes.  */
  
  unsigned int
! attribute_hash_list (tree list, hashval_t hashcode)
  {
    tree tail;
  
!   for (tail = list; tail; tail = TREE_CHAIN (tail))
      /* ??? Do we want to add in TREE_VALUE too? */
!     hashcode = iterative_hash_object
!       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
    return hashcode;
  }
  
*************** tree
*** 3940,3946 ****
  build_array_type (tree elt_type, tree index_type)
  {
    tree t;
!   unsigned int hashcode;
  
    if (TREE_CODE (elt_type) == FUNCTION_TYPE)
      {
--- 3953,3959 ----
  build_array_type (tree elt_type, tree index_type)
  {
    tree t;
!   hashval_t hashcode = 0;
  
    if (TREE_CODE (elt_type) == FUNCTION_TYPE)
      {
*************** build_array_type (tree elt_type, tree in
*** 3962,3968 ****
        return t;
      }
  
!   hashcode = TYPE_HASH (elt_type) + TYPE_HASH (index_type);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
--- 3975,3982 ----
        return t;
      }
  
!   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
!   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
*************** tree
*** 3995,4001 ****
  build_function_type (tree value_type, tree arg_types)
  {
    tree t;
!   unsigned int hashcode;
  
    if (TREE_CODE (value_type) == FUNCTION_TYPE)
      {
--- 4009,4015 ----
  build_function_type (tree value_type, tree arg_types)
  {
    tree t;
!   hashval_t hashcode = 0;
  
    if (TREE_CODE (value_type) == FUNCTION_TYPE)
      {
*************** build_function_type (tree value_type, tr
*** 4009,4015 ****
    TYPE_ARG_TYPES (t) = arg_types;
  
    /* If we already have such a type, use the old one and free this one.  */
!   hashcode = TYPE_HASH (value_type) + type_hash_list (arg_types);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
--- 4023,4030 ----
    TYPE_ARG_TYPES (t) = arg_types;
  
    /* If we already have such a type, use the old one and free this one.  */
!   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
!   hashcode = type_hash_list (arg_types, hashcode);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
*************** build_method_type_directly (tree basetyp
*** 4055,4061 ****
  {
    tree t;
    tree ptype;
!   int hashcode;
  
    /* Make a node of the sort we want.  */
    t = make_node (METHOD_TYPE);
--- 4070,4076 ----
  {
    tree t;
    tree ptype;
!   int hashcode = 0;
  
    /* Make a node of the sort we want.  */
    t = make_node (METHOD_TYPE);
*************** build_method_type_directly (tree basetyp
*** 4071,4078 ****
  
    /* If we already have such a type, use the old one and free this one.
       Note that it also frees up the above cons cell if found.  */
!   hashcode = TYPE_HASH (basetype) + TYPE_HASH (rettype) +
!     type_hash_list (argtypes);
  
    t = type_hash_canon (hashcode, t);
  
--- 4086,4094 ----
  
    /* If we already have such a type, use the old one and free this one.
       Note that it also frees up the above cons cell if found.  */
!   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
!   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
!   hashcode = type_hash_list (argtypes, hashcode);
  
    t = type_hash_canon (hashcode, t);
  
*************** tree
*** 4106,4112 ****
  build_offset_type (tree basetype, tree type)
  {
    tree t;
!   unsigned int hashcode;
  
    /* Make a node of the sort we want.  */
    t = make_node (OFFSET_TYPE);
--- 4122,4128 ----
  build_offset_type (tree basetype, tree type)
  {
    tree t;
!   hashval_t hashcode = 0;
  
    /* Make a node of the sort we want.  */
    t = make_node (OFFSET_TYPE);
*************** build_offset_type (tree basetype, tree t
*** 4115,4121 ****
    TREE_TYPE (t) = type;
  
    /* If we already have such a type, use the old one and free this one.  */
!   hashcode = TYPE_HASH (basetype) + TYPE_HASH (type);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
--- 4131,4138 ----
    TREE_TYPE (t) = type;
  
    /* If we already have such a type, use the old one and free this one.  */
!   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
!   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
*************** tree
*** 4130,4136 ****
  build_complex_type (tree component_type)
  {
    tree t;
!   unsigned int hashcode;
  
    /* Make a node of the sort we want.  */
    t = make_node (COMPLEX_TYPE);
--- 4147,4153 ----
  build_complex_type (tree component_type)
  {
    tree t;
!   hashval_t hashcode;
  
    /* Make a node of the sort we want.  */
    t = make_node (COMPLEX_TYPE);
*************** build_complex_type (tree component_type)
*** 4139,4145 ****
    set_type_quals (t, TYPE_QUALS (component_type));
  
    /* If we already have such a type, use the old one and free this one.  */
!   hashcode = TYPE_HASH (component_type);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
--- 4156,4162 ----
    set_type_quals (t, TYPE_QUALS (component_type));
  
    /* If we already have such a type, use the old one and free this one.  */
!   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
    t = type_hash_canon (hashcode, t);
  
    if (!COMPLETE_TYPE_P (t))
*** ./gcc/tree.h.~1~	2004-03-04 10:06:56.000000000 -0500
--- ./gcc/tree.h	2004-03-04 17:11:56.000000000 -0500
*************** extern void tree_operand_check_failed (i
*** 386,392 ****
  
  /* Here is how primitive or already-canonicalized types' hash codes
     are made.  */
! #define TYPE_HASH(TYPE) ((size_t) (TYPE) & 0777777)
  
  /* Nodes are chained together for many purposes.
     Types are chained together to record them for being output to the debugger
--- 386,396 ----
  
  /* Here is how primitive or already-canonicalized types' hash codes
     are made.  */
! #define TYPE_HASH(TYPE) (TYPE_UID (TYPE))
! 
! /* A simple hash function for an arbitrary tree node.  This must not be
!    used in hash tables which are saved to a PCH.  */
! #define TREE_HASH(NODE) ((size_t) (NODE) & 0777777)
  
  /* Nodes are chained together for many purposes.
     Types are chained together to record them for being output to the debugger
*************** extern tree array_type_nelts (tree);
*** 2167,2173 ****
  extern tree value_member (tree, tree);
  extern tree purpose_member (tree, tree);
  extern tree binfo_member (tree, tree);
! extern unsigned int attribute_hash_list (tree);
  extern int attribute_list_equal (tree, tree);
  extern int attribute_list_contained (tree, tree);
  extern int tree_int_cst_equal (tree, tree);
--- 2171,2177 ----
  extern tree value_member (tree, tree);
  extern tree purpose_member (tree, tree);
  extern tree binfo_member (tree, tree);
! 
  extern int attribute_list_equal (tree, tree);
  extern int attribute_list_contained (tree, tree);
  extern int tree_int_cst_equal (tree, tree);
*************** extern int type_list_equal (tree, tree);
*** 2868,2874 ****
  extern int chain_member (tree, tree);
  extern tree type_hash_lookup (unsigned int, tree);
  extern void type_hash_add (unsigned int, tree);
- extern unsigned int type_hash_list (tree);
  extern int simple_cst_list_equal (tree, tree);
  extern void dump_tree_statistics (void);
  extern void expand_function_end (void);
--- 2872,2877 ----
*** ./gcc/except.c.~1~	2004-02-26 15:17:46.000000000 -0500
--- ./gcc/except.c	2004-03-04 17:11:56.000000000 -0500
*************** static hashval_t
*** 1411,1417 ****
  t2r_hash (const void *pentry)
  {
    tree entry = (tree) pentry;
!   return TYPE_HASH (TREE_PURPOSE (entry));
  }
  
  static void
--- 1411,1417 ----
  t2r_hash (const void *pentry)
  {
    tree entry = (tree) pentry;
!   return TREE_HASH (TREE_PURPOSE (entry));
  }
  
  static void
*************** add_type_for_runtime (tree type)
*** 1420,1426 ****
    tree *slot;
  
    slot = (tree *) htab_find_slot_with_hash (type_to_runtime_map, type,
! 					    TYPE_HASH (type), INSERT);
    if (*slot == NULL)
      {
        tree runtime = (*lang_eh_runtime_type) (type);
--- 1420,1426 ----
    tree *slot;
  
    slot = (tree *) htab_find_slot_with_hash (type_to_runtime_map, type,
! 					    TREE_HASH (type), INSERT);
    if (*slot == NULL)
      {
        tree runtime = (*lang_eh_runtime_type) (type);
*************** lookup_type_for_runtime (tree type)
*** 1434,1440 ****
    tree *slot;
  
    slot = (tree *) htab_find_slot_with_hash (type_to_runtime_map, type,
! 					    TYPE_HASH (type), NO_INSERT);
  
    /* We should have always inserted the data earlier.  */
    return TREE_VALUE (*slot);
--- 1434,1440 ----
    tree *slot;
  
    slot = (tree *) htab_find_slot_with_hash (type_to_runtime_map, type,
! 					    TREE_HASH (type), NO_INSERT);
  
    /* We should have always inserted the data earlier.  */
    return TREE_VALUE (*slot);
*************** static hashval_t
*** 1465,1471 ****
  ttypes_filter_hash (const void *pentry)
  {
    const struct ttypes_filter *entry = (const struct ttypes_filter *) pentry;
!   return TYPE_HASH (entry->t);
  }
  
  /* Compare ENTRY with DATA (both struct ttypes_filter) for a @TTypes
--- 1465,1471 ----
  ttypes_filter_hash (const void *pentry)
  {
    const struct ttypes_filter *entry = (const struct ttypes_filter *) pentry;
!   return TREE_HASH (entry->t);
  }
  
  /* Compare ENTRY with DATA (both struct ttypes_filter) for a @TTypes
*************** ehspec_filter_hash (const void *pentry)
*** 1492,1503 ****
    tree list;
  
    for (list = entry->t; list ; list = TREE_CHAIN (list))
!     h = (h << 5) + (h >> 27) + TYPE_HASH (TREE_VALUE (list));
    return h;
  }
  
! /* Add TYPE to cfun->eh->ttype_data, using TYPES_HASH to speed
!    up the search.  Return the filter value to be used.  */
  
  static int
  add_ttypes_entry (htab_t ttypes_hash, tree type)
--- 1492,1503 ----
    tree list;
  
    for (list = entry->t; list ; list = TREE_CHAIN (list))
!     h = (h << 5) + (h >> 27) + TREE_HASH (TREE_VALUE (list));
    return h;
  }
  
! /* Add TYPE (which may be NULL) to cfun->eh->ttype_data, using TYPES_HASH
!    to speed up the search.  Return the filter value to be used.  */
  
  static int
  add_ttypes_entry (htab_t ttypes_hash, tree type)
*************** add_ttypes_entry (htab_t ttypes_hash, tr
*** 1505,1511 ****
    struct ttypes_filter **slot, *n;
  
    slot = (struct ttypes_filter **)
!     htab_find_slot_with_hash (ttypes_hash, type, TYPE_HASH (type), INSERT);
  
    if ((n = *slot) == NULL)
      {
--- 1505,1511 ----
    struct ttypes_filter **slot, *n;
  
    slot = (struct ttypes_filter **)
!     htab_find_slot_with_hash (ttypes_hash, type, TREE_HASH (type), INSERT);
  
    if ((n = *slot) == NULL)
      {

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]