Re: [PATCH 2/4] New data structure for cgraph_summary introduced.

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

On 11/14/2014 03:04 PM, Martin Liška wrote:
> On 11/13/2014 04:50 PM, Jan Hubicka wrote:
> > > gcc/ChangeLog:
> > >
> > > 2014-11-12  Martin Liska  <mliska@suse.cz>
> > >
> > >     * Makefile.in: New object file is added.
> > >     * cgraph.h (symbol_table::allocate_cgraph_symbol): Summary UID
> > >     is filled up.
> > >     * cgraph_summary.c: New file.
> > >     * cgraph_summary.h: New file.
> >
> > Since I am trying to get rid of the cgraph prefixes for symbols (keep it for
> > the graph only) and the summaries can be annotated to variables too. Even if it
> > not necessarily supported by your current implementation, lets keep API
> > prepared for it. So I would call it symtab-summary.* for source files and
> > symtab_summary for base type  (probably function_summary for annotating
> > functions/cgraph_edge_summary for annotating edges?)
>
> Hello.
>
> I followed your remarks, new class is called function_summary and is located
> in symbol-summary.h.
> > > diff --git a/gcc/cgraph.h b/gcc/cgraph.h
> > > index e2becb9..588b6d5 100644
> > > --- a/gcc/cgraph.h
> > > +++ b/gcc/cgraph.h
> > > @@ -1225,6 +1225,8 @@ public:
> > >     int count_materialization_scale;
> > >     /* Unique id of the node.  */
> > >     int uid;
> > > +  /* Summary unique id of the node.  */
> > > +  int summary_uid;
> >
> > What makes summary_uid better than uid?
>
> Because cgraph_node::uid is not a unique ID, it's recycled. As I can see,
> there are two remaining usages of the fact that cgraph::uid are quite consecutive:
>
> a) node_growth_cache vector is resized according to cgraph_max_uid
> b) lto-partition.c: lto_balanced_map
>
> If we change ipa-related stuff to annotations and lto_balanced_map with be rewritten,
> we can finally unify uid and summary_uid. As Martin correctly pointed out, we should
> unify cgraph_node dumps, we combine uid and order.
>
> > > diff --git a/gcc/cgraph_summary.c b/gcc/cgraph_summary.c
> > > new file mode 100644
> > > index 0000000..9af1d7e
> > > --- /dev/null
> > > +++ b/gcc/cgraph_summary.c
> >
> > And why do we need this file?  It will need license header if really needed.
>
> Sure, the file can be removed.
>
> Martin
>
> > The implementation seems sane - I will check the actual uses :)
> > Please send the updated patch though.
> >
> > Honza

Hello.

There's v3 of the patch.

Martin

>From 89b6fb0f599944b564726947b33a7be214dd0f74 Mon Sep 17 00:00:00 2001
From: mliska <mliska@suse.cz>
Date: Thu, 13 Nov 2014 15:11:05 +0100
Subject: [PATCH 1/3] New data structure for function_summary introduced.

gcc/ChangeLog:

2014-11-12  Martin Liska  <mliska@suse.cz>

	* cgraph.h (symbol_table::allocate_cgraph_symbol): Summary UID
	is filled up.
	* symbol-summary.h: New file.
	* gengtype.c (open_base_files): Add symbol-summary.h.
	* toplev.c (general_init): Call constructor of symbol_table.
---
 gcc/cgraph.h         |   8 ++
 gcc/gengtype.c       |   4 +-
 gcc/symbol-summary.h | 317 +++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/toplev.c         |   3 +-
 4 files changed, 329 insertions(+), 3 deletions(-)
 create mode 100644 gcc/symbol-summary.h

diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index e2becb9..588b6d5 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -1225,6 +1225,8 @@ public:
   int count_materialization_scale;
   /* Unique id of the node.  */
   int uid;
+  /* Summary unique id of the node.  */
+  int summary_uid;
   /* ID assigned by the profiling.  */
   unsigned int profile_id;
   /* Time profiler: first run of function.  */
@@ -1786,6 +1788,10 @@ public:
   friend class cgraph_node;
   friend class cgraph_edge;
 
+  symbol_table (): cgraph_max_summary_uid (1)
+  {
+  }
+
   /* Initialize callgraph dump file.  */
   void initialize (void);
 
@@ -1982,6 +1988,7 @@ public:
 
   int cgraph_count;
   int cgraph_max_uid;
+  int cgraph_max_summary_uid;
 
   int edges_count;
   int edges_max_uid;
@@ -2310,6 +2317,7 @@ symbol_table::allocate_cgraph_symbol (void)
       node->uid = cgraph_max_uid++;
     }
 
+  node->summary_uid = cgraph_max_summary_uid++;
   return node;
 }
 
diff --git a/gcc/gengtype.c b/gcc/gengtype.c
index fac83ee..0161004 100644
--- a/gcc/gengtype.c
+++ b/gcc/gengtype.c
@@ -1842,8 +1842,8 @@ open_base_files (void)
       "tree-ssa-loop-niter.h", "tree-into-ssa.h", "tree-dfa.h", 
       "tree-ssa.h", "reload.h", "cpp-id-data.h", "tree-chrec.h",
       "except.h", "output.h",  "cfgloop.h", "target.h", "lto-streamer.h",
