[PGO] Fix two issues in PGOMemOPSizeOpt.

[hjyamauchi]

Summary

1. PGOMemOPSizeOpt grabs only the first, up to five (by default) entries from

the value profile metadata and preserves the remaining entries for the fallback
memop call site. If there are more than five entries, the rest of the entries
would get dropped. This is fine for PGOMemOPSizeOpt itself as it only promotes
up to 3 (by default) values, but potentially not for other downstream passes
that may use the value profile metadata.

2. PGOMemOPSizeOpt originally assumed that only values 0 through 8 are kept

track of. When the range buckets were introduced, it was changed to skip the
range buckets, but since it does not grab all entries (only five), if some range
buckets exist in the first five entries, it could potentially cause fewer
promotion opportunities (eg. if 4 out of 5 were range buckets, it may be able to
promote up to one non-range bucket, as opposed to 3.) Also, combined with 1, it
means that wrong entries may be preserved, as it didn't correctly keep track of
which were entries were skipped.

To fix this, PGOMemOPSizeOpt now grabs all the entries (up to the maximum number
of value profile buckets), keeps track of which entries were skipped, and
preserves all the remaining entries.

[davidxl]

Perhaps add a test case showing that up to 3 ranges can be promoted?

[hjyamauchi]

In D97592#2593258, @davidxl wrote:

Perhaps add a test case showing that up to 3 ranges can be promoted?

Do you mean one in general or for 2 (specially this part "if 4 out of 5 were range buckets, it may be able to
promote up to one non-range bucket, as opposed to 3.")?

[hjyamauchi]

Address comment.

[hjyamauchi]

Okay added a new test.

[davidxl]

compiler-rt/include/profile/InstrProfData.inc

863

should we define a macro for it?

[hjyamauchi]

Address comment.

[davidxl]

lgtm

compiler-rt/include/profile/InstrProfData.inc

 /* 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 {
   /* Profiled value. */
   uint64_t Value;
   /* Number of times the value appears in the training run. */
   uint64_t Count;
 } InstrProfValueData;
 
 #endif /* INSTR_PROF_DATA_INC */
 
 #ifndef INSTR_ORDER_FILE_INC
 /* The maximal # of functions: 128*1024 (the buffer size will be 128*4 KB). */
 #define INSTR_ORDER_FILE_BUFFER_SIZE 131072
 #define INSTR_ORDER_FILE_BUFFER_BITS 17

 
 INSTR_PROF_VISIBILITY INSTR_PROF_INLINE
 int InstProfClzll(unsigned long long X) { return __builtin_clzll(X); }
 INSTR_PROF_VISIBILITY INSTR_PROF_INLINE
 int InstProfPopcountll(unsigned long long X) { return __builtin_popcountll(X); }
 
 #endif  /* defined(_MSC_VER) && !defined(__clang__) */
 
+/* Return the number of the value range buckets */
+INSTR_PROF_VISIBILITY INSTR_PROF_INLINE uint64_t
+InstrProfGetNumBuckets() {
+  return 22;
+}
+
 /* Map an (observed) memop size value to the representative value of its range.
  * For example, 5 -> 5, 22 -> 17, 99 -> 65, 256 -> 256, 1001 -> 513. */
 INSTR_PROF_VISIBILITY INSTR_PROF_INLINE uint64_t
 InstrProfGetRangeRepValue(uint64_t Value) {
   if (Value <= 8)
     // The first ranges are individually tracked. Use the value as is.
     return Value;
   else if (Value >= 513)

llvm/include/llvm/ProfileData/InstrProfData.inc

 /* 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 {
   /* Profiled value. */
   uint64_t Value;
   /* Number of times the value appears in the training run. */
   uint64_t Count;
 } InstrProfValueData;
 
 #endif /* INSTR_PROF_DATA_INC */
 
 #ifndef INSTR_ORDER_FILE_INC
 /* The maximal # of functions: 128*1024 (the buffer size will be 128*4 KB). */
 #define INSTR_ORDER_FILE_BUFFER_SIZE 131072
 #define INSTR_ORDER_FILE_BUFFER_BITS 17

 
 INSTR_PROF_VISIBILITY INSTR_PROF_INLINE
 int InstProfClzll(unsigned long long X) { return __builtin_clzll(X); }
 INSTR_PROF_VISIBILITY INSTR_PROF_INLINE
 int InstProfPopcountll(unsigned long long X) { return __builtin_popcountll(X); }
 
 #endif  /* defined(_MSC_VER) && !defined(__clang__) */
 
