[BOLT] Match blocks with calls as anchors (#96596)

Added another hash level – call hash – following opcode hash matching
for stale block matching. Call hash strings are the concatenation of the
lexicographically ordered names of each blocks’ called functions. This 
change bolsters block matching in cases where some instructions have
been removed or added but calls remain constant.

Test Plan: added match-functions-with-calls-as-anchors.test.

7 files changed, 317 insertions, 19 deletions

diff --git a/bolt/include/bolt/Core/HashUtilities.h b/bolt/include/bolt/Core/HashUtilities.h
index 53ea110..d12ecbe 100644
--- a/bolt/include/bolt/Core/HashUtilities.h
+++ b/bolt/include/bolt/Core/HashUtilities.h
@@ -16,6 +16,7 @@
 
 #include "bolt/Core/BinaryBasicBlock.h"
 #include "bolt/Core/BinaryContext.h"
+#include "bolt/Profile/ProfileYAMLMapping.h"
 
 namespace llvm {
 namespace bolt {
@@ -35,6 +36,13 @@ std::string hashBlock(BinaryContext &BC, const BinaryBasicBlock &BB,
 
 std::string hashBlockLoose(BinaryContext &BC, const BinaryBasicBlock &BB);
 
+std::string hashBlockCalls(BinaryContext &BC, const BinaryBasicBlock &BB);
+
+std::string
+hashBlockCalls(const DenseMap<uint32_t, yaml::bolt::BinaryFunctionProfile *>
+                   &IdToYamlFunction,
+               const yaml::bolt::BinaryBasicBlockProfile &YamlBB);
+
 } // namespace bolt
 } // namespace llvm
 
diff --git a/bolt/include/bolt/Profile/YAMLProfileReader.h b/bolt/include/bolt/Profile/YAMLProfileReader.h
index 582546a..502a1ad 100644
--- a/bolt/include/bolt/Profile/YAMLProfileReader.h
+++ b/bolt/include/bolt/Profile/YAMLProfileReader.h
@@ -40,6 +40,9 @@ public:
   /// Check if the file contains YAML.
   static bool isYAML(StringRef Filename);
 
+  using ProfileLookupMap =
+      DenseMap<uint32_t, yaml::bolt::BinaryFunctionProfile *>;
+
 private:
   /// Adjustments for basic samples profiles (without LBR).
   bool NormalizeByInsnCount{false};
@@ -56,6 +59,10 @@ private:
   /// is attributed.
   FunctionSet ProfiledFunctions;
 
+  /// Maps profiled function id to function, for function matching with calls as
+  /// anchors.
+  ProfileLookupMap IdToYamLBF;
+
   /// For LTO symbol resolution.
   /// Map a common LTO prefix to a list of YAML profiles matching the prefix.
   StringMap<std::vector<yaml::bolt::BinaryFunctionProfile *>> LTOCommonNameMap;
diff --git a/bolt/include/bolt/Utils/NameResolver.h b/bolt/include/bolt/Utils/NameResolver.h
index ccffa56..9719ce1 100644
--- a/bolt/include/bolt/Utils/NameResolver.h
+++ b/bolt/include/bolt/Utils/NameResolver.h
@@ -61,6 +61,12 @@ public:
     std::tie(LHS, RHS) = UniqueName.split(Sep);
     return (LHS + Suffix + Twine(Sep) + RHS).str();
   }
+
+  // Drops the suffix that describes the function's number of names.
+  static StringRef dropNumNames(StringRef Name) {
+    const size_t Pos = Name.find("(*");
+    return Pos != StringRef::npos ? Name.substr(0, Pos) : Name;
+  }
 };
 
 } // namespace bolt
diff --git a/bolt/lib/Core/HashUtilities.cpp b/bolt/lib/Core/HashUtilities.cpp
index c4c67bd..dfbbdb8 100644
--- a/bolt/lib/Core/HashUtilities.cpp
+++ b/bolt/lib/Core/HashUtilities.cpp
@@ -12,6 +12,7 @@
 
 #include "bolt/Core/HashUtilities.h"
 #include "bolt/Core/BinaryContext.h"
