[RFC, PATCH 3/n] IPA C++ refactoring

[Martin Liška <mliska at suse dot cz>]

Hello,
   in the following patch, I would like to introduce a new template class (indexed_set) that can replace many cgraph_node_set and varpool_node_set related functions.

Bootstrapped on x86_64-pc-linux-gnu, no regression observed.

Thank you,
Martin

Attachment: symbol-set.changelog
Description: Text document

diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index d8651e2..3de76ed 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -27,6 +27,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "basic-block.h"
 #include "function.h"
 #include "ipa-ref.h"
+#include "indexed-set.h"
 
 /* Symbol table consists of functions and variables.
    TODO: add labels and CONST_DECLs.  */
@@ -1200,41 +1201,6 @@ public:
   unsigned calls_comdat_local : 1;
 };
 
-/* 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 *> nodes;
-};
-
-typedef cgraph_node_set_def *cgraph_node_set;
-typedef struct varpool_node_set_def *varpool_node_set;
-
-class varpool_node;
-
-/* 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 *> nodes;
-};
-
-/* Iterator structure for cgraph node sets.  */
-struct cgraph_node_set_iterator
-{
-  cgraph_node_set set;
-  unsigned index;
-};
-
-/* Iterator structure for varpool node sets.  */
-struct varpool_node_set_iterator
-{
-  varpool_node_set set;
-  unsigned index;
-};
-
 /* Structure containing additional information about an indirect call.  */
 
 struct GTY(()) cgraph_indirect_call_info
@@ -1509,7 +1475,7 @@ enum cgraph_state
 };
 extern enum cgraph_state cgraph_state;
 extern bool cgraph_function_flags_ready;
-extern cgraph_node_set cgraph_new_nodes;
+extern vec<cgraph_node *> cgraph_new_nodes;
 
 extern GTY(()) struct asm_node *asm_nodes;
 extern GTY(()) int symtab_order;
@@ -1615,24 +1581,7 @@ void record_references_in_initializer (tree, bool);
 
 /* In ipa.c  */
 bool symtab_remove_unreachable_nodes (bool, FILE *);
-cgraph_node_set cgraph_node_set_new (void);
-cgraph_node_set_iterator cgraph_node_set_find (cgraph_node_set,
-					       cgraph_node *);
-void cgraph_node_set_add (cgraph_node_set, cgraph_node *);
-void cgraph_node_set_remove (cgraph_node_set, 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);
 void cgraph_build_static_cdtor (char which, tree body, int priority);
-
-varpool_node_set varpool_node_set_new (void);
-varpool_node_set_iterator varpool_node_set_find (varpool_node_set,
-						 varpool_node *);
-void varpool_node_set_add (varpool_node_set, varpool_node *);
-void varpool_node_set_remove (varpool_node_set, 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);
 
 /* In predict.c  */
@@ -1948,93 +1897,6 @@ cgraph_next_function_with_gimple_body (cgraph_node *node)
 /* Create a new static variable of type TYPE.  */
 tree add_new_static_var (tree type);
 
-/* Return true if iterator CSI points to nothing.  */
-static inline bool
-csi_end_p (cgraph_node_set_iterator csi)
-{
-  return csi.index >= csi.set->nodes.length ();
-}
-
-/* Advance iterator CSI.  */
-static inline void
-csi_next (cgraph_node_set_iterator *csi)
-{
-  csi->index++;
-}
-
-/* Return the node pointed to by CSI.  */
-static inline cgraph_node *
-csi_node (cgraph_node_set_iterator csi)
-{
-  return csi.set->nodes[csi.index];
-}
-
-/* Return an iterator to the first node in SET.  */
-static inline cgraph_node_set_iterator
-csi_start (cgraph_node_set set)
-{
-  cgraph_node_set_iterator csi;
-
-  csi.set = set;
-  csi.index = 0;
-  return csi;
-}
-
-/* Return true if SET contains NODE.  */
-static inline bool
-cgraph_node_in_set_p (cgraph_node *node, cgraph_node_set set)
-{
-  cgraph_node_set_iterator csi;
-  csi = cgraph_node_set_find (set, node);
-  return !csi_end_p (csi);
-}
-
-/* Return number of nodes in SET.  */
-static inline size_t
-cgraph_node_set_size (cgraph_node_set set)
-{
-  return set->nodes.length ();
-}
-
-/* Return true if iterator VSI points to nothing.  */
-static inline bool
-vsi_end_p (varpool_node_set_iterator vsi)
-{
-  return vsi.index >= vsi.set->nodes.length ();
-}
-
-/* Advance iterator VSI.  */
-static inline void
-vsi_next (varpool_node_set_iterator *vsi)
-{
-  vsi->index++;
-}
-
-/* Return the node pointed to by VSI.  */
-static inline varpool_node *
-vsi_node (varpool_node_set_iterator vsi)
-{
-  return vsi.set->nodes[vsi.index];
-}
-
-/* Return an iterator to the first node in SET.  */
-static inline varpool_node_set_iterator
-vsi_start (varpool_node_set set)
-{
-  varpool_node_set_iterator vsi;
-
-  vsi.set = set;
-  vsi.index = 0;
-  return vsi;
-}
-
-/* Return number of nodes in SET.  */
-static inline size_t
-varpool_node_set_size (varpool_node_set set)
-{
-  return set->nodes.length ();
-}
-
 /* Uniquize all constants that appear in memory.
    Each constant in memory thus far output is recorded
    in `const_desc_table'.  */
