Move cgraph_node_set and varpool_node_set out of GGC and make them use pointer_map

Move cgraph_node_set and varpool_node_set out of GGC and make them use pointer_map

[Jan Hubicka]

Hi,
I always considered the cgrpah_node_set/varpool_node_set to be overengineered
but they also turned out to be quite ineffective since we do quite a lot of
queries into them during stremaing out.

This patch moves them to pointer_map, like I did for streamer cache.  While
doing so I needed to get the structure out of GGC memory since pointer_map is
not ggc firendly. This is not a deal at all, because the sets can only point to
live cgraph/varpool entries anyway. Pointing to removed ones would lead to
spectacular failures in any case.

Bootstrapped/regtested x86_64-linux, OK?

Honza

	* cgraph.h (cgraph_node_set_def, varpool_node_set_def): Move out of GTY;
	replace hash by pointer map.
	(cgraph_node_set_element_def, cgraph_node_set_element,
	const_cgraph_node_set_element, varpool_node_set_element_def,
	varpool_node_set_element, const_varpool_node_set_element): Remove.
	(free_cgraph_node_set, free_varpool_node_set): New function.
	(cgraph_node_set_size, varpool_node_set_size): Use vector size.
	* tree-emutls.c: Free varpool node set.
	* ipa-utils.c (cgraph_node_set_new, cgraph_node_set_add,
	cgraph_node_set_remove, cgraph_node_set_find, dump_cgraph_node_set,
	debug_cgraph_node_set, free_cgraph_node_set, varpool_node_set_new,
	varpool_node_set_add, varpool_node_set_remove, varpool_node_set_find,
	dump_varpool_node_set, free_varpool_node_set, debug_varpool_node_set):
	Move here from ipa.c; implement using pointer_map
	* ipa.c (cgraph_node_set_new, cgraph_node_set_add,
	cgraph_node_set_remove, cgraph_node_set_find, dump_cgraph_node_set,
	debug_cgraph_node_set, varpool_node_set_new,
	varpool_node_set_add, varpool_node_set_remove, varpool_node_set_find,
	dump_varpool_node_set, debug_varpool_node_set):
	Move to ipa-uitls.c.
	* lto/lto.c (ltrans_partition_def): Remove GTY annotations.
	(ltrans_partitions): Move to heap.
	(new_partition): Update.
	(free_ltrans_partitions): New function.
	(lto_wpa_write_files): Use it.
	* passes.c (ipa_write_summaries): Update.
Index: cgraph.h
===================================================================
*** cgraph.h	(revision 173301)
--- cgraph.h	(working copy)
*************** DEF_VEC_ALLOC_P(cgraph_node_ptr,gc);
*** 256,265 ****
  
  /* A cgraph node set is a collection of cgraph nodes.  A cgraph node
     can appear in multiple sets.  */
! struct GTY(()) cgraph_node_set_def
  {
!   htab_t GTY((param_is (struct cgraph_node_set_element_def))) hashtab;
!   VEC(cgraph_node_ptr, gc) *nodes;
  };
  
  typedef struct varpool_node *varpool_node_ptr;
--- 256,265 ----
  
  /* A cgraph node set is a collection of cgraph nodes.  A cgraph node
     can appear in multiple sets.  */
! struct cgraph_node_set_def
  {
!   struct pointer_map_t *map;
!   VEC(cgraph_node_ptr, heap) *nodes;
  };
  
  typedef struct varpool_node *varpool_node_ptr;
*************** DEF_VEC_ALLOC_P(varpool_node_ptr,gc);
*** 270,279 ****
  
  /* A varpool node set is a collection of varpool nodes.  A varpool node
     can appear in multiple sets.  */
! struct GTY(()) varpool_node_set_def
  {
!   htab_t GTY((param_is (struct varpool_node_set_element_def))) hashtab;
!   VEC(varpool_node_ptr, gc) *nodes;
  };
  
  typedef struct cgraph_node_set_def *cgraph_node_set;
--- 270,279 ----
  
  /* A varpool node set is a collection of varpool nodes.  A varpool node
     can appear in multiple sets.  */
! struct varpool_node_set_def
  {
!   struct pointer_map_t * map;
!   VEC(varpool_node_ptr, heap) *nodes;
  };
  
  typedef struct cgraph_node_set_def *cgraph_node_set;
*************** DEF_VEC_P(varpool_node_set);
*** 288,304 ****
  DEF_VEC_ALLOC_P(varpool_node_set,gc);
  DEF_VEC_ALLOC_P(varpool_node_set,heap);
  
