[llvm-profdata] Check for all duplicate entries in MemOpSize table

[ormris]

Summary

Previously, we only checked for duplicate zero entries when merging a MemOPSize table (see D92074), but a user recently provided a reproducer demonstrating that other entries can also be duplicated. As demonstrated by the test in this patch, PGOMemOPSizeOpt can potentially generate invalid IR for non-zero, non-consecutive duplicate entries. This seems to be a rare case, since the duplicate entry is often below the threshold, but possible. This patch extends the existing warning to check for any duplicate values in the table, both in the optimization and in llvm-profdata. We're hoping that this expanded warning will catch more examples of this behavior so we can diagnose the root cause of these duplicate entries more easily.

[ormris]

ping

[ellis]

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

318–319

Why not make this a full diagnostic error/warning? Is this something a user could encounter in the wild?

318–319

llvm/test/tools/llvm-profdata/invalid-profile-gen-dup-entries.proftext

5

It seems strange that this is emitted as a warning rather than an error. Is there a case where this warning can be safely ignored?

[ormris]

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

318–319

Why not make this a full diagnostic error/warning?

Well, my understanding is that invalid profile data is usually skipped with a diagnostic. I don't want this error to be out of line with other profile data diagnostics. If something more severe is usually emitted, then we should change this error as well.

Is this something a user could encounter in the wild?

This does occur in the wild, though it's very rare. We originally discovered this issue when a user sent us invalid bitcode which we determined had been generated by this pass.

llvm/test/tools/llvm-profdata/invalid-profile-gen-dup-entries.proftext

5

My original intention was to make this an error (see the earlier patch), but my experiments seem to indicate that very few users 1) encounter the bug that generates this invalid profile data and 2) have the correct conditions to force the MemOpSize pass to use that invalid profile data. If the 3 largest counts aren't invalid, it seems like generating invalid bitcode is unlikely. We also haven't seen many users report this diagnostic to us.

That said, while I'm comfortable leaving it as a warning, but I would still prefer this to be an error. If it's an error, we would likely get more data to reproduce this issue. @xur, do you have any thoughts on this?

[ormris]

Changelist:

• Roll insertion and existence check into one line.

[ellis]

llvm/lib/ProfileData/InstrProfWriter.cpp

536

Oh I missed this the first time.

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

318–319

This does occur in the wild, though it's very rare. We originally discovered this issue when a user sent us invalid bitcode which we determined had been generated by this pass.

If the compiler generated invalid bitcode then IMO we should definitely emit an error. Or maybe we can turn this into an assert at least? Maybe there is something I'm missing because I'm not familiar with MemOP.

[ormris]

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

318–319

OK, that makes sense to me. I'll change it in the next update.

[ormris]

• Correct existence check
• Change debug note to an error
• Update tests to look for error

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

318–319

I've changed this to a simple error, but there is an argument that it should be an optimization remark. Thoughts?

[ormris]

Ping

[ellis]

Seems fine to me!

[ormris]

Thanks! I'll commit this.