@@ -2052,20 +1914,6 @@ struct GTY(()) constant_descriptor_tree {
   hashval_t hash;
 };
 
-/* Return true if set is nonempty.  */
-static inline bool
-cgraph_node_set_nonempty_p (cgraph_node_set set)
-{
-  return !set->nodes.is_empty ();
-}
-
-/* Return true if set is nonempty.  */
-static inline bool
-varpool_node_set_nonempty_p (varpool_node_set set)
-{
-  return !set->nodes.is_empty ();
-}
-
 /* Return true when function is only called directly or it has alias.
    i.e. it is not externally visible, address was not taken and
    it is not used in any other non-standard way.  */
diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c
index 3080b9a..a33a171 100644
--- a/gcc/cgraphunit.c
+++ b/gcc/cgraphunit.c
@@ -211,11 +211,12 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-nested.h"
 #include "gimplify.h"
 #include "dbgcnt.h"
+#include "indexed-set.h"
 
 /* Queue of cgraph nodes scheduled to be added into cgraph.  This is a
    secondary queue used during optimization to accommodate passes that
    may generate new functions that need to be optimized and expanded.  */
-cgraph_node_set cgraph_new_nodes;
+vec<cgraph_node *> cgraph_new_nodes;
 
 static void expand_all_functions (void);
 static void mark_functions_to_output (void);
