Make TOPN counter dynamically allocated.

gcc/ChangeLog:

	* coverage.c (get_coverage_counts): Skip sanity check for TOP N counters
	as they have variable number of counters.
	* gcov-dump.c (main): Add new option -r.
	(print_usage): Likewise.
	(tag_counters): All new raw format.
	* gcov-io.h (struct gcov_kvp): New.
	(GCOV_TOPN_VALUES): Remove.
	(GCOV_TOPN_VALUES_COUNTERS): Likewise.
	(GCOV_TOPN_MEM_COUNTERS): New.
	(GCOV_TOPN_DISK_COUNTERS): Likewise.
	(GCOV_TOPN_MAXIMUM_TRACKED_VALUES): Likewise.
	* ipa-profile.c (ipa_profile_generate_summary): Use
	GCOV_TOPN_MAXIMUM_TRACKED_VALUES.
	(ipa_profile_write_edge_summary): Likewise.
	(ipa_profile_read_edge_summary): Likewise.
	(ipa_profile): Remove usage of GCOV_TOPN_VALUES.
	* profile.c (sort_hist_values): Sort variable number
	of counters.
	(compute_value_histograms): Special case for TOP N counters
	that have dynamic number of key-value pairs.
	* value-prof.c (dump_histogram_value): Dump variable number
	of key-value pairs.
	(stream_in_histogram_value): Stream in variable number
	of key-value pairs for TOP N counter.
	(get_nth_most_common_value): Deal with variable number
	of key-value pairs.
	(dump_ic_profile): Use GCOV_TOPN_MAXIMUM_TRACKED_VALUES
	for loop iteration.
	(gimple_find_values_to_profile): Set GCOV_TOPN_MEM_COUNTERS
	to n_counters.
	* doc/gcov-dump.texi: Document new -r option.

libgcc/ChangeLog:

	* libgcov-driver.c (prune_topn_counter): Remove.
	(prune_counters): Likewise.
	(merge_one_data): Special case TOP N counters
	as they have variable length.
	(write_top_counters): New.
	(write_one_data): Special case TOP N.
	(dump_one_gcov): Do not prune TOP N counters.
	* libgcov-merge.c (merge_topn_values_set): Remove.
	(__gcov_merge_topn): Use gcov_topn_add_value.
	* libgcov-profiler.c (__gcov_topn_values_profiler_body):
	Likewise here.
	* libgcov.h (gcov_counter_add): New.
	(gcov_counter_set_if_null): Likewise.
	(gcov_topn_add_value): New.

4 files changed, 162 insertions, 184 deletions

diff --git a/libgcc/libgcov-driver.c b/libgcc/libgcov-driver.c
index fb32073..8348d9f 100644
--- a/libgcc/libgcov-driver.c
+++ b/libgcc/libgcov-driver.c
@@ -213,51 +213,6 @@ static struct gcov_fn_buffer *fn_buffer;
 /* Including system dependent components. */
 #include "libgcov-driver-system.c"
 
-/* Prune TOP N value COUNTERS.  It's needed in order to preserve
-   reproducibility of builds.  */
-
-static void
-prune_topn_counter (gcov_type *counters, gcov_type all)
-{
-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    if (counters[2 * i + 1] < all)
-      {
-	counters[2 * i] = 0;
-	counters[2 * i + 1] = 0;
-      }
-}
-
-/* Prune counters so that they are ready to store or merge.  */
-
-static void
-prune_counters (struct gcov_info *gi)
-{
-  for (unsigned i = 0; i < gi->n_functions; i++)
-    {
-      const struct gcov_fn_info *gfi = gi->functions[i];
-      const struct gcov_ctr_info *ci = gfi->ctrs;
-
-      for (unsigned j = 0; j < GCOV_COUNTERS; j++)
-	{
-	  if (gi->merge[j] == NULL)
-	    continue;
-
-	  if (gi->merge[j] == __gcov_merge_topn)
-	    {
-	      gcc_assert (!(ci->num % GCOV_TOPN_VALUES_COUNTERS));
-	      for (unsigned k = 0; k < (ci->num / GCOV_TOPN_VALUES_COUNTERS);
-		   k++)
-		{
-		  gcov_type *counters
-		    = ci->values + (k * GCOV_TOPN_VALUES_COUNTERS);
-		  prune_topn_counter (counters + 1, *counters);
-		}
-	    }
-	  ci++;
-	}
-    }
-}
-
 /* This function merges counters in GI_PTR to an existing gcda file.
    Return 0 on success.
    Return -1 on error. In this case, caller will goto read_fatal.  */
