[PGO] Use sum of count values to fix func entry count and add a check to verify BFI counts

[xur]

Summary

Raw profile count values for each BB are not kept after profile annotation.
We record function entry count and branch weights and use them to compute the count when needed.
This mechanism works well in a perfect world, but often breaks in real programs,
because of number prevision, inconsistent profile, or bugs in BFI) .
This patch add functionality to compare BFI counts with real profile counts right after reading the profile.
It also fixes function entry count to make the BFI count close to real profile counts.

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

260

It is probably more useful to have an option controlling checking hot BB's only -- check with either RawCount or BFI count is hot (can catch the case when a cold block becomes 'hot' with BFI info).

1625

what is the rationale and use of this fixup?

1678

Add comment of make variable name NonC0BBNum more obvious for its meaning.

1702

Variable not used.

llvm/test/Transforms/PGOProfile/fix_bfi.ll

2

Add an comment on the what the test case is testing (especially the fix check part).

[xur]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

260

Yes. Checking hot BFI counts will catch some abnormal cases.
The reason I used a cutoff instead of default hot threshold is that there could be too many hot BB to check for some programs.
Using a high cutoff could make the output much cleaner. And the user can specify the hot threshold from detailed summary.

I will probably keep this option and add another option that checking hot BB as you suggested.

1625

There is no perfect way to fix this: when the information is lost, we could not recover. This is just one way to fix it so that the total count close.

1678

will do.

1702

will put this variable under Debug macro.

llvm/test/Transforms/PGOProfile/fix_bfi.ll

2

will do.

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1630

assert here that function entry count is already set.

1634

In what situation can this happen?

1637

how can this be possible?

1645

maybe early return?

1648

negate the logic and early return?

1649

assert SumBFCount is not zero

1651

early return?

1654

Is this handled by the next statements?

1668

Is this needed?

[xur]

I'm reviving this patch because this fixes one of our internal bugs.

Before the fix, The BFI counters are way off the raw profile counter:

` BB : Count=96615607 BFI Count=16

BB : Count=96615607  BFI Count=16
BB : Count=9874441  BFI Count=2
BB : Count=9849389  BFI Count=2
BB : Count=9928400  BFI Count=2
BB : Count=96694618  BFI Count=16
BB : Count=30  BFI Count=0
BB : Count=96694588  BFI Count=16
BB : Count=93506121  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=6933665  BFI Count=1
BB : Count=6933665  BFI Count=1
BB : Count=4641130  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=3439260  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=4624009  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=2299158  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2234047  BFI Count=0
BB : Count=3500  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2225955  BFI Count=0
BB : Count=18824  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230585  BFI Count=0
BB : Count=2229242  BFI Count=0
BB : Count=38  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=68611  BFI Count=0
BB : Count=103021581  BFI Count=16
BB : Count=103021611  BFI Count=16
BB : Count=6406005  BFI Count=1

`

With this patch, we can get:

`BB : Count=1  BFI Count=6145756
BB : Count=96615607  BFI Count=98836277
BB : Count=96615607  BFI Count=98836277
BB : Count=9874441  BFI Count=10101401
BB : Count=9849389  BFI Count=10075773
BB : Count=9928400  BFI Count=10075773
BB : Count=96694618  BFI Count=98836277
BB : Count=30  BFI Count=31
BB : Count=96694588  BFI Count=98836246
BB : Count=93506121  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=6933665  BFI Count=6844610
BB : Count=6933665  BFI Count=6844610
BB : Count=4641130  BFI Count=4581520
BB : Count=4634507  BFI Count=4574982
BB : Count=4634507  BFI Count=4574982
BB : Count=3439260  BFI Count=3395087
BB : Count=4634090  BFI Count=4574982
BB : Count=4624009  BFI Count=4565030
BB : Count=4634090  BFI Count=4574982
BB : Count=2299158  BFI Count=2269628
BB : Count=2230547  BFI Count=2201898
BB : Count=2234047  BFI Count=2205353
BB : Count=3500  BFI Count=3455
BB : Count=2230547  BFI Count=2201898
BB : Count=2225955  BFI Count=2197365
BB : Count=18824  BFI Count=18582
BB : Count=2230547  BFI Count=2201898
BB : Count=2230547  BFI Count=2201898
BB : Count=2230585  BFI Count=2201936
BB : Count=2229242  BFI Count=2200610
BB : Count=2230547  BFI Count=2201898
BB : Count=68611  BFI Count=67730
BB : Count=103021581  BFI Count=98836246
BB : Count=103021611  BFI Count=98836277
BB : Count=6406005  BFI Count=6145756

`

