libgcc/libgcov-profiler.c

   1 /* Routines required for instrumenting a program.  */
   2 /* Compile this one with gcc.  */
   3 /* Copyright (C) 1989-2017 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 /* Detect whether target can support atomic update of profilers.  */
  30 #if __SIZEOF_LONG_LONG__ == 4 && __GCC_HAVE_SYNC_COMPARE_AND_SWAP_4
  31 #define GCOV_SUPPORTS_ATOMIC 1
  32 #else
  33 #if __SIZEOF_LONG_LONG__ == 8 && __GCC_HAVE_SYNC_COMPARE_AND_SWAP_8
  34 #define GCOV_SUPPORTS_ATOMIC 1
  35 #else
  36 #define GCOV_SUPPORTS_ATOMIC 0
  37 #endif
  38 #endif
  39
  40 #ifdef L_gcov_interval_profiler
  41 /* If VALUE is in interval <START, START + STEPS - 1>, then increases the
  42    corresponding counter in COUNTERS.  If the VALUE is above or below
  43    the interval, COUNTERS[STEPS] or COUNTERS[STEPS + 1] is increased
  44    instead.  */
  45
  46 void
  47 __gcov_interval_profiler (gcov_type *counters, gcov_type value,
  48                           int start, unsigned steps)
  49 {
  50   gcov_type delta = value - start;
  51   if (delta < 0)
  52     counters[steps + 1]++;
  53   else if (delta >= steps)
  54     counters[steps]++;
  55   else
  56     counters[delta]++;
  57 }
  58 #endif
  59
  60 #if defined(L_gcov_interval_profiler_atomic) && GCOV_SUPPORTS_ATOMIC
  61 /* If VALUE is in interval <START, START + STEPS - 1>, then increases the
  62    corresponding counter in COUNTERS.  If the VALUE is above or below
  63    the interval, COUNTERS[STEPS] or COUNTERS[STEPS + 1] is increased
  64    instead.  Function is thread-safe.  */
  65
  66 void
  67 __gcov_interval_profiler_atomic (gcov_type *counters, gcov_type value,
  68                                  int start, unsigned steps)
  69 {
  70   gcov_type delta = value - start;
  71   if (delta < 0)
  72     __atomic_fetch_add (&counters[steps + 1], 1, __ATOMIC_RELAXED);
  73   else if (delta >= steps)
  74     __atomic_fetch_add (&counters[steps], 1, __ATOMIC_RELAXED);
  75   else
  76     __atomic_fetch_add (&counters[delta], 1, __ATOMIC_RELAXED);
  77 }
  78 #endif
  79
  80 #ifdef L_gcov_pow2_profiler
  81 /* If VALUE is a power of two, COUNTERS[1] is incremented.  Otherwise
  82    COUNTERS[0] is incremented.  */
  83
  84 void
  85 __gcov_pow2_profiler (gcov_type *counters, gcov_type value)
  86 {
  87   if (value == 0 || (value & (value - 1)))
  88     counters[0]++;
  89   else
  90     counters[1]++;
  91 }
  92 #endif
  93
  94 #if defined(L_gcov_pow2_profiler_atomic) && GCOV_SUPPORTS_ATOMIC
  95 /* If VALUE is a power of two, COUNTERS[1] is incremented.  Otherwise
  96    COUNTERS[0] is incremented.  Function is thread-safe.  */
  97
  98 void
  99 __gcov_pow2_profiler_atomic (gcov_type *counters, gcov_type value)
 100 {
 101   if (value == 0 || (value & (value - 1)))
 102     __atomic_fetch_add (&counters[0], 1, __ATOMIC_RELAXED);
 103   else
 104     __atomic_fetch_add (&counters[1], 1, __ATOMIC_RELAXED);
 105 }
 106 #endif
 107
 108
 109 /* Tries to determine the most common value among its inputs.  Checks if the
 110    value stored in COUNTERS[0] matches VALUE.  If this is the case, COUNTERS[1]
 111    is incremented.  If this is not the case and COUNTERS[1] is not zero,
 112    COUNTERS[1] is decremented.  Otherwise COUNTERS[1] is set to one and
 113    VALUE is stored to COUNTERS[0].  This algorithm guarantees that if this
 114    function is called more than 50% of the time with one value, this value
 115    will be in COUNTERS[0] in the end.
 116
 117    In any case, COUNTERS[2] is incremented.  If USE_ATOMIC is set to 1,
 118    COUNTERS[2] is updated with an atomic instruction.  */
 119
 120 static inline void
 121 __gcov_one_value_profiler_body (gcov_type *counters, gcov_type value,
 122                                 int use_atomic)
 123 {
 124   if (value == counters[0])
 125     counters[1]++;
 126   else if (counters[1] == 0)
 127     {
 128       counters[1] = 1;
 129       counters[0] = value;
 130     }
 131   else
 132     counters[1]--;
 133
 134   if (use_atomic)
 135     __atomic_fetch_add (&counters[2], 1, __ATOMIC_RELAXED);
 136   else
 137     counters[2]++;
 138 }
 139
 140 #ifdef L_gcov_one_value_profiler
 141 void
 142 __gcov_one_value_profiler (gcov_type *counters, gcov_type value)
 143 {
 144   __gcov_one_value_profiler_body (counters, value, 0);
 145 }
 146 #endif
 147
 148 #if defined(L_gcov_one_value_profiler_atomic) && GCOV_SUPPORTS_ATOMIC
 149
 150 /* Update one value profilers (COUNTERS) for a given VALUE.
 151
 152    CAVEAT: Following function is not thread-safe, only total number
 153    of executions (COUNTERS[2]) is update with an atomic instruction.
 154    Problem is that one cannot atomically update two counters
 155    (COUNTERS[0] and COUNTERS[1]), for more information please read
 156    following email thread:
 157    https://gcc.gnu.org/ml/gcc-patches/2016-08/msg00024.html.  */
 158
 159 void
 160 __gcov_one_value_profiler_atomic (gcov_type *counters, gcov_type value)
 161 {
 162   __gcov_one_value_profiler_body (counters, value, 1);
 163 }
 164 #endif
 165
 166 #ifdef L_gcov_indirect_call_topn_profiler
 167 /* Tries to keep track the most frequent N values in the counters where
 168    N is specified by parameter TOPN_VAL. To track top N values, 2*N counter
 169    entries are used.
 170    counter[0] --- the accumative count of the number of times one entry in
 171                   in the counters gets evicted/replaced due to limited capacity.
 172                   When this value reaches a threshold, the bottom N values are
 173                   cleared.
 174    counter[1] through counter[2*N] records the top 2*N values collected so far.
 175    Each value is represented by two entries: count[2*i+1] is the ith value, and
 176    count[2*i+2] is the number of times the value is seen.  */
 177
 178 static void
 179 __gcov_topn_value_profiler_body (gcov_type *counters, gcov_type value)
 180 {
 181    unsigned i, found = 0, have_zero_count = 0;
 182    gcov_type *entry;
 183    gcov_type *lfu_entry = &counters[1];
 184    gcov_type *value_array = &counters[1];
 185    gcov_type *num_eviction = &counters[0];
 186    gcov_unsigned_t topn_val = GCOV_ICALL_TOPN_VAL;
 187
 188    /* There are 2*topn_val values tracked, each value takes two slots in the
 189       counter array.  */
 190    for (i = 0; i < (topn_val << 2); i += 2)
 191      {
 192        entry = &value_array[i];
 193        if (entry[0] == value)
 194          {
 195            entry[1]++ ;
 196            found = 1;
 197            break;
 198          }
 199        else if (entry[1] == 0)
 200          {
 201            lfu_entry = entry;
 202            have_zero_count = 1;
 203          }
 204       else if (entry[1] < lfu_entry[1])
 205         lfu_entry = entry;
 206      }
 207
 208    if (found)
 209      return;
 210
 211    /* lfu_entry is either an empty entry or an entry
 212       with lowest count, which will be evicted.  */
 213    lfu_entry[0] = value;
 214    lfu_entry[1] = 1;
 215
 216 #define GCOV_ICALL_COUNTER_CLEAR_THRESHOLD 3000
 217
 218    /* Too many evictions -- time to clear bottom entries to
 219       avoid hot values bumping each other out.  */
 220    if (!have_zero_count
 221        && ++*num_eviction >= GCOV_ICALL_COUNTER_CLEAR_THRESHOLD)
 222      {
 223        unsigned i, j;
 224        gcov_type *p, minv;
 225        gcov_type* tmp_cnts
 226            = (gcov_type *)alloca (topn_val * sizeof (gcov_type));
 227
 228        *num_eviction = 0;
 229
 230        for (i = 0; i < topn_val; i++)
 231          tmp_cnts[i] = 0;
 232
 233        /* Find the largest topn_val values from the group of
 234           2*topn_val values and put them into tmp_cnts.  */
 235
 236        for (i = 0; i < 2 * topn_val; i += 2)
 237          {
 238            p = 0;
 239            for (j = 0; j < topn_val; j++)
 240              {
 241                if (!p || tmp_cnts[j] < *p)
 242                   p = &tmp_cnts[j];
 243              }
 244             if (value_array[i + 1] > *p)
 245               *p = value_array[i + 1];
 246          }
 247
 248        minv = tmp_cnts[0];
 249        for (j = 1; j < topn_val; j++)
 250          {
 251            if (tmp_cnts[j] < minv)
 252              minv = tmp_cnts[j];
 253          }
 254        /* Zero out low value entries.  */
 255        for (i = 0; i < 2 * topn_val; i += 2)
 256          {
 257            if (value_array[i + 1] < minv)
 258              {
 259                value_array[i] = 0;
 260                value_array[i + 1] = 0;
 261              }
 262          }
 263      }
 264 }
 265
 266 /* These two variables are used to actually track caller and callee.  Keep
 267    them in TLS memory so races are not common (they are written to often).
 268    The variables are set directly by GCC instrumented code, so declaration
 269    here must match one in tree-profile.c.  */
 270
 271 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 272 __thread
 273 #endif
 274 gcov_type *__gcov_indirect_call_topn_counters ATTRIBUTE_HIDDEN;
 275
 276 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 277 __thread
 278 #endif
 279 void *__gcov_indirect_call_topn_callee ATTRIBUTE_HIDDEN;
 280
 281 #ifdef TARGET_VTABLE_USES_DESCRIPTORS
 282 #define VTABLE_USES_DESCRIPTORS 1
 283 #else
 284 #define VTABLE_USES_DESCRIPTORS 0
 285 #endif
 286
 287 /* This fucntion is instrumented at function entry to track topn indirect
 288    calls to CUR_FUNC.  */
 289
 290 void
 291 __gcov_indirect_call_topn_profiler (gcov_type value, void* cur_func)
 292 {
 293   void *callee_func = __gcov_indirect_call_topn_callee;
 294   /* If the C++ virtual tables contain function descriptors then one
 295      function may have multiple descriptors and we need to dereference
 296      the descriptors to see if they point to the same function.  */
 297   if (cur_func == callee_func
 298       || (VTABLE_USES_DESCRIPTORS && callee_func
 299           && *(void **) cur_func == *(void **) callee_func))
 300     __gcov_topn_value_profiler_body (__gcov_indirect_call_topn_counters, value);
 301 }
 302 #endif
 303
 304 #ifdef L_gcov_indirect_call_profiler_v2
 305
 306 /* These two variables are used to actually track caller and callee.  Keep
 307    them in TLS memory so races are not common (they are written to often).
 308    The variables are set directly by GCC instrumented code, so declaration
 309    here must match one in tree-profile.c  */
 310
 311 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 312 __thread
 313 #endif
 314 void * __gcov_indirect_call_callee;
 315 #if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS)
 316 __thread
 317 #endif
 318 gcov_type * __gcov_indirect_call_counters;
 319
 320 /* By default, the C++ compiler will use function addresses in the
 321    vtable entries.  Setting TARGET_VTABLE_USES_DESCRIPTORS to nonzero
 322    tells the compiler to use function descriptors instead.  The value
 323    of this macro says how many words wide the descriptor is (normally 2).
 324
 325    It is assumed that the address of a function descriptor may be treated
 326    as a pointer to a function.  */
 327
 328 /* Tries to determine the most common value among its inputs. */
 329 void
 330 __gcov_indirect_call_profiler_v2 (gcov_type value, void* cur_func)
 331 {
 332   /* If the C++ virtual tables contain function descriptors then one
 333      function may have multiple descriptors and we need to dereference
 334      the descriptors to see if they point to the same function.  */
 335   if (cur_func == __gcov_indirect_call_callee
 336       || (__LIBGCC_VTABLE_USES_DESCRIPTORS__ && __gcov_indirect_call_callee
 337           && *(void **) cur_func == *(void **) __gcov_indirect_call_callee))
 338     __gcov_one_value_profiler_body (__gcov_indirect_call_counters, value, 0);
 339
 340   __gcov_indirect_call_callee = NULL;
 341 }
 342 #endif
 343
 344 #ifdef L_gcov_time_profiler
 345
 346 /* Counter for first visit of each function.  */
 347 gcov_type __gcov_time_profiler_counter ATTRIBUTE_HIDDEN;
 348
 349 #endif
 350
 351 #ifdef L_gcov_average_profiler
 352 /* Increase corresponding COUNTER by VALUE.  FIXME: Perhaps we want
 353    to saturate up.  */
 354
 355 void
 356 __gcov_average_profiler (gcov_type *counters, gcov_type value)
 357 {
 358   counters[0] += value;
 359   counters[1] ++;
 360 }
 361 #endif
 362
 363 #if defined(L_gcov_average_profiler_atomic) && GCOV_SUPPORTS_ATOMIC
 364 /* Increase corresponding COUNTER by VALUE.  FIXME: Perhaps we want
 365    to saturate up.  Function is thread-safe.  */
 366
 367 void
 368 __gcov_average_profiler_atomic (gcov_type *counters, gcov_type value)
 369 {
 370   __atomic_fetch_add (&counters[0], value, __ATOMIC_RELAXED);
 371   __atomic_fetch_add (&counters[1], 1, __ATOMIC_RELAXED);
 372 }
 373 #endif
 374
 375 #ifdef L_gcov_ior_profiler
 376 /* Bitwise-OR VALUE into COUNTER.  */
 377
 378 void
 379 __gcov_ior_profiler (gcov_type *counters, gcov_type value)
 380 {
 381   *counters |= value;
 382 }
 383 #endif
 384
 385 #if defined(L_gcov_ior_profiler_atomic) && GCOV_SUPPORTS_ATOMIC
 386 /* Bitwise-OR VALUE into COUNTER.  Function is thread-safe.  */
 387
 388 void
 389 __gcov_ior_profiler_atomic (gcov_type *counters, gcov_type value)
 390 {
 391   __atomic_fetch_or (&counters[0], value, __ATOMIC_RELAXED);
 392 }
 393 #endif
 394
 395
 396 #endif /* inhibit_libc */