- /* A cgraph node set element contains an index in the vector of nodes in
-    the set.  */
- struct GTY(()) cgraph_node_set_element_def
- {
-   struct cgraph_node *node;
-   HOST_WIDE_INT index;
- };
- 
- typedef struct cgraph_node_set_element_def *cgraph_node_set_element;
- typedef const struct cgraph_node_set_element_def *const_cgraph_node_set_element;
- 
  /* Iterator structure for cgraph node sets.  */
  typedef struct
  {
--- 288,293 ----
*************** typedef struct
*** 306,322 ****
    unsigned index;
  } cgraph_node_set_iterator;
  
- /* A varpool node set element contains an index in the vector of nodes in
-    the set.  */
- struct GTY(()) varpool_node_set_element_def
- {
-   struct varpool_node *node;
-   HOST_WIDE_INT index;
- };
- 
- typedef struct varpool_node_set_element_def *varpool_node_set_element;
- typedef const struct varpool_node_set_element_def *const_varpool_node_set_element;
- 
  /* Iterator structure for varpool node sets.  */
  typedef struct
  {
--- 295,300 ----
*************** void cgraph_node_set_add (cgraph_node_se
*** 632,637 ****
--- 610,616 ----
  void cgraph_node_set_remove (cgraph_node_set, struct cgraph_node *);
  void dump_cgraph_node_set (FILE *, cgraph_node_set);
  void debug_cgraph_node_set (cgraph_node_set);
+ void free_cgraph_node_set (cgraph_node_set);
  
  varpool_node_set varpool_node_set_new (void);
  varpool_node_set_iterator varpool_node_set_find (varpool_node_set,
*************** void varpool_node_set_add (varpool_node_
*** 640,645 ****
--- 619,625 ----
  void varpool_node_set_remove (varpool_node_set, struct varpool_node *);
  void dump_varpool_node_set (FILE *, varpool_node_set);
  void debug_varpool_node_set (varpool_node_set);
+ void free_varpool_node_set (varpool_node_set);
  void ipa_discover_readonly_nonaddressable_vars (void);
  bool cgraph_comdat_can_be_unshared_p (struct cgraph_node *);
  
*************** cgraph_node_in_set_p (struct cgraph_node
*** 763,769 ****
  static inline size_t
  cgraph_node_set_size (cgraph_node_set set)
  {
!   return htab_elements (set->hashtab);
  }
  
  /* Return true if iterator VSI points to nothing.  */
--- 743,749 ----
  static inline size_t
  cgraph_node_set_size (cgraph_node_set set)
  {
!   return VEC_length (cgraph_node_ptr, set->nodes);
  }
  
  /* Return true if iterator VSI points to nothing.  */
*************** varpool_node_in_set_p (struct varpool_no
*** 811,817 ****
  static inline size_t
  varpool_node_set_size (varpool_node_set set)
  {
!   return htab_elements (set->hashtab);
  }
  
  /* Uniquize all constants that appear in memory.
--- 791,797 ----
  static inline size_t
  varpool_node_set_size (varpool_node_set set)
  {
!   return VEC_length (varpool_node_ptr, set->nodes);
  }
  
  /* Uniquize all constants that appear in memory.
Index: tree-emutls.c
===================================================================
*** tree-emutls.c	(revision 173301)
--- tree-emutls.c	(working copy)
*************** ipa_lower_emutls (void)
*** 781,787 ****
  
    VEC_free (varpool_node_ptr, heap, control_vars);
    VEC_free (tree, heap, access_vars);
!   tls_vars = NULL;
  
    return TODO_dump_func | TODO_ggc_collect | TODO_verify_all;
  }
--- 781,787 ----
  
    VEC_free (varpool_node_ptr, heap, control_vars);
    VEC_free (tree, heap, access_vars);
!   free_varpool_node_set (tls_vars);
  
    return TODO_dump_func | TODO_ggc_collect | TODO_verify_all;
  }
Index: ipa-utils.c
===================================================================
*** ipa-utils.c	(revision 173301)
--- ipa-utils.c	(working copy)
*************** get_base_var (tree t)
*** 324,326 ****
--- 324,583 ----
    return t;
  }
  
+ 
+ /* Create a new cgraph node set.  */
+ 
+ cgraph_node_set
+ cgraph_node_set_new (void)
+ {
+   cgraph_node_set new_node_set;
+ 
+   new_node_set = XCNEW (struct cgraph_node_set_def);
+   new_node_set->map = pointer_map_create ();
+   new_node_set->nodes = NULL;
+   return new_node_set;
+ }
+ 
+ 
+ /* Add cgraph_node NODE to cgraph_node_set SET.  */
+ 
+ void
+ cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
+ {
+   void **slot;
+ 
+   slot = pointer_map_insert (set->map, node);
+ 
+   if (*slot)
+     {
+       int index = (size_t) *slot - 1;
+       gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
+ 		           == node));
+       return;
+     }
+ 
+   *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
+ 
+   /* Insert into node vector.  */
+   VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);
+ }
+ 
+ 
+ /* Remove cgraph_node NODE from cgraph_node_set SET.  */
+ 
+ void
+ cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
+ {
+   void **slot, **last_slot;
+   int index;
+   struct cgraph_node *last_node;
+ 
+   slot = pointer_map_contains (set->map, node);
+   if (slot == NULL || !*slot)
+     return;
+ 
+   index = (size_t) *slot - 1;
+   gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index)
+ 	      	       == node);
+ 
+   /* Remove from vector. We do this by swapping node with the last element
+      of the vector.  */
+   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
+   if (last_node != node)
+     {
+       last_slot = pointer_map_contains (set->map, last_node);
+       gcc_checking_assert (last_slot && *last_slot);
+       *last_slot = (void *)(size_t) (index + 1);
+ 
+       /* Move the last element to the original spot of NODE.  */
+       VEC_replace (cgraph_node_ptr, set->nodes, index, last_node);
+     }
+ 
+   /* Remove element from hash table.  */
+   *slot = NULL;
+ }
+ 
+ 
+ /* Find NODE in SET and return an iterator to it if found.  A null iterator
+    is returned if NODE is not in SET.  */
+ 
+ cgraph_node_set_iterator
+ cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
+ {
+   void **slot;
+   cgraph_node_set_iterator csi;
+ 
+   slot = pointer_map_contains (set->map, node);
+   if (slot == NULL || !*slot)
+     csi.index = (unsigned) ~0;
+   else
+     csi.index = (size_t)*slot - 1;
+   csi.set = set;
+ 
+   return csi;
+ }
+ 
+ 
+ /* Dump content of SET to file F.  */
+ 
+ void
+ dump_cgraph_node_set (FILE *f, cgraph_node_set set)
+ {
+   cgraph_node_set_iterator iter;
+ 
+   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
+     {
+       struct cgraph_node *node = csi_node (iter);
+       fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
+     }
+   fprintf (f, "\n");
+ }
+ 
+ 
+ /* Dump content of SET to stderr.  */
+ 
+ DEBUG_FUNCTION void
+ debug_cgraph_node_set (cgraph_node_set set)
+ {
+   dump_cgraph_node_set (stderr, set);
+ }
+ 
+ 
+ /* Free varpool node set.  */
+ 
+ void
+ free_cgraph_node_set (cgraph_node_set set)
+ {
+   VEC_free (cgraph_node_ptr, heap, set->nodes);
+   pointer_map_destroy (set->map);
+   free (set);
+ }
+ 
+ 
+ /* Create a new varpool node set.  */
+ 
+ varpool_node_set
+ varpool_node_set_new (void)
+ {
+   varpool_node_set new_node_set;
+ 
+   new_node_set = XCNEW (struct varpool_node_set_def);
+   new_node_set->map = pointer_map_create ();
+   new_node_set->nodes = NULL;
+   return new_node_set;
+ }
+ 
+ 
+ /* Add varpool_node NODE to varpool_node_set SET.  */
+ 
+ void
+ varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
+ {
+   void **slot;
+ 
+   slot = pointer_map_insert (set->map, node);
+ 
+   if (*slot)
+     {
+       int index = (size_t) *slot - 1;
+       gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index)
+ 		           == node));
+       return;
+     }
+ 
+   *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1);
+ 
+   /* Insert into node vector.  */
+   VEC_safe_push (varpool_node_ptr, heap, set->nodes, node);
+ }
+ 
+ 
+ /* Remove varpool_node NODE from varpool_node_set SET.  */
+ 
+ void
+ varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
+ {
+   void **slot, **last_slot;
+   int index;
+   struct varpool_node *last_node;
+ 
+   slot = pointer_map_contains (set->map, node);
+   if (slot == NULL || !*slot)
+     return;
+ 
+   index = (size_t) *slot - 1;
+   gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index)
+ 	      	       == node);
+ 
+   /* Remove from vector. We do this by swapping node with the last element
+      of the vector.  */
+   last_node = VEC_pop (varpool_node_ptr, set->nodes);
+   if (last_node != node)
+     {
+       last_slot = pointer_map_contains (set->map, last_node);
+       gcc_checking_assert (last_slot && *last_slot);
+       *last_slot = (void *)(size_t) (index + 1);
+ 
+       /* Move the last element to the original spot of NODE.  */
+       VEC_replace (varpool_node_ptr, set->nodes, index, last_node);
+     }
+ 
+   /* Remove element from hash table.  */
+   *slot = NULL;
+ }
+ 
+ 
+ /* Find NODE in SET and return an iterator to it if found.  A null iterator
+    is returned if NODE is not in SET.  */
+ 
+ varpool_node_set_iterator
+ varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
+ {
+   void **slot;
+   varpool_node_set_iterator vsi;
+ 
+   slot = pointer_map_contains (set->map, node);
+   if (slot == NULL || !*slot)
+     vsi.index = (unsigned) ~0;
+   else
+     vsi.index = (size_t)*slot - 1;
+   vsi.set = set;
+ 
+   return vsi;
+ }
+ 
+ 
+ /* Dump content of SET to file F.  */
+ 
+ void
+ dump_varpool_node_set (FILE *f, varpool_node_set set)
+ {
+   varpool_node_set_iterator iter;
+ 
+   for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
+     {
+       struct varpool_node *node = vsi_node (iter);
+       fprintf (f, " %s", varpool_node_name (node));
+     }
+   fprintf (f, "\n");
+ }
+ 
+ 
+ /* Free varpool node set.  */
+ 
+ void
+ free_varpool_node_set (varpool_node_set set)
+ {
+   VEC_free (varpool_node_ptr, heap, set->nodes);
+   pointer_map_destroy (set->map);
+   free (set);
+ }
+ 
+ 
+ /* Dump content of SET to stderr.  */
+ 
+ DEBUG_FUNCTION void
+ debug_varpool_node_set (varpool_node_set set)
+ {
+   dump_varpool_node_set (stderr, set);
+ }
Index: ipa.c
===================================================================
*** ipa.c	(revision 173301)
--- ipa.c	(working copy)
*************** struct ipa_opt_pass_d pass_ipa_whole_pro
*** 1047,1366 ****
   NULL,					/* variable_transform */
  };
  
