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

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