llvm-profdata: Indirect infrequently used fields to reduce memory usage

[dblaikie]

Summary

Examining a large profile example, it seems relatively few records have
non-empty IndirectCall and MemOP data, so indirecting these through a
unique_ptr (non-null only when they are non-empty) Reduces memory usage
on this particular example from 14GB to 10GB according to valgrind's
massif.

I suspect it'd still be worth moving InstrProfWriter to its own data
structure that had Counts and the indirected IndirectCall+MemOP, and did
not include the Name, Hash, or Error fields. This would reduce the size
of this dominant data structure by half of this new, lower amount.
(Name(2), Hash(1), Error(1) ~= Counts(vector, 3), ValueProfData
(unique_ptr, 1))

[dblaikie]

Open questions:

Is this relatively low incidence of IndirectCall and MemOP collections representative, or is it likely to be more common in the future/in other use cases? (I haven't really looked at the code/what these mean in any great detail at all)

The copyability of InstrProfRecord might be able to be avoided with more work - there were certainly a bunch of cases where they didn't need to be copied that I found before I hit a more difficult one that seemed like more work than was worth it for the prototype of this change at least, but happy to go back to that if it seems worthwhile.

If InstrProfWriter's going to need to move away from InstrProfRecord anyway (to avoid the Name/Hash/Error values) this change may be a dead end not worth committing (since it'd change the data structure, only to not end up using the data structure in this codepath anyway).

[davidxl]

Yes, in general, the profile data is very sparse for large applications. Only a small percentage of modules have non-zero profile counts. Unlike edge/block profile which is statically allocated, the value profile data is created on-demand, this makes it possible to take advantage the sparsity as your patch does.

Regarding the followup change, here is my suggestion:

1. refactor InstrProfRecord into two parts, one part is the identification related including name, hash, etc, and the second part includes only counters -- InstrProfRecord becomes a wrapper class.
2. InstrProfWriter can use the counter record and maintains its own mapping.

include/llvm/ProfileData/InstrProf.h

717–718

Can we change the interface to return ArrayRef so that

1. we don't need empty vector
2. no need to duplicate the const/non-const version of the method?

[dblaikie]

Move to 'getOrCreateValueSitesForKind' for accessing the mutable std::vector reference.

[davidxl]

include/llvm/ProfileData/InstrProf.h

698

Is the const_cast here needed? Non const pointer can be used with const method right?

lib/ProfileData/InstrProf.cpp

510–511

This one should use the read-only version of the API.

537–538

Should use the read-only version.

[dblaikie]

Address review comments - using get instead of getOrCreate in a couple of places.

[dblaikie]

Range-for-ify a loop.

[dblaikie]

Remove unneeded bounds checking.

include/llvm/ProfileData/InstrProf.h

698

Yep - otherwise this function would infinitely recurse - calling back into this non-const function.

Ideally we'd have an "implicit_cast<T>" function template that would make it more obvious this was only adding const, and not a dangerous thing like const_cast that can take away const.

lib/ProfileData/InstrProf.cpp

510–511

Ah, well, it does need to use the non-const, but not the 'creating' kind. 'merge' takes the InstrProfRecord by non-const ref to call sort on it, it seems, just in case it's not already sorted.

537–538

Right right - like the other one, it doesn't need the 'orCreate' part, but it does need the non-const (MutableArrayRef) to scale the elements.

[davidxl]

lgtm

lib/ProfileData/InstrProf.cpp

510–511

Ok. can you put a comment there (re. using the non-const version)?

include/llvm/ProfileData/InstrProf.h

struct InstrProfRecord {
   StringRef Name;
   uint64_t Hash;
   std::vector<uint64_t> Counts;
   SoftInstrProfErrors SIPE;
 
