[profile] Add support for static counter allocation for value profiling (part-1)

[davidxl]

Summary

Current value profiler implementation relies on libc runtime for lazy allocation of profile counters. While this is flexible, it limits the usability greatly for apps running in restricted runtime environment.

With this change, VP will now have counters allocated statically by default. Dynamic allocation is still supported which is controlled by compile time option.

The implementation chooses allocate only one node per-site. Tested with instrumented clang (compiing a large C++ source) -- the total number of values collected at runtime is a still quite smaller than statically allocated # of counters .

[silvas]

This is very exciting. This will hopefully make VP feasible on PS4.

A couple small comments but this LGTM.

lib/Transforms/Instrumentation/InstrProfiling.cpp

40

Typo avverage.

42

This is a very interesting statistic.

443

Can you expand on the explanation here?

[davidxl]

lib/Transforms/Instrumentation/InstrProfiling.cpp

443

The small ratio we choose for #counters over #of sites is based on the observation of large apps with large number of value sites, in which majority of them either have no profile or small number of values. When the number of sites is small, we won't have this average effect. Ideally we should do this computation at link time -- but we will need to do this on a per-module basis. The value 10 can still be tuned -- for instance to make small programs like SPEC happy.

[davidxl]

Fixed typo.

[silvas]

lib/Transforms/Instrumentation/InstrProfiling.cpp

443

Thanks, that makes sense. Can you mention this in the comment?

[davidxl]

Adjusted and added comments for cases with very few value sites.

[davidxl]

Fix a bug that triggers debug assert (pointer type mismatch).

include/llvm/ProfileData/InstrProf.h

 
 /// Return the name of the data section containing per-function control
 /// data.
 inline StringRef getInstrProfDataSectionName(bool AddSegment) {
   return AddSegment ? "__DATA," INSTR_PROF_DATA_SECT_NAME_STR
                     : INSTR_PROF_DATA_SECT_NAME_STR;
 }
 
+/// Return the name of data section containing pointers to value profile
+/// counters/nodes.
+inline StringRef getInstrProfValuesSectionName(bool AddSegment) {
+  return AddSegment ? "__DATA," INSTR_PROF_VALS_SECT_NAME_STR
+                    : INSTR_PROF_VALS_SECT_NAME_STR;
+}
+
+/// Return the name of data section containing nodes holdling value
+/// profiling data.
+inline StringRef getInstrProfVNodesSectionName(bool AddSegment) {
+  return AddSegment ? "__DATA," INSTR_PROF_VNODES_SECT_NAME_STR
+                    : INSTR_PROF_VNODES_SECT_NAME_STR;
+}
+
 /// Return the name profile runtime entry point to do value profiling
 /// for a given site.
 inline StringRef getInstrProfValueProfFuncName() {
   return INSTR_PROF_VALUE_PROF_FUNC_STR;
 }
 
 /// Return the name of the section containing function coverage mapping
 /// data.
 inline StringRef getInstrProfCoverageSectionName(bool AddSegment) {
   return AddSegment ? "__DATA," INSTR_PROF_COVMAP_SECT_NAME_STR
                     : INSTR_PROF_COVMAP_SECT_NAME_STR;
 }
 
 /// Return the name prefix of variables containing instrumented function names.
 inline StringRef getInstrProfNameVarPrefix() { return "__profn_"; }
 
 /// Return the name prefix of variables containing per-function control data.
 inline StringRef getInstrProfDataVarPrefix() { return "__profd_"; }
 
 /// Return the name prefix of profile counter variables.
 inline StringRef getInstrProfCountersVarPrefix() { return "__profc_"; }
 