- /* Hash a cgraph node set element.  */
- 
- static hashval_t
- hash_cgraph_node_set_element (const void *p)
- {
-   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
-   return htab_hash_pointer (element->node);
- }
- 
- /* Compare two cgraph node set elements.  */
- 
- static int
- eq_cgraph_node_set_element (const void *p1, const void *p2)
- {
-   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
-   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
- 
-   return e1->node == e2->node;
- }
- 
- /* Create a new cgraph node set.  */
- 
- cgraph_node_set
- cgraph_node_set_new (void)
- {
-   cgraph_node_set new_node_set;
- 
-   new_node_set = ggc_alloc_cgraph_node_set_def ();
-   new_node_set->hashtab = htab_create_ggc (10,
- 					   hash_cgraph_node_set_element,
- 					   eq_cgraph_node_set_element,
- 					   NULL);
-   new_node_set->nodes = NULL;
-   return new_node_set;
- }
- 
- /* Add cgraph_node NODE to cgraph_node_set SET.  */
- 
- void
- cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
- {
-   void **slot;
-   cgraph_node_set_element element;
-   struct cgraph_node_set_element_def dummy;
- 
-   dummy.node = node;
-   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
- 
-   if (*slot != HTAB_EMPTY_ENTRY)
-     {
-       element = (cgraph_node_set_element) *slot;
-       gcc_assert (node == element->node
- 		  && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
- 		      == node));
-       return;
-     }
- 
-   /* Insert node into hash table.  */
-   element = ggc_alloc_cgraph_node_set_element_def ();
-   element->node = node;
-   element->index = VEC_length (cgraph_node_ptr, set->nodes);
-   *slot = element;
- 
-   /* Insert into node vector.  */
-   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
- }
- 
- /* Remove cgraph_node NODE from cgraph_node_set SET.  */
- 
- void
- cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
- {
-   void **slot, **last_slot;
-   cgraph_node_set_element element, last_element;
-   struct cgraph_node *last_node;
-   struct cgraph_node_set_element_def dummy;
- 
-   dummy.node = node;
-   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
-   if (slot == NULL)
-     return;
- 
-   element = (cgraph_node_set_element) *slot;
-   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
- 	      == node);
- 
-   /* Remove from vector. We do this by swapping node with the last element
-      of the vector.  */
-   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
-   if (last_node != node)
-     {
-       dummy.node = last_node;
-       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
-       last_element = (cgraph_node_set_element) *last_slot;
-       gcc_assert (last_element);
- 
-       /* Move the last element to the original spot of NODE.  */
-       last_element->index = element->index;
-       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
- 		   last_node);
-     }
- 
-   /* Remove element from hash table.  */
-   htab_clear_slot (set->hashtab, slot);
-   ggc_free (element);
- }
- 
- /* Find NODE in SET and return an iterator to it if found.  A null iterator
-    is returned if NODE is not in SET.  */
- 
- cgraph_node_set_iterator
- cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
- {
-   void **slot;
-   struct cgraph_node_set_element_def dummy;
-   cgraph_node_set_element element;
-   cgraph_node_set_iterator csi;
- 
-   dummy.node = node;
-   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
-   if (slot == NULL)
-     csi.index = (unsigned) ~0;
-   else
-     {
-       element = (cgraph_node_set_element) *slot;
-       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
- 		  == node);
-       csi.index = element->index;
-     }
-   csi.set = set;
- 
-   return csi;
- }
- 
- /* Dump content of SET to file F.  */
- 
- void
- dump_cgraph_node_set (FILE *f, cgraph_node_set set)
- {
-   cgraph_node_set_iterator iter;
- 
-   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
-     {
-       struct cgraph_node *node = csi_node (iter);
-       fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
-     }
-   fprintf (f, "\n");
- }
- 
- /* Dump content of SET to stderr.  */
- 
- DEBUG_FUNCTION void
- debug_cgraph_node_set (cgraph_node_set set)
- {
-   dump_cgraph_node_set (stderr, set);
- }
- 
- /* Hash a varpool node set element.  */
- 
- static hashval_t
- hash_varpool_node_set_element (const void *p)
- {
-   const_varpool_node_set_element element = (const_varpool_node_set_element) p;
-   return htab_hash_pointer (element->node);
- }
- 
- /* Compare two varpool node set elements.  */
- 
- static int
- eq_varpool_node_set_element (const void *p1, const void *p2)
- {
-   const_varpool_node_set_element e1 = (const_varpool_node_set_element) p1;
-   const_varpool_node_set_element e2 = (const_varpool_node_set_element) p2;
- 
-   return e1->node == e2->node;
- }
- 
- /* Create a new varpool node set.  */
- 
- varpool_node_set
- varpool_node_set_new (void)
- {
-   varpool_node_set new_node_set;
- 
-   new_node_set = ggc_alloc_varpool_node_set_def ();
-   new_node_set->hashtab = htab_create_ggc (10,
- 					   hash_varpool_node_set_element,
- 					   eq_varpool_node_set_element,
- 					   NULL);
-   new_node_set->nodes = NULL;
-   return new_node_set;
- }
- 
- /* Add varpool_node NODE to varpool_node_set SET.  */
- 
- void
- varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
- {
-   void **slot;
-   varpool_node_set_element element;
-   struct varpool_node_set_element_def dummy;
- 
-   dummy.node = node;
-   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
- 
-   if (*slot != HTAB_EMPTY_ENTRY)
-     {
-       element = (varpool_node_set_element) *slot;
-       gcc_assert (node == element->node
- 		  && (VEC_index (varpool_node_ptr, set->nodes, element->index)
- 		      == node));
-       return;
-     }
- 
-   /* Insert node into hash table.  */
-   element = ggc_alloc_varpool_node_set_element_def ();
-   element->node = node;
-   element->index = VEC_length (varpool_node_ptr, set->nodes);
-   *slot = element;
- 
-   /* Insert into node vector.  */
-   VEC_safe_push (varpool_node_ptr, gc, set->nodes, node);
- }
- 
- /* Remove varpool_node NODE from varpool_node_set SET.  */
- 
- void
- varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
- {
-   void **slot, **last_slot;
-   varpool_node_set_element element, last_element;
-   struct varpool_node *last_node;
-   struct varpool_node_set_element_def dummy;
- 
-   dummy.node = node;
-   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
-   if (slot == NULL)
-     return;
- 
-   element = (varpool_node_set_element) *slot;
-   gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
- 	      == node);
- 
-   /* Remove from vector. We do this by swapping node with the last element
-      of the vector.  */
-   last_node = VEC_pop (varpool_node_ptr, set->nodes);
-   if (last_node != node)
-     {
-       dummy.node = last_node;
-       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
-       last_element = (varpool_node_set_element) *last_slot;
-       gcc_assert (last_element);
- 
-       /* Move the last element to the original spot of NODE.  */
-       last_element->index = element->index;
-       VEC_replace (varpool_node_ptr, set->nodes, last_element->index,
- 		   last_node);
-     }
- 
-   /* Remove element from hash table.  */
-   htab_clear_slot (set->hashtab, slot);
-   ggc_free (element);
- }
- 
- /* Find NODE in SET and return an iterator to it if found.  A null iterator
-    is returned if NODE is not in SET.  */
- 
- varpool_node_set_iterator
- varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
- {
-   void **slot;
-   struct varpool_node_set_element_def dummy;
-   varpool_node_set_element element;
-   varpool_node_set_iterator vsi;
- 
-   dummy.node = node;
-   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
-   if (slot == NULL)
-     vsi.index = (unsigned) ~0;
-   else
-     {
-       element = (varpool_node_set_element) *slot;
-       gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
- 		  == node);
-       vsi.index = element->index;
-     }
-   vsi.set = set;
- 
-   return vsi;
- }
- 
- /* Dump content of SET to file F.  */
- 
- void
- dump_varpool_node_set (FILE *f, varpool_node_set set)
- {
-   varpool_node_set_iterator iter;
- 
-   for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
-     {
-       struct varpool_node *node = vsi_node (iter);
-       fprintf (f, " %s", varpool_node_name (node));
-     }
-   fprintf (f, "\n");
- }
- 
- /* Dump content of SET to stderr.  */
- 
- DEBUG_FUNCTION void
- debug_varpool_node_set (varpool_node_set set)
- {
-   dump_varpool_node_set (stderr, set);
- }
- 
  
  /* Simple ipa profile pass propagating frequencies across the callgraph.  */
  
