diff mbox

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

Message ID 54982FAF.4080407@suse.cz
State New
Headers show

Commit Message

Martin Liška Dec. 22, 2014, 2:50 p.m. UTC 
On 12/18/2014 08:40 PM, Jan Hubicka wrote:
>> 2014-12-08  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 | 281 +++++++++++++++++++++++++++++++++++++++++++++++++++
>>   gcc/toplev.c         |   3 +-
>>   4 files changed, 293 insertions(+), 3 deletions(-)
>>   create mode 100644 gcc/symbol-summary.h
>>
>> diff --git a/gcc/cgraph.h b/gcc/cgraph.h
>> index a5c5f56..1664bd7 100644
>> --- a/gcc/cgraph.h
>> +++ b/gcc/cgraph.h
>> @@ -1237,6 +1237,8 @@ public:
>>     int count_materialization_scale;
>>     /* Unique id of the node.  */
>>     int uid;
>> +  /* Summary unique id of the node.  */
>> +  int summary_uid;
>
> Hmm, can't we just use uid here?  I guess the only difference is that summary
> uid is not kept dense, unlike the uid.
> This should not propagate into much of trouble simply because the summary datastructure
> should safely remove the summaires via removal hook.

Hello.

There's patch I've been just testing. It removes summary_uid and uid is going to be
really unique. I tested the change on Inkscape WPA, and there's time difference in level
of < 1%.

Ready for trunk after proper testing?
Thanks,
Martin

>> +
>> +/* We want to pass just pointer types as argument for function_summary
>> +   template class.  */
>> +
>> +template <class T>
>> +class function_summary
>> +{
>> +private:
>> +  function_summary();
>> +};
>> +
>> +template <class T>
>> +class GTY((user)) function_summary <T *>
>
> Eventually I would like this to allow attaching summaries to variables (and symbols in general),
> too. But currently we do not have use for it, so we can care about this later.
>
> The patch is OK.  Preferrably with summary_uid replaced by uid if it is easily doable.
>
> Honza
>

Comments

Martin Liška Jan. 14, 2015, 3:09 p.m. UTC | #1 
On 12/22/2014 03:50 PM, Martin Liška wrote:
> On 12/18/2014 08:40 PM, Jan Hubicka wrote:
>>> 2014-12-08  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 | 281 +++++++++++++++++++++++++++++++++++++++++++++++++++
>>>   gcc/toplev.c         |   3 +-
>>>   4 files changed, 293 insertions(+), 3 deletions(-)
>>>   create mode 100644 gcc/symbol-summary.h
>>>
>>> diff --git a/gcc/cgraph.h b/gcc/cgraph.h
>>> index a5c5f56..1664bd7 100644
>>> --- a/gcc/cgraph.h
>>> +++ b/gcc/cgraph.h
>>> @@ -1237,6 +1237,8 @@ public:
>>>     int count_materialization_scale;
>>>     /* Unique id of the node.  */
>>>     int uid;
>>> +  /* Summary unique id of the node.  */
>>> +  int summary_uid;
>>
>> Hmm, can't we just use uid here?  I guess the only difference is that summary
>> uid is not kept dense, unlike the uid.
>> This should not propagate into much of trouble simply because the summary datastructure
>> should safely remove the summaires via removal hook.
>
> Hello.
>
> There's patch I've been just testing. It removes summary_uid and uid is going to be
> really unique. I tested the change on Inkscape WPA, and there's time difference in level
> of < 1%.
>
> Ready for trunk after proper testing?
> Thanks,
> Martin
>
>>> +
>>> +/* We want to pass just pointer types as argument for function_summary
>>> +   template class.  */
>>> +
>>> +template <class T>
>>> +class function_summary
>>> +{
>>> +private:
>>> +  function_summary();
>>> +};
>>> +
>>> +template <class T>
>>> +class GTY((user)) function_summary <T *>
>>
>> Eventually I would like this to allow attaching summaries to variables (and symbols in general),
>> too. But currently we do not have use for it, so we can care about this later.
>>
>> The patch is OK.  Preferrably with summary_uid replaced by uid if it is easily doable.
>>
>> Honza
>>
>

PING.

Thanks,
Martin
diff mbox

Patch

From 852166518eedaa75562ad8e8324a8dfd25e2b7ff Mon Sep 17 00:00:00 2001
From: mliska <mliska@suse.cz>
Date: Fri, 19 Dec 2014 15:10:27 +0100
Subject: [PATCH] Call graph: summary_uid is removed.

