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