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