893 lines · cpp
1//===- bolt/Profile/YAMLProfileReader.cpp - YAML profile de-serializer ----===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "bolt/Profile/YAMLProfileReader.h"10#include "bolt/Core/BinaryBasicBlock.h"11#include "bolt/Core/BinaryFunction.h"12#include "bolt/Passes/MCF.h"13#include "bolt/Profile/ProfileYAMLMapping.h"14#include "bolt/Utils/NameResolver.h"15#include "bolt/Utils/Utils.h"16#include "llvm/ADT/STLExtras.h"17#include "llvm/ADT/edit_distance.h"18#include "llvm/Demangle/Demangle.h"19#include "llvm/MC/MCPseudoProbe.h"20#include "llvm/Support/CommandLine.h"21 22using namespace llvm;23 24namespace opts {25 26extern cl::opt<unsigned> Verbosity;27extern cl::OptionCategory BoltOptCategory;28extern cl::opt<bool> InferStaleProfile;29extern cl::opt<bool> Lite;30 31static cl::opt<unsigned> NameSimilarityFunctionMatchingThreshold(32 "name-similarity-function-matching-threshold",33 cl::desc("Match functions using namespace and edit distance"), cl::init(0),34 cl::Hidden, cl::cat(BoltOptCategory));35 36static llvm::cl::opt<bool>37 IgnoreHash("profile-ignore-hash",38 cl::desc("ignore hash while reading function profile"),39 cl::Hidden, cl::cat(BoltOptCategory));40 41static llvm::cl::opt<bool>42 MatchProfileWithFunctionHash("match-profile-with-function-hash",43 cl::desc("Match profile with function hash"),44 cl::Hidden, cl::cat(BoltOptCategory));45static llvm::cl::opt<bool>46 MatchWithCallGraph("match-with-call-graph",47 cl::desc("Match functions with call graph"), cl::Hidden,48 cl::cat(BoltOptCategory));49 50llvm::cl::opt<bool> ProfileUseDFS("profile-use-dfs",51 cl::desc("use DFS order for YAML profile"),52 cl::Hidden, cl::cat(BoltOptCategory));53 54extern llvm::cl::opt<bool> StaleMatchingWithPseudoProbes;55} // namespace opts56 57namespace llvm {58namespace bolt {59 60YAMLProfileReader::CallGraphMatcher::CallGraphMatcher(61 BinaryContext &BC, yaml::bolt::BinaryProfile &YamlBP,62 ProfileLookupMap &IdToYAMLBF) {63 constructBFCG(BC, YamlBP);64 constructYAMLFCG(YamlBP, IdToYAMLBF);65 computeBFNeighborHashes(BC);66}67 68void YAMLProfileReader::CallGraphMatcher::constructBFCG(69 BinaryContext &BC, yaml::bolt::BinaryProfile &YamlBP) {70 for (BinaryFunction *BF : BC.getAllBinaryFunctions()) {71 for (const BinaryBasicBlock &BB : BF->blocks()) {72 for (const MCInst &Instr : BB) {73 if (!BC.MIB->isCall(Instr))74 continue;75 const MCSymbol *CallSymbol = BC.MIB->getTargetSymbol(Instr);76 if (!CallSymbol)77 continue;78 BinaryData *BD = BC.getBinaryDataByName(CallSymbol->getName());79 if (!BD)80 continue;81 BinaryFunction *CalleeBF = BC.getFunctionForSymbol(BD->getSymbol());82 if (!CalleeBF)83 continue;84 85 BFAdjacencyMap[CalleeBF].insert(BF);86 BFAdjacencyMap[BF].insert(CalleeBF);87 }88 }89 }90}91 92void YAMLProfileReader::CallGraphMatcher::computeBFNeighborHashes(93 BinaryContext &BC) {94 for (BinaryFunction *BF : BC.getAllBinaryFunctions()) {95 auto It = BFAdjacencyMap.find(BF);96 if (It == BFAdjacencyMap.end())97 continue;98 auto &AdjacentBFs = It->second;99 std::string HashStr;100 for (BinaryFunction *BF : AdjacentBFs)101 HashStr += BF->getOneName();102 uint64_t Hash = std::hash<std::string>{}(HashStr);103 NeighborHashToBFs[Hash].push_back(BF);104 }105}106 107void YAMLProfileReader::CallGraphMatcher::constructYAMLFCG(108 yaml::bolt::BinaryProfile &YamlBP, ProfileLookupMap &IdToYAMLBF) {109 110 for (auto &CallerYamlBF : YamlBP.Functions) {111 for (auto &YamlBB : CallerYamlBF.Blocks) {112 for (auto &CallSite : YamlBB.CallSites) {113 auto IdToYAMLBFIt = IdToYAMLBF.find(CallSite.DestId);114 if (IdToYAMLBFIt == IdToYAMLBF.end())115 continue;116 YamlBFAdjacencyMap[&CallerYamlBF].insert(IdToYAMLBFIt->second);117 YamlBFAdjacencyMap[IdToYAMLBFIt->second].insert(&CallerYamlBF);118 }119 }120 }121}122 123bool YAMLProfileReader::isYAML(const StringRef Filename) {124 if (auto MB = MemoryBuffer::getFileOrSTDIN(Filename)) {125 StringRef Buffer = (*MB)->getBuffer();126 return Buffer.starts_with("---\n");127 } else {128 report_error(Filename, MB.getError());129 }130 return false;131}132 133void YAMLProfileReader::buildNameMaps(BinaryContext &BC) {134 auto lookupFunction = [&](StringRef Name) -> BinaryFunction * {135 if (BinaryData *BD = BC.getBinaryDataByName(Name))136 return BC.getFunctionForSymbol(BD->getSymbol());137 return nullptr;138 };139 140 ProfileBFs.reserve(YamlBP.Functions.size());141 142 for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {143 StringRef Name = YamlBF.Name;144 const size_t Pos = Name.find("(*");145 if (Pos != StringRef::npos)146 Name = Name.substr(0, Pos);147 ProfileFunctionNames.insert(Name);148 ProfileBFs.push_back(lookupFunction(Name));149 if (const std::optional<StringRef> CommonName = getLTOCommonName(Name))150 LTOCommonNameMap[*CommonName].push_back(&YamlBF);151 }152 for (auto &[Symbol, BF] : BC.SymbolToFunctionMap) {153 StringRef Name = Symbol->getName();154 if (const std::optional<StringRef> CommonName = getLTOCommonName(Name))155 LTOCommonNameFunctionMap[*CommonName].insert(BF);156 }157}158 159bool YAMLProfileReader::hasLocalsWithFileName() const {160 return llvm::any_of(ProfileFunctionNames.keys(), [](StringRef FuncName) {161 return FuncName.count('/') == 2 && FuncName[0] != '/';162 });163}164 165bool YAMLProfileReader::parseFunctionProfile(166 BinaryFunction &BF, const yaml::bolt::BinaryFunctionProfile &YamlBF) {167 BinaryContext &BC = BF.getBinaryContext();168 169 const bool IsDFSOrder = YamlBP.Header.IsDFSOrder;170 const HashFunction HashFunction = YamlBP.Header.HashFunction;171 bool ProfileMatched = true;172 uint64_t MismatchedBlocks = 0;173 uint64_t MismatchedCalls = 0;174 uint64_t MismatchedEdges = 0;175 176 uint64_t FunctionExecutionCount = 0;177 178 BF.setExecutionCount(YamlBF.ExecCount);179 BF.setExternEntryCount(YamlBF.ExternEntryCount);180 181 uint64_t FuncRawBranchCount = 0;182 for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks)183 for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors)184 FuncRawBranchCount += YamlSI.Count;185 BF.setRawSampleCount(FuncRawBranchCount);186 187 if (BF.empty())188 return true;189 190 if (!opts::IgnoreHash) {191 if (!BF.getHash())192 BF.computeHash(IsDFSOrder, HashFunction);193 if (YamlBF.Hash != BF.getHash()) {194 if (opts::Verbosity >= 1)195 errs() << "BOLT-WARNING: function hash mismatch\n";196 ProfileMatched = false;197 }198 }199 200 if (YamlBF.NumBasicBlocks != BF.size()) {201 if (opts::Verbosity >= 1)202 errs() << "BOLT-WARNING: number of basic blocks mismatch\n";203 ProfileMatched = false;204 }205 206 BinaryFunction::BasicBlockOrderType Order;207 if (IsDFSOrder)208 llvm::copy(BF.dfs(), std::back_inserter(Order));209 else210 llvm::copy(BF.getLayout().blocks(), std::back_inserter(Order));211 212 for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {213 if (YamlBB.Index >= Order.size()) {214 if (opts::Verbosity >= 2)215 errs() << "BOLT-WARNING: index " << YamlBB.Index216 << " is out of bounds\n";217 ++MismatchedBlocks;218 continue;219 }220 221 BinaryBasicBlock &BB = *Order[YamlBB.Index];222 223 // Basic samples profile (without LBR) does not have branches information224 // and needs a special processing.225 if (YamlBP.Header.Flags & BinaryFunction::PF_BASIC) {226 if (!YamlBB.EventCount) {227 BB.setExecutionCount(0);228 continue;229 }230 uint64_t NumSamples = YamlBB.EventCount * 1000;231 if (NormalizeByInsnCount && BB.getNumNonPseudos())232 NumSamples /= BB.getNumNonPseudos();233 else if (NormalizeByCalls)234 NumSamples /= BB.getNumCalls() + 1;235 236 BB.setExecutionCount(NumSamples);237 if (BB.isEntryPoint())238 FunctionExecutionCount += NumSamples;239 continue;240 }241 242 BB.setExecutionCount(YamlBB.ExecCount);243 244 for (const yaml::bolt::CallSiteInfo &YamlCSI : YamlBB.CallSites) {245 BinaryFunction *Callee = YamlProfileToFunction.lookup(YamlCSI.DestId);246 bool IsFunction = Callee ? true : false;247 MCSymbol *CalleeSymbol = nullptr;248 if (IsFunction)249 CalleeSymbol = Callee->getSymbolForEntryID(YamlCSI.EntryDiscriminator);250 251 BF.getAllCallSites().emplace_back(CalleeSymbol, YamlCSI.Count,252 YamlCSI.Mispreds, YamlCSI.Offset);253 254 if (YamlCSI.Offset >= BB.getOriginalSize()) {255 if (opts::Verbosity >= 2)256 errs() << "BOLT-WARNING: offset " << YamlCSI.Offset257 << " out of bounds in block " << BB.getName() << '\n';258 ++MismatchedCalls;259 continue;260 }261 262 MCInst *Instr =263 BF.getInstructionAtOffset(BB.getInputOffset() + YamlCSI.Offset);264 if (!Instr) {265 if (opts::Verbosity >= 2)266 errs() << "BOLT-WARNING: no instruction at offset " << YamlCSI.Offset267 << " in block " << BB.getName() << '\n';268 ++MismatchedCalls;269 continue;270 }271 if (!BC.MIB->isCall(*Instr) && !BC.MIB->isIndirectBranch(*Instr)) {272 if (opts::Verbosity >= 2)273 errs() << "BOLT-WARNING: expected call at offset " << YamlCSI.Offset274 << " in block " << BB.getName() << '\n';275 ++MismatchedCalls;276 continue;277 }278 279 auto setAnnotation = [&](StringRef Name, uint64_t Count) {280 if (BC.MIB->hasAnnotation(*Instr, Name)) {281 if (opts::Verbosity >= 1)282 errs() << "BOLT-WARNING: ignoring duplicate " << Name283 << " info for offset 0x" << Twine::utohexstr(YamlCSI.Offset)284 << " in function " << BF << '\n';285 return;286 }287 BC.MIB->addAnnotation(*Instr, Name, Count);288 };289 290 if (BC.MIB->isIndirectCall(*Instr) || BC.MIB->isIndirectBranch(*Instr)) {291 auto &CSP = BC.MIB->getOrCreateAnnotationAs<IndirectCallSiteProfile>(292 *Instr, "CallProfile");293 CSP.emplace_back(CalleeSymbol, YamlCSI.Count, YamlCSI.Mispreds);294 } else if (BC.MIB->getConditionalTailCall(*Instr)) {295 setAnnotation("CTCTakenCount", YamlCSI.Count);296 setAnnotation("CTCMispredCount", YamlCSI.Mispreds);297 } else {298 setAnnotation("Count", YamlCSI.Count);299 }300 }301 302 for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {303 if (YamlSI.Index >= Order.size()) {304 if (opts::Verbosity >= 1)305 errs() << "BOLT-WARNING: index out of bounds for profiled block\n";306 ++MismatchedEdges;307 continue;308 }309 310 BinaryBasicBlock *ToBB = Order[YamlSI.Index];311 if (!BB.getSuccessor(ToBB->getLabel())) {312 // Allow passthrough blocks.313 BinaryBasicBlock *FTSuccessor = BB.getConditionalSuccessor(false);314 if (FTSuccessor && FTSuccessor->succ_size() == 1 &&315 FTSuccessor->getSuccessor(ToBB->getLabel())) {316 BinaryBasicBlock::BinaryBranchInfo &FTBI =317 FTSuccessor->getBranchInfo(*ToBB);318 FTBI.Count += YamlSI.Count;319 FTBI.MispredictedCount += YamlSI.Mispreds;320 ToBB = FTSuccessor;321 } else {322 if (opts::Verbosity >= 1)323 errs() << "BOLT-WARNING: no successor for block " << BB.getName()324 << " that matches index " << YamlSI.Index << " or block "325 << ToBB->getName() << '\n';326 ++MismatchedEdges;327 continue;328 }329 }330 331 BinaryBasicBlock::BinaryBranchInfo &BI = BB.getBranchInfo(*ToBB);332 BI.Count += YamlSI.Count;333 BI.MispredictedCount += YamlSI.Mispreds;334 }335 }336 337 // If basic block profile wasn't read it should be 0.338 for (BinaryBasicBlock &BB : BF)339 if (BB.getExecutionCount() == BinaryBasicBlock::COUNT_NO_PROFILE)340 BB.setExecutionCount(0);341 342 if (YamlBP.Header.Flags & BinaryFunction::PF_BASIC)343 BF.setExecutionCount(FunctionExecutionCount);344 345 ProfileMatched &= !MismatchedBlocks && !MismatchedCalls && !MismatchedEdges;346 347 if (!ProfileMatched) {348 if (opts::Verbosity >= 1)349 errs() << "BOLT-WARNING: " << MismatchedBlocks << " blocks, "350 << MismatchedCalls << " calls, and " << MismatchedEdges351 << " edges in profile did not match function " << BF << '\n';352 353 if (!opts::InferStaleProfile)354 return false;355 ArrayRef<ProbeMatchSpec> ProbeMatchSpecs;356 auto BFIt = BFToProbeMatchSpecs.find(&BF);357 if (BFIt != BFToProbeMatchSpecs.end())358 ProbeMatchSpecs = BFIt->second;359 ProfileMatched = inferStaleProfile(BF, YamlBF, ProbeMatchSpecs);360 }361 if (ProfileMatched)362 BF.markProfiled(YamlBP.Header.Flags);363 364 return ProfileMatched;365}366 367Error YAMLProfileReader::preprocessProfile(BinaryContext &BC) {368 ErrorOr<std::unique_ptr<MemoryBuffer>> MB =369 MemoryBuffer::getFileOrSTDIN(Filename);370 if (std::error_code EC = MB.getError()) {371 errs() << "ERROR: cannot open " << Filename << ": " << EC.message() << "\n";372 return errorCodeToError(EC);373 }374 yaml::Input YamlInput(MB.get()->getBuffer());375 YamlInput.setAllowUnknownKeys(true);376 377 // Consume YAML file.378 YamlInput >> YamlBP;379 if (YamlInput.error()) {380 errs() << "BOLT-ERROR: syntax error parsing profile in " << Filename381 << " : " << YamlInput.error().message() << '\n';382 return errorCodeToError(YamlInput.error());383 }384 385 // Sanity check.386 if (YamlBP.Header.Version != 1)387 return make_error<StringError>(388 Twine("cannot read profile : unsupported version"),389 inconvertibleErrorCode());390 391 if (YamlBP.Header.EventNames.find(',') != StringRef::npos)392 return make_error<StringError>(393 Twine("multiple events in profile are not supported"),394 inconvertibleErrorCode());395 396 // Match profile to function based on a function name.397 buildNameMaps(BC);398 399 // Preliminary assign function execution count.400 for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs)) {401 if (!BF)402 continue;403 if (!BF->hasProfile()) {404 BF->setExecutionCount(YamlBF.ExecCount);405 } else {406 if (opts::Verbosity >= 1) {407 errs() << "BOLT-WARNING: dropping duplicate profile for " << YamlBF.Name408 << '\n';409 }410 BF = nullptr;411 }412 }413 414 return Error::success();415}416 417bool YAMLProfileReader::profileMatches(418 const yaml::bolt::BinaryFunctionProfile &Profile, const BinaryFunction &BF) {419 if (opts::IgnoreHash)420 return Profile.NumBasicBlocks == BF.size();421 return Profile.Hash == static_cast<uint64_t>(BF.getHash());422}423 424bool YAMLProfileReader::mayHaveProfileData(const BinaryFunction &BF) {425 if (opts::MatchProfileWithFunctionHash || opts::MatchWithCallGraph)426 return true;427 for (StringRef Name : BF.getNames())428 if (ProfileFunctionNames.contains(Name))429 return true;430 for (StringRef Name : BF.getNames()) {431 if (const std::optional<StringRef> CommonName = getLTOCommonName(Name)) {432 if (LTOCommonNameMap.contains(*CommonName))433 return true;434 }435 }436 437 return false;438}439 440size_t YAMLProfileReader::matchWithExactName() {441 size_t MatchedWithExactName = 0;442 // This first pass assigns profiles that match 100% by name and by hash.443 for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs)) {444 if (!BF)445 continue;446 BinaryFunction &Function = *BF;447 // Clear function call count that may have been set while pre-processing448 // the profile.449 Function.setExecutionCount(BinaryFunction::COUNT_NO_PROFILE);450 451 if (profileMatches(YamlBF, Function)) {452 matchProfileToFunction(YamlBF, Function);453 ++MatchedWithExactName;454 }455 }456 return MatchedWithExactName;457}458 459size_t YAMLProfileReader::matchWithHash(BinaryContext &BC) {460 // Iterates through profiled functions to match the first binary function with461 // the same exact hash. Serves to match identical, renamed functions.462 // Collisions are possible where multiple functions share the same exact hash.463 size_t MatchedWithHash = 0;464 if (opts::MatchProfileWithFunctionHash) {465 DenseMap<size_t, BinaryFunction *> StrictHashToBF;466 StrictHashToBF.reserve(BC.getBinaryFunctions().size());467 468 for (auto &[_, BF] : BC.getBinaryFunctions())469 StrictHashToBF[BF.getHash()] = &BF;470 471 for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {472 if (YamlBF.Used)473 continue;474 auto It = StrictHashToBF.find(YamlBF.Hash);475 if (It != StrictHashToBF.end() && !ProfiledFunctions.count(It->second)) {476 BinaryFunction *BF = It->second;477 matchProfileToFunction(YamlBF, *BF);478 ++MatchedWithHash;479 }480 }481 }482 return MatchedWithHash;483}484 485size_t YAMLProfileReader::matchWithLTOCommonName() {486 // This second pass allows name ambiguity for LTO private functions.487 size_t MatchedWithLTOCommonName = 0;488 for (const auto &[CommonName, LTOProfiles] : LTOCommonNameMap) {489 if (!LTOCommonNameFunctionMap.contains(CommonName))490 continue;491 std::unordered_set<BinaryFunction *> &Functions =492 LTOCommonNameFunctionMap[CommonName];493 // Return true if a given profile is matched to one of BinaryFunctions with494 // matching LTO common name.495 auto matchProfile = [&](yaml::bolt::BinaryFunctionProfile *YamlBF) {496 if (YamlBF->Used)497 return false;498 for (BinaryFunction *BF : Functions) {499 if (!ProfiledFunctions.count(BF) && profileMatches(*YamlBF, *BF)) {500 matchProfileToFunction(*YamlBF, *BF);501 ++MatchedWithLTOCommonName;502 return true;503 }504 }505 return false;506 };507 bool ProfileMatched = llvm::any_of(LTOProfiles, matchProfile);508 509 // If there's only one function with a given name, try to match it510 // partially.511 if (!ProfileMatched && LTOProfiles.size() == 1 && Functions.size() == 1 &&512 !LTOProfiles.front()->Used &&513 !ProfiledFunctions.count(*Functions.begin())) {514 matchProfileToFunction(*LTOProfiles.front(), **Functions.begin());515 ++MatchedWithLTOCommonName;516 }517 }518 return MatchedWithLTOCommonName;519}520 521size_t YAMLProfileReader::matchWithCallGraph(BinaryContext &BC) {522 if (!opts::MatchWithCallGraph)523 return 0;524 525 size_t MatchedWithCallGraph = 0;526 CallGraphMatcher CGMatcher(BC, YamlBP, IdToYamLBF);527 528 ItaniumPartialDemangler Demangler;529 auto GetBaseName = [&](std::string &FunctionName) {530 if (Demangler.partialDemangle(FunctionName.c_str()))531 return std::string("");532 size_t BufferSize = 1;533 char *Buffer = static_cast<char *>(std::malloc(BufferSize));534 char *BaseName = Demangler.getFunctionBaseName(Buffer, &BufferSize);535 if (!BaseName) {536 std::free(Buffer);537 return std::string("");538 }539 if (Buffer != BaseName)540 Buffer = BaseName;541 std::string BaseNameStr(Buffer, BufferSize);542 std::free(Buffer);543 return BaseNameStr;544 };545 546 // Matches YAMLBF to BFs with neighbor hashes.547 for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {548 if (YamlBF.Used)549 continue;550 auto AdjacentYamlBFsOpt = CGMatcher.getAdjacentYamlBFs(YamlBF);551 if (!AdjacentYamlBFsOpt)552 continue;553 std::set<yaml::bolt::BinaryFunctionProfile *> AdjacentYamlBFs =554 AdjacentYamlBFsOpt.value();555 std::string AdjacentYamlBFsHashStr;556 for (auto *AdjacentYamlBF : AdjacentYamlBFs)557 AdjacentYamlBFsHashStr += AdjacentYamlBF->Name;558 uint64_t Hash = std::hash<std::string>{}(AdjacentYamlBFsHashStr);559 auto BFsWithSameHashOpt = CGMatcher.getBFsWithNeighborHash(Hash);560 if (!BFsWithSameHashOpt)561 continue;562 std::vector<BinaryFunction *> BFsWithSameHash = BFsWithSameHashOpt.value();563 // Finds the binary function with the longest common prefix to the profiled564 // function and matches.565 BinaryFunction *ClosestBF = nullptr;566 size_t LCP = 0;567 std::string YamlBFBaseName = GetBaseName(YamlBF.Name);568 for (BinaryFunction *BF : BFsWithSameHash) {569 if (ProfiledFunctions.count(BF))570 continue;571 std::string BFName = std::string(BF->getOneName());572 std::string BFBaseName = GetBaseName(BFName);573 size_t PrefixLength = 0;574 size_t N = std::min(YamlBFBaseName.size(), BFBaseName.size());575 for (size_t I = 0; I < N; ++I) {576 if (YamlBFBaseName[I] != BFBaseName[I])577 break;578 ++PrefixLength;579 }580 if (PrefixLength >= LCP) {581 LCP = PrefixLength;582 ClosestBF = BF;583 }584 }585 if (ClosestBF) {586 matchProfileToFunction(YamlBF, *ClosestBF);587 ++MatchedWithCallGraph;588 }589 }590 591 return MatchedWithCallGraph;592}593 594size_t YAMLProfileReader::InlineTreeNodeMapTy::matchInlineTrees(595 const MCPseudoProbeDecoder &Decoder,596 const std::vector<yaml::bolt::InlineTreeNode> &DecodedInlineTree,597 const MCDecodedPseudoProbeInlineTree *Root) {598 // Match inline tree nodes by GUID, checksum, parent, and call site.599 for (const auto &[InlineTreeNodeId, InlineTreeNode] :600 llvm::enumerate(DecodedInlineTree)) {601 uint64_t GUID = InlineTreeNode.GUID;602 uint64_t Hash = InlineTreeNode.Hash;603 uint32_t ParentId = InlineTreeNode.ParentIndexDelta;604 uint32_t CallSiteProbe = InlineTreeNode.CallSiteProbe;605 const MCDecodedPseudoProbeInlineTree *Cur = nullptr;606 if (!InlineTreeNodeId) {607 Cur = Root;608 } else if (const MCDecodedPseudoProbeInlineTree *Parent =609 getInlineTreeNode(ParentId)) {610 for (const MCDecodedPseudoProbeInlineTree &Child :611 Parent->getChildren()) {612 if (Child.Guid == GUID) {613 if (std::get<1>(Child.getInlineSite()) == CallSiteProbe)614 Cur = &Child;615 break;616 }617 }618 }619 // Don't match nodes if the profile is stale (mismatching binary FuncHash620 // and YAML Hash)621 if (Cur && Decoder.getFuncDescForGUID(Cur->Guid)->FuncHash == Hash)622 mapInlineTreeNode(InlineTreeNodeId, Cur);623 }624 return Map.size();625}626 627// Decode index deltas and indirection through \p YamlPD. Return modified copy628// of \p YamlInlineTree with populated decoded fields (GUID, Hash, ParentIndex).629static std::vector<yaml::bolt::InlineTreeNode>630decodeYamlInlineTree(const yaml::bolt::ProfilePseudoProbeDesc &YamlPD,631 std::vector<yaml::bolt::InlineTreeNode> YamlInlineTree) {632 uint32_t ParentId = 0;633 uint32_t PrevGUIDIdx = 0;634 for (yaml::bolt::InlineTreeNode &InlineTreeNode : YamlInlineTree) {635 uint32_t GUIDIdx = InlineTreeNode.GUIDIndex;636 if (GUIDIdx != UINT32_MAX)637 PrevGUIDIdx = GUIDIdx;638 else639 GUIDIdx = PrevGUIDIdx;640 uint32_t HashIdx = YamlPD.GUIDHashIdx[GUIDIdx];641 ParentId += InlineTreeNode.ParentIndexDelta;642 InlineTreeNode.GUID = YamlPD.GUID[GUIDIdx];643 InlineTreeNode.Hash = YamlPD.Hash[HashIdx];644 InlineTreeNode.ParentIndexDelta = ParentId;645 }646 return YamlInlineTree;647}648 649size_t YAMLProfileReader::matchWithPseudoProbes(BinaryContext &BC) {650 if (!opts::StaleMatchingWithPseudoProbes)651 return 0;652 653 const MCPseudoProbeDecoder *Decoder = BC.getPseudoProbeDecoder();654 const yaml::bolt::ProfilePseudoProbeDesc &YamlPD = YamlBP.PseudoProbeDesc;655 656 // Set existing BF->YamlBF match into ProbeMatchSpecs for (local) probe657 // matching.658 assert(Decoder &&659 "If pseudo probes are in use, pseudo probe decoder should exist");660 for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs)) {661 // BF is preliminary name-matched function to YamlBF662 // MatchedBF is final matched function663 BinaryFunction *MatchedBF = YamlProfileToFunction.lookup(YamlBF.Id);664 if (!BF)665 BF = MatchedBF;666 if (!BF)667 continue;668 uint64_t GUID = BF->getGUID();669 if (!GUID)670 continue;671 auto It = TopLevelGUIDToInlineTree.find(GUID);672 if (It == TopLevelGUIDToInlineTree.end())673 continue;674 const MCDecodedPseudoProbeInlineTree *Node = It->second;675 assert(Node && "Malformed TopLevelGUIDToInlineTree");676 auto &MatchSpecs = BFToProbeMatchSpecs[BF];677 auto &InlineTreeMap =678 MatchSpecs.emplace_back(InlineTreeNodeMapTy(), YamlBF).first;679 std::vector<yaml::bolt::InlineTreeNode> ProfileInlineTree =680 decodeYamlInlineTree(YamlPD, YamlBF.InlineTree);681 // Erase unsuccessful match682 if (!InlineTreeMap.matchInlineTrees(*Decoder, ProfileInlineTree, Node))683 MatchSpecs.pop_back();684 }685 686 return 0;687}688 689size_t YAMLProfileReader::matchWithNameSimilarity(BinaryContext &BC) {690 if (opts::NameSimilarityFunctionMatchingThreshold == 0)691 return 0;692 693 size_t MatchedWithNameSimilarity = 0;694 ItaniumPartialDemangler Demangler;695 696 // Demangle and derive namespace from function name.697 auto DemangleName = [&](std::string &FunctionName) {698 StringRef RestoredName = NameResolver::restore(FunctionName);699 return demangle(RestoredName);700 };701 auto DeriveNameSpace = [&](std::string &DemangledName) {702 if (Demangler.partialDemangle(DemangledName.c_str()))703 return std::string("");704 std::vector<char> Buffer(DemangledName.begin(), DemangledName.end());705 size_t BufferSize;706 char *NameSpace =707 Demangler.getFunctionDeclContextName(&Buffer[0], &BufferSize);708 return std::string(NameSpace, BufferSize);709 };710 711 // Maps namespaces to associated function block counts and gets profile712 // function names and namespaces to minimize the number of BFs to process and713 // avoid repeated name demangling/namespace derivation.714 StringMap<std::set<uint32_t>> NamespaceToProfiledBFSizes;715 std::vector<std::string> ProfileBFDemangledNames;716 ProfileBFDemangledNames.reserve(YamlBP.Functions.size());717 std::vector<std::string> ProfiledBFNamespaces;718 ProfiledBFNamespaces.reserve(YamlBP.Functions.size());719 720 for (auto &YamlBF : YamlBP.Functions) {721 std::string YamlBFDemangledName = DemangleName(YamlBF.Name);722 ProfileBFDemangledNames.push_back(YamlBFDemangledName);723 std::string YamlBFNamespace = DeriveNameSpace(YamlBFDemangledName);724 ProfiledBFNamespaces.push_back(YamlBFNamespace);725 NamespaceToProfiledBFSizes[YamlBFNamespace].insert(YamlBF.NumBasicBlocks);726 }727 728 StringMap<std::vector<BinaryFunction *>> NamespaceToBFs;729 730 // Maps namespaces to BFs excluding binary functions with no equal sized731 // profiled functions belonging to the same namespace.732 for (BinaryFunction *BF : BC.getAllBinaryFunctions()) {733 std::string DemangledName = BF->getDemangledName();734 std::string Namespace = DeriveNameSpace(DemangledName);735 736 auto NamespaceToProfiledBFSizesIt =737 NamespaceToProfiledBFSizes.find(Namespace);738 // Skip if there are no ProfileBFs with a given \p Namespace.739 if (NamespaceToProfiledBFSizesIt == NamespaceToProfiledBFSizes.end())740 continue;741 // Skip if there are no ProfileBFs in a given \p Namespace with742 // equal number of blocks.743 if (NamespaceToProfiledBFSizesIt->second.count(BF->size()) == 0)744 continue;745 NamespaceToBFs[Namespace].push_back(BF);746 }747 748 // Iterates through all profiled functions and binary functions belonging to749 // the same namespace and matches based on edit distance threshold.750 assert(YamlBP.Functions.size() == ProfiledBFNamespaces.size() &&751 ProfiledBFNamespaces.size() == ProfileBFDemangledNames.size());752 for (size_t I = 0; I < YamlBP.Functions.size(); ++I) {753 yaml::bolt::BinaryFunctionProfile &YamlBF = YamlBP.Functions[I];754 std::string &YamlBFNamespace = ProfiledBFNamespaces[I];755 if (YamlBF.Used)756 continue;757 // Skip if there are no BFs in a given \p Namespace.758 auto It = NamespaceToBFs.find(YamlBFNamespace);759 if (It == NamespaceToBFs.end())760 continue;761 762 std::string &YamlBFDemangledName = ProfileBFDemangledNames[I];763 std::vector<BinaryFunction *> BFs = It->second;764 unsigned MinEditDistance = UINT_MAX;765 BinaryFunction *ClosestNameBF = nullptr;766 767 // Determines BF the closest to the profiled function, in the768 // same namespace.769 for (BinaryFunction *BF : BFs) {770 if (ProfiledFunctions.count(BF))771 continue;772 if (BF->size() != YamlBF.NumBasicBlocks)773 continue;774 std::string BFDemangledName = BF->getDemangledName();775 unsigned BFEditDistance =776 StringRef(BFDemangledName).edit_distance(YamlBFDemangledName);777 if (BFEditDistance < MinEditDistance) {778 MinEditDistance = BFEditDistance;779 ClosestNameBF = BF;780 }781 }782 783 if (ClosestNameBF &&784 MinEditDistance <= opts::NameSimilarityFunctionMatchingThreshold) {785 matchProfileToFunction(YamlBF, *ClosestNameBF);786 ++MatchedWithNameSimilarity;787 }788 }789 790 return MatchedWithNameSimilarity;791}792 793Error YAMLProfileReader::readProfile(BinaryContext &BC) {794 if (opts::Verbosity >= 1) {795 outs() << "BOLT-INFO: YAML profile with hash: ";796 switch (YamlBP.Header.HashFunction) {797 case HashFunction::StdHash:798 outs() << "std::hash\n";799 break;800 case HashFunction::XXH3:801 outs() << "xxh3\n";802 break;803 }804 }805 YamlProfileToFunction.reserve(YamlBP.Functions.size());806 807 // Computes hash for binary functions.808 if (opts::MatchProfileWithFunctionHash) {809 for (auto &[_, BF] : BC.getBinaryFunctions()) {810 BF.computeHash(YamlBP.Header.IsDFSOrder, YamlBP.Header.HashFunction);811 }812 } else if (!opts::IgnoreHash) {813 for (BinaryFunction *BF : ProfileBFs) {814 if (!BF)815 continue;816 BF->computeHash(YamlBP.Header.IsDFSOrder, YamlBP.Header.HashFunction);817 }818 }819 820 if (opts::StaleMatchingWithPseudoProbes) {821 const MCPseudoProbeDecoder *Decoder = BC.getPseudoProbeDecoder();822 assert(Decoder &&823 "If pseudo probes are in use, pseudo probe decoder should exist");824 for (const MCDecodedPseudoProbeInlineTree &TopLev :825 Decoder->getDummyInlineRoot().getChildren())826 TopLevelGUIDToInlineTree[TopLev.Guid] = &TopLev;827 }828 829 // Map profiled function ids to names.830 for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions)831 IdToYamLBF[YamlBF.Id] = &YamlBF;832 833 const size_t MatchedWithExactName = matchWithExactName();834 const size_t MatchedWithHash = matchWithHash(BC);835 const size_t MatchedWithLTOCommonName = matchWithLTOCommonName();836 const size_t MatchedWithCallGraph = matchWithCallGraph(BC);837 const size_t MatchedWithNameSimilarity = matchWithNameSimilarity(BC);838 [[maybe_unused]] const size_t MatchedWithPseudoProbes =839 matchWithPseudoProbes(BC);840 841 for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs))842 if (!YamlBF.Used && BF && !ProfiledFunctions.count(BF))843 matchProfileToFunction(YamlBF, *BF);844 845 846 for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions)847 if (!YamlBF.Used && opts::Verbosity >= 1)848 errs() << "BOLT-WARNING: profile ignored for function " << YamlBF.Name849 << '\n';850 851 if (opts::Verbosity >= 1) {852 outs() << "BOLT-INFO: matched " << MatchedWithExactName853 << " functions with identical names\n";854 outs() << "BOLT-INFO: matched " << MatchedWithHash855 << " functions with hash\n";856 outs() << "BOLT-INFO: matched " << MatchedWithLTOCommonName857 << " functions with matching LTO common names\n";858 outs() << "BOLT-INFO: matched " << MatchedWithCallGraph859 << " functions with call graph\n";860 outs() << "BOLT-INFO: matched " << MatchedWithNameSimilarity861 << " functions with similar names\n";862 }863 864 // Set for parseFunctionProfile().865 NormalizeByInsnCount = usesEvent("cycles") || usesEvent("instructions");866 NormalizeByCalls = usesEvent("branches");867 uint64_t NumUnused = 0;868 for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {869 if (BinaryFunction *BF = YamlProfileToFunction.lookup(YamlBF.Id))870 parseFunctionProfile(*BF, YamlBF);871 else872 ++NumUnused;873 }874 875 BC.setNumUnusedProfiledObjects(NumUnused);876 877 if (opts::Lite &&878 (opts::MatchProfileWithFunctionHash || opts::MatchWithCallGraph)) {879 for (BinaryFunction *BF : BC.getAllBinaryFunctions())880 if (!BF->hasProfile())881 BF->setIgnored();882 }883 884 return Error::success();885}886 887bool YAMLProfileReader::usesEvent(StringRef Name) const {888 return StringRef(YamlBP.Header.EventNames).contains(Name);889}890 891} // end namespace bolt892} // end namespace llvm893