[PATCH][varmap] Add global uid to tree mapping for decls

[Richard Guenther <rguenther at suse dot de>]

This patch adds a global mapping from DECL_UID to its decl.  The mapping
acts as a cache (that is, it doesn't pin decls to memory), unless the
new flag DECL_NOGC_P is set.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to varmap
branch.

This patch is suitable for 4.4 independent of the varmap changes.

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.
	(struct tree_base): Add nogc_flag.
	(DECL_NOGC_P): New define.
	* tree-ssa.c (uid_decl_map_eq, uid_decl_map_hash): Move ...
	* tree.c (uid_decl_map_eq, uid_decl_map_hash): ... here.
	(uid_decl_map_marked_p): New static helper function.
	(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.
	(print_decl_for_uid_map_statistics): New helper.
	(dump_tree_statistics): Call it.

Index: pointer_plus/gcc/tree-flow.h
===================================================================
*** pointer_plus.orig/gcc/tree-flow.h	2007-11-12 15:49:59.000000000 +0100
--- pointer_plus/gcc/tree-flow.h	2007-11-12 15:50:02.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: pointer_plus/gcc/tree-ssa.c
===================================================================
*** pointer_plus.orig/gcc/tree-ssa.c	2007-11-12 15:49:59.000000000 +0100
--- pointer_plus/gcc/tree-ssa.c	2007-11-12 15:50:02.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: pointer_plus/gcc/tree.c
===================================================================
*** pointer_plus.orig/gcc/tree.c	2007-11-12 15:49:59.000000000 +0100
--- pointer_plus/gcc/tree.c	2007-11-12 15:50:17.000000000 +0100
*************** static GTY(()) int next_decl_uid;
*** 110,115 ****
--- 110,123 ----
  /* Unique id for next type created.  */
  static GTY(()) int next_type_uid = 1;
  
+ static int uid_decl_map_marked_p (const void *);
+ 
+ /* Mapping from unique DECL_UID to the decl tree node.  */
+ static GTY ((if_marked ("uid_decl_map_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 ****
--- 239,247 ----
    
    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 ****
--- 612,618 ----
  	}
        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 ****
--- 716,722 ----
  	  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
*** 3324,3329 ****
--- 3337,3414 ----
    return t;
  }
  
+ /* Return true if the DECL in the global uid to decl mapping can be GCed.  */
+ 
+ static int
+ uid_decl_map_marked_p (const void *p)
+ {
+   return DECL_NOGC_P ((const_tree) p) || ggc_marked_p (p);
+ }
+ 
+ /* 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);
+ }
+ 
+ /* 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)
*** 6638,6643 ****
--- 6723,6729 ----
    print_debug_expr_statistics ();
    print_value_expr_statistics ();
    print_restrict_base_statistics ();
+   print_decl_for_uid_map_statistics ();
    lang_hooks.print_statistics ();
  }
  
Index: pointer_plus/gcc/tree.h
===================================================================
*** pointer_plus.orig/gcc/tree.h	2007-11-12 15:49:59.000000000 +0100
--- pointer_plus/gcc/tree.h	2007-11-12 15:50:02.000000000 +0100
*************** struct tree_base GTY(())
*** 398,403 ****
--- 398,404 ----
    unsigned lang_flag_6 : 1;
    unsigned visited : 1;
  
+   unsigned nogc_flag : 1;
    unsigned spare : 23;
  
    /* FIXME tuples: Eventually, we need to move this somewhere external to
*************** struct tree_memory_partition_tag GTY(())
*** 2735,2740 ****
--- 2736,2745 ----
  #define DECL_PRESERVE_P(DECL) \
    DECL_COMMON_CHECK (DECL)->decl_common.preserve_flag
  
+ /* Nonzero for a decl that should be protected from GC.  */
+ #define DECL_NOGC_P(DECL) \
+   ((DECL)->base.nogc_flag)
+ 
  /* For function local variables of COMPLEX and VECTOR types,
     indicates that the variable is not aliased, and that all
     modifications to the variable have been adjusted so that
*************** struct tree_int_map GTY(())
*** 5209,5214 ****
--- 5214,5225 ----
  #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);
+ 
  /* Map from a tree to initialization/finalization priorities.  */
  
  struct tree_priority_map GTY(())