[PGO] Enable common VP format in profile runtime

[davidxl]

Summary

In this patch, the following changes are done

1. Enable emission of VP data in ValueProfData format using common API (now made available through InstrProfData.inc)

2. Removed the update of TotalValueDataSize
   • this reduced the number of atomtic operations (slow with high latency) executed during profile update
   • allows MIPS arch to enable value profiling -- which lacks the syn fetch-add support
   • Using TotalValueDataSize also has a fundamental problem that it always penalize the last function that gets profile collected -- if new values were added after buffer is created, last function's existing vp data (can be hot) may get dropped.
   • With the new approach in the patch, only the new values for any function are dropped (if any).

3. Added an extensive value profiling mock test. The test declares > 100 dummy caller functions and synthesize up to 128 value profile sites for each caller. Up to 8 values are added to each value site using profiler runtime VP interfaces.

[vsk]

lib/profile/InstrProfiling.c

66

nit, method

117

Is Data->Values supposed to be free'd at some point?

175

NULL?

test/profile/instrprof-value-prof.c

4

I might be doing this incorrectly but I get a syntax error here. Doesn't this need to be:

// RUN: llvm-profdata show --all-functions -ic-targets  %t.profdata | FileCheck \
// RUN: %s

51

return (intptr_t)p2 - (intptr_t)p1?

95

Will the CHECK lines break if the assumed mapping between function names and addresses changes?

[davidxl]

lib/profile/InstrProfiling.c

117

Fixed.

test/profile/instrprof-value-prof.c

4

Clang format did this, I think. Fixed.

95

Right - the callee address sorting should be removed. This is fixed now -- as the callee targets are properly ordered according to how the initializer for calleeAddr array is defined.

[davidxl]

Updated patch with vsk's comments.

[betulb]

One side comment on the commit message: Using TotalValueDataSize would only cause a drop of the last N function(s)' value data if/when file writing is to be triggered through means other than atexit() and calls to __llvm_profile_instrument_target are allowed to execute concurrently w/ file write. Neither is happening at this time.

lib/profile/InstrProfiling.c

70

Is the casting really needed? What's passed in is a __llvm_profile_data pointer, so
shouldn't Data->NumValueSites[ValueKind] be OK?

187

Nothing to free. So, just "return 0;" ?

223

Shouldn't line 223 check for !getValueProfDataSizeRT(R) and not for !I->Values? The new check also should happen after line 225.

[betulb]

betulb added a comment.

One side comment on the commit message: Using TotalValueDataSize would
only
cause a drop of the last N function(s)' value data if/when file writing is
to be triggered through means other than atexit() and calls to
__llvm_profile_instrument_target are allowed to execute concurrently w/
file
write. Neither is happening at this time.

Comment at: lib/profile/InstrProfiling.c:70
@@ +69,3 @@
+ uint32_t ValueKind, uint16_t
NumValueSites) {
+ *((uint16_t *)&Data->NumValueSites[ValueKind]) = NumValueSites;

+}

Is the casting really needed? What's passed in is a __llvm_profile_data
pointer, so
shouldn't Data->NumValueSites[ValueKind] be OK?

I see. It's needed to remove the const qualifier.

Comment at: lib/profile/InstrProfiling.c:188
@@ +187,3 @@
+ if (!Records)
+ goto Return;