llvm/lib/ProfileData/InstrProfWriter.cpp

 Error InstrProfWriter::validateRecord(const InstrProfRecord &Func) {
   for (uint32_t VK = 0; VK <= IPVK_Last; VK++) {
     uint32_t NS = Func.getNumValueSites(VK);
     if (!NS)
       continue;
     for (uint32_t S = 0; S < NS; S++) {
       uint32_t ND = Func.getNumValueDataForSite(VK, S);
       std::unique_ptr<InstrProfValueData[]> VD = Func.getValueForSite(VK, S);
-      bool WasZero = false;
+      DenseSet<uint64_t> SeenValues;
       for (uint32_t I = 0; I < ND; I++)
-        if ((VK != IPVK_IndirectCallTarget) && (VD[I].Value == 0)) {
-          if (WasZero)
-            return make_error<InstrProfError>(instrprof_error::invalid_prof);
-          WasZero = true;
-        }
+        if ((VK != IPVK_IndirectCallTarget) && !SeenValues.insert(VD[I].Value).second)
     }
   }
 
   return Error::success();
 }
 
 void InstrProfWriter::writeRecordInText(StringRef Name, uint64_t Hash,
                                         const InstrProfRecord &Func,

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

if (MemOPScaleCount)
     LLVM_DEBUG(dbgs() << "Scale counts: numerator = " << ActualCount
                       << " denominator = " << SavedTotalCount << "\n");
 
   // Keeping track of the count of the default case:
   uint64_t RemainCount = TotalCount;
   uint64_t SavedRemainCount = SavedTotalCount;
   SmallVector<uint64_t, 16> SizeIds;
   SmallVector<uint64_t, 16> CaseCounts;
+  SmallDenseSet<uint64_t, 16> SeenSizeId;
   uint64_t MaxCount = 0;
   unsigned Version = 0;
-  int64_t LastV = -1;
   // Default case is in the front -- save the slot here.
   CaseCounts.push_back(0);
   SmallVector<InstrProfValueData, 24> RemainingVDs;
   for (auto I = VDs.begin(), E = VDs.end(); I != E; ++I) {
     auto &VD = *I;
     int64_t V = VD.Value;
     uint64_t C = VD.Count;
     if (MemOPScaleCount)
       C = getScaledCount(C, ActualCount, SavedTotalCount);
 
     if (!InstrProfIsSingleValRange(V) || V > MemOpMaxOptSize) {
       RemainingVDs.push_back(VD);
       continue;
     }
 
     // ValueCounts are sorted on the count. Break at the first un-profitable
     // value.
     if (!isProfitable(C, RemainCount)) {
       RemainingVDs.insert(RemainingVDs.end(), I, E);
       break;
     }
 
-    if (V == LastV) {
-      LLVM_DEBUG(dbgs() << "Invalid Profile Data in Function " << Func.getName()
-                        << ": Two consecutive, identical values in MemOp value"
-                           "counts.\n");
+    if (!SeenSizeId.insert(V).second) {
+      errs() << "Invalid Profile Data in Function " << Func.getName()
+             << ": Two identical values in MemOp value counts.\n";
       return false;
     }
 
-    LastV = V;
-
     SizeIds.push_back(V);
     CaseCounts.push_back(C);
     if (C > MaxCount)
       MaxCount = C;
 
     assert(RemainCount >= C);
     RemainCount -= C;
     assert(SavedRemainCount >= VD.Count);

llvm/test/Transforms/PGOProfile/Inputs/duplicate-values.proftext

+# IR level Instrumentation Flag
+:ir
+foo
+# Func Hash:
+687116424982578944
+# Num Counters:
+3
+# Counter Values:
+523
+20
+1
+# Num Value Kinds:
+1
+# ValueKind = IPVK_MemOPSize:
+1
+# NumValueSites:
+3
+9
+1:99
+2:88
+1:77
+9:72
+4:66
+5:55
+2:44
+7:33
+8:22
+9
+7:33
+2:88
+9:72
+4:66
+1:99
+5:55
+6:44
+3:77
+8:22
+9
+7:33
+2:88
+9:72
+4:66
+1:99
+5:55
+6:44
+3:77
+8:22

llvm/test/Transforms/PGOProfile/consecutive-zeros.ll

-; REQUIRES: asserts
 ; RUN: llvm-profdata merge %S/Inputs/consecutive-zeros.proftext -o %t.profdata
-; RUN: opt < %s -debug -passes=pgo-instr-use,pgo-memop-opt -pgo-memop-count-threshold=0 -pgo-memop-percent-threshold=0 -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s
+; RUN: opt < %s -passes=pgo-instr-use,pgo-memop-opt -pgo-memop-count-threshold=0 -pgo-memop-percent-threshold=0 -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @foo(ptr %dst, ptr %src, ptr %a, i32 %n) {
 ; CHECK: Invalid Profile
 entry:
   br label %for.cond

llvm/test/Transforms/PGOProfile/duplicate-memop-values.ll

+; RUN: llvm-profdata merge %S/Inputs/consecutive-zeros.proftext -o %t.profdata
+; RUN: opt < %s -debug -passes=pgo-instr-use,pgo-memop-opt -pgo-memop-count-threshold=0 -pgo-memop-percent-threshold=0 -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @foo(i8* %dst, i8* %src, i32* %a, i32 %n) {
+; CHECK: {{[Ii]}}nvalid {{[Pp]}}rofile
+entry:
+  br label %for.cond
+
+for.cond:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc5, %for.inc4 ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end6
+
+for.body:
+  br label %for.cond1
+
+for.cond1:
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %idx.ext = sext i32 %i.0 to i64
+  %add.ptr = getelementptr inbounds i32, i32* %a, i64 %idx.ext
+  %0 = load i32, i32* %add.ptr, align 4
+  %cmp2 = icmp slt i32 %j.0, %0
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:
+  %add = add nsw i32 %i.0, 1
+  %conv = sext i32 %add to i64
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %conv, i1 false)
+  %memcmp = call i32 @memcmp(i8* %dst, i8* %src, i64 %conv)
+  %bcmp = call i32 @bcmp(i8* %dst, i8* %src, i64 %conv)
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:
+  br label %for.inc4
+
+for.inc4:
+  %inc5 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end6:
+  ret void
+}
+
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1)
+
+declare i32 @memcmp(i8*, i8*, i64)
+declare i32 @bcmp(i8*, i8*, i64)
+
+declare void @llvm.lifetime.end(i64, i8* nocapture)

llvm/test/tools/llvm-profdata/invalid-profile-gen-dup-entries.proftext

+# RUN: llvm-profdata merge --text -j 4 %s %s %s %s -o %t 2>&1 | FileCheck %s
+# RUN: llvm-profdata merge --binary -j 4 %s %s %s %s -o %t 2>&1 | FileCheck %s
+# IR level Instrumentation Flag
+# CHECK: warning: invalid profile created
+:ir
+foo
+# Func Hash:
[phone]
+# Num Counters:
+3
+# Counter Values:
+20
+556
+1
+# Num Value Kinds:
+1
+# ValueKind = IPVK_MemOPSize:
+1
+# NumValueSites:
+1
+9
+1:99
+3:88
+1:77
+9:72
+4:66
+5:55
+6:44
+7:33
+8:22