@@ -346,16 +301,18 @@ merge_one_data (const char *filename,
           if (!merge)
             continue;
 
-          tag = gcov_read_unsigned ();
-          length = gcov_read_unsigned ();
-          if (tag != GCOV_TAG_FOR_COUNTER (t_ix)
-              || length != GCOV_TAG_COUNTER_LENGTH (ci_ptr->num))
-            goto read_mismatch;
-          (*merge) (ci_ptr->values, ci_ptr->num);
-          ci_ptr++;
-        }
+	  tag = gcov_read_unsigned ();
+	  length = gcov_read_unsigned ();
+	  if (tag != GCOV_TAG_FOR_COUNTER (t_ix)
+	      || (length != GCOV_TAG_COUNTER_LENGTH (ci_ptr->num)
+		  && t_ix != GCOV_COUNTER_V_TOPN
+		  && t_ix != GCOV_COUNTER_V_INDIR))
+	    goto read_mismatch;
+	  (*merge) (ci_ptr->values, ci_ptr->num);
+	  ci_ptr++;
+	}
       if ((error = gcov_is_error ()))
-        goto read_error;
+	goto read_error;
     }
 
   if (tag)
@@ -374,6 +331,37 @@ read_error:
   return -1;
 }
 
+/* Store all TOP N counters where each has a dynamic length.  */
+
+static void
+write_top_counters (const struct gcov_ctr_info *ci_ptr,
+		    unsigned t_ix,
+		    gcov_unsigned_t n_counts)
+{
+  unsigned counters = n_counts / GCOV_TOPN_MEM_COUNTERS;
+  gcc_assert (n_counts % GCOV_TOPN_MEM_COUNTERS == 0);
+  unsigned pair_total = 0;
+  for (unsigned i = 0; i < counters; i++)
+    pair_total += ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i + 1];
+  unsigned disk_size = GCOV_TOPN_DISK_COUNTERS * counters + 2 * pair_total;
+  gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix),
+			 GCOV_TAG_COUNTER_LENGTH (disk_size));
+
+  for (unsigned i = 0; i < counters; i++)
+    {
+      gcov_type pair_count = ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i + 1];
+      gcov_write_counter (ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i]);
+      gcov_write_counter (pair_count);
+      for (struct gcov_kvp *node
+	   = (struct gcov_kvp *)ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i + 2];
+	   node != NULL; node = node->next)
+	{
+	  gcov_write_counter (node->value);
+	  gcov_write_counter (node->count);
+	}
+    }
+}
+
 /* Write counters in GI_PTR and the summary in PRG to a gcda file. In
    the case of appending to an existing file, SUMMARY_POS will be non-zero.
    We will write the file starting from SUMMAY_POS.  */
@@ -433,11 +421,18 @@ write_one_data (const struct gcov_info *gi_ptr,
             continue;
 
           n_counts = ci_ptr->num;
-          gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix),
-                                 GCOV_TAG_COUNTER_LENGTH (n_counts));
-          c_ptr = ci_ptr->values;
-          while (n_counts--)
-            gcov_write_counter (*c_ptr++);
+
+	  if (gi_ptr->merge[t_ix] == __gcov_merge_topn)
+	    write_top_counters (ci_ptr, t_ix, n_counts);
+	  else
+	    {
+	      gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix),
+				     GCOV_TAG_COUNTER_LENGTH (n_counts));
+	      c_ptr = ci_ptr->values;
+	      while (n_counts--)
+		gcov_write_counter (*c_ptr++);
+	    }
+
           ci_ptr++;
         }
       if (buffered)
