[PGO] Runtime support for value profiling.

This change adds extends the data structures and adds in the routines
for handling runtime calls for value profiling. The profile data format
is modified and the version number is incremented.



git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@253483 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 215 insertions, 7 deletions

diff --git a/lib/profile/InstrProfiling.c b/lib/profile/InstrProfiling.c
index 8d010df28..42779acc7 100644
--- a/lib/profile/InstrProfiling.c
+++ b/lib/profile/InstrProfiling.c
@@ -8,6 +8,8 @@
 \*===----------------------------------------------------------------------===*/
 
 #include "InstrProfiling.h"
+#include <limits.h>
+#include <stdlib.h>
 #include <string.h>
 
 __attribute__((visibility("hidden")))
@@ -34,9 +36,14 @@ uint64_t __llvm_profile_get_magic(void) {
 }
 
 __attribute__((visibility("hidden")))
+uint8_t __llvm_profile_get_num_padding_bytes(uint64_t SizeInBytes) {
+  return 7 & (sizeof(uint64_t) - SizeInBytes % sizeof(uint64_t));
+}
+
+__attribute__((visibility("hidden")))
 uint64_t __llvm_profile_get_version(void) {
   /* This should be bumped any time the output format changes. */
-  return 1;
+  return 2;
 }
 
 __attribute__((visibility("hidden")))
@@ -45,4 +52,143 @@ void __llvm_profile_reset_counters(void) {
   uint64_t *E = __llvm_profile_end_counters();
 
   memset(I, 0, sizeof(uint64_t)*(E - I));
+
+  const __llvm_profile_data *DataBegin = __llvm_profile_begin_data();
+  const __llvm_profile_data *DataEnd = __llvm_profile_end_data();
+  for (const __llvm_profile_data *DI = DataBegin; DI != DataEnd; ++DI) {
+    if (!DI->ValueCounters)
+      continue;
+
+    uint64_t CurrentVSiteCount = 0;
+    for (uint32_t VKI = VK_FIRST; VKI <= VK_LAST; ++VKI)
+      CurrentVSiteCount += DI->NumValueSites[VKI];
+
+    for (uint32_t i = 0; i < CurrentVSiteCount; ++i) {
+      __llvm_profile_value_node *CurrentVNode = DI->ValueCounters[i];
+
+      while (CurrentVNode) {
+        CurrentVNode->VData.NumTaken = 0;
+        CurrentVNode = CurrentVNode->Next;
+      }
+    }
+  }
+}
+
+static uint64_t TotalValueDataSize = 0;
+
+__attribute__((visibility("hidden")))
+void __llvm_profile_instrument_target(uint64_t TargetValue, void *Data_,
+  uint32_t CounterIndex) {
+
+  __llvm_profile_data *Data = (__llvm_profile_data*)Data_;
+  if (!Data)
+    return;
+
+  if (!Data->ValueCounters) {
+    uint64_t NumVSites = 0;
+    for (uint32_t VKI = VK_FIRST; VKI <= VK_LAST; ++VKI)
+      NumVSites += Data->NumValueSites[VKI];
+
+    __llvm_profile_value_node** Mem = (__llvm_profile_value_node**)
+        calloc(NumVSites, sizeof(__llvm_profile_value_node*));
+    if (!Mem)
+      return;
+    if (!__sync_bool_compare_and_swap(&Data->ValueCounters, 0, Mem)) {
+      free(Mem);
+      return;
+    }
+    // Acccount for padding during write out.
+    uint8_t Padding = __llvm_profile_get_num_padding_bytes(NumVSites);
+    __sync_fetch_and_add(&TotalValueDataSize, NumVSites + Padding);
+  }
+
+  __llvm_profile_value_node *PrevVNode = NULL;
+  __llvm_profile_value_node *CurrentVNode = Data->ValueCounters[CounterIndex];
+
+  uint8_t VDataCount = 0;
+  while (CurrentVNode) {
+    if (TargetValue == CurrentVNode->VData.TargetValue) {
+      CurrentVNode->VData.NumTaken++;
+      return;
+    }
+    PrevVNode = CurrentVNode;
+    CurrentVNode = CurrentVNode->Next;
+    ++VDataCount;
+  }
+
+  if (VDataCount >= UCHAR_MAX)
+    return;
+
+  CurrentVNode = (__llvm_profile_value_node*)
+    calloc(1, sizeof(__llvm_profile_value_node));
+  if (!CurrentVNode)
+    return;
+
+  CurrentVNode->VData.TargetValue = TargetValue;
+  CurrentVNode->VData.NumTaken++;
+
+  uint32_t Success = 0;
+  if (!Data->ValueCounters[CounterIndex])
+   Success = __sync_bool_compare_and_swap(
+      &(Data->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(__llvm_profile_value_data));
+}
+
+__attribute__((visibility("hidden")))
+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)
+    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();
+  for (__llvm_profile_data *I = (__llvm_profile_data *)DataBegin;
+       I != DataEnd; ++I) {
+
+    if (!I->ValueCounters)
+      continue;
+
+    uint64_t NumVSites = 0;
+    for (uint32_t VKI = VK_FIRST; VKI <= VK_LAST; ++VKI)
+      NumVSites += I->NumValueSites[VKI];
+    uint8_t Padding = __llvm_profile_get_num_padding_bytes(NumVSites);
+
+    uint8_t *PerSiteCountPtr = PerSiteCountsHead;
+    __llvm_profile_value_data *VDataPtr =
+        (__llvm_profile_value_data *)(PerSiteCountPtr + NumVSites + Padding);
+
+    for (uint32_t i = 0; i < NumVSites; ++i) {
+
+      __llvm_profile_value_node *VNode = I->ValueCounters[i];
+
+      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->ValueCounters = (void *)PerSiteCountsHead;
+    PerSiteCountsHead = (uint8_t *)VDataPtr;
+  }
+  return PerSiteCountsHead - *VDataArray;
 }
