Makefile.in: Fix dependence.

2014-10-06  Rong Xu  <xur@google.com>

	* gcc/Makefile.in: Fix dependence.
	* gcc/gcov-counter.def (GCOV_COUNTER_ICALL_TOPNV): Add
        indirect call topn profiler.
	* gcc/gcov-io.h: Ditto.
	* libgcc/Makefile.in: Ditto.
	* libgcc/libgcov-driver.c (gcov_sort_n_vals): New utility function.
	(gcov_sort_icall_topn_counter): Ditto.
	(gcov_sort_topn_counter_arrays): Ditto.
	(dump_one_gcov): Sort indirect_call topn counters.
	* libgcc/libgcov-merge.c (__gcov_merge_icall_topn): New merge
        function.
	* libgcc/libgcov-profiler.c (__gcov_topn_value_profiler_body): New
        utility function.
	(__gcov_indirect_call_topn_profiler): New profiler function.
	* libgcc/libgcov-util.c (__gcov_icall_topn_counter_op): New.
	* libgcc/libgcov.h: New decls.

From-SVN: r215962

6 files changed, 312 insertions, 3 deletions

diff --git a/libgcc/Makefile.in b/libgcc/Makefile.in
index 0d2c0b4..4008a85 100644
--- a/libgcc/Makefile.in
+++ b/libgcc/Makefile.in
@@ -855,11 +855,12 @@ include $(iterator)
 # Build libgcov components.
 
 LIBGCOV_MERGE = _gcov_merge_add _gcov_merge_single _gcov_merge_delta	\
-	_gcov_merge_ior _gcov_merge_time_profile
+	_gcov_merge_ior _gcov_merge_time_profile _gcov_merge_icall_topn
 LIBGCOV_PROFILER = _gcov_interval_profiler _gcov_pow2_profiler		\
 	_gcov_one_value_profiler _gcov_indirect_call_profiler		\
  	_gcov_average_profiler _gcov_ior_profiler			\
-	_gcov_indirect_call_profiler_v2 _gcov_time_profiler
+	_gcov_indirect_call_profiler_v2 _gcov_time_profiler		\
+	_gcov_indirect_call_topn_profiler
 LIBGCOV_INTERFACE = _gcov_dump _gcov_flush _gcov_fork			\
 	_gcov_execl _gcov_execlp					\
 	_gcov_execle _gcov_execv _gcov_execvp _gcov_execve _gcov_reset
diff --git a/libgcc/libgcov-driver.c b/libgcc/libgcov-driver.c
index 7bde526..754584d 100644
--- a/libgcc/libgcov-driver.c
+++ b/libgcc/libgcov-driver.c
@@ -665,6 +665,85 @@ merge_summary (const char *filename, int run_counted,
   return 0;
 }
 
+
+/* Sort N entries in VALUE_ARRAY in descending order.
+   Each entry in VALUE_ARRAY has two values. The sorting
+   is based on the second value.  */
+
+GCOV_LINKAGE  void
+gcov_sort_n_vals (gcov_type *value_array, int n)
+{
+  int j, k;
+
+  for (j = 2; j < n; j += 2)
+    {
+      gcov_type cur_ent[2];
+
+      cur_ent[0] = value_array[j];
+      cur_ent[1] = value_array[j + 1];
+      k = j - 2;
+      while (k >= 0 && value_array[k + 1] < cur_ent[1])
+        {
+          value_array[k + 2] = value_array[k];
+          value_array[k + 3] = value_array[k+1];
+          k -= 2;
+        }
+      value_array[k + 2] = cur_ent[0];
+      value_array[k + 3] = cur_ent[1];
+    }
+}
+
+/* Sort the profile counters for all indirect call sites. Counters
+   for each call site are allocated in array COUNTERS.  */
+
+static void
+gcov_sort_icall_topn_counter (const struct gcov_ctr_info *counters)
+{
+  int i;
+  gcov_type *values;
+  int n = counters->num;
+
+  gcc_assert (!(n % GCOV_ICALL_TOPN_NCOUNTS));
+  values = counters->values;
+
+  for (i = 0; i < n; i += GCOV_ICALL_TOPN_NCOUNTS)
+    {
+      gcov_type *value_array = &values[i + 1];
+      gcov_sort_n_vals (value_array, GCOV_ICALL_TOPN_NCOUNTS - 1);
+    }
+}
+
+/* Sort topn indirect_call profile counters in GI_PTR.  */
+
+static void
+gcov_sort_topn_counter_arrays (const struct gcov_info *gi_ptr)
+{
+  unsigned int i;
+  int f_ix;
+  const struct gcov_fn_info *gfi_ptr;
+  const struct gcov_ctr_info *ci_ptr;
+
+  if (!gi_ptr->merge[GCOV_COUNTER_ICALL_TOPNV]) 
+    return;
+
+  for (f_ix = 0; (unsigned)f_ix != gi_ptr->n_functions; f_ix++)
+    {
+      gfi_ptr = gi_ptr->functions[f_ix];
+      ci_ptr = gfi_ptr->ctrs;
+      for (i = 0; i < GCOV_COUNTERS; i++)
+        {
+          if (!gi_ptr->merge[i])
+            continue;
+          if (i == GCOV_COUNTER_ICALL_TOPNV)
+            {
+              gcov_sort_icall_topn_counter (ci_ptr);
+              break;
+            }
+          ci_ptr++;
+        }
+    }
+}
+
 /* Dump the coverage counts for one gcov_info object. We merge with existing
    counts when possible, to avoid growing the .da files ad infinitum. We use
    this program's checksum to make sure we only accumulate whole program
@@ -687,6 +766,8 @@ dump_one_gcov (struct gcov_info *gi_ptr, struct gcov_filename *gf,
   fn_buffer = 0;
   sum_buffer = 0;
 
+  gcov_sort_topn_counter_arrays (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 f6eacd1..5ed4793 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -166,4 +166,67 @@ __gcov_merge_delta (gcov_type *counters, unsigned n_counters)
     }
 }
 #endif /* L_gcov_merge_delta */