+/// Return the name prefix of value profile variables.
+inline StringRef getInstrProfValuesVarPrefix() { return "__profvp_"; }
+
+/// Return the name of value profile node array variables:
+inline StringRef getInstrProfVNodesVarName() { return "__llvm_prf_vnodes"; }
+
 /// Return the name prefix of the COMDAT group for instrumentation variables
 /// associated with a COMDAT function.
 inline StringRef getInstrProfComdatPrefix() { return "__profv_"; }
 
 /// Return the name of the variable holding the strings (possibly compressed)
 /// of all function's PGO names.
 inline StringRef getInstrProfNamesVarName() {
   return "__llvm_prf_nm";

include/llvm/ProfileData/InstrProfData.inc

INSTR_PROF_DATA(const IntPtrT, llvm::Type::getInt64PtrTy(Ctx), CounterPtr, \
                 llvm::Type::getInt64PtrTy(Ctx)))
 /* This is used to map function pointers for the indirect call targets to
  * function name hashes during the conversion from raw to merged profile
  * data.
  */
 INSTR_PROF_DATA(const IntPtrT, llvm::Type::getInt8PtrTy(Ctx), FunctionPointer, \
                 FunctionAddr)
 INSTR_PROF_DATA(IntPtrT, llvm::Type::getInt8PtrTy(Ctx), Values, \
-                ConstantPointerNull::get(Int8PtrTy))
+                ValuesPtrExpr)
 INSTR_PROF_DATA(const uint32_t, llvm::Type::getInt32Ty(Ctx), NumCounters, \
                 ConstantInt::get(llvm::Type::getInt32Ty(Ctx), NumCounters))
 INSTR_PROF_DATA(const uint16_t, Int16ArrayTy, NumValueSites[IPVK_Last+1], \
                 ConstantArray::get(Int16ArrayTy, Int16ArrayVals))
 #undef INSTR_PROF_DATA
 /* INSTR_PROF_DATA end. */
 
 

 #define GET_VERSION(V) ((V) & ~VARIANT_MASKS_ALL)
 #define VARIANT_MASK_IR_PROF (0x1ULL << 56)
 #define IR_LEVEL_PROF_VERSION_VAR __llvm_profile_raw_version
 
 /* Runtime section names and name strings.  */
 #define INSTR_PROF_DATA_SECT_NAME __llvm_prf_data
 #define INSTR_PROF_NAME_SECT_NAME __llvm_prf_names
 #define INSTR_PROF_CNTS_SECT_NAME __llvm_prf_cnts
+/* Array of pointers. Each pointer points to a list
+ * of value nodes associated with one value site.
+ */
+#define INSTR_PROF_VALS_SECT_NAME __llvm_prf_values
+/* Value profile nodes section. */
+#define INSTR_PROF_VNODES_SECT_NAME __llvm_prf_vnodes
 #define INSTR_PROF_COVMAP_SECT_NAME __llvm_covmap
 
 #define INSTR_PROF_DATA_SECT_NAME_STR                                          \
   INSTR_PROF_QUOTE(INSTR_PROF_DATA_SECT_NAME)
 #define INSTR_PROF_NAME_SECT_NAME_STR                                          \
   INSTR_PROF_QUOTE(INSTR_PROF_NAME_SECT_NAME)
 #define INSTR_PROF_CNTS_SECT_NAME_STR                                          \
   INSTR_PROF_QUOTE(INSTR_PROF_CNTS_SECT_NAME)
 #define INSTR_PROF_COVMAP_SECT_NAME_STR                                        \
   INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_SECT_NAME)
+#define INSTR_PROF_VALS_SECT_NAME_STR                                          \
+  INSTR_PROF_QUOTE(INSTR_PROF_VALS_SECT_NAME)
+#define INSTR_PROF_VNODES_SECT_NAME_STR                                        \
+  INSTR_PROF_QUOTE(INSTR_PROF_VNODES_SECT_NAME)
 
 /* Macros to define start/stop section symbol for a given
  * section on Linux. For instance
  * INSTR_PROF_SECT_START(INSTR_PROF_DATA_SECT_NAME) will
  * expand to __start___llvm_prof_data
  */
 #define INSTR_PROF_SECT_START(Sect) \
         INSTR_PROF_CONCAT(__start_,Sect)

include/llvm/Transforms/InstrProfiling.h

private:
   ///
   /// If the counter array doesn't yet exist, the profile data variables
   /// referring to them will also be created.
   GlobalVariable *getOrCreateRegionCounters(InstrProfIncrementInst *Inc);
 
   /// Emit the section with compressed function names.
   void emitNameData();
 
+  /// Emit value nodes section for value profiling.
+  void emitVNodes();
+
   /// Emit runtime registration functions for each profile data variable.
   void emitRegistration();
 
   /// Emit the necessary plumbing to pull in the runtime initialization.
   void emitRuntimeHook();
 
   /// Add uses of our data variables and runtime hook.
   void emitUses();
 
   /// Create a static initializer for our data, on platforms that need it,
   /// and for any profile output file that was specified.
   void emitInitialization();
 };
 
 } // End llvm namespace
 #endif