diff --git a/lib/profile/InstrProfiling.h b/lib/profile/InstrProfiling.h
index fb6e32a47..15a25abe9 100644
--- a/lib/profile/InstrProfiling.h
+++ b/lib/profile/InstrProfiling.h
@@ -10,6 +10,14 @@
 #ifndef PROFILE_INSTRPROFILING_H_
 #define PROFILE_INSTRPROFILING_H_
 
+#ifdef _MSC_VER
+# define LLVM_ALIGNAS(x) __declspec(align(x))
+#elif __GNUC__ && !__has_feature(cxx_alignas)
+# define LLVM_ALIGNAS(x) __attribute__((aligned(x)))
+#else
+# define LLVM_ALIGNAS(x) alignas(x)
+#endif
+
 #if defined(__FreeBSD__) && defined(__i386__)
 
 /* System headers define 'size_t' incorrectly on x64 FreeBSD (prior to
@@ -27,13 +35,31 @@ typedef uint32_t uintptr_t;
 
 #endif /* defined(__FreeBSD__) && defined(__i386__) */
 
+typedef enum ValueKind {
+  VK_IndirectCallTarget = 0,
+  VK_FIRST = VK_IndirectCallTarget,
+  VK_LAST = VK_IndirectCallTarget
+} __llvm_profile_value_kind;
+
+typedef struct __llvm_profile_value_data {
+  uint64_t TargetValue;
+  uint64_t NumTaken;
+} __llvm_profile_value_data;
 
