aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bolt/include/bolt/Core/HashUtilities.h8
-rw-r--r--bolt/include/bolt/Profile/YAMLProfileReader.h7
-rw-r--r--bolt/include/bolt/Utils/NameResolver.h6
-rw-r--r--bolt/lib/Core/HashUtilities.cpp46
-rw-r--r--bolt/lib/Profile/StaleProfileMatching.cpp103
-rw-r--r--bolt/lib/Profile/YAMLProfileReader.cpp4
-rw-r--r--bolt/test/X86/match-functions-with-calls-as-anchors.test162
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} ]
+...
generated by cgit v1.1 at 2024-10-03 14:55:32 +0000