@@ -300,17 +301,16 @@ void
 cgraph_process_new_functions (void)
 {
   tree fndecl;
-  struct cgraph_node *node;
-  cgraph_node_set_iterator csi;
 
-  if (!cgraph_new_nodes)
+  if (!cgraph_new_nodes.exists ())
     return;
+
   handle_alias_pairs ();
   /*  Note that this queue may grow as its being processed, as the new
       functions may generate new ones.  */
-  for (csi = csi_start (cgraph_new_nodes); !csi_end_p (csi); csi_next (&csi))
+  for (unsigned i = 0; i < cgraph_new_nodes.length (); i++)
     {
-      node = csi_node (csi);
+      cgraph_node *node = cgraph_new_nodes[i];
       fndecl = node->decl;
       switch (cgraph_state)
 	{
@@ -357,8 +357,8 @@ cgraph_process_new_functions (void)
 	  break;
 	}
     }
-  free_cgraph_node_set (cgraph_new_nodes);
-  cgraph_new_nodes = NULL;
+
+    cgraph_new_nodes.release ();
 }
 
 /* As an GCC extension we allow redefinition of the function.  The
@@ -501,9 +501,9 @@ cgraph_node::add_new_function (tree fndecl, bool lowered)
 	node = cgraph_node::get_create (fndecl);
 	if (lowered)
 	  node->lowered = true;
-	if (!cgraph_new_nodes)
-	  cgraph_new_nodes = cgraph_node_set_new ();
-	cgraph_node_set_add (cgraph_new_nodes, node);
+	if (!cgraph_new_nodes.exists ())
+	  cgraph_new_nodes.create (4);
+	cgraph_new_nodes.safe_push (node);
         break;
 
       case CGRAPH_STATE_IPA:
@@ -529,9 +529,9 @@ cgraph_node::add_new_function (tree fndecl, bool lowered)
 	  }
 	if (lowered)
 	  node->lowered = true;
-	if (!cgraph_new_nodes)
-	  cgraph_new_nodes = cgraph_node_set_new ();
-	cgraph_node_set_add (cgraph_new_nodes, node);
+	if (!cgraph_new_nodes.exists ())
+	  cgraph_new_nodes.create (4);
+	cgraph_new_nodes.safe_push (node);
         break;
 
       case CGRAPH_STATE_FINISHED:
diff --git a/gcc/indexed-set.h b/gcc/indexed-set.h
new file mode 100644
index 0000000..a9b862a
--- /dev/null
+++ b/gcc/indexed-set.h
@@ -0,0 +1,125 @@
+/* A type-safe indexed hash set.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+   Contributed by Martin Liska
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+#ifndef indexed_hash_set_h
+#define indexed_hash_set_h
+
+#include "hash-map.h"
+#include "vec.h"
+
+template<typename T>
+class indexed_set
+{
+public:
+  class iterator
+  {
+  public:
+    iterator (const vec<T> *v, unsigned index) : m_index (index), m_vector (v) {};
+
+    inline T operator * ()
+    {
+      gcc_assert (m_index < m_vector->length ());
+
+      return (*m_vector)[m_index];
+    }
+
+    inline iterator &operator ++ ()
+    {
+      m_index++;
+      return *this;
+    }
+
+    bool operator != (const iterator &other) const
+    {
+      return m_vector != other.m_vector || m_index != other.m_index;
+    }
+
+    inline int
+    get_index (void) const
+    {
+      return m_index;
+    }
+
+  private:
+    unsigned m_index;
+    const vec <T> *m_vector;
+  };
+
+  /* Iterator to the start of data structure.  */
+
+  iterator begin () const
+  {
+    gcc_assert (!is_empty ());
+
+    iterator iter (&m_vector, 0);
+    return iter;
+  }
+
+  /* Iterator to the end of data structure.  */
+
+  iterator end () const
+  {
+    return iterator (&m_vector, m_vector.length ());
+  }
+
+  /* Add item V to data structure.  */
+
+  inline void
+  add (T v)
+  {
+    m_map.put (v, m_vector.length ());
+    m_vector.safe_push (v);
+  }
+
+  /* Return iterator for an item V.  */
+
+  inline iterator
+  find (T v)
+  {
+    int *item = m_map.get (v);
+    gcc_unreachable ();
+
+    return item ?  iterator (&m_vector, *item) : end ();
+  }
+
+  /* Return if the data structure is empty.  */
+
+  inline bool
+  is_empty (void) const
+  {
+    return m_vector.is_empty ();
+  }
+
+  /* Return number of items stored in data structure.  */
+
+  inline unsigned
+  length (void)
+  {
+    return m_vector.length ();
+  }
+
+
+private:
+  hash_map<T, int> m_map;
+  auto_vec<T> m_vector;
+};
+
+#endif
diff --git a/gcc/ipa-inline-transform.c b/gcc/ipa-inline-transform.c
index 5924140..2ddd029 100644
--- a/gcc/ipa-inline-transform.c
+++ b/gcc/ipa-inline-transform.c
@@ -96,7 +96,7 @@ can_remove_node_now_p_1 (struct cgraph_node *node)
 	  && !DECL_VIRTUAL_P (node->decl)
 	  /* During early inlining some unanalyzed cgraph nodes might be in the
 	     callgraph and they might reffer the function in question.  */
-	  && !cgraph_new_nodes);
+	  && !cgraph_new_nodes.exists ());
 }
 
 /* We are going to eliminate last direct call to NODE (or alias of it) via edge E.
diff --git a/gcc/ipa-utils.c b/gcc/ipa-utils.c
index 7810e55..f08debb 100644
--- a/gcc/ipa-utils.c
+++ b/gcc/ipa-utils.c
@@ -380,265 +380,6 @@ get_base_var (tree t)
   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.create (0);
-  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 ((set->nodes[index]
-		           == node));
-      return;
-    }
-
-  *slot = (void *)(size_t) (set->nodes.length () + 1);
-
-  /* Insert into node vector.  */
-  set->nodes.safe_push (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 (set->nodes[index]
-	      	       == node);
-
-  /* Remove from vector. We do this by swapping node with the last element
-     of the vector.  */
-  last_node = set->nodes.pop ();
-  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.  */
-      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", node->name (), node->order);
-    }
-  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)
-{
-  set->nodes.release ();
-  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.create (0);
-  return new_node_set;
-}
-
-
-/* Add varpool_node NODE to varpool_node_set SET.  */
-
-void
-varpool_node_set_add (varpool_node_set set, varpool_node *node)
-{
-  void **slot;
-
-  slot = pointer_map_insert (set->map, node);
-
-  if (*slot)
-    {
-      int index = (size_t) *slot - 1;
-      gcc_checking_assert ((set->nodes[index]
-		           == node));
-      return;
-    }
-
-  *slot = (void *)(size_t) (set->nodes.length () + 1);
-
-  /* Insert into node vector.  */
-  set->nodes.safe_push (node);
-}
-
-
-/* Remove varpool_node NODE from varpool_node_set SET.  */
-
-void
-varpool_node_set_remove (varpool_node_set set, varpool_node *node)
-{
-  void **slot, **last_slot;
-  int index;
-  varpool_node *last_node;
-
-  slot = pointer_map_contains (set->map, node);
-  if (slot == NULL || !*slot)
-    return;
-
-  index = (size_t) *slot - 1;
-  gcc_checking_assert (set->nodes[index]
-	      	       == node);
-
-  /* Remove from vector. We do this by swapping node with the last element
-     of the vector.  */
-  last_node = set->nodes.pop ();
-  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.  */
-      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, 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))
-    {
-      varpool_node *node = vsi_node (iter);
-      fprintf (f, " %s", node->name ());
-    }
-  fprintf (f, "\n");
-}
-
-
-/* Free varpool node set.  */
-
-void
-free_varpool_node_set (varpool_node_set set)
-{
-  set->nodes.release ();
-  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);
-}
-
-
 /* SRC and DST are going to be merged.  Take SRC's profile and merge it into
    DST so it is not going to be lost.  Destroy SRC's body on the way.  */
 
