[RFC, PATCH]: Introduction of callgraph annotation class

[RFC, PATCH]: Introduction of callgraph annotation class

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 1139 bytes --]

Hello.

Following patch introduces a new class called callgraph_annotation. Idea behind the patch is to provide a generic interface one can use to register custom info related to a cgraph_node. As you know, symbol_table provides hooks for creation, deletion and duplication of a cgraph_node. If you have a pass, you need to handle all these hooks and store custom data in your data structure.

As an example, after discussion with Martin, I chose usage in ipa-prop.h:

data structure:
vec<ipa_node_params> ipa_node_params_vector

if the pass handles an event, following chunk is executed:
if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
     ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);

The problem is that you can have sparse UIDs of cgraph_nodes and every time you have to allocate a vector of size equal to cgraph_max_uid.

As a replacement, I implemented first version of cgraph_annotation that internally uses hash_map<cgraph_unique_identifier, T>.
Every time a node is deleted, we remove corresponding data associated to the node.

What do you think about it?

Thank you,
Martin

[-- Attachment #2: cgraph-annotation-1.patch --]
[-- Type: text/x-patch, Size: 23802 bytes --]

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 04ce0c0..bf34c96 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1171,6 +1171,7 @@ OBJS = \
 	cfgrtl.o \
 	symtab.o \
 	cgraph.o \
+	annotation.o \
 	cgraphbuild.o \
 	cgraphunit.o \
 	cgraphclones.o \
diff --git a/gcc/annotation.c b/gcc/annotation.c
new file mode 100644
index 0000000..a8b6053
--- /dev/null
+++ b/gcc/annotation.c
@@ -0,0 +1 @@
+#include "annotation.h"
diff --git a/gcc/annotation.h b/gcc/annotation.h
new file mode 100644
index 0000000..7520677
--- /dev/null
+++ b/gcc/annotation.h
@@ -0,0 +1,285 @@
+/* Annotations handling code.
+   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 GCC_ANNOTATION_H
+#define GCC_ANNOTATION_H
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "varasm.h"
+#include "calls.h"
+#include "print-tree.h"
+#include "tree-inline.h"
+#include "langhooks.h"
+#include "hashtab.h"
+#include "toplev.h"
+#include "flags.h"
+#include "debug.h"
+#include "target.h"
+#include "cgraph.h"
+#include "hash-map.h"
+
+#define ANNOTATION_DELETED_VALUE -1
+#define ANNOTATION_EMPTY_VALUE 0
+
+struct annotation_hashmap_traits: default_hashmap_traits
+{
+  static inline
+  hashval_t hash (const int v)
+  {
+    return (hashval_t)v;
+  }
+
+  template<typename T>
+  static inline
+  bool is_deleted (T &e)
+  {
+    return e.m_key == ANNOTATION_DELETED_VALUE;
+  }
+
+  template<typename T>
+  static inline
+  bool is_empty (T &e)
+  {
+    return e.m_key == ANNOTATION_EMPTY_VALUE;
+  }
+
+  template<typename T>
+  static inline
+  void mark_deleted (T &e)
+  {
+    e.m_key = ANNOTATION_DELETED_VALUE;
+  }
+
+  template<typename T>
+  static inline
+  void mark_empty (T &e)
+  {
+    e.m_key = ANNOTATION_EMPTY_VALUE;
+  }
+};
+
+template <class T>
+class cgraph_annotation
+{
+public:
+  /* Default construction takes SYMTAB as an argument.  */
+  cgraph_annotation (symbol_table *symtab): m_symtab (symtab)
+  {
+    cgraph_node *node;
+
+    FOR_EACH_FUNCTION (node)
+    {
+      gcc_assert (node->annotation_uid > 0);
+      m_reverse_map.put (node, node->annotation_uid);
+    }
+
+    m_map = new  hash_map<int, T*, annotation_hashmap_traits>();
+
+    m_symtab_insertion_hook =
+      symtab->add_cgraph_insertion_hook
+      (cgraph_annotation::symtab_insertion, this);
+
+    m_symtab_removal_hook =
+      symtab->add_cgraph_removal_hook
+      (cgraph_annotation::symtab_removal, this);
+    m_symtab_duplication_hook =
+      symtab->add_cgraph_duplication_hook
+      (cgraph_annotation::symtab_duplication, this);
+
+  }
+
+  /* Destructor.  */
+  ~cgraph_annotation ()
+  {
+    m_symtab->remove_cgraph_insertion_hook (m_symtab_insertion_hook);
+    m_symtab->remove_cgraph_removal_hook (m_symtab_removal_hook);
+    m_symtab->remove_cgraph_duplication_hook (m_symtab_duplication_hook);
+
+    m_map->traverse <void *, cgraph_annotation::release> (NULL);
+  }
+
+  /* Traverses all annotations with a function F called with
+     ARG as argument.  */
+  template<typename Arg, bool (*f)(const T &, Arg)>
+  void traverse (Arg a) const
+  {
+    m_map->traverse <f> (a);
+  }
+
+  /* Function for registering insertion hook.  */
+  template <void (*f) (const cgraph_node *, T *)>
+  inline void add_insertion_hook (void)
+  {
+    m_insertion_hooks.safe_push (f);
+  }
+
+  /* Function for registering removal hook.  */
+  template <void (*f) (const cgraph_node *, T *)>
+  inline void add_removal_hook (void)
+  {
+    m_removal_hooks.safe_push (f);
+  }
+
+  /* Function for registering duplication hook.  */
+  template <void (*f) (const cgraph_node *, const cgraph_node *, T *, T *)>
+  inline void add_duplication_hook (void)
+  {
+    m_duplication_hooks.safe_push (f);
+  }
+
+  /* Getter for annotation callgraph ID.  */
+  inline T* get_or_add (int uid)
+  {
+    T **v = m_map->get (uid);
+    if (!v)
+      {
+	T *new_value = new T();
+	m_map->put (uid, new_value);
+
+	v = &new_value;
+      }
+
+    return *v;
+  }
+
+  /* Getter for annotation callgraph node pointer.  */
+  inline T *get_or_add (cgraph_node *node)
+  {
+    return get_or_add (node->annotation_uid);
+  }
+
+  /* Symbol insertion hook that is registered to symbol table.  */
+  static void symtab_insertion (cgraph_node *node, void *data)
+  {
+    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
+    annotation->call_insertion_hooks (node);
+  }
+
+  /* Symbol removal hook that is registered to symbol table.  */
+  static void symtab_removal (cgraph_node *node, void *data)
+  {
+    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
+    int *annotation_uid_ptr = annotation->m_reverse_map.get (node);
+
+    if (!annotation_uid_ptr)
+      return;
+
+    int annotation_uid = *annotation_uid_ptr;
+
+    T **v = annotation->m_map->get (annotation_uid);
+
+    if (v)
+      annotation->call_removal_hooks (node, *v);
+
+    annotation->m_reverse_map.remove (node);
+
+    if (annotation->m_map->get (annotation_uid))
+      annotation->m_map->remove (annotation_uid);
+
+  }
+
+  /* Symbol duplication hook that is registered to symbol table.  */
+  static void symtab_duplication (cgraph_node *node, cgraph_node *node2,
+				  void *data)
+  {
+    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
+    T **v = annotation->m_map->get (node->annotation_uid);
+
+    gcc_assert (node2->annotation_uid > 0);
+    annotation->m_reverse_map.put (node2, node2->annotation_uid);
+
+    if (v)
+      {
+	T *data = *v;
+	T *duplicate = new T();
+	annotation->m_map->put (node2->annotation_uid, duplicate);
+	annotation->call_duplication_hooks (node, node2, data);
+      }
+
+  }
+
+  /* Main annotation store, where annotation ID is used as key.  */
+  hash_map <int, T *, annotation_hashmap_traits> *m_map;
+
+  /* Inverse mapping structure used in cgraph deletion context.  */
+  hash_map <cgraph_node *, int> m_reverse_map;
+
+private:
+  /* Remove annotation for annotation UID.  */
+  inline void remove (int uid)
+  {
+    T *v = m_map->get (uid);
+
+    if (v)
+      m_map->erase (uid);
+  }
+
+  /* Annotation class release function called by traverse method.  */
+  static bool release (int const &, T * const &v, void *)
+  {
+    delete (v);
+    return true;
+  }
+
+  /* Call insertion hook for callgraph NODE.  */
+  inline void call_insertion_hooks (cgraph_node *node)
+  {
+    for (unsigned int i = 0; i < m_insertion_hooks.length (); i++)
+      m_insertion_hooks[i] (node, get_or_add (node));
+  }
+
+  /* Call removal hook for callgraph NODE.  */
+  inline void call_removal_hooks (cgraph_node *node, T *v)
+  {
+    for (unsigned int i = 0; i < m_removal_hooks.length (); i++)
+      m_removal_hooks[i] (node, v);
+  }
+
+  /* Call duplication hook for callgraph NODE.  */
+  inline void call_duplication_hooks (cgraph_node *node, cgraph_node *node2, T *v)
+  {
+    for (unsigned int i = 0; i < m_duplication_hooks.length (); i++)
+      m_duplication_hooks[i] (node, node2, v, get_or_add (node2));
+  }
+
+  /* List of symbol insertion hooks.  */
+  auto_vec <void (*) (cgraph_node *, T *)> m_insertion_hooks;
+  /* List of symbol removal hooks.  */
+  auto_vec <void (*) (cgraph_node *, T *)> m_removal_hooks;
+  /* List of symbol duplication hooks.  */
+  auto_vec <void (*) (const cgraph_node *, const cgraph_node *, T *, T *)>
+  m_duplication_hooks;
+
+  /* Internal annotation insertion hook pointer.  */
+  cgraph_node_hook_list *m_symtab_insertion_hook;
+  /* Internal annotation removal hook pointer.  */
+  cgraph_node_hook_list *m_symtab_removal_hook;
+  /* Internal annotation duplication hook pointer.  */
+  cgraph_2node_hook_list *m_symtab_duplication_hook;
+
+  /* Symbol table the annotation is registered to.  */
+  symbol_table *m_symtab;
+};
+
+#endif  /* GCC_ANNOTATION_H  */
diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index a5777c2..32a770a 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -1219,6 +1219,8 @@ public:
   int count_materialization_scale;
   /* Unique id of the node.  */
   int uid;
+  /* Annotation unique id of the node.  */
+  int annotation_uid;
   /* ID assigned by the profiling.  */
   unsigned int profile_id;
   /* Time profiler: first run of function.  */
@@ -1771,6 +1773,10 @@ public:
   friend class cgraph_node;
   friend class cgraph_edge;
 
+  symbol_table (): cgraph_max_annotation_uid (1)
+  {
+  }
+
   /* Initialize callgraph dump file.  */
   inline void
   initialize (void)
@@ -1972,6 +1978,7 @@ public:
 
   int cgraph_count;
   int cgraph_max_uid;
+  int cgraph_max_annotation_uid;
 
   int edges_count;
   int edges_max_uid;
