[PATCH] Introduce global DECL_UID -> tree mapping (with pch fixed)

[PATCH] Introduce global DECL_UID -> tree mapping (with pch fixed)

[Richard Guenther]

This is the mapping introduction patch with a fix for the bootstrap
problems that happened in the "right" ggc circumstances.  The problem
is that the C++ FE ggc_frees decls, so the memory can be re-used while
the global mapping still points to that memory.  Fixed by removing the
decl from the mapping before ggc_freeing it.

I bootstrapped and tested this on x86_64-unknown-linux-gnu with release
checking enabled (this triggered the failure before), and I'll now
re-test the combined patch that makes referenced_vars a bitmap.

I suppose the cp/ change is obvious, so I'll apply the patch again after
that extra testing finished.

Thanks,
Richard.

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

	* tree-flow.h (uid_decl_map_hash, uid_decl_map_eq): Move ...
	* tree.h (uid_decl_map_hash, uid_decl_map_eq): ... here.
	(lookup_decl_from_uid): Declare.
	(remove_decl_from_map): Likewise.
	* tree-ssa.c (uid_decl_map_eq, uid_decl_map_hash): Move ...
	* tree.c (uid_decl_map_eq, uid_decl_map_hash): ... here.
	(decl_for_uid_map): New global hashtable mapping DECL_UID
	to the decl tree.
	(init_ttree): Allocate it.
	(insert_decl_to_uid_decl_map): New helper function.
	(make_node_stat): Insert new decls into the map.
	(copy_node_stat): Likewise.
	(lookup_decl_from_uid): New function.
	(remove_decl_from_map): Likewise.
	(print_decl_for_uid_map_statistics): New helper.
	(dump_tree_statistics): Call it.

	cp/
	* decl.c (duplicate_decls): Remove decl from global mapping
	before ggc_freeing it.

Index: trunk/gcc/tree-flow.h
===================================================================
*** trunk.orig/gcc/tree-flow.h	2008-02-26 11:38:19.000000000 +0100
--- trunk/gcc/tree-flow.h	2008-02-26 11:45:24.000000000 +0100
*************** struct int_tree_map GTY(())
*** 569,577 ****
  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;
--- 569,574 ----
Index: trunk/gcc/tree-ssa.c
===================================================================
*** trunk.orig/gcc/tree-ssa.c	2008-02-26 11:38:19.000000000 +0100
--- trunk/gcc/tree-ssa.c	2008-02-26 11:45:24.000000000 +0100
*************** int_tree_map_hash (const void *item)
*** 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
--- 774,779 ----
Index: trunk/gcc/tree.c
===================================================================
*** trunk.orig/gcc/tree.c	2008-02-26 11:38:19.000000000 +0100
--- trunk/gcc/tree.c	2008-02-26 13:10:42.000000000 +0100
*************** static GTY(()) int next_decl_uid;
*** 110,115 ****
--- 110,121 ----
  /* Unique id for next type created.  */
  static GTY(()) int next_type_uid = 1;
  
+ /* Mapping from unique DECL_UID to the decl tree node.  */
+ static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
+      htab_t decl_for_uid_map;
+ 
+ static void insert_decl_to_uid_decl_map (tree);
+ 
  /* Since we cannot rehash a type after it is in the table, we have to
     keep the hash code.  */
  
*************** init_ttree (void)
*** 231,236 ****
--- 237,245 ----
    
    int_cst_node = make_node (INTEGER_CST);
  
+   decl_for_uid_map = htab_create_ggc (4093, uid_decl_map_hash,
+ 				      uid_decl_map_eq, NULL);
+ 
    tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
    tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
    tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
*************** make_node_stat (enum tree_code code MEM_
*** 601,606 ****
--- 610,616 ----
  	}
        DECL_SOURCE_LOCATION (t) = input_location;
        DECL_UID (t) = next_decl_uid++;
+       insert_decl_to_uid_decl_map (t);
  
        break;
  
*************** copy_node_stat (tree node MEM_STAT_DECL)
*** 704,709 ****
--- 714,720 ----
  	  SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
  	  DECL_BASED_ON_RESTRICT_P (t) = 1;
  	}
