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