453 lines · cpp
1//===- bolt/Rewrite/PseudoProbeRewriter.cpp -------------------------------===//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// Implement support for pseudo probes.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Core/BinaryFunction.h"14#include "bolt/Rewrite/MetadataRewriter.h"15#include "bolt/Rewrite/MetadataRewriters.h"16#include "bolt/Utils/CommandLineOpts.h"17#include "bolt/Utils/Utils.h"18#include "llvm/IR/Function.h"19#include "llvm/MC/MCPseudoProbe.h"20#include "llvm/Support/CommandLine.h"21#include "llvm/Support/Debug.h"22#include "llvm/Support/LEB128.h"23#include <memory>24 25#undef DEBUG_TYPE26#define DEBUG_TYPE "pseudo-probe-rewriter"27 28using namespace llvm;29using namespace bolt;30 31namespace opts {32 33enum PrintPseudoProbesOptions {34 PPP_None = 0,35 PPP_Probes_Section_Decode = 0x1,36 PPP_Probes_Address_Conversion = 0x2,37 PPP_Encoded_Probes = 0x3,38 PPP_All = 0xf39};40 41static cl::opt<PrintPseudoProbesOptions> PrintPseudoProbes(42 "print-pseudo-probes", cl::desc("print pseudo probe info"),43 cl::init(PPP_None),44 cl::values(clEnumValN(PPP_Probes_Section_Decode, "decode",45 "decode probes section from binary"),46 clEnumValN(PPP_Probes_Address_Conversion, "address_conversion",47 "update address2ProbesMap with output block address"),48 clEnumValN(PPP_Encoded_Probes, "encoded_probes",49 "display the encoded probes in binary section"),50 clEnumValN(PPP_All, "all", "enable all debugging printout")),51 cl::Hidden, cl::cat(BoltCategory));52 53extern cl::opt<bool> ProfileWritePseudoProbes;54extern cl::opt<bool> StaleMatchingWithPseudoProbes;55} // namespace opts56 57namespace {58class PseudoProbeRewriter final : public MetadataRewriter {59 /// .pseudo_probe_desc section.60 /// Contains information about pseudo probe description, like its related61 /// function62 ErrorOr<BinarySection &> PseudoProbeDescSection{std::errc::bad_address};63 64 /// .pseudo_probe section.65 /// Contains information about pseudo probe details, like its address66 ErrorOr<BinarySection &> PseudoProbeSection{std::errc::bad_address};67 68 /// Update address of MCDecodedPseudoProbe.69 void updatePseudoProbes();70 71 /// Encode MCDecodedPseudoProbe.72 void encodePseudoProbes();73 74 /// Parse .pseudo_probe_desc section and .pseudo_probe section75 /// Setup Pseudo probe decoder76 /// If \p ProfiledOnly is set, only parse records for functions with profile.77 void parsePseudoProbe(bool ProfiledOnly = false);78 79 /// PseudoProbe decoder80 std::shared_ptr<MCPseudoProbeDecoder> ProbeDecoderPtr;81 82public:83 PseudoProbeRewriter(BinaryContext &BC)84 : MetadataRewriter("pseudo-probe-rewriter", BC),85 ProbeDecoderPtr(std::make_shared<MCPseudoProbeDecoder>()) {86 BC.setPseudoProbeDecoder(ProbeDecoderPtr);87 }88 89 Error preCFGInitializer() override;90 Error postEmitFinalizer() override;91 92 ~PseudoProbeRewriter() override { ProbeDecoderPtr.reset(); }93};94 95Error PseudoProbeRewriter::preCFGInitializer() {96 if (opts::ProfileWritePseudoProbes || opts::StaleMatchingWithPseudoProbes)97 parsePseudoProbe(opts::ProfileWritePseudoProbes);98 99 return Error::success();100}101 102Error PseudoProbeRewriter::postEmitFinalizer() {103 if (!opts::StaleMatchingWithPseudoProbes)104 parsePseudoProbe();105 updatePseudoProbes();106 107 return Error::success();108}109 110void PseudoProbeRewriter::parsePseudoProbe(bool ProfiledOnly) {111 MCPseudoProbeDecoder &ProbeDecoder(*ProbeDecoderPtr);112 PseudoProbeDescSection = BC.getUniqueSectionByName(".pseudo_probe_desc");113 PseudoProbeSection = BC.getUniqueSectionByName(".pseudo_probe");114 115 if (!PseudoProbeDescSection && !PseudoProbeSection) {116 // pesudo probe is not added to binary. It is normal and no warning needed.117 return;118 }119 120 // If only one section is found, it might mean the ELF is corrupted.121 if (!PseudoProbeDescSection) {122 errs() << "BOLT-WARNING: fail in reading .pseudo_probe_desc binary\n";123 return;124 } else if (!PseudoProbeSection) {125 errs() << "BOLT-WARNING: fail in reading .pseudo_probe binary\n";126 return;127 }128 129 StringRef Contents = PseudoProbeDescSection->getContents();130 if (!ProbeDecoder.buildGUID2FuncDescMap(131 reinterpret_cast<const uint8_t *>(Contents.data()), Contents.size(),132 /*IsMMapped*/ true)) {133 errs() << "BOLT-WARNING: fail in building GUID2FuncDescMap\n";134 return;135 }136 137 MCPseudoProbeDecoder::Uint64Set GuidFilter;138 MCPseudoProbeDecoder::Uint64Map FuncStartAddrs;139 SmallVector<StringRef, 0> Suffixes(140 {".destroy", ".resume", ".llvm.", ".cold", ".warm"});141 for (const BinaryFunction *F : BC.getAllBinaryFunctions()) {142 bool HasProfile = F->hasProfileAvailable();143 for (const MCSymbol *Sym : F->getSymbols()) {144 StringRef SymName = Sym->getName();145 for (auto Name : {std::optional(NameResolver::restore(SymName)),146 getCommonName(SymName, false, Suffixes)}) {147 if (!Name)148 continue;149 SymName = *Name;150 uint64_t GUID = Function::getGUIDAssumingExternalLinkage(SymName);151 FuncStartAddrs[GUID] = F->getAddress();152 if (ProfiledOnly && HasProfile)153 GuidFilter.insert(GUID);154 }155 }156 }157 Contents = PseudoProbeSection->getContents();158 if (!ProbeDecoder.buildAddress2ProbeMap(159 reinterpret_cast<const uint8_t *>(Contents.data()), Contents.size(),160 GuidFilter, FuncStartAddrs)) {161 errs() << "BOLT-WARNING: fail in building Address2ProbeMap\n";162 return;163 }164 165 if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||166 opts::PrintPseudoProbes ==167 opts::PrintPseudoProbesOptions::PPP_Probes_Section_Decode) {168 outs() << "Report of decoding input pseudo probe binaries \n";169 ProbeDecoder.printGUID2FuncDescMap(outs());170 ProbeDecoder.printProbesForAllAddresses(outs());171 }172 173 const GUIDProbeFunctionMap &GUID2Func = ProbeDecoder.getGUID2FuncDescMap();174 // Checks GUID in GUID2Func and returns it if it's present or null otherwise.175 auto checkGUID = [&](StringRef SymName) -> uint64_t {176 uint64_t GUID = Function::getGUIDAssumingExternalLinkage(SymName);177 if (GUID2Func.find(GUID) == GUID2Func.end())178 return 0;179 return GUID;180 };181 for (BinaryFunction *F : BC.getAllBinaryFunctions()) {182 for (const MCSymbol *Sym : F->getSymbols()) {183 StringRef SymName = NameResolver::restore(Sym->getName());184 uint64_t GUID = checkGUID(SymName);185 std::optional<StringRef> CommonName =186 getCommonName(SymName, false, Suffixes);187 if (!GUID && CommonName)188 GUID = checkGUID(*CommonName);189 if (GUID)190 F->setGUID(GUID);191 }192 }193}194 195void PseudoProbeRewriter::updatePseudoProbes() {196 MCPseudoProbeDecoder &ProbeDecoder(*ProbeDecoderPtr);197 // check if there is pseudo probe section decoded198 if (ProbeDecoder.getAddress2ProbesMap().empty())199 return;200 // input address converted to output201 AddressProbesMap &Address2ProbesMap = ProbeDecoder.getAddress2ProbesMap();202 const GUIDProbeFunctionMap &GUID2Func = ProbeDecoder.getGUID2FuncDescMap();203 204 for (MCDecodedPseudoProbe &Probe : Address2ProbesMap) {205 uint64_t Address = Probe.getAddress();206 BinaryFunction *F = BC.getBinaryFunctionContainingAddress(Address);207 // If F is removed, eliminate all probes inside it from inline tree208 // Setting probes' addresses as INT64_MAX means elimination209 if (!F) {210 Probe.setAddress(INT64_MAX);211 continue;212 }213 // If F is not emitted, the function will remain in the same address as its214 // input215 if (!F->isEmitted())216 continue;217 218 uint64_t Offset = Address - F->getAddress();219 const BinaryBasicBlock *BB = F->getBasicBlockContainingOffset(Offset);220 uint64_t BlkOutputAddress = BB->getOutputAddressRange().first;221 // Check if block output address is defined.222 // If not, such block is removed from binary. Then remove the probes from223 // inline tree224 if (BlkOutputAddress == 0) {225 Probe.setAddress(INT64_MAX);226 continue;227 }228 229 if (Probe.isBlock()) {230 Probe.setAddress(BlkOutputAddress);231 } else if (Probe.isCall()) {232 // A call probe may be duplicated due to ICP233 // Go through output of InputOffsetToAddressMap to collect all related234 // probes235 auto CallOutputAddresses = BC.getIOAddressMap().lookupAll(Address);236 auto CallOutputAddress = CallOutputAddresses.first;237 if (CallOutputAddress == CallOutputAddresses.second) {238 Probe.setAddress(INT64_MAX);239 } else {240 Probe.setAddress(CallOutputAddress->second);241 CallOutputAddress = std::next(CallOutputAddress);242 }243 244 while (CallOutputAddress != CallOutputAddresses.second) {245 ProbeDecoder.addInjectedProbe(Probe, CallOutputAddress->second);246 CallOutputAddress = std::next(CallOutputAddress);247 }248 }249 }250 251 if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||252 opts::PrintPseudoProbes ==253 opts::PrintPseudoProbesOptions::PPP_Probes_Address_Conversion) {254 outs() << "Pseudo Probe Address Conversion results:\n";255 // table that correlates address to block256 std::unordered_map<uint64_t, StringRef> Addr2BlockNames;257 for (auto &F : BC.getBinaryFunctions())258 for (BinaryBasicBlock &BinaryBlock : F.second)259 Addr2BlockNames[BinaryBlock.getOutputAddressRange().first] =260 BinaryBlock.getName();261 262 // scan all addresses -> correlate probe to block when print out263 for (MCDecodedPseudoProbe &Probe : Address2ProbesMap) {264 if (Probe.getAddress() == INT64_MAX)265 outs() << "Deleted Probe: ";266 else267 outs() << "Address: " << format_hex(Probe.getAddress(), 8) << " ";268 Probe.print(outs(), GUID2Func, true);269 // print block name only if the probe is block type and undeleted.270 if (Probe.isBlock() && Probe.getAddress() != INT64_MAX)271 outs() << format_hex(Probe.getAddress(), 8) << " Probe is in "272 << Addr2BlockNames[Probe.getAddress()] << "\n";273 }274 outs() << "=======================================\n";275 }276 277 // encode pseudo probes with updated addresses278 encodePseudoProbes();279}280 281void PseudoProbeRewriter::encodePseudoProbes() {282 MCPseudoProbeDecoder &ProbeDecoder(*ProbeDecoderPtr);283 // Buffer for new pseudo probes section284 SmallString<8> Contents;285 MCDecodedPseudoProbe *LastProbe = nullptr;286 287 auto EmitInt = [&](uint64_t Value, uint32_t Size) {288 const bool IsLittleEndian = BC.AsmInfo->isLittleEndian();289 uint64_t Swapped = support::endian::byte_swap(290 Value,291 IsLittleEndian ? llvm::endianness::little : llvm::endianness::big);292 unsigned Index = IsLittleEndian ? 0 : 8 - Size;293 auto Entry = StringRef(reinterpret_cast<char *>(&Swapped) + Index, Size);294 Contents.append(Entry.begin(), Entry.end());295 };296 297 auto EmitULEB128IntValue = [&](uint64_t Value) {298 SmallString<128> Tmp;299 raw_svector_ostream OSE(Tmp);300 encodeULEB128(Value, OSE, 0);301 Contents.append(OSE.str().begin(), OSE.str().end());302 };303 304 auto EmitSLEB128IntValue = [&](int64_t Value) {305 SmallString<128> Tmp;306 raw_svector_ostream OSE(Tmp);307 encodeSLEB128(Value, OSE);308 Contents.append(OSE.str().begin(), OSE.str().end());309 };310 311 // Emit individual pseudo probes in a inline tree node312 // Probe index, type, attribute, address type and address are encoded313 // Address of the first probe is absolute.314 // Other probes' address are represented by delta315 auto EmitDecodedPseudoProbe = [&](MCDecodedPseudoProbe *&CurProbe) {316 assert(!isSentinelProbe(CurProbe->getAttributes()) &&317 "Sentinel probes should not be emitted");318 EmitULEB128IntValue(CurProbe->getIndex());319 uint8_t PackedType = CurProbe->getType() | (CurProbe->getAttributes() << 4);320 uint8_t Flag =321 LastProbe ? ((int8_t)MCPseudoProbeFlag::AddressDelta << 7) : 0;322 EmitInt(Flag | PackedType, 1);323 if (LastProbe) {324 // Emit the delta between the address label and LastProbe.325 int64_t Delta = CurProbe->getAddress() - LastProbe->getAddress();326 EmitSLEB128IntValue(Delta);327 } else {328 // Emit absolute address for encoding the first pseudo probe.329 uint32_t AddrSize = BC.AsmInfo->getCodePointerSize();330 EmitInt(CurProbe->getAddress(), AddrSize);331 }332 };333 334 std::map<InlineSite, MCDecodedPseudoProbeInlineTree *,335 std::greater<InlineSite>>336 Inlinees;337 338 // DFS of inline tree to emit pseudo probes in all tree node339 // Inline site index of a probe is emitted first.340 // Then tree node Guid, size of pseudo probes and children nodes, and detail341 // of contained probes are emitted Deleted probes are skipped Root node is not342 // encoded to binaries. It's a "wrapper" of inline trees of each function.343 std::list<std::pair<uint64_t, MCDecodedPseudoProbeInlineTree *>> NextNodes;344 const MCDecodedPseudoProbeInlineTree &Root =345 ProbeDecoder.getDummyInlineRoot();346 for (auto Child = Root.getChildren().begin();347 Child != Root.getChildren().end(); ++Child)348 Inlinees[Child->getInlineSite()] = &*Child;349 350 for (auto Inlinee : Inlinees)351 // INT64_MAX is "placeholder" of unused callsite index field in the pair352 NextNodes.push_back({INT64_MAX, Inlinee.second});353 354 Inlinees.clear();355 356 while (!NextNodes.empty()) {357 uint64_t ProbeIndex = NextNodes.back().first;358 MCDecodedPseudoProbeInlineTree *Cur = NextNodes.back().second;359 NextNodes.pop_back();360 361 if (Cur->Parent && !Cur->Parent->isRoot())362 // Emit probe inline site363 EmitULEB128IntValue(ProbeIndex);364 365 // Emit probes grouped by GUID.366 LLVM_DEBUG({367 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);368 dbgs() << "GUID: " << Cur->Guid << "\n";369 });370 // Emit Guid371 EmitInt(Cur->Guid, 8);372 // Emit number of probes in this node373 uint64_t Deleted = 0;374 for (MCDecodedPseudoProbe *&Probe :375 llvm::make_pointer_range(Cur->getProbes()))376 if (Probe->getAddress() == INT64_MAX)377 Deleted++;378 LLVM_DEBUG(dbgs() << "Deleted Probes:" << Deleted << "\n");379 size_t InjectedProbes = ProbeDecoder.getNumInjectedProbes(Cur);380 uint64_t ProbesSize = Cur->getProbes().size() - Deleted + InjectedProbes;381 EmitULEB128IntValue(ProbesSize);382 // Emit number of direct inlinees383 EmitULEB128IntValue(Cur->getChildren().size());384 // Emit probes in this group385 for (MCDecodedPseudoProbe *&Probe :386 llvm::make_pointer_range(Cur->getProbes())) {387 if (Probe->getAddress() == INT64_MAX)388 continue;389 EmitDecodedPseudoProbe(Probe);390 LastProbe = Probe;391 }392 if (InjectedProbes) {393 for (MCDecodedPseudoProbe *&Probe :394 llvm::make_pointer_range(ProbeDecoder.getInjectedProbes(Cur))) {395 if (Probe->getAddress() == INT64_MAX)396 continue;397 EmitDecodedPseudoProbe(Probe);398 LastProbe = Probe;399 }400 }401 402 for (auto Child = Cur->getChildren().begin();403 Child != Cur->getChildren().end(); ++Child)404 Inlinees[Child->getInlineSite()] = &*Child;405 for (const auto &Inlinee : Inlinees) {406 assert(Cur->Guid != 0 && "non root tree node must have nonzero Guid");407 NextNodes.push_back({std::get<1>(Inlinee.first), Inlinee.second});408 LLVM_DEBUG({409 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);410 dbgs() << "InlineSite: " << std::get<1>(Inlinee.first) << "\n";411 });412 }413 Inlinees.clear();414 }415 416 // Create buffer for new contents for the section417 // Freed when parent section is destroyed418 uint8_t *Output = new uint8_t[Contents.str().size()];419 memcpy(Output, Contents.str().data(), Contents.str().size());420 BC.registerOrUpdateSection(".pseudo_probe", PseudoProbeSection->getELFType(),421 PseudoProbeSection->getELFFlags(), Output,422 Contents.str().size(), 1);423 if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||424 opts::PrintPseudoProbes ==425 opts::PrintPseudoProbesOptions::PPP_Encoded_Probes) {426 // create a dummy decoder;427 MCPseudoProbeDecoder DummyDecoder;428 StringRef DescContents = PseudoProbeDescSection->getContents();429 DummyDecoder.buildGUID2FuncDescMap(430 reinterpret_cast<const uint8_t *>(DescContents.data()),431 DescContents.size());432 StringRef ProbeContents = PseudoProbeSection->getOutputContents();433 MCPseudoProbeDecoder::Uint64Set GuidFilter;434 MCPseudoProbeDecoder::Uint64Map FuncStartAddrs;435 for (const BinaryFunction *F : BC.getAllBinaryFunctions()) {436 const uint64_t Addr =437 F->isEmitted() ? F->getOutputAddress() : F->getAddress();438 FuncStartAddrs[Function::getGUIDAssumingExternalLinkage(439 NameResolver::restore(F->getOneName()))] = Addr;440 }441 DummyDecoder.buildAddress2ProbeMap(442 reinterpret_cast<const uint8_t *>(ProbeContents.data()),443 ProbeContents.size(), GuidFilter, FuncStartAddrs);444 DummyDecoder.printProbesForAllAddresses(outs());445 }446}447} // namespace448 449std::unique_ptr<MetadataRewriter>450llvm::bolt::createPseudoProbeRewriter(BinaryContext &BC) {451 return std::make_unique<PseudoProbeRewriter>(BC);452}453