+
+#ifdef L_gcov_merge_icall_topn
+/* The profile merging function used for merging indirect call counts
+   This function is given array COUNTERS of N_COUNTERS old counters and it
+   reads the same number of counters from the gcov file.  */
+
+void
+__gcov_merge_icall_topn (gcov_type *counters, unsigned n_counters)
+{
+  unsigned i, j, k, m;
+
+  gcc_assert (!(n_counters % GCOV_ICALL_TOPN_NCOUNTS));
+  for (i = 0; i < n_counters; i += GCOV_ICALL_TOPN_NCOUNTS)
+    {
+      gcov_type *value_array = &counters[i + 1];
+      unsigned tmp_size = 2 * (GCOV_ICALL_TOPN_NCOUNTS - 1);
+      gcov_type *tmp_array 
+          = (gcov_type *) alloca (tmp_size * sizeof (gcov_type));
+
+      for (j = 0; j < tmp_size; j++)
+        tmp_array[j] = 0;
+
+      for (j = 0; j < GCOV_ICALL_TOPN_NCOUNTS - 1; j += 2)
+        {
+          tmp_array[j] = value_array[j];
+          tmp_array[j + 1] = value_array [j + 1];
+        }
+
+      /* Skip the number_of_eviction entry.  */
+      gcov_get_counter ();
+      for (k = 0; k < GCOV_ICALL_TOPN_NCOUNTS - 1; k += 2)
+        {
+          int found = 0;
+          gcov_type global_id = gcov_get_counter_target ();
+          gcov_type call_count = gcov_get_counter ();
+          for (m = 0; m < j; m += 2)
+            {
+              if (tmp_array[m] == global_id)
+                {
+                  found = 1;
+                  tmp_array[m + 1] += call_count;
+                  break;
+                }
+            }
+          if (!found)
+            {
+              tmp_array[j] = global_id;
+              tmp_array[j + 1] = call_count;
+              j += 2;
+            }
+        }
+      /* Now sort the temp array */
+      gcov_sort_n_vals (tmp_array, j);
+
+      /* Now copy back the top half of the temp array */
+      for (k = 0; k < GCOV_ICALL_TOPN_NCOUNTS - 1; k += 2)
+        {
+          value_array[k] = tmp_array[k];
+          value_array[k + 1] = tmp_array[k + 1];
+        }
+    }
+}
+#endif /* L_gcov_merge_icall_topn */
 #endif /* inhibit_libc */
diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c
index 5f0b052..98f1ae9 100644
--- a/libgcc/libgcov-profiler.c
+++ b/libgcc/libgcov-profiler.c
@@ -93,6 +93,144 @@ __gcov_one_value_profiler (gcov_type *counters, gcov_type value)
 }
 #endif
 
