[PGO] Value profile support for value ranges

[xur]

Summary

This patch adds profile run time support to profile a range of values.

It has two adjustable parameters: SmallVal and LargeVal size less than or equal to SmallVal will be precisely profiled. size greater than SmallVal but less than LargeVal will have one count size greater than or equal to LargeVale will have one count. These parameters are passed from compiler.

This interface is going to used in profiling the size of memory intrinsic calls.

[davidxl]

A general comment.

The range profiling should not be limited to just memory intrinsics. It should be designed to be a more general interval profiler. Interval profiler is also useful for other value profiling transformations such as mod operation for integer values (x%y). The value profiler can do interval profiling for division x/y and track resulting values in interval [0, 1].

In a more general form, an interval profiler API should specify the following things

1. counter index
2. interval start and end (inclusive) : [S, E]
3. optionally specify the start value of a large value range [SL, inf)

3 + (E-S+1) values will be tracked:
(-inf, S) one value
[S,E] one for each in the range
[E, SL) one value
[SL, inf) for one.

The client (instrumentor) decides the the interval boundaries depending on the value profile kind.

[davidxl]

In fact, I don't there is a need for compiler_rt change at all for the interval/range profiling. The compiler_rt API should be kept simple. In other words, interval profiling should already be 'lowered' into regular value profiling in the instrumentation lowering phase. The instrumentation lowering will general inline sequence that collapse ranges into single value depending on the value profile kind. Only the __llvm_profile_instrument_target low level interface is needed.

The only downside of this approach that we can not override the range definitions at runtime -- but I don't think that is worth the complexity introduced.

[xur]

changed the patch based on David's review comments:
(1) reuse __llvm_profile_instrument_target as much as possible and make the new function a wrapper.
(3) use parameter rather global variables.
(2) supported signed type.

changes in InstrProfData.inc is mostly to sync with the compiler.

[davidxl]

The raw profile format version needs to change too.

lib/profile/InstrProfData.inc

156

remove this line

158

change this line to

#ifdef VALUE_RANGE_PROF

lib/profile/InstrProfilingValue.c

223

Describe it more clearly to cover information such as: the target values are partitioned into multiple regions/ranges. There is one contiguous region which is precise -- every value in the range is tracked individually. A value outside the precise region will be collapsed into one value depending on the region it falls in.

228

There are three regions:

1. (-inf, StartVal) and (PreciseLast, LargeValue) belong to one region -- all values here should be mapped to one value
2. [PreciseStart, PreciseLast]
3. Large values: [LargeValue, +inf) maps to one value.

231

for range/interval profiling, it is simpler to make target value Int64 type. With this, we can get rid of SignedType parameter. LargeTargetValue is also optional. The default value of MIN_INT64 indicates it is not specified.

233

StartValue --> PreciseRangeStart

234

PreciseRangeLast

[xur]

Integrated David's review comments.

[xur]

It seems I have to fall back the latest change in InstrProfData.inc. We have to use #else clause "VALUE_PROF_FUNC_PARAM(uint32_t, CounterIndex, Type::getInt32Ty(Ctx))" because one of the version need to append INSTR_PROF_COMMA.

[xur]

drop the recent change in InstrProfData.inc

[vsk]

Could you add periods where appropriate in your patch description? It's a little hard to parse it as-is.

Also, this is missing a test. You can add one without the llvm changes, see e.g test/profile/instrprof-value-prof*.

Finally, what's the raw profile change that's needed?

lib/profile/InstrProfilingValue.c

244

Please clang-format this function body.

251

IIUC we get precise counts if TargetValue is in [PreciseRangeStart, PreciseRangeLast], or if LargeValue == INT64_MIN. If so, that doesn't seem quite right, because I thought you only wanted precise counts for in-range values.

[xur]

One reply to vsk's comment in inlined.

I'll add a test per vsk's suggestion. Patch description will also be updated when I upload the new patch.

lib/profile/InstrProfilingValue.c

251

I don't see a problem here: if LargeValue is INT64_MIN, we will go the second if in the else branch -- this collapse the out of range values.