--- 1047,1052 ----
Index: lto/lto.c
===================================================================
*** lto/lto.c	(revision 173301)
--- lto/lto.c	(working copy)
*************** free_section_data (struct lto_file_decl_
*** 1127,1145 ****
  
  /* Structure describing ltrans partitions.  */
  
! struct GTY (()) ltrans_partition_def
  {
    cgraph_node_set cgraph_set;
    varpool_node_set varpool_set;
!   const char * GTY ((skip)) name;
    int insns;
  };
  
  typedef struct ltrans_partition_def *ltrans_partition;
  DEF_VEC_P(ltrans_partition);
! DEF_VEC_ALLOC_P(ltrans_partition,gc);
  
! static GTY (()) VEC(ltrans_partition, gc) *ltrans_partitions;
  
  static void add_cgraph_node_to_partition (ltrans_partition part, struct cgraph_node *node);
  static void add_varpool_node_to_partition (ltrans_partition part, struct varpool_node *vnode);
--- 1127,1145 ----
  
  /* Structure describing ltrans partitions.  */
  
! struct ltrans_partition_def
  {
    cgraph_node_set cgraph_set;
    varpool_node_set varpool_set;
!   const char * name;
    int insns;
  };
  
  typedef struct ltrans_partition_def *ltrans_partition;
  DEF_VEC_P(ltrans_partition);
! DEF_VEC_ALLOC_P(ltrans_partition,heap);
  
! static VEC(ltrans_partition, heap) *ltrans_partitions;
  
  static void add_cgraph_node_to_partition (ltrans_partition part, struct cgraph_node *node);
  static void add_varpool_node_to_partition (ltrans_partition part, struct varpool_node *vnode);
*************** static void add_varpool_node_to_partitio
*** 1148,1162 ****
  static ltrans_partition
  new_partition (const char *name)
  {
!   ltrans_partition part = ggc_alloc_ltrans_partition_def ();
    part->cgraph_set = cgraph_node_set_new ();
    part->varpool_set = varpool_node_set_new ();
    part->name = name;
    part->insns = 0;
!   VEC_safe_push (ltrans_partition, gc, ltrans_partitions, part);
    return part;
  }
  
  /* See all references that go to comdat objects and bring them into partition too.  */
  static void
  add_references_to_partition (ltrans_partition part, struct ipa_ref_list *refs)
--- 1148,1176 ----
  static ltrans_partition
  new_partition (const char *name)
  {
!   ltrans_partition part = XCNEW (struct ltrans_partition_def);
    part->cgraph_set = cgraph_node_set_new ();
    part->varpool_set = varpool_node_set_new ();
    part->name = name;
    part->insns = 0;
!   VEC_safe_push (ltrans_partition, heap, ltrans_partitions, part);
    return part;
  }
  
+ /* Free all memory used by ltrans partitions vector.   */
+ static void
+ free_ltrans_partitions ()
+ {
+   unsigned int idx;
+   ltrans_partition part;
+   for (idx = 0; VEC_iterate (ltrans_partition, ltrans_partitions, idx, part); idx++)
+     {
+       free_cgraph_node_set (part->cgraph-set);
+       free (part);
+     }
+   VEC_free (latrans_partition, heap, ltrans_partitions);
+ }
+ 
  /* See all references that go to comdat objects and bring them into partition too.  */
  static void
  add_references_to_partition (ltrans_partition part, struct ipa_ref_list *refs)
*************** lto_wpa_write_files (void)
*** 1977,1982 ****
--- 1990,1997 ----
    if (fclose (ltrans_output_list_stream))
      fatal_error ("closing LTRANS output list %s: %m", ltrans_output_list);
  
+   free_ltrans_partitions();
+ 
    timevar_pop (TV_WHOPR_WPA_IO);
  }
  