@@ -476,9 +471,6 @@ dump_one_gcov (struct gcov_info *gi_ptr, struct gcov_filename *gf,
   gcov_unsigned_t tag;
   fn_buffer = 0;
 
-  /* Prune current counters before we merge them.  */
-  prune_counters (gi_ptr);
-
   error = gcov_exit_open_gcda_file (gi_ptr, gf);
   if (error == -1)
     return;
diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
index c0785b0..1acdaa0 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -86,86 +86,6 @@ __gcov_merge_time_profile (gcov_type *counters, unsigned n_counters)
 
 #ifdef L_gcov_merge_topn
 
-/* To merging of TOPN profiles.
-   counters[0] is the number of executions
-   for i in 0 ... TOPN-1
-     counters[2 * i + 1] is target
-     counters[2 * i + 2] is corresponding hitrate counter.
-
-   Because we prune counters only those with probability >= 1/TOPN are
-   present now.
-
-   We use sign of counters[0] to track whether the number of different
-   targets exceeds TOPN.  */
-
-static void
-merge_topn_values_set (gcov_type *counters)
-{
-  /* First value is number of total executions of the profiler.  */
-  gcov_type all = gcov_get_counter ();
-  gcov_type *total = &counters[0];
-  ++counters;
-
-  /* Negative value means that counter is missing some of values.  */
-  if (all < 0)
-    *total = -(*total);
-
-  *total += all;
-
-  /* Read all part values.  */
-  gcov_type read_counters[2 * GCOV_TOPN_VALUES];
-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    {
-      read_counters[2 * i] = gcov_get_counter_target ();
-      read_counters[2 * i + 1] = gcov_get_counter_ignore_scaling (-1);
-    }
-
-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    {
-      if (read_counters[2 * i + 1] == 0)
-	continue;
-
-      unsigned j;
-      int slot = 0;
-
-      for (j = 0; j < GCOV_TOPN_VALUES; j++)
-	{
-	  if (counters[2 * j] == read_counters[2 * i])
-	    {
-	      counters[2 * j + 1] += read_counters[2 * i + 1];
-	      break;
-	    }
-	  else if (counters[2 * j + 1] < counters[2 * slot + 1])
-	    slot = j;
-	}
-
-      if (j == GCOV_TOPN_VALUES)
-	{
-	  gcov_type slot_count = counters[2 * slot + 1];
-	  /* We found an empty slot.  */
-	  if (slot_count == 0)
-	    {
-	      /* If we found empty slot, add the value.  */
-	      counters[2 * slot] = read_counters[2 * i];
-	      counters[2 * slot + 1] = read_counters[2 * i + 1];
-	    }
-	  else
-	    {
-	      /* Here we are loosing some values.  */
-	      if (*total >= 0)
-		*total = -(*total);
-	      if (read_counters[2 * i + 1] > slot_count)
-		{
-		  counters[2 * slot] = read_counters[2 * i];
-		  counters[2 * slot + 1] = read_counters[2 * i + 1];
-		}
-	      else
-		counters[2 * slot + 1] -= read_counters[2 * i + 1];
-	    }
-	}
-    }
-}
-
 /* The profile merging function for choosing the most common value.
    It is given an array COUNTERS of N_COUNTERS old counters and it
    reads the same number of counters from the gcov file.  The counters
@@ -175,13 +95,30 @@ merge_topn_values_set (gcov_type *counters)
    -- the stored candidate on the most common value of the measured entity
    -- counter
    */
+
 void
 __gcov_merge_topn (gcov_type *counters, unsigned n_counters)
 {
-  gcc_assert (!(n_counters % GCOV_TOPN_VALUES_COUNTERS));
+  gcc_assert (!(n_counters % GCOV_TOPN_MEM_COUNTERS));
 
-  for (unsigned i = 0; i < (n_counters / GCOV_TOPN_VALUES_COUNTERS); i++)
-    merge_topn_values_set (counters + (i * GCOV_TOPN_VALUES_COUNTERS));
+  for (unsigned i = 0; i < (n_counters / GCOV_TOPN_MEM_COUNTERS); i++)
+    {
+      /* First value is number of total executions of the profiler.  */
+      gcov_type all = gcov_get_counter_ignore_scaling (-1);
+      gcov_type n = gcov_get_counter_ignore_scaling (-1);
+
+      counters[GCOV_TOPN_MEM_COUNTERS * i] += all;
+
+      for (unsigned j = 0; j < n; j++)
+	{
+	  gcov_type value = gcov_get_counter_target ();
+	  gcov_type count = gcov_get_counter_ignore_scaling (-1);
+
+	  // TODO: we should use atomic here
+	  gcov_topn_add_value (counters + GCOV_TOPN_MEM_COUNTERS * i, value,
+			       count, 0, 0);
+	}
+    }
 }
 #endif /* L_gcov_merge_topn */
 
diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c
index 6043ac4..7b17138 100644
--- a/libgcc/libgcov-profiler.c
+++ b/libgcc/libgcov-profiler.c
@@ -105,51 +105,13 @@ __gcov_pow2_profiler_atomic (gcov_type *counters, gcov_type value)
 }
 #endif
 