[xur]

To vsk: if seems hard to add a test without the compiler part of change. We can add the calls to __llvm_profile_instrument_range(). But to check the result, we need llvm-profdata to dump the counters.

How about I added the test in projects/compiler-rt/test/profile after committing the compiler change?

[xur]

Integrated part of vsk's review comments.

Updated description:

This patch adds profile run time support to profile a range of values.

The target values are partitioned into multiple regions/ranges. There is one
contiguous region which is precise -- every value in the range is tracked
individually. A value outside the precise region will be collapsed into one
value depending on the region it falls in.

There are three regions:

1. (-inf, PreciseRangeStart) and (PreciseRangeLast, LargeRangeValue) belong to one region -- all values here should be mapped to one value of "PreciseRangeLast + 1".
2. [PreciseRangeStart, PreciseRangeLast]
3. Large values: [LargeValue, +inf) maps to one value of LargeValue.

The range for large values is optional. The default value of MIN_INT64 indicates it is not specified.

This interface is going to be used in profiling the size of memory intrinsic calls.

[vsk]

In D28964#661149, @xur wrote:

To vsk: if seems hard to add a test without the compiler part of change. We can add the calls to __llvm_profile_instrument_range(). But to check the result, we need llvm-profdata to dump the counters.

How about I added the test in projects/compiler-rt/test/profile after committing the compiler change?

Makes sense to me.

lib/profile/InstrProfilingValue.c

251

Ah, right, sorry about that

[davidxl]

lgtm

lib/profile/InstrProfData.inc

 #define INSTR_PROF_COMMA
 #else
 #define INSTR_PROF_DATA_DEFINED
 #define INSTR_PROF_COMMA ,
 #endif
 VALUE_PROF_FUNC_PARAM(uint64_t, TargetValue, Type::getInt64Ty(Ctx)) \
                       INSTR_PROF_COMMA
 VALUE_PROF_FUNC_PARAM(void *, Data, Type::getInt8PtrTy(Ctx)) INSTR_PROF_COMMA
+#ifndef VALUE_RANGE_PROF
 VALUE_PROF_FUNC_PARAM(uint32_t, CounterIndex, Type::getInt32Ty(Ctx))
+#else /* VALUE_RANGE_PROF */
+VALUE_PROF_FUNC_PARAM(uint32_t, CounterIndex, Type::getInt32Ty(Ctx)) \
+                      INSTR_PROF_COMMA
+VALUE_PROF_FUNC_PARAM(uint32_t, SignedType, Type::getInt32Ty(Ctx)) \
+                      INSTR_PROF_COMMA
+VALUE_PROF_FUNC_PARAM(uint64_t, StartValue, Type::getInt64Ty(Ctx)) \
+                      INSTR_PROF_COMMA
+VALUE_PROF_FUNC_PARAM(uint64_t, SmallTargetValue, Type::getInt64Ty(Ctx)) \
+                      INSTR_PROF_COMMA
+VALUE_PROF_FUNC_PARAM(uint64_t, LargeTargetValue, Type::getInt64Ty(Ctx))
+#endif /*VALUE_RANGE_PROF */
 #undef VALUE_PROF_FUNC_PARAM
 #undef INSTR_PROF_COMMA
 /* VALUE_PROF_FUNC_PARAM end */
 
 /* VALUE_PROF_KIND start */
 #ifndef VALUE_PROF_KIND
 #define VALUE_PROF_KIND(Enumerator, Value)
 #else
 #define INSTR_PROF_DATA_DEFINED
 #endif
 /* For indirect function call value profiling, the addresses of the target
  * functions are profiled by the instrumented code. The target addresses are
  * written in the raw profile data and converted to target function name's MD5
  * hash by the profile reader during deserialization.  Typically, this happens
  * when the the raw profile data is read during profile merging.
  *
  * For this remapping the ProfData is used.  ProfData contains both the function
  * name hash and the function address.
  */
 VALUE_PROF_KIND(IPVK_IndirectCallTarget, 0)