+#ifdef L_gcov_indirect_call_topn_profiler
+/* Tries to keep track the most frequent N values in the counters where
+   N is specified by parameter TOPN_VAL. To track top N values, 2*N counter
+   entries are used.
+   counter[0] --- the accumative count of the number of times one entry in
+                  in the counters gets evicted/replaced due to limited capacity.
+                  When this value reaches a threshold, the bottom N values are
+                  cleared.
+   counter[1] through counter[2*N] records the top 2*N values collected so far.
+   Each value is represented by two entries: count[2*i+1] is the ith value, and
+   count[2*i+2] is the number of times the value is seen.  */
+
+static void
+__gcov_topn_value_profiler_body (gcov_type *counters, gcov_type value)
+{
+   unsigned i, found = 0, have_zero_count = 0;
+   gcov_type *entry;
+   gcov_type *lfu_entry = &counters[1];
+   gcov_type *value_array = &counters[1];
+   gcov_type *num_eviction = &counters[0];
+   gcov_unsigned_t topn_val = GCOV_ICALL_TOPN_VAL;
+
+   /* There are 2*topn_val values tracked, each value takes two slots in the
+      counter array.  */
+   for (i = 0; i < (topn_val << 2); i += 2)
+     {
+       entry = &value_array[i];
+       if (entry[0] == value)
+         {
+           entry[1]++ ;
+           found = 1;
+           break;
+         }
+       else if (entry[1] == 0)
+         {
+           lfu_entry = entry;
+           have_zero_count = 1;
+         }
+      else if (entry[1] < lfu_entry[1])
+        lfu_entry = entry;
+     }
+
+   if (found)
+     return;
+
+   /* lfu_entry is either an empty entry or an entry
+      with lowest count, which will be evicted.  */
+   lfu_entry[0] = value;
+   lfu_entry[1] = 1;
+
+#define GCOV_ICALL_COUNTER_CLEAR_THRESHOLD 3000
+
+   /* Too many evictions -- time to clear bottom entries to
+      avoid hot values bumping each other out.  */
+   if (!have_zero_count
+       && ++*num_eviction >= GCOV_ICALL_COUNTER_CLEAR_THRESHOLD)
+     {
+       unsigned i, j;
+       gcov_type *p, minv;
+       gcov_type* tmp_cnts
+           = (gcov_type *)alloca (topn_val * sizeof (gcov_type));
+
+       *num_eviction = 0;
+
+       for (i = 0; i < topn_val; i++)
+         tmp_cnts[i] = 0;
+
+       /* Find the largest topn_val values from the group of
+          2*topn_val values and put them into tmp_cnts.  */
+
+       for (i = 0; i < 2 * topn_val; i += 2)
+         {
+           p = 0;
+           for (j = 0; j < topn_val; j++)
+             {
+               if (!p || tmp_cnts[j] < *p)
+                  p = &tmp_cnts[j];
+             }
+            if (value_array[i + 1] > *p)
+              *p = value_array[i + 1];
+         }
+
+       minv = tmp_cnts[0];
+       for (j = 1; j < topn_val; j++)
+         {
+           if (tmp_cnts[j] < minv)
+             minv = tmp_cnts[j];
+         }
+       /* Zero out low value entries.  */
+       for (i = 0; i < 2 * topn_val; i += 2)
+         {
+           if (value_array[i + 1] < minv)
+             {
+               value_array[i] = 0;
+               value_array[i + 1] = 0;
+             }
+         }
+     }
+}
+
+/* These two variables are used to actually track caller and callee.  Keep
+   them in TLS memory so races are not common (they are written to often).
+   The variables are set directly by GCC instrumented code, so declaration
+   here must match one in tree-profile.c.  */
+
+#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
+__thread
+#endif
+gcov_type *__gcov_indirect_call_topn_counters ATTRIBUTE_HIDDEN;
+
+#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
+__thread
+#endif
+void *__gcov_indirect_call_topn_callee ATTRIBUTE_HIDDEN;
+
+#ifdef TARGET_VTABLE_USES_DESCRIPTORS
+#define VTABLE_USES_DESCRIPTORS 1
+#else
+#define VTABLE_USES_DESCRIPTORS 0
+#endif
+
+/* This fucntion is instrumented at function entry to track topn indirect
+   calls to CUR_FUNC.  */
+ 
+void
+__gcov_indirect_call_topn_profiler (gcov_type value, void* cur_func)
+{
+  void *callee_func = __gcov_indirect_call_topn_callee;
+  /* If the C++ virtual tables contain function descriptors then one
+     function may have multiple descriptors and we need to dereference
+     the descriptors to see if they point to the same function.  */
+  if (cur_func == callee_func
+      || (VTABLE_USES_DESCRIPTORS && callee_func
+	  && *(void **) cur_func == *(void **) callee_func))
+    __gcov_topn_value_profiler_body (__gcov_indirect_call_topn_counters, value);
+}
+#endif
+
 #ifdef L_gcov_indirect_call_profiler
 /* This function exist only for workaround of binutils bug 14342.
    Once this compatibility hack is obsolette, it can be removed.  */