+/* Return the number of the value range buckets */
+INSTR_PROF_VISIBILITY INSTR_PROF_INLINE uint64_t
+InstrProfGetNumBuckets() {
+  return 22;
+}
+
 /* Map an (observed) memop size value to the representative value of its range.
  * For example, 5 -> 5, 22 -> 17, 99 -> 65, 256 -> 256, 1001 -> 513. */
 INSTR_PROF_VISIBILITY INSTR_PROF_INLINE uint64_t
 InstrProfGetRangeRepValue(uint64_t Value) {
   if (Value <= 8)
     // The first ranges are individually tracked. Use the value as is.
     return Value;
   else if (Value >= 513)

llvm/lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

 
 class MemOPSizeOpt : public InstVisitor<MemOPSizeOpt> {
 public:
   MemOPSizeOpt(Function &Func, BlockFrequencyInfo &BFI,
                OptimizationRemarkEmitter &ORE, DominatorTree *DT,
                TargetLibraryInfo &TLI)
       : Func(Func), BFI(BFI), ORE(ORE), DT(DT), TLI(TLI), Changed(false) {
     ValueDataArray =
-        std::make_unique<InstrProfValueData[]>(MemOPMaxVersion + 2);
+        std::make_unique<InstrProfValueData[]>(InstrProfGetNumBuckets());
   }
   bool isChanged() const { return Changed; }
   void perform() {
     WorkList.clear();
     visit(Func);
 
     for (auto &MO : WorkList) {
       ++NumOfPGOMemOPAnnotate;

 
 bool MemOPSizeOpt::perform(MemOp MO) {
   assert(MO.I);
   if (MO.isMemmove())
     return false;
   if (!MemOPOptMemcmpBcmp && (MO.isMemcmp(TLI) || MO.isBcmp(TLI)))
     return false;
 
-  uint32_t NumVals, MaxNumPromotions = MemOPMaxVersion + 2;
+  uint32_t NumVals, MaxNumVals = InstrProfGetNumBuckets();
   uint64_t TotalCount;
-  if (!getValueProfDataFromInst(*MO.I, IPVK_MemOPSize, MaxNumPromotions,
+  if (!getValueProfDataFromInst(*MO.I, IPVK_MemOPSize, MaxNumVals,
                                 ValueDataArray.get(), NumVals, TotalCount))
     return false;
 
   uint64_t ActualCount = TotalCount;
   uint64_t SavedTotalCount = TotalCount;
   if (MemOPScaleCount) {
     auto BBEdgeCount = BFI.getBlockProfileCount(MO.I->getParent());
     if (!BBEdgeCount)
bool MemOPSizeOpt::perform(MemOp MO) {
   uint64_t SavedRemainCount = SavedTotalCount;
   SmallVector<uint64_t, 16> SizeIds;
   SmallVector<uint64_t, 16> CaseCounts;
   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);
-  for (auto &VD : VDs) {
+  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)
+    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))
+    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");
       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);
     SavedRemainCount -= VD.Count;
 
-    if (++Version > MemOPMaxVersion && MemOPMaxVersion != 0)
+    if (++Version > MemOPMaxVersion && MemOPMaxVersion != 0) {
+      RemainingVDs.insert(RemainingVDs.end(), I + 1, E);
       break;
     }
+  }
 
   if (Version == 0)
     return false;
 
   CaseCounts[0] = RemainCount;
   if (RemainCount > MaxCount)
     MaxCount = RemainCount;
 
if (!MemOpTy->isVoidTy()) {
     PHI = IRBM.CreatePHI(MemOpTy, SizeIds.size() + 1, "MemOP.RVMerge");
     MO.I->replaceAllUsesWith(PHI);
     PHI->addIncoming(MO.I, DefaultBB);
   }
 
   // Clear the value profile data.
   MO.I->setMetadata(LLVMContext::MD_prof, nullptr);
   // If all promoted, we don't need the MD.prof metadata.
-  if (SavedRemainCount > 0 || Version != NumVals)
+  if (SavedRemainCount > 0 || Version != NumVals) {
     // Otherwise we need update with the un-promoted records back.
-    annotateValueSite(*Func.getParent(), *MO.I, VDs.slice(Version),
-                      SavedRemainCount, IPVK_MemOPSize, NumVals);
+    ArrayRef<InstrProfValueData> RemVDs(RemainingVDs);
+    annotateValueSite(*Func.getParent(), *MO.I, RemVDs, SavedRemainCount,
+                      IPVK_MemOPSize, NumVals);
+  }
 
   LLVM_DEBUG(dbgs() << "\n\n== Basic Block After==\n");
 
   std::vector<DominatorTree::UpdateType> Updates;
   if (DT)
     Updates.reserve(2 * SizeIds.size());
 
   for (uint64_t SizeId : SizeIds) {

llvm/test/Transforms/PGOProfile/memop_size_opt.ll

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), !prof !30
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst2, i8* %src2, i64 %conv, i1 false), !prof !31
   br label %for.inc
 
 ; MEMOP_OPT:  switch i64 %conv, label %[[DEFAULT_LABEL:.*]] [
 ; MEMOP_OPT:    i64 0, label %[[CASE_1_LABEL:.*]]
-; MEMOP_OPT:  ], !prof [[SWITCH_BW:![0-9]+]] 
+; MEMOP_OPT:  ], !prof [[SWITCH_BW1:![0-9]+]]
 ; MEMOP_OPT: [[CASE_1_LABEL]]:
 ; MEMOP_OPT:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 0, i1 false)
 ; MEMOP_OPT:   br label %[[MERGE_LABEL:.*]]
 ; MEMOP_OPT: [[DEFAULT_LABEL]]:
-; MEMOP_OPT:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %conv, i1 false), !prof [[NEWVP:![0-9]+]]
+; MEMOP_OPT:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %conv, i1 false), !prof [[NEWVP1:![0-9]+]]
 ; MEMOP_OPT:   br label %[[MERGE_LABEL]]
 ; MEMOP_OPT: [[MERGE_LABEL]]:
 ; MEMOP_OPT:  switch i64 %conv, label %[[DEFAULT_LABEL2:.*]] [
 ; MEMOP_OPT:    i64 0, label %[[CASE_1_LABEL2:.*]]
-; MEMOP_OPT:  ], !prof [[SWITCH_BW:![0-9]+]] 
+; MEMOP_OPT:  ], !prof [[SWITCH_BW2:![0-9]+]]
 ; MEMOP_OPT: [[CASE_1_LABEL2]]:
 ; MEMOP_OPT:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst2, i8* %src2, i64 0, i1 false)
 ; MEMOP_OPT:   br label %[[MERGE_LABEL2:.*]]
 ; MEMOP_OPT: [[DEFAULT_LABEL2]]:
-; MEMOP_OPT:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst2, i8* %src2, i64 %conv, i1 false), !prof [[NEWVP]]
+; MEMOP_OPT:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst2, i8* %src2, i64 %conv, i1 false), !prof [[NEWVP2:![0-9]+]]
 ; MEMOP_OPT:   br label %[[MERGE_LABEL2]]
 ; MEMOP_OPT: [[MERGE_LABEL2]]:
 ; MEMOP_OPT:   br label %for.inc
 
 for.inc:
   %inc = add nsw i32 %j.0, 1
   br label %for.cond1
 
for.body3:
   %conv = sext i32 %add to i64
   %memcmp = call i32 @memcmp(i8* %dst, i8* %src, i64 %conv), !prof !30
   %bcmp = call i32 @bcmp(i8* %dst2, i8* %src2, i64 %conv), !prof !31
   call void @consume(i32 %memcmp, i32 %bcmp)
   br label %for.inc
 
 ; MEMOP_OPT:  switch i64 %conv, label %[[DEFAULT_LABEL:.*]] [
 ; MEMOP_OPT:    i64 0, label %[[CASE_1_LABEL:.*]]
-; MEMOP_OPT:  ], !prof [[SWITCH_BW:![0-9]+]]
+; MEMOP_OPT:  ], !prof [[SWITCH_BW1]]
 ; MEMOP_OPT: [[CASE_1_LABEL]]:
 ; MEMOP_OPT:   %[[RV:.*]] = call i32 @memcmp(i8* %dst, i8* %src, i64 0)
 ; MEMOP_OPT:   br label %[[MERGE_LABEL:.*]]
 ; MEMOP_OPT: [[DEFAULT_LABEL]]:
-; MEMOP_OPT:   %[[RVD:.*]] = call i32 @memcmp(i8* %dst, i8* %src, i64 %conv), !prof [[NEWVP:![0-9]+]]
+; MEMOP_OPT:   %[[RVD:.*]] = call i32 @memcmp(i8* %dst, i8* %src, i64 %conv), !prof [[NEWVP1]]
 ; MEMOP_OPT:   br label %[[MERGE_LABEL]]
 ; MEMOP_OPT: [[MERGE_LABEL]]:
 ; MEMOP_OPT:  %[[PHI:.*]] = phi i32 [ %[[RVD]], %[[DEFAULT_LABEL]] ], [ %[[RV]], %[[CASE_1_LABEL]] ]
 ; MEMOP_OPT:  switch i64 %conv, label %[[DEFAULT_LABEL2:.*]] [
 ; MEMOP_OPT:    i64 0, label %[[CASE_1_LABEL2:.*]]
-; MEMOP_OPT:  ], !prof [[SWITCH_BW:![0-9]+]]
+; MEMOP_OPT:  ], !prof [[SWITCH_BW2]]
 ; MEMOP_OPT: [[CASE_1_LABEL2]]:
 ; MEMOP_OPT:   %[[RV2:.*]] = call i32 @bcmp(i8* %dst2, i8* %src2, i64 0)
 ; MEMOP_OPT:   br label %[[MERGE_LABEL2:.*]]
 ; MEMOP_OPT: [[DEFAULT_LABEL2]]:
-; MEMOP_OPT:   %[[RVD2:.*]] = call i32 @bcmp(i8* %dst2, i8* %src2, i64 %conv), !prof [[NEWVP]]
+; MEMOP_OPT:   %[[RVD2:.*]] = call i32 @bcmp(i8* %dst2, i8* %src2, i64 %conv), !prof [[NEWVP2]]
 ; MEMOP_OPT:   br label %[[MERGE_LABEL2]]
 ; MEMOP_OPT: [[MERGE_LABEL2]]:
 ; MEMOP_OPT:   %[[PHI2:.*]] = phi i32 [ %[[RVD2]], %[[DEFAULT_LABEL2]] ], [ %[[RV2]], %[[CASE_1_LABEL2]] ]
 ; MEMOP_OPT:   call void @consume(i32 %[[PHI]], i32 %[[PHI2]])
 ; MEMOP_OPT:   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
 }
 