+       insert_decl_to_uid_decl_map (t);
      }
    else if (TREE_CODE_CLASS (code) == tcc_type)
      {
*************** build_nt_call_list (tree fn, tree arglis
*** 3325,3330 ****
--- 3336,3421 ----
    return t;
  }
  \f
+ /* 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;
+ }
+ 
+ /* Insert the declaration NODE into the map mapping its unique uid
+    back to the tree.  */
+ 
+ static void
+ insert_decl_to_uid_decl_map (tree node)
+ {
+   void **slot;
+   struct tree_decl_minimal key;
+ 
+   key.uid = DECL_UID (node);
+   slot = htab_find_slot_with_hash (decl_for_uid_map,
+ 				   &key, DECL_UID (node), INSERT);
+ 
+   /* We should never try to re-insert a decl with the same uid.
+      ???  The C++ frontend breaks this invariant.  Hopefully in a
+      non-fatal way, so just overwrite the slot in this case.  */
+ #if 0
+   gcc_assert (!*slot);
+ #endif
+ 
+   *(tree *)slot = node;
+ }
+ 
+ /* Lookup the declaration tree from its unique DECL_UID UID.  Returns
+    the tree node with DECL_UID UID or NULL, if this node was collected.  */
+ 
+ tree
+ lookup_decl_from_uid (int uid)
+ {
+   struct tree_decl_minimal key;
+ 
+   key.uid = uid;
+   return (tree) htab_find_with_hash (decl_for_uid_map, &key, uid);
+ }
+ 
+ /* Remove the declaration tree DECL from the global UID to decl map.
+    This needs to be called if you ggc_free a decl tree, otherwise
+    garbage collection will take care of it.  */
+ 
+ void
+ remove_decl_from_map (tree decl)
+ {
+   struct tree_decl_minimal key;
+ 
+   key.uid = DECL_UID (decl);
+ #if ENABLE_CHECKING
+   gcc_assert (decl == htab_find_with_hash (decl_for_uid_map, &key, key.uid));
+ #endif
+   htab_remove_elt_with_hash (decl_for_uid_map, &key, key.uid);
+ }
+ 
+ /* Print out the statistics for the decl_for_uid_map hash table.  */
+ 
+ static void
+ print_decl_for_uid_map_statistics (void)
+ {
+   fprintf (stderr, "DECL_FOR_UID_MAP hash: size %ld, %ld elements, %f collisions\n",
+ 	   (long) htab_size (decl_for_uid_map),
+ 	   (long) htab_elements (decl_for_uid_map),
+ 	   htab_collisions (decl_for_uid_map));
+ }
+ 
  /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
     We do NOT enter this node in any sort of symbol table.
  
*************** dump_tree_statistics (void)
*** 6654,6659 ****
--- 6745,6751 ----
    print_debug_expr_statistics ();
    print_value_expr_statistics ();
    print_restrict_base_statistics ();
+   print_decl_for_uid_map_statistics ();
    lang_hooks.print_statistics ();
  }
  \f
Index: trunk/gcc/tree.h
===================================================================
*** trunk.orig/gcc/tree.h	2008-02-26 11:38:19.000000000 +0100
--- trunk/gcc/tree.h	2008-02-26 13:11:04.000000000 +0100
*************** struct tree_int_map GTY(())
*** 5233,5238 ****
--- 5233,5246 ----
  #define tree_int_map_hash tree_map_base_hash
  #define tree_int_map_marked_p tree_map_base_marked_p
  
+ /* Map from a DECL_UID to the decl tree.  */
+ 
+ extern unsigned int uid_decl_map_hash (const void *);
+ extern int uid_decl_map_eq (const void *, const void *);
+ extern tree lookup_decl_from_uid (int);
+ extern void remove_decl_from_map (tree);
+ 
+ 
  /* Map from a tree to initialization/finalization priorities.  */
  
  struct tree_priority_map GTY(())
Index: trunk/gcc/cp/decl.c
===================================================================
*** trunk.orig/gcc/cp/decl.c	2008-02-26 10:52:18.000000000 +0100
--- trunk/gcc/cp/decl.c	2008-02-26 13:12:23.000000000 +0100
*************** duplicate_decls (tree newdecl, tree oldd
*** 2154,2159 ****
--- 2154,2160 ----
    /* The NEWDECL will no longer be needed.  Because every out-of-class
       declaration of a member results in a call to duplicate_decls,
       freeing these nodes represents in a significant savings.  */
+   remove_decl_from_map (newdecl);
    ggc_free (newdecl);
  
    return olddecl;

Re: [PATCH] Introduce global DECL_UID -> tree mapping (with pch fixed)

[Richard Guenther]

On Tue, 26 Feb 2008, Richard Guenther wrote:

> 
> This is the mapping introduction patch with a fix for the bootstrap
> problems that happened in the "right" ggc circumstances.  The problem
> is that the C++ FE ggc_frees decls, so the memory can be re-used while
> the global mapping still points to that memory.  Fixed by removing the
> decl from the mapping before ggc_freeing it.
> 
> I bootstrapped and tested this on x86_64-unknown-linux-gnu with release
> checking enabled (this triggered the failure before), and I'll now
> re-test the combined patch that makes referenced_vars a bitmap.
> 
> I suppose the cp/ change is obvious, so I'll apply the patch again after
> that extra testing finished.

Thus, re-applied as rev. 132676.

Richard.

Re: [PATCH] Introduce global DECL_UID -> tree mapping (with pch fixed)

[Richard Guenther]

On Tue, 26 Feb 2008, Richard Guenther wrote:

> On Tue, 26 Feb 2008, Richard Guenther wrote:
> 
> > 
> > This is the mapping introduction patch with a fix for the bootstrap
> > problems that happened in the "right" ggc circumstances.  The problem
> > is that the C++ FE ggc_frees decls, so the memory can be re-used while
> > the global mapping still points to that memory.  Fixed by removing the
> > decl from the mapping before ggc_freeing it.
> > 
> > I bootstrapped and tested this on x86_64-unknown-linux-gnu with release
> > checking enabled (this triggered the failure before), and I'll now
> > re-test the combined patch that makes referenced_vars a bitmap.
> > 
> > I suppose the cp/ change is obvious, so I'll apply the patch again after
> > that extra testing finished.
> 
> Thus, re-applied as rev. 132676.

And reverted again due to other problems.

Richard.