@@ -2268,6 +2275,9 @@ symbol_table::create_empty (void)
 {
   cgraph_node *node = allocate_cgraph_symbol ();
 
+  gcc_assert (cgraph_max_annotation_uid);
+  node->annotation_uid = cgraph_max_annotation_uid++;
+
   node->type = SYMTAB_FUNCTION;
   node->frequency = NODE_FREQUENCY_NORMAL;
   node->count_materialization_scale = REG_BR_PROB_BASE;
diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c
index 38f56d2..e2576b3 100644
--- a/gcc/ipa-inline-analysis.c
+++ b/gcc/ipa-inline-analysis.c
@@ -895,7 +895,7 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
   if (known_binfos_ptr)
     known_binfos_ptr->create (0);
 
-  if (ipa_node_params_vector.exists ()
+  if (ipa_node_params_annotation
       && !e->call_stmt_cannot_inline_p
       && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
     {
@@ -1115,7 +1115,7 @@ inline_node_duplication_hook (struct cgraph_node *src,
 
   /* When there are any replacements in the function body, see if we can figure
      out that something was optimized out.  */
-  if (ipa_node_params_vector.exists () && dst->clone.tree_map)
+  if (ipa_node_params_annotation && dst->clone.tree_map)
     {
       vec<size_time_entry, va_gc> *entry = info->entry;
       /* Use SRC parm info since it may not be copied yet.  */
@@ -2462,7 +2462,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
       calculate_dominance_info (CDI_DOMINATORS);
       loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 
-      if (ipa_node_params_vector.exists ())
+      if (ipa_node_params_annotation)
 	{
 	  parms_info = IPA_NODE_REF (node);
 	  nonconstant_names.safe_grow_cleared
@@ -2610,7 +2610,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
 		  nonconstant_names[SSA_NAME_VERSION (gimple_call_lhs (stmt))]
 		    = false_p;
 		}
-	      if (ipa_node_params_vector.exists ())
+	      if (ipa_node_params_annotation)
 		{
 		  int count = gimple_call_num_args (stmt);
 		  int i;
@@ -3353,7 +3353,7 @@ static void
 remap_edge_change_prob (struct cgraph_edge *inlined_edge,
 			struct cgraph_edge *edge)
 {
-  if (ipa_node_params_vector.exists ())
+  if (ipa_node_params_annotation)
     {
       int i;
       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
@@ -3509,7 +3509,7 @@ inline_merge_summary (struct cgraph_edge *edge)
   else
     toplev_predicate = true_predicate ();
 
-  if (ipa_node_params_vector.exists () && callee_info->conds)
+  if (ipa_node_params_annotation && callee_info->conds)
     {
       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
       int count = ipa_get_cs_argument_count (args);
diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c
index 9ac1929..ad98467 100644
--- a/gcc/ipa-inline.c
+++ b/gcc/ipa-inline.c
@@ -2408,7 +2408,7 @@ pass_early_inline::execute (function *fun)
      it.  This may confuse ourself when early inliner decide to inline call to
      function clone, because function clones don't have parameter list in
      ipa-prop matching their signature.  */
-  if (ipa_node_params_vector.exists ())
+  if (ipa_node_params_annotation)
     return 0;
 
 #ifdef ENABLE_CHECKING
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index 62db327..743d9ff 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -115,7 +115,8 @@ struct func_body_info
   unsigned int aa_walked;
 };
 
-/* Vector where the parameter infos are actually stored. */
+/* Callgraph annotation where the parameter infos are actually stored. */
+cgraph_annotation <struct ipa_node_params> *ipa_node_params_annotation = NULL;
 vec<ipa_node_params> ipa_node_params_vector;
 /* Vector of known aggregate values in cloned nodes.  */
 vec<ipa_agg_replacement_value_p, va_gc> *ipa_node_agg_replacements;
@@ -124,9 +125,7 @@ vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
 
 /* Holders of ipa cgraph hooks: */
 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
-static struct cgraph_node_hook_list *node_removal_hook_holder;
 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
-static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 static struct cgraph_node_hook_list *function_insertion_hook_holder;
 
 /* Description of a reference to an IPA constant.  */
@@ -3554,7 +3553,7 @@ ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
   bool changed;
   /* Do nothing if the preparation phase has not been carried out yet
      (i.e. during early inlining).  */
-  if (!ipa_node_params_vector.exists ())
+  if (!ipa_node_params_annotation)
     return false;
   gcc_assert (ipa_edge_args_vector);
 
@@ -3594,15 +3593,21 @@ ipa_free_all_edge_args (void)
 /* Frees all dynamically allocated structures that the param info points
    to.  */
 
-void
-ipa_free_node_params_substructures (struct ipa_node_params *info)
+ipa_node_params::~ipa_node_params ()
 {
-  info->descriptors.release ();
-  free (info->lattices);
+  descriptors.release ();
+  free (lattices);
   /* Lattice values and their sources are deallocated with their alocation
      pool.  */
-  info->known_vals.release ();
-  memset (info, 0, sizeof (*info));
+  known_vals.release ();
+
+  lattices = NULL;
+  ipcp_orig_node = NULL;
+  analysis_done = 0;
+  node_enqueued = 0;
+  do_clone_for_all_contexts = 0;
+  is_all_contexts_clone = 0;
+  node_dead = 0;
 }
 
 /* Free all ipa_node_params structures.  */
@@ -3610,11 +3615,8 @@ ipa_free_node_params_substructures (struct ipa_node_params *info)
 void
 ipa_free_all_node_params (void)
 {
-  int i;
-  struct ipa_node_params *info;
-
-  FOR_EACH_VEC_ELT (ipa_node_params_vector, i, info)
-    ipa_free_node_params_substructures (info);
+  delete ipa_node_params_annotation;
+  ipa_node_params_annotation = NULL;
 
   ipa_node_params_vector.release ();
 }
@@ -3622,7 +3624,7 @@ ipa_free_all_node_params (void)
 /* Set the aggregate replacements of NODE to be AGGVALS.  */
 
 void
-ipa_set_node_agg_value_chain (struct cgraph_node *node,
+ipa_set_node_agg_value_chain (const struct cgraph_node *node,
 			      struct ipa_agg_replacement_value *aggvals)
 {
   if (vec_safe_length (ipa_node_agg_replacements)
@@ -3663,18 +3665,6 @@ ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
 }
 
-/* Hook that is called by cgraph.c when a node is removed.  */
-
-static void
-ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
-{
-  /* During IPA-CP updating we can be called on not-yet analyze clones.  */
-  if (ipa_node_params_vector.length () > (unsigned)node->uid)
-    ipa_free_node_params_substructures (IPA_NODE_REF (node));
-  if (vec_safe_length (ipa_node_agg_replacements) > (unsigned)node->uid)
-    (*ipa_node_agg_replacements)[(unsigned)node->uid] = NULL;
-}
-
 /* Hook that is called by cgraph.c when an edge is duplicated.  */
 
 static void
@@ -3779,18 +3769,22 @@ ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
     }
 }
 
-/* Hook that is called by cgraph.c when a node is duplicated.  */
+/* Analyze newly added function into callgraph.  */
 
 static void
-ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
-			   ATTRIBUTE_UNUSED void *data)
+ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 {
-  struct ipa_node_params *old_info, *new_info;
-  struct ipa_agg_replacement_value *old_av, *new_av;
+  if (node->has_gimple_body_p ())
+    ipa_analyze_node (node);
+}
 
-  ipa_check_create_node_params ();
-  old_info = IPA_NODE_REF (src);
-  new_info = IPA_NODE_REF (dst);
+/* Hook that is called by cgraph.c when a node is duplicated.  */
+
+void
+ipa_node_duplication_hook (const struct cgraph_node *src, const struct cgraph_node *dst,
+                          struct ipa_node_params *old_info, struct ipa_node_params *new_info)
+{
+  struct ipa_agg_replacement_value *old_av, *new_av;
 
   new_info->descriptors = old_info->descriptors.copy ();
   new_info->lattices = NULL;
@@ -3817,33 +3811,19 @@ ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
   ipa_set_node_agg_value_chain (dst, new_av);
 }
 
-
-/* Analyze newly added function into callgraph.  */
-
-static void
-ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
-{
-  if (node->has_gimple_body_p ())
-    ipa_analyze_node (node);
-}
-
 /* Register our cgraph hooks if they are not already there.  */
 
 void
 ipa_register_cgraph_hooks (void)
 {
+  ipa_check_create_node_params ();
+
   if (!edge_removal_hook_holder)
     edge_removal_hook_holder =
       symtab->add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
-  if (!node_removal_hook_holder)
-    node_removal_hook_holder =
-      symtab->add_cgraph_removal_hook (&ipa_node_removal_hook, NULL);
   if (!edge_duplication_hook_holder)
     edge_duplication_hook_holder =
       symtab->add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
-  if (!node_duplication_hook_holder)
-    node_duplication_hook_holder =
-      symtab->add_cgraph_duplication_hook (&ipa_node_duplication_hook, NULL);
   function_insertion_hook_holder =
       symtab->add_cgraph_insertion_hook (&ipa_add_new_function, NULL);
 }
@@ -3855,12 +3835,8 @@ ipa_unregister_cgraph_hooks (void)
 {
   symtab->remove_edge_removal_hook (edge_removal_hook_holder);
   edge_removal_hook_holder = NULL;
-  symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
-  node_removal_hook_holder = NULL;
   symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
   edge_duplication_hook_holder = NULL;
-  symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
-  node_duplication_hook_holder = NULL;
   symtab->remove_cgraph_insertion_hook (function_insertion_hook_holder);
   function_insertion_hook_holder = NULL;
 }
@@ -5030,8 +5006,7 @@ ipa_prop_write_jump_functions (void)
   lto_symtab_encoder_iterator lsei;
   lto_symtab_encoder_t encoder;
 
-
-  if (!ipa_node_params_vector.exists ())
+  if (!ipa_node_params_annotation)
     return;
 
   ob = create_output_block (LTO_section_jump_functions);
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index 7a06af9..6a3772d 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "vec.h"
 #include "cgraph.h"
 #include "alloc-pool.h"
+#include "annotation.h"
 
 /* The following definitions and interfaces are used by
    interprocedural analyses or parameters.  */
@@ -359,6 +360,8 @@ struct ipcp_lattice;
 
 struct ipa_node_params
 {
+  ~ipa_node_params ();
+
   /* Information about individual formal parameters that are gathered when
      summaries are generated. */
   vec<ipa_param_descriptor> descriptors;
@@ -473,7 +476,7 @@ struct GTY(()) ipa_agg_replacement_value
 
 typedef struct ipa_agg_replacement_value *ipa_agg_replacement_value_p;
 
-void ipa_set_node_agg_value_chain (struct cgraph_node *node,
+void ipa_set_node_agg_value_chain (const struct cgraph_node *node,
 				   struct ipa_agg_replacement_value *aggvals);
 
 /* ipa_edge_args stores information related to a callsite and particularly its
@@ -519,7 +522,7 @@ ipa_get_ith_polymorhic_call_context (struct ipa_edge_args *args, int i)
 /* Types of vectors holding the infos.  */
 
 /* Vector where the parameter infos are actually stored. */
-extern vec<ipa_node_params> ipa_node_params_vector;
+extern cgraph_annotation <ipa_node_params> *ipa_node_params_annotation;
 /* Vector of known aggregate values in cloned nodes.  */
 extern GTY(()) vec<ipa_agg_replacement_value_p, va_gc> *ipa_node_agg_replacements;
 /* Vector where the parameter infos are actually stored. */
@@ -527,7 +530,7 @@ extern GTY(()) vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
 
 /* Return the associated parameter/argument info corresponding to the given
    node/edge.  */
-#define IPA_NODE_REF(NODE) (&ipa_node_params_vector[(NODE)->uid])
+#define IPA_NODE_REF(NODE) (ipa_node_params_annotation->get_or_add (NODE))
 #define IPA_EDGE_REF(EDGE) (&(*ipa_edge_args_vector)[(EDGE)->uid])
 /* This macro checks validity of index returned by
    ipa_get_param_decl_index function.  */
@@ -537,11 +540,15 @@ extern GTY(()) vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
 void ipa_create_all_node_params (void);
 void ipa_create_all_edge_args (void);
 void ipa_free_edge_args_substructures (struct ipa_edge_args *);
-void ipa_free_node_params_substructures (struct ipa_node_params *);
 void ipa_free_all_node_params (void);
 void ipa_free_all_edge_args (void);
 void ipa_free_all_structures_after_ipa_cp (void);
 void ipa_free_all_structures_after_iinln (void);
+void  ipa_node_duplication_hook (const struct cgraph_node *src,
+				 const struct cgraph_node *dst,
+				 struct ipa_node_params *old_info,
+				 struct ipa_node_params *new_info);
+
 void ipa_register_cgraph_hooks (void);
 int count_formal_params (tree fndecl);
 
@@ -551,11 +558,11 @@ int count_formal_params (tree fndecl);
 static inline void
 ipa_check_create_node_params (void)
 {
-  if (!ipa_node_params_vector.exists ())
-    ipa_node_params_vector.create (symtab->cgraph_max_uid);
-
-  if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
-    ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
+  if (!ipa_node_params_annotation)
+    {
+      ipa_node_params_annotation = new cgraph_annotation <ipa_node_params> (symtab);
+      ipa_node_params_annotation->add_duplication_hook <ipa_node_duplication_hook> ();
+    }
 }
 
 /* This function ensures the array of edge arguments infos is big enough to
@@ -582,7 +589,7 @@ ipa_edge_args_info_available_for_edge_p (struct cgraph_edge *edge)
 /* Return the aggregate replacements for NODE, if there are any.  */
 
 static inline struct ipa_agg_replacement_value *
-ipa_get_agg_replacements_for_node (struct cgraph_node *node)
+ipa_get_agg_replacements_for_node (const struct cgraph_node *node)
 {
   if ((unsigned) node->uid >= vec_safe_length (ipa_node_agg_replacements))
     return NULL;
diff --git a/gcc/toplev.c b/gcc/toplev.c
index f7a5035..5e31ec2 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -1176,7 +1176,7 @@ general_init (const char *argv0)
   /* Create the singleton holder for global state.
      Doing so also creates the pass manager and with it the passes.  */
   g = new gcc::context ();
-  symtab = ggc_cleared_alloc <symbol_table> ();
+  symtab = new (ggc_cleared_alloc <symbol_table> ()) symbol_table ();
 
   statistics_early_init ();
   finish_params ();

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Richard Biener]

On Wed, Oct 15, 2014 at 6:26 PM, Martin Liška <mliska@suse.cz> wrote:
> Hello.
>
> Following patch introduces a new class called callgraph_annotation. Idea
> behind the patch is to provide a generic interface one can use to register
> custom info related to a cgraph_node. As you know, symbol_table provides
> hooks for creation, deletion and duplication of a cgraph_node. If you have a
> pass, you need to handle all these hooks and store custom data in your data
> structure.
>
> As an example, after discussion with Martin, I chose usage in ipa-prop.h:
>
> data structure:
> vec<ipa_node_params> ipa_node_params_vector
>
> if the pass handles an event, following chunk is executed:
> if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
>     ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
>
> The problem is that you can have sparse UIDs of cgraph_nodes and every time
> you have to allocate a vector of size equal to cgraph_max_uid.
>
> As a replacement, I implemented first version of cgraph_annotation that
> internally uses hash_map<cgraph_unique_identifier, T>.
> Every time a node is deleted, we remove corresponding data associated to the
> node.
>
> What do you think about it?

I don't like "generic annotation" facilities at all.  Would it be possible
to make cgraph UIDs not sparse?  (keep a free-list of cgraph nodes
with UID < cgraph_max_uid, only really free nodes at the end)
Using a different data structure than a vector indexed by cgraph UID
should also be easily possible (a map from UID to data, hash_map <int, T>).

Richard.

> Thank you,
> Martin

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Jan Hubicka]

> 
> I don't like "generic annotation" facilities at all.  Would it be possible

Why?

> to make cgraph UIDs not sparse?  (keep a free-list of cgraph nodes

cgraph nodes are already kept "dense" via freelist.  However in WPA you usually have a lot
of different nodes prior merging and unreachable code removal and very few afterwards,
the number of nodes grows again with inlining.

Depending on what you want to store for values, I guess either vector or hashtable is
good choice - if you want to keep data that needs to be duplicated per inline clone
you can rely on density. If you want data on few function bodies, you will likely use
hash...

Honza

> with UID < cgraph_max_uid, only really free nodes at the end)
> Using a different data structure than a vector indexed by cgraph UID
> should also be easily possible (a map from UID to data, hash_map <int, T>).
> 
> Richard.
> 
> > Thank you,
> > Martin

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Richard Biener]

On Thu, Oct 16, 2014 at 1:40 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> I don't like "generic annotation" facilities at all.  Would it be possible
>
> Why?

Because it's the way to hell if the IL has "magic" things only one
pass can understand.  It can't ever know if it may invalidate some
of that data.

Same reason why I dislike the ->aux pointers we have.  (even if they
are of course convenient)

>> to make cgraph UIDs not sparse?  (keep a free-list of cgraph nodes
>
> cgraph nodes are already kept "dense" via freelist.  However in WPA you usually have a lot
> of different nodes prior merging and unreachable code removal and very few afterwards,
> the number of nodes grows again with inlining.
>
> Depending on what you want to store for values, I guess either vector or hashtable is
> good choice - if you want to keep data that needs to be duplicated per inline clone
> you can rely on density. If you want data on few function bodies, you will likely use
> hash...
>
> Honza
>
>> with UID < cgraph_max_uid, only really free nodes at the end)
>> Using a different data structure than a vector indexed by cgraph UID
>> should also be easily possible (a map from UID to data, hash_map <int, T>).
>>
>> Richard.
>>
>> > Thank you,
>> > Martin

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Jan Hubicka]

> On Thu, Oct 16, 2014 at 1:40 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >>
> >> I don't like "generic annotation" facilities at all.  Would it be possible
> >
> > Why?
> 
> Because it's the way to hell if the IL has "magic" things only one
> pass can understand.  It can't ever know if it may invalidate some
> of that data.

Well, this is mostly indented for maintaining WHOPR summaries where we already
have infrastructure to keep them up to date just the APIs are somewhat unhandy
(having to register hooks all the time)

I also think we can put there sparse stuff that is part of IL but you
do not want to allocate it for every symbol/decl or statement
(like EH regions or not stuff in symbol table that can not be easily handled
by non-multiple inheritance)

Honza
> 
> Same reason why I dislike the ->aux pointers we have.  (even if they
> are of course convenient)
> 
> >> to make cgraph UIDs not sparse?  (keep a free-list of cgraph nodes
> >
> > cgraph nodes are already kept "dense" via freelist.  However in WPA you usually have a lot
> > of different nodes prior merging and unreachable code removal and very few afterwards,
> > the number of nodes grows again with inlining.
> >
> > Depending on what you want to store for values, I guess either vector or hashtable is
> > good choice - if you want to keep data that needs to be duplicated per inline clone
> > you can rely on density. If you want data on few function bodies, you will likely use
> > hash...
> >
> > Honza
> >
> >> with UID < cgraph_max_uid, only really free nodes at the end)
> >> Using a different data structure than a vector indexed by cgraph UID
> >> should also be easily possible (a map from UID to data, hash_map <int, T>).
> >>
> >> Richard.
> >>
> >> > Thank you,
> >> > Martin

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Martin Jambor]

Hi,

On Thu, Oct 16, 2014 at 01:44:05PM +0200, Richard Biener wrote:
> On Thu, Oct 16, 2014 at 1:40 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >>
> >> I don't like "generic annotation" facilities at all.  Would it be possible
> >
> > Why?
> 
> Because it's the way to hell if the IL has "magic" things only one
> pass can understand.  It can't ever know if it may invalidate some
> of that data.

But what would be an alternative to summaries?  Putting all, even
pass-special, data into cgraph_node and cgraph_edge?  Because with LTO
we do not have function bodies at our disposal, the summaries that we
keep in annotations are large enough that we certainly do not want to
grow cgraph_node by that much.

Annotations are only intended for IPA passes, intraprocedural ones
should not worry about the magic in them (yeah, IPA-SRA has to, but
the problem is IPA-SRA, not annotations).  Unfortunately, due to the
three stage nature of IPA world, passes will occasionally trip over
each other, but the solution is a clear API so that passes can
"communicate," rather than making every pass understand data of every
other one.  And this patch moves us in that direction.

> 
> Same reason why I dislike the ->aux pointers we have.  (even if they
> are of course convenient)

I don't think aux is a good analogy.  It is used always only very
briefly, while data from annotations is even stored on disk in LTO.

Martin

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Martin Liška]

On 10/16/2014 01:31 PM, Richard Biener wrote:
> On Wed, Oct 15, 2014 at 6:26 PM, Martin Liška <mliska@suse.cz> wrote:
>> Hello.
>>
>> Following patch introduces a new class called callgraph_annotation. Idea
>> behind the patch is to provide a generic interface one can use to register
>> custom info related to a cgraph_node. As you know, symbol_table provides
>> hooks for creation, deletion and duplication of a cgraph_node. If you have a
>> pass, you need to handle all these hooks and store custom data in your data
>> structure.
>>
>> As an example, after discussion with Martin, I chose usage in ipa-prop.h:
>>
>> data structure:
>> vec<ipa_node_params> ipa_node_params_vector
>>
>> if the pass handles an event, following chunk is executed:
>> if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
>>      ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
>>
>> The problem is that you can have sparse UIDs of cgraph_nodes and every time
>> you have to allocate a vector of size equal to cgraph_max_uid.
>>
>> As a replacement, I implemented first version of cgraph_annotation that
>> internally uses hash_map<cgraph_unique_identifier, T>.
>> Every time a node is deleted, we remove corresponding data associated to the
>> node.
>>
>> What do you think about it?
>
> I don't like "generic annotation" facilities at all.  Would it be possible
> to make cgraph UIDs not sparse?  (keep a free-list of cgraph nodes
> with UID < cgraph_max_uid, only really free nodes at the end)
> Using a different data structure than a vector indexed by cgraph UID
> should also be easily possible (a map from UID to data, hash_map <int, T>).

Hello.

If I recall correctly, we recycle cgraph_nodes and it's possible that an UID is given to different nodes:
symbol_table::allocate_cgraph_symbol (void). Such uid is problematic from perspective that it cannot be used as a index to a vector.

It was also Honza's note that one can choose inner implementation of such annotation class. We can implement both sparse (hash_map) and consecutive vector data structure.

According to first numbers I was given, Inkscape allocates about ~64k cgraph_nodes in WPA. After function merging is processed, it shrinks to about a half. So that, our free list contains the half of nodes. If we use consecutive vector, our memory impact is bigger thank necessary.

Martin


>
> Richard.
>
>> Thank you,
>> Martin

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Richard Biener]

On Thu, Oct 16, 2014 at 1:42 PM, Martin Liška <mliska@suse.cz> wrote:
> On 10/16/2014 01:31 PM, Richard Biener wrote:
>>
>> On Wed, Oct 15, 2014 at 6:26 PM, Martin Liška <mliska@suse.cz> wrote:
>>>
>>> Hello.
>>>
>>> Following patch introduces a new class called callgraph_annotation. Idea
>>> behind the patch is to provide a generic interface one can use to
>>> register
>>> custom info related to a cgraph_node. As you know, symbol_table provides
>>> hooks for creation, deletion and duplication of a cgraph_node. If you
>>> have a
>>> pass, you need to handle all these hooks and store custom data in your
>>> data
>>> structure.
>>>
>>> As an example, after discussion with Martin, I chose usage in ipa-prop.h:
>>>
>>> data structure:
>>> vec<ipa_node_params> ipa_node_params_vector
>>>
>>> if the pass handles an event, following chunk is executed:
>>> if (ipa_node_params_vector.length () <= (unsigned)
>>> symtab->cgraph_max_uid)
>>>      ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid +
>>> 1);
>>>
>>> The problem is that you can have sparse UIDs of cgraph_nodes and every
>>> time
>>> you have to allocate a vector of size equal to cgraph_max_uid.
>>>
>>> As a replacement, I implemented first version of cgraph_annotation that
>>> internally uses hash_map<cgraph_unique_identifier, T>.
>>> Every time a node is deleted, we remove corresponding data associated to
>>> the
>>> node.
>>>
>>> What do you think about it?
>>
>>
>> I don't like "generic annotation" facilities at all.  Would it be possible
>> to make cgraph UIDs not sparse?  (keep a free-list of cgraph nodes
>> with UID < cgraph_max_uid, only really free nodes at the end)
>> Using a different data structure than a vector indexed by cgraph UID
>> should also be easily possible (a map from UID to data, hash_map <int,
>> T>).
>
>
> Hello.
>
> If I recall correctly, we recycle cgraph_nodes and it's possible that an UID
> is given to different nodes:
> symbol_table::allocate_cgraph_symbol (void). Such uid is problematic from
> perspective that it cannot be used as a index to a vector.
>
> It was also Honza's note that one can choose inner implementation of such
> annotation class. We can implement both sparse (hash_map) and consecutive
> vector data structure.
>
> According to first numbers I was given, Inkscape allocates about ~64k
> cgraph_nodes in WPA. After function merging is processed, it shrinks to
> about a half. So that, our free list contains the half of nodes. If we use
> consecutive vector, our memory impact is bigger thank necessary.

I don't think there is anything that forces us to retain the original
UID allocation after WPA merging?  So why not compact it?

Richard.

> Martin
>
>
>>
>> Richard.
>>
>>> Thank you,
>>> Martin
>
>

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Jan Hubicka]

> > Hello.
> >
> > If I recall correctly, we recycle cgraph_nodes and it's possible that an UID
> > is given to different nodes:
> > symbol_table::allocate_cgraph_symbol (void). Such uid is problematic from
> > perspective that it cannot be used as a index to a vector.
> >
> > It was also Honza's note that one can choose inner implementation of such
> > annotation class. We can implement both sparse (hash_map) and consecutive
> > vector data structure.
> >
> > According to first numbers I was given, Inkscape allocates about ~64k
> > cgraph_nodes in WPA. After function merging is processed, it shrinks to
> > about a half. So that, our free list contains the half of nodes. If we use
> > consecutive vector, our memory impact is bigger thank necessary.
> 
> I don't think there is anything that forces us to retain the original
> UID allocation after WPA merging?  So why not compact it?

We could, if we have way to update the summaries that are currently UID allocated.
With annotation template we could have handle to do that more easily than diving into
each of passes maintaining summaries by hand.

On the other hand it still does not make the records quite dense in cases
 1) you do not want to have separate records for clones because you know clones
    and master are identical
 2) you care only about definitions 