   InstrProfRecord() = default;
   InstrProfRecord(StringRef Name, uint64_t Hash, std::vector<uint64_t> Counts)
       : Name(Name), Hash(Hash), Counts(std::move(Counts)) {}
+  InstrProfRecord(InstrProfRecord &&) = default;
+  InstrProfRecord(const InstrProfRecord &RHS)
+      : Name(RHS.Name), Hash(RHS.Hash), Counts(RHS.Counts), SIPE(RHS.SIPE),
+        ValueData(RHS.ValueData
+                      ? llvm::make_unique<ValueProfData>(*RHS.ValueData)
+                      : nullptr) {}
+  InstrProfRecord &operator=(InstrProfRecord &&) = default;
+  InstrProfRecord &operator=(const InstrProfRecord &RHS) {
+    Name = RHS.Name;
+    Hash = RHS.Hash;
+    Counts = RHS.Counts;
+    SIPE = RHS.SIPE;
+    if (!RHS.ValueData) {
+      ValueData = nullptr;
+      return *this;
+    }
+    if (!ValueData)
+      ValueData = llvm::make_unique<ValueProfData>(*RHS.ValueData);
+    else
+      *ValueData = *RHS.ValueData;
+    return *this;
+  }
 
   using ValueMapType = std::vector<std::pair<uint64_t, uint64_t>>;
 
   /// Return the number of value profile kinds with non-zero number
   /// of profile sites.
   inline uint32_t getNumValueKinds() const;
 
   /// Return the number of instrumented sites for ValueKind.
struct InstrProfRecord {
   void merge(InstrProfRecord &Other, uint64_t Weight = 1);
 
   /// Scale up profile counts (including value profile data) by
   /// \p Weight.
   void scale(uint64_t Weight);
 
   /// Sort value profile data (per site) by count.
   void sortValueData() {
-    for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
-      std::vector<InstrProfValueSiteRecord> &SiteRecords =
-          getValueSitesForKind(Kind);
-      for (auto &SR : SiteRecords)
+    for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
+      for (auto &SR : getValueSitesForKind(Kind))
         SR.sortByCount();
-    }
-  }
 
   /// Clear value data entries and edge counters.
   void Clear() {
     Counts.clear();
     clearValueData();
   }
 
   /// Clear value data entries
-  void clearValueData() {
-    for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
-      getValueSitesForKind(Kind).clear();
-  }
+  void clearValueData() { ValueData = nullptr; }
 
   /// Get the error contained within the record's soft error counter.
   Error takeError() { return SIPE.takeError(); }
 
 private:
+  struct ValueProfData {
     std::vector<InstrProfValueSiteRecord> IndirectCallSites;
     std::vector<InstrProfValueSiteRecord> MemOPSizes;
+  };
+  std::unique_ptr<ValueProfData> ValueData;
 
-  const std::vector<InstrProfValueSiteRecord> &
+  MutableArrayRef<InstrProfValueSiteRecord>
+  getValueSitesForKind(uint32_t ValueKind) {
+    auto AR = const_cast<const InstrProfRecord *>(this)->getValueSitesForKind(
+        ValueKind);
+    return makeMutableArrayRef(
+        const_cast<InstrProfValueSiteRecord *>(AR.data()), AR.size());
+  }
+  ArrayRef<InstrProfValueSiteRecord>
   getValueSitesForKind(uint32_t ValueKind) const {
+    if (!ValueData)
+      return None;
     switch (ValueKind) {
     case IPVK_IndirectCallTarget:
-      return IndirectCallSites;
+      return ValueData->IndirectCallSites;
     case IPVK_MemOPSize:
-      return MemOPSizes;
+      return ValueData->MemOPSizes;
     default:
       llvm_unreachable("Unknown value kind!");
     }
-    return IndirectCallSites;
   }
 