@@ -118,8 +256,8 @@ __gcov_indirect_call_profiler (gcov_type* counter, gcov_type value,
           && *(void **) cur_func == *(void **) callee_func))
     __gcov_one_value_profiler_body (counter, value);
 }
-
 #endif
+
 #ifdef L_gcov_indirect_call_profiler_v2
 
 /* These two variables are used to actually track caller and callee.  Keep
diff --git a/libgcc/libgcov-util.c b/libgcc/libgcov-util.c
index e46ae06..38d434a 100644
--- a/libgcc/libgcov-util.c
+++ b/libgcc/libgcov-util.c
@@ -746,6 +746,25 @@ __gcov_single_counter_op (gcov_type *counters, unsigned n_counters,
     }
 }
 
+/* Performing FN upon indirect-call profile counters.  */
+
+static void
+__gcov_icall_topn_counter_op (gcov_type *counters, unsigned n_counters,
+                              counter_op_fn fn, void *data1, void *data2)
+{
+  unsigned i;
+
+  gcc_assert (!(n_counters % GCOV_ICALL_TOPN_NCOUNTS));
+  for (i = 0; i < n_counters; i += GCOV_ICALL_TOPN_NCOUNTS)
+    {
+      unsigned j;
+      gcov_type *value_array = &counters[i + 1];
+
+      for (j = 0; j < GCOV_ICALL_TOPN_NCOUNTS - 1; j += 2)
+        value_array[j + 1] = fn (value_array[j + 1], data1, data2);
+    }
+}
+
 /* Scaling the counter value V by multiplying *(float*) DATA1.  */
 
 static gcov_type
diff --git a/libgcc/libgcov.h b/libgcc/libgcov.h
index 3816b6a..7830063 100644
--- a/libgcc/libgcov.h
+++ b/libgcc/libgcov.h
@@ -100,6 +100,7 @@ typedef unsigned gcov_type_unsigned __attribute__ ((mode (QI)));
 #define gcov_read_unsigned __gcov_read_unsigned
 #define gcov_read_counter __gcov_read_counter
 #define gcov_read_summary __gcov_read_summary
+#define gcov_sort_n_vals __gcov_sort_n_vals
 
 #else /* IN_GCOV_TOOL */
 /* About the host.  */
@@ -128,6 +129,7 @@ typedef unsigned gcov_position_t;
 #define L_gcov_merge_delta 1
 #define L_gcov_merge_ior 1
 #define L_gcov_merge_time_profile 1
+#define L_gcov_merge_icall_topn 1
 
 extern gcov_type gcov_read_counter_mem ();
 extern unsigned gcov_get_merge_weight ();
@@ -261,6 +263,9 @@ extern void __gcov_merge_delta (gcov_type *, unsigned) ATTRIBUTE_HIDDEN;
 /* The merge function that just ors the counters together.  */
 extern void __gcov_merge_ior (gcov_type *, unsigned) ATTRIBUTE_HIDDEN;
 
+/* The merge function is used for topn indirect call counters.  */
+extern void __gcov_merge_icall_topn (gcov_type *, unsigned) ATTRIBUTE_HIDDEN;
+
 /* The profiler functions.  */
 extern void __gcov_interval_profiler (gcov_type *, gcov_type, int, unsigned);
 extern void __gcov_pow2_profiler (gcov_type *, gcov_type);
@@ -271,6 +276,8 @@ extern void __gcov_indirect_call_profiler_v2 (gcov_type, void *);
 extern void __gcov_time_profiler (gcov_type *);
 extern void __gcov_average_profiler (gcov_type *, gcov_type);
 extern void __gcov_ior_profiler (gcov_type *, gcov_type);
+extern void __gcov_indirect_call_topn_profiler (gcov_type, void *);
+extern void gcov_sort_n_vals (gcov_type *, int);
 
 #ifndef inhibit_libc
 /* The wrappers around some library functions..  */