-      "target-globals.h", "ipa-ref.h", "cgraph.h", "ipa-prop.h", 
-      "ipa-inline.h", "dwarf2out.h", NULL
+      "target-globals.h", "ipa-ref.h", "cgraph.h", "symbol-summary.h",
+      "ipa-prop.h", "ipa-inline.h", "dwarf2out.h", NULL
     };
     const char *const *ifp;
     outf_p gtype_desc_c;
diff --git a/gcc/symbol-summary.h b/gcc/symbol-summary.h
new file mode 100644
index 0000000..039d052
--- /dev/null
+++ b/gcc/symbol-summary.h
@@ -0,0 +1,317 @@
+/* Callgraph summary data structure.
+   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_SYMBOL_SUMMARY_H
+#define GCC_SYMBOL_SUMMARY_H
+
+#define SYMBOL_SUMMARY_DELETED_VALUE -1
+#define SYMBOL_SUMMARY_EMPTY_VALUE 0
+
+/* Following class enforces to use pointer type as function_summary
+   template argument.  */
+
+template <class T>
+class function_summary
+{
+private:
+  function_summary();
+};
+
+template <class T>
+class GTY((user)) function_summary <T *>
+{
+public:
+  /* Default construction takes SYMTAB as an argument.  */
+  function_summary (symbol_table *symtab, bool ggc = false): m_ggc (ggc),
+    m_insertion_enabled (true), m_symtab (symtab)
+  {
+    cgraph_node *node;
+
+    FOR_EACH_FUNCTION (node)
+    {
+      gcc_assert (node->summary_uid > 0);
+    }
+
+    m_map = new hash_map<int, T*, summary_hashmap_traits>(13, m_ggc);
+
+    m_symtab_insertion_hook =
+      symtab->add_cgraph_insertion_hook
+      (function_summary::symtab_insertion, this);
+
+    m_symtab_removal_hook =
+      symtab->add_cgraph_removal_hook
+      (function_summary::symtab_removal, this);
+    m_symtab_duplication_hook =
+      symtab->add_cgraph_duplication_hook
+      (function_summary::symtab_duplication, this);
+  }
+
+  /* Destructor.  */
+  virtual ~function_summary ()
+  {
+    release ();
+  }
+
+  /* Release method that can be called for GTY purpose.  */
+  void release ()
+  {
+    if (m_symtab_insertion_hook)
+      m_symtab->remove_cgraph_insertion_hook (m_symtab_insertion_hook);
+
+    if (m_symtab_removal_hook)
+      m_symtab->remove_cgraph_removal_hook (m_symtab_removal_hook);
+
+    if (m_symtab_duplication_hook)
+      m_symtab->remove_cgraph_duplication_hook (m_symtab_duplication_hook);
+
+    m_symtab_insertion_hook = NULL;
+    m_symtab_removal_hook = NULL;
+    m_symtab_duplication_hook = NULL;
+
+    if (!m_ggc)
+      m_map->traverse <void *, function_summary::release> (NULL);
+  }
+
+  /* Traverses all summarys 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);
+  }
+
+  /* Basic implementation of insert operation.  */
+  virtual void insert (cgraph_node *, T *) {}
+
+  /* Basic implementation of removal operation.  */
+  virtual void remove (cgraph_node *, T *) {}
+
+  /* Basic implementation of duplication operation.  */
+  virtual void duplicate (cgraph_node *, cgraph_node *, T *, T *) {}
+
+  /* Allocates new data that are stored within map.  */
+  T* allocate_new ()
+  {
+    return m_ggc ? new (ggc_alloc <T> ()) T() : new T () ;
+  }
+
+  /* Getter for summary callgraph ID.  */
+  T* get (int uid)
+  {
+    T **v = m_map->get (uid);
+    if (!v)
+      {
+	T *new_value = allocate_new ();
+	m_map->put (uid, new_value);
+
+	v = &new_value;
+      }
+
+    return *v;
+  }
+
+  /* Getter for summary callgraph node pointer.  */
+  T* get (cgraph_node *node)
+  {
+    return get (node->summary_uid);
+  }
+
+  /* Getter operator for summary callgraph ID.  */
+  T* operator[] (int uid)
+  {
+    return get (uid);
+  }
+
+  /* Getter operator for summary callgraph node pointer.  */
+  T* operator[] (cgraph_node *node)
+  {
+    return get (node);
+  }
+
+  /* Return number of elements handled by data structure.  */
+  size_t elements ()
+  {
+    return m_map->elements ();
+  }
+
+  /* Enable insertion operation that is triggered if a new
+     cgraph_node is inserted.  */
+  void enable_insertion_hook ()
+  {
+    m_insertion_enabled = true;
+  }
+
+  /* Enable insertin hook invocation.  */
+  void disable_insertion_hook ()
+  {
+    m_insertion_enabled = false;
+  }
+
+  /* Symbol insertion hook that is registered to symbol table.  */
+  static void symtab_insertion (cgraph_node *node, void *data)
+  {
+    function_summary *summary = (function_summary <T *> *) (data);
+
+    if (summary->m_insertion_enabled)
+      summary->insert (node, summary->get (node));
+  }
+
+  /* Symbol removal hook that is registered to symbol table.  */
+  static void symtab_removal (cgraph_node *node, void *data)
+  {
+    gcc_assert (node->summary_uid);
+    function_summary *summary = (function_summary <T *> *) (data);
+
+    int summary_uid = node->summary_uid;
+    T **v = summary->m_map->get (summary_uid);
+
+    if (v)
+      {
+	summary->remove (node, *v);
+
+	if (!summary->m_ggc)
+	  delete (*v);
+      }
+
+    if (summary->m_map->get (summary_uid))
+      summary->m_map->remove (summary_uid);
+  }
+
+  /* Symbol duplication hook that is registered to symbol table.  */
+  static void symtab_duplication (cgraph_node *node, cgraph_node *node2,
+				  void *data)
+  {
+    function_summary *summary = (function_summary <T *> *) (data);
+    T **v = summary->m_map->get (node->summary_uid);
+
+    gcc_assert (node2->summary_uid > 0);
+
+    if (v)
+      {
+	T *data = *v;
+	T *duplicate = summary->allocate_new ();
+	summary->m_map->put (node2->summary_uid, duplicate);
+	summary->duplicate (node, node2, data, (summary->get (node2)));
+      }
+  }
+
+protected:
+  /* Indicatation if we use ggc summary.  */
+  bool m_ggc;
+
+private:
+  struct summary_hashmap_traits: default_hashmap_traits
+  {
+    static
+    hashval_t hash (const int v)
+    {
+      return (hashval_t)v;
+    }
+
+    template<typename Type>
+    static
+    bool is_deleted (Type &e)
+    {
+      return e.m_key == SYMBOL_SUMMARY_DELETED_VALUE;
+    }
+
+    template<typename Type>
+    static
+    bool is_empty (Type &e)
+    {
+      return e.m_key == SYMBOL_SUMMARY_EMPTY_VALUE;
+    }
+
+    template<typename Type>
+    static
+    void mark_deleted (Type &e)
+    {
+      e.m_key = SYMBOL_SUMMARY_DELETED_VALUE;
+    }
+
+    template<typename Type>
+    static
+    void mark_empty (Type &e)
+    {
+      e.m_key = SYMBOL_SUMMARY_EMPTY_VALUE;
+    }
+  };
+
+  /* Remove summary for summary UID.  */
+  void remove (int uid)
+  {
+    T *v = m_map->get (uid);
+
+    if (v)
+      m_map->erase (uid);
+  }
+
+  /* Summary class release function called by traverse method.  */
+  static bool release (int const &, T * const &v, void *)
+  {
+    delete (v);
+    return true;
+  }
+
+  /* Main summary store, where summary ID is used as key.  */
+  hash_map <int, T *, summary_hashmap_traits> *m_map;
+  /* Internal summary insertion hook pointer.  */
+  cgraph_node_hook_list *m_symtab_insertion_hook;
+  /* Internal summary removal hook pointer.  */
+  cgraph_node_hook_list *m_symtab_removal_hook;
+  /* Internal summary duplication hook pointer.  */
+  cgraph_2node_hook_list *m_symtab_duplication_hook;
+  /* Indicates if insertion hook is enabled.  */
+  bool m_insertion_enabled;
+  /* Symbol table the summary is registered to.  */
+  symbol_table *m_symtab;
+
+  template <typename U> friend void gt_ggc_mx (function_summary <U *> * const &);
+  template <typename U> friend void gt_pch_nx (function_summary <U *> * const &);
+  template <typename U> friend void gt_pch_nx (function_summary <U *> * const &,
+      gt_pointer_operator, void *);
+};
+
+template <typename T>
+void
+gt_ggc_mx(function_summary<T *>* const &summary)
+{
+  if (summary->m_ggc)
+    gt_ggc_mx (summary->m_map);
+}
+
+template <typename T>
+void
+gt_pch_nx(function_summary<T *>* const &summary)
+{
+  if (summary->m_ggc)
+    gt_pch_nx (summary->m_map);
+}
+
+template <typename T>
+void
+gt_pch_nx(function_summary<T *>* const& summary, gt_pointer_operator op,
+	  void *cookie)
+{
+  if (summary->m_map)
+    gt_pch_nx (summary->m_map, op, cookie);
+}
+
+#endif  /* GCC_SYMBOL_SUMMARY_H  */
diff --git a/gcc/toplev.c b/gcc/toplev.c
index aa1653e..b0f5b11 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -93,6 +93,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "dwarf2out.h"
 #include "bitmap.h"
 #include "ipa-reference.h"
+#include "symbol-summary.h"
 #include "ipa-prop.h"
 #include "gcse.h"
 #include "insn-codes.h"
@@ -1209,7 +1210,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 ();
-- 
2.1.2