diff --git a/gcc/tree-emutls.c b/gcc/tree-emutls.c
index 89197c7..9c06aec 100644
--- a/gcc/tree-emutls.c
+++ b/gcc/tree-emutls.c
@@ -42,6 +42,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "target.h"
 #include "targhooks.h"
 #include "tree-iterator.h"
+#include "indexed-set.h"
 
 
 /* Whenever a target does not support thread-local storage (TLS) natively,
@@ -70,7 +71,7 @@ along with GCC; see the file COPYING3.  If not see
 /* These two vectors, once fully populated, are kept in lock-step so that
    the index of a TLS variable equals the index of its control variable in
    the other vector.  */
-static varpool_node_set tls_vars;
+static indexed_set<varpool_node *> tls_vars;
 static vec<varpool_node *> control_vars;
 
 /* For the current basic block, an SSA_NAME that has computed the address 
@@ -356,12 +357,9 @@ new_emutls_decl (tree decl, tree alias_of)
 static unsigned int
 emutls_index (tree decl)
 {
-  varpool_node_set_iterator i;
-  
-  i = varpool_node_set_find (tls_vars, varpool_node::get (decl));
-  gcc_assert (i.index != ~0u);
+  indexed_set <varpool_node *>::iterator i = tls_vars.find (varpool_node::get (decl));
 
-  return i.index;
+  return i.get_index ();
 }
 
 /* Look up the control variable for the TLS variable DECL.  */
@@ -744,38 +742,36 @@ ipa_lower_emutls (void)
   tree ctor_body = NULL;
   unsigned int i, n_tls;
 
-  tls_vars = varpool_node_set_new ();
-
   /* Examine all global variables for TLS variables.  */
   FOR_EACH_VARIABLE (var)
     if (DECL_THREAD_LOCAL_P (var->decl))
       {
 	gcc_checking_assert (TREE_STATIC (var->decl)
 			     || DECL_EXTERNAL (var->decl));
-	varpool_node_set_add (tls_vars, var);
+	tls_vars.add (var);
 	if (var->alias && var->definition)
-	  varpool_node_set_add (tls_vars, var->ultimate_alias_target ());
+	  tls_vars.add (var->ultimate_alias_target ());
       }
 
   /* If we found no TLS variables, then there is no further work to do.  */
-  if (!tls_vars->nodes.exists ())
+  if (tls_vars.is_empty ())
     {
-      tls_vars = NULL;
       if (dump_file)
 	fprintf (dump_file, "No TLS variables found.\n");
       return 0;
     }
 
   /* Allocate the on-the-side arrays that share indicies with the TLS vars.  */
-  n_tls = tls_vars->nodes.length ();
+  n_tls = tls_vars.length ();
   control_vars.create (n_tls);
   access_vars.create (n_tls);
   access_vars.safe_grow_cleared (n_tls);
 
   /* Create the control variables for each TLS variable.  */
-  FOR_EACH_VEC_ELT (tls_vars->nodes, i, var)
+  for (indexed_set <varpool_node *>::iterator it = tls_vars.begin ();
+       it != tls_vars.end (); ++it)
     {
-      var = tls_vars->nodes[i];
+      var = *it;
 
       if (var->alias && !var->analyzed)
 	any_aliases = true;
@@ -806,7 +802,6 @@ ipa_lower_emutls (void)
 
   control_vars.release ();
   access_vars.release ();
-  free_varpool_node_set (tls_vars);
 
   return 0;
 }