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