Index: passes.c
===================================================================
*** passes.c	(revision 173301)
--- passes.c	(working copy)
*************** ipa_write_summaries (void)
*** 1729,1736 ****
    ipa_write_summaries_1 (set, vset);
  
    free (order);
!   ggc_free (set);
!   ggc_free (vset);
  }
  
  /* Same as execute_pass_list but assume that subpasses of IPA passes
--- 1729,1736 ----
    ipa_write_summaries_1 (set, vset);
  
    free (order);
!   free_cgraph_node_set (set);
!   free_varpool_node_set (vset);
  }
  
  /* Same as execute_pass_list but assume that subpasses of IPA passes

Re: Move cgraph_node_set and varpool_node_set out of GGC and make them use pointer_map

[Richard Guenther]

On Tue, 3 May 2011, Jan Hubicka wrote:

> Hi,
> I always considered the cgrpah_node_set/varpool_node_set to be overengineered
> but they also turned out to be quite ineffective since we do quite a lot of
> queries into them during stremaing out.
> 
> This patch moves them to pointer_map, like I did for streamer cache.  While
> doing so I needed to get the structure out of GGC memory since pointer_map is
> not ggc firendly. This is not a deal at all, because the sets can only point to
> live cgraph/varpool entries anyway. Pointing to removed ones would lead to
> spectacular failures in any case.
> 
> Bootstrapped/regtested x86_64-linux, OK?

Umm, I wonder why ...

> + cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
> + {
> +   void **slot;
> + 
> +   slot = pointer_map_insert (set->map, node);
> + 
> +   if (*slot)
> +     {
> +       int index = (size_t) *slot - 1;
> +       gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
> + 		           == node));
> +       return;
> +     }
> + 
> +   *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
> + 
> +   /* Insert into node vector.  */
> +   VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);