lib/Transforms/Instrumentation/InstrProfiling.cpp

 #define DEBUG_TYPE "instrprof"
 
 namespace {
 
 cl::opt<bool> DoNameCompression("enable-name-compression",
                                 cl::desc("Enable name string compression"),
                                 cl::init(true));
 
+cl::opt<bool> ValueProfileStaticAlloc(
+    "vp-static-alloc",
+    cl::desc("Do static counter allocation for value profiler"),
+    cl::init(true));
+cl::opt<double> NumCountersPerValueSite(
+    "vp-counters-per-site",
+    cl::desc("The average number of profile counters allocated "
+             "per value profiling site."),
+    // This is set to a very small value because in real programs, only
+    // a very small percentage of value sites have non-zero targets, e.g, 1/30.
+    // For those sites with non-zero profile, the average number of targets
+    // is usually smaller than 2.
+    cl::init(1.0));
+
 class InstrProfilingLegacyPass : public ModulePass {
   InstrProfiling InstrProf;
 
 public:
   static char ID;
   InstrProfilingLegacyPass() : ModulePass(ID), InstrProf() {}
   InstrProfilingLegacyPass(const InstrProfOptions &Options)
       : ModulePass(ID), InstrProf(Options) {}
if (GlobalVariable *CoverageNamesVar =
           M.getNamedGlobal(getCoverageUnusedNamesVarName())) {
     lowerCoverageData(CoverageNamesVar);
     MadeChange = true;
   }
 
   if (!MadeChange)
     return false;
 
+  emitVNodes();
   emitNameData();
   emitRegistration();
   emitRuntimeHook();
   emitUses();
   emitInitialization();
   return true;
 }
 
static inline Comdat *getOrCreateProfileComdat(Module &M, Function &F,
   // a section is associated to must precede the associating section. For this
   // reason, we must choose the counter var's name as the name of the comdat.
   StringRef ComdatPrefix = (Triple(M.getTargetTriple()).isOSBinFormatCOFF()
                                 ? getInstrProfCountersVarPrefix()
                                 : getInstrProfComdatPrefix());
   return M.getOrInsertComdat(StringRef(getVarName(Inc, ComdatPrefix)));
 }
 
+static bool needsRuntimeRegistrationOfSectionRange(const Module &M) {
+  // Don't do this for Darwin.  compiler-rt uses linker magic.
+  if (Triple(M.getTargetTriple()).isOSDarwin())
+    return false;
+
+  // Use linker script magic to get data/cnts/name start/end.
+  if (Triple(M.getTargetTriple()).isOSLinux() ||
+      Triple(M.getTargetTriple()).isOSFreeBSD() ||
+      Triple(M.getTargetTriple()).isPS4CPU())
+    return false;
+
+  return true;
+}
+
 GlobalVariable *
 InstrProfiling::getOrCreateRegionCounters(InstrProfIncrementInst *Inc) {
   GlobalVariable *NamePtr = Inc->getName();
   auto It = ProfileDataMap.find(NamePtr);
   PerFunctionProfileData PD;
   if (It != ProfileDataMap.end()) {
     if (It->second.RegionCounters)
       return It->second.RegionCounters;
auto *CounterPtr =
       new GlobalVariable(*M, CounterTy, false, NamePtr->getLinkage(),
                          Constant::getNullValue(CounterTy),
                          getVarName(Inc, getInstrProfCountersVarPrefix()));
   CounterPtr->setVisibility(NamePtr->getVisibility());
   CounterPtr->setSection(getCountersSection());
   CounterPtr->setAlignment(8);
   CounterPtr->setComdat(ProfileVarsComdat);
 
-  // Create data variable.
   auto *Int8PtrTy = Type::getInt8PtrTy(Ctx);
+  // Allocate statically the array of pointers to value profile nodes for
+  // the current function.
+  Constant *ValuesPtrExpr = ConstantPointerNull::get(Int8PtrTy);
+  if (ValueProfileStaticAlloc && !needsRuntimeRegistrationOfSectionRange(*M)) {
+
+    uint64_t NS = 0;
+    for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
+      NS += PD.NumValueSites[Kind];
+    if (NS) {
+      ArrayType *ValuesTy = ArrayType::get(Type::getInt64Ty(Ctx), NS);
+
+      auto *ValuesVar =
+          new GlobalVariable(*M, ValuesTy, false, NamePtr->getLinkage(),
+                             Constant::getNullValue(ValuesTy),
+                             getVarName(Inc, getInstrProfValuesVarPrefix()));
+      ValuesVar->setVisibility(NamePtr->getVisibility());
+      ValuesVar->setSection(getInstrProfValuesSectionName(isMachO()));
+      ValuesVar->setAlignment(8);
+      ValuesVar->setComdat(ProfileVarsComdat);
+      ValuesPtrExpr =
+          ConstantExpr::getBitCast(ValuesVar, llvm::Type::getInt8PtrTy(Ctx));
+    }
+  }
+
+  // Create data variable.
   auto *Int16Ty = Type::getInt16Ty(Ctx);
-  auto *Int16ArrayTy = ArrayType::get(Int16Ty, IPVK_Last+1);
+  auto *Int16ArrayTy = ArrayType::get(Int16Ty, IPVK_Last + 1);
   Type *DataTypes[] = {
     #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) LLVMType,
     #include "llvm/ProfileData/InstrProfData.inc"
   };
   auto *DataTy = StructType::get(Ctx, makeArrayRef(DataTypes));
 
   Constant *FunctionAddr = shouldRecordFunctionAddr(Fn) ?
                            ConstantExpr::getBitCast(Fn, Int8PtrTy) :
InstrProfiling::getOrCreateRegionCounters(InstrProfIncrementInst *Inc) {
   // it can be removed later by the compiler.
   NamePtr->setLinkage(GlobalValue::PrivateLinkage);
   // Collect the referenced names to be used by emitNameData.
   ReferencedNames.push_back(NamePtr);
 
   return CounterPtr;
 }
 
-static bool needsRuntimeRegistrationOfSectionRange(const Module &M) {
-  // Don't do this for Darwin.  compiler-rt uses linker magic.
-  if (Triple(M.getTargetTriple()).isOSDarwin())
-    return false;
+void InstrProfiling::emitVNodes() {
+  if (!ValueProfileStaticAlloc)
+    return;
 
-  // Use linker script magic to get data/cnts/name start/end.
-  if (Triple(M.getTargetTriple()).isOSLinux() ||
-      Triple(M.getTargetTriple()).isOSFreeBSD() ||
-      Triple(M.getTargetTriple()).isPS4CPU())
-    return false;
+  // For now only support this on platforms that do
+  // not require runtime registration to discover
+  // named section start/end.
+  if (needsRuntimeRegistrationOfSectionRange(*M))
+    return;
 
-  return true;
+  size_t TotalNS = 0;
+  for (auto &PD : ProfileDataMap) {
+    for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
+      TotalNS += PD.second.NumValueSites[Kind];
+  }
+
+  if (!TotalNS)
+    return;
+
+  uint64_t NumCounters = TotalNS * NumCountersPerValueSite;
+  // Heuristic for small programs with very few total value sites.
+  // The default value of vp-counters-per-site is chosen based on
+  // the observation that large apps usually have a low percentage
+  // of value sites that actually have any profile data, and thus
+  // the average number of counters per site is low. For small
+  // apps with very few sites, this may not be true. Bump up the
+  // number of counters in this case.
+  if (NumCounters < 10)
+    NumCounters *= 2;
+
+  auto &Ctx = M->getContext();
+  Type *VNodeTypes[] = {
+#define INSTR_PROF_VALUE_NODE(Type, LLVMType, Name, Init) LLVMType,
+#include "llvm/ProfileData/InstrProfData.inc"
+  };
+  auto *VNodeTy = StructType::get(Ctx, makeArrayRef(VNodeTypes));
+
+  ArrayType *VNodesTy = ArrayType::get(VNodeTy, NumCounters);
+  auto *VNodesVar = new GlobalVariable(
+      *M, VNodesTy, false, llvm::GlobalValue::PrivateLinkage,
+      Constant::getNullValue(VNodesTy), getInstrProfVNodesVarName());
+  VNodesVar->setSection(getInstrProfVNodesSectionName(isMachO()));
+  UsedVars.push_back(VNodesVar);
 }
 
 void InstrProfiling::emitNameData() {
   std::string UncompressedData;
 
   if (ReferencedNames.empty())
     return;
 

test/Instrumentation/InstrProfiling/icall.ll

+;; Check that static counters are allocated for value profiler
+
+; RUN: opt < %s -mtriple=x86_64-apple-macosx10.10.0 -vp-static-alloc=true -instrprof -S | FileCheck %s --check-prefix=STATIC
+; RUN: opt < %s -mtriple=x86_64-unknown-linux -instrprof -vp-static-alloc=true -S | FileCheck %s --check-prefix=STATIC
+; RUN: opt < %s -mtriple=x86_64-apple-macosx10.10.0 -vp-static-alloc=false -instrprof -S | FileCheck %s --check-prefix=DYN
+; RUN: opt < %s -mtriple=x86_64-unknown-linux -instrprof -vp-static-alloc=false -S | FileCheck %s --check-prefix=DYN
+
+
+$__llvm_profile_raw_version = comdat any
+
+@__llvm_profile_raw_version = constant i64 72057594037927940, comdat
+@__profn_foo = private constant [3 x i8] c"foo"
+
+define i32 @foo(i32 ()* ) {
+  call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 12884901887, i32 1, i32 0)
+  %2 = ptrtoint i32 ()* %0 to i64
+  call void @llvm.instrprof.value.profile(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 12884901887, i64 %2, i32 0, i32 0)
+  %3 = tail call i32 %0()
+  ret i32 %3
+}
+
+; Function Attrs: nounwind
+declare void @llvm.instrprof.increment(i8*, i64, i32, i32) #0
+
+; Function Attrs: nounwind
+declare void @llvm.instrprof.value.profile(i8*, i64, i64, i32, i32) #0
+
+attributes #0 = { nounwind }
+
+; STATIC: @__profvp_foo
+; STATIC: @__llvm_prf_vnodes
+
+; DYN-NOT: @__profvp_foo
+; DYN-NOT: @__llvm_prf_vnodes