...
At some point we discussed introducing separate UIDs for those but that was also
not very welcome (and I agree we already have bit too many UIDs for functions - DECL_UID,
node->uid, DECL_STRUCT_FUNCTION (node)->uid, profile_uid

I tried to get rid of DECL_STRUCT_FUNCTION uid at some point, but did not quite finished
it.

Honza
> 
> Richard.
> 
> > Martin
> >
> >
> >>
> >> Richard.
> >>
> >>> Thank you,
> >>> Martin
> >
> >

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Martin Liška]

On 10/16/2014 02:01 PM, Jan Hubicka wrote:
>>> Hello.
>>>
>>> If I recall correctly, we recycle cgraph_nodes and it's possible that an UID
>>> is given to different nodes:
>>> symbol_table::allocate_cgraph_symbol (void). Such uid is problematic from
>>> perspective that it cannot be used as a index to a vector.
>>>
>>> It was also Honza's note that one can choose inner implementation of such
>>> annotation class. We can implement both sparse (hash_map) and consecutive
>>> vector data structure.
>>>
>>> According to first numbers I was given, Inkscape allocates about ~64k
>>> cgraph_nodes in WPA. After function merging is processed, it shrinks to
>>> about a half. So that, our free list contains the half of nodes. If we use
>>> consecutive vector, our memory impact is bigger thank necessary.
>>
>> I don't think there is anything that forces us to retain the original
>> UID allocation after WPA merging?  So why not compact it?
>
> We could, if we have way to update the summaries that are currently UID allocated.
> With annotation template we could have handle to do that more easily than diving into
> each of passes maintaining summaries by hand.

