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

1 files changed, 139 insertions, 1 deletions

diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c
index 5f0b052b952..98f1ae9cb5f 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