[BOLT] Add stale-related logging

[spupyrev]

Summary

Adding some logs related to stale profile matching. The new data can be helpful
to understand how "stale" the input profile is and how well the inference is
able to utilize the stale data.

Example of outputs on clang-10 built with LTO (profile collected on a year-old release):

BOLT-INFO: inferred profile for 2101 (18.52% of profiled, 100.00% of stale) functions responsible for 30.95% samples (14754697 out of 47670654)
BOLT-INFO: stale inference matched 89.42% of basic blocks (79052 out of 88402 stale) responsible for 76.99% samples (645737 out of 838719 stale)

LTO+AutoFDO:

BOLT-INFO: inferred profile for 6146 (57.57% of profiled, 100.00% of stale) functions responsible for 90.34% samples (50891403 out of 56330313)
BOLT-INFO: stale inference matched 74.55% of basic blocks (191295 out of 256589 stale) responsible for 57.30% samples (1288632 out of 2248799 stale)

[Amir]

LGTM.
@maksfb – please take a look if it's fine to add BF Inference stats and methods.

[maksfb]

bolt/include/bolt/Core/BinaryFunction.h

391–400

Let's move the stats out of the BinaryFunction. Once the input function list is populated, function addresses are fixed. You can use a map, e.g., to attach stats to BinaryFunction *. I'm also not sure you need per-function stats or having aggregated is enough.

[spupyrev]

bolt/include/bolt/Core/BinaryFunction.h

391–400

Yes that's what I was thinking on doing. Is there a good example of storing stats or some other info across different passes?

[maksfb]

bolt/include/bolt/Core/BinaryFunction.h

391–400

We don't have a good stats aggregator in BOLT. The easiest way is to create a new class and include its instance in the BC. Another way is to modify the pass manager, which is more involved. Also worth checking what LLVM has implemented.

[spupyrev]

bolt/include/bolt/Core/BinaryFunction.h

391–400

BC seems to already have something similar, e.g., BinaryContext::MissedMacroFusionPairs, although that's not a separate object.
LLVM has ADT/Statistic.h which looks similar but implemented via static variables so some changes would be needed to access the stats in different passes.

I guess the best would be to have a stat wrapper in BC and move existing fields (MissedMacroFusionPairs, MissedMacroFusionExecCount) there?

[spupyrev]

Moving stats from BinaryFunction to (aggregated) BinaryContext

[maksfb]

bolt/include/bolt/Core/BinaryFunction.h

391–400

Sounds reasonable to me.

[maksfb]

bolt/lib/Profile/StaleProfileMatching.cpp

395–396

Now you can pass just the BinaryContext.

[spupyrev]

• wrapping binary stats into a struct;
• printing matching stats based on strong hashes, where we have high confidence in correctness.

[spupyrev]

a typo

[spupyrev]

another typo

[Amir]

bolt/lib/Profile/StaleProfileMatching.cpp

437

But AllInstrHashes is not used in FlowBlock lookup above?

[spupyrev]

Updated the part computing matching metrics to make it more readable. Let me know if there is still confusion.

[maksfb]

LGTM with a couple of nits. Thanks!

bolt/include/bolt/Core/BinaryContext.h

650 ↗