-typedef struct __llvm_profile_data {
+typedef struct __llvm_profile_value_node {
+  __llvm_profile_value_data VData;
+  struct __llvm_profile_value_node *Next;
+} __llvm_profile_value_node;
+
+typedef struct LLVM_ALIGNAS(8) __llvm_profile_data {
   const uint32_t NameSize;
   const uint32_t NumCounters;
   const uint64_t FuncHash;
   const char *const NamePtr;
   uint64_t *const CounterPtr;
+  const uint8_t *FunctionPointer;
+  __llvm_profile_value_node **ValueCounters;
+  const uint16_t NumValueSites[VK_LAST + 1];
 } __llvm_profile_data;
 
 typedef struct __llvm_profile_header {
@@ -44,8 +70,16 @@ typedef struct __llvm_profile_header {
   uint64_t NamesSize;
   uint64_t CountersDelta;
   uint64_t NamesDelta;
+  uint64_t ValueKindLast;
+  uint64_t ValueDataSize;
+  uint64_t ValueDataDelta;
 } __llvm_profile_header;
 
+/*!
+ * \brief Get number of bytes necessary to pad the argument to eight
+ * byte boundary.
+ */
+uint8_t __llvm_profile_get_num_padding_bytes(uint64_t SizeInBytes);
 
 /*!
  * \brief Get required size for profile buffer.
@@ -68,6 +102,23 @@ uint64_t *__llvm_profile_begin_counters(void);
 uint64_t *__llvm_profile_end_counters(void);
 
 /*!
+ * \brief Counts the number of times a target value is seen.
+ *
+ * Records the target value for the CounterIndex if not seen before. Otherwise,
+ * increments the counter associated w/ the target value.
+ */
+void __llvm_profile_instrument_target(uint64_t TargetValue,
+  void *Data_, uint32_t CounterIndex);
+
+/*!
+ * \brief Prepares the value profiling data for output.
+ *
+ * Prepares a single __llvm_profile_value_data array out of the many
+ * __llvm_profile_value_node trees (one per instrumented function).
+ */
+uint64_t __llvm_profile_gather_value_data(uint8_t **DataArray);
+
+/*!
  * \brief Write instrumentation data to the current file.
  *
  * Writes to the file with the last name given to \a __llvm_profile_set_filename(),
diff --git a/lib/profile/InstrProfilingBuffer.c b/lib/profile/InstrProfilingBuffer.c
index 620c1755b..f64765a2c 100644
--- a/lib/profile/InstrProfilingBuffer.c
+++ b/lib/profile/InstrProfilingBuffer.c
@@ -35,7 +35,7 @@ uint64_t __llvm_profile_get_size_for_buffer_internal(
         const char *NamesEnd) {
   /* Match logic in __llvm_profile_write_buffer(). */
   const uint64_t NamesSize = PROFILE_RANGE_SIZE(Names) * sizeof(char);
-  const uint64_t Padding = sizeof(uint64_t) - NamesSize % sizeof(uint64_t);
+  const uint8_t Padding = __llvm_profile_get_num_padding_bytes(NamesSize);
   return sizeof(__llvm_profile_header) +
       PROFILE_RANGE_SIZE(Data) * sizeof(__llvm_profile_data) +
       PROFILE_RANGE_SIZE(Counters) * sizeof(uint64_t) +
@@ -72,7 +72,7 @@ int __llvm_profile_write_buffer_internal(
   const uint64_t DataSize = DataEnd - DataBegin;
   const uint64_t CountersSize = CountersEnd - CountersBegin;
   const uint64_t NamesSize = NamesEnd - NamesBegin;
-  const uint64_t Padding = sizeof(uint64_t) - NamesSize % sizeof(uint64_t);
+  const uint8_t Padding = __llvm_profile_get_num_padding_bytes(NamesSize);
 
   /* Enough zeroes for padding. */
   const char Zeroes[sizeof(uint64_t)] = {0};
@@ -90,6 +90,9 @@ int __llvm_profile_write_buffer_internal(
   Header.NamesSize = NamesSize;
   Header.CountersDelta = (uintptr_t)CountersBegin;
   Header.NamesDelta = (uintptr_t)NamesBegin;
+  Header.ValueKindLast = VK_LAST;
+  Header.ValueDataSize = 0;
+  Header.ValueDataDelta = (uintptr_t)NULL;
 
   /* Write the data. */
 #define UPDATE_memcpy(Data, Size) \
diff --git a/lib/profile/InstrProfilingFile.c b/lib/profile/InstrProfilingFile.c
index 318648e44..06df67d6b 100644
--- a/lib/profile/InstrProfilingFile.c
+++ b/lib/profile/InstrProfilingFile.c
@@ -24,12 +24,15 @@ static int writeFile(FILE *File) {
   const uint64_t *CountersEnd   = __llvm_profile_end_counters();
   const char *NamesBegin = __llvm_profile_begin_names();
   const char *NamesEnd   = __llvm_profile_end_names();
+  uint8_t *ValueDataBegin = NULL;
 
   /* Calculate size of sections. */
   const uint64_t DataSize = DataEnd - DataBegin;
   const uint64_t CountersSize = CountersEnd - CountersBegin;
   const uint64_t NamesSize = NamesEnd - NamesBegin;
-  const uint64_t Padding = sizeof(uint64_t) - NamesSize % sizeof(uint64_t);
+  const uint8_t Padding = __llvm_profile_get_num_padding_bytes(NamesSize);
+  const uint64_t ValueDataSize =
+      __llvm_profile_gather_value_data(&ValueDataBegin);
 
   /* Enough zeroes for padding. */
   const char Zeroes[sizeof(uint64_t)] = {0};
@@ -47,17 +50,22 @@ static int writeFile(FILE *File) {
   Header.NamesSize = NamesSize;
   Header.CountersDelta = (uintptr_t)CountersBegin;
   Header.NamesDelta = (uintptr_t)NamesBegin;
+  Header.ValueKindLast = VK_LAST;
+  Header.ValueDataSize = ValueDataSize;
+  Header.ValueDataDelta = (uintptr_t)ValueDataBegin;
 
   /* Write the data. */
 #define CHECK_fwrite(Data, Size, Length, File) \
   do { if (fwrite(Data, Size, Length, File) != Length) return -1; } while (0)
-  CHECK_fwrite(&Header,        sizeof(__llvm_profile_header), 1, File);
+  CHECK_fwrite(&Header,       sizeof(__llvm_profile_header), 1, File);
   CHECK_fwrite(DataBegin,     sizeof(__llvm_profile_data), DataSize, File);
   CHECK_fwrite(CountersBegin, sizeof(uint64_t), CountersSize, File);
   CHECK_fwrite(NamesBegin,    sizeof(char), NamesSize, File);
   CHECK_fwrite(Zeroes,        sizeof(char), Padding, File);
+  CHECK_fwrite(ValueDataBegin,
+      sizeof(__llvm_profile_value_data), ValueDataSize, File);
 #undef CHECK_fwrite
-
+  free(ValueDataBegin);
   return 0;
 }