We have both a vector and a pointer-map.  Why not simply use a
pointer-map only?!  I see this may need more re-structuring, eventually
adding an iterator interface to pointer-sets/maps (which would be
nice anyway).

It also makes me think again that why do we have both a cgraph
and a varpool set ... at least when you now deal with a non-GC
data structure you could as well use a vector of void * and
provide macros doing the casting for you, unifying the implementation
itself.

Well, I suppose most of that can be done as a followup (when
eventually the symtab arrives and varpool and cgraph nodes merge anyway).

Thus, ok for now.

Thanks,
Richard.

Re: Move cgraph_node_set and varpool_node_set out of GGC and make them use pointer_map

[Jan Hubicka]

> 
> We have both a vector and a pointer-map.  Why not simply use a
> pointer-map only?!  I see this may need more re-structuring, eventually

Well, pointer-maps would be randomly ordered (sensitive to pointer values)
and thus we would give different .o files depending on memory layout.
But yes, combination of hashtable and array is bit funny. I was considering
using simple bitmaps but given that the sets might be large and we do
quite many queries, I concluded that it might lead to problems with O(n)
lookup times in our bitmap structure.

The problem of frequent lookups is actually problem with fact that
ipa-reference output routines are quadratic in computing the boundary.
Something I will fix later, too.

