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
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 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(FuncOutputAddress: 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(args: BBOutputOffset, args: 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(args: OutputOffset, args: (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't
85 // changed
86 if (Function.isIgnored() || (!BC.HasRelocations && !Function.isSimple()))
87 continue;
88
89 uint32_t NumSecondaryEntryPoints = 0;
90 Function.forEachEntryPoint(Callback: [&](uint64_t Offset, const MCSymbol *) {
91 if (!Offset)
92 return true;
93 ++NumSecondaryEntryPoints;
94 SecondaryEntryPointsMap[OutputAddress].push_back(x: 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: *BB, FuncInputAddress: InputAddress, FuncOutputAddress: 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(FuncOutputAddress: 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(args: BB.getInputOffset());
118 for (const auto &[InputOffset, _] : BBHashMap)
119 if (!llvm::is_contained(Range&: MappedInputOffsets, Element: InputOffset))
120 Map.emplace(args: EndOffset, args: InputOffset << 1);
121 }
122 Maps.emplace(args: Function.getOutputAddress(), args: std::move(Map));
123 ReverseMap.emplace(args: OutputAddress, args: 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(args: FF.getAddress(), args: Function.getOutputAddress());
136 Map.clear();
137 for (const BinaryBasicBlock *const BB : FF)
138 writeEntriesForBB(Map, BB: *BB, FuncInputAddress: InputAddress, FuncOutputAddress: FF.getAddress());
139
140 Maps.emplace(args: FF.getAddress(), args: 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
155APInt BoltAddressTranslation::calculateBranchEntriesBitMask(
156 MapTy &Map, size_t EqualElems) const {
157 APInt BitMask(alignTo(Value: EqualElems, Align: 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 else
179 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(c&: Maps), [&](const uint64_t Address) {
188 return Cold == ColdPartSource.count(x: Address);
189 });
190 encodeULEB128(Value: 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(x: 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(Value: Address - PrevAddress, OS);
208 PrevAddress = Address;
209 const uint32_t NumSecondaryEntryPoints =
210 SecondaryEntryPointsMap.count(x: Address)
211 ? SecondaryEntryPointsMap[Address].size()
212 : 0;
213 uint32_t Skew = 0;
214 if (Cold) {
215 auto HotEntryIt = llvm::lower_bound(Range&: HotFuncs, Value&: ColdPartSource[Address]);
216 assert(HotEntryIt != HotFuncs.end());
217 size_t HotIndex = std::distance(first: HotFuncs.begin(), last: HotEntryIt);
218 encodeULEB128(Value: 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(Value: Skew, OS);
224 } else {
225 HotFuncs.push_back(x: Address);
226 // Function hash
227 size_t BFHash = getBFHash(FuncOutputAddress: HotInputAddress);
228 LLVM_DEBUG(dbgs() << "Hash: " << formatv("{0:x}\n", BFHash));
229 OS.write(Ptr: reinterpret_cast<char *>(&BFHash), Size: 8);
230 // Number of basic blocks
231 size_t NumBasicBlocks = NumBasicBlocksMap[HotInputAddress];
232 LLVM_DEBUG(dbgs() << "Basic blocks: " << NumBasicBlocks << '\n');
233 encodeULEB128(Value: NumBasicBlocks, OS);
234 // Secondary entry points
235 encodeULEB128(Value: NumSecondaryEntryPoints, OS);
236 LLVM_DEBUG(dbgs() << "Secondary Entry Points: " << NumSecondaryEntryPoints
237 << '\n');
238 }
239 encodeULEB128(Value: 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(Value: EqualElems, OS);
244 if (EqualElems) {
245 const size_t BranchEntriesBytes = alignTo(Value: EqualElems, Align: 8) / 8;
246 APInt BranchEntries = calculateBranchEntriesBitMask(Map, EqualElems);
247 OS.write(Ptr: reinterpret_cast<const char *>(BranchEntries.getRawData()),
248 Size: 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(FuncOutputAddress: 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(Value: OutputAddress - PrevAddress, OS);
264 PrevAddress = OutputAddress;
265 if (Index++ >= EqualElems)
266 encodeSLEB128(Value: 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(InputOffset: InOffset >> 1);
270 unsigned BBIndex = IsBlock ? BBHashMap.getBBIndex(BBInputOffset: InOffset >> 1) : 0;
271 size_t BBHash = IsBlock ? BBHashMap.getBBHash(BBInputOffset: InOffset >> 1) : 0;
272 OS.write(Ptr: reinterpret_cast<char *>(&BBHash), Size: 8);
273 // Basic block index in the input binary
274 encodeULEB128(Value: 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(Value: 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(E: llvm::errc::io_error);
299
300 const uint32_t NameSz = DE.getU32(offset_ptr: &Offset);
301 const uint32_t DescSz = DE.getU32(offset_ptr: &Offset);
302 const uint32_t Type = DE.getU32(offset_ptr: &Offset);
303
304 if (Type != BinarySection::NT_BOLT_BAT ||
305 Buf.size() + Offset < alignTo(Value: NameSz, Align: 4) + DescSz)
306 return make_error_code(E: llvm::errc::io_error);
307
308 StringRef Name = Buf.slice(Start: Offset, End: Offset + NameSz);
309 Offset = alignTo(Value: Offset + NameSz, Align: 4);
310 if (!Name.starts_with(Prefix: "BOLT"))
311 return make_error_code(E: 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(Err: 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_ptr: &Offset, Err: &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_ptr: &Offset, Err: &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_ptr: &Offset, Err: &Err);
336 HotAddress = HotFuncs[HotIndex];
337 ColdPartSource.emplace(args: Address, args&: HotAddress);
338 ColdInputSkew = DE.getULEB128(offset_ptr: &Offset, Err: &Err);
339 } else {
340 HotFuncs.push_back(x: Address);
341 // Function hash
342 const size_t FuncHash = DE.getU64(offset_ptr: &Offset, Err: &Err);
343 FuncHashes.addEntry(FuncOutputAddress: Address, BFHash: 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_ptr: &Offset, Err: &Err);
347 NumBasicBlocksMap.emplace(args: Address, args: 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_ptr: &Offset, Err: &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_ptr: &Offset, Err: &Err);
359 // Equal offsets.
360 const size_t EqualElems = DE.getULEB128(offset_ptr: &Offset, Err: &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(Value: EqualElems, Align: 8) / 8;
366 BEBitMask = APInt(alignTo(Value: EqualElems, Align: 8), 0);
367 LoadIntFromMemory(
368 IntVal&: BEBitMask,
369 Src: reinterpret_cast<const uint8_t *>(
370 DE.getBytes(OffsetPtr: &Offset, Length: BranchEntriesBytes, Err: &Err).data()),
371 LoadBytes: 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_ptr: &Offset, Err: &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(OffsetPtr: &Offset, Err: &Err);
395 InputOffset += InputDelta;
396 }
397 Map.insert(x: 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_ptr: &Offset, Err: &Err);
403 BBIndexDelta = DE.getULEB128(offset_ptr: &Offset, Err: &Err);
404 BBIndex += BBIndexDelta;
405 // Map basic block hash to hot fragment by input offset
406 getBBHashMap(FuncOutputAddress: HotAddress).addEntry(BBInputOffset: 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(x: 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_ptr: &Offset, Err: &Err);
427 EntryPointOffset += OffsetDelta;
428 SecondaryEntryPointsMap[Address].push_back(x: 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(Val: Address);
445 if (IsHotFunction)
446 OS << formatv(Fmt: ", hash: {0:x}", Vals: getBFHash(FuncOutputAddress: Address));
447 OS << "\n";
448 OS << "BB mappings:\n";
449 const BBHashMapTy &BBHashMap =
450 getBBHashMap(FuncOutputAddress: 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(Val: Entry.first) << " -> "
455 << "0x" << Twine::utohexstr(Val);
456 if (IsBranch)
457 OS << " (branch)";
458 else
459 OS << formatv(Fmt: " hash: {0:x}", Vals: BBHashMap.getBBHash(BBInputOffset: Val));
460 OS << "\n";
461 }
462 if (IsHotFunction) {
463 auto NumBasicBlocksIt = NumBasicBlocksMap.find(x: Address);
464 assert(NumBasicBlocksIt != NumBasicBlocksMap.end());
465 OS << "NumBlocks: " << NumBasicBlocksIt->second << '\n';
466 }
467 auto SecondaryEntryPointsIt = SecondaryEntryPointsMap.find(x: 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(Fmt: "{0:x}\n", Vals&: 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(Val: Entry.first) << " -> "
484 << Twine::utohexstr(Val: 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(x: FuncAddress);
493 if (Iter == Maps.end())
494 return Offset;
495
496 const MapTy &Map = Iter->second;
497 auto KeyVal = Map.upper_bound(x: 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
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 case
519 if (From >= To)
520 return Res;
521
522 From -= FuncAddress;
523 To -= FuncAddress;
524
525 auto Iter = Maps.find(x: FuncAddress);
526 if (Iter == Maps.end())
527 return std::nullopt;
528
529 const MapTy &Map = Iter->second;
530 auto FromIter = Map.upper_bound(x: 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(x: 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(Args: Src, Args: Iter->first);
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(c&: 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(FuncOutputAddress: BF.getAddress(), BFHash: BF.computeHash());
587 BF.computeBlockHashes();
588 BBHashMapTy &BBHashMap = getBBHashMap(FuncOutputAddress: BF.getAddress());
589 // Set BF/BB metadata
590 for (const BinaryBasicBlock &BB : BF)
591 BBHashMap.addEntry(BBInputOffset: BB.getInputOffset(), BBIndex: BB.getIndex(), BBHash: BB.getHash());
592 NumBasicBlocksMap.emplace(args: BF.getAddress(), args: BF.size());
593 }
594}
595
596unsigned
597BoltAddressTranslation::getSecondaryEntryPointId(uint64_t Address,
598 uint32_t Offset) const {
599 auto FunctionIt = SecondaryEntryPointsMap.find(x: Address);
600 if (FunctionIt == SecondaryEntryPointsMap.end())
601 return 0;
602 const std::vector<uint32_t> &Offsets = FunctionIt->second;
603 auto OffsetIt = llvm::find(Range: Offsets, Val: 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
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(ValOrErr: errorOrToExpected(EO: BC.getSymbolValue(Symbol)));
617
618 const BinaryFunction *Callee = BC.getFunctionForSymbol(Symbol: &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(Address: CalleeAddress);
626 const uint64_t HotAddress = ParentAddress ? ParentAddress : CalleeAddress;
627
628 const BinaryFunction *ParentBF = BC.getBinaryFunctionAtAddress(Address: HotAddress);
629
630 const uint32_t InputOffset =
631 translate(FuncAddress: CalleeAddress, Offset: OutputOffset, /*IsBranchSrc*/ false) + Offset;
632
633 unsigned SecondaryEntryId{0};
634 if (InputOffset)
635 SecondaryEntryId = getSecondaryEntryPointId(Address: HotAddress, Offset: InputOffset);
636
637 return std::pair(ParentBF, SecondaryEntryId);
638}
639
640} // namespace bolt
641} // namespace llvm
642

source code of bolt/lib/Profile/BoltAddressTranslation.cpp