| //===- bolt/Profile/BoltAddressTranslation.cpp ----------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "bolt/Profile/BoltAddressTranslation.h" |
| #include "bolt/Core/BinaryFunction.h" |
| #include "llvm/ADT/APInt.h" |
| #include "llvm/Support/Errc.h" |
| #include "llvm/Support/Error.h" |
| #include "llvm/Support/LEB128.h" |
| |
| #define DEBUG_TYPE "bolt-bat" |
| |
| namespace llvm { |
| namespace bolt { |
| |
| const char *BoltAddressTranslation::SECTION_NAME = ".note.bolt_bat"; |
| |
| void BoltAddressTranslation::writeEntriesForBB( |
| MapTy &Map, const BinaryBasicBlock &BB, uint64_t FuncInputAddress, |
| uint64_t FuncOutputAddress) const { |
| const uint64_t BBOutputOffset = |
| BB.getOutputAddressRange().first - FuncOutputAddress; |
| const uint32_t BBInputOffset = BB.getInputOffset(); |
| |
| // Every output BB must track back to an input BB for profile collection |
| // in bolted binaries. If we are missing an offset, it means this block was |
| // created by a pass. We will skip writing any entries for it, and this means |
| // any traffic happening in this block will map to the previous block in the |
| // layout. This covers the case where an input basic block is split into two, |
| // and the second one lacks any offset. |
| if (BBInputOffset == BinaryBasicBlock::INVALID_OFFSET) |
| return; |
| |
| LLVM_DEBUG(dbgs() << "BB " << BB.getName() << "\n"); |
| LLVM_DEBUG(dbgs() << " Key: " << Twine::utohexstr(BBOutputOffset) |
| << " Val: " << Twine::utohexstr(BBInputOffset) << "\n"); |
| // NB: in `writeEntriesForBB` we use the input address because hashes are |
| // saved early in `saveMetadata` before output addresses are assigned. |
| const BBHashMapTy &BBHashMap = getBBHashMap(FuncInputAddress); |
| (void)BBHashMap; |
| LLVM_DEBUG( |
| dbgs() << formatv(" Hash: {0:x}\n", BBHashMap.getBBHash(BBInputOffset))); |
| LLVM_DEBUG( |
| dbgs() << formatv(" Index: {0}\n", BBHashMap.getBBIndex(BBInputOffset))); |
| // In case of conflicts (same Key mapping to different Vals), the last |
| // update takes precedence. Of course it is not ideal to have conflicts and |
| // those happen when we have an empty BB that either contained only |
| // NOPs or a jump to the next block (successor). Either way, the successor |
| // and this deleted block will both share the same output address (the same |
| // key), and we need to map back. We choose here to privilege the successor by |
| // allowing it to overwrite the previously inserted key in the map. |
| Map.emplace(BBOutputOffset, BBInputOffset << 1); |
| |
| const auto &IOAddressMap = |
| BB.getFunction()->getBinaryContext().getIOAddressMap(); |
| |
| for (const auto &[InputOffset, Sym] : BB.getLocSyms()) { |
| const auto InputAddress = BB.getFunction()->getAddress() + InputOffset; |
| const auto OutputAddress = IOAddressMap.lookup(InputAddress); |
| assert(OutputAddress && "Unknown instruction address"); |
| const auto OutputOffset = *OutputAddress - FuncOutputAddress; |
| |
| // Is this the first instruction in the BB? No need to duplicate the entry. |
| if (OutputOffset == BBOutputOffset) |
| continue; |
| |
| LLVM_DEBUG(dbgs() << " Key: " << Twine::utohexstr(OutputOffset) << " Val: " |
| << Twine::utohexstr(InputOffset) << " (branch)\n"); |
| Map.emplace(OutputOffset, (InputOffset << 1) | BRANCHENTRY); |
| } |
| } |
| |
| void BoltAddressTranslation::write(const BinaryContext &BC, raw_ostream &OS) { |
| LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Writing BOLT Address Translation Tables\n"); |
| for (auto &BFI : BC.getBinaryFunctions()) { |
| const BinaryFunction &Function = BFI.second; |
| const uint64_t InputAddress = Function.getAddress(); |
| const uint64_t OutputAddress = Function.getOutputAddress(); |
| // We don't need a translation table if the body of the function hasn't |
| // changed |
| if (Function.isIgnored() || (!BC.HasRelocations && !Function.isSimple())) |
| continue; |
| |
| uint32_t NumSecondaryEntryPoints = 0; |
| Function.forEachEntryPoint([&](uint64_t Offset, const MCSymbol *) { |
| if (!Offset) |
| return true; |
| ++NumSecondaryEntryPoints; |
| SecondaryEntryPointsMap[OutputAddress].push_back(Offset); |
| return true; |
| }); |
| |
| LLVM_DEBUG(dbgs() << "Function name: " << Function.getPrintName() << "\n"); |
| LLVM_DEBUG(dbgs() << " Address reference: 0x" |
| << Twine::utohexstr(Function.getOutputAddress()) << "\n"); |
| LLVM_DEBUG(dbgs() << formatv(" Hash: {0:x}\n", getBFHash(InputAddress))); |
| LLVM_DEBUG(dbgs() << " Secondary Entry Points: " << NumSecondaryEntryPoints |
| << '\n'); |
| |
| MapTy Map; |
| for (const BinaryBasicBlock *const BB : |
| Function.getLayout().getMainFragment()) |
| writeEntriesForBB(Map, *BB, InputAddress, OutputAddress); |
| // Add entries for deleted blocks. They are still required for correct BB |
| // mapping of branches modified by SCTC. By convention, they would have the |
| // end of the function as output address. |
| const BBHashMapTy &BBHashMap = getBBHashMap(InputAddress); |
| if (BBHashMap.size() != Function.size()) { |
| const uint64_t EndOffset = Function.getOutputSize(); |
| std::unordered_set<uint32_t> MappedInputOffsets; |
| for (const BinaryBasicBlock &BB : Function) |
| MappedInputOffsets.emplace(BB.getInputOffset()); |
| for (const auto &[InputOffset, _] : BBHashMap) |
| if (!llvm::is_contained(MappedInputOffsets, InputOffset)) |
| Map.emplace(EndOffset, InputOffset << 1); |
| } |
| Maps.emplace(Function.getOutputAddress(), std::move(Map)); |
| ReverseMap.emplace(OutputAddress, InputAddress); |
| |
| if (!Function.isSplit()) |
| continue; |
| |
| // Split maps |
| LLVM_DEBUG(dbgs() << " Cold part\n"); |
| for (const FunctionFragment &FF : |
| Function.getLayout().getSplitFragments()) { |
| // Skip empty fragments to avoid adding zero-address entries to maps. |
| if (FF.empty()) |
| continue; |
| ColdPartSource.emplace(FF.getAddress(), Function.getOutputAddress()); |
| Map.clear(); |
| for (const BinaryBasicBlock *const BB : FF) |
| writeEntriesForBB(Map, *BB, InputAddress, FF.getAddress()); |
| |
| Maps.emplace(FF.getAddress(), std::move(Map)); |
| } |
| } |
| |
| // Output addresses are delta-encoded |
| uint64_t PrevAddress = 0; |
| writeMaps</*Cold=*/false>(PrevAddress, OS); |
| writeMaps</*Cold=*/true>(PrevAddress, OS); |
| |
| BC.outs() << "BOLT-INFO: Wrote " << Maps.size() << " BAT maps\n"; |
| BC.outs() << "BOLT-INFO: Wrote " << FuncHashes.getNumFunctions() |
| << " function and " << FuncHashes.getNumBasicBlocks() |
| << " basic block hashes\n"; |
| } |
| |
| APInt BoltAddressTranslation::calculateBranchEntriesBitMask( |
| MapTy &Map, size_t EqualElems) const { |
| APInt BitMask(alignTo(EqualElems, 8), 0); |
| size_t Index = 0; |
| for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) { |
| if (Index == EqualElems) |
| break; |
| const uint32_t OutputOffset = KeyVal.second; |
| if (OutputOffset & BRANCHENTRY) |
| BitMask.setBit(Index); |
| ++Index; |
| } |
| return BitMask; |
| } |
| |
| size_t BoltAddressTranslation::getNumEqualOffsets(const MapTy &Map, |
| uint32_t Skew) const { |
| size_t EqualOffsets = 0; |
| for (const std::pair<const uint32_t, uint32_t> &KeyVal : Map) { |
| const uint32_t OutputOffset = KeyVal.first; |
| const uint32_t InputOffset = KeyVal.second >> 1; |
| if (OutputOffset == InputOffset - Skew) |
| ++EqualOffsets; |
| else |
| break; |
| } |
| return EqualOffsets; |
| } |
| |
| template <bool Cold> |
| void BoltAddressTranslation::writeMaps(uint64_t &PrevAddress, raw_ostream &OS) { |
| const uint32_t NumFuncs = |
| llvm::count_if(llvm::make_first_range(Maps), [&](const uint64_t Address) { |
| return Cold == ColdPartSource.count(Address); |
| }); |
| encodeULEB128(NumFuncs, OS); |
| LLVM_DEBUG(dbgs() << "Writing " << NumFuncs << (Cold ? " cold" : "") |
| << " functions for BAT.\n"); |
| size_t PrevIndex = 0; |
| for (auto &MapEntry : Maps) { |
| const uint64_t Address = MapEntry.first; |
| // Only process cold fragments in cold mode, and vice versa. |
| if (Cold != ColdPartSource.count(Address)) |
| continue; |
| // NB: in `writeMaps` we use the input address because hashes are saved |
| // early in `saveMetadata` before output addresses are assigned. |
| const uint64_t HotInputAddress = |
| ReverseMap[Cold ? ColdPartSource[Address] : Address]; |
| MapTy &Map = MapEntry.second; |
| const uint32_t NumEntries = Map.size(); |
| LLVM_DEBUG(dbgs() << "Writing " << NumEntries << " entries for 0x" |
| << Twine::utohexstr(Address) << ".\n"); |
| encodeULEB128(Address - PrevAddress, OS); |
| PrevAddress = Address; |
| const uint32_t NumSecondaryEntryPoints = |
| SecondaryEntryPointsMap.count(Address) |
| ? SecondaryEntryPointsMap[Address].size() |
| : 0; |
| uint32_t Skew = 0; |
| if (Cold) { |
| auto HotEntryIt = llvm::lower_bound(HotFuncs, ColdPartSource[Address]); |
| assert(HotEntryIt != HotFuncs.end()); |
| size_t HotIndex = std::distance(HotFuncs.begin(), HotEntryIt); |
| encodeULEB128(HotIndex - PrevIndex, OS); |
| PrevIndex = HotIndex; |
| // Skew of all input offsets for cold fragments is simply the first input |
| // offset. |
| Skew = Map.begin()->second >> 1; |
| encodeULEB128(Skew, OS); |
| } else { |
| HotFuncs.push_back(Address); |
| // Function hash |
| size_t BFHash = getBFHash(HotInputAddress); |
| LLVM_DEBUG(dbgs() << "Hash: " << formatv("{0:x}\n", BFHash)); |
| OS.write(reinterpret_cast<char *>(&BFHash), 8); |
| // Number of basic blocks |
| size_t NumBasicBlocks = NumBasicBlocksMap[HotInputAddress]; |
| LLVM_DEBUG(dbgs() << "Basic blocks: " << NumBasicBlocks << '\n'); |
| encodeULEB128(NumBasicBlocks, OS); |
| // Secondary entry points |
| encodeULEB128(NumSecondaryEntryPoints, OS); |
| LLVM_DEBUG(dbgs() << "Secondary Entry Points: " << NumSecondaryEntryPoints |
| << '\n'); |
| } |
| encodeULEB128(NumEntries, OS); |
| // Encode the number of equal offsets (output = input - skew) in the |
| // beginning of the function. Only encode one offset in these cases. |
| const size_t EqualElems = getNumEqualOffsets(Map, Skew); |
| encodeULEB128(EqualElems, OS); |
| if (EqualElems) { |
| const size_t BranchEntriesBytes = alignTo(EqualElems, 8) / 8; |
| APInt BranchEntries = calculateBranchEntriesBitMask(Map, EqualElems); |
| OS.write(reinterpret_cast<const char *>(BranchEntries.getRawData()), |
| BranchEntriesBytes); |
| LLVM_DEBUG({ |
| dbgs() << "BranchEntries: "; |
| SmallString<8> BitMaskStr; |
| BranchEntries.toString(BitMaskStr, 2, false); |
| dbgs() << BitMaskStr << '\n'; |
| }); |
| } |
| const BBHashMapTy &BBHashMap = getBBHashMap(HotInputAddress); |
| size_t Index = 0; |
| uint64_t InOffset = 0; |
| size_t PrevBBIndex = 0; |
| // Output and Input addresses and delta-encoded |
| for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) { |
| const uint64_t OutputAddress = KeyVal.first + Address; |
| encodeULEB128(OutputAddress - PrevAddress, OS); |
| PrevAddress = OutputAddress; |
| if (Index++ >= EqualElems) |
| encodeSLEB128(KeyVal.second - InOffset, OS); |
| InOffset = KeyVal.second; // Keeping InOffset as if BRANCHENTRY is encoded |
| if ((InOffset & BRANCHENTRY) == 0) { |
| const bool IsBlock = BBHashMap.isInputBlock(InOffset >> 1); |
| unsigned BBIndex = IsBlock ? BBHashMap.getBBIndex(InOffset >> 1) : 0; |
| size_t BBHash = IsBlock ? BBHashMap.getBBHash(InOffset >> 1) : 0; |
| OS.write(reinterpret_cast<char *>(&BBHash), 8); |
| // Basic block index in the input binary |
| encodeULEB128(BBIndex - PrevBBIndex, OS); |
| PrevBBIndex = BBIndex; |
| LLVM_DEBUG(dbgs() << formatv("{0:x} -> {1:x} {2:x} {3}\n", KeyVal.first, |
| InOffset >> 1, BBHash, BBIndex)); |
| } |
| } |
| uint32_t PrevOffset = 0; |
| if (!Cold && NumSecondaryEntryPoints) { |
| LLVM_DEBUG(dbgs() << "Secondary entry points: "); |
| // Secondary entry point offsets, delta-encoded |
| for (uint32_t Offset : SecondaryEntryPointsMap[Address]) { |
| encodeULEB128(Offset - PrevOffset, OS); |
| LLVM_DEBUG(dbgs() << formatv("{0:x} ", Offset)); |
| PrevOffset = Offset; |
| } |
| LLVM_DEBUG(dbgs() << '\n'); |
| } |
| } |
| } |
| |
| std::error_code BoltAddressTranslation::parse(raw_ostream &OS, StringRef Buf) { |
| DataExtractor DE = DataExtractor(Buf, true, 8); |
| uint64_t Offset = 0; |
| if (Buf.size() < 12) |
| return make_error_code(llvm::errc::io_error); |
| |
| const uint32_t NameSz = DE.getU32(&Offset); |
| const uint32_t DescSz = DE.getU32(&Offset); |
| const uint32_t Type = DE.getU32(&Offset); |
| |
| if (Type != BinarySection::NT_BOLT_BAT || |
| Buf.size() + Offset < alignTo(NameSz, 4) + DescSz) |
| return make_error_code(llvm::errc::io_error); |
| |
| StringRef Name = Buf.slice(Offset, Offset + NameSz); |
| Offset = alignTo(Offset + NameSz, 4); |
| if (!Name.starts_with("BOLT")) |
| return make_error_code(llvm::errc::io_error); |
| |
| Error Err(Error::success()); |
| uint64_t PrevAddress = 0; |
| parseMaps</*Cold=*/false>(PrevAddress, DE, Offset, Err); |
| parseMaps</*Cold=*/true>(PrevAddress, DE, Offset, Err); |
| OS << "BOLT-INFO: Parsed " << Maps.size() << " BAT entries\n"; |
| return errorToErrorCode(std::move(Err)); |
| } |
| |
| template <bool Cold> |
| void BoltAddressTranslation::parseMaps(uint64_t &PrevAddress, DataExtractor &DE, |
| uint64_t &Offset, Error &Err) { |
| const uint32_t NumFunctions = DE.getULEB128(&Offset, &Err); |
| LLVM_DEBUG(dbgs() << "Parsing " << NumFunctions << (Cold ? " cold" : "") |
| << " functions\n"); |
| size_t HotIndex = 0; |
| for (uint32_t I = 0; I < NumFunctions; ++I) { |
| const uint64_t Address = PrevAddress + DE.getULEB128(&Offset, &Err); |
| uint64_t HotAddress = Cold ? 0 : Address; |
| PrevAddress = Address; |
| uint32_t SecondaryEntryPoints = 0; |
| uint64_t ColdInputSkew = 0; |
| if (Cold) { |
| HotIndex += DE.getULEB128(&Offset, &Err); |
| HotAddress = HotFuncs[HotIndex]; |
| ColdPartSource.emplace(Address, HotAddress); |
| ColdInputSkew = DE.getULEB128(&Offset, &Err); |
| } else { |
| HotFuncs.push_back(Address); |
| // Function hash |
| const size_t FuncHash = DE.getU64(&Offset, &Err); |
| FuncHashes.addEntry(Address, FuncHash); |
| LLVM_DEBUG(dbgs() << formatv("{0:x}: hash {1:x}\n", Address, FuncHash)); |
| // Number of basic blocks |
| const size_t NumBasicBlocks = DE.getULEB128(&Offset, &Err); |
| NumBasicBlocksMap.emplace(Address, NumBasicBlocks); |
| LLVM_DEBUG(dbgs() << formatv("{0:x}: #bbs {1}, {2} bytes\n", Address, |
| NumBasicBlocks, |
| getULEB128Size(NumBasicBlocks))); |
| // Secondary entry points |
| SecondaryEntryPoints = DE.getULEB128(&Offset, &Err); |
| LLVM_DEBUG( |
| dbgs() << formatv("{0:x}: secondary entry points {1}, {2} bytes\n", |
| Address, SecondaryEntryPoints, |
| getULEB128Size(SecondaryEntryPoints))); |
| } |
| const uint32_t NumEntries = DE.getULEB128(&Offset, &Err); |
| // Equal offsets. |
| const size_t EqualElems = DE.getULEB128(&Offset, &Err); |
| APInt BEBitMask; |
| LLVM_DEBUG(dbgs() << formatv("Equal offsets: {0}, {1} bytes\n", EqualElems, |
| getULEB128Size(EqualElems))); |
| if (EqualElems) { |
| const size_t BranchEntriesBytes = alignTo(EqualElems, 8) / 8; |
| BEBitMask = APInt(alignTo(EqualElems, 8), 0); |
| LoadIntFromMemory( |
| BEBitMask, |
| reinterpret_cast<const uint8_t *>( |
| DE.getBytes(&Offset, BranchEntriesBytes, &Err).data()), |
| BranchEntriesBytes); |
| LLVM_DEBUG({ |
| dbgs() << "BEBitMask: "; |
| SmallString<8> BitMaskStr; |
| BEBitMask.toString(BitMaskStr, 2, false); |
| dbgs() << BitMaskStr << ", " << BranchEntriesBytes << " bytes\n"; |
| }); |
| } |
| MapTy Map; |
| |
| LLVM_DEBUG(dbgs() << "Parsing " << NumEntries << " entries for 0x" |
| << Twine::utohexstr(Address) << "\n"); |
| uint64_t InputOffset = 0; |
| size_t BBIndex = 0; |
| for (uint32_t J = 0; J < NumEntries; ++J) { |
| const uint64_t OutputDelta = DE.getULEB128(&Offset, &Err); |
| const uint64_t OutputAddress = PrevAddress + OutputDelta; |
| const uint64_t OutputOffset = OutputAddress - Address; |
| PrevAddress = OutputAddress; |
| int64_t InputDelta = 0; |
| if (J < EqualElems) { |
| InputOffset = ((OutputOffset + ColdInputSkew) << 1) | BEBitMask[J]; |
| } else { |
| InputDelta = DE.getSLEB128(&Offset, &Err); |
| InputOffset += InputDelta; |
| } |
| Map.insert(std::pair<uint32_t, uint32_t>(OutputOffset, InputOffset)); |
| size_t BBHash = 0; |
| size_t BBIndexDelta = 0; |
| const bool IsBranchEntry = InputOffset & BRANCHENTRY; |
| if (!IsBranchEntry) { |
| BBHash = DE.getU64(&Offset, &Err); |
| BBIndexDelta = DE.getULEB128(&Offset, &Err); |
| BBIndex += BBIndexDelta; |
| // Map basic block hash to hot fragment by input offset |
| getBBHashMap(HotAddress).addEntry(InputOffset >> 1, BBIndex, BBHash); |
| } |
| LLVM_DEBUG({ |
| dbgs() << formatv( |
| "{0:x} -> {1:x} ({2}/{3}b -> {4}/{5}b), {6:x}", OutputOffset, |
| InputOffset, OutputDelta, getULEB128Size(OutputDelta), InputDelta, |
| (J < EqualElems) ? 0 : getSLEB128Size(InputDelta), OutputAddress); |
| if (!IsBranchEntry) { |
| dbgs() << formatv(" {0:x} {1}/{2}b", BBHash, BBIndex, |
| getULEB128Size(BBIndexDelta)); |
| } |
| dbgs() << '\n'; |
| }); |
| } |
| Maps.insert(std::pair<uint64_t, MapTy>(Address, Map)); |
| if (!Cold && SecondaryEntryPoints) { |
| uint32_t EntryPointOffset = 0; |
| LLVM_DEBUG(dbgs() << "Secondary entry points: "); |
| for (uint32_t EntryPointId = 0; EntryPointId != SecondaryEntryPoints; |
| ++EntryPointId) { |
| uint32_t OffsetDelta = DE.getULEB128(&Offset, &Err); |
| EntryPointOffset += OffsetDelta; |
| SecondaryEntryPointsMap[Address].push_back(EntryPointOffset); |
| LLVM_DEBUG(dbgs() << formatv("{0:x}/{1}b ", EntryPointOffset, |
| getULEB128Size(OffsetDelta))); |
| } |
| LLVM_DEBUG(dbgs() << '\n'); |
| } |
| } |
| } |
| |
| void BoltAddressTranslation::dump(raw_ostream &OS) const { |
| const size_t NumTables = Maps.size(); |
| OS << "BAT tables for " << NumTables << " functions:\n"; |
| for (const auto &MapEntry : Maps) { |
| const uint64_t Address = MapEntry.first; |
| const uint64_t HotAddress = fetchParentAddress(Address); |
| const bool IsHotFunction = HotAddress == 0; |
| OS << "Function Address: 0x" << Twine::utohexstr(Address); |
| if (IsHotFunction) |
| OS << formatv(", hash: {0:x}", getBFHash(Address)); |
| OS << "\n"; |
| OS << "BB mappings:\n"; |
| const BBHashMapTy &BBHashMap = |
| getBBHashMap(HotAddress ? HotAddress : Address); |
| for (const auto &Entry : MapEntry.second) { |
| const bool IsBranch = Entry.second & BRANCHENTRY; |
| const uint32_t Val = Entry.second >> 1; // dropping BRANCHENTRY bit |
| OS << "0x" << Twine::utohexstr(Entry.first) << " -> " |
| << "0x" << Twine::utohexstr(Val); |
| if (IsBranch) |
| OS << " (branch)"; |
| else |
| OS << formatv(" hash: {0:x}", BBHashMap.getBBHash(Val)); |
| OS << "\n"; |
| } |
| if (IsHotFunction) { |
| auto NumBasicBlocksIt = NumBasicBlocksMap.find(Address); |
| assert(NumBasicBlocksIt != NumBasicBlocksMap.end()); |
| OS << "NumBlocks: " << NumBasicBlocksIt->second << '\n'; |
| } |
| auto SecondaryEntryPointsIt = SecondaryEntryPointsMap.find(Address); |
| if (SecondaryEntryPointsIt != SecondaryEntryPointsMap.end()) { |
| const std::vector<uint32_t> &SecondaryEntryPoints = |
| SecondaryEntryPointsIt->second; |
| OS << SecondaryEntryPoints.size() << " secondary entry points:\n"; |
| for (uint32_t EntryPointOffset : SecondaryEntryPoints) |
| OS << formatv("{0:x}\n", EntryPointOffset); |
| } |
| OS << "\n"; |
| } |
| const size_t NumColdParts = ColdPartSource.size(); |
| if (!NumColdParts) |
| return; |
| |
| OS << NumColdParts << " cold mappings:\n"; |
| for (const auto &Entry : ColdPartSource) { |
| OS << "0x" << Twine::utohexstr(Entry.first) << " -> " |
| << Twine::utohexstr(Entry.second) << "\n"; |
| } |
| OS << "\n"; |
| } |
| |
| uint64_t BoltAddressTranslation::translate(uint64_t FuncAddress, |
| uint64_t Offset, |
| bool IsBranchSrc) const { |
| auto Iter = Maps.find(FuncAddress); |
| if (Iter == Maps.end()) |
| return Offset; |
| |
| const MapTy &Map = Iter->second; |
| auto KeyVal = Map.upper_bound(Offset); |
| if (KeyVal == Map.begin()) |
| return Offset; |
| |
| --KeyVal; |
| |
| const uint32_t Val = KeyVal->second >> 1; // dropping BRANCHENTRY bit |
| // Branch source addresses are translated to the first instruction of the |
| // source BB to avoid accounting for modifications BOLT may have made in the |
| // BB regarding deletion/addition of instructions. |
| if (IsBranchSrc) |
| return Val; |
| return Offset - KeyVal->first + Val; |
| } |
| |
| std::optional<BoltAddressTranslation::FallthroughListTy> |
| BoltAddressTranslation::getFallthroughsInTrace(uint64_t FuncAddress, |
| uint64_t From, |
| uint64_t To) const { |
| SmallVector<std::pair<uint64_t, uint64_t>, 16> Res; |
| |
| // Filter out trivial case |
| if (From >= To) |
| return Res; |
| |
| From -= FuncAddress; |
| To -= FuncAddress; |
| |
| auto Iter = Maps.find(FuncAddress); |
| if (Iter == Maps.end()) |
| return std::nullopt; |
| |
| const MapTy &Map = Iter->second; |
| auto FromIter = Map.upper_bound(From); |
| if (FromIter == Map.begin()) |
| return Res; |
| // Skip instruction entries, to create fallthroughs we are only interested in |
| // BB boundaries |
| do { |
| if (FromIter == Map.begin()) |
| return Res; |
| --FromIter; |
| } while (FromIter->second & BRANCHENTRY); |
| |
| auto ToIter = Map.upper_bound(To); |
| if (ToIter == Map.begin()) |
| return Res; |
| --ToIter; |
| if (FromIter->first >= ToIter->first) |
| return Res; |
| |
| for (auto Iter = FromIter; Iter != ToIter;) { |
| const uint32_t Src = Iter->first; |
| if (Iter->second & BRANCHENTRY) { |
| ++Iter; |
| continue; |
| } |
| |
| ++Iter; |
| while (Iter->second & BRANCHENTRY && Iter != ToIter) |
| ++Iter; |
| if (Iter->second & BRANCHENTRY) |
| break; |
| Res.emplace_back(Src, Iter->first); |
| } |
| |
| return Res; |
| } |
| |
| bool BoltAddressTranslation::enabledFor( |
| llvm::object::ELFObjectFileBase *InputFile) const { |
| for (const SectionRef &Section : InputFile->sections()) { |
| Expected<StringRef> SectionNameOrErr = Section.getName(); |
| if (Error E = SectionNameOrErr.takeError()) |
| continue; |
| |
| if (SectionNameOrErr.get() == SECTION_NAME) |
| return true; |
| } |
| return false; |
| } |
| |
| void BoltAddressTranslation::saveMetadata(BinaryContext &BC) { |
| for (BinaryFunction &BF : llvm::make_second_range(BC.getBinaryFunctions())) { |
| // We don't need a translation table if the body of the function hasn't |
| // changed |
| if (BF.isIgnored() || (!BC.HasRelocations && !BF.isSimple())) |
| continue; |
| // Prepare function and block hashes |
| FuncHashes.addEntry(BF.getAddress(), BF.computeHash()); |
| BF.computeBlockHashes(); |
| BBHashMapTy &BBHashMap = getBBHashMap(BF.getAddress()); |
| // Set BF/BB metadata |
| for (const BinaryBasicBlock &BB : BF) |
| BBHashMap.addEntry(BB.getInputOffset(), BB.getIndex(), BB.getHash()); |
| NumBasicBlocksMap.emplace(BF.getAddress(), BF.size()); |
| } |
| } |
| |
| unsigned |
| BoltAddressTranslation::getSecondaryEntryPointId(uint64_t Address, |
| uint32_t Offset) const { |
| auto FunctionIt = SecondaryEntryPointsMap.find(Address); |
| if (FunctionIt == SecondaryEntryPointsMap.end()) |
| return 0; |
| const std::vector<uint32_t> &Offsets = FunctionIt->second; |
| auto OffsetIt = std::find(Offsets.begin(), Offsets.end(), Offset); |
| if (OffsetIt == Offsets.end()) |
| return 0; |
| // Adding one here because main entry point is not stored in BAT, and |
| // enumeration for secondary entry points starts with 1. |
| return OffsetIt - Offsets.begin() + 1; |
| } |
| |
| std::pair<const BinaryFunction *, unsigned> |
| BoltAddressTranslation::translateSymbol(const BinaryContext &BC, |
| const MCSymbol &Symbol, |
| uint32_t Offset) const { |
| // The symbol could be a secondary entry in a cold fragment. |
| uint64_t SymbolValue = cantFail(errorOrToExpected(BC.getSymbolValue(Symbol))); |
| |
| const BinaryFunction *Callee = BC.getFunctionForSymbol(&Symbol); |
| assert(Callee); |
| |
| // Containing function, not necessarily the same as symbol value. |
| const uint64_t CalleeAddress = Callee->getAddress(); |
| const uint32_t OutputOffset = SymbolValue - CalleeAddress; |
| |
| const uint64_t ParentAddress = fetchParentAddress(CalleeAddress); |
| const uint64_t HotAddress = ParentAddress ? ParentAddress : CalleeAddress; |
| |
| const BinaryFunction *ParentBF = BC.getBinaryFunctionAtAddress(HotAddress); |
| |
| const uint32_t InputOffset = |
| translate(CalleeAddress, OutputOffset, /*IsBranchSrc*/ false) + Offset; |
| |
| unsigned SecondaryEntryId{0}; |
| if (InputOffset) |
| SecondaryEntryId = getSecondaryEntryPointId(HotAddress, InputOffset); |
| |
| return std::pair(ParentBF, SecondaryEntryId); |
| } |
| |
| } // namespace bolt |
| } // namespace llvm |
