[PATCH][4.4] Add a global DECL_UID -> tree mapping

[Richard Guenther <rguenther@suse.de>]

This patch adds a global map to look up a decl from its uid.  At the
moment all places doing this use the referenced_vars () hashtables which
exist per function and only during a part of the compilation.

This patch enables making these hashtables bitmaps which allows to
do unused vars removal more efficient and makes walking referenced vars
order independed of the hashtable size (the walk is now sorted after
UID).  See the followup patch.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

For tramp3d the global hashtable peaks at 1M entries which makes its
cost 8MB on a x86_64 architecture.

FYI, I was just sitting on this patch for a while now.

You can also see the single problem:

+   /* 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

so the C++ frontend does something "interesting" here, which still
needs investigation (and fixing).

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.
	* 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.
	(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-09 13:55:57.000000000 +0100
--- pointer_plus/gcc/tree-flow.h	2007-11-09 15:07:34.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-09 11:05:46.000000000 +0100
--- pointer_plus/gcc/tree-ssa.c	2007-11-09 15:07:34.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-09 11:06:59.000000000 +0100
--- pointer_plus/gcc/tree.c	2007-11-09 15:07:34.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
*** 3324,3329 ****
--- 3335,3404 ----
    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);
+ }
+ 
+ /* 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 ****
--- 6713,6719 ----
    print_debug_expr_statistics ();
    print_value_expr_statistics ();
    print_restrict_base_statistics ();
+   print_decl_for_uid_map_statistics ();
    lang_hooks.print_statistics ();
  }
  \f
Index: pointer_plus/gcc/tree.h
===================================================================
*** pointer_plus.orig/gcc/tree.h	2007-11-09 11:06:59.000000000 +0100
--- pointer_plus/gcc/tree.h	2007-11-09 15:07:34.000000000 +0100
*************** struct tree_int_map GTY(())
*** 5209,5214 ****
--- 5209,5220 ----
  #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(())