+ /*

Nothing to free. So, just "return 0;" ?

Comment at: lib/profile/InstrProfiling.c:224
@@ +223,3 @@
+ if (!I->Values)
+ continue;

+ ValueProfRuntimeRecord *R = &Records[I - DataBegin];

Shouldn't line 223 check for !getValueProfDataSizeRT(R) and not for
!I->Values? The new check also should happen after line 225.

http://reviews.llvm.org/D15057

[davidxl]

lib/profile/InstrProfiling.c

70

the const qualifier needs to be removed.

223

You are right. I->Values is lazily initialized -- so I->Values == NULL does not mean we can skip it (only when there is zero value site statically). I need to enhance the test case to cover it.

[betulb]

lib/profile/InstrProfiling.c

223

I'm not sure if I'm following your concern about lazy initialization for I->Values.
The earlier loop initializes the ValueProfRuntimeRecord.

It did seemed to me that you're concerned about value data being dropped at file write time. If there is any scenario which can cause dropping of the value data in the previous implementation, then this new implementation could cause a buffer overwrite under the same circumstances, if a NULL entry for I->Values gets updated after the null check on line 194 and before line 223. But, I do not see any allowance for that at the moment.

[davidxl]

lib/profile/InstrProfiling.c

223

No -- I don't have a concern about I->Values being lazily initialized -- it is perfectly fine to do it -- just the writer code needs to handle it properly -- and your suggestion of not checking !I->Values is correct (also avoid the overwrite problem you mentioned here).

The value dropping problem as you mentioned can happen for the last 'N' function -- the main problem is that it can potentially lead to hot values gets truncated.

[davidxl]

Updated the patch according to Betul's feedback.

1. uses getNumValueKindsRT to determine if a function can be skipped (the size method will always return >0 size for the header due to indexed format restriction)
2. enhanced test case to cover the case when no value data is collected -- the resulting profile data should be mergable with the case when value profile data exist

The data race problem to I->Values still exist -- I will have a follow up patch to deal with it.

[davidxl]

Update the patch:

1. instead of pre-allocate RuntimeRecord which wastes heap space, we now just precomputes the base buffer size
2. an environment variable is introduced to allow user to allocate no default extra bytes to accommodate the case when concurrent profile update form other threads causes profile data to be dropped (due to to capacity limit)
3. verbose messages are added to diagnose various error conditions.

Patch to completely remove data races on Values field will follow.

[betulb]

LGTM.

[betulb]

My LGTM was for Diff 41674.

[davidxl]

The new version is functional equivalent to the previous diff -- but
more user friendly (in terms of runtime behavior). I will check in
this version (to remove one of the unwanted atomic operations) for now

• more comments are welcome after this.

David

lib/profile/InstrProfiling.c

 /*===- InstrProfiling.c - Support library for PGO instrumentation ---------===*\
 |*
 |*                     The LLVM Compiler Infrastructure
 |*
 |* This file is distributed under the University of Illinois Open Source
 |* License. See LICENSE.TXT for details.
 |*
 \*===----------------------------------------------------------------------===*/
 
 #include "InstrProfiling.h"
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
+#define INSTR_PROF_VALUE_PROF_DATA
+#define INSTR_PROF_COMMON_API_IMPL
+#include "InstrProfData.inc"
 
 LLVM_LIBRARY_VISIBILITY uint64_t __llvm_profile_get_magic(void) {
   return sizeof(void *) == sizeof(uint64_t) ? (INSTR_PROF_RAW_MAGIC_64)
                                             : (INSTR_PROF_RAW_MAGIC_32);
 }
 
 /* Return the number of bytes needed to add to SizeInBytes to make it
  *   the result a multiple of 8.
for (i = 0; i < CurrentVSiteCount; ++i) {
       while (CurrentVNode) {
         CurrentVNode->VData.Count = 0;
         CurrentVNode = CurrentVNode->Next;
       }
     }
   }
 }
 
-/* Total number of value profile data in bytes. */
-static uint64_t TotalValueDataSize = 0;
-
-#ifdef _MIPS_ARCH
+/* This methid is only used in value profiler mock testing.  */
 LLVM_LIBRARY_VISIBILITY void
-__llvm_profile_instrument_target(uint64_t TargetValue, void *Data_,
-                                 uint32_t CounterIndex) {}
-
-#else
+__llvm_profile_set_num_value_sites(__llvm_profile_data *Data,
+                                   uint32_t ValueKind, uint16_t NumValueSites) {
+  *((uint16_t *)&Data->NumValueSites[ValueKind]) = NumValueSites;
+}
+/* This methid is only used in value profiler mock testing.  */
+LLVM_LIBRARY_VISIBILITY const __llvm_profile_data *
+__llvm_profile_iterate_data(const __llvm_profile_data *Data) {
+  return Data + 1;
+}
+LLVM_LIBRARY_VISIBILITY void *
+__llvm_get_function_addr(const __llvm_profile_data *Data) {
+  return Data->FunctionPointer;
+}
 
 /* Allocate an array that holds the pointers to the linked lists of
  * value profile counter nodes. The number of element of the array
  * is the total number of value profile sites instrumented. Returns
- *  0 if allocation fails.
+ * 0 if allocation fails.
  */
 
 static int allocateValueProfileCounters(__llvm_profile_data *Data) {
   uint64_t NumVSites = 0;
   uint32_t VKI;
   for (VKI = IPVK_First; VKI <= IPVK_Last; ++VKI)
     NumVSites += Data->NumValueSites[VKI];
 
   ValueProfNode **Mem =
       (ValueProfNode **)calloc(NumVSites, sizeof(ValueProfNode *));
   if (!Mem)
     return 0;
   if (!__sync_bool_compare_and_swap(&Data->Values, 0, Mem)) {
     free(Mem);
     return 0;
   }
-  /*  In the raw format, there will be an value count array preceding
-   *  the value profile data. The element type of the array is uint8_t,
-   *  and there is one element in array per value site. The element
-   *  stores the number of values profiled for the corresponding site.
-   */
-  uint8_t Padding = __llvm_profile_get_num_padding_bytes(NumVSites);
-  __sync_fetch_and_add(&TotalValueDataSize, NumVSites + Padding);
   return 1;
 }
 
