642 lines · cpp
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-exception6//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 18namespace llvm {19namespace bolt {20 21const char *BoltAddressTranslation::SECTION_NAME = ".note.bolt_bat";22 23void 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 collection31 // in bolted binaries. If we are missing an offset, it means this block was32 // created by a pass. We will skip writing any entries for it, and this means33 // any traffic happening in this block will map to the previous block in the34 // 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 are43 // 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 last51 // update takes precedence. Of course it is not ideal to have conflicts and52 // those happen when we have an empty BB that either contained only53 // NOPs or a jump to the next block (successor). Either way, the successor54 // and this deleted block will both share the same output address (the same55 // key), and we need to map back. We choose here to privilege the successor by56 // 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 78void 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't85 // changed86 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: " << NumSecondaryEntryPoints103 << '\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 BB110 // mapping of branches modified by SCTC. By convention, they would have the111 // 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 maps129 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-encoded145 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 155APInt 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 170size_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 else179 break;180 }181 return EqualOffsets;182}183 184template <bool Cold>185void 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 saved200 // 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 input221 // offset.222 Skew = Map.begin()->second >> 1;223 encodeULEB128(Skew, OS);224 } else {225 HotFuncs.push_back(Address);226 // Function hash227 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 blocks231 size_t NumBasicBlocks = NumBasicBlocksMap[HotInputAddress];232 LLVM_DEBUG(dbgs() << "Basic blocks: " << NumBasicBlocks << '\n');233 encodeULEB128(NumBasicBlocks, OS);234 // Secondary entry points235 encodeULEB128(NumSecondaryEntryPoints, OS);236 LLVM_DEBUG(dbgs() << "Secondary Entry Points: " << NumSecondaryEntryPoints237 << '\n');238 }239 encodeULEB128(NumEntries, OS);240 // Encode the number of equal offsets (output = input - skew) in the241 // 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-encoded261 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 encoded268 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 binary274 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-encoded284 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 294std::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 321template <bool Cold>322void 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 hash342 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 blocks346 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 points352 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 offset406 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 437void 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 bit454 OS << "0x" << Twine::utohexstr(Entry.first) << " -> "455 << "0x" << Twine::utohexstr(Val);456 if (IsBranch)457 OS << " (branch)";458 else459 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 489uint64_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 bit504 // Branch source addresses are translated to the first instruction of the505 // source BB to avoid accounting for modifications BOLT may have made in the506 // BB regarding deletion/addition of instructions.507 if (IsBranchSrc)508 return Val;509 return Offset - KeyVal->first + Val;510}511 512std::optional<BoltAddressTranslation::FallthroughListTy>513BoltAddressTranslation::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 case519 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 in534 // BB boundaries535 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->second >> 1;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->second >> 1);561 }562 563 return Res;564}565 566bool 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 579void 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't582 // changed583 if (BF.isIgnored() || (!BC.HasRelocations && !BF.isSimple()))584 continue;585 // Prepare function and block hashes586 FuncHashes.addEntry(BF.getAddress(), BF.computeHash());587 BF.computeBlockHashes();588 BBHashMapTy &BBHashMap = getBBHashMap(BF.getAddress());589 // Set BF/BB metadata590 for (const BinaryBasicBlock &BB : BF)591 BBHashMap.addEntry(BB.getInputOffset(), BB.getIndex(), BB.getHash());592 NumBasicBlocksMap.emplace(BF.getAddress(), BF.size());593 }594}595 596unsigned597BoltAddressTranslation::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 = llvm::find(Offsets, Offset);604 if (OffsetIt == Offsets.end())605 return 0;606 // Adding one here because main entry point is not stored in BAT, and607 // enumeration for secondary entry points starts with 1.608 return OffsetIt - Offsets.begin() + 1;609}610 611std::pair<const BinaryFunction *, unsigned>612BoltAddressTranslation::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 bolt641} // namespace llvm642