+/* For memory intrinsic functions size profiling. */
+VALUE_PROF_KIND(IPVK_MemOPSize, 1)
 /* These two kinds must be the last to be
  * declared. This is to make sure the string
  * array created with the template can be
  * indexed with the kind value.
  */
 VALUE_PROF_KIND(IPVK_First, IPVK_IndirectCallTarget)
-VALUE_PROF_KIND(IPVK_Last, IPVK_IndirectCallTarget)
+VALUE_PROF_KIND(IPVK_Last, IPVK_MemOPSize)
 
 #undef VALUE_PROF_KIND
 /* VALUE_PROF_KIND end */
 
 /* COVMAP_FUNC_RECORD start */
 /* Definition of member fields of the function record structure in coverage
  * map.
  */
#define INSTR_PROF_SECT_START(Sect) \
         INSTR_PROF_CONCAT(__start_,Sect)
 #define INSTR_PROF_SECT_STOP(Sect) \
         INSTR_PROF_CONCAT(__stop_,Sect)
 
 /* Value Profiling API linkage name.  */
 #define INSTR_PROF_VALUE_PROF_FUNC __llvm_profile_instrument_target
 #define INSTR_PROF_VALUE_PROF_FUNC_STR \
         INSTR_PROF_QUOTE(INSTR_PROF_VALUE_PROF_FUNC)
+#define INSTR_PROF_VALUE_RANGE_PROF_FUNC __llvm_profile_instrument_range
+#define INSTR_PROF_VALUE_RANGE_PROF_FUNC_STR \
+        INSTR_PROF_QUOTE(INSTR_PROF_VALUE_RANGE_PROF_FUNC)
 
 /* InstrProfile per-function control data alignment.  */
 #define INSTR_PROF_DATA_ALIGNMENT 8
 
 /* The data structure that represents a tracked value by the
  * value profiler.
  */
 typedef struct InstrProfValueData {

lib/profile/InstrProfilingValue.c

__llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
 
   if (!Success && !hasStaticCounters) {
     free(CurVNode);
     return;
   }
 }
 
 /*
+ * We divide the possible values of TargetValue into the following ranges:
+ *   Range                               Represent Value
+ * (-inf, StartVal):                     StartVal - 1;
+ * [StartValue, SmallTargetValue]        TargetValue
+ * (SmallTargetalue, LargeTargetValue)   SmallTargetValue + 1
+ * [LargeTargetValue, +inf)              LargetTargetValue
+ */
+COMPILER_RT_VISIBILITY void
+__llvm_profile_instrument_range(uint64_t TargetValue, void *Data,
+                                uint32_t CounterIndex, uint32_t SignedType,
+                                uint64_t StartValue,
+                                uint64_t SmallTargetValue,
+                                uint64_t LargeTargetValue) {
+
+  if (SignedType) {
+    if ((int64_t) TargetValue >= (int64_t) LargeTargetValue)
+      TargetValue = LargeTargetValue;
+    else if ((int64_t) TargetValue > (int64_t) SmallTargetValue)
+      TargetValue = SmallTargetValue + 1;
+    else if ((int64_t) TargetValue < (int64_t) StartValue)
+      TargetValue = StartValue - 1;
+  } else {
+    if (TargetValue >= LargeTargetValue)
+      TargetValue = LargeTargetValue;
+    else if (TargetValue > SmallTargetValue)
+      TargetValue = SmallTargetValue + 1;
+    else if (TargetValue < StartValue)
+      TargetValue = StartValue - 1;
+  }
+
+  __llvm_profile_instrument_target(TargetValue, Data, CounterIndex);
+}
+
+/*
  * A wrapper struct that represents value profile runtime data.
  * Like InstrProfRecord class which is used by profiling host tools,
  * ValueProfRuntimeRecord also implements the abstract intefaces defined in
  * ValueProfRecordClosure so that the runtime data can be serialized using
  * shared C implementation.
  */
 typedef struct ValueProfRuntimeRecord {
   const __llvm_profile_data *Data;