I will post the updated patch shortly.

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1634

I changed to findBBInfo.
Usually this won't happen. But this can happen if there is unreachable BB (like when build at -O0).

1637

If the entryCount is 0, we don't have Profile Count for BB.
This could happen if we did not fix the entryCount.

But now, 0 entryCount is not possible after we populatedCounters (if the maxcount is nonzero). This is not needed. I will remove.

1651

Done

1654

Changed the code.

1668

Probably not. I removed it.

[xur]

Updated the patch that addressed David's review comments.
One noticeable change was to .add a new option "pgo-vefify-hot-bfi" which will
output a message when one of the following happens:
(1) a hot rawCount becomes non-hot in BFI
(2) a cold rawCount becomes hot in BFI

-Rong

[davidxl]

Can you split this patch into two? one for verification, the other for fixing?

[wenlei]

We record function entry count and branch weights and use them to compute the count when needed. This mechanism works well in a perfect world, but often breaks in real programs

We're battling this exact problem from sample PGO side. And we have internal patches for comparing block counts from BFI with ground truth. Perhaps these all can be refactored to be shared between Instr PGO and sample PGO. +@hoy

How does fixing up entry count alone help mitigate this problem?

[hoy]

In D61540#2404348, @xur wrote:

I'm reviving this patch because this fixes one of our internal bugs.

Before the fix, The BFI counters are way off the raw profile counter:

` BB : Count=96615607 BFI Count=16

BB : Count=96615607  BFI Count=16
BB : Count=9874441  BFI Count=2
BB : Count=9849389  BFI Count=2
BB : Count=9928400  BFI Count=2
BB : Count=96694618  BFI Count=16
BB : Count=30  BFI Count=0
BB : Count=96694588  BFI Count=16
BB : Count=93506121  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=6933665  BFI Count=1
BB : Count=6933665  BFI Count=1
BB : Count=4641130  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=3439260  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=4624009  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=2299158  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2234047  BFI Count=0
BB : Count=3500  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2225955  BFI Count=0
BB : Count=18824  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230585  BFI Count=0
BB : Count=2229242  BFI Count=0
BB : Count=38  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=68611  BFI Count=0
BB : Count=103021581  BFI Count=16
BB : Count=103021611  BFI Count=16
BB : Count=6406005  BFI Count=1

`

With this patch, we can get:

`BB : Count=1  BFI Count=6145756
BB : Count=96615607  BFI Count=98836277
BB : Count=96615607  BFI Count=98836277
BB : Count=9874441  BFI Count=10101401
BB : Count=9849389  BFI Count=10075773
BB : Count=9928400  BFI Count=10075773
BB : Count=96694618  BFI Count=98836277
BB : Count=30  BFI Count=31
BB : Count=96694588  BFI Count=98836246
BB : Count=93506121  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=6933665  BFI Count=6844610
BB : Count=6933665  BFI Count=6844610
BB : Count=4641130  BFI Count=4581520
BB : Count=4634507  BFI Count=4574982
BB : Count=4634507  BFI Count=4574982
BB : Count=3439260  BFI Count=3395087
BB : Count=4634090  BFI Count=4574982
BB : Count=4624009  BFI Count=4565030
BB : Count=4634090  BFI Count=4574982
BB : Count=2299158  BFI Count=2269628
BB : Count=2230547  BFI Count=2201898
BB : Count=2234047  BFI Count=2205353
BB : Count=3500  BFI Count=3455
BB : Count=2230547  BFI Count=2201898
BB : Count=2225955  BFI Count=2197365
BB : Count=18824  BFI Count=18582
BB : Count=2230547  BFI Count=2201898
BB : Count=2230547  BFI Count=2201898
BB : Count=2230585  BFI Count=2201936
BB : Count=2229242  BFI Count=2200610
BB : Count=2230547  BFI Count=2201898
BB : Count=68611  BFI Count=67730
BB : Count=103021581  BFI Count=98836246
BB : Count=103021611  BFI Count=98836277
BB : Count=6406005  BFI Count=6145756

`

I will post the updated patch shortly.

