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-exception 6 // 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_TYPE 26 #define DEBUG_TYPE "pseudo-probe-rewriter" 27 28 using namespace llvm; 29 using namespace bolt; 30 31 namespace opts { 32 33 enum 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 = 0xf 39 }; 40 41 static 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 53 extern cl::opt<bool> ProfileWritePseudoProbes; 54 extern cl::opt<bool> StaleMatchingWithPseudoProbes; 55 } // namespace opts 56 57 namespace { 58 class PseudoProbeRewriter final : public MetadataRewriter { 59 /// .pseudo_probe_desc section. 60 /// Contains information about pseudo probe description, like its related 61 /// function 62 ErrorOr<BinarySection &> PseudoProbeDescSection{std::errc::bad_address}; 63 64 /// .pseudo_probe section. 65 /// Contains information about pseudo probe details, like its address 66 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 section 75 /// Setup Pseudo probe decoder 76 /// If \p ProfiledOnly is set, only parse records for functions with profile. 77 void parsePseudoProbe(bool ProfiledOnly = false); 78 79 /// PseudoProbe decoder 80 std::shared_ptr<MCPseudoProbeDecoder> ProbeDecoderPtr; 81 82 public: 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 95 Error PseudoProbeRewriter::preCFGInitializer() { 96 if (opts::ProfileWritePseudoProbes || opts::StaleMatchingWithPseudoProbes) 97 parsePseudoProbe(opts::ProfileWritePseudoProbes); 98 99 return Error::success(); 100 } 101 102 Error PseudoProbeRewriter::postEmitFinalizer() { 103 if (!opts::StaleMatchingWithPseudoProbes) 104 parsePseudoProbe(); 105 updatePseudoProbes(); 106 107 return Error::success(); 108 } 109 110 void 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::getGUID(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::getGUID(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 195 void PseudoProbeRewriter::updatePseudoProbes() { 196 MCPseudoProbeDecoder &ProbeDecoder(*ProbeDecoderPtr); 197 // check if there is pseudo probe section decoded 198 if (ProbeDecoder.getAddress2ProbesMap().empty()) 199 return; 200 // input address converted to output 201 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 tree 208 // Setting probes' addresses as INT64_MAX means elimination 209 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 its 214 // input 215 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 from 223 // inline tree 224 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 ICP 233 // Go through output of InputOffsetToAddressMap to collect all related 234 // probes 235 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 block 256 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 out 263 for (MCDecodedPseudoProbe &Probe : Address2ProbesMap) { 264 if (Probe.getAddress() == INT64_MAX) 265 outs() << "Deleted Probe: "; 266 else 267 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 addresses 278 encodePseudoProbes(); 279 } 280 281 void PseudoProbeRewriter::encodePseudoProbes() { 282 MCPseudoProbeDecoder &ProbeDecoder(*ProbeDecoderPtr); 283 // Buffer for new pseudo probes section 284 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 indiviual pseudo probes in a inline tree node 312 // Probe index, type, attribute, address type and address are encoded 313 // Address of the first probe is absolute. 314 // Other probes' address are represented by delta 315 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 node 339 // Inline site index of a probe is emitted first. 340 // Then tree node Guid, size of pseudo probes and children nodes, and detail 341 // of contained probes are emitted Deleted probes are skipped Root node is not 342 // 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 pair 352 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 site 363 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 Guid 371 EmitInt(Cur->Guid, 8); 372 // Emit number of probes in this node 373 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 inlinees 383 EmitULEB128IntValue(Cur->getChildren().size()); 384 // Emit probes in this group 385 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 section 417 // Freed when parent section is destroyed 418 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::getGUID( 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 } // namespace 448 449 std::unique_ptr<MetadataRewriter> 450 llvm::bolt::createPseudoProbeRewriter(BinaryContext &BC) { 451 return std::make_unique<PseudoProbeRewriter>(BC); 452 } 453