1/* Routines required for instrumenting a program. */ 2/* Compile this one with gcc. */ 3/* Copyright (C) 1989-2014 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17Under Section 7 of GPL version 3, you are granted additional 18permissions described in the GCC Runtime Library Exception, version 193.1, as published by the Free Software Foundation. 20 21You should have received a copy of the GNU General Public License and 22a copy of the GCC Runtime Library Exception along with this program; 23see 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 35void 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 53void 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 73static 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/* Atomic update version of __gcov_one_value_profile_body(). */ 89static inline void 90__gcov_one_value_profiler_body_atomic (gcov_type *counters, gcov_type value) 91{ 92 if (value == counters[0]) 93 GCOV_TYPE_ATOMIC_FETCH_ADD_FN (&counters[1], 1, MEMMODEL_RELAXED); 94 else if (counters[1] == 0) 95 { 96 counters[1] = 1; 97 counters[0] = value; 98 } 99 else 100 GCOV_TYPE_ATOMIC_FETCH_ADD_FN (&counters[1], -1, MEMMODEL_RELAXED); 101 GCOV_TYPE_ATOMIC_FETCH_ADD_FN (&counters[2], 1, MEMMODEL_RELAXED); 102} 103 104 105#ifdef L_gcov_one_value_profiler 106void 107__gcov_one_value_profiler (gcov_type *counters, gcov_type value) 108{ 109 __gcov_one_value_profiler_body (counters, value); 110} 111 112void 113__gcov_one_value_profiler_atomic (gcov_type *counters, gcov_type value) 114{ 115 __gcov_one_value_profiler_body_atomic (counters, value); 116} 117 118 119#endif 120 121#ifdef L_gcov_indirect_call_profiler 122/* This function exist only for workaround of binutils bug 14342. 123 Once this compatibility hack is obsolette, it can be removed. */ 124 125/* By default, the C++ compiler will use function addresses in the 126 vtable entries. Setting TARGET_VTABLE_USES_DESCRIPTORS to nonzero 127 tells the compiler to use function descriptors instead. The value 128 of this macro says how many words wide the descriptor is (normally 2), 129 but it may be dependent on target flags. Since we do not have access 130 to the target flags here we just check to see if it is set and use 131 that to set VTABLE_USES_DESCRIPTORS to 0 or 1. 132 133 It is assumed that the address of a function descriptor may be treated 134 as a pointer to a function. */ 135 136#ifdef TARGET_VTABLE_USES_DESCRIPTORS 137#define VTABLE_USES_DESCRIPTORS 1 138#else 139#define VTABLE_USES_DESCRIPTORS 0 140#endif 141 142/* Tries to determine the most common value among its inputs. */ 143void 144__gcov_indirect_call_profiler (gcov_type* counter, gcov_type value, 145 void* cur_func, void* callee_func) 146{ 147 /* If the C++ virtual tables contain function descriptors then one 148 function may have multiple descriptors and we need to dereference 149 the descriptors to see if they point to the same function. */ 150 if (cur_func == callee_func 151 || (VTABLE_USES_DESCRIPTORS && callee_func 152 && *(void **) cur_func == *(void **) callee_func)) 153 __gcov_one_value_profiler_body (counter, value); 154} 155 156 157/* Atomic update version of __gcov_indirect_call_profiler(). */ 158void 159__gcov_indirect_call_profiler_atomic (gcov_type* counter, gcov_type value, 160 void* cur_func, void* callee_func) 161{ 162 if (cur_func == callee_func 163 || (VTABLE_USES_DESCRIPTORS && callee_func 164 && *(void **) cur_func == *(void **) callee_func)) 165 __gcov_one_value_profiler_body_atomic (counter, value); 166} 167 168 169#endif 170#ifdef L_gcov_indirect_call_profiler_v2 171 172/* These two variables are used to actually track caller and callee. Keep 173 them in TLS memory so races are not common (they are written to often). 174 The variables are set directly by GCC instrumented code, so declaration 175 here must match one in tree-profile.c */ 176 177#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 178__thread 179#endif 180void * __gcov_indirect_call_callee; 181#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 182__thread 183#endif 184gcov_type * __gcov_indirect_call_counters; 185 186/* By default, the C++ compiler will use function addresses in the 187 vtable entries. Setting TARGET_VTABLE_USES_DESCRIPTORS to nonzero 188 tells the compiler to use function descriptors instead. The value 189 of this macro says how many words wide the descriptor is (normally 2), 190 but it may be dependent on target flags. Since we do not have access 191 to the target flags here we just check to see if it is set and use 192 that to set VTABLE_USES_DESCRIPTORS to 0 or 1. 193 194 It is assumed that the address of a function descriptor may be treated 195 as a pointer to a function. */ 196 197#ifdef TARGET_VTABLE_USES_DESCRIPTORS 198#define VTABLE_USES_DESCRIPTORS 1 199#else 200#define VTABLE_USES_DESCRIPTORS 0 201#endif 202 203/* Tries to determine the most common value among its inputs. */ 204void 205__gcov_indirect_call_profiler_v2 (gcov_type value, void* cur_func) 206{ 207 /* If the C++ virtual tables contain function descriptors then one 208 function may have multiple descriptors and we need to dereference 209 the descriptors to see if they point to the same function. */ 210 if (cur_func == __gcov_indirect_call_callee 211 || (VTABLE_USES_DESCRIPTORS && __gcov_indirect_call_callee 212 && *(void **) cur_func == *(void **) __gcov_indirect_call_callee)) 213 __gcov_one_value_profiler_body (__gcov_indirect_call_counters, value); 214} 215 216void 217__gcov_indirect_call_profiler_atomic_v2 (gcov_type value, void* cur_func) 218{ 219 /* If the C++ virtual tables contain function descriptors then one 220 function may have multiple descriptors and we need to dereference 221 the descriptors to see if they point to the same function. */ 222 if (cur_func == __gcov_indirect_call_callee 223 || (VTABLE_USES_DESCRIPTORS && __gcov_indirect_call_callee 224 && *(void **) cur_func == *(void **) __gcov_indirect_call_callee)) 225 __gcov_one_value_profiler_body_atomic (__gcov_indirect_call_counters, value); 226} 227 228#endif 229 230/* 231#if defined(L_gcov_direct_call_profiler) || defined(L_gcov_indirect_call_topn_profiler) 232__attribute__ ((weak)) gcov_unsigned_t __gcov_lipo_sampling_period; 233#endif 234*/ 235 236extern gcov_unsigned_t __gcov_lipo_sampling_period; 237 238#ifdef L_gcov_indirect_call_topn_profiler 239 240#include "gthr.h" 241 242#ifdef __GTHREAD_MUTEX_INIT 243__thread int in_profiler; 244ATTRIBUTE_HIDDEN __gthread_mutex_t __indir_topn_val_mx = __GTHREAD_MUTEX_INIT; 245#endif 246 247/* Tries to keep track the most frequent N values in the counters where 248 N is specified by parameter TOPN_VAL. To track top N values, 2*N counter 249 entries are used. 250 counter[0] --- the accumative count of the number of times one entry in 251 in the counters gets evicted/replaced due to limited capacity. 252 When this value reaches a threshold, the bottom N values are 253 cleared. 254 counter[1] through counter[2*N] records the top 2*N values collected so far. 255 Each value is represented by two entries: count[2*i+1] is the ith value, and 256 count[2*i+2] is the number of times the value is seen. */ 257 258static void 259__gcov_topn_value_profiler_body (gcov_type *counters, gcov_type value, 260 gcov_unsigned_t topn_val) 261{ 262 unsigned i, found = 0, have_zero_count = 0; 263 264 gcov_type *entry; 265 gcov_type *lfu_entry = &counters[1]; 266 gcov_type *value_array = &counters[1]; 267 gcov_type *num_eviction = &counters[0]; 268 269 /* There are 2*topn_val values tracked, each value takes two slots in the 270 counter array */ 271#ifdef __GTHREAD_MUTEX_INIT 272 /* If this is reentry, return. */ 273 if (in_profiler == 1) 274 return; 275 276 in_profiler = 1; 277 __gthread_mutex_lock (&__indir_topn_val_mx); 278#endif 279 for (i = 0; i < topn_val << 2; i += 2) 280 { 281 entry = &value_array[i]; 282 if (entry[0] == value) 283 { 284 entry[1]++ ; 285 found = 1; 286 break; 287 } 288 else if (entry[1] == 0) 289 { 290 lfu_entry = entry; 291 have_zero_count = 1; 292 } 293 else if (entry[1] < lfu_entry[1]) 294 lfu_entry = entry; 295 } 296 297 if (found) 298 { 299 in_profiler = 0; 300#ifdef __GTHREAD_MUTEX_INIT 301 __gthread_mutex_unlock (&__indir_topn_val_mx); 302#endif 303 return; 304 } 305 306 /* lfu_entry is either an empty entry or an entry 307 with lowest count, which will be evicted. */ 308 lfu_entry[0] = value; 309 lfu_entry[1] = 1; 310 311#define GCOV_ICALL_COUNTER_CLEAR_THRESHOLD 3000 312 313 /* Too many evictions -- time to clear bottom entries to 314 avoid hot values bumping each other out. */ 315 if (!have_zero_count 316 && ++*num_eviction >= GCOV_ICALL_COUNTER_CLEAR_THRESHOLD) 317 { 318 unsigned i, j; 319 gcov_type **p; 320 gcov_type **tmp_cnts 321 = (gcov_type **)alloca (topn_val * sizeof(gcov_type *)); 322 323 *num_eviction = 0; 324 325 /* Find the largest topn_val values from the group of 326 2*topn_val values and put the addresses into tmp_cnts. */ 327 for (i = 0; i < topn_val; i++) 328 tmp_cnts[i] = &value_array[i * 2 + 1]; 329 330 for (i = topn_val * 2; i < topn_val << 2; i += 2) 331 { 332 p = &tmp_cnts[0]; 333 for (j = 1; j < topn_val; j++) 334 if (*tmp_cnts[j] > **p) 335 p = &tmp_cnts[j]; 336 if (value_array[i + 1] < **p) 337 *p = &value_array[i + 1]; 338 } 339 340 /* Zero out low value entries. */ 341 for (i = 0; i < topn_val; i++) 342 { 343 *tmp_cnts[i] = 0; 344 *(tmp_cnts[i] - 1) = 0; 345 } 346 } 347 348#ifdef __GTHREAD_MUTEX_INIT 349 in_profiler = 0; 350 __gthread_mutex_unlock (&__indir_topn_val_mx); 351#endif 352} 353 354#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 355__thread 356#endif 357gcov_type *__gcov_indirect_call_topn_counters ATTRIBUTE_HIDDEN; 358 359#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 360__thread 361#endif 362void *__gcov_indirect_call_topn_callee ATTRIBUTE_HIDDEN; 363 364#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 365__thread 366#endif 367gcov_unsigned_t __gcov_indirect_call_sampling_counter ATTRIBUTE_HIDDEN; 368 369#ifdef TARGET_VTABLE_USES_DESCRIPTORS 370#define VTABLE_USES_DESCRIPTORS 1 371#else 372#define VTABLE_USES_DESCRIPTORS 0 373#endif 374void 375__gcov_indirect_call_topn_profiler (void *cur_func, 376 void *cur_module_gcov_info, 377 gcov_unsigned_t cur_func_id) 378{ 379 void *callee_func = __gcov_indirect_call_topn_callee; 380 gcov_type *counter = __gcov_indirect_call_topn_counters; 381 /* If the C++ virtual tables contain function descriptors then one 382 function may have multiple descriptors and we need to dereference 383 the descriptors to see if they point to the same function. */ 384 if (cur_func == callee_func 385 || (VTABLE_USES_DESCRIPTORS && callee_func 386 && *(void **) cur_func == *(void **) callee_func)) 387 { 388 if (++__gcov_indirect_call_sampling_counter >= __gcov_lipo_sampling_period) 389 { 390 __gcov_indirect_call_sampling_counter = 0; 391 gcov_type global_id 392 = ((struct gcov_info *) cur_module_gcov_info)->mod_info->ident; 393 global_id = GEN_FUNC_GLOBAL_ID (global_id, cur_func_id); 394 __gcov_topn_value_profiler_body (counter, global_id, GCOV_ICALL_TOPN_VAL); 395 } 396 __gcov_indirect_call_topn_callee = 0; 397 } 398} 399 400#endif 401 402#ifdef L_gcov_direct_call_profiler 403#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 404__thread 405#endif 406gcov_type *__gcov_direct_call_counters ATTRIBUTE_HIDDEN; 407#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 408__thread 409#endif 410void *__gcov_direct_call_callee ATTRIBUTE_HIDDEN; 411#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 412__thread 413#endif 414gcov_unsigned_t __gcov_direct_call_sampling_counter ATTRIBUTE_HIDDEN; 415 416/* Direct call profiler. */ 417 418void 419__gcov_direct_call_profiler (void *cur_func, 420 void *cur_module_gcov_info, 421 gcov_unsigned_t cur_func_id) 422{ 423 if (cur_func == __gcov_direct_call_callee) 424 { 425 if (++__gcov_direct_call_sampling_counter >= __gcov_lipo_sampling_period) 426 { 427 __gcov_direct_call_sampling_counter = 0; 428 gcov_type global_id 429 = ((struct gcov_info *) cur_module_gcov_info)->mod_info->ident; 430 global_id = GEN_FUNC_GLOBAL_ID (global_id, cur_func_id); 431 __gcov_direct_call_counters[0] = global_id; 432 __gcov_direct_call_counters[1]++; 433 } 434 __gcov_direct_call_callee = 0; 435 } 436} 437#endif 438 439 440#ifdef L_gcov_time_profiler 441 442/* Counter for first visit of each function. */ 443static gcov_type function_counter; 444 445/* Sets corresponding COUNTERS if there is no value. */ 446 447void 448__gcov_time_profiler (gcov_type* counters) 449{ 450 if (!counters[0]) 451 counters[0] = ++function_counter; 452} 453#endif 454 455#ifdef L_gcov_average_profiler 456/* Increase corresponding COUNTER by VALUE. FIXME: Perhaps we want 457 to saturate up. */ 458 459void 460__gcov_average_profiler (gcov_type *counters, gcov_type value) 461{ 462 counters[0] += value; 463 counters[1] ++; 464} 465#endif 466 467#ifdef L_gcov_ior_profiler 468/* Bitwise-OR VALUE into COUNTER. */ 469 470void 471__gcov_ior_profiler (gcov_type *counters, gcov_type value) 472{ 473 *counters |= value; 474} 475#endif 476 477#endif /* inhibit_libc */ 478