445 lines · cpp
1//===- bolt/Profile/YAMLProfileWriter.cpp - YAML profile 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/YAMLProfileWriter.h"10#include "bolt/Core/BinaryBasicBlock.h"11#include "bolt/Core/BinaryFunction.h"12#include "bolt/Profile/BoltAddressTranslation.h"13#include "bolt/Profile/DataAggregator.h"14#include "bolt/Profile/ProfileReaderBase.h"15#include "bolt/Rewrite/RewriteInstance.h"16#include "bolt/Utils/CommandLineOpts.h"17#include "llvm/MC/MCPseudoProbe.h"18#include "llvm/Support/CommandLine.h"19#include "llvm/Support/FileSystem.h"20#include "llvm/Support/raw_ostream.h"21 22#undef DEBUG_TYPE23#define DEBUG_TYPE "bolt-prof"24 25namespace opts {26using namespace llvm;27extern cl::opt<bool> ProfileUseDFS;28cl::opt<bool> ProfileWritePseudoProbes(29 "profile-write-pseudo-probes",30 cl::desc("Use pseudo probes in profile generation"), cl::Hidden,31 cl::cat(BoltOptCategory));32} // namespace opts33 34namespace llvm {35namespace bolt {36 37const BinaryFunction *YAMLProfileWriter::setCSIDestination(38 const BinaryContext &BC, yaml::bolt::CallSiteInfo &CSI,39 const MCSymbol *Symbol, const BoltAddressTranslation *BAT,40 uint32_t Offset) {41 CSI.DestId = 0; // designated for unknown functions42 CSI.EntryDiscriminator = 0;43 44 if (Symbol) {45 uint64_t EntryID = 0;46 if (const BinaryFunction *Callee =47 BC.getFunctionForSymbol(Symbol, &EntryID)) {48 if (BAT && BAT->isBATFunction(Callee->getAddress()))49 std::tie(Callee, EntryID) = BAT->translateSymbol(BC, *Symbol, Offset);50 else if (const BinaryBasicBlock *BB =51 Callee->getBasicBlockContainingOffset(Offset))52 BC.getFunctionForSymbol(Callee->getSecondaryEntryPointSymbol(*BB),53 &EntryID);54 CSI.DestId = Callee->getFunctionNumber();55 CSI.EntryDiscriminator = EntryID;56 return Callee;57 }58 }59 return nullptr;60}61 62std::vector<YAMLProfileWriter::InlineTreeNode>63YAMLProfileWriter::collectInlineTree(64 const MCPseudoProbeDecoder &Decoder,65 const MCDecodedPseudoProbeInlineTree &Root) {66 auto getHash = [&](const MCDecodedPseudoProbeInlineTree &Node) {67 return Decoder.getFuncDescForGUID(Node.Guid)->FuncHash;68 };69 std::vector<InlineTreeNode> InlineTree(70 {InlineTreeNode{&Root, Root.Guid, getHash(Root), 0, 0}});71 uint32_t ParentId = 0;72 while (ParentId != InlineTree.size()) {73 const MCDecodedPseudoProbeInlineTree *Cur = InlineTree[ParentId].InlineTree;74 for (const MCDecodedPseudoProbeInlineTree &Child : Cur->getChildren())75 InlineTree.emplace_back(76 InlineTreeNode{&Child, Child.Guid, getHash(Child), ParentId,77 std::get<1>(Child.getInlineSite())});78 ++ParentId;79 }80 81 return InlineTree;82}83 84std::tuple<yaml::bolt::ProfilePseudoProbeDesc,85 YAMLProfileWriter::InlineTreeDesc>86YAMLProfileWriter::convertPseudoProbeDesc(const MCPseudoProbeDecoder &Decoder) {87 yaml::bolt::ProfilePseudoProbeDesc Desc;88 InlineTreeDesc InlineTree;89 90 for (const MCDecodedPseudoProbeInlineTree &TopLev :91 Decoder.getDummyInlineRoot().getChildren())92 InlineTree.TopLevelGUIDToInlineTree[TopLev.Guid] = &TopLev;93 94 for (const auto &FuncDesc : Decoder.getGUID2FuncDescMap())95 ++InlineTree.HashIdxMap[FuncDesc.FuncHash];96 97 InlineTree.GUIDIdxMap.reserve(Decoder.getGUID2FuncDescMap().size());98 for (const auto &Node : Decoder.getInlineTreeVec())99 ++InlineTree.GUIDIdxMap[Node.Guid];100 101 std::vector<std::pair<uint32_t, uint64_t>> GUIDFreqVec;102 GUIDFreqVec.reserve(InlineTree.GUIDIdxMap.size());103 for (const auto [GUID, Cnt] : InlineTree.GUIDIdxMap)104 GUIDFreqVec.emplace_back(Cnt, GUID);105 llvm::sort(GUIDFreqVec);106 107 std::vector<std::pair<uint32_t, uint64_t>> HashFreqVec;108 HashFreqVec.reserve(InlineTree.HashIdxMap.size());109 for (const auto [Hash, Cnt] : InlineTree.HashIdxMap)110 HashFreqVec.emplace_back(Cnt, Hash);111 llvm::sort(HashFreqVec);112 113 uint32_t Index = 0;114 Desc.Hash.reserve(HashFreqVec.size());115 for (uint64_t Hash : llvm::make_second_range(llvm::reverse(HashFreqVec))) {116 Desc.Hash.emplace_back(Hash);117 InlineTree.HashIdxMap[Hash] = Index++;118 }119 120 Index = 0;121 Desc.GUID.reserve(GUIDFreqVec.size());122 for (uint64_t GUID : llvm::make_second_range(llvm::reverse(GUIDFreqVec))) {123 Desc.GUID.emplace_back(GUID);124 InlineTree.GUIDIdxMap[GUID] = Index++;125 uint64_t Hash = Decoder.getFuncDescForGUID(GUID)->FuncHash;126 Desc.GUIDHashIdx.emplace_back(InlineTree.HashIdxMap[Hash]);127 }128 129 return {Desc, InlineTree};130}131 132void YAMLProfileWriter::BlockProbeCtx::addBlockProbe(133 const InlineTreeMapTy &Map, const MCDecodedPseudoProbe &Probe,134 uint32_t ProbeOffset) {135 auto It = Map.find(Probe.getInlineTreeNode());136 if (It == Map.end())137 return;138 auto NodeId = It->second;139 uint32_t Index = Probe.getIndex();140 if (Probe.isCall())141 CallProbes[ProbeOffset] =142 Call{Index, NodeId, Probe.isIndirectCall(), false};143 else144 NodeToProbes[NodeId].emplace_back(Index);145}146 147void YAMLProfileWriter::BlockProbeCtx::finalize(148 yaml::bolt::BinaryBasicBlockProfile &YamlBB) {149 // Hash block probes by vector150 struct ProbeHasher {151 size_t operator()(const ArrayRef<uint64_t> Probes) const {152 return llvm::hash_combine_range(Probes);153 }154 };155 156 // Check identical block probes and merge them157 std::unordered_map<std::vector<uint64_t>, std::vector<uint32_t>, ProbeHasher>158 ProbesToNodes;159 for (auto &[NodeId, Probes] : NodeToProbes) {160 llvm::sort(Probes);161 ProbesToNodes[Probes].emplace_back(NodeId);162 }163 for (auto &[Probes, Nodes] : ProbesToNodes) {164 llvm::sort(Nodes);165 YamlBB.PseudoProbes.emplace_back(166 yaml::bolt::PseudoProbeInfo{Probes, Nodes});167 }168 for (yaml::bolt::CallSiteInfo &CSI : YamlBB.CallSites) {169 auto It = CallProbes.find(CSI.Offset);170 if (It == CallProbes.end())171 continue;172 Call &Probe = It->second;173 CSI.Probe = Probe.Id;174 CSI.InlineTreeNode = Probe.Node;175 CSI.Indirect = Probe.Indirect;176 Probe.Used = true;177 }178 for (const auto &[Offset, Probe] : CallProbes) {179 if (Probe.Used)180 continue;181 yaml::bolt::CallSiteInfo CSI;182 CSI.Offset = Offset;183 CSI.Probe = Probe.Id;184 CSI.InlineTreeNode = Probe.Node;185 CSI.Indirect = Probe.Indirect;186 YamlBB.CallSites.emplace_back(CSI);187 }188}189 190std::tuple<std::vector<yaml::bolt::InlineTreeNode>,191 YAMLProfileWriter::InlineTreeMapTy>192YAMLProfileWriter::convertBFInlineTree(const MCPseudoProbeDecoder &Decoder,193 const InlineTreeDesc &InlineTree,194 uint64_t GUID) {195 DenseMap<const MCDecodedPseudoProbeInlineTree *, uint32_t> InlineTreeNodeId;196 std::vector<yaml::bolt::InlineTreeNode> YamlInlineTree;197 auto It = InlineTree.TopLevelGUIDToInlineTree.find(GUID);198 if (It == InlineTree.TopLevelGUIDToInlineTree.end())199 return {YamlInlineTree, InlineTreeNodeId};200 const MCDecodedPseudoProbeInlineTree *Root = It->second;201 assert(Root && "Malformed TopLevelGUIDToInlineTree");202 uint32_t Index = 0;203 uint32_t PrevParent = 0;204 uint32_t PrevGUIDIdx = 0;205 for (const auto &Node : collectInlineTree(Decoder, *Root)) {206 InlineTreeNodeId[Node.InlineTree] = Index++;207 auto GUIDIdxIt = InlineTree.GUIDIdxMap.find(Node.GUID);208 assert(GUIDIdxIt != InlineTree.GUIDIdxMap.end() && "Malformed GUIDIdxMap");209 uint32_t GUIDIdx = GUIDIdxIt->second;210 if (GUIDIdx == PrevGUIDIdx)211 GUIDIdx = UINT32_MAX;212 else213 PrevGUIDIdx = GUIDIdx;214 YamlInlineTree.emplace_back(yaml::bolt::InlineTreeNode{215 Node.ParentId - PrevParent, Node.InlineSite, GUIDIdx, 0, 0});216 PrevParent = Node.ParentId;217 }218 return {YamlInlineTree, InlineTreeNodeId};219}220 221yaml::bolt::BinaryFunctionProfile222YAMLProfileWriter::convert(const BinaryFunction &BF, bool UseDFS,223 const InlineTreeDesc &InlineTree,224 const BoltAddressTranslation *BAT) {225 yaml::bolt::BinaryFunctionProfile YamlBF;226 const BinaryContext &BC = BF.getBinaryContext();227 const MCPseudoProbeDecoder *PseudoProbeDecoder =228 opts::ProfileWritePseudoProbes ? BC.getPseudoProbeDecoder() : nullptr;229 230 const uint16_t LBRProfile = BF.getProfileFlags() & BinaryFunction::PF_BRANCH;231 232 // Prepare function and block hashes233 BF.computeHash(UseDFS);234 BF.computeBlockHashes();235 236 YamlBF.Name = DataAggregator::getLocationName(BF, BAT);237 YamlBF.Id = BF.getFunctionNumber();238 YamlBF.Hash = BF.getHash();239 YamlBF.NumBasicBlocks = BF.size();240 YamlBF.ExecCount = BF.getKnownExecutionCount();241 YamlBF.ExternEntryCount = BF.getExternEntryCount();242 DenseMap<const MCDecodedPseudoProbeInlineTree *, uint32_t> InlineTreeNodeId;243 if (PseudoProbeDecoder && BF.getGUID()) {244 std::tie(YamlBF.InlineTree, InlineTreeNodeId) =245 convertBFInlineTree(*PseudoProbeDecoder, InlineTree, BF.getGUID());246 }247 248 BinaryFunction::BasicBlockOrderType Order;249 llvm::copy(UseDFS ? BF.dfs() : BF.getLayout().blocks(),250 std::back_inserter(Order));251 252 const FunctionLayout Layout = BF.getLayout();253 Layout.updateLayoutIndices(Order);254 255 for (const BinaryBasicBlock *BB : Order) {256 yaml::bolt::BinaryBasicBlockProfile YamlBB;257 YamlBB.Index = BB->getLayoutIndex();258 YamlBB.NumInstructions = BB->getNumNonPseudos();259 YamlBB.Hash = BB->getHash();260 261 if (!LBRProfile) {262 YamlBB.EventCount = BB->getKnownExecutionCount();263 if (YamlBB.EventCount)264 YamlBF.Blocks.emplace_back(YamlBB);265 continue;266 }267 268 YamlBB.ExecCount = BB->getKnownExecutionCount();269 270 for (const MCInst &Instr : *BB) {271 if (!BC.MIB->isCall(Instr) && !BC.MIB->isIndirectBranch(Instr))272 continue;273 274 SmallVector<std::pair<StringRef, yaml::bolt::CallSiteInfo>> CSTargets;275 yaml::bolt::CallSiteInfo CSI;276 std::optional<uint32_t> Offset = BC.MIB->getOffset(Instr);277 if (!Offset || *Offset < BB->getInputOffset())278 continue;279 CSI.Offset = *Offset - BB->getInputOffset();280 281 if (BC.MIB->isIndirectCall(Instr) || BC.MIB->isIndirectBranch(Instr)) {282 const auto ICSP = BC.MIB->tryGetAnnotationAs<IndirectCallSiteProfile>(283 Instr, "CallProfile");284 if (!ICSP)285 continue;286 for (const IndirectCallProfile &CSP : ICSP.get()) {287 StringRef TargetName = "";288 const BinaryFunction *Callee =289 setCSIDestination(BC, CSI, CSP.Symbol, BAT);290 if (Callee)291 TargetName = Callee->getOneName();292 CSI.Count = CSP.Count;293 CSI.Mispreds = CSP.Mispreds;294 CSTargets.emplace_back(TargetName, CSI);295 }296 } else { // direct call or a tail call297 StringRef TargetName = "";298 const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(Instr);299 const BinaryFunction *const Callee =300 setCSIDestination(BC, CSI, CalleeSymbol, BAT);301 if (Callee)302 TargetName = Callee->getOneName();303 304 auto getAnnotationWithDefault = [&](const MCInst &Inst, StringRef Ann) {305 return BC.MIB->getAnnotationWithDefault(Instr, Ann, 0ull);306 };307 if (BC.MIB->getConditionalTailCall(Instr)) {308 CSI.Count = getAnnotationWithDefault(Instr, "CTCTakenCount");309 CSI.Mispreds = getAnnotationWithDefault(Instr, "CTCMispredCount");310 } else {311 CSI.Count = getAnnotationWithDefault(Instr, "Count");312 }313 314 if (CSI.Count)315 CSTargets.emplace_back(TargetName, CSI);316 }317 // Sort targets in a similar way to getBranchData, see Location::operator<318 llvm::sort(CSTargets, [](const auto &RHS, const auto &LHS) {319 return std::tie(RHS.first, RHS.second.Offset) <320 std::tie(LHS.first, LHS.second.Offset);321 });322 for (auto &KV : CSTargets)323 YamlBB.CallSites.push_back(KV.second);324 }325 326 // Skip printing if there's no profile data for non-entry basic block.327 // Include landing pads with non-zero execution count.328 if (YamlBB.CallSites.empty() && !BB->isEntryPoint() &&329 !(BB->isLandingPad() && BB->getKnownExecutionCount() != 0)) {330 // Include blocks having successors or predecessors with positive counts.331 uint64_t SuccessorExecCount = 0;332 for (const BinaryBasicBlock::BinaryBranchInfo &BranchInfo :333 BB->branch_info())334 SuccessorExecCount += BranchInfo.Count;335 uint64_t PredecessorExecCount = 0;336 for (auto Pred : BB->predecessors())337 PredecessorExecCount += Pred->getBranchInfo(*BB).Count;338 if (!SuccessorExecCount && !PredecessorExecCount)339 continue;340 }341 342 auto BranchInfo = BB->branch_info_begin();343 for (const BinaryBasicBlock *Successor : BB->successors()) {344 yaml::bolt::SuccessorInfo YamlSI;345 YamlSI.Index = Successor->getLayoutIndex();346 YamlSI.Count = BranchInfo->Count;347 YamlSI.Mispreds = BranchInfo->MispredictedCount;348 349 YamlBB.Successors.emplace_back(YamlSI);350 351 ++BranchInfo;352 }353 354 if (PseudoProbeDecoder) {355 const AddressProbesMap &ProbeMap =356 PseudoProbeDecoder->getAddress2ProbesMap();357 const uint64_t FuncAddr = BF.getAddress();358 auto [Start, End] = BB->getInputAddressRange();359 Start += FuncAddr;360 End += FuncAddr;361 BlockProbeCtx Ctx;362 for (const MCDecodedPseudoProbe &Probe : ProbeMap.find(Start, End))363 Ctx.addBlockProbe(InlineTreeNodeId, Probe, Probe.getAddress() - Start);364 Ctx.finalize(YamlBB);365 }366 367 YamlBF.Blocks.emplace_back(YamlBB);368 }369 return YamlBF;370}371 372std::error_code YAMLProfileWriter::writeProfile(const RewriteInstance &RI) {373 const BinaryContext &BC = RI.getBinaryContext();374 const auto &Functions = BC.getBinaryFunctions();375 376 std::error_code EC;377 OS = std::make_unique<raw_fd_ostream>(Filename, EC, sys::fs::OF_None);378 if (EC) {379 errs() << "BOLT-WARNING: " << EC.message() << " : unable to open "380 << Filename << " for output.\n";381 return EC;382 }383 384 yaml::bolt::BinaryProfile BP;385 386 // Fill out the header info.387 BP.Header.Version = 1;388 BP.Header.FileName = std::string(BC.getFilename());389 std::optional<StringRef> BuildID = BC.getFileBuildID();390 BP.Header.Id = BuildID ? std::string(*BuildID) : "<unknown>";391 BP.Header.Origin = std::string(RI.getProfileReader()->getReaderName());392 BP.Header.IsDFSOrder = opts::ProfileUseDFS;393 BP.Header.HashFunction = HashFunction::Default;394 395 StringSet<> EventNames = RI.getProfileReader()->getEventNames();396 if (!EventNames.empty()) {397 std::string Sep;398 for (const StringMapEntry<EmptyStringSetTag> &EventEntry : EventNames) {399 BP.Header.EventNames += Sep + EventEntry.first().str();400 Sep = ",";401 }402 }403 404 // Make sure the profile is consistent across all functions.405 uint16_t ProfileFlags = BinaryFunction::PF_NONE;406 for (const auto &BFI : Functions) {407 const BinaryFunction &BF = BFI.second;408 if (BF.hasProfile() && !BF.empty()) {409 assert(BF.getProfileFlags() != BinaryFunction::PF_NONE);410 if (ProfileFlags == BinaryFunction::PF_NONE)411 ProfileFlags = BF.getProfileFlags();412 413 assert(BF.getProfileFlags() == ProfileFlags &&414 "expected consistent profile flags across all functions");415 }416 }417 BP.Header.Flags = ProfileFlags;418 419 // Add probe inline tree nodes.420 InlineTreeDesc InlineTree;421 if (const MCPseudoProbeDecoder *Decoder =422 opts::ProfileWritePseudoProbes ? BC.getPseudoProbeDecoder() : nullptr)423 std::tie(BP.PseudoProbeDesc, InlineTree) = convertPseudoProbeDesc(*Decoder);424 425 // Add all function objects.426 for (const auto &BFI : Functions) {427 const BinaryFunction &BF = BFI.second;428 if (BF.hasProfile()) {429 if (!BF.hasValidProfile() && !RI.getProfileReader()->isTrustedSource())430 continue;431 432 BP.Functions.emplace_back(convert(BF, opts::ProfileUseDFS, InlineTree));433 }434 }435 436 // Write the profile.437 yaml::Output Out(*OS, nullptr, 0);438 Out << BP;439 440 return std::error_code();441}442 443} // namespace bolt444} // namespace llvm445