+static void deallocateValueProfileCounters(__llvm_profile_data *Data) {
+  uint64_t NumVSites = 0, I;
+  uint32_t VKI;
+  for (VKI = IPVK_First; VKI <= IPVK_Last; ++VKI)
+    NumVSites += Data->NumValueSites[VKI];
+  for (I = 0; I < NumVSites; I++) {
+    ValueProfNode *Node = ((ValueProfNode **)Data->Values)[I];
+    while (Node) {
+      ValueProfNode *Next = Node->Next;
+      free(Node);
+      Node = Next;
+    }
+  }
+}
+
 LLVM_LIBRARY_VISIBILITY void
 __llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
                                  uint32_t CounterIndex) {
 
   __llvm_profile_data *PData = (__llvm_profile_data *)Data;
   if (!PData)
     return;
 
Success = __sync_bool_compare_and_swap(&ValueCounters[CounterIndex], 0,
                                            CurrentVNode);
   else if (PrevVNode && !PrevVNode->Next)
     Success = __sync_bool_compare_and_swap(&(PrevVNode->Next), 0, CurrentVNode);
 
   if (!Success) {
     free(CurrentVNode);
     return;
   }
-  __sync_fetch_and_add(&TotalValueDataSize, Success * sizeof(ValueProfNode));
 }
-#endif
 
 LLVM_LIBRARY_VISIBILITY uint64_t
 __llvm_profile_gather_value_data(uint8_t **VDataArray) {
-
-  if (!VDataArray || 0 == TotalValueDataSize)
-    return 0;
-
-  uint64_t NumData = TotalValueDataSize;
-  *VDataArray = (uint8_t *)calloc(NumData, sizeof(uint8_t));
-  if (!*VDataArray)
+  size_t S = 0, TotalSize = 0;
+  __llvm_profile_data *I;
+  ValueProfRuntimeRecord *Records = 0;
+  if (!VDataArray)
     return 0;
 
-  uint8_t *VDataEnd = *VDataArray + NumData;
-  uint8_t *PerSiteCountsHead = *VDataArray;
   const __llvm_profile_data *DataEnd = __llvm_profile_end_data();
   const __llvm_profile_data *DataBegin = __llvm_profile_begin_data();
-  __llvm_profile_data *I;
-  for (I = (__llvm_profile_data *)DataBegin; I != DataEnd; ++I) {
+  size_t ND = DataEnd - DataBegin;
 
-    uint64_t NumVSites = 0;
-    uint32_t VKI, i;
+  Records =
+      (ValueProfRuntimeRecord *)calloc(sizeof(ValueProfRuntimeRecord), ND);
 
+  if (!Records)
+    goto Return;
+  /*
+   * Compute the total Size of the buffer to hold ValueProfData
+   * structures for functions with value profile data.
+   */
+  for (I = (__llvm_profile_data *)DataBegin; I != DataEnd; ++I) {
     if (!I->Values)
       continue;
+    ValueProfRuntimeRecord *R = &Records[I - DataBegin];
+    /* Extract the value profile data info from the runtime. */
+    if (initializeValueProfRuntimeRecord(R, I->NumValueSites, I->Values))
+      goto Return;
+    /* Compute the size of ValueProfData from this runtime record.  */
+    S += getValueProfDataSizeRT(R);
+  }
+  /* No value sites or no value profile data is collected. */
+  if (!S)
+    goto Return;
 
-    ValueProfNode **ValueCounters = (ValueProfNode **)I->Values;
-
-    for (VKI = IPVK_First; VKI <= IPVK_Last; ++VKI)
-      NumVSites += I->NumValueSites[VKI];
-    uint8_t Padding = __llvm_profile_get_num_padding_bytes(NumVSites);
-
-    uint8_t *PerSiteCountPtr = PerSiteCountsHead;
-    InstrProfValueData *VDataPtr =
-        (InstrProfValueData *)(PerSiteCountPtr + NumVSites + Padding);
-
-    for (i = 0; i < NumVSites; ++i) {
-
-      ValueProfNode *VNode = ValueCounters[i];
+  *VDataArray = calloc(S, sizeof(uint8_t));
+  if (!*VDataArray)
+    goto Return;
 
-      uint8_t VDataCount = 0;
-      while (VNode && ((uint8_t *)(VDataPtr + 1) <= VDataEnd)) {
-        *VDataPtr = VNode->VData;
-        VNode = VNode->Next;
-        ++VDataPtr;
-        if (++VDataCount == UCHAR_MAX)
-          break;
-      }
-      *PerSiteCountPtr = VDataCount;
-      ++PerSiteCountPtr;
-    }
-    I->Values = (void *)PerSiteCountsHead;
-    PerSiteCountsHead = (uint8_t *)VDataPtr;
-  }
-  return PerSiteCountsHead - *VDataArray;
+  /* Now commit the final total size to be returned.  */
+  TotalSize = S;
+  ValueProfData *VD = (ValueProfData *)(*VDataArray);
+  /*
+   * Extract value profile data and write into ValueProfData structure
+   * one by one. Note that new value profile data added to any value
+   * site (from another thread) after the ValueProfRuntimeRecord is
+   * initialized (when the profile data snapshot is taken) won't be
+   * collected. This is not a problem as those dropped value will have
+   * very low taken count.
+   */
+  for (I = (__llvm_profile_data *)DataBegin; I != DataEnd; ++I) {
+    if (!I->Values)
+      continue;
+    ValueProfRuntimeRecord *R = &Records[I - DataBegin];
+    serializeValueProfDataFromRT(R, VD);
+    deallocateValueProfileCounters(I);
+    I->Values = VD;
+    finalizeValueProfRuntimeRecord(R);
+    VD = (ValueProfData *)((char *)VD + VD->TotalSize);
+  }
+Return:
+  if (Records)
+    free(Records);
+  return TotalSize;
 }