Still replacing htab here seems like obvious improvement. pointer-map looks
even prettier and it should be good enough for any future use we can come up in
WHOPR.  Unlike the type merging and streamer cache, those sets are relatively
small.

> adding an iterator interface to pointer-sets/maps (which would be
> nice anyway).
> 
> It also makes me think again that why do we have both a cgraph
> and a varpool set ... at least when you now deal with a non-GC
> data structure you could as well use a vector of void * and
> provide macros doing the casting for you, unifying the implementation
> itself.

I would deffer this to symtab patches that will unify both sets into single
structure.
> 
> Well, I suppose most of that can be done as a followup (when
> eventually the symtab arrives and varpool and cgraph nodes merge anyway).
> 
> Thus, ok for now.

Thanks!
Honza
> 
> Thanks,
> Richard.

RE: Move cgraph_node_set and varpool_node_set out of GGC and make them use pointer_map

[Ian Bolton]

> Hi,
> I always considered the cgrpah_node_set/varpool_node_set to be
> overengineered
> but they also turned out to be quite ineffective since we do quite a
> lot of
> queries into them during stremaing out.
> 
> This patch moves them to pointer_map, like I did for streamer cache.
> While
> doing so I needed to get the structure out of GGC memory since
> pointer_map is
> not ggc firendly. This is not a deal at all, because the sets can only
> point to
> live cgraph/varpool entries anyway. Pointing to removed ones would lead
> to
> spectacular failures in any case.
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> Honza
> 
> 	* cgraph.h (cgraph_node_set_def, varpool_node_set_def): Move out
> of GTY;
> 	replace hash by pointer map.
> 	(cgraph_node_set_element_def, cgraph_node_set_element,
> 	const_cgraph_node_set_element, varpool_node_set_element_def,
> 	varpool_node_set_element, const_varpool_node_set_element):
> Remove.
> 	(free_cgraph_node_set, free_varpool_node_set): New function.
> 	(cgraph_node_set_size, varpool_node_set_size): Use vector size.
> 	* tree-emutls.c: Free varpool node set.
> 	* ipa-utils.c (cgraph_node_set_new, cgraph_node_set_add,
> 	cgraph_node_set_remove, cgraph_node_set_find,
> dump_cgraph_node_set,
> 	debug_cgraph_node_set, free_cgraph_node_set,
> varpool_node_set_new,
> 	varpool_node_set_add, varpool_node_set_remove,
> varpool_node_set_find,
> 	dump_varpool_node_set, free_varpool_node_set,
> debug_varpool_node_set):
> 	Move here from ipa.c; implement using pointer_map
> 	* ipa.c (cgraph_node_set_new, cgraph_node_set_add,
> 	cgraph_node_set_remove, cgraph_node_set_find,
> dump_cgraph_node_set,
> 	debug_cgraph_node_set, varpool_node_set_new,
> 	varpool_node_set_add, varpool_node_set_remove,
> varpool_node_set_find,
> 	dump_varpool_node_set, debug_varpool_node_set):
> 	Move to ipa-uitls.c.
> 	* lto/lto.c (ltrans_partition_def): Remove GTY annotations.
> 	(ltrans_partitions): Move to heap.
> 	(new_partition): Update.
> 	(free_ltrans_partitions): New function.
> 	(lto_wpa_write_files): Use it.
> 	* passes.c (ipa_write_summaries): Update.

