1/* Routines required for instrumenting a program. */ 2/* Compile this one with gcc. */ 3/* Copyright (C) 1989-2015 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#ifdef L_gcov_one_value_profiler 89void 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 108static 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 204gcov_type *__gcov_indirect_call_topn_counters ATTRIBUTE_HIDDEN; 205 206#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 207__thread 208#endif 209void *__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 220void 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. */ 247void 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 271void * __gcov_indirect_call_callee; 272#if defined(HAVE_CC_TLS) && !defined (USE_EMUTLS) 273__thread 274#endif 275gcov_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. */ 286void 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. */ 302static gcov_type function_counter; 303 304/* Sets corresponding COUNTERS if there is no value. */ 305 306void 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 318void 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 329void 330__gcov_ior_profiler (gcov_type *counters, gcov_type value) 331{ 332 *counters |= value; 333} 334#endif 335 336#endif /* inhibit_libc */ 337