1 /* Routines required for instrumenting a program. */ 2 /* Compile this one with gcc. */ 3 /* Copyright (C) 1989-2018 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 */ 397