This causes cross and native build of ARM Linux toolchain to fail:

gcc -c   -g -O2 -DIN_GCC -DCROSS_DIRECTORY_STRUCTURE  -W -Wall -Wwrite-
strings -Wcast-qual -Wstrict-prototypes -Wmissing-prototypes -Wmissing-
format-attribute -Wold-style-definition -Wc++-compat -fno-common  -
DHAVE_CONFIG_H -I. -Ilto -
I/work/source/gcc -
I/work/source/gcc/lto -
I/work/source/gcc/../include -
I/work/source/gcc/../libcpp/include -
I/work/source/gcc/../libdecnumber -
I/work/source/gcc/../libdecnumber/dpd
-I../libdecnumber
/work/source/gcc/lto/lto.c -o
lto/lto.o
/work/source/gcc/lto/lto.c:1163:
warning: function declaration isn't a prototype
/work/source/gcc/lto/lto.c: In
function 'free_ltrans_partitions':
/work/source/gcc/lto/lto.c:1163:
warning: old-style function definition
/work/source/gcc/lto/lto.c:1168:
error: 'struct ltrans_partition_def' has no member named 'cgraph'
/work/source/gcc/lto/lto.c:1168:
error: 'set' undeclared (first use in this function)
/work/source/gcc/lto/lto.c:1168:
error: (Each undeclared identifier is reported only once
/work/source/gcc/lto/lto.c:1168:
error: for each function it appears in.)
/work/source/gcc/lto/lto.c:1171:
warning: implicit declaration of function
'VEC_latrans_partition_heap_free'
make[2]: *** [lto/lto.o] Error 1
make[2]: *** Waiting for unfinished jobs....
rm gcov.pod gfdl.pod cpp.pod fsf-funding.pod gcc.pod
make[2]: Leaving directory `/work/cross-build/trunk-r173334-
thumb/arm-none-linux-gnueabi/obj/gcc1/gcc'
make[1]: *** [all-gcc] Error 2
make[1]: Leaving directory `/work/cross-build/trunk-r173334-
thumb/arm-none-linux-gnueabi/obj/gcc1'
make: *** [all] Error 2
+ exit

But I see you fixed it up soon after (r173336), so no action is
required now, but I figured it was worth letting people know anyway.

Cheers,
Ian