+#include "bolt/Utils/NameResolver.h"
 #include "llvm/MC/MCInstPrinter.h"
 
 namespace llvm {
@@ -155,5 +156,50 @@ std::string hashBlockLoose(BinaryContext &BC, const BinaryBasicBlock &BB) {
   return HashString;
 }
 
+/// An even looser hash level relative to $ hashBlockLoose to use with stale
+/// profile matching, composed of the names of a block's called functions in
+/// lexicographic order.
+std::string hashBlockCalls(BinaryContext &BC, const BinaryBasicBlock &BB) {
+  // The hash is computed by creating a string of all lexicographically ordered
+  // called function names.
+  std::vector<std::string> FunctionNames;
+  for (const MCInst &Instr : BB) {
+    // Skip non-call instructions.
+    if (!BC.MIB->isCall(Instr))
+      continue;
+    const MCSymbol *CallSymbol = BC.MIB->getTargetSymbol(Instr);
+    if (!CallSymbol)
+      continue;
+    FunctionNames.push_back(std::string(CallSymbol->getName()));
+  }
+  std::sort(FunctionNames.begin(), FunctionNames.end());
+  std::string HashString;
+  for (const std::string &FunctionName : FunctionNames)
+    HashString.append(FunctionName);
+
+  return HashString;
+}
+
+/// The same as the $hashBlockCalls function, but for profiled functions.
+std::string
+hashBlockCalls(const DenseMap<uint32_t, yaml::bolt::BinaryFunctionProfile *>
+                   &IdToYamlFunction,
+               const yaml::bolt::BinaryBasicBlockProfile &YamlBB) {
+  std::vector<std::string> FunctionNames;
+  for (const yaml::bolt::CallSiteInfo &CallSiteInfo : YamlBB.CallSites) {
+    auto It = IdToYamlFunction.find(CallSiteInfo.DestId);
+    if (It == IdToYamlFunction.end())
+      continue;
+    StringRef Name = NameResolver::dropNumNames(It->second->Name);
+    FunctionNames.push_back(std::string(Name));
+  }
+  std::sort(FunctionNames.begin(), FunctionNames.end());
+  std::string HashString;
+  for (const std::string &FunctionName : FunctionNames)
+    HashString.append(FunctionName);
+
+  return HashString;
+}
+
 } // namespace bolt
 } // namespace llvm
