1 //===- bolt/Profile/BoltAddressTranslation.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 #include "bolt/Profile/BoltAddressTranslation.h" 10 #include "bolt/Core/BinaryFunction.h" 11 #include "llvm/ADT/APInt.h" 12 #include "llvm/Support/Errc.h" 13 #include "llvm/Support/Error.h" 14 #include "llvm/Support/LEB128.h" 15 16 #define DEBUG_TYPE "bolt-bat" 17 18 namespace llvm { 19 namespace bolt { 20 21 const char *BoltAddressTranslation::SECTION_NAME = ".note.bolt_bat"; 22 23 void BoltAddressTranslation::writeEntriesForBB(MapTy &Map, 24 const BinaryBasicBlock &BB, 25 uint64_t FuncInputAddress, 26 uint64_t FuncOutputAddress) { 27 const uint64_t BBOutputOffset = 28 BB.getOutputAddressRange().first - FuncOutputAddress; 29 const uint32_t BBInputOffset = BB.getInputOffset(); 30 31 // Every output BB must track back to an input BB for profile collection 32 // in bolted binaries. If we are missing an offset, it means this block was 33 // created by a pass. We will skip writing any entries for it, and this means 34 // any traffic happening in this block will map to the previous block in the 35 // layout. This covers the case where an input basic block is split into two, 36 // and the second one lacks any offset. 37 if (BBInputOffset == BinaryBasicBlock::INVALID_OFFSET) 38 return; 39 40 LLVM_DEBUG(dbgs() << "BB " << BB.getName() << "\n"); 41 LLVM_DEBUG(dbgs() << " Key: " << Twine::utohexstr(BBOutputOffset) 42 << " Val: " << Twine::utohexstr(BBInputOffset) << "\n"); 43 // NB: in `writeEntriesForBB` we use the input address because hashes are 44 // saved early in `saveMetadata` before output addresses are assigned. 45 const BBHashMapTy &BBHashMap = getBBHashMap(FuncInputAddress); 46 (void)BBHashMap; 47 LLVM_DEBUG( 48 dbgs() << formatv(" Hash: {0:x}\n", BBHashMap.getBBHash(BBInputOffset))); 49 LLVM_DEBUG( 50 dbgs() << formatv(" Index: {0}\n", BBHashMap.getBBIndex(BBInputOffset))); 51 // In case of conflicts (same Key mapping to different Vals), the last 52 // update takes precedence. Of course it is not ideal to have conflicts and 53 // those happen when we have an empty BB that either contained only 54 // NOPs or a jump to the next block (successor). Either way, the successor 55 // and this deleted block will both share the same output address (the same 56 // key), and we need to map back. We choose here to privilege the successor by 57 // allowing it to overwrite the previously inserted key in the map. 58 Map[BBOutputOffset] = BBInputOffset << 1; 59 60 const auto &IOAddressMap = 61 BB.getFunction()->getBinaryContext().getIOAddressMap(); 62 63 for (const auto &[InputOffset, Sym] : BB.getLocSyms()) { 64 const auto InputAddress = BB.getFunction()->getAddress() + InputOffset; 65 const auto OutputAddress = IOAddressMap.lookup(InputAddress); 66 assert(OutputAddress && "Unknown instruction address"); 67 const auto OutputOffset = *OutputAddress - FuncOutputAddress; 68 69 // Is this the first instruction in the BB? No need to duplicate the entry. 70 if (OutputOffset == BBOutputOffset) 71 continue; 72 73 LLVM_DEBUG(dbgs() << " Key: " << Twine::utohexstr(OutputOffset) << " Val: " 74 << Twine::utohexstr(InputOffset) << " (branch)\n"); 75 Map.insert(std::pair<uint32_t, uint32_t>(OutputOffset, 76 (InputOffset << 1) | BRANCHENTRY)); 77 } 78 } 79 80 void BoltAddressTranslation::write(const BinaryContext &BC, raw_ostream &OS) { 81 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Writing BOLT Address Translation Tables\n"); 82 for (auto &BFI : BC.getBinaryFunctions()) { 83 const BinaryFunction &Function = BFI.second; 84 const uint64_t InputAddress = Function.getAddress(); 85 const uint64_t OutputAddress = Function.getOutputAddress(); 86 // We don't need a translation table if the body of the function hasn't 87 // changed 88 if (Function.isIgnored() || (!BC.HasRelocations && !Function.isSimple())) 89 continue; 90 91 // TBD: handle BAT functions w/multiple entry points. 92 if (Function.isMultiEntry()) 93 continue; 94 95 LLVM_DEBUG(dbgs() << "Function name: " << Function.getPrintName() << "\n"); 96 LLVM_DEBUG(dbgs() << " Address reference: 0x" 97 << Twine::utohexstr(Function.getOutputAddress()) << "\n"); 98 LLVM_DEBUG(dbgs() << formatv(" Hash: {0:x}\n", getBFHash(OutputAddress))); 99 100 MapTy Map; 101 for (const BinaryBasicBlock *const BB : 102 Function.getLayout().getMainFragment()) 103 writeEntriesForBB(Map, *BB, InputAddress, OutputAddress); 104 Maps.emplace(Function.getOutputAddress(), std::move(Map)); 105 ReverseMap.emplace(OutputAddress, InputAddress); 106 107 if (!Function.isSplit()) 108 continue; 109 110 // Split maps 111 LLVM_DEBUG(dbgs() << " Cold part\n"); 112 for (const FunctionFragment &FF : 113 Function.getLayout().getSplitFragments()) { 114 ColdPartSource.emplace(FF.getAddress(), Function.getOutputAddress()); 115 Map.clear(); 116 for (const BinaryBasicBlock *const BB : FF) 117 writeEntriesForBB(Map, *BB, InputAddress, FF.getAddress()); 118 119 Maps.emplace(FF.getAddress(), std::move(Map)); 120 } 121 } 122 123 // Output addresses are delta-encoded 124 uint64_t PrevAddress = 0; 125 writeMaps</*Cold=*/false>(Maps, PrevAddress, OS); 126 writeMaps</*Cold=*/true>(Maps, PrevAddress, OS); 127 128 BC.outs() << "BOLT-INFO: Wrote " << Maps.size() << " BAT maps\n"; 129 BC.outs() << "BOLT-INFO: Wrote " << FuncHashes.getNumFunctions() 130 << " function and " << FuncHashes.getNumBasicBlocks() 131 << " basic block hashes\n"; 132 } 133 134 APInt BoltAddressTranslation::calculateBranchEntriesBitMask(MapTy &Map, 135 size_t EqualElems) { 136 APInt BitMask(alignTo(EqualElems, 8), 0); 137 size_t Index = 0; 138 for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) { 139 if (Index == EqualElems) 140 break; 141 const uint32_t OutputOffset = KeyVal.second; 142 if (OutputOffset & BRANCHENTRY) 143 BitMask.setBit(Index); 144 ++Index; 145 } 146 return BitMask; 147 } 148 149 size_t BoltAddressTranslation::getNumEqualOffsets(const MapTy &Map) const { 150 size_t EqualOffsets = 0; 151 for (const std::pair<const uint32_t, uint32_t> &KeyVal : Map) { 152 const uint32_t OutputOffset = KeyVal.first; 153 const uint32_t InputOffset = KeyVal.second >> 1; 154 if (OutputOffset == InputOffset) 155 ++EqualOffsets; 156 else 157 break; 158 } 159 return EqualOffsets; 160 } 161 162 template <bool Cold> 163 void BoltAddressTranslation::writeMaps(std::map<uint64_t, MapTy> &Maps, 164 uint64_t &PrevAddress, raw_ostream &OS) { 165 const uint32_t NumFuncs = 166 llvm::count_if(llvm::make_first_range(Maps), [&](const uint64_t Address) { 167 return Cold == ColdPartSource.count(Address); 168 }); 169 encodeULEB128(NumFuncs, OS); 170 LLVM_DEBUG(dbgs() << "Writing " << NumFuncs << (Cold ? " cold" : "") 171 << " functions for BAT.\n"); 172 size_t PrevIndex = 0; 173 for (auto &MapEntry : Maps) { 174 const uint64_t Address = MapEntry.first; 175 // Only process cold fragments in cold mode, and vice versa. 176 if (Cold != ColdPartSource.count(Address)) 177 continue; 178 // NB: in `writeMaps` we use the input address because hashes are saved 179 // early in `saveMetadata` before output addresses are assigned. 180 const uint64_t HotInputAddress = 181 ReverseMap[Cold ? ColdPartSource[Address] : Address]; 182 MapTy &Map = MapEntry.second; 183 const uint32_t NumEntries = Map.size(); 184 LLVM_DEBUG(dbgs() << "Writing " << NumEntries << " entries for 0x" 185 << Twine::utohexstr(Address) << ".\n"); 186 encodeULEB128(Address - PrevAddress, OS); 187 PrevAddress = Address; 188 if (Cold) { 189 size_t HotIndex = 190 std::distance(ColdPartSource.begin(), ColdPartSource.find(Address)); 191 encodeULEB128(HotIndex - PrevIndex, OS); 192 PrevIndex = HotIndex; 193 } else { 194 // Function hash 195 size_t BFHash = getBFHash(HotInputAddress); 196 LLVM_DEBUG(dbgs() << "Hash: " << formatv("{0:x}\n", BFHash)); 197 OS.write(reinterpret_cast<char *>(&BFHash), 8); 198 // Number of basic blocks 199 size_t NumBasicBlocks = getBBHashMap(HotInputAddress).getNumBasicBlocks(); 200 LLVM_DEBUG(dbgs() << "Basic blocks: " << NumBasicBlocks << '\n'); 201 encodeULEB128(NumBasicBlocks, OS); 202 } 203 encodeULEB128(NumEntries, OS); 204 // For hot fragments only: encode the number of equal offsets 205 // (output = input) in the beginning of the function. Only encode one offset 206 // in these cases. 207 const size_t EqualElems = Cold ? 0 : getNumEqualOffsets(Map); 208 if (!Cold) { 209 encodeULEB128(EqualElems, OS); 210 if (EqualElems) { 211 const size_t BranchEntriesBytes = alignTo(EqualElems, 8) / 8; 212 APInt BranchEntries = calculateBranchEntriesBitMask(Map, EqualElems); 213 OS.write(reinterpret_cast<const char *>(BranchEntries.getRawData()), 214 BranchEntriesBytes); 215 LLVM_DEBUG({ 216 dbgs() << "BranchEntries: "; 217 SmallString<8> BitMaskStr; 218 BranchEntries.toString(BitMaskStr, 2, false); 219 dbgs() << BitMaskStr << '\n'; 220 }); 221 } 222 } 223 const BBHashMapTy &BBHashMap = getBBHashMap(HotInputAddress); 224 size_t Index = 0; 225 uint64_t InOffset = 0; 226 size_t PrevBBIndex = 0; 227 // Output and Input addresses and delta-encoded 228 for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) { 229 const uint64_t OutputAddress = KeyVal.first + Address; 230 encodeULEB128(OutputAddress - PrevAddress, OS); 231 PrevAddress = OutputAddress; 232 if (Index++ >= EqualElems) 233 encodeSLEB128(KeyVal.second - InOffset, OS); 234 InOffset = KeyVal.second; // Keeping InOffset as if BRANCHENTRY is encoded 235 if ((InOffset & BRANCHENTRY) == 0) { 236 const bool IsBlock = BBHashMap.isInputBlock(InOffset >> 1); 237 unsigned BBIndex = IsBlock ? BBHashMap.getBBIndex(InOffset >> 1) : 0; 238 size_t BBHash = IsBlock ? BBHashMap.getBBHash(InOffset >> 1) : 0; 239 OS.write(reinterpret_cast<char *>(&BBHash), 8); 240 // Basic block index in the input binary 241 encodeULEB128(BBIndex - PrevBBIndex, OS); 242 PrevBBIndex = BBIndex; 243 LLVM_DEBUG(dbgs() << formatv("{0:x} -> {1:x} {2:x} {3}\n", KeyVal.first, 244 InOffset >> 1, BBHash, BBIndex)); 245 } 246 } 247 } 248 } 249 250 std::error_code BoltAddressTranslation::parse(raw_ostream &OS, StringRef Buf) { 251 DataExtractor DE = DataExtractor(Buf, true, 8); 252 uint64_t Offset = 0; 253 if (Buf.size() < 12) 254 return make_error_code(llvm::errc::io_error); 255 256 const uint32_t NameSz = DE.getU32(&Offset); 257 const uint32_t DescSz = DE.getU32(&Offset); 258 const uint32_t Type = DE.getU32(&Offset); 259 260 if (Type != BinarySection::NT_BOLT_BAT || 261 Buf.size() + Offset < alignTo(NameSz, 4) + DescSz) 262 return make_error_code(llvm::errc::io_error); 263 264 StringRef Name = Buf.slice(Offset, Offset + NameSz); 265 Offset = alignTo(Offset + NameSz, 4); 266 if (Name.substr(0, 4) != "BOLT") 267 return make_error_code(llvm::errc::io_error); 268 269 Error Err(Error::success()); 270 std::vector<uint64_t> HotFuncs; 271 uint64_t PrevAddress = 0; 272 parseMaps</*Cold=*/false>(HotFuncs, PrevAddress, DE, Offset, Err); 273 parseMaps</*Cold=*/true>(HotFuncs, PrevAddress, DE, Offset, Err); 274 OS << "BOLT-INFO: Parsed " << Maps.size() << " BAT entries\n"; 275 return errorToErrorCode(std::move(Err)); 276 } 277 278 template <bool Cold> 279 void BoltAddressTranslation::parseMaps(std::vector<uint64_t> &HotFuncs, 280 uint64_t &PrevAddress, DataExtractor &DE, 281 uint64_t &Offset, Error &Err) { 282 const uint32_t NumFunctions = DE.getULEB128(&Offset, &Err); 283 LLVM_DEBUG(dbgs() << "Parsing " << NumFunctions << (Cold ? " cold" : "") 284 << " functions\n"); 285 size_t HotIndex = 0; 286 for (uint32_t I = 0; I < NumFunctions; ++I) { 287 const uint64_t Address = PrevAddress + DE.getULEB128(&Offset, &Err); 288 uint64_t HotAddress = Cold ? 0 : Address; 289 PrevAddress = Address; 290 if (Cold) { 291 HotIndex += DE.getULEB128(&Offset, &Err); 292 HotAddress = HotFuncs[HotIndex]; 293 ColdPartSource.emplace(Address, HotAddress); 294 } else { 295 HotFuncs.push_back(Address); 296 // Function hash 297 const size_t FuncHash = DE.getU64(&Offset, &Err); 298 FuncHashes.addEntry(Address, FuncHash); 299 LLVM_DEBUG(dbgs() << formatv("{0:x}: hash {1:x}\n", Address, FuncHash)); 300 // Number of basic blocks 301 const size_t NumBasicBlocks = DE.getULEB128(&Offset, &Err); 302 NumBasicBlocksMap.emplace(Address, NumBasicBlocks); 303 LLVM_DEBUG(dbgs() << formatv("{0:x}: #bbs {1}, {2} bytes\n", Address, 304 NumBasicBlocks, 305 getULEB128Size(NumBasicBlocks))); 306 } 307 const uint32_t NumEntries = DE.getULEB128(&Offset, &Err); 308 // Equal offsets, hot fragments only. 309 size_t EqualElems = 0; 310 APInt BEBitMask; 311 if (!Cold) { 312 EqualElems = DE.getULEB128(&Offset, &Err); 313 LLVM_DEBUG(dbgs() << formatv("Equal offsets: {0}, {1} bytes\n", 314 EqualElems, getULEB128Size(EqualElems))); 315 if (EqualElems) { 316 const size_t BranchEntriesBytes = alignTo(EqualElems, 8) / 8; 317 BEBitMask = APInt(alignTo(EqualElems, 8), 0); 318 LoadIntFromMemory( 319 BEBitMask, 320 reinterpret_cast<const uint8_t *>( 321 DE.getBytes(&Offset, BranchEntriesBytes, &Err).data()), 322 BranchEntriesBytes); 323 LLVM_DEBUG({ 324 dbgs() << "BEBitMask: "; 325 SmallString<8> BitMaskStr; 326 BEBitMask.toString(BitMaskStr, 2, false); 327 dbgs() << BitMaskStr << ", " << BranchEntriesBytes << " bytes\n"; 328 }); 329 } 330 } 331 MapTy Map; 332 333 LLVM_DEBUG(dbgs() << "Parsing " << NumEntries << " entries for 0x" 334 << Twine::utohexstr(Address) << "\n"); 335 uint64_t InputOffset = 0; 336 size_t BBIndex = 0; 337 for (uint32_t J = 0; J < NumEntries; ++J) { 338 const uint64_t OutputDelta = DE.getULEB128(&Offset, &Err); 339 const uint64_t OutputAddress = PrevAddress + OutputDelta; 340 const uint64_t OutputOffset = OutputAddress - Address; 341 PrevAddress = OutputAddress; 342 int64_t InputDelta = 0; 343 if (J < EqualElems) { 344 InputOffset = (OutputOffset << 1) | BEBitMask[J]; 345 } else { 346 InputDelta = DE.getSLEB128(&Offset, &Err); 347 InputOffset += InputDelta; 348 } 349 Map.insert(std::pair<uint32_t, uint32_t>(OutputOffset, InputOffset)); 350 size_t BBHash = 0; 351 size_t BBIndexDelta = 0; 352 const bool IsBranchEntry = InputOffset & BRANCHENTRY; 353 if (!IsBranchEntry) { 354 BBHash = DE.getU64(&Offset, &Err); 355 BBIndexDelta = DE.getULEB128(&Offset, &Err); 356 BBIndex += BBIndexDelta; 357 // Map basic block hash to hot fragment by input offset 358 getBBHashMap(HotAddress).addEntry(InputOffset >> 1, BBIndex, BBHash); 359 } 360 LLVM_DEBUG({ 361 dbgs() << formatv( 362 "{0:x} -> {1:x} ({2}/{3}b -> {4}/{5}b), {6:x}", OutputOffset, 363 InputOffset, OutputDelta, getULEB128Size(OutputDelta), InputDelta, 364 (J < EqualElems) ? 0 : getSLEB128Size(InputDelta), OutputAddress); 365 if (!IsBranchEntry) { 366 dbgs() << formatv(" {0:x} {1}/{2}b", BBHash, BBIndex, 367 getULEB128Size(BBIndexDelta)); 368 } 369 dbgs() << '\n'; 370 }); 371 } 372 Maps.insert(std::pair<uint64_t, MapTy>(Address, Map)); 373 } 374 } 375 376 void BoltAddressTranslation::dump(raw_ostream &OS) { 377 const size_t NumTables = Maps.size(); 378 OS << "BAT tables for " << NumTables << " functions:\n"; 379 for (const auto &MapEntry : Maps) { 380 const uint64_t Address = MapEntry.first; 381 const uint64_t HotAddress = fetchParentAddress(Address); 382 OS << "Function Address: 0x" << Twine::utohexstr(Address); 383 if (HotAddress == 0) 384 OS << formatv(", hash: {0:x}", getBFHash(Address)); 385 OS << "\n"; 386 OS << "BB mappings:\n"; 387 const BBHashMapTy &BBHashMap = 388 getBBHashMap(HotAddress ? HotAddress : Address); 389 for (const auto &Entry : MapEntry.second) { 390 const bool IsBranch = Entry.second & BRANCHENTRY; 391 const uint32_t Val = Entry.second >> 1; // dropping BRANCHENTRY bit 392 OS << "0x" << Twine::utohexstr(Entry.first) << " -> " 393 << "0x" << Twine::utohexstr(Val); 394 if (IsBranch) 395 OS << " (branch)"; 396 else 397 OS << formatv(" hash: {0:x}", BBHashMap.getBBHash(Val)); 398 OS << "\n"; 399 } 400 OS << "\n"; 401 } 402 const size_t NumColdParts = ColdPartSource.size(); 403 if (!NumColdParts) 404 return; 405 406 OS << NumColdParts << " cold mappings:\n"; 407 for (const auto &Entry : ColdPartSource) { 408 OS << "0x" << Twine::utohexstr(Entry.first) << " -> " 409 << Twine::utohexstr(Entry.second) << "\n"; 410 } 411 OS << "\n"; 412 } 413 414 uint64_t BoltAddressTranslation::translate(uint64_t FuncAddress, 415 uint64_t Offset, 416 bool IsBranchSrc) const { 417 auto Iter = Maps.find(FuncAddress); 418 if (Iter == Maps.end()) 419 return Offset; 420 421 const MapTy &Map = Iter->second; 422 auto KeyVal = Map.upper_bound(Offset); 423 if (KeyVal == Map.begin()) 424 return Offset; 425 426 --KeyVal; 427 428 const uint32_t Val = KeyVal->second >> 1; // dropping BRANCHENTRY bit 429 // Branch source addresses are translated to the first instruction of the 430 // source BB to avoid accounting for modifications BOLT may have made in the 431 // BB regarding deletion/addition of instructions. 432 if (IsBranchSrc) 433 return Val; 434 return Offset - KeyVal->first + Val; 435 } 436 437 std::optional<BoltAddressTranslation::FallthroughListTy> 438 BoltAddressTranslation::getFallthroughsInTrace(uint64_t FuncAddress, 439 uint64_t From, 440 uint64_t To) const { 441 SmallVector<std::pair<uint64_t, uint64_t>, 16> Res; 442 443 // Filter out trivial case 444 if (From >= To) 445 return Res; 446 447 From -= FuncAddress; 448 To -= FuncAddress; 449 450 auto Iter = Maps.find(FuncAddress); 451 if (Iter == Maps.end()) 452 return std::nullopt; 453 454 const MapTy &Map = Iter->second; 455 auto FromIter = Map.upper_bound(From); 456 if (FromIter == Map.begin()) 457 return Res; 458 // Skip instruction entries, to create fallthroughs we are only interested in 459 // BB boundaries 460 do { 461 if (FromIter == Map.begin()) 462 return Res; 463 --FromIter; 464 } while (FromIter->second & BRANCHENTRY); 465 466 auto ToIter = Map.upper_bound(To); 467 if (ToIter == Map.begin()) 468 return Res; 469 --ToIter; 470 if (FromIter->first >= ToIter->first) 471 return Res; 472 473 for (auto Iter = FromIter; Iter != ToIter;) { 474 const uint32_t Src = Iter->first; 475 if (Iter->second & BRANCHENTRY) { 476 ++Iter; 477 continue; 478 } 479 480 ++Iter; 481 while (Iter->second & BRANCHENTRY && Iter != ToIter) 482 ++Iter; 483 if (Iter->second & BRANCHENTRY) 484 break; 485 Res.emplace_back(Src, Iter->first); 486 } 487 488 return Res; 489 } 490 491 uint64_t BoltAddressTranslation::fetchParentAddress(uint64_t Address) const { 492 auto Iter = ColdPartSource.find(Address); 493 if (Iter == ColdPartSource.end()) 494 return 0; 495 return Iter->second; 496 } 497 498 bool BoltAddressTranslation::enabledFor( 499 llvm::object::ELFObjectFileBase *InputFile) const { 500 for (const SectionRef &Section : InputFile->sections()) { 501 Expected<StringRef> SectionNameOrErr = Section.getName(); 502 if (Error E = SectionNameOrErr.takeError()) 503 continue; 504 505 if (SectionNameOrErr.get() == SECTION_NAME) 506 return true; 507 } 508 return false; 509 } 510 511 void BoltAddressTranslation::saveMetadata(BinaryContext &BC) { 512 for (BinaryFunction &BF : llvm::make_second_range(BC.getBinaryFunctions())) { 513 // We don't need a translation table if the body of the function hasn't 514 // changed 515 if (BF.isIgnored() || (!BC.HasRelocations && !BF.isSimple())) 516 continue; 517 // Prepare function and block hashes 518 FuncHashes.addEntry(BF.getAddress(), BF.computeHash()); 519 BF.computeBlockHashes(); 520 BBHashMapTy &BBHashMap = getBBHashMap(BF.getAddress()); 521 // Set BF/BB metadata 522 for (const BinaryBasicBlock &BB : BF) 523 BBHashMap.addEntry(BB.getInputOffset(), BB.getIndex(), BB.getHash()); 524 } 525 } 526 527 } // namespace bolt 528 } // namespace llvm 529