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

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

[Richard Guenther]

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(())

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

[Richard Guenther]

On Fri, 9 Nov 2007, Richard Guenther wrote:

> 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.

I am going to go forward with this (and the followup) early next week.

http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00524.html

This will make referenced_vars a bitmap which allows stable traversal
and fixes most of the bootstrap-debug fails if we re-enable
remove_unused_vars before final inlining.

> 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).

I will not do this though, but file a PR instead and let the C++ FE
maintainers sort this out.

Constructive complaints welcome;  if this is in I am going to
tackle the unexpanded_vars list next, which if made a bitmap will
allow us getting rid of TREE_CHAIN of (hopefully all) decls.

If we do the same for BLOCK_VARS we can get rid of remove_unused_vars
pass and let GC do its work instead.  (remove_unused_vars takes quite
some compile-time on tramp3d, which of course overall pays back)

Thanks,
Richard.

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

[Andrew MacLeod]

Richard Guenther wrote:
> On Fri, 9 Nov 2007, Richard Guenther wrote:
>
>   
>> 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.
>>     
>
> I am going to go forward with this (and the followup) early next week.
>
> http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00524.html
>
> This will make referenced_vars a bitmap which allows stable traversal
> and fixes most of the bootstrap-debug fails if we re-enable
> remove_unused_vars before final inlining.
>
>   

I didn't take notice of this the first time through :-)

This oughta fix the odd compile time hit we have when the hash table 
doesn't perform well too eh? I remember looking at something a few weeks 
ago where most of the operand scan time (which was needlessly excessive) 
was almost all in referenced_var hash table lookups.  getting rid of 
that hash lookup is a good thing.

Andrew

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

[Diego Novillo]

On 2/22/08 2:00 PM, Andrew MacLeod wrote:

> This oughta fix the odd compile time hit we have when the hash table 
> doesn't perform well too eh? I remember looking at something a few weeks 
> ago where most of the operand scan time (which was needlessly excessive) 
> was almost all in referenced_var hash table lookups.  getting rid of 
> that hash lookup is a good thing.

Indeed.  I like this change quite a bit.  Thanks for working on this 
Richard.


Diego.

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

[Richard Guenther]

On Sat, Feb 23, 2008 at 12:46 AM, Diego Novillo <dnovillo@google.com> wrote:
> On 2/22/08 2:00 PM, Andrew MacLeod wrote:
>
>  > This oughta fix the odd compile time hit we have when the hash table
>  > doesn't perform well too eh? I remember looking at something a few weeks
>  > ago where most of the operand scan time (which was needlessly excessive)
>  > was almost all in referenced_var hash table lookups.  getting rid of
>  > that hash lookup is a good thing.

Though we replace it with a hash lookup on the global table.

>  Indeed.  I like this change quite a bit.  Thanks for working on this
>  Richard.

It might also prove useful for IPA analysis where you now can track vars
with just their UIDs (rather than function + UID).

Richard.

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

[Richard Guenther]

On Fri, 22 Feb 2008, Diego Novillo wrote:

> On 2/22/08 2:00 PM, Andrew MacLeod wrote:
> 
> > This oughta fix the odd compile time hit we have when the hash table doesn't
> > perform well too eh? I remember looking at something a few weeks ago where
> > most of the operand scan time (which was needlessly excessive) was almost
> > all in referenced_var hash table lookups.  getting rid of that hash lookup
> > is a good thing.
> 
> Indeed.  I like this change quite a bit.  Thanks for working on this Richard.

Applied after re-testing on x86_64-unknown-linux-gnu as r132629.

Richard.