-; MEMOP_OPT: [[SWITCH_BW]] = !{!"branch_weights", i32 457, i32 99}
+; MEMOP_OPT: [[SWITCH_BW1]] = !{!"branch_weights", i32 457, i32 99}
 ; Should be 457 total left (original total count 556, minus 99 from specialized
-; value 1, which is removed from VP array. Also, we only end up with 5 total
-; values, since the default max number of promotions is 5 and therefore
-; the rest of the values are ignored when extracting the VP metadata.
-; MEMOP_OPT: [[NEWVP]] = !{!"VP", i32 1, i64 457, i64 2, i64 88, i64 3, i64 77, i64 9, i64 72, i64 4, i64 66}
+; value 0, which is removed from VP array. This should preserve all unpromoted values.
+; MEMOP_OPT: [[NEWVP1]] = !{!"VP", i32 1, i64 457, i64 2, i64 88, i64 3, i64 77, i64 9, i64 72, i64 4, i64 66, i64 5, i64 55, i64 6, i64 44, i64 7, i64 33, i64 8, i64 22}
+; MEMOP_OPT: [[SWITCH_BW2]] = !{!"branch_weights", i32 465, i32 91}
+; Should be 465 total left (original total count 556, minus 91 from specialized
+; value 0, which is removed from VP array. This should preserve all unpromoted values. Range values 9, 17, 33, 65, 129 should be skipped and preserved.
+; MEMOP_OPT: [[NEWVP2]] = !{!"VP", i32 1, i64 465, i64 9, i64 94, i64 17, i64 93, i64 33, i64 93, i64 65, i64 92, i64 129, i64 92, i64 2, i64 1}
 
 !llvm.module.flags = !{!0}
 
 !0 = !{i32 1, !"ProfileSummary", !1}
 !1 = !{!2, !3, !4, !5, !6, !7, !8, !9}
 !2 = !{!"ProfileFormat", !"InstrProf"}
 !3 = !{!"TotalCount", i64 579}
 !4 = !{!"MaxCount", i64 556}

 !23 = !{i32 999000, i64 1, i32 5}
 !24 = !{i32 999900, i64 1, i32 5}
 !25 = !{i32 999990, i64 1, i32 5}
 !26 = !{i32 999999, i64 1, i32 5}
 !27 = !{!"function_entry_count", i64 1}
 !28 = !{!"branch_weights", i32 20, i32 1}
 !29 = !{!"branch_weights", i32 556, i32 20}
 !30 = !{!"VP", i32 1, i64 556, i64 0, i64 99, i64 2, i64 88, i64 3, i64 77, i64 9, i64 72, i64 4, i64 66, i64 5, i64 55, i64 6, i64 44, i64 7, i64 33, i64 8, i64 22}
-!31 = !{!"VP", i32 1, i64 556, i64 0, i64 99, i64 2, i64 88, i64 3, i64 77, i64 9, i64 72, i64 4, i64 66, i64 5, i64 55, i64 6, i64 44, i64 7, i64 33, i64 8, i64 22}
+!31 = !{!"VP", i32 1, i64 556, i64 9, i64 94, i64 17, i64 93, i64 33, i64 93, i64 65, i64 92, i64 129, i64 92, i64 0, i64 91, i64 2, i64 1}
 
 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)
 

 ; YAML-NEXT: Pass:            pgo-memop-opt
 ; YAML-NEXT: Name:            memopt-opt
 ; YAML-NEXT: Function:        foo
 ; YAML-NEXT: Hotness:         0
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'optimized '
 ; YAML-NEXT:   - Memop:           memcpy
 ; YAML-NEXT:   - String:          ' with count '
-; YAML-NEXT:   - Count:           '99'
+; YAML-NEXT:   - Count:           '91'
 ; YAML-NEXT:   - String:          ' out of '
 ; YAML-NEXT:   - Total:           '556'
 ; YAML-NEXT:   - String:          ' for '
 ; YAML-NEXT:   - Versions:        '1'
 ; YAML-NEXT:   - String:          ' versions'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Passed
 ; YAML-NEXT: Pass:            pgo-memop-opt

 ; YAML-NEXT: Pass:            pgo-memop-opt
 ; YAML-NEXT: Name:            memopt-opt
 ; YAML-NEXT: Function:        foo_memcmp_bcmp
 ; YAML-NEXT: Hotness:         0
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'optimized '
 ; YAML-NEXT:   - Memop:           bcmp
 ; YAML-NEXT:   - String:          ' with count '
-; YAML-NEXT:   - Count:           '99'
+; YAML-NEXT:   - Count:           '91'
 ; YAML-NEXT:   - String:          ' out of '
 ; YAML-NEXT:   - Total:           '556'
 ; YAML-NEXT:   - String:          ' for '
 ; YAML-NEXT:   - Versions:        '1'
 ; YAML-NEXT:   - String:          ' versions'
 ; YAML-NEXT: ...