   std::vector<InstrProfValueSiteRecord> &
-  getValueSitesForKind(uint32_t ValueKind) {
-    return const_cast<std::vector<InstrProfValueSiteRecord> &>(
-        const_cast<const InstrProfRecord *>(this)
-            ->getValueSitesForKind(ValueKind));
+  getOrCreateValueSitesForKind(uint32_t ValueKind) {
+    if (!ValueData)
+      ValueData = llvm::make_unique<ValueProfData>();
+    switch (ValueKind) {
+    case IPVK_IndirectCallTarget:
+      return ValueData->IndirectCallSites;
+    case IPVK_MemOPSize:
+      return ValueData->MemOPSizes;
+    default:
+      llvm_unreachable("Unknown value kind!");
+    }
   }
 
   // Map indirect call target name hash to name string.
   uint64_t remapValue(uint64_t Value, uint32_t ValueKind,
                       ValueMapType *HashKeys);
 
   // Merge Value Profile data from Src record to this record for ValueKind.
   // Scale merged value counts by \p Weight.
for (auto V : getValueSitesForKind(ValueKind)[Site].ValueData) {
     Dest[I].Count = V.Count;
     TotalCount = SaturatingAdd(TotalCount, V.Count);
     I++;
   }
   return TotalCount;
 }
 
 void InstrProfRecord::reserveSites(uint32_t ValueKind, uint32_t NumValueSites) {
-  std::vector<InstrProfValueSiteRecord> &ValueSites =
-      getValueSitesForKind(ValueKind);
-  ValueSites.reserve(NumValueSites);
+  if (!NumValueSites)
+    return;
+  getOrCreateValueSitesForKind(ValueKind).reserve(NumValueSites);
 }
 
 inline support::endianness getHostEndianness() {
   return sys::IsLittleEndianHost ? support::little : support::big;
 }
 
 // Include definitions for value profile data
 #define INSTR_PROF_VALUE_PROF_DATA

lib/ProfileData/InstrProf.cpp

void InstrProfRecord::mergeValueProfData(uint32_t ValueKind,
                                          InstrProfRecord &Src,
                                          uint64_t Weight) {
   uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
   uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
   if (ThisNumValueSites != OtherNumValueSites) {
     SIPE.addError(instrprof_error::value_site_count_mismatch);
     return;
   }
+  if (!ThisNumValueSites)
+    return;
   std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
-      getValueSitesForKind(ValueKind);
-  std::vector<InstrProfValueSiteRecord> &OtherSiteRecords =
+      getOrCreateValueSitesForKind(ValueKind);
+  MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =
       Src.getValueSitesForKind(ValueKind);
   for (uint32_t I = 0; I < ThisNumValueSites; I++)
     ThisSiteRecords[I].merge(SIPE, OtherSiteRecords[I], Weight);
 }
 
 void InstrProfRecord::merge(InstrProfRecord &Other, uint64_t Weight) {
   // If the number of counters doesn't match we either have bad data
   // or a hash collision.
for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
     if (Overflowed)
       SIPE.addError(instrprof_error::counter_overflow);
   }
 
   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
     mergeValueProfData(Kind, Other, Weight);
 }
 
 void InstrProfRecord::scaleValueProfData(uint32_t ValueKind, uint64_t Weight) {
-  uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
-  std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
-      getValueSitesForKind(ValueKind);
-  for (uint32_t I = 0; I < ThisNumValueSites; I++)
-    ThisSiteRecords[I].scale(SIPE, Weight);
+  for (auto &R : getValueSitesForKind(ValueKind))
+    R.scale(SIPE, Weight);
 }
 
 void InstrProfRecord::scale(uint64_t Weight) {
   for (auto &Count : this->Counts) {
     bool Overflowed;
     Count = SaturatingMultiply(Count, Weight, &Overflowed);
     if (Overflowed)
       SIPE.addError(instrprof_error::counter_overflow);

 
 void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site,
                                    InstrProfValueData *VData, uint32_t N,
                                    ValueMapType *ValueMap) {
   for (uint32_t I = 0; I < N; I++) {
     VData[I].Value = remapValue(VData[I].Value, ValueKind, ValueMap);
   }
   std::vector<InstrProfValueSiteRecord> &ValueSites =
-      getValueSitesForKind(ValueKind);
+      getOrCreateValueSitesForKind(ValueKind);
   if (N == 0)
     ValueSites.emplace_back();
   else
     ValueSites.emplace_back(VData, VData + N);
 }
 
 #define INSTR_PROF_COMMON_API_IMPL
 #include "llvm/ProfileData/InstrProfData.inc"