1 files changed, 45 insertions, 1 deletions

diff --git a/compiler-rt/lib/profile/InstrProfilingValue.c b/compiler-rt/lib/profile/InstrProfilingValue.c
index f51e6729204..856c8cf5bca 100644
--- a/compiler-rt/lib/profile/InstrProfilingValue.c
+++ b/compiler-rt/lib/profile/InstrProfilingValue.c
@@ -36,6 +36,10 @@ COMPILER_RT_VISIBILITY void lprofSetupValueProfiler() {
     VPMaxNumValsPerSite = INSTR_PROF_MAX_NUM_VAL_PER_SITE;
 }
 
+COMPILER_RT_VISIBILITY void lprofSetMaxValsPerSite(uint32_t MaxVals) {
+  VPMaxNumValsPerSite = MaxVals;
+}
+
 /* This method is only used in value profiler mock testing.  */
 COMPILER_RT_VISIBILITY void
 __llvm_profile_set_num_value_sites(__llvm_profile_data *Data,
@@ -93,7 +97,9 @@ __llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
 
   ValueProfNode **ValueCounters = (ValueProfNode **)PData->Values;
   ValueProfNode *PrevVNode = NULL;
+  ValueProfNode *MinCountVNode = NULL;
   ValueProfNode *CurrentVNode = ValueCounters[CounterIndex];
+  uint64_t MinCount = UINT64_MAX;
 
   uint8_t VDataCount = 0;
   while (CurrentVNode) {
@@ -101,13 +107,51 @@ __llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
       CurrentVNode->Count++;
       return;
     }
+    if (CurrentVNode->Count < MinCount) {
+      MinCount = CurrentVNode->Count;
+      MinCountVNode = CurrentVNode;
+    }
     PrevVNode = CurrentVNode;
     CurrentVNode = CurrentVNode->Next;
     ++VDataCount;
   }
 
-  if (VDataCount >= VPMaxNumValsPerSite)
+  if (VDataCount >= VPMaxNumValsPerSite) {
+    /* Bump down the min count node's count. If it reaches 0,
+     * evict it. This eviction/replacement policy makes hot
+     * targets more sticky while cold targets less so. In other
+     * words, it makes it less likely for the hot targets to be
+     * prematurally evicted during warmup/establishment period,
+     * when their counts are still low. In a special case when
+     * the number of values tracked is reduced to only one, this
+     * policy will guarantee that the dominating target with >50%
+     * total count will survive in the end. Note that this scheme
+     * allows the runtime to track the min count node in an adaptive
+     * manner. It can correct previous mistakes and eventually
+     * lock on a cold target that is alread in stable state.
+     *
+     * In very rare cases,  this replacement scheme may still lead
+     * to target loss. For instance, out of \c N value slots, \c N-1
+     * slots are occupied by luke warm targets during the warmup
+     * period and the remaining one slot is competed by two or more
+     * very hot targets. If those hot targets occur in an interleaved
+     * way, none of them will survive (gain enough weight to throw out
+     * other established entries) due to the ping-pong effect.
+     * To handle this situation, user can choose to increase the max
+     * number of tracked values per value site. Alternatively, a more
+     * expensive eviction mechanism can be implemented. It requires
+     * the runtime to track the total number of evictions per-site.
+     * When the total number of evictions reaches certain threshold,
+     * the runtime can wipe out more than one lowest count entries
+     * to give space for hot targets.
+     */
+    if (!(--MinCountVNode->Count)) {
+      CurrentVNode = MinCountVNode;
+      CurrentVNode->Value = TargetValue;
+      CurrentVNode->Count++;
+    }
     return;
+  }
 
   CurrentVNode = (ValueProfNode *)calloc(1, sizeof(ValueProfNode));
   if (!CurrentVNode)