gcc/ChangeLog:

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

	* cgraph.h (symbol_table::allocate_cgraph_symbol):
	Replace cgraph_max_summary_uid with cgraph_max_uid.
	* passes.c (struct cgraph_order_traits): New structure.
	(remove_cgraph_node_from_order): Replace int* with hash_map<int, int>.
	(do_per_function_toporder): Likewise.
	* symbol-summary.h: Change cgraph_node::symbol_uid with uid that
	is going to be really unique and not recycled.

gcc/lto/ChangeLog:

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

	* lto-partition.c (lto_balanced_map): Replace array with
	vec data structure.
---
 gcc/cgraph.h            | 10 ++--------
 gcc/lto/lto-partition.c | 11 ++++++-----
 gcc/passes.c            | 44 +++++++++++++++++++++++++++++++++++---------
 gcc/symbol-summary.h    | 18 +++++++++---------
 4 files changed, 52 insertions(+), 31 deletions(-)

diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index 0cff779..10f60ad 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -1255,8 +1255,6 @@  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.  */
@@ -1839,7 +1837,7 @@  public:
   friend class cgraph_node;
   friend class cgraph_edge;
 
-  symbol_table (): cgraph_max_summary_uid (1)
+  symbol_table (): cgraph_max_uid (1)
   {
   }
 
@@ -2039,7 +2037,6 @@  public:
 
   int cgraph_count;
   int cgraph_max_uid;
-  int cgraph_max_summary_uid;
 
   int edges_count;
   int edges_max_uid;
@@ -2363,12 +2360,9 @@  symbol_table::allocate_cgraph_symbol (void)
       free_nodes = NEXT_FREE_NODE (node);
     }
   else
-    {
       node = ggc_cleared_alloc<cgraph_node> ();
-      node->uid = cgraph_max_uid++;
-    }
 
-  node->summary_uid = cgraph_max_summary_uid++;
+  node->uid = cgraph_max_uid++;
   return node;
 }
 
diff --git a/gcc/lto/lto-partition.c b/gcc/lto/lto-partition.c
index 160b910..6c61102 100644
--- a/gcc/lto/lto-partition.c
+++ b/gcc/lto/lto-partition.c
@@ -449,7 +449,8 @@  lto_balanced_map (int n_lto_partitions)
 {
   int n_nodes = 0;
   int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0;
-  struct cgraph_node **order = XNEWVEC (cgraph_node *, symtab->cgraph_max_uid);
+
+  auto_vec<cgraph_node *> order;
   auto_vec<cgraph_node *> noreorder;
   auto_vec<varpool_node *> varpool_order;
   int i;
@@ -475,17 +476,19 @@  lto_balanced_map (int n_lto_partitions)
 	if (node->no_reorder)
 	  noreorder.safe_push (node);
 	else
-	  order[n_nodes++] = node;
+	  order.safe_push (node);
 	if (!node->alias)
 	  total_size += inline_summaries->get (node)->size;
       }
 
+  n_nodes = order.length ();
+
   /* Streaming works best when the source units do not cross partition
      boundaries much.  This is because importing function from a source
      unit tends to import a lot of global trees defined there.  We should
      get better about minimizing the function bounday, but until that
      things works smoother if we order in source order.  */
-  qsort (order, n_nodes, sizeof (struct cgraph_node *), node_cmp);
+  order.qsort(node_cmp);
   noreorder.qsort (node_cmp);
 
   if (symtab->dump_file)
@@ -772,8 +775,6 @@  lto_balanced_map (int n_lto_partitions)
   while (noreorder_pos < (int)noreorder.length ())
     next_nodes.safe_push (noreorder[noreorder_pos++]);
   add_sorted_nodes (next_nodes, partition);