diff --git a/bolt/lib/Profile/StaleProfileMatching.cpp b/bolt/lib/Profile/StaleProfileMatching.cpp
index e473beb..cd6e96f 100644
--- a/bolt/lib/Profile/StaleProfileMatching.cpp
+++ b/bolt/lib/Profile/StaleProfileMatching.cpp
@@ -193,18 +193,43 @@ class StaleMatcher {
 public:
   /// Initialize stale matcher.
   void init(const std::vector<FlowBlock *> &Blocks,
-            const std::vector<BlendedBlockHash> &Hashes) {
+            const std::vector<BlendedBlockHash> &Hashes,
+            const std::vector<uint64_t> &CallHashes) {
     assert(Blocks.size() == Hashes.size() &&
+           Hashes.size() == CallHashes.size() &&
            "incorrect matcher initialization");
     for (size_t I = 0; I < Blocks.size(); I++) {
       FlowBlock *Block = Blocks[I];
       uint16_t OpHash = Hashes[I].OpcodeHash;
       OpHashToBlocks[OpHash].push_back(std::make_pair(Hashes[I], Block));
+      if (CallHashes[I])
+        CallHashToBlocks[CallHashes[I]].push_back(
+            std::make_pair(Hashes[I], Block));
     }
   }
 
   /// Find the most similar block for a given hash.
-  const FlowBlock *matchBlock(BlendedBlockHash BlendedHash) const {
+  const FlowBlock *matchBlock(BlendedBlockHash BlendedHash,
+                              uint64_t CallHash) const {
+    const FlowBlock *BestBlock = matchWithOpcodes(BlendedHash);
+    return BestBlock ? BestBlock : matchWithCalls(BlendedHash, CallHash);
+  }
+
+  /// Returns true if the two basic blocks (in the binary and in the profile)
+  /// corresponding to the given hashes are matched to each other with a high
+  /// confidence.
+  static bool isHighConfidenceMatch(BlendedBlockHash Hash1,
+                                    BlendedBlockHash Hash2) {
+    return Hash1.InstrHash == Hash2.InstrHash;
+  }
+
+private:
+  using HashBlockPairType = std::pair<BlendedBlockHash, FlowBlock *>;
+  std::unordered_map<uint16_t, std::vector<HashBlockPairType>> OpHashToBlocks;
+  std::unordered_map<uint64_t, std::vector<HashBlockPairType>> CallHashToBlocks;
+
+  // Uses OpcodeHash to find the most similar block for a given hash.
+  const FlowBlock *matchWithOpcodes(BlendedBlockHash BlendedHash) const {
     auto BlockIt = OpHashToBlocks.find(BlendedHash.OpcodeHash);
     if (BlockIt == OpHashToBlocks.end())
       return nullptr;
@@ -220,17 +245,27 @@ public:
     return BestBlock;
   }
 
-  /// Returns true if the two basic blocks (in the binary and in the profile)
-  /// corresponding to the given hashes are matched to each other with a high
-  /// confidence.
-  static bool isHighConfidenceMatch(BlendedBlockHash Hash1,
-                                    BlendedBlockHash Hash2) {
-    return Hash1.InstrHash == Hash2.InstrHash;
+  // Uses CallHash to find the most similar block for a given hash.
+  const FlowBlock *matchWithCalls(BlendedBlockHash BlendedHash,
+                                  uint64_t CallHash) const {
+    if (!CallHash)
+      return nullptr;
+    auto BlockIt = CallHashToBlocks.find(CallHash);
+    if (BlockIt == CallHashToBlocks.end())
+      return nullptr;
+    FlowBlock *BestBlock = nullptr;
+    uint64_t BestDist = std::numeric_limits<uint64_t>::max();
+    for (const auto &[Hash, Block] : BlockIt->second) {
+      uint64_t Dist = Hash.OpcodeHash > BlendedHash.OpcodeHash
+                          ? Hash.OpcodeHash - BlendedHash.OpcodeHash
+                          : BlendedHash.OpcodeHash - Hash.OpcodeHash;
+      if (BestBlock == nullptr || Dist < BestDist) {
+        BestDist = Dist;
+        BestBlock = Block;
+      }
+    }
+    return BestBlock;
   }
-
-private:
-  using HashBlockPairType = std::pair<BlendedBlockHash, FlowBlock *>;
-  std::unordered_map<uint16_t, std::vector<HashBlockPairType>> OpHashToBlocks;
 };
 
 void BinaryFunction::computeBlockHashes(HashFunction HashFunction) const {
@@ -412,16 +447,34 @@ createFlowFunction(const BinaryFunction::BasicBlockOrderType &BlockOrder) {
 /// 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.
-size_t matchWeightsByHashes(
-    BinaryContext &BC, const BinaryFunction::BasicBlockOrderType &BlockOrder,
-    const yaml::bolt::BinaryFunctionProfile &YamlBF, FlowFunction &Func) {
+size_t
+matchWeightsByHashes(BinaryContext &BC,
+                     const BinaryFunction::BasicBlockOrderType &BlockOrder,
+                     const yaml::bolt::BinaryFunctionProfile &YamlBF,
+                     FlowFunction &Func, HashFunction HashFunction,
+                     YAMLProfileReader::ProfileLookupMap &IdToYamlBF) {
+
   assert(Func.Blocks.size() == BlockOrder.size() + 2);
 
+  std::vector<uint64_t> CallHashes;
   std::vector<FlowBlock *> Blocks;
   std::vector<BlendedBlockHash> BlendedHashes;
   for (uint64_t I = 0; I < BlockOrder.size(); I++) {
     const BinaryBasicBlock *BB = BlockOrder[I];
     assert(BB->getHash() != 0 && "empty hash of BinaryBasicBlock");
+
+    std::string CallHashStr = hashBlockCalls(BC, *BB);
+    if (CallHashStr.empty()) {
+      CallHashes.push_back(0);
+    } else {
+      if (HashFunction == HashFunction::StdHash)
+        CallHashes.push_back(std::hash<std::string>{}(CallHashStr));
+      else if (HashFunction == HashFunction::XXH3)
+        CallHashes.push_back(llvm::xxh3_64bits(CallHashStr));
+      else
+        llvm_unreachable("Unhandled HashFunction");
+    }
+
     Blocks.push_back(&Func.Blocks[I + 1]);
     BlendedBlockHash BlendedHash(BB->getHash());
     BlendedHashes.push_back(BlendedHash);
@@ -429,7 +482,7 @@ size_t matchWeightsByHashes(
                       << Twine::utohexstr(BB->getHash()) << "\n");
   }
   StaleMatcher Matcher;
-  Matcher.init(Blocks, BlendedHashes);
+  Matcher.init(Blocks, BlendedHashes, CallHashes);
 
   // Index in yaml profile => corresponding (matched) block
   DenseMap<uint64_t, const FlowBlock *> MatchedBlocks;
@@ -437,8 +490,19 @@ size_t matchWeightsByHashes(
   for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
     assert(YamlBB.Hash != 0 && "empty hash of BinaryBasicBlockProfile");
     BlendedBlockHash YamlHash(YamlBB.Hash);
-    const FlowBlock *MatchedBlock = Matcher.matchBlock(YamlHash);
-    // Always match the entry block.
+
+    const FlowBlock *MatchedBlock = nullptr;
+    std::string CallHashStr = hashBlockCalls(IdToYamlBF, YamlBB);
+    uint64_t CallHash = 0;
+    if (!CallHashStr.empty()) {
+      if (HashFunction == HashFunction::StdHash)
+        CallHash = std::hash<std::string>{}(CallHashStr);
+      else if (HashFunction == HashFunction::XXH3)
+        CallHash = llvm::xxh3_64bits(CallHashStr);
+      else
+        llvm_unreachable("Unhandled HashFunction");
+    }
+    MatchedBlock = Matcher.matchBlock(YamlHash, CallHash);
     if (MatchedBlock == nullptr && YamlBB.Index == 0)
       MatchedBlock = Blocks[0];
     if (MatchedBlock != nullptr) {
@@ -763,7 +827,8 @@ bool YAMLProfileReader::inferStaleProfile(
 
   // Match as many block/jump counts from the stale profile as possible
   size_t MatchedBlocks =
-      matchWeightsByHashes(BF.getBinaryContext(), BlockOrder, YamlBF, Func);
+      matchWeightsByHashes(BF.getBinaryContext(), BlockOrder, YamlBF, Func,
+                           YamlBP.Header.HashFunction, IdToYamLBF);
 
   // Adjust the flow function by marking unreachable blocks Unlikely so that
   // they don't get any counts assigned.
diff --git a/bolt/lib/Profile/YAMLProfileReader.cpp b/bolt/lib/Profile/YAMLProfileReader.cpp
index 3abc034..d9a6998 100644
--- a/bolt/lib/Profile/YAMLProfileReader.cpp
+++ b/bolt/lib/Profile/YAMLProfileReader.cpp
@@ -611,6 +611,10 @@ Error YAMLProfileReader::readProfile(BinaryContext &BC) {
   NormalizeByInsnCount = usesEvent("cycles") || usesEvent("instructions");
   NormalizeByCalls = usesEvent("branches");
 
+  // Map profiled function ids to names.
+  for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions)
+    IdToYamLBF[YamlBF.Id] = &YamlBF;
+
   uint64_t NumUnused = 0;
   for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {
     if (YamlBF.Id >= YamlProfileToFunction.size()) {
diff --git a/bolt/test/X86/match-functions-with-calls-as-anchors.test b/bolt/test/X86/match-functions-with-calls-as-anchors.test
new file mode 100644
index 0000000..7fef128
--- /dev/null
+++ b/bolt/test/X86/match-functions-with-calls-as-anchors.test
@@ -0,0 +1,162 @@
+## Tests blocks matching by called function names in inferStaleProfile.
+
+# REQUIRES: system-linux
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %t/main.s -o %t.o
+# RUN: %clang %cflags %t.o -o %t.exe -Wl,-q -nostdlib
+# RUN: llvm-bolt %t.exe -o %t.out --data %t/yaml --profile-ignore-hash -v=1 \
+# RUN:   --dyno-stats --print-cfg --infer-stale-profile=1 --debug 2>&1 | FileCheck %s
+
+# CHECK: BOLT-INFO: applying profile inference for "qux"
+# CHECK: Matched yaml block (bid = 1) with hash 4 to BB (index = 0) with hash 314e1bc10000
+# CHECK:  loose match
+
+# CHECK: BOLT-INFO: applying profile inference for "fred"
+# CHECK: Matched yaml block (bid = 1) with hash 5 to BB (index = 0) with hash 7541bc10000
+# CHECK:  loose match
+
+#--- main.s
+.globl  foo                         # -- Begin function foo
+  .p2align        4, 0x90
+  .type   foo,@function
+foo:                                # @foo
+# %bb.0:
+  pushq   %rbp
+  movq    %rsp, %rbp
+  popq    %rbp
+  retq
+.Lfunc_end0:
+  .size   foo, .Lfunc_end0-foo
+                                      # -- End function
+  .globl  bar                         # -- Begin function bar
+  .p2align        4, 0x90
+  .type   bar,@function
+bar:                                # @bar
+# %bb.0:
+  pushq   %rbp
+  movq    %rsp, %rbp
+  popq    %rbp
+  retq
+.Lfunc_end1:
+  .size   bar, .Lfunc_end1-bar
+                                      # -- End function
+  .globl  qux                         # -- Begin function qux
+  .p2align        4, 0x90
+  .type   qux,@function
+qux:                                # @qux
+# %bb.0:
+  pushq   %rbp
+  movq    %rsp, %rbp
+  callq   foo
+  callq   bar
+  popq    %rbp
+  retq
+.Lfunc_end2:
+  .size   qux, .Lfunc_end2-qux
+                                      # -- End function
+  .globl  fred                        # -- Begin function fred
+  .p2align        4, 0x90
+  .type   fred,@function
+fred:                               # @fred
+# %bb.0:
+  pushq   %rbp
+  movq    %rsp, %rbp
+  callq   foo
+  callq   qux
+  callq   bar
+  callq   bar
+  callq   foo
+  popq    %rbp
+  retq
+.Lfunc_end3:
+  .size   fred, .Lfunc_end3-fred
+                                          # -- End function
+  .globl  main                            # -- Begin function main
+  .p2align        4, 0x90
+  .type   main,@function
+main:                                   # @main
+# %bb.0:
+  pushq   %rbp
+  movq    %rsp, %rbp
+  xorl    %eax, %eax
+  popq    %rbp
+  retq
+.Lfunc_end4:
+  .size   main, .Lfunc_end4-main
+                                  # -- End function
+  .addrsig
+  .addrsig_sym foo
+  .addrsig_sym bar
+  .addrsig_sym qux
+
+#--- yaml
+---
+header:
+  profile-version: 1
+  binary-name:     'match-functions-with-calls-as-anchors.s.tmp.exe'
+  binary-build-id: '<unknown>'
+  profile-flags:   [ lbr ]
+  profile-origin:  branch profile reader
+  profile-events:  ''
+  dfs-order:       false
+  hash-func:       xxh3
+functions:
+  - name:            main
+    fid:             0
+    hash:            0x0000000000000001
+    exec:            1
+    nblocks:         6
+    blocks:
+      - bid:             1
+        hash:            0x0000000000000001
+        insns:           1
+        succ:            [ { bid: 3, cnt: 1} ]
+  - name:            foo
+    fid:             1
+    hash:            0x0000000000000002
+    exec:            1
+    nblocks:         6
+    blocks:
+      - bid:             1
+        hash:            0x0000000000000002
+        insns:           1
+        succ:            [ { bid: 3, cnt: 1} ]
+
+  - name:            bar
+    fid:             2
+    hash:            0x0000000000000003
+    exec:            1
+    nblocks:         6
+    blocks:
+      - bid:             1
+        hash:            0x0000000000000003
+        insns:           1
+        succ:            [ { bid: 3, cnt: 1} ]
+  - name:            qux
+    fid:             3
+    hash:            0x0000000000000004
+    exec:            4
+    nblocks:         6
+    blocks:
+      - bid:             1
+        hash:            0x0000000000000004
+        insns:           1
+        succ:            [ { bid: 3, cnt: 1} ]
+        calls:           [ { off : 0, fid : 1, cnt : 0},
+                           { off : 0, fid : 2, cnt : 0} ]
+  - name:            fred
+    fid:             4
+    hash:            0x0000000000000005
+    exec:            1
+    nblocks:         6
+    blocks:
+      - bid:             1
+        hash:            0x0000000000000005
+        insns:           1
+        succ:            [ { bid: 3, cnt: 1} ]
+        calls:           [ { off : 0, fid : 3, cnt : 0},
+                           { off : 0, fid : 1, cnt : 0},
+                           { off : 0, fid : 2, cnt : 0},
+                           { off : 0, fid : 1, cnt : 0},
+                           { off : 0, fid : 2, cnt : 0} ]
+...