[llvm-profdata] Change instr prof counter overflow to saturate rather than discard

[slingn]

Summary

This changes overflow handling during instrumentation profile merge. Rathar than throwing away records that would result in counter overflow, merged counts are instead clamped to the maximum representable value. A warning about counter overflow is still surfaced to the user as before.

[silvas]

include/llvm/ProfileData/InstrProf.h

421 ↗

(On Diff #40841)

Is this the right check? Seems like it would incorrectly fire when adding Counts[I] == "CounterMax - 1" and Other.Counts[I] == "1" since we are overwriting Counts[I]
The cleanest thing might be to add an optional argument bool *ResultOverflowed = nullptr to SaturatingAdd.

[davidxl]

include/llvm/ProfileData/InstrProf.h

421 ↗

(On Diff #40841)

Or perhaps just

NewCount = SaturatingAdd(....);
if (NewCount - Counts[I] != Other.Counts[I)

Result = ...

Counts[I] = NewCount;

Quoted Text

[silvas]

include/llvm/ProfileData/InstrProf.h

421 ↗

(On Diff #40841)

I like that!

[slingn]

Updated for davidxl and silvas comments.

[davidxl]

lib/ProfileData/InstrProfWriter.cpp

118 ↗

(On Diff #40934)

This line does not look right. Is it needed?

[slingn]

Updated for davidxl's comment.

include/llvm/ProfileData/InstrProf.h

421 ↗

(On Diff #40934)

The inline check for SaturatingAdd() overflow works well here, but thinking about the final weighted profile change - we need a way to check for SaturatingMultiply() overflow at multiple points in the code.

I'll follow up this change with Sean's suggestion of adding a third optional argument to SaturatingAdd()/SaturatingMultiply() so the overflow check code can be encapsulated there.

lib/ProfileData/InstrProfWriter.cpp

118 ↗

(On Diff #40934)

Good point. Not needed.

[slingn]

Updated to use new version of SaturatingAdd() that sets if result overflow.

[davidxl]

include/llvm/ProfileData/InstrProf.h

428 ↗

(On Diff #40978)

Should this be Result != success?

[slingn]

Updated for davidxl's comments.

include/llvm/ProfileData/InstrProf.h

428 ↗

(On Diff #40978)

The idea here was to give the first error to occur priority. But really the ordering of multiple errors during merge isn't critical - or even obviously better either way. So the simpler check wins.

[davidxl]

include/llvm/ProfileData/InstrProf.h

428 ↗

(On Diff #40978)

Ah -- I misread the code -- but it indeed was confusing -- the new way is better.

llvm/trunk/include/llvm/ProfileData/InstrProf.h

 }
 
 instrprof_error InstrProfRecord::merge(InstrProfRecord &Other) {
   // If the number of counters doesn't match we either have bad data
   // or a hash collision.
   if (Counts.size() != Other.Counts.size())
     return instrprof_error::count_mismatch;
 
+  instrprof_error Result = instrprof_error::success;
+
   for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
-    if (Counts[I] + Other.Counts[I] < Counts[I])
-      return instrprof_error::counter_overflow;
-    Counts[I] += Other.Counts[I];
+    bool ResultOverflowed;
+    Counts[I] = SaturatingAdd(Counts[I], Other.Counts[I], ResultOverflowed);
+    if (ResultOverflowed)
+      Result = instrprof_error::counter_overflow;
   }
 
   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
-    instrprof_error result = mergeValueProfData(Kind, Other);
-    if (result != instrprof_error::success)
-      return result;
+    instrprof_error MergeValueResult = mergeValueProfData(Kind, Other);
+    if (MergeValueResult != instrprof_error::success)
+      Result = MergeValueResult;
   }
 
-  return instrprof_error::success;
+  return Result;
 }
 
 inline support::endianness getHostEndianness() {
   return sys::IsLittleEndianHost ? support::little : support::big;
 }
 
 
 // Include definitions for value profile data

llvm/trunk/lib/ProfileData/InstrProfWriter.cpp

std::error_code InstrProfWriter::addRecord(InstrProfRecord &&I) {
   updateStringTableReferences(I);
   auto &ProfileDataMap = FunctionData[I.Name];
 
   bool NewFunc;
   ProfilingData::iterator Where;
   std::tie(Where, NewFunc) =
       ProfileDataMap.insert(std::make_pair(I.Hash, InstrProfRecord()));
   InstrProfRecord &Dest = Where->second;
+
+  instrprof_error Result;
   if (NewFunc) {
     // We've never seen a function with this name and hash, add it.
     Dest = std::move(I);
+    Result = instrprof_error::success;
   } else {
     // We're updating a function we've seen before.
-    instrprof_error MergeResult = Dest.merge(I);
-    if (MergeResult != instrprof_error::success) {
-      return MergeResult;
-    }
+    Result = Dest.merge(I);
   }
 
   // We keep track of the max function count as we go for simplicity.
+  // Update this statistic no matter the result of the merge.
   if (Dest.Counts[0] > MaxFunctionCount)
     MaxFunctionCount = Dest.Counts[0];
 
-  return instrprof_error::success;
+  return Result;
 }
 
 std::pair<uint64_t, uint64_t> InstrProfWriter::writeImpl(raw_ostream &OS) {
   OnDiskChainedHashTableGenerator<InstrProfRecordTrait> Generator;
 
   // Populate the hash table generator.
   for (const auto &I : FunctionData)
     Generator.insert(I.getKey(), &I.getValue());

llvm/trunk/test/tools/llvm-profdata/overflow.proftext

-# RUN: llvm-profdata merge %s -o %t.out 2>&1 | FileCheck %s
-# CHECK: overflow.proftext: overflow: Counter overflow
+# RUN: llvm-profdata merge %s -o %t.out 2>&1 | FileCheck %s --check-prefix=MERGE
+# RUN: llvm-profdata show %t.out | FileCheck %s --check-prefix=SHOW
+# MERGE: overflow.proftext: overflow: Counter overflow
+# SHOW: Total functions: 1
+# SHOW: Maximum function count: 18446744073709551615
+# SHOW: Maximum internal block count: 18446744073709551615
 
 overflow
 1
-1
+3
+18446744073709551615
 9223372036854775808
+18446744073709551615
 
 overflow
 1
-1
+3
+9223372036854775808
 9223372036854775808
+0

llvm/trunk/unittests/ProfileData/InstrProfTest.cpp

TEST_F(InstrProfTest, get_icall_data_merge1) {
   ASSERT_EQ(StringRef((const char *)VD_4[2].Value, 7), StringRef("callee1"));
   ASSERT_EQ(2U, VD_4[2].Count);
 }
 
 TEST_F(InstrProfTest, get_icall_data_merge1_saturation) {
   const uint64_t Max = std::numeric_limits<uint64_t>::max();
 
   InstrProfRecord Record1("caller", 0x1234, {1});
-  InstrProfRecord Record2("caller", 0x1234, {1});
+  InstrProfRecord Record2("caller", 0x1234, {Max});
   InstrProfRecord Record3("callee1", 0x1235, {3, 4});
 
   Record1.reserveSites(IPVK_IndirectCallTarget, 1);
   InstrProfValueData VD1[] = {{(uint64_t) "callee1", 1}};
   Record1.addValueData(IPVK_IndirectCallTarget, 0, VD1, 1, nullptr);
 
   Record2.reserveSites(IPVK_IndirectCallTarget, 1);
   InstrProfValueData VD2[] = {{(uint64_t) "callee1", Max}};
   Record2.addValueData(IPVK_IndirectCallTarget, 0, VD2, 1, nullptr);
 
   Writer.addRecord(std::move(Record1));
   Writer.addRecord(std::move(Record2));
   Writer.addRecord(std::move(Record3));
 
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   // Verify saturation of counts.
   ErrorOr<InstrProfRecord> R = Reader->getInstrProfRecord("caller", 0x1234);
   ASSERT_TRUE(NoError(R.getError()));
+
+  ASSERT_EQ(Max, R.get().Counts[0]);
+
   ASSERT_EQ(1U, R.get().getNumValueSites(IPVK_IndirectCallTarget));
   std::unique_ptr<InstrProfValueData[]> VD =
           R.get().getValueForSite(IPVK_IndirectCallTarget, 0);
   ASSERT_EQ(StringRef("callee1"), StringRef((const char *)VD[0].Value, 7));
   ASSERT_EQ(Max, VD[0].Count);
 }
 
 // Synthesize runtime value profile data.