Interesting to see the BFI-computed execution count diverse so much from real counts, even for PGO. I'm wondering if this is due to optimizations in the training build. For the example above, the BFI-computed block frequencies (ratio, not execution count) seem not diverging too much for each block, compared to the real profile counts.

[xur]

Split the verification to another patch.

verification patch:
https://reviews.llvm.org/D91813

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1657

Perhaps take the max of the original func entry count and the new entry count?

[xur]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1657

Not sure if want a max here. Here a value of 1 makes the sum of raw counters and sum of BFI counters close to each other, better than original func entry count.

Using max will never reduce the entry count -- I don't think that is what we want.

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1657

I thought the intention of the patch is to correct the 'guessed' entry count which is usually '1'. If the original entry count is not 1, it is usually a value we can trust. Sometimes BFI can create insanely large counts which makes the scale really small. It ends up leading to new entry entry count to become 1 (from non-1 value). Is that the intended behavior?

[davidxl]

lgtm

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

EmitBranchProbability("pgo-emit-branch-prob", cl::init(false), cl::Hidden,
                                    "branch probability will be emitted as "
                                    "optimization remarks: -{Rpass|"
                                    "pass-remarks}=pgo-instrumentation"));
 
 static cl::opt<bool> PGOInstrumentEntry(
     "pgo-instrument-entry", cl::init(false), cl::Hidden,
     cl::desc("Force to instrument function entry basicblock."));
 
