contrib/compiler-rt/lib/profile/InstrProfilingValue.c

   1 /*===- InstrProfilingValue.c - Support library for PGO instrumentation ----===*\
   2 |*
   3 |*                     The LLVM Compiler Infrastructure
   4 |*
   5 |* This file is distributed under the University of Illinois Open Source
   6 |* License. See LICENSE.TXT for details.
   7 |*
   8 \*===----------------------------------------------------------------------===*/
   9
  10 #include <limits.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 #include "InstrProfiling.h"
  16 #include "InstrProfilingInternal.h"
  17 #include "InstrProfilingUtil.h"
  18
  19 #define INSTR_PROF_VALUE_PROF_DATA
  20 #define INSTR_PROF_COMMON_API_IMPL
  21 #include "InstrProfData.inc"
  22
  23 static int hasStaticCounters = 1;
  24 static int OutOfNodesWarnings = 0;
  25 static int hasNonDefaultValsPerSite = 0;
  26 #define INSTR_PROF_MAX_VP_WARNS 10
  27 #define INSTR_PROF_DEFAULT_NUM_VAL_PER_SITE 16
  28 #define INSTR_PROF_VNODE_POOL_SIZE 1024
  29
  30 #ifndef _MSC_VER
  31 /* A shared static pool in addition to the vnodes statically
  32  * allocated by the compiler.  */
  33 COMPILER_RT_VISIBILITY ValueProfNode
  34     lprofValueProfNodes[INSTR_PROF_VNODE_POOL_SIZE] COMPILER_RT_SECTION(
  35        COMPILER_RT_SEG INSTR_PROF_VNODES_SECT_NAME_STR);
  36 #endif
  37
  38 COMPILER_RT_VISIBILITY uint32_t VPMaxNumValsPerSite =
  39     INSTR_PROF_DEFAULT_NUM_VAL_PER_SITE;
  40
  41 COMPILER_RT_VISIBILITY void lprofSetupValueProfiler() {
  42   const char *Str = 0;
  43   Str = getenv("LLVM_VP_MAX_NUM_VALS_PER_SITE");
  44   if (Str && Str[0]) {
  45     VPMaxNumValsPerSite = atoi(Str);
  46     hasNonDefaultValsPerSite = 1;
  47   }
  48   if (VPMaxNumValsPerSite > INSTR_PROF_MAX_NUM_VAL_PER_SITE)
  49     VPMaxNumValsPerSite = INSTR_PROF_MAX_NUM_VAL_PER_SITE;
  50 }
  51
  52 COMPILER_RT_VISIBILITY void lprofSetMaxValsPerSite(uint32_t MaxVals) {
  53   VPMaxNumValsPerSite = MaxVals;
  54   hasNonDefaultValsPerSite = 1;
  55 }
  56
  57 /* This method is only used in value profiler mock testing.  */
  58 COMPILER_RT_VISIBILITY void
  59 __llvm_profile_set_num_value_sites(__llvm_profile_data *Data,
  60                                    uint32_t ValueKind, uint16_t NumValueSites) {
  61   *((uint16_t *)&Data->NumValueSites[ValueKind]) = NumValueSites;
  62 }
  63
  64 /* This method is only used in value profiler mock testing.  */
  65 COMPILER_RT_VISIBILITY const __llvm_profile_data *
  66 __llvm_profile_iterate_data(const __llvm_profile_data *Data) {
  67   return Data + 1;
  68 }
  69
  70 /* This method is only used in value profiler mock testing.  */
  71 COMPILER_RT_VISIBILITY void *
  72 __llvm_get_function_addr(const __llvm_profile_data *Data) {
  73   return Data->FunctionPointer;
  74 }
  75
  76 /* Allocate an array that holds the pointers to the linked lists of
  77  * value profile counter nodes. The number of element of the array
  78  * is the total number of value profile sites instrumented. Returns
  79  * 0 if allocation fails.
  80  */
  81
  82 static int allocateValueProfileCounters(__llvm_profile_data *Data) {
  83   uint64_t NumVSites = 0;
  84   uint32_t VKI;
  85
  86   /* This function will never be called when value site array is allocated
  87      statically at compile time.  */
  88   hasStaticCounters = 0;
  89   /* When dynamic allocation is enabled, allow tracking the max number of
  90    * values allowd.  */
  91   if (!hasNonDefaultValsPerSite)
  92     VPMaxNumValsPerSite = INSTR_PROF_MAX_NUM_VAL_PER_SITE;
  93
  94   for (VKI = IPVK_First; VKI <= IPVK_Last; ++VKI)
  95     NumVSites += Data->NumValueSites[VKI];
  96
  97   ValueProfNode **Mem =
  98       (ValueProfNode **)calloc(NumVSites, sizeof(ValueProfNode *));
  99   if (!Mem)
 100     return 0;
 101   if (!COMPILER_RT_BOOL_CMPXCHG(&Data->Values, 0, Mem)) {
 102     free(Mem);
 103     return 0;
 104   }
 105   return 1;
 106 }
 107
 108 static ValueProfNode *allocateOneNode(__llvm_profile_data *Data, uint32_t Index,
 109                                       uint64_t Value) {
 110   ValueProfNode *Node;
 111
 112   if (!hasStaticCounters)
 113     return (ValueProfNode *)calloc(1, sizeof(ValueProfNode));
 114
 115   /* Early check to avoid value wrapping around.  */
 116   if (CurrentVNode + 1 > EndVNode) {
 117     if (OutOfNodesWarnings++ < INSTR_PROF_MAX_VP_WARNS) {
 118       PROF_WARN("Unable to track new values: %s. "
 119                 " Consider using option -mllvm -vp-counters-per-site=<n> to "
 120                 "allocate more"
 121                 " value profile counters at compile time. \n",
 122                 "Running out of static counters");
 123     }
 124     return 0;
 125   }
 126   Node = COMPILER_RT_PTR_FETCH_ADD(ValueProfNode, CurrentVNode, 1);
 127   /* Due to section padding, EndVNode point to a byte which is one pass
 128    * an incomplete VNode, so we need to skip the last incomplete node. */
 129   if (Node + 1 > EndVNode)
 130     return 0;
 131
 132   return Node;
 133 }
 134
 135 static COMPILER_RT_ALWAYS_INLINE void
 136 instrumentTargetValueImpl(uint64_t TargetValue, void *Data,
 137                           uint32_t CounterIndex, uint64_t CountValue) {
 138   __llvm_profile_data *PData = (__llvm_profile_data *)Data;
 139   if (!PData)
 140     return;
 141   if (!CountValue)
 142     return;
 143   if (!PData->Values) {
 144     if (!allocateValueProfileCounters(PData))
 145       return;
 146   }
 147
 148   ValueProfNode **ValueCounters = (ValueProfNode **)PData->Values;
 149   ValueProfNode *PrevVNode = NULL;
 150   ValueProfNode *MinCountVNode = NULL;
 151   ValueProfNode *CurVNode = ValueCounters[CounterIndex];
 152   uint64_t MinCount = UINT64_MAX;
 153
 154   uint8_t VDataCount = 0;
 155   while (CurVNode) {
 156     if (TargetValue == CurVNode->Value) {
 157       CurVNode->Count += CountValue;
 158       return;
 159     }
 160     if (CurVNode->Count < MinCount) {
 161       MinCount = CurVNode->Count;
 162       MinCountVNode = CurVNode;
 163     }
 164     PrevVNode = CurVNode;
 165     CurVNode = CurVNode->Next;
 166     ++VDataCount;
 167   }
 168
 169   if (VDataCount >= VPMaxNumValsPerSite) {
 170     /* Bump down the min count node's count. If it reaches 0,
 171      * evict it. This eviction/replacement policy makes hot
 172      * targets more sticky while cold targets less so. In other
 173      * words, it makes it less likely for the hot targets to be
 174      * prematurally evicted during warmup/establishment period,
 175      * when their counts are still low. In a special case when
 176      * the number of values tracked is reduced to only one, this
 177      * policy will guarantee that the dominating target with >50%
 178      * total count will survive in the end. Note that this scheme
 179      * allows the runtime to track the min count node in an adaptive
 180      * manner. It can correct previous mistakes and eventually
 181      * lock on a cold target that is alread in stable state.
 182      *
 183      * In very rare cases,  this replacement scheme may still lead
 184      * to target loss. For instance, out of \c N value slots, \c N-1
 185      * slots are occupied by luke warm targets during the warmup
 186      * period and the remaining one slot is competed by two or more
 187      * very hot targets. If those hot targets occur in an interleaved
 188      * way, none of them will survive (gain enough weight to throw out
 189      * other established entries) due to the ping-pong effect.
 190      * To handle this situation, user can choose to increase the max
 191      * number of tracked values per value site. Alternatively, a more
 192      * expensive eviction mechanism can be implemented. It requires
 193      * the runtime to track the total number of evictions per-site.
 194      * When the total number of evictions reaches certain threshold,
 195      * the runtime can wipe out more than one lowest count entries
 196      * to give space for hot targets.
 197      */
 198     if (MinCountVNode->Count <= CountValue) {
 199       CurVNode = MinCountVNode;
 200       CurVNode->Value = TargetValue;
 201       CurVNode->Count = CountValue;
 202     } else
 203       MinCountVNode->Count -= CountValue;
 204
 205     return;
 206   }
 207
 208   CurVNode = allocateOneNode(PData, CounterIndex, TargetValue);
 209   if (!CurVNode)
 210     return;
 211   CurVNode->Value = TargetValue;
 212   CurVNode->Count += CountValue;
 213
 214   uint32_t Success = 0;
 215   if (!ValueCounters[CounterIndex])
 216     Success =
 217         COMPILER_RT_BOOL_CMPXCHG(&ValueCounters[CounterIndex], 0, CurVNode);
 218   else if (PrevVNode && !PrevVNode->Next)
 219     Success = COMPILER_RT_BOOL_CMPXCHG(&(PrevVNode->Next), 0, CurVNode);
 220
 221   if (!Success && !hasStaticCounters) {
 222     free(CurVNode);
 223     return;
 224   }
 225 }
 226
 227 COMPILER_RT_VISIBILITY void
 228 __llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
 229                                  uint32_t CounterIndex) {
 230   instrumentTargetValueImpl(TargetValue, Data, CounterIndex, 1);
 231 }
 232 COMPILER_RT_VISIBILITY void
 233 __llvm_profile_instrument_target_value(uint64_t TargetValue, void *Data,
 234                                        uint32_t CounterIndex,
 235                                        uint64_t CountValue) {
 236   instrumentTargetValueImpl(TargetValue, Data, CounterIndex, CountValue);
 237 }
 238
 239 /*
 240  * The target values are partitioned into multiple regions/ranges. There is one
 241  * contiguous region which is precise -- every value in the range is tracked
 242  * individually. A value outside the precise region will be collapsed into one
 243  * value depending on the region it falls in.
 244  *
 245  * There are three regions:
 246  * 1. (-inf, PreciseRangeStart) and (PreciseRangeLast, LargeRangeValue) belong
 247  * to one region -- all values here should be mapped to one value of
 248  * "PreciseRangeLast + 1".
 249  * 2. [PreciseRangeStart, PreciseRangeLast]
 250  * 3. Large values: [LargeValue, +inf) maps to one value of LargeValue.
 251  *
 252  * The range for large values is optional. The default value of INT64_MIN
 253  * indicates it is not specified.
 254  */
 255 COMPILER_RT_VISIBILITY void __llvm_profile_instrument_range(
 256     uint64_t TargetValue, void *Data, uint32_t CounterIndex,
 257     int64_t PreciseRangeStart, int64_t PreciseRangeLast, int64_t LargeValue) {
 258
 259   if (LargeValue != INT64_MIN && (int64_t)TargetValue >= LargeValue)
 260     TargetValue = LargeValue;
 261   else if ((int64_t)TargetValue < PreciseRangeStart ||
 262            (int64_t)TargetValue > PreciseRangeLast)
 263     TargetValue = PreciseRangeLast + 1;
 264
 265   __llvm_profile_instrument_target(TargetValue, Data, CounterIndex);
 266 }
 267
 268 /*
 269  * A wrapper struct that represents value profile runtime data.
 270  * Like InstrProfRecord class which is used by profiling host tools,
 271  * ValueProfRuntimeRecord also implements the abstract intefaces defined in
 272  * ValueProfRecordClosure so that the runtime data can be serialized using
 273  * shared C implementation.
 274  */
 275 typedef struct ValueProfRuntimeRecord {
 276   const __llvm_profile_data *Data;
 277   ValueProfNode **NodesKind[IPVK_Last + 1];
 278   uint8_t **SiteCountArray;
 279 } ValueProfRuntimeRecord;
 280
 281 /* ValueProfRecordClosure Interface implementation. */
 282
 283 static uint32_t getNumValueSitesRT(const void *R, uint32_t VK) {
 284   return ((const ValueProfRuntimeRecord *)R)->Data->NumValueSites[VK];
 285 }
 286
 287 static uint32_t getNumValueDataRT(const void *R, uint32_t VK) {
 288   uint32_t S = 0, I;
 289   const ValueProfRuntimeRecord *Record = (const ValueProfRuntimeRecord *)R;
 290   if (Record->SiteCountArray[VK] == INSTR_PROF_NULLPTR)
 291     return 0;
 292   for (I = 0; I < Record->Data->NumValueSites[VK]; I++)
 293     S += Record->SiteCountArray[VK][I];
 294   return S;
 295 }
 296
 297 static uint32_t getNumValueDataForSiteRT(const void *R, uint32_t VK,
 298                                          uint32_t S) {
 299   const ValueProfRuntimeRecord *Record = (const ValueProfRuntimeRecord *)R;
 300   return Record->SiteCountArray[VK][S];
 301 }
 302
 303 static ValueProfRuntimeRecord RTRecord;
 304 static ValueProfRecordClosure RTRecordClosure = {
 305     &RTRecord,          INSTR_PROF_NULLPTR, /* GetNumValueKinds */
 306     getNumValueSitesRT, getNumValueDataRT,  getNumValueDataForSiteRT,
 307     INSTR_PROF_NULLPTR, /* RemapValueData */
 308     INSTR_PROF_NULLPTR, /* GetValueForSite, */
 309     INSTR_PROF_NULLPTR  /* AllocValueProfData */
 310 };
 311
 312 static uint32_t
 313 initializeValueProfRuntimeRecord(const __llvm_profile_data *Data,
 314                                  uint8_t *SiteCountArray[]) {
 315   unsigned I, J, S = 0, NumValueKinds = 0;
 316   ValueProfNode **Nodes = (ValueProfNode **)Data->Values;
 317   RTRecord.Data = Data;
 318   RTRecord.SiteCountArray = SiteCountArray;
 319   for (I = 0; I <= IPVK_Last; I++) {
 320     uint16_t N = Data->NumValueSites[I];
 321     if (!N)
 322       continue;
 323
 324     NumValueKinds++;
 325
 326     RTRecord.NodesKind[I] = Nodes ? &Nodes[S] : INSTR_PROF_NULLPTR;
 327     for (J = 0; J < N; J++) {
 328       /* Compute value count for each site. */
 329       uint32_t C = 0;
 330       ValueProfNode *Site =
 331           Nodes ? RTRecord.NodesKind[I][J] : INSTR_PROF_NULLPTR;
 332       while (Site) {
 333         C++;
 334         Site = Site->Next;
 335       }
 336       if (C > UCHAR_MAX)
 337         C = UCHAR_MAX;
 338       RTRecord.SiteCountArray[I][J] = C;
 339     }
 340     S += N;
 341   }
 342   return NumValueKinds;
 343 }
 344
 345 static ValueProfNode *getNextNValueData(uint32_t VK, uint32_t Site,
 346                                         InstrProfValueData *Dst,
 347                                         ValueProfNode *StartNode, uint32_t N) {
 348   unsigned I;
 349   ValueProfNode *VNode = StartNode ? StartNode : RTRecord.NodesKind[VK][Site];
 350   for (I = 0; I < N; I++) {
 351     Dst[I].Value = VNode->Value;
 352     Dst[I].Count = VNode->Count;
 353     VNode = VNode->Next;
 354   }
 355   return VNode;
 356 }
 357
 358 static uint32_t getValueProfDataSizeWrapper(void) {
 359   return getValueProfDataSize(&RTRecordClosure);
 360 }
 361
 362 static uint32_t getNumValueDataForSiteWrapper(uint32_t VK, uint32_t S) {
 363   return getNumValueDataForSiteRT(&RTRecord, VK, S);
 364 }
 365
 366 static VPDataReaderType TheVPDataReader = {
 367     initializeValueProfRuntimeRecord, getValueProfRecordHeaderSize,
 368     getFirstValueProfRecord,          getNumValueDataForSiteWrapper,
 369     getValueProfDataSizeWrapper,      getNextNValueData};
 370
 371 COMPILER_RT_VISIBILITY VPDataReaderType *lprofGetVPDataReader() {
 372   return &TheVPDataReader;
 373 }