-
 /* Tries to determine N most commons value among its inputs.  */
 
 static inline void
 __gcov_topn_values_profiler_body (gcov_type *counters, gcov_type value,
 				  int use_atomic)
 {
-  if (use_atomic)
-    __atomic_fetch_add (&counters[0], 1, __ATOMIC_RELAXED);
-  else
-    counters[0]++;
-
-  ++counters;
-
-  /* First try to find an existing value.  */
-  int empty_counter = -1;
-
-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    if (value == counters[2 * i])
-      {
-	if (use_atomic)
-	  __atomic_fetch_add (&counters[2 * i + 1], GCOV_TOPN_VALUES,
-			      __ATOMIC_RELAXED);
-	else
-	  counters[2 * i + 1] += GCOV_TOPN_VALUES;
-	return;
-      }
-    else if (counters[2 * i + 1] <= 0)
-      empty_counter = i;
-
-  /* Find an empty slot for a new value.  */
-  if (empty_counter != -1)
-    {
-      counters[2 * empty_counter] = value;
-      counters[2 * empty_counter + 1] = GCOV_TOPN_VALUES;
-      return;
-    }
-
-  /* We haven't found an empty slot, then decrement all
-     counter values by one.  */
-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    if (use_atomic)
-      __atomic_fetch_sub (&counters[2 * i + 1], 1, __ATOMIC_RELAXED);
-    else
-      counters[2 * i + 1]--;
+  gcov_topn_add_value (counters, value, 1, use_atomic, 1);
 }
 
 #ifdef L_gcov_topn_values_profiler
diff --git a/libgcc/libgcov.h b/libgcc/libgcov.h
index b248690..bc38f4d 100644
--- a/libgcc/libgcov.h
+++ b/libgcc/libgcov.h
@@ -373,6 +373,93 @@ gcov_get_counter_target (void)
 #endif
 }
 
+/* Add VALUE to *COUNTER and make it with atomic operation
+   if USE_ATOMIC is true.  */
+
+static inline void
+gcov_counter_add (gcov_type *counter, gcov_type value, int use_atomic)
+{
+  if (use_atomic)
+    __atomic_fetch_add (counter, value, __ATOMIC_RELAXED);
+  else
+    *counter += value;
+}
+
+/* Set NODE to memory location COUNTER and make it with atomic operation
+   if USE_ATOMIC is true.  */
+
+static inline int
+gcov_counter_set_if_null (gcov_type *counter, struct gcov_kvp *node,
+			  int use_atomic)
+{
+  if (use_atomic)
+    return !__sync_val_compare_and_swap (counter, NULL, (intptr_t)node);
+  else
+    {
+      *counter = (intptr_t)node;
+      return 1;
+    }
+}
+
+/* Add key value pair VALUE:COUNT to a top N COUNTERS.  When INCREMENT_TOTAL
+   is true, add COUNT to total of the TOP counter.  If USE_ATOMIC is true,
+   do it in atomic way.  */
+
+static inline void
+gcov_topn_add_value (gcov_type *counters, gcov_type value, gcov_type count,
+		     int use_atomic, int increment_total)
+{
+  if (increment_total)
+    gcov_counter_add (&counters[0], 1, use_atomic);
+
+  struct gcov_kvp *prev_node = NULL;
+  struct gcov_kvp *minimal_node = NULL;
+  struct gcov_kvp *current_node  = (struct gcov_kvp *)counters[2];
+
+  while (current_node)
+    {
+      if (current_node->value == value)
+	{
+	  gcov_counter_add (&current_node->count, count, use_atomic);
+	  return;
+	}
+
+      if (minimal_node == NULL
+	  || current_node->count < minimal_node->count)
+	minimal_node = current_node;
+
+      prev_node = current_node;
+      current_node = current_node->next;
+    }
+
+  if (counters[1] == GCOV_TOPN_MAXIMUM_TRACKED_VALUES)
+    {
+      if (--minimal_node->count < count)
+	{
+	  minimal_node->value = value;
+	  minimal_node->count = count;
+	}
+    }
+  else
+    {
+      struct gcov_kvp *new_node
+	= (struct gcov_kvp *)xmalloc (sizeof (struct gcov_kvp));
+      new_node->value = value;
+      new_node->count = count;
+
+      int success = 0;
+      if (!counters[2])
+	success = gcov_counter_set_if_null (&counters[2], new_node, use_atomic);
+      else if (prev_node && !prev_node->next)
+	success = gcov_counter_set_if_null ((gcov_type *)&prev_node->next,
+					    new_node, use_atomic);
+
+      /* Increment number of nodes.  */
+      if (success)
+	gcov_counter_add (&counters[1], 1, use_atomic);
+    }
+}
+
 #endif /* !inhibit_libc */
 
 #endif /* GCC_LIBGCOV_H */