+static cl::opt<bool>
+    PGOFixEntryCount("pgo-fix-entry-count", cl::init(true), cl::Hidden,
+                     cl::desc("Fix function entry count in profile use."));
+
 // Command line option to turn on CFG dot dump after profile annotation.
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -pgo-view-counts
 extern cl::opt<PGOViewCountsType> PGOViewCounts;
 
 // Command line option to specify the name of the function for CFG dump
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -view-bfi-func-name=
 extern cl::opt<std::string> ViewBlockFreqFuncName;
 
 static cl::opt<bool>
     PGOOldCFGHashing("pgo-instr-old-cfg-hashing", cl::init(false), cl::Hidden,
PreservedAnalyses PGOInstrumentationGen::run(Module &M,
   };
 
   if (!InstrumentAllFunctions(M, LookupTLI, LookupBPI, LookupBFI, IsCS))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
+// Using the ratio b/w sums of profile count values and BFI count values to
+// adjust the func entry count.
+static void fixFuncEntryCount(PGOUseFunc &Func, LoopInfo &LI,
+                              BranchProbabilityInfo &NBPI) {
+  Function &F = Func.getFunc();
+  BlockFrequencyInfo NBFI(F, NBPI, LI);
+  auto BFIEntryCount = F.getEntryCount();
+  assert(BFIEntryCount.hasValue() && (BFIEntryCount.getCount() > 0) &&
+         "Invalid BFI Entrycount");
+  auto SumCount = APFloat::getZero(APFloat::IEEEdouble());
+  auto SumBFICount = APFloat::getZero(APFloat::IEEEdouble());
+  for (auto &BBI : F) {
+    uint64_t CountValue = 0;
+    uint64_t BFICountValue = 0;
+    if (!Func.findBBInfo(&BBI))
+      continue;
+    auto BFICount = NBFI.getBlockProfileCount(&BBI);
+    CountValue = Func.getBBInfo(&BBI).CountValue;
+    BFICountValue = BFICount.getValue();
+    SumCount.add(APFloat(CountValue * 1.0), APFloat::rmNearestTiesToEven);
+    SumBFICount.add(APFloat(BFICountValue * 1.0), APFloat::rmNearestTiesToEven);
+  }
+  if (SumCount.isZero())
+    return;
+
+  assert(SumBFICount.compare(APFloat(0.0)) == APFloat::cmpGreaterThan &&
+         "Incorrect sum of BFI counts");
+  if (SumBFICount.compare(SumCount) == APFloat::cmpEqual)
+    return;
+  double Scale = (SumCount / SumBFICount).convertToDouble();
+  if (Scale < 1.001 && Scale > 0.999)
+    return;
+
+  uint64_t FuncEntryCount = Func.getBBInfo(&*F.begin()).CountValue;
+  uint64_t NewEntryCount = 0.5 + FuncEntryCount * Scale;
+  if (NewEntryCount == 0)
+    NewEntryCount = 1;
+  if (NewEntryCount != FuncEntryCount) {
+    F.setEntryCount(ProfileCount(NewEntryCount, Function::PCT_Real));
+    LLVM_DEBUG(dbgs() << "FixFuncEntryCount: in " << F.getName()
+                      << ", entry_count " << FuncEntryCount << " --> "
+                      << NewEntryCount << "\n");
+  }
+}
+
 static bool annotateAllFunctions(
     Module &M, StringRef ProfileFileName, StringRef ProfileRemappingFileName,
     function_ref<TargetLibraryInfo &(Function &)> LookupTLI,
     function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
     ProfileSummaryInfo *PSI, bool IsCS) {
   LLVM_DEBUG(dbgs() << "Read in profile counters: ");
   auto &Ctx = M.getContext();
   // Read the counter array from file.
   auto ReaderOrErr =
       IndexedInstrProfReader::create(ProfileFileName, ProfileRemappingFileName);
   if (Error E = ReaderOrErr.takeError()) {
     handleAllErrors(std::move(E), [&](const ErrorInfoBase &EI) {
       Ctx.diagnose(
           DiagnosticInfoPGOProfile(ProfileFileName.data(), EI.message()));
     });
     return false;
   }
 
   std::unique_ptr<IndexedInstrProfReader> PGOReader =
       std::move(ReaderOrErr.get());
   if (!PGOReader) {
     Ctx.diagnose(DiagnosticInfoPGOProfile(ProfileFileName.data(),
                                           StringRef("Cannot get PGOReader")));
     return false;
   }
   if (!PGOReader->hasCSIRLevelProfile() && IsCS)
     return false;
 
   // TODO: might need to change the warning once the clang option is finalized.
   if (!PGOReader->isIRLevelProfile()) {
     Ctx.diagnose(DiagnosticInfoPGOProfile(
         ProfileFileName.data(), "Not an IR level instrumentation profile"));
     return false;
   }
 
   // Add the profile summary (read from the header of the indexed summary) here
   // so that we can use it below when reading counters (which checks if the
   // function should be marked with a cold or inlinehint attribute).
   M.setProfileSummary(PGOReader->getSummary(IsCS).getMD(M.getContext()),
                       IsCS ? ProfileSummary::PSK_CSInstr
                            : ProfileSummary::PSK_Instr);
   PSI->refresh();
if (PGOViewRawCounts != PGOVCT_None &&
           WriteGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
         else
           ViewGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
       else if (PGOViewRawCounts == PGOVCT_Text) {
         dbgs() << "pgo-view-raw-counts: " << Func.getFunc().getName() << "\n";
         Func.dumpInfo();
       }
     }
+
+    // Fix func entry count.
+    if (PGOFixEntryCount) {
+      LoopInfo LI{DominatorTree(F)};
+      BranchProbabilityInfo NBPI(F, LI);
+      fixFuncEntryCount(Func, LI, NBPI);
+    }
   }
 
   // Set function hotness attribute from the profile.
   // We have to apply these attributes at the end because their presence
   // can affect the BranchProbabilityInfo of any callers, resulting in an
   // inconsistent MST between prof-gen and prof-use.
   for (auto &F : HotFunctions) {
     F->addFnAttr(Attribute::InlineHint);

llvm/test/Transforms/PGOProfile/Inputs/fix_bfi.proftext

+# IR level Instrumentation Flag
+:ir
+sort_basket
+# Func Hash:
+948827210500800754
+# Num Counters:
+7
+# Counter Values:
[phone]
[phone]
[phone]
[phone]
[phone]
+6990942
+6013544
+

llvm/test/Transforms/PGOProfile/fix_bfi.ll

+; Note: Scaling the func entry count (using the sum of count value) so that BFI counter value is close to raw profile counter values.
+; RUN: llvm-profdata merge %S/Inputs/fix_bfi.proftext -o %t.profdata
+; RUN: opt -pgo-instr-use -pgo-test-profile-file=%t.profdata -S -pgo-fix-entry-count=true < %s 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.basket = type { %struct.arc*, i64, i64 }
+%struct.arc = type { i64, %struct.node*, %struct.node*, i32, %struct.arc*, %struct.arc*, i64, i64 }
+%struct.node = type { i64, i32, %struct.node*, %struct.node*, %struct.node*, %struct.node*, %struct.arc*, %struct.arc*, %struct.arc*, %struct.arc*, i64, i64, i32, i32 }
+
+@perm = internal unnamed_addr global [351 x %struct.basket*] zeroinitializer, align 16
+
+define dso_local void @sort_basket(i64 %min, i64 %max) {
+entry:
+  %add = add nsw i64 %min, %max
+  %div = sdiv i64 %add, 2
+  %arrayidx = getelementptr inbounds [351 x %struct.basket*], [351 x %struct.basket*]* @perm, i64 0, i64 %div
+  %0 = load %struct.basket*, %struct.basket** %arrayidx, align 8
+  %abs_cost = getelementptr inbounds %struct.basket, %struct.basket* %0, i64 0, i32 2
+  %1 = load i64, i64* %abs_cost, align 8
+  br label %do.body
+
+do.body:
+  %r.0 = phi i64 [ %max, %entry ], [ %r.2, %if.end ]
+  %l.0 = phi i64 [ %min, %entry ], [ %l.2, %if.end ]
+  br label %while.cond
+
+while.cond:
+  %l.1 = phi i64 [ %l.0, %do.body ], [ %inc, %while.body ]
+  %arrayidx1 = getelementptr inbounds [351 x %struct.basket*], [351 x %struct.basket*]* @perm, i64 0, i64 %l.1
+  %2 = load %struct.basket*, %struct.basket** %arrayidx1, align 8
+  %abs_cost2 = getelementptr inbounds %struct.basket, %struct.basket* %2, i64 0, i32 2
+  %3 = load i64, i64* %abs_cost2, align 8
+  %cmp = icmp sgt i64 %3, %1
+  br i1 %cmp, label %while.body, label %while.cond3
+
+while.body:
+  %inc = add nsw i64 %l.1, 1
+  br label %while.cond
+
+while.cond3:
+  %r.1 = phi i64 [ %r.0, %while.cond ], [ %dec, %while.body7 ]
+  %arrayidx4 = getelementptr inbounds [351 x %struct.basket*], [351 x %struct.basket*]* @perm, i64 0, i64 %r.1
+  %4 = load %struct.basket*, %struct.basket** %arrayidx4, align 8
+  %abs_cost5 = getelementptr inbounds %struct.basket, %struct.basket* %4, i64 0, i32 2
+  %5 = load i64, i64* %abs_cost5, align 8
+  %cmp6 = icmp sgt i64 %1, %5
+  br i1 %cmp6, label %while.body7, label %while.end8
+
+while.body7:
+  %dec = add nsw i64 %r.1, -1
+  br label %while.cond3
+
+while.end8:
+  %cmp9 = icmp slt i64 %l.1, %r.1
+  br i1 %cmp9, label %if.then, label %if.end
+
+if.then:
+  %6 = bitcast %struct.basket** %arrayidx1 to i64*
+  %7 = load i64, i64* %6, align 8
+  store %struct.basket* %4, %struct.basket** %arrayidx1, align 8
+  %8 = bitcast %struct.basket** %arrayidx4 to i64*
+  store i64 %7, i64* %8, align 8
+  br label %if.end
+
+if.end:
+  %cmp14 = icmp sgt i64 %l.1, %r.1
+  %not.cmp14 = xor i1 %cmp14, true
+  %9 = zext i1 %not.cmp14 to i64
+  %r.2 = sub i64 %r.1, %9
+  %not.cmp1457 = xor i1 %cmp14, true
+  %inc16 = zext i1 %not.cmp1457 to i64
+  %l.2 = add nsw i64 %l.1, %inc16
+  %cmp19 = icmp sgt i64 %l.2, %r.2
+  br i1 %cmp19, label %do.end, label %do.body
+
+do.end:
+  %cmp20 = icmp sgt i64 %r.2, %min
+  br i1 %cmp20, label %if.then21, label %if.end22
+
+if.then21:
+  call void @sort_basket(i64 %min, i64 %r.2)
+  br label %if.end22
+
+if.end22:
+  %cmp23 = icmp slt i64 %l.2, %max
+  %cmp24 = icmp slt i64 %l.2, 51
+  %or.cond = and i1 %cmp23, %cmp24
+  br i1 %or.cond, label %if.then25, label %if.end26
+
+if.then25:
+  call void @sort_basket(i64 %l.2, i64 %max)
+  br label %if.end26
+
+if.end26:
+  ret void
+}
+
+; CHECK: define dso_local void @sort_basket(i64 %min, i64 %max) #0 !prof [[ENTRY_COUNT:![0-9]+]]
+; CHECK: [[ENTRY_COUNT]] = !{!"function_entry_count", i64 12949310}