libgcc/libgcov-profiler.c

   1 /* Routines required for instrumenting a program.  */
   2 /* Compile this one with gcc.  */
   3 /* Copyright (C) 1989-2016 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 Under Section 7 of GPL version 3, you are granted additional
  18 permissions described in the GCC Runtime Library Exception, version
  19 3.1, as published by the Free Software Foundation.
  20
  21 You should have received a copy of the GNU General Public License and
  22 a copy of the GCC Runtime Library Exception along with this program;
  23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 <http://www.gnu.org/licenses/>.  */
  25
  26 #include "libgcov.h"
  27 #if !defined(inhibit_libc)
  28
  29 #ifdef L_gcov_interval_profiler
  30 /* If VALUE is in interval <START, START + STEPS - 1>, then increases the
  31    corresponding counter in COUNTERS.  If the VALUE is above or below
  32    the interval, COUNTERS[STEPS] or COUNTERS[STEPS + 1] is increased
  33    instead.  */
  34
  35 void
  36 __gcov_interval_profiler (gcov_type *counters, gcov_type value,
  37                           int start, unsigned steps)
  38 {
  39   gcov_type delta = value - start;
  40   if (delta < 0)
  41     counters[steps + 1]++;
  42   else if (delta >= steps)
  43     counters[steps]++;
  44   else
  45     counters[delta]++;
  46 }
  47 #endif
  48
  49 #ifdef L_gcov_pow2_profiler
  50 /* If VALUE is a power of two, COUNTERS[1] is incremented.  Otherwise
  51    COUNTERS[0] is incremented.  */
  52
  53 void
  54 __gcov_pow2_profiler (gcov_type *counters, gcov_type value)
  55 {
  56   if (value & (value - 1))
  57     counters[0]++;
  58   else
  59     counters[1]++;
  60 }
  61 #endif
  62
  63 /* Tries to determine the most common value among its inputs.  Checks if the
  64    value stored in COUNTERS[0] matches VALUE.  If this is the case, COUNTERS[1]
  65    is incremented.  If this is not the case and COUNTERS[1] is not zero,
  66    COUNTERS[1] is decremented.  Otherwise COUNTERS[1] is set to one and
  67    VALUE is stored to COUNTERS[0].  This algorithm guarantees that if this
  68    function is called more than 50% of the time with one value, this value
  69    will be in COUNTERS[0] in the end.
  70
  71    In any case, COUNTERS[2] is incremented.  */
  72
  73 static inline void
  74 __gcov_one_value_profiler_body (gcov_type *counters, gcov_type value)
  75 {
  76   if (value == counters[0])
  77     counters[1]++;
  78   else if (counters[1] == 0)
  79     {
  80       counters[1] = 1;
  81       counters[0] = value;
  82     }
  83   else
  84     counters[1]--;
  85   counters[2]++;
  86 }
  87
  88 #ifdef L_gcov_one_value_profiler
  89 void
  90 __gcov_one_value_profiler (gcov_type *counters, gcov_type value)
  91 {
  92   __gcov_one_value_profiler_body (counters, value);
  93 }
  94 #endif
  95
  96 #ifdef L_gcov_indirect_call_topn_profiler
  97 /* Tries to keep track the most frequent N values in the counters where
  98    N is specified by parameter TOPN_VAL. To track top N values, 2*N counter
  99    entries are used.
 100    counter[0] --- the accumative count of the number of times one entry in
 101                   in the counters gets evicted/replaced due to limited capacity.
 102                   When this value reaches a threshold, the bottom N values are
 103                   cleared.
 104    counter[1] through counter[2*N] records the top 2*N values collected so far.
 105    Each value is represented by two entries: count[2*i+1] is the ith value, and
 106    count[2*i+2] is the number of times the value is seen.  */
 107
 108 static void
 109 __gcov_topn_value_profiler_body (gcov_type *counters, gcov_type value)
 110 {
 111    unsigned i, found = 0, have_zero_count = 0;
 112    gcov_type *entry;
 113    gcov_type *lfu_entry = &counters[1];
 114    gcov_type *value_array = &counters[1];
 115    gcov_type *num_eviction = &counters[0];
 116    gcov_unsigned_t topn_val = GCOV_ICALL_TOPN_VAL;
 117
 118    /* There are 2*topn_val values tracked, each value takes two slots in the
 119       counter array.  */
 120    for (i = 0; i < (topn_val << 2); i += 2)
 121      {
 122        entry = &value_array[i];
 123        if (entry[0] == value)
 124          {
 125            entry[1]++ ;
 126            found = 1;
 127            break;
 128          }
 129        else if (entry[1] == 0)
 130          {
 131            lfu_entry = entry;
 132            have_zero_count = 1;
 133          }
 134       else if (entry[1] < lfu_entry[1])
 135         lfu_entry = entry;
 136      }
 137
 138    if (found)
 139      return;
 140
 141    /* lfu_entry is either an empty entry or an entry
 142       with lowest count, which will be evicted.  */
 143    lfu_entry[0] = value;
 144    lfu_entry[1] = 1;
 145
 146 #define GCOV_ICALL_COUNTER_CLEAR_THRESHOLD 3000
 147
 148    /* Too many evictions -- time to clear bottom entries to
 149       avoid hot values bumping each other out.  */
 150    if (!have_zero_count
 151        && ++*num_eviction >= GCOV_ICALL_COUNTER_CLEAR_THRESHOLD)
 152      {
 153        unsigned i, j;
 154        gcov_type *p, minv;
 155        gcov_type* tmp_cnts
 156            = (gcov_type *)alloca (topn_val * sizeof (gcov_type));
 157
 158        *num_eviction = 0;
 159
 160        for (i = 0; i < topn_val; i++)
 161          tmp_cnts[i] = 0;
 162
 163        /* Find the largest topn_val values from the group of
 164           2*topn_val values and put them into tmp_cnts.  */
 165
 166        for (i = 0; i < 2 * topn_val; i += 2)
 167          {
 168            p = 0;
 169            for (j = 0; j < topn_val; j++)
 170              {
 171                if (!p || tmp_cnts[j] < *p)
 172                   p = &tmp_cnts[j];
 173              }
 174             if (value_array[i + 1] > *p)
 175               *p = value_array[i + 1];
 176          }
 177
 178        minv = tmp_cnts[0];
 179        for (j = 1; j < topn_val; j++)
 180          {
 181            if (tmp_cnts[j] < minv)
 182              minv = tmp_cnts[j];
 183          }
 184        /* Zero out low value entries.  */
 185        for (i = 0; i < 2 * topn_val; i += 2)
 186          {
 187            if (value_array[i + 1] < minv)
 188              {
 189                value_array[i] = 0;
 190                value_array[i + 1] = 0;
 191              }
 192          }
 193      }
 194 }
 195
 196 /* These two variables are used to actually track caller and callee.  Keep
 197    them in TLS memory so races are not common (they are written to often).
 198    The variables are set directly by GCC instrumented code, so declaration
 199    here must match one in tree-profile.c.  */
 200
 201 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 202 __thread
 203 #endif
 204 gcov_type *__gcov_indirect_call_topn_counters ATTRIBUTE_HIDDEN;
 205
 206 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 207 __thread
 208 #endif
 209 void *__gcov_indirect_call_topn_callee ATTRIBUTE_HIDDEN;
 210
 211 #ifdef TARGET_VTABLE_USES_DESCRIPTORS
 212 #define VTABLE_USES_DESCRIPTORS 1
 213 #else
 214 #define VTABLE_USES_DESCRIPTORS 0
 215 #endif
 216
 217 /* This fucntion is instrumented at function entry to track topn indirect
 218    calls to CUR_FUNC.  */
 219
 220 void
 221 __gcov_indirect_call_topn_profiler (gcov_type value, void* cur_func)
 222 {
 223   void *callee_func = __gcov_indirect_call_topn_callee;
 224   /* If the C++ virtual tables contain function descriptors then one
 225      function may have multiple descriptors and we need to dereference
 226      the descriptors to see if they point to the same function.  */
 227   if (cur_func == callee_func
 228       || (VTABLE_USES_DESCRIPTORS && callee_func
 229           && *(void **) cur_func == *(void **) callee_func))
 230     __gcov_topn_value_profiler_body (__gcov_indirect_call_topn_counters, value);
 231 }
 232 #endif
 233
 234 #ifdef L_gcov_indirect_call_profiler
 235 /* This function exist only for workaround of binutils bug 14342.
 236    Once this compatibility hack is obsolette, it can be removed.  */
 237
 238 /* By default, the C++ compiler will use function addresses in the
 239    vtable entries.  Setting TARGET_VTABLE_USES_DESCRIPTORS to nonzero
 240    tells the compiler to use function descriptors instead.  The value
 241    of this macro says how many words wide the descriptor is (normally 2).
 242
 243    It is assumed that the address of a function descriptor may be treated
 244    as a pointer to a function.  */
 245
 246 /* Tries to determine the most common value among its inputs. */
 247 void
 248 __gcov_indirect_call_profiler (gcov_type* counter, gcov_type value,
 249                                void* cur_func, void* callee_func)
 250 {
 251   /* If the C++ virtual tables contain function descriptors then one
 252      function may have multiple descriptors and we need to dereference
 253      the descriptors to see if they point to the same function.  */
 254   if (cur_func == callee_func
 255       || (__LIBGCC_VTABLE_USES_DESCRIPTORS__ && callee_func
 256           && *(void **) cur_func == *(void **) callee_func))
 257     __gcov_one_value_profiler_body (counter, value);
 258 }
 259 #endif
 260
 261 #ifdef L_gcov_indirect_call_profiler_v2
 262
 263 /* These two variables are used to actually track caller and callee.  Keep
 264    them in TLS memory so races are not common (they are written to often).
 265    The variables are set directly by GCC instrumented code, so declaration
 266    here must match one in tree-profile.c  */
 267
 268 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 269 __thread
 270 #endif
 271 void * __gcov_indirect_call_callee;
 272 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 273 __thread
 274 #endif
 275 gcov_type * __gcov_indirect_call_counters;
 276
 277 /* By default, the C++ compiler will use function addresses in the
 278    vtable entries.  Setting TARGET_VTABLE_USES_DESCRIPTORS to nonzero
 279    tells the compiler to use function descriptors instead.  The value
 280    of this macro says how many words wide the descriptor is (normally 2).
 281
 282    It is assumed that the address of a function descriptor may be treated
 283    as a pointer to a function.  */
 284
 285 /* Tries to determine the most common value among its inputs. */
 286 void
 287 __gcov_indirect_call_profiler_v2 (gcov_type value, void* cur_func)
 288 {
 289   /* If the C++ virtual tables contain function descriptors then one
 290      function may have multiple descriptors and we need to dereference
 291      the descriptors to see if they point to the same function.  */
 292   if (cur_func == __gcov_indirect_call_callee
 293       || (__LIBGCC_VTABLE_USES_DESCRIPTORS__ && __gcov_indirect_call_callee
 294           && *(void **) cur_func == *(void **) __gcov_indirect_call_callee))
 295     __gcov_one_value_profiler_body (__gcov_indirect_call_counters, value);
 296 }
 297 #endif
 298
 299 #ifdef L_gcov_time_profiler
 300
 301 /* Counter for first visit of each function.  */
 302 static gcov_type function_counter;
 303
 304 /* Sets corresponding COUNTERS if there is no value.  */
 305
 306 void
 307 __gcov_time_profiler (gcov_type* counters)
 308 {
 309   if (!counters[0])
 310     counters[0] = ++function_counter;
 311 }
 312 #endif
 313
 314 #ifdef L_gcov_average_profiler
 315 /* Increase corresponding COUNTER by VALUE.  FIXME: Perhaps we want
 316    to saturate up.  */
 317
 318 void
 319 __gcov_average_profiler (gcov_type *counters, gcov_type value)
 320 {
 321   counters[0] += value;
 322   counters[1] ++;
 323 }
 324 #endif
 325
 326 #ifdef L_gcov_ior_profiler
 327 /* Bitwise-OR VALUE into COUNTER.  */
 328
 329 void
 330 __gcov_ior_profiler (gcov_type *counters, gcov_type value)
 331 {
 332   *counters |= value;
 333 }
 334 #endif
 335
 336 #endif /* inhibit_libc */