-
-  free (order);
 }
 
 /* Mangle NODE symbol name into a local name.  
diff --git a/gcc/passes.c b/gcc/passes.c
index 3f9f7df..436b4cb 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -1646,6 +1646,33 @@  do_per_function (void (*callback) (function *, void *data), void *data)
 static int nnodes;
 static GTY ((length ("nnodes"))) cgraph_node **order;
 
+struct cgraph_order_traits : default_hashmap_traits
+{
+  template<typename T>
+  static bool
+  is_empty (T &e)
+  {
+    return e.m_key == INT_MIN;
+  }
+
+  template<typename  T>
+  static bool
+  is_deleted (T &e)
+  {
+    return e.m_key == (INT_MIN + 1);
+  }
+
+  template<typename T> static void mark_empty (T &e) { e.m_key = INT_MIN; }
+
+  template<typename T>
+  static void
+  mark_deleted (T &e)
+  {
+    e.m_key = INT_MIN + 1;
+  }
+};
+
+
 /* Hook called when NODE is removed and therefore should be
    excluded from order vector.  DATA is an array of integers.
    DATA[0] holds max index it may be accessed by.  For cgraph
@@ -1654,12 +1681,13 @@  static GTY ((length ("nnodes"))) cgraph_node **order;
 static void
 remove_cgraph_node_from_order (cgraph_node *node, void *data)
 {
-  int *order_idx = (int *)data;
+  hash_map<int, int, cgraph_order_traits> *order_idx_map =
+    (hash_map <int, int, cgraph_order_traits> *)data;
 
-  if (node->uid >= order_idx[0])
+  if (node->uid >= *order_idx_map->get (0))
     return;
 
-  int idx = order_idx[node->uid + 1];
+  int idx = *order_idx_map->get (node->uid + 1);
   if (idx >= 0 && idx < nnodes && order[idx] == node)
     order[idx] = NULL;
 }
@@ -1678,22 +1706,20 @@  do_per_function_toporder (void (*callback) (function *, void *data), void *data)
   else
     {
       cgraph_node_hook_list *hook;
-      int *order_idx;
       gcc_assert (!order);
       order = ggc_vec_alloc<cgraph_node *> (symtab->cgraph_count);
 
-      order_idx = XALLOCAVEC (int, symtab->cgraph_max_uid + 1);
-      memset (order_idx + 1, -1, sizeof (int) * symtab->cgraph_max_uid);
-      order_idx[0] = symtab->cgraph_max_uid;
+      hash_map<int, int, cgraph_order_traits> order_idx_map;
+      order_idx_map.put (0, symtab->cgraph_max_uid);
 
       nnodes = ipa_reverse_postorder (order);
       for (i = nnodes - 1; i >= 0; i--)
 	{
 	  order[i]->process = 1;
-	  order_idx[order[i]->uid + 1] = i;
+	  order_idx_map.put (order[i]->uid + 1, i);
 	}
       hook = symtab->add_cgraph_removal_hook (remove_cgraph_node_from_order,
-					      order_idx);
+					      &order_idx_map);
       for (i = nnodes - 1; i >= 0; i--)
 	{
 	  /* Function could be inlined and removed as unreachable.  */
diff --git a/gcc/symbol-summary.h b/gcc/symbol-summary.h
index d001f64..ec1dc9c 100644
--- a/gcc/symbol-summary.h
+++ b/gcc/symbol-summary.h
@@ -44,7 +44,7 @@  public:
 
     FOR_EACH_FUNCTION (node)
     {
-      gcc_checking_assert (node->summary_uid > 0);
+      gcc_checking_assert (node->uid > 0);
     }
 #endif
 
@@ -109,7 +109,7 @@  public:
   /* Getter for summary callgraph node pointer.  */
   T* get (cgraph_node *node)
   {
-    return get (node->summary_uid);
+    return get (node->uid);
   }
 
   /* Return number of elements handled by data structure.  */
@@ -142,11 +142,11 @@  public:
   /* Symbol removal hook that is registered to symbol table.  */
   static void symtab_removal (cgraph_node *node, void *data)
   {
-    gcc_checking_assert (node->summary_uid);
+    gcc_checking_assert (node->uid);
     function_summary *summary = (function_summary <T *> *) (data);
 
-    int summary_uid = node->summary_uid;
-    T **v = summary->m_map.get (summary_uid);
+    int uid = node->uid;
+    T **v = summary->m_map.get (uid);
 
     if (v)
       {
@@ -155,7 +155,7 @@  public:
 	if (!summary->m_ggc)
 	  delete (*v);
 
-	summary->m_map.remove (summary_uid);
+	summary->m_map.remove (uid);
       }
   }
 
@@ -164,16 +164,16 @@  public:
 				  void *data)
   {
     function_summary *summary = (function_summary <T *> *) (data);
-    T **v = summary->m_map.get (node->summary_uid);
+    T **v = summary->m_map.get (node->uid);
 
-    gcc_checking_assert (node2->summary_uid > 0);
+    gcc_checking_assert (node2->uid > 0);
 
     if (v)
       {
 	/* This load is necessary, because we insert a new value!  */
 	T *data = *v;
 	T *duplicate = summary->allocate_new ();
-	summary->m_map.put (node2->summary_uid, duplicate);
+	summary->m_map.put (node2->uid, duplicate);
 	summary->duplicate (node, node2, data, duplicate);
       }
   }
-- 
2.1.2