(On Diff #544098)

654 ↗

(On Diff #544098)

[spupyrev]

nit

bolt/include/bolt/Core/BinaryFunction.h

private:
 
   /// Indicates the type of profile the function is using.
   uint16_t ProfileFlags{PF_NONE};
 
   /// True if the function's input profile data has been inaccurate but has
   /// been adjusted by the profile inference algorithm.
   bool HasInferredProfile{false};
 
+  /// Inference stats:
+  ///   the total number of basic blocks in the profile
+  uint32_t NumStaleBlocks{0};
+  ///   the number matched basic blocks
+  uint32_t NumMatchedBlocks{0};
+  ///   the total count of samples in the profile
+  uint64_t StaleSampleCount{0};
+  ///   the count matched samples
+  uint64_t MatchedSampleCount{0};
+
   /// For functions with mismatched profile we store all call profile
   /// information at a function level (as opposed to tying it to
   /// specific call sites).
   IndirectCallSiteProfile AllCallSites;
 
   /// Score of the function (estimated number of instructions executed,
   /// according to profile data). -1 if the score has not been calculated yet.
   mutable int64_t FunctionScore{-1};
public:
   uint16_t getProfileFlags() const { return ProfileFlags; }
 
   /// Return true if the function's input profile data has been inaccurate but
   /// has been corrected by the profile inference algorithm.
   bool hasInferredProfile() const { return HasInferredProfile; }
 
   void setHasInferredProfile(bool Inferred) { HasInferredProfile = Inferred; }
 
+  uint32_t getNumStaleBlocks() const { return NumStaleBlocks; }
+
+  void setNumStaleBlocks(uint32_t Count) { NumStaleBlocks = Count; }
+
+  uint32_t getNumMatchedBlocks() const { return NumMatchedBlocks; }
+
+  void setNumMatchedBlocks(uint32_t Count) { NumMatchedBlocks = Count; }
+
+  uint64_t getStaleSampleCount() const { return StaleSampleCount; }
+
+  void setStaleSampleCount(uint64_t Count) { StaleSampleCount = Count; }
+
+  uint64_t getMatchedSampleCount() const { return MatchedSampleCount; }
+
+  void setMatchedSampleCount(uint64_t Count) { MatchedSampleCount = Count; }
+
   void addCFIInstruction(uint64_t Offset, MCCFIInstruction &&Inst) {
     assert(!Instructions.empty());
 
     // Fix CFI instructions skipping NOPs. We need to fix this because changing
     // CFI state after a NOP, besides being wrong and inaccurate,  makes it
     // harder for us to recover this information, since we can create empty BBs
     // with NOPs and then reorder it away.
     // We fix this by moving the CFI instruction just before any NOPs.

bolt/lib/Passes/BinaryPasses.cpp

if (NumInferredFunctions) {
     outs() << format("BOLT-INFO: inferred profile for %d (%.2f%% of profiled, "
                      "%.2f%% of stale) functions responsible for %.2f%% samples"
                      " (%zu out of %zu)\n",
                      NumInferredFunctions,
                      100.0 * NumInferredFunctions / NumAllProfiledFunctions,
                      100.0 * NumInferredFunctions / NumAllStaleFunctions,
                      100.0 * InferredSampleCount / TotalSampleCount,
                      InferredSampleCount, TotalSampleCount);
+    uint32_t TotalNumStaleBlocks = 0;
+    uint32_t TotalNumMatchedBlocks = 0;
+    uint64_t TotalStaleSampleCount = 0;
+    uint64_t TotalMatchedSampleCount = 0;
+    for (const BinaryFunction *BF : ProfiledFunctions) {
+      if (!BF->hasInferredProfile())
+        continue;
+      TotalNumStaleBlocks += BF->getNumStaleBlocks();
+      TotalNumMatchedBlocks += BF->getNumMatchedBlocks();
+      TotalStaleSampleCount += BF->getStaleSampleCount();
+      TotalMatchedSampleCount += BF->getMatchedSampleCount();
+    }
+    outs() << format("BOLT-INFO: stale inference matched %.2f%% of basic blocks"
+                     " (%zu out of %zu stale) responsible for %.2f%% samples"
+                     " (%zu out of %zu stale)\n",
+                     100.0 * TotalNumMatchedBlocks / TotalNumStaleBlocks,
+                     TotalNumMatchedBlocks, TotalNumStaleBlocks,
+                     100.0 * TotalMatchedSampleCount / TotalStaleSampleCount,
+                     TotalMatchedSampleCount, TotalStaleSampleCount);
   }
 
   if (const uint64_t NumUnusedObjects = BC.getNumUnusedProfiledObjects()) {
     outs() << "BOLT-INFO: profile for " << NumUnusedObjects
            << " objects was ignored\n";
   }
 
   if (ProfiledFunctions.size() > 10) {

bolt/lib/Profile/StaleProfileMatching.cpp

for (size_t I = 0; I < Blocks.size(); I++) {
       uint16_t OpHash = Hashes[I].OpcodeHash;
       OpHashToBlocks[OpHash].push_back(std::make_pair(Hashes[I], Block));
     }
   }
 
   /// Find the most similar block for a given hash.
   const FlowBlock *matchBlock(BlendedBlockHash BlendedHash) const {
     auto BlockIt = OpHashToBlocks.find(BlendedHash.OpcodeHash);
-    if (BlockIt == OpHashToBlocks.end()) {
+    if (BlockIt == OpHashToBlocks.end())
       return nullptr;
-    }
     FlowBlock *BestBlock = nullptr;
     uint64_t BestDist = std::numeric_limits<uint64_t>::max();
     for (auto It : BlockIt->second) {
       FlowBlock *Block = It.second;
       BlendedBlockHash Hash = It.first;
       uint64_t Dist = Hash.distance(BlendedHash);
       if (BestBlock == nullptr || Dist < BestDist) {
         BestDist = Dist;

 /// is to extract as much information from the stale profile as possible. Here
 /// we assume that each basic block is specified via a hash value computed from
 /// its content and the hashes of the unchanged basic blocks stay the same
 /// across different revisions of the binary.
 /// Whenever there is a count in the profile with the hash corresponding to one
 /// of the basic blocks in the binary, the count is "matched" to the block.
 /// Similarly, if both the source and the target of a count in the profile are
 /// matched to a jump in the binary, the count is recorded in CFG.
-void matchWeightsByHashes(const BinaryFunction::BasicBlockOrderType &BlockOrder,
+void matchWeightsByHashes(BinaryFunction &BF,
+                          const BinaryFunction::BasicBlockOrderType &BlockOrder,
                           const yaml::bolt::BinaryFunctionProfile &YamlBF,
                           FlowFunction &Func) {
   assert(Func.Blocks.size() == BlockOrder.size() + 1);
 
   std::vector<FlowBlock *> Blocks;
   std::vector<BlendedBlockHash> BlendedHashes;
   for (uint64_t I = 0; I < BlockOrder.size(); I++) {
     const BinaryBasicBlock *BB = BlockOrder[I];
if (MatchedBlock != nullptr) {
       LLVM_DEBUG(
           dbgs() << "Couldn't match yaml block with bid = " << YamlBB.Index
                  << " and hash = " << Twine::utohexstr(YamlBB.Hash) << "\n");
     }
   }
 
   // Match jumps from the profile to the jumps from CFG
   std::vector<uint64_t> OutWeight(Func.Blocks.size(), 0);
   std::vector<uint64_t> InWeight(Func.Blocks.size(), 0);
   for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
     for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {
       if (YamlSI.Count == 0)
         continue;
 
       // Try to find the jump for a given (src, dst) pair from the profile and
       // assign the jump weight based on the profile count
       const uint64_t SrcIndex = YamlBB.Index;
for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {
       if (MatchedDstBlock != nullptr)
         InWeight[MatchedDstBlock->Index] += YamlSI.Count;
     }
   }
 
   // Assign block counts based on in-/out- jumps
   for (FlowBlock &Block : Func.Blocks) {
     if (OutWeight[Block.Index] == 0 && InWeight[Block.Index] == 0) {
-      assert(Block.HasUnknownWeight && "unmatched block with positive count");
+      assert(Block.HasUnknownWeight && "unmatched block with a positive count");
       continue;
     }
     Block.HasUnknownWeight = false;
     Block.Weight = std::max(OutWeight[Block.Index], InWeight[Block.Index]);
   }
+
+  // Compute and assign matching stats
+  uint32_t NumStaleBlocks = 0;
+  uint32_t NumMatchedBlocks = 0;
+  uint64_t StaleSampleCount = 0;
+  uint64_t MatchedSampleCount = 0;
+  for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
+    NumStaleBlocks += 1;
+    StaleSampleCount += YamlBB.ExecCount;
+    if (MatchedBlocks.find(YamlBB.Index) != MatchedBlocks.end()) {
+      NumMatchedBlocks += 1;
+      MatchedSampleCount += YamlBB.ExecCount;
+    }
+  }
+  BF.setNumStaleBlocks(NumStaleBlocks);
+  BF.setNumMatchedBlocks(NumMatchedBlocks);
+  BF.setStaleSampleCount(StaleSampleCount);
+  BF.setMatchedSampleCount(MatchedSampleCount);
 }
 
 /// The function finds all blocks that are (i) reachable from the Entry block
 /// and (ii) do not have a path to an exit, and marks all such blocks 'cold'
 /// so that profi does not send any flow to such blocks.
 void preprocessUnreachableBlocks(FlowFunction &Func) {
   const uint64_t NumBlocks = Func.Blocks.size();
 
bool YAMLProfileReader::inferStaleProfile(
 
   const BinaryFunction::BasicBlockOrderType BlockOrder(
       BF.getLayout().block_begin(), BF.getLayout().block_end());
 
   // Create a wrapper flow function to use with the profile inference algorithm
   FlowFunction Func = createFlowFunction(BlockOrder);
 
   // Match as many block/jump counts from the stale profile as possible
-  matchWeightsByHashes(BlockOrder, YamlBF, Func);
+  matchWeightsByHashes(BF, BlockOrder, YamlBF, Func);
 
   // Adjust the flow function by marking unreachable blocks Unlikely so that
   // they don't get any counts assigned
   preprocessUnreachableBlocks(Func);
 
   // Check if profile inference can be applied for the instance
   if (!canApplyInference(Func))
     return false;