Agree with that, I will be central point one can implement these optimizations.
One idea is to implement lazy allocation where we can allocate memory just in case
someone calls annotation::get method.

>
> On the other hand it still does not make the records quite dense in cases
>   1) you do not want to have separate records for clones because you know clones
>      and master are identical

It would be quite easy to implement
annotation::get_for_origin (int clone_id), where we find origin for the clone and
return data associated to such origin node.

>   2) you care only about definitions

Maybe similar stuff?

Martin

> ...
> At some point we discussed introducing separate UIDs for those but that was also
> not very welcome (and I agree we already have bit too many UIDs for functions - DECL_UID,
> node->uid, DECL_STRUCT_FUNCTION (node)->uid, profile_uid
>
> I tried to get rid of DECL_STRUCT_FUNCTION uid at some point, but did not quite finished
> it.
>
> Honza
>>
>> Richard.
>>
>>> Martin
>>>
>>>
>>>>
>>>> Richard.
>>>>
>>>>> Thank you,
>>>>> Martin
>>>
>>>

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Martin Liška]

On 10/16/2014 02:05 PM, Martin Liška wrote:
> On 10/16/2014 02:01 PM, Jan Hubicka wrote:
>>>> Hello.
>>>>
>>>> If I recall correctly, we recycle cgraph_nodes and it's possible that an UID
>>>> is given to different nodes:
>>>> symbol_table::allocate_cgraph_symbol (void). Such uid is problematic from
>>>> perspective that it cannot be used as a index to a vector.
>>>>
>>>> It was also Honza's note that one can choose inner implementation of such
>>>> annotation class. We can implement both sparse (hash_map) and consecutive
>>>> vector data structure.
>>>>
>>>> According to first numbers I was given, Inkscape allocates about ~64k
>>>> cgraph_nodes in WPA. After function merging is processed, it shrinks to
>>>> about a half. So that, our free list contains the half of nodes. If we use
>>>> consecutive vector, our memory impact is bigger thank necessary.
>>>
>>> I don't think there is anything that forces us to retain the original
>>> UID allocation after WPA merging?  So why not compact it?
>>
>> We could, if we have way to update the summaries that are currently UID allocated.
>> With annotation template we could have handle to do that more easily than diving into
>> each of passes maintaining summaries by hand.
>
> Agree with that, I will be central point one can implement these optimizations.

s/I/it

> One idea is to implement lazy allocation where we can allocate memory just in case
> someone calls annotation::get method.
>
>>
>> On the other hand it still does not make the records quite dense in cases
>>   1) you do not want to have separate records for clones because you know clones
>>      and master are identical
>
> It would be quite easy to implement
> annotation::get_for_origin (int clone_id), where we find origin for the clone and
> return data associated to such origin node.
>
>>   2) you care only about definitions
>
> Maybe similar stuff?
>
> Martin
>
>> ...
>> At some point we discussed introducing separate UIDs for those but that was also
>> not very welcome (and I agree we already have bit too many UIDs for functions - DECL_UID,
>> node->uid, DECL_STRUCT_FUNCTION (node)->uid, profile_uid
>>
>> I tried to get rid of DECL_STRUCT_FUNCTION uid at some point, but did not quite finished
>> it.
>>
>> Honza
>>>
>>> Richard.
>>>
>>>> Martin
>>>>
>>>>
>>>>>
>>>>> Richard.
>>>>>
>>>>>> Thank you,
>>>>>> Martin
>>>>
>>>>
>

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Martin Jambor]

Hi,

On Wed, Oct 15, 2014 at 06:26:34PM +0200, Martin Liska wrote:
> Hello.
> 
> Following patch introduces a new class called callgraph_annotation. Idea behind the patch is to provide a generic interface one can use to register custom info related to a cgraph_node. As you know, symbol_table provides hooks for creation, deletion and duplication of a cgraph_node. If you have a pass, you need to handle all these hooks and store custom data in your data structure.
> 
> As an example, after discussion with Martin, I chose usage in ipa-prop.h:
> 
> data structure:
> vec<ipa_node_params> ipa_node_params_vector
> 
> if the pass handles an event, following chunk is executed:
> if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
>     ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
> 
> The problem is that you can have sparse UIDs of cgraph_nodes and every time you have to allocate a vector of size equal to cgraph_max_uid.
> 
> As a replacement, I implemented first version of cgraph_annotation that internally uses hash_map<cgraph_unique_identifier, T>.
> Every time a node is deleted, we remove corresponding data associated to the node.
> 
> What do you think about it?

It is clearly an improvement over how we manage our annotations now.
However, I do have a few comments/suggestions:

1. I do not think we need multiple hooks for the same event for one
   kind of annotations.  So I think they need not be stored in a
   vector.  In fact, I thought that these would be converted to
   virtual functions with some default implementation (i.e. nothing
   for creation/deletion, memcpy for duplication) and one would only
   register the annotation, not its hooks, and redefine the virtual
   methods if need be.

2. I think you want to keep a deletion hook (or virtual method),
   rather than relying on destructors of types you keep in
   annotations.  One reason is that it may be useful to be able to
   store a POD and still be notified when its life is over, another is
   that once you attempt to store garbage collected data then
   destructors really won't make any sense.  Of course it is very nice
   if the using destructors also works.

3. If you change a line with "struct cgraph_node" in ipa-prop.[ch],
   don't worry about keeping the struct part and omit it as you do in
   other files.  The good old C times are gone forever and I am doing
   the same in my patches too.

4. I believe that the reverse map should not be necessary if we change
   timing of deletion hook calls which should not cause any problems.

5. I am no C++ expert but can't annotation_hashmap_traits be a private
   type of class cgraph_annotation template?

6. I know that an operator overload is a bold proposal but given this
   is supposed to be an important part of IPA infrastructure I think
   that eventually it would be appropriate and convenient to overload
   [] and use that instead of calling get_or_add method.

7. I certainly hope that after we convert all annotations, UID can
   become unique and not recycled again and we can use that instead of
   the new annotation_uid.  (And use it in dumps too!)

Thanks,

Martin


> 
> Thank you,
> Martin

> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 04ce0c0..bf34c96 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1171,6 +1171,7 @@ OBJS = \
>  	cfgrtl.o \
>  	symtab.o \
>  	cgraph.o \
> +	annotation.o \
>  	cgraphbuild.o \
>  	cgraphunit.o \
>  	cgraphclones.o \
> diff --git a/gcc/annotation.c b/gcc/annotation.c
> new file mode 100644
> index 0000000..a8b6053
> --- /dev/null
> +++ b/gcc/annotation.c
> @@ -0,0 +1 @@
> +#include "annotation.h"
> diff --git a/gcc/annotation.h b/gcc/annotation.h
> new file mode 100644
> index 0000000..7520677
> --- /dev/null
> +++ b/gcc/annotation.h
> @@ -0,0 +1,285 @@
> +/* Annotations handling code.
> +   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 GCC_ANNOTATION_H
> +#define GCC_ANNOTATION_H
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tm.h"
> +#include "tree.h"
> +#include "varasm.h"
> +#include "calls.h"
> +#include "print-tree.h"
> +#include "tree-inline.h"
> +#include "langhooks.h"
> +#include "hashtab.h"
> +#include "toplev.h"
> +#include "flags.h"
> +#include "debug.h"
> +#include "target.h"
> +#include "cgraph.h"
> +#include "hash-map.h"
> +
> +#define ANNOTATION_DELETED_VALUE -1
> +#define ANNOTATION_EMPTY_VALUE 0
> +
> +struct annotation_hashmap_traits: default_hashmap_traits
> +{
> +  static inline
> +  hashval_t hash (const int v)
> +  {
> +    return (hashval_t)v;
> +  }
> +
> +  template<typename T>
> +  static inline
> +  bool is_deleted (T &e)
> +  {
> +    return e.m_key == ANNOTATION_DELETED_VALUE;
> +  }
> +
> +  template<typename T>
> +  static inline
> +  bool is_empty (T &e)
> +  {
> +    return e.m_key == ANNOTATION_EMPTY_VALUE;
> +  }
> +
> +  template<typename T>
> +  static inline
> +  void mark_deleted (T &e)
> +  {
> +    e.m_key = ANNOTATION_DELETED_VALUE;
> +  }
> +
> +  template<typename T>
> +  static inline
> +  void mark_empty (T &e)
> +  {
> +    e.m_key = ANNOTATION_EMPTY_VALUE;
> +  }
> +};
> +
> +template <class T>
> +class cgraph_annotation
> +{
> +public:
> +  /* Default construction takes SYMTAB as an argument.  */
> +  cgraph_annotation (symbol_table *symtab): m_symtab (symtab)
> +  {
> +    cgraph_node *node;
> +
> +    FOR_EACH_FUNCTION (node)
> +    {
> +      gcc_assert (node->annotation_uid > 0);
> +      m_reverse_map.put (node, node->annotation_uid);
> +    }
> +
> +    m_map = new  hash_map<int, T*, annotation_hashmap_traits>();
> +
> +    m_symtab_insertion_hook =
> +      symtab->add_cgraph_insertion_hook
> +      (cgraph_annotation::symtab_insertion, this);
> +
> +    m_symtab_removal_hook =
> +      symtab->add_cgraph_removal_hook
> +      (cgraph_annotation::symtab_removal, this);
> +    m_symtab_duplication_hook =
> +      symtab->add_cgraph_duplication_hook
> +      (cgraph_annotation::symtab_duplication, this);
> +
> +  }
> +
> +  /* Destructor.  */
> +  ~cgraph_annotation ()
> +  {
> +    m_symtab->remove_cgraph_insertion_hook (m_symtab_insertion_hook);
> +    m_symtab->remove_cgraph_removal_hook (m_symtab_removal_hook);
> +    m_symtab->remove_cgraph_duplication_hook (m_symtab_duplication_hook);
> +
> +    m_map->traverse <void *, cgraph_annotation::release> (NULL);
> +  }
> +
> +  /* Traverses all annotations with a function F called with
> +     ARG as argument.  */
> +  template<typename Arg, bool (*f)(const T &, Arg)>
> +  void traverse (Arg a) const
> +  {
> +    m_map->traverse <f> (a);
> +  }
> +
> +  /* Function for registering insertion hook.  */
> +  template <void (*f) (const cgraph_node *, T *)>
> +  inline void add_insertion_hook (void)
> +  {
> +    m_insertion_hooks.safe_push (f);
> +  }
> +
> +  /* Function for registering removal hook.  */
> +  template <void (*f) (const cgraph_node *, T *)>
> +  inline void add_removal_hook (void)
> +  {
> +    m_removal_hooks.safe_push (f);
> +  }
> +
> +  /* Function for registering duplication hook.  */
> +  template <void (*f) (const cgraph_node *, const cgraph_node *, T *, T *)>
> +  inline void add_duplication_hook (void)
> +  {
> +    m_duplication_hooks.safe_push (f);
> +  }
> +
> +  /* Getter for annotation callgraph ID.  */
> +  inline T* get_or_add (int uid)
> +  {
> +    T **v = m_map->get (uid);
> +    if (!v)
> +      {
> +	T *new_value = new T();
> +	m_map->put (uid, new_value);
> +
> +	v = &new_value;
> +      }
> +
> +    return *v;
> +  }
> +
> +  /* Getter for annotation callgraph node pointer.  */
> +  inline T *get_or_add (cgraph_node *node)
> +  {
> +    return get_or_add (node->annotation_uid);
> +  }
> +
> +  /* Symbol insertion hook that is registered to symbol table.  */
> +  static void symtab_insertion (cgraph_node *node, void *data)
> +  {
> +    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
> +    annotation->call_insertion_hooks (node);
> +  }
> +
> +  /* Symbol removal hook that is registered to symbol table.  */
> +  static void symtab_removal (cgraph_node *node, void *data)
> +  {
> +    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
> +    int *annotation_uid_ptr = annotation->m_reverse_map.get (node);
> +
> +    if (!annotation_uid_ptr)
> +      return;
> +
> +    int annotation_uid = *annotation_uid_ptr;
> +
> +    T **v = annotation->m_map->get (annotation_uid);
> +
> +    if (v)
> +      annotation->call_removal_hooks (node, *v);
> +
> +    annotation->m_reverse_map.remove (node);
> +
> +    if (annotation->m_map->get (annotation_uid))
> +      annotation->m_map->remove (annotation_uid);
> +
> +  }
> +
> +  /* Symbol duplication hook that is registered to symbol table.  */
> +  static void symtab_duplication (cgraph_node *node, cgraph_node *node2,
> +				  void *data)
> +  {
> +    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
> +    T **v = annotation->m_map->get (node->annotation_uid);
> +
> +    gcc_assert (node2->annotation_uid > 0);
> +    annotation->m_reverse_map.put (node2, node2->annotation_uid);
> +
> +    if (v)
> +      {
> +	T *data = *v;
> +	T *duplicate = new T();
> +	annotation->m_map->put (node2->annotation_uid, duplicate);
> +	annotation->call_duplication_hooks (node, node2, data);
> +      }
> +
> +  }
> +
> +  /* Main annotation store, where annotation ID is used as key.  */
> +  hash_map <int, T *, annotation_hashmap_traits> *m_map;
> +
> +  /* Inverse mapping structure used in cgraph deletion context.  */
> +  hash_map <cgraph_node *, int> m_reverse_map;
> +
> +private:
> +  /* Remove annotation for annotation UID.  */
> +  inline void remove (int uid)
> +  {
> +    T *v = m_map->get (uid);
> +
> +    if (v)
> +      m_map->erase (uid);
> +  }
> +
> +  /* Annotation class release function called by traverse method.  */
> +  static bool release (int const &, T * const &v, void *)
> +  {
> +    delete (v);
> +    return true;
> +  }
> +
> +  /* Call insertion hook for callgraph NODE.  */
> +  inline void call_insertion_hooks (cgraph_node *node)
> +  {
> +    for (unsigned int i = 0; i < m_insertion_hooks.length (); i++)
> +      m_insertion_hooks[i] (node, get_or_add (node));
> +  }
> +
> +  /* Call removal hook for callgraph NODE.  */
> +  inline void call_removal_hooks (cgraph_node *node, T *v)
> +  {
> +    for (unsigned int i = 0; i < m_removal_hooks.length (); i++)
> +      m_removal_hooks[i] (node, v);
> +  }
> +
> +  /* Call duplication hook for callgraph NODE.  */
> +  inline void call_duplication_hooks (cgraph_node *node, cgraph_node *node2, T *v)
> +  {
> +    for (unsigned int i = 0; i < m_duplication_hooks.length (); i++)
> +      m_duplication_hooks[i] (node, node2, v, get_or_add (node2));
> +  }
> +
> +  /* List of symbol insertion hooks.  */
> +  auto_vec <void (*) (cgraph_node *, T *)> m_insertion_hooks;
> +  /* List of symbol removal hooks.  */
> +  auto_vec <void (*) (cgraph_node *, T *)> m_removal_hooks;
> +  /* List of symbol duplication hooks.  */
> +  auto_vec <void (*) (const cgraph_node *, const cgraph_node *, T *, T *)>
> +  m_duplication_hooks;
> +
> +  /* Internal annotation insertion hook pointer.  */
> +  cgraph_node_hook_list *m_symtab_insertion_hook;
> +  /* Internal annotation removal hook pointer.  */
> +  cgraph_node_hook_list *m_symtab_removal_hook;
> +  /* Internal annotation duplication hook pointer.  */
> +  cgraph_2node_hook_list *m_symtab_duplication_hook;
> +
> +  /* Symbol table the annotation is registered to.  */
> +  symbol_table *m_symtab;
> +};
> +
> +#endif  /* GCC_ANNOTATION_H  */
> diff --git a/gcc/cgraph.h b/gcc/cgraph.h
> index a5777c2..32a770a 100644
> --- a/gcc/cgraph.h
> +++ b/gcc/cgraph.h
> @@ -1219,6 +1219,8 @@ public:
>    int count_materialization_scale;
>    /* Unique id of the node.  */
>    int uid;
> +  /* Annotation unique id of the node.  */
> +  int annotation_uid;
>    /* ID assigned by the profiling.  */
>    unsigned int profile_id;
>    /* Time profiler: first run of function.  */
> @@ -1771,6 +1773,10 @@ public:
>    friend class cgraph_node;
>    friend class cgraph_edge;
>  
> +  symbol_table (): cgraph_max_annotation_uid (1)
> +  {
> +  }
> +
>    /* Initialize callgraph dump file.  */
>    inline void
>    initialize (void)
> @@ -1972,6 +1978,7 @@ public:
>  
>    int cgraph_count;
>    int cgraph_max_uid;
> +  int cgraph_max_annotation_uid;
>  
>    int edges_count;
>    int edges_max_uid;
> @@ -2268,6 +2275,9 @@ symbol_table::create_empty (void)
>  {
>    cgraph_node *node = allocate_cgraph_symbol ();
>  
> +  gcc_assert (cgraph_max_annotation_uid);
> +  node->annotation_uid = cgraph_max_annotation_uid++;
> +
>    node->type = SYMTAB_FUNCTION;
>    node->frequency = NODE_FREQUENCY_NORMAL;
>    node->count_materialization_scale = REG_BR_PROB_BASE;
> diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c
> index 38f56d2..e2576b3 100644
> --- a/gcc/ipa-inline-analysis.c
> +++ b/gcc/ipa-inline-analysis.c
> @@ -895,7 +895,7 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
>    if (known_binfos_ptr)
>      known_binfos_ptr->create (0);
>  
> -  if (ipa_node_params_vector.exists ()
> +  if (ipa_node_params_annotation
>        && !e->call_stmt_cannot_inline_p
>        && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
>      {
> @@ -1115,7 +1115,7 @@ inline_node_duplication_hook (struct cgraph_node *src,
>  
>    /* When there are any replacements in the function body, see if we can figure
>       out that something was optimized out.  */
> -  if (ipa_node_params_vector.exists () && dst->clone.tree_map)
> +  if (ipa_node_params_annotation && dst->clone.tree_map)
>      {
>        vec<size_time_entry, va_gc> *entry = info->entry;
>        /* Use SRC parm info since it may not be copied yet.  */
> @@ -2462,7 +2462,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
>        calculate_dominance_info (CDI_DOMINATORS);
>        loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
>  
> -      if (ipa_node_params_vector.exists ())
> +      if (ipa_node_params_annotation)
>  	{
>  	  parms_info = IPA_NODE_REF (node);
>  	  nonconstant_names.safe_grow_cleared
> @@ -2610,7 +2610,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
>  		  nonconstant_names[SSA_NAME_VERSION (gimple_call_lhs (stmt))]
>  		    = false_p;
>  		}
> -	      if (ipa_node_params_vector.exists ())
> +	      if (ipa_node_params_annotation)
>  		{
>  		  int count = gimple_call_num_args (stmt);
>  		  int i;
> @@ -3353,7 +3353,7 @@ static void
>  remap_edge_change_prob (struct cgraph_edge *inlined_edge,
>  			struct cgraph_edge *edge)
>  {
> -  if (ipa_node_params_vector.exists ())
> +  if (ipa_node_params_annotation)
>      {
>        int i;
>        struct ipa_edge_args *args = IPA_EDGE_REF (edge);
> @@ -3509,7 +3509,7 @@ inline_merge_summary (struct cgraph_edge *edge)
>    else
>      toplev_predicate = true_predicate ();
>  
> -  if (ipa_node_params_vector.exists () && callee_info->conds)
> +  if (ipa_node_params_annotation && callee_info->conds)
>      {
>        struct ipa_edge_args *args = IPA_EDGE_REF (edge);
>        int count = ipa_get_cs_argument_count (args);
> diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c
> index 9ac1929..ad98467 100644
> --- a/gcc/ipa-inline.c
> +++ b/gcc/ipa-inline.c
> @@ -2408,7 +2408,7 @@ pass_early_inline::execute (function *fun)
>       it.  This may confuse ourself when early inliner decide to inline call to
>       function clone, because function clones don't have parameter list in
>       ipa-prop matching their signature.  */
> -  if (ipa_node_params_vector.exists ())
> +  if (ipa_node_params_annotation)
>      return 0;
>  
>  #ifdef ENABLE_CHECKING
> diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
> index 62db327..743d9ff 100644
> --- a/gcc/ipa-prop.c
> +++ b/gcc/ipa-prop.c
> @@ -115,7 +115,8 @@ struct func_body_info
>    unsigned int aa_walked;
>  };
>  
> -/* Vector where the parameter infos are actually stored. */
> +/* Callgraph annotation where the parameter infos are actually stored. */
> +cgraph_annotation <struct ipa_node_params> *ipa_node_params_annotation = NULL;
>  vec<ipa_node_params> ipa_node_params_vector;
>  /* Vector of known aggregate values in cloned nodes.  */
>  vec<ipa_agg_replacement_value_p, va_gc> *ipa_node_agg_replacements;
> @@ -124,9 +125,7 @@ vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
>  
>  /* Holders of ipa cgraph hooks: */
>  static struct cgraph_edge_hook_list *edge_removal_hook_holder;
> -static struct cgraph_node_hook_list *node_removal_hook_holder;
>  static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
> -static struct cgraph_2node_hook_list *node_duplication_hook_holder;
>  static struct cgraph_node_hook_list *function_insertion_hook_holder;
>  
>  /* Description of a reference to an IPA constant.  */
> @@ -3554,7 +3553,7 @@ ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
>    bool changed;
>    /* Do nothing if the preparation phase has not been carried out yet
>       (i.e. during early inlining).  */
> -  if (!ipa_node_params_vector.exists ())
> +  if (!ipa_node_params_annotation)
>      return false;
>    gcc_assert (ipa_edge_args_vector);
>  
> @@ -3594,15 +3593,21 @@ ipa_free_all_edge_args (void)
>  /* Frees all dynamically allocated structures that the param info points
>     to.  */
>  
> -void
> -ipa_free_node_params_substructures (struct ipa_node_params *info)
> +ipa_node_params::~ipa_node_params ()
>  {
> -  info->descriptors.release ();
> -  free (info->lattices);
> +  descriptors.release ();
> +  free (lattices);
>    /* Lattice values and their sources are deallocated with their alocation
>       pool.  */
> -  info->known_vals.release ();
> -  memset (info, 0, sizeof (*info));
> +  known_vals.release ();
> +
> +  lattices = NULL;
> +  ipcp_orig_node = NULL;
> +  analysis_done = 0;
> +  node_enqueued = 0;
> +  do_clone_for_all_contexts = 0;
> +  is_all_contexts_clone = 0;
> +  node_dead = 0;
>  }
>  
>  /* Free all ipa_node_params structures.  */
> @@ -3610,11 +3615,8 @@ ipa_free_node_params_substructures (struct ipa_node_params *info)
>  void
>  ipa_free_all_node_params (void)
>  {
> -  int i;
> -  struct ipa_node_params *info;
> -
> -  FOR_EACH_VEC_ELT (ipa_node_params_vector, i, info)
> -    ipa_free_node_params_substructures (info);
> +  delete ipa_node_params_annotation;
> +  ipa_node_params_annotation = NULL;
>  
>    ipa_node_params_vector.release ();
>  }
> @@ -3622,7 +3624,7 @@ ipa_free_all_node_params (void)
>  /* Set the aggregate replacements of NODE to be AGGVALS.  */
>  
>  void
> -ipa_set_node_agg_value_chain (struct cgraph_node *node,
> +ipa_set_node_agg_value_chain (const struct cgraph_node *node,
>  			      struct ipa_agg_replacement_value *aggvals)
>  {
>    if (vec_safe_length (ipa_node_agg_replacements)
> @@ -3663,18 +3665,6 @@ ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
>    ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
>  }
>  
> -/* Hook that is called by cgraph.c when a node is removed.  */
> -
> -static void
> -ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
> -{
> -  /* During IPA-CP updating we can be called on not-yet analyze clones.  */
> -  if (ipa_node_params_vector.length () > (unsigned)node->uid)
> -    ipa_free_node_params_substructures (IPA_NODE_REF (node));
> -  if (vec_safe_length (ipa_node_agg_replacements) > (unsigned)node->uid)
> -    (*ipa_node_agg_replacements)[(unsigned)node->uid] = NULL;
> -}
> -
>  /* Hook that is called by cgraph.c when an edge is duplicated.  */
>  
>  static void
> @@ -3779,18 +3769,22 @@ ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
>      }
>  }
>  
> -/* Hook that is called by cgraph.c when a node is duplicated.  */
> +/* Analyze newly added function into callgraph.  */
>  
>  static void
> -ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
> -			   ATTRIBUTE_UNUSED void *data)
> +ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
>  {
> -  struct ipa_node_params *old_info, *new_info;
> -  struct ipa_agg_replacement_value *old_av, *new_av;
> +  if (node->has_gimple_body_p ())
> +    ipa_analyze_node (node);
> +}
>  
> -  ipa_check_create_node_params ();
> -  old_info = IPA_NODE_REF (src);
> -  new_info = IPA_NODE_REF (dst);
> +/* Hook that is called by cgraph.c when a node is duplicated.  */
> +
> +void
> +ipa_node_duplication_hook (const struct cgraph_node *src, const struct cgraph_node *dst,
> +                          struct ipa_node_params *old_info, struct ipa_node_params *new_info)
> +{
> +  struct ipa_agg_replacement_value *old_av, *new_av;
>  
>    new_info->descriptors = old_info->descriptors.copy ();
>    new_info->lattices = NULL;
> @@ -3817,33 +3811,19 @@ ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
>    ipa_set_node_agg_value_chain (dst, new_av);
>  }
>  
> -
> -/* Analyze newly added function into callgraph.  */
> -
> -static void
> -ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
> -{
> -  if (node->has_gimple_body_p ())
> -    ipa_analyze_node (node);
> -}
> -
>  /* Register our cgraph hooks if they are not already there.  */
>  
>  void
>  ipa_register_cgraph_hooks (void)
>  {
> +  ipa_check_create_node_params ();
> +
>    if (!edge_removal_hook_holder)
>      edge_removal_hook_holder =
>        symtab->add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
> -  if (!node_removal_hook_holder)
> -    node_removal_hook_holder =
> -      symtab->add_cgraph_removal_hook (&ipa_node_removal_hook, NULL);
>    if (!edge_duplication_hook_holder)
>      edge_duplication_hook_holder =
>        symtab->add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
> -  if (!node_duplication_hook_holder)
> -    node_duplication_hook_holder =
> -      symtab->add_cgraph_duplication_hook (&ipa_node_duplication_hook, NULL);
>    function_insertion_hook_holder =
>        symtab->add_cgraph_insertion_hook (&ipa_add_new_function, NULL);
>  }
> @@ -3855,12 +3835,8 @@ ipa_unregister_cgraph_hooks (void)
>  {
>    symtab->remove_edge_removal_hook (edge_removal_hook_holder);
>    edge_removal_hook_holder = NULL;
> -  symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
> -  node_removal_hook_holder = NULL;
>    symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
>    edge_duplication_hook_holder = NULL;
> -  symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
> -  node_duplication_hook_holder = NULL;
>    symtab->remove_cgraph_insertion_hook (function_insertion_hook_holder);
>    function_insertion_hook_holder = NULL;
>  }
> @@ -5030,8 +5006,7 @@ ipa_prop_write_jump_functions (void)
>    lto_symtab_encoder_iterator lsei;
>    lto_symtab_encoder_t encoder;
>  
> -
> -  if (!ipa_node_params_vector.exists ())
> +  if (!ipa_node_params_annotation)
>      return;
>  
>    ob = create_output_block (LTO_section_jump_functions);
> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
> index 7a06af9..6a3772d 100644
> --- a/gcc/ipa-prop.h
> +++ b/gcc/ipa-prop.h
> @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "vec.h"
>  #include "cgraph.h"
>  #include "alloc-pool.h"
> +#include "annotation.h"
>  
>  /* The following definitions and interfaces are used by
>     interprocedural analyses or parameters.  */
> @@ -359,6 +360,8 @@ struct ipcp_lattice;
>  
>  struct ipa_node_params
>  {
> +  ~ipa_node_params ();
> +
>    /* Information about individual formal parameters that are gathered when
>       summaries are generated. */
>    vec<ipa_param_descriptor> descriptors;
> @@ -473,7 +476,7 @@ struct GTY(()) ipa_agg_replacement_value
>  
>  typedef struct ipa_agg_replacement_value *ipa_agg_replacement_value_p;
>  
> -void ipa_set_node_agg_value_chain (struct cgraph_node *node,
> +void ipa_set_node_agg_value_chain (const struct cgraph_node *node,
>  				   struct ipa_agg_replacement_value *aggvals);
>  
>  /* ipa_edge_args stores information related to a callsite and particularly its
> @@ -519,7 +522,7 @@ ipa_get_ith_polymorhic_call_context (struct ipa_edge_args *args, int i)
>  /* Types of vectors holding the infos.  */
>  
>  /* Vector where the parameter infos are actually stored. */
> -extern vec<ipa_node_params> ipa_node_params_vector;
> +extern cgraph_annotation <ipa_node_params> *ipa_node_params_annotation;
>  /* Vector of known aggregate values in cloned nodes.  */
>  extern GTY(()) vec<ipa_agg_replacement_value_p, va_gc> *ipa_node_agg_replacements;
>  /* Vector where the parameter infos are actually stored. */
> @@ -527,7 +530,7 @@ extern GTY(()) vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
>  
>  /* Return the associated parameter/argument info corresponding to the given
>     node/edge.  */
> -#define IPA_NODE_REF(NODE) (&ipa_node_params_vector[(NODE)->uid])
> +#define IPA_NODE_REF(NODE) (ipa_node_params_annotation->get_or_add (NODE))
>  #define IPA_EDGE_REF(EDGE) (&(*ipa_edge_args_vector)[(EDGE)->uid])
>  /* This macro checks validity of index returned by
>     ipa_get_param_decl_index function.  */
> @@ -537,11 +540,15 @@ extern GTY(()) vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
>  void ipa_create_all_node_params (void);
>  void ipa_create_all_edge_args (void);
>  void ipa_free_edge_args_substructures (struct ipa_edge_args *);
> -void ipa_free_node_params_substructures (struct ipa_node_params *);
>  void ipa_free_all_node_params (void);
>  void ipa_free_all_edge_args (void);
>  void ipa_free_all_structures_after_ipa_cp (void);
>  void ipa_free_all_structures_after_iinln (void);
> +void  ipa_node_duplication_hook (const struct cgraph_node *src,
> +				 const struct cgraph_node *dst,
> +				 struct ipa_node_params *old_info,
> +				 struct ipa_node_params *new_info);
> +
>  void ipa_register_cgraph_hooks (void);
>  int count_formal_params (tree fndecl);
>  
> @@ -551,11 +558,11 @@ int count_formal_params (tree fndecl);
>  static inline void
>  ipa_check_create_node_params (void)
>  {
> -  if (!ipa_node_params_vector.exists ())
> -    ipa_node_params_vector.create (symtab->cgraph_max_uid);
> -
> -  if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
> -    ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
> +  if (!ipa_node_params_annotation)
> +    {
> +      ipa_node_params_annotation = new cgraph_annotation <ipa_node_params> (symtab);
> +      ipa_node_params_annotation->add_duplication_hook <ipa_node_duplication_hook> ();
> +    }
>  }
>  
>  /* This function ensures the array of edge arguments infos is big enough to
> @@ -582,7 +589,7 @@ ipa_edge_args_info_available_for_edge_p (struct cgraph_edge *edge)
>  /* Return the aggregate replacements for NODE, if there are any.  */
>  
>  static inline struct ipa_agg_replacement_value *
> -ipa_get_agg_replacements_for_node (struct cgraph_node *node)
> +ipa_get_agg_replacements_for_node (const struct cgraph_node *node)
>  {
>    if ((unsigned) node->uid >= vec_safe_length (ipa_node_agg_replacements))
>      return NULL;
> diff --git a/gcc/toplev.c b/gcc/toplev.c
> index f7a5035..5e31ec2 100644
> --- a/gcc/toplev.c
> +++ b/gcc/toplev.c
> @@ -1176,7 +1176,7 @@ general_init (const char *argv0)
>    /* Create the singleton holder for global state.
>       Doing so also creates the pass manager and with it the passes.  */
>    g = new gcc::context ();
> -  symtab = ggc_cleared_alloc <symbol_table> ();
> +  symtab = new (ggc_cleared_alloc <symbol_table> ()) symbol_table ();
>  
>    statistics_early_init ();
>    finish_params ();

Re: [RFC, PATCH]: Introduction of callgraph annotation class

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 30077 bytes --]

On 10/16/2014 04:15 PM, Martin Jambor wrote:
> Hi,
>
> On Wed, Oct 15, 2014 at 06:26:34PM +0200, Martin Liska wrote:
>> Hello.
>>
>> Following patch introduces a new class called callgraph_annotation. Idea behind the patch is to provide a generic interface one can use to register custom info related to a cgraph_node. As you know, symbol_table provides hooks for creation, deletion and duplication of a cgraph_node. If you have a pass, you need to handle all these hooks and store custom data in your data structure.
>>
>> As an example, after discussion with Martin, I chose usage in ipa-prop.h:
>>
>> data structure:
>> vec<ipa_node_params> ipa_node_params_vector
>>
>> if the pass handles an event, following chunk is executed:
>> if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
>>      ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
>>
>> The problem is that you can have sparse UIDs of cgraph_nodes and every time you have to allocate a vector of size equal to cgraph_max_uid.
>>
>> As a replacement, I implemented first version of cgraph_annotation that internally uses hash_map<cgraph_unique_identifier, T>.
>> Every time a node is deleted, we remove corresponding data associated to the node.
>>
>> What do you think about it?
>
> It is clearly an improvement over how we manage our annotations now.
> However, I do have a few comments/suggestions:
>
> 1. I do not think we need multiple hooks for the same event for one
>     kind of annotations.  So I think they need not be stored in a
>     vector.  In fact, I thought that these would be converted to
>     virtual functions with some default implementation (i.e. nothing
>     for creation/deletion, memcpy for duplication) and one would only
>     register the annotation, not its hooks, and redefine the virtual
>     methods if need be.
>
> 2. I think you want to keep a deletion hook (or virtual method),
>     rather than relying on destructors of types you keep in
>     annotations.  One reason is that it may be useful to be able to
>     store a POD and still be notified when its life is over, another is
>     that once you attempt to store garbage collected data then
>     destructors really won't make any sense.  Of course it is very nice
>     if the using destructors also works.
>
> 3. If you change a line with "struct cgraph_node" in ipa-prop.[ch],
>     don't worry about keeping the struct part and omit it as you do in
>     other files.  The good old C times are gone forever and I am doing
>     the same in my patches too.
>
> 4. I believe that the reverse map should not be necessary if we change
>     timing of deletion hook calls which should not cause any problems.
>
> 5. I am no C++ expert but can't annotation_hashmap_traits be a private
>     type of class cgraph_annotation template?
>
> 6. I know that an operator overload is a bold proposal but given this
>     is supposed to be an important part of IPA infrastructure I think
>     that eventually it would be appropriate and convenient to overload
>     [] and use that instead of calling get_or_add method.
>
> 7. I certainly hope that after we convert all annotations, UID can
>     become unique and not recycled again and we can use that instead of
>     the new annotation_uid.  (And use it in dumps too!)
>
> Thanks,
>
> Martin

Thank you Martin for very fitting suggestions, all were implemented
in updated patch.

I've been working on GGC variant of the data structure.

New numbers for ipa_node_params:
cgraph_max_uid = 144720
maximum structures stored in annotation = 64091
# of structures in first IPA pass = 25138

As I replaced vector to annotation, ipa_node_params can save just 6x less elements,
giving us about 5MB of memory footprint. Looks negligible, but inlining-related structures
will be more interesting. I've been working on a variant that can be used with GGC structures.

What do you think about merging the patch for 5.0?

Thank you,
Martin

>
>
>>
>> Thank you,
>> Martin
>
>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>> index 04ce0c0..bf34c96 100644
>> --- a/gcc/Makefile.in
>> +++ b/gcc/Makefile.in
>> @@ -1171,6 +1171,7 @@ OBJS = \
>>   	cfgrtl.o \
>>   	symtab.o \
>>   	cgraph.o \
>> +	annotation.o \
>>   	cgraphbuild.o \
>>   	cgraphunit.o \
>>   	cgraphclones.o \
>> diff --git a/gcc/annotation.c b/gcc/annotation.c
>> new file mode 100644
>> index 0000000..a8b6053
>> --- /dev/null
>> +++ b/gcc/annotation.c
>> @@ -0,0 +1 @@
>> +#include "annotation.h"
>> diff --git a/gcc/annotation.h b/gcc/annotation.h
>> new file mode 100644
>> index 0000000..7520677
>> --- /dev/null
>> +++ b/gcc/annotation.h
>> @@ -0,0 +1,285 @@
>> +/* Annotations handling code.
>> +   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 GCC_ANNOTATION_H
>> +#define GCC_ANNOTATION_H
>> +
>> +#include "config.h"
>> +#include "system.h"
>> +#include "coretypes.h"
>> +#include "tm.h"
>> +#include "tree.h"
>> +#include "varasm.h"
>> +#include "calls.h"
>> +#include "print-tree.h"
>> +#include "tree-inline.h"
>> +#include "langhooks.h"
>> +#include "hashtab.h"
>> +#include "toplev.h"
>> +#include "flags.h"
>> +#include "debug.h"
>> +#include "target.h"
>> +#include "cgraph.h"
>> +#include "hash-map.h"
>> +
>> +#define ANNOTATION_DELETED_VALUE -1
>> +#define ANNOTATION_EMPTY_VALUE 0
>> +
>> +struct annotation_hashmap_traits: default_hashmap_traits
>> +{
>> +  static inline
>> +  hashval_t hash (const int v)
>> +  {
>> +    return (hashval_t)v;
>> +  }
>> +
>> +  template<typename T>
>> +  static inline
>> +  bool is_deleted (T &e)
>> +  {
>> +    return e.m_key == ANNOTATION_DELETED_VALUE;
>> +  }
>> +
>> +  template<typename T>
>> +  static inline
>> +  bool is_empty (T &e)
>> +  {
>> +    return e.m_key == ANNOTATION_EMPTY_VALUE;
>> +  }
>> +
>> +  template<typename T>
>> +  static inline
>> +  void mark_deleted (T &e)
>> +  {
>> +    e.m_key = ANNOTATION_DELETED_VALUE;
>> +  }
>> +
>> +  template<typename T>
>> +  static inline
>> +  void mark_empty (T &e)
>> +  {
>> +    e.m_key = ANNOTATION_EMPTY_VALUE;
>> +  }
>> +};
>> +
>> +template <class T>
>> +class cgraph_annotation
>> +{
>> +public:
>> +  /* Default construction takes SYMTAB as an argument.  */
>> +  cgraph_annotation (symbol_table *symtab): m_symtab (symtab)
>> +  {
>> +    cgraph_node *node;
>> +
>> +    FOR_EACH_FUNCTION (node)
>> +    {
>> +      gcc_assert (node->annotation_uid > 0);
>> +      m_reverse_map.put (node, node->annotation_uid);
>> +    }
>> +
>> +    m_map = new  hash_map<int, T*, annotation_hashmap_traits>();
>> +
>> +    m_symtab_insertion_hook =
>> +      symtab->add_cgraph_insertion_hook
>> +      (cgraph_annotation::symtab_insertion, this);
>> +
>> +    m_symtab_removal_hook =
>> +      symtab->add_cgraph_removal_hook
>> +      (cgraph_annotation::symtab_removal, this);
>> +    m_symtab_duplication_hook =
>> +      symtab->add_cgraph_duplication_hook
>> +      (cgraph_annotation::symtab_duplication, this);
>> +
>> +  }
>> +
>> +  /* Destructor.  */
>> +  ~cgraph_annotation ()
>> +  {
>> +    m_symtab->remove_cgraph_insertion_hook (m_symtab_insertion_hook);
>> +    m_symtab->remove_cgraph_removal_hook (m_symtab_removal_hook);
>> +    m_symtab->remove_cgraph_duplication_hook (m_symtab_duplication_hook);
>> +
>> +    m_map->traverse <void *, cgraph_annotation::release> (NULL);
>> +  }
>> +
>> +  /* Traverses all annotations with a function F called with
>> +     ARG as argument.  */
>> +  template<typename Arg, bool (*f)(const T &, Arg)>
>> +  void traverse (Arg a) const
>> +  {
>> +    m_map->traverse <f> (a);
>> +  }
>> +
>> +  /* Function for registering insertion hook.  */
>> +  template <void (*f) (const cgraph_node *, T *)>
>> +  inline void add_insertion_hook (void)
>> +  {
>> +    m_insertion_hooks.safe_push (f);
>> +  }
>> +
>> +  /* Function for registering removal hook.  */
>> +  template <void (*f) (const cgraph_node *, T *)>
>> +  inline void add_removal_hook (void)
>> +  {
>> +    m_removal_hooks.safe_push (f);
>> +  }
>> +
>> +  /* Function for registering duplication hook.  */
>> +  template <void (*f) (const cgraph_node *, const cgraph_node *, T *, T *)>
>> +  inline void add_duplication_hook (void)
>> +  {
>> +    m_duplication_hooks.safe_push (f);
>> +  }
>> +
>> +  /* Getter for annotation callgraph ID.  */
>> +  inline T* get_or_add (int uid)
>> +  {
>> +    T **v = m_map->get (uid);
>> +    if (!v)
>> +      {
>> +	T *new_value = new T();
>> +	m_map->put (uid, new_value);
>> +
>> +	v = &new_value;
>> +      }
>> +
>> +    return *v;
>> +  }
>> +
>> +  /* Getter for annotation callgraph node pointer.  */
>> +  inline T *get_or_add (cgraph_node *node)
>> +  {
>> +    return get_or_add (node->annotation_uid);
>> +  }
>> +
>> +  /* Symbol insertion hook that is registered to symbol table.  */
>> +  static void symtab_insertion (cgraph_node *node, void *data)
>> +  {
>> +    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
>> +    annotation->call_insertion_hooks (node);
>> +  }
>> +
>> +  /* Symbol removal hook that is registered to symbol table.  */
>> +  static void symtab_removal (cgraph_node *node, void *data)
>> +  {
>> +    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
>> +    int *annotation_uid_ptr = annotation->m_reverse_map.get (node);
>> +
>> +    if (!annotation_uid_ptr)
>> +      return;
>> +
>> +    int annotation_uid = *annotation_uid_ptr;
>> +
>> +    T **v = annotation->m_map->get (annotation_uid);
>> +
>> +    if (v)
>> +      annotation->call_removal_hooks (node, *v);
>> +
>> +    annotation->m_reverse_map.remove (node);
>> +
>> +    if (annotation->m_map->get (annotation_uid))
>> +      annotation->m_map->remove (annotation_uid);
>> +
>> +  }
>> +
>> +  /* Symbol duplication hook that is registered to symbol table.  */
>> +  static void symtab_duplication (cgraph_node *node, cgraph_node *node2,
>> +				  void *data)
>> +  {
>> +    cgraph_annotation *annotation = (cgraph_annotation <T> *) (data);
>> +    T **v = annotation->m_map->get (node->annotation_uid);
>> +
>> +    gcc_assert (node2->annotation_uid > 0);
>> +    annotation->m_reverse_map.put (node2, node2->annotation_uid);
>> +
>> +    if (v)
>> +      {
>> +	T *data = *v;
>> +	T *duplicate = new T();
>> +	annotation->m_map->put (node2->annotation_uid, duplicate);
>> +	annotation->call_duplication_hooks (node, node2, data);
>> +      }
>> +
>> +  }
>> +
>> +  /* Main annotation store, where annotation ID is used as key.  */
>> +  hash_map <int, T *, annotation_hashmap_traits> *m_map;
>> +
>> +  /* Inverse mapping structure used in cgraph deletion context.  */
>> +  hash_map <cgraph_node *, int> m_reverse_map;
>> +
>> +private:
>> +  /* Remove annotation for annotation UID.  */
>> +  inline void remove (int uid)
>> +  {
>> +    T *v = m_map->get (uid);
>> +
>> +    if (v)
>> +      m_map->erase (uid);
>> +  }
>> +
>> +  /* Annotation class release function called by traverse method.  */
>> +  static bool release (int const &, T * const &v, void *)
>> +  {
>> +    delete (v);
>> +    return true;
>> +  }
>> +
>> +  /* Call insertion hook for callgraph NODE.  */
>> +  inline void call_insertion_hooks (cgraph_node *node)
>> +  {
>> +    for (unsigned int i = 0; i < m_insertion_hooks.length (); i++)
>> +      m_insertion_hooks[i] (node, get_or_add (node));
>> +  }
>> +
>> +  /* Call removal hook for callgraph NODE.  */
>> +  inline void call_removal_hooks (cgraph_node *node, T *v)
>> +  {
>> +    for (unsigned int i = 0; i < m_removal_hooks.length (); i++)
>> +      m_removal_hooks[i] (node, v);
>> +  }
>> +
>> +  /* Call duplication hook for callgraph NODE.  */
>> +  inline void call_duplication_hooks (cgraph_node *node, cgraph_node *node2, T *v)
>> +  {
>> +    for (unsigned int i = 0; i < m_duplication_hooks.length (); i++)
>> +      m_duplication_hooks[i] (node, node2, v, get_or_add (node2));
>> +  }
>> +
>> +  /* List of symbol insertion hooks.  */
>> +  auto_vec <void (*) (cgraph_node *, T *)> m_insertion_hooks;
>> +  /* List of symbol removal hooks.  */
>> +  auto_vec <void (*) (cgraph_node *, T *)> m_removal_hooks;
>> +  /* List of symbol duplication hooks.  */
>> +  auto_vec <void (*) (const cgraph_node *, const cgraph_node *, T *, T *)>
>> +  m_duplication_hooks;
>> +
>> +  /* Internal annotation insertion hook pointer.  */
>> +  cgraph_node_hook_list *m_symtab_insertion_hook;
>> +  /* Internal annotation removal hook pointer.  */
>> +  cgraph_node_hook_list *m_symtab_removal_hook;
>> +  /* Internal annotation duplication hook pointer.  */
>> +  cgraph_2node_hook_list *m_symtab_duplication_hook;
>> +
>> +  /* Symbol table the annotation is registered to.  */
>> +  symbol_table *m_symtab;
>> +};
>> +
>> +#endif  /* GCC_ANNOTATION_H  */
>> diff --git a/gcc/cgraph.h b/gcc/cgraph.h
>> index a5777c2..32a770a 100644
>> --- a/gcc/cgraph.h
>> +++ b/gcc/cgraph.h
>> @@ -1219,6 +1219,8 @@ public:
>>     int count_materialization_scale;
>>     /* Unique id of the node.  */
>>     int uid;
>> +  /* Annotation unique id of the node.  */
>> +  int annotation_uid;
>>     /* ID assigned by the profiling.  */
>>     unsigned int profile_id;
>>     /* Time profiler: first run of function.  */
>> @@ -1771,6 +1773,10 @@ public:
>>     friend class cgraph_node;
>>     friend class cgraph_edge;
>>
>> +  symbol_table (): cgraph_max_annotation_uid (1)
>> +  {
>> +  }
>> +
>>     /* Initialize callgraph dump file.  */
>>     inline void
>>     initialize (void)
>> @@ -1972,6 +1978,7 @@ public:
>>
>>     int cgraph_count;
>>     int cgraph_max_uid;
>> +  int cgraph_max_annotation_uid;
>>
>>     int edges_count;
>>     int edges_max_uid;
>> @@ -2268,6 +2275,9 @@ symbol_table::create_empty (void)
>>   {
>>     cgraph_node *node = allocate_cgraph_symbol ();
>>
>> +  gcc_assert (cgraph_max_annotation_uid);
>> +  node->annotation_uid = cgraph_max_annotation_uid++;
>> +
>>     node->type = SYMTAB_FUNCTION;
>>     node->frequency = NODE_FREQUENCY_NORMAL;
>>     node->count_materialization_scale = REG_BR_PROB_BASE;
>> diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c
>> index 38f56d2..e2576b3 100644
>> --- a/gcc/ipa-inline-analysis.c
>> +++ b/gcc/ipa-inline-analysis.c
>> @@ -895,7 +895,7 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
>>     if (known_binfos_ptr)
>>       known_binfos_ptr->create (0);
>>
>> -  if (ipa_node_params_vector.exists ()
>> +  if (ipa_node_params_annotation
>>         && !e->call_stmt_cannot_inline_p
>>         && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
>>       {
>> @@ -1115,7 +1115,7 @@ inline_node_duplication_hook (struct cgraph_node *src,
>>
>>     /* When there are any replacements in the function body, see if we can figure
>>        out that something was optimized out.  */
>> -  if (ipa_node_params_vector.exists () && dst->clone.tree_map)
>> +  if (ipa_node_params_annotation && dst->clone.tree_map)
>>       {
>>         vec<size_time_entry, va_gc> *entry = info->entry;
>>         /* Use SRC parm info since it may not be copied yet.  */
>> @@ -2462,7 +2462,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
>>         calculate_dominance_info (CDI_DOMINATORS);
>>         loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
>>
>> -      if (ipa_node_params_vector.exists ())
>> +      if (ipa_node_params_annotation)
>>   	{
>>   	  parms_info = IPA_NODE_REF (node);
>>   	  nonconstant_names.safe_grow_cleared
>> @@ -2610,7 +2610,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
>>   		  nonconstant_names[SSA_NAME_VERSION (gimple_call_lhs (stmt))]
>>   		    = false_p;
>>   		}
>> -	      if (ipa_node_params_vector.exists ())
>> +	      if (ipa_node_params_annotation)
>>   		{
>>   		  int count = gimple_call_num_args (stmt);
>>   		  int i;
>> @@ -3353,7 +3353,7 @@ static void
>>   remap_edge_change_prob (struct cgraph_edge *inlined_edge,
>>   			struct cgraph_edge *edge)
>>   {
>> -  if (ipa_node_params_vector.exists ())
>> +  if (ipa_node_params_annotation)
>>       {
>>         int i;
>>         struct ipa_edge_args *args = IPA_EDGE_REF (edge);
>> @@ -3509,7 +3509,7 @@ inline_merge_summary (struct cgraph_edge *edge)
>>     else
>>       toplev_predicate = true_predicate ();
>>
>> -  if (ipa_node_params_vector.exists () && callee_info->conds)
>> +  if (ipa_node_params_annotation && callee_info->conds)
>>       {
>>         struct ipa_edge_args *args = IPA_EDGE_REF (edge);
>>         int count = ipa_get_cs_argument_count (args);
>> diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c
>> index 9ac1929..ad98467 100644
>> --- a/gcc/ipa-inline.c
>> +++ b/gcc/ipa-inline.c
>> @@ -2408,7 +2408,7 @@ pass_early_inline::execute (function *fun)
>>        it.  This may confuse ourself when early inliner decide to inline call to
>>        function clone, because function clones don't have parameter list in
>>        ipa-prop matching their signature.  */
>> -  if (ipa_node_params_vector.exists ())
>> +  if (ipa_node_params_annotation)
>>       return 0;
>>
>>   #ifdef ENABLE_CHECKING
>> diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
>> index 62db327..743d9ff 100644
>> --- a/gcc/ipa-prop.c
>> +++ b/gcc/ipa-prop.c
>> @@ -115,7 +115,8 @@ struct func_body_info
>>     unsigned int aa_walked;
>>   };
>>
>> -/* Vector where the parameter infos are actually stored. */
>> +/* Callgraph annotation where the parameter infos are actually stored. */
>> +cgraph_annotation <struct ipa_node_params> *ipa_node_params_annotation = NULL;
>>   vec<ipa_node_params> ipa_node_params_vector;
>>   /* Vector of known aggregate values in cloned nodes.  */
>>   vec<ipa_agg_replacement_value_p, va_gc> *ipa_node_agg_replacements;
>> @@ -124,9 +125,7 @@ vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
>>
>>   /* Holders of ipa cgraph hooks: */
>>   static struct cgraph_edge_hook_list *edge_removal_hook_holder;
>> -static struct cgraph_node_hook_list *node_removal_hook_holder;
>>   static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
>> -static struct cgraph_2node_hook_list *node_duplication_hook_holder;
>>   static struct cgraph_node_hook_list *function_insertion_hook_holder;
>>
>>   /* Description of a reference to an IPA constant.  */
>> @@ -3554,7 +3553,7 @@ ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
>>     bool changed;
>>     /* Do nothing if the preparation phase has not been carried out yet
>>        (i.e. during early inlining).  */
>> -  if (!ipa_node_params_vector.exists ())
>> +  if (!ipa_node_params_annotation)
>>       return false;
>>     gcc_assert (ipa_edge_args_vector);
>>
>> @@ -3594,15 +3593,21 @@ ipa_free_all_edge_args (void)
>>   /* Frees all dynamically allocated structures that the param info points
>>      to.  */
>>
>> -void
>> -ipa_free_node_params_substructures (struct ipa_node_params *info)
>> +ipa_node_params::~ipa_node_params ()
>>   {
>> -  info->descriptors.release ();
>> -  free (info->lattices);
>> +  descriptors.release ();
>> +  free (lattices);
>>     /* Lattice values and their sources are deallocated with their alocation
>>        pool.  */
>> -  info->known_vals.release ();
>> -  memset (info, 0, sizeof (*info));
>> +  known_vals.release ();
>> +
>> +  lattices = NULL;
>> +  ipcp_orig_node = NULL;
>> +  analysis_done = 0;
>> +  node_enqueued = 0;
>> +  do_clone_for_all_contexts = 0;
>> +  is_all_contexts_clone = 0;
>> +  node_dead = 0;
>>   }
>>
>>   /* Free all ipa_node_params structures.  */
>> @@ -3610,11 +3615,8 @@ ipa_free_node_params_substructures (struct ipa_node_params *info)
>>   void
>>   ipa_free_all_node_params (void)
>>   {
>> -  int i;
>> -  struct ipa_node_params *info;
>> -
>> -  FOR_EACH_VEC_ELT (ipa_node_params_vector, i, info)
>> -    ipa_free_node_params_substructures (info);
>> +  delete ipa_node_params_annotation;
>> +  ipa_node_params_annotation = NULL;
>>
>>     ipa_node_params_vector.release ();
>>   }
>> @@ -3622,7 +3624,7 @@ ipa_free_all_node_params (void)
>>   /* Set the aggregate replacements of NODE to be AGGVALS.  */
>>
>>   void
>> -ipa_set_node_agg_value_chain (struct cgraph_node *node,
>> +ipa_set_node_agg_value_chain (const struct cgraph_node *node,
>>   			      struct ipa_agg_replacement_value *aggvals)
>>   {
>>     if (vec_safe_length (ipa_node_agg_replacements)
>> @@ -3663,18 +3665,6 @@ ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
>>     ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
>>   }
>>
>> -/* Hook that is called by cgraph.c when a node is removed.  */
>> -
>> -static void
>> -ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
>> -{
>> -  /* During IPA-CP updating we can be called on not-yet analyze clones.  */
>> -  if (ipa_node_params_vector.length () > (unsigned)node->uid)
>> -    ipa_free_node_params_substructures (IPA_NODE_REF (node));
>> -  if (vec_safe_length (ipa_node_agg_replacements) > (unsigned)node->uid)
>> -    (*ipa_node_agg_replacements)[(unsigned)node->uid] = NULL;
>> -}
>> -
>>   /* Hook that is called by cgraph.c when an edge is duplicated.  */
>>
>>   static void
>> @@ -3779,18 +3769,22 @@ ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
>>       }
>>   }
>>
>> -/* Hook that is called by cgraph.c when a node is duplicated.  */
>> +/* Analyze newly added function into callgraph.  */
>>
>>   static void
>> -ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
>> -			   ATTRIBUTE_UNUSED void *data)
>> +ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
>>   {
>> -  struct ipa_node_params *old_info, *new_info;
>> -  struct ipa_agg_replacement_value *old_av, *new_av;
>> +  if (node->has_gimple_body_p ())
>> +    ipa_analyze_node (node);
>> +}
>>
>> -  ipa_check_create_node_params ();
>> -  old_info = IPA_NODE_REF (src);
>> -  new_info = IPA_NODE_REF (dst);
>> +/* Hook that is called by cgraph.c when a node is duplicated.  */
>> +
>> +void
>> +ipa_node_duplication_hook (const struct cgraph_node *src, const struct cgraph_node *dst,
>> +                          struct ipa_node_params *old_info, struct ipa_node_params *new_info)
>> +{
>> +  struct ipa_agg_replacement_value *old_av, *new_av;
>>
>>     new_info->descriptors = old_info->descriptors.copy ();
>>     new_info->lattices = NULL;
>> @@ -3817,33 +3811,19 @@ ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
>>     ipa_set_node_agg_value_chain (dst, new_av);
>>   }
>>
>> -
>> -/* Analyze newly added function into callgraph.  */
>> -
>> -static void
>> -ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
>> -{
>> -  if (node->has_gimple_body_p ())
>> -    ipa_analyze_node (node);
>> -}
>> -
>>   /* Register our cgraph hooks if they are not already there.  */
>>
>>   void
>>   ipa_register_cgraph_hooks (void)
>>   {
>> +  ipa_check_create_node_params ();
>> +
>>     if (!edge_removal_hook_holder)
>>       edge_removal_hook_holder =
>>         symtab->add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
>> -  if (!node_removal_hook_holder)
>> -    node_removal_hook_holder =
>> -      symtab->add_cgraph_removal_hook (&ipa_node_removal_hook, NULL);
>>     if (!edge_duplication_hook_holder)
>>       edge_duplication_hook_holder =
>>         symtab->add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
>> -  if (!node_duplication_hook_holder)
>> -    node_duplication_hook_holder =
>> -      symtab->add_cgraph_duplication_hook (&ipa_node_duplication_hook, NULL);
>>     function_insertion_hook_holder =
>>         symtab->add_cgraph_insertion_hook (&ipa_add_new_function, NULL);
>>   }
>> @@ -3855,12 +3835,8 @@ ipa_unregister_cgraph_hooks (void)
>>   {
>>     symtab->remove_edge_removal_hook (edge_removal_hook_holder);
>>     edge_removal_hook_holder = NULL;
>> -  symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
>> -  node_removal_hook_holder = NULL;
>>     symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
>>     edge_duplication_hook_holder = NULL;
>> -  symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
>> -  node_duplication_hook_holder = NULL;
>>     symtab->remove_cgraph_insertion_hook (function_insertion_hook_holder);
>>     function_insertion_hook_holder = NULL;
>>   }
>> @@ -5030,8 +5006,7 @@ ipa_prop_write_jump_functions (void)
>>     lto_symtab_encoder_iterator lsei;
>>     lto_symtab_encoder_t encoder;
>>
>> -
>> -  if (!ipa_node_params_vector.exists ())
>> +  if (!ipa_node_params_annotation)
>>       return;
>>
>>     ob = create_output_block (LTO_section_jump_functions);
>> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
>> index 7a06af9..6a3772d 100644
>> --- a/gcc/ipa-prop.h
>> +++ b/gcc/ipa-prop.h
>> @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.  If not see
>>   #include "vec.h"
>>   #include "cgraph.h"
>>   #include "alloc-pool.h"
>> +#include "annotation.h"
>>
>>   /* The following definitions and interfaces are used by
>>      interprocedural analyses or parameters.  */
>> @@ -359,6 +360,8 @@ struct ipcp_lattice;
>>
>>   struct ipa_node_params
>>   {
>> +  ~ipa_node_params ();
>> +
>>     /* Information about individual formal parameters that are gathered when
>>        summaries are generated. */
>>     vec<ipa_param_descriptor> descriptors;
>> @@ -473,7 +476,7 @@ struct GTY(()) ipa_agg_replacement_value
>>
>>   typedef struct ipa_agg_replacement_value *ipa_agg_replacement_value_p;
>>
>> -void ipa_set_node_agg_value_chain (struct cgraph_node *node,
>> +void ipa_set_node_agg_value_chain (const struct cgraph_node *node,
>>   				   struct ipa_agg_replacement_value *aggvals);
>>
>>   /* ipa_edge_args stores information related to a callsite and particularly its
>> @@ -519,7 +522,7 @@ ipa_get_ith_polymorhic_call_context (struct ipa_edge_args *args, int i)
>>   /* Types of vectors holding the infos.  */
>>
>>   /* Vector where the parameter infos are actually stored. */
>> -extern vec<ipa_node_params> ipa_node_params_vector;
>> +extern cgraph_annotation <ipa_node_params> *ipa_node_params_annotation;
>>   /* Vector of known aggregate values in cloned nodes.  */
>>   extern GTY(()) vec<ipa_agg_replacement_value_p, va_gc> *ipa_node_agg_replacements;
>>   /* Vector where the parameter infos are actually stored. */
>> @@ -527,7 +530,7 @@ extern GTY(()) vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
>>
>>   /* Return the associated parameter/argument info corresponding to the given
>>      node/edge.  */
>> -#define IPA_NODE_REF(NODE) (&ipa_node_params_vector[(NODE)->uid])
>> +#define IPA_NODE_REF(NODE) (ipa_node_params_annotation->get_or_add (NODE))
>>   #define IPA_EDGE_REF(EDGE) (&(*ipa_edge_args_vector)[(EDGE)->uid])
>>   /* This macro checks validity of index returned by
>>      ipa_get_param_decl_index function.  */
>> @@ -537,11 +540,15 @@ extern GTY(()) vec<ipa_edge_args, va_gc> *ipa_edge_args_vector;
>>   void ipa_create_all_node_params (void);
>>   void ipa_create_all_edge_args (void);
>>   void ipa_free_edge_args_substructures (struct ipa_edge_args *);
>> -void ipa_free_node_params_substructures (struct ipa_node_params *);
>>   void ipa_free_all_node_params (void);
>>   void ipa_free_all_edge_args (void);
>>   void ipa_free_all_structures_after_ipa_cp (void);
>>   void ipa_free_all_structures_after_iinln (void);
>> +void  ipa_node_duplication_hook (const struct cgraph_node *src,
>> +				 const struct cgraph_node *dst,
>> +				 struct ipa_node_params *old_info,
>> +				 struct ipa_node_params *new_info);
>> +
>>   void ipa_register_cgraph_hooks (void);
>>   int count_formal_params (tree fndecl);
>>
>> @@ -551,11 +558,11 @@ int count_formal_params (tree fndecl);
>>   static inline void
>>   ipa_check_create_node_params (void)
>>   {
>> -  if (!ipa_node_params_vector.exists ())
>> -    ipa_node_params_vector.create (symtab->cgraph_max_uid);
>> -
>> -  if (ipa_node_params_vector.length () <= (unsigned) symtab->cgraph_max_uid)
>> -    ipa_node_params_vector.safe_grow_cleared (symtab->cgraph_max_uid + 1);
>> +  if (!ipa_node_params_annotation)
>> +    {
>> +      ipa_node_params_annotation = new cgraph_annotation <ipa_node_params> (symtab);
>> +      ipa_node_params_annotation->add_duplication_hook <ipa_node_duplication_hook> ();
>> +    }
>>   }
>>
>>   /* This function ensures the array of edge arguments infos is big enough to
>> @@ -582,7 +589,7 @@ ipa_edge_args_info_available_for_edge_p (struct cgraph_edge *edge)
>>   /* Return the aggregate replacements for NODE, if there are any.  */
>>
>>   static inline struct ipa_agg_replacement_value *
>> -ipa_get_agg_replacements_for_node (struct cgraph_node *node)
>> +ipa_get_agg_replacements_for_node (const struct cgraph_node *node)
>>   {
>>     if ((unsigned) node->uid >= vec_safe_length (ipa_node_agg_replacements))
>>       return NULL;
>> diff --git a/gcc/toplev.c b/gcc/toplev.c
>> index f7a5035..5e31ec2 100644
>> --- a/gcc/toplev.c
>> +++ b/gcc/toplev.c
>> @@ -1176,7 +1176,7 @@ general_init (const char *argv0)
>>     /* Create the singleton holder for global state.
>>        Doing so also creates the pass manager and with it the passes.  */
>>     g = new gcc::context ();
>> -  symtab = ggc_cleared_alloc <symbol_table> ();
>> +  symtab = new (ggc_cleared_alloc <symbol_table> ()) symbol_table ();
>>
>>     statistics_early_init ();
>>     finish_params ();
>


[-- Attachment #2: cgraph-annotation-2.patch.bz2 --]
[-- Type: application/x-bzip, Size: 18816 bytes --]