test/profile/instrprof-value-prof.c

+// RUN: %clang_profgen -O2 -o %t %s
+// RUN: env LLVM_PROFILE_FILE=%t.profraw %run %t
+// RUN: llvm-profdata merge -o %t.profdata %t.profraw
+// RUN: llvm-profdata show --all-functions -ic-targets  %t.profdata | FileCheck
+// %s
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+typedef struct __llvm_profile_data __llvm_profile_data;
+const __llvm_profile_data *__llvm_profile_begin_data(void);
+const __llvm_profile_data *__llvm_profile_end_data(void);
+void __llvm_profile_set_num_value_sites(__llvm_profile_data *Data,
+                                        uint32_t ValueKind,
+                                        uint16_t NumValueSites);
+__llvm_profile_data *
+__llvm_profile_iterate_data(const __llvm_profile_data *Data);
+void *__llvm_get_function_addr(const __llvm_profile_data *Data);
+void __llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
+                                      uint32_t CounterIndex);
+
+#define DEF_FUNC(x)                                                            \
+  void x() {}
+#define DEF_2_FUNCS(x) DEF_FUNC(x##_1) DEF_FUNC(x##_2)
+#define DEF_4_FUNCS(x) DEF_2_FUNCS(x##_1) DEF_2_FUNCS(x##_2)
+#define DEF_8_FUNCS(x) DEF_4_FUNCS(x##_1) DEF_4_FUNCS(x##_2)
+#define DEF_16_FUNCS(x) DEF_8_FUNCS(x##_1) DEF_8_FUNCS(x##_2)
+#define DEF_32_FUNCS(x) DEF_16_FUNCS(x##_1) DEF_16_FUNCS(x##_2)
+#define DEF_64_FUNCS(x) DEF_32_FUNCS(x##_1) DEF_32_FUNCS(x##_2)
+#define DEF_128_FUNCS(x) DEF_64_FUNCS(x##_1) DEF_64_FUNCS(x##_2)
+
+#define FUNC_ADDR(x) &x,
+#define FUNC_2_ADDRS(x) FUNC_ADDR(x##_1) FUNC_ADDR(x##_2)
+#define FUNC_4_ADDRS(x) FUNC_2_ADDRS(x##_1) FUNC_2_ADDRS(x##_2)
+#define FUNC_8_ADDRS(x) FUNC_4_ADDRS(x##_1) FUNC_4_ADDRS(x##_2)
+#define FUNC_16_ADDRS(x) FUNC_8_ADDRS(x##_1) FUNC_8_ADDRS(x##_2)
+#define FUNC_32_ADDRS(x) FUNC_16_ADDRS(x##_1) FUNC_16_ADDRS(x##_2)
+#define FUNC_64_ADDRS(x) FUNC_32_ADDRS(x##_1) FUNC_32_ADDRS(x##_2)
+#define FUNC_128_ADDRS(x) FUNC_64_ADDRS(x##_1) FUNC_64_ADDRS(x##_2)
+
+DEF_8_FUNCS(callee)
+DEF_128_FUNCS(caller)
+
+void *CallerAddrs[] = {FUNC_128_ADDRS(caller)};
+
+void *CalleeAddrs[] = {FUNC_8_ADDRS(callee)};
+
+static int cmpaddr(const void *p1, const void *p2) {
+  void *addr1 = *(void **)p1;
+  void *addr2 = *(void **)p2;
+  if (addr1 < addr2)
+    return 1;
+  if (addr1 == addr2)
+    return 0;
+  return -1;
+}
+
+int main(int argc, const char *argv[]) {
+  unsigned S, NS = 0, V;
+  const __llvm_profile_data *Data, *DataEnd;
+  void *key = &caller_2_2_2_2_1_2_2;
+  qsort(CallerAddrs, sizeof(CallerAddrs) / sizeof(void *), sizeof(void *),
+        cmpaddr);
+  qsort(CalleeAddrs, sizeof(CalleeAddrs) / sizeof(void *), sizeof(void *),
+        cmpaddr);
+
+  /* We will synthesis value profile data for 128 callers functions.
+   * The number of * value sites. The number values for each value site
+   * ranges from 0 to 8.  */
+
+  Data = __llvm_profile_begin_data();
+  DataEnd = __llvm_profile_end_data();
+
+  for (; Data < DataEnd; Data = __llvm_profile_iterate_data(Data)) {
+    void *func = __llvm_get_function_addr(Data);
+    if (bsearch(&func, CallerAddrs, sizeof(CallerAddrs) / sizeof(void *),
+                sizeof(void *), cmpaddr)) {
+      __llvm_profile_set_num_value_sites((__llvm_profile_data *)Data,
+                                         0 /*IPVK_IndirectCallTarget */, NS);
+      for (S = 0; S < NS; S++) {
+        for (V = 0; V < S % 8; V++) {
+          unsigned C;
+          for (C = 0; C < V + 1; C++)
+            __llvm_profile_instrument_target((uint64_t)CalleeAddrs[V],
+                                             (void *)Data, S);
+        }
+      }
+      NS++;
+    }
+  }
+}
+
+// CHECK: Indirect Call Site Count: 127
+// CHECK-NEXT: Indirect Target Results:
+// CHECK-NEXT:  [ 1, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 2, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 2, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 3, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 3, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 3, callee_2_1_2, 3 ]
+// CHECK-NEXT:  [ 4, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 4, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 4, callee_2_1_2, 3 ]
+// CHECK-NEXT:  [ 4, callee_2_1_1, 4 ]
+// CHECK-NEXT:  [ 5, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 5, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 5, callee_2_1_2, 3 ]
+// CHECK-NEXT:  [ 5, callee_2_1_1, 4 ]
+// CHECK-NEXT:  [ 5, callee_1_2_2, 5 ]
+// CHECK-NEXT:  [ 6, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 6, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 6, callee_2_1_2, 3 ]
+// CHECK-NEXT:  [ 6, callee_2_1_1, 4 ]
+// CHECK-NEXT:  [ 6, callee_1_2_2, 5 ]
+// CHECK-NEXT:  [ 6, callee_1_2_1, 6 ]
+// CHECK-NEXT:  [ 7, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 7, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 7, callee_2_1_2, 3 ]
+// CHECK-NEXT:  [ 7, callee_2_1_1, 4 ]
+// CHECK-NEXT:  [ 7, callee_1_2_2, 5 ]
+// CHECK-NEXT:  [ 7, callee_1_2_1, 6 ]
+// CHECK-NEXT:  [ 7, callee_1_1_2, 7 ]
+// CHECK-NEXT:  [ 9, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 10, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 10, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 11, callee_2_2_2, 1 ]
+// CHECK-NEXT:  [ 11, callee_2_2_1, 2 ]
+// CHECK-NEXT:  [ 11, callee_2_1_2, 3 ]