1 | //===- bolt/Profile/BoltAddressTranslation.cpp ----------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "bolt/Profile/BoltAddressTranslation.h" |
10 | #include "bolt/Core/BinaryFunction.h" |
11 | #include "llvm/ADT/APInt.h" |
12 | #include "llvm/Support/Errc.h" |
13 | #include "llvm/Support/Error.h" |
14 | #include "llvm/Support/LEB128.h" |
15 | |
16 | #define DEBUG_TYPE "bolt-bat" |
17 | |
18 | namespace llvm { |
19 | namespace bolt { |
20 | |
21 | const char *BoltAddressTranslation::SECTION_NAME = ".note.bolt_bat" ; |
22 | |
23 | void BoltAddressTranslation::writeEntriesForBB( |
24 | MapTy &Map, const BinaryBasicBlock &BB, uint64_t FuncInputAddress, |
25 | uint64_t FuncOutputAddress) const { |
26 | const uint64_t BBOutputOffset = |
27 | BB.getOutputAddressRange().first - FuncOutputAddress; |
28 | const uint32_t BBInputOffset = BB.getInputOffset(); |
29 | |
30 | // Every output BB must track back to an input BB for profile collection |
31 | // in bolted binaries. If we are missing an offset, it means this block was |
32 | // created by a pass. We will skip writing any entries for it, and this means |
33 | // any traffic happening in this block will map to the previous block in the |
34 | // layout. This covers the case where an input basic block is split into two, |
35 | // and the second one lacks any offset. |
36 | if (BBInputOffset == BinaryBasicBlock::INVALID_OFFSET) |
37 | return; |
38 | |
39 | LLVM_DEBUG(dbgs() << "BB " << BB.getName() << "\n" ); |
40 | LLVM_DEBUG(dbgs() << " Key: " << Twine::utohexstr(BBOutputOffset) |
41 | << " Val: " << Twine::utohexstr(BBInputOffset) << "\n" ); |
42 | // NB: in `writeEntriesForBB` we use the input address because hashes are |
43 | // saved early in `saveMetadata` before output addresses are assigned. |
44 | const BBHashMapTy &BBHashMap = getBBHashMap(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 | |
78 | void BoltAddressTranslation::write(const BinaryContext &BC, raw_ostream &OS) { |
79 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Writing BOLT Address Translation Tables\n" ); |
80 | for (auto &BFI : BC.getBinaryFunctions()) { |
81 | const BinaryFunction &Function = BFI.second; |
82 | const uint64_t InputAddress = Function.getAddress(); |
83 | const uint64_t OutputAddress = Function.getOutputAddress(); |
84 | // We don't need a translation table if the body of the function hasn't |
85 | // changed |
86 | if (Function.isIgnored() || (!BC.HasRelocations && !Function.isSimple())) |
87 | continue; |
88 | |
89 | uint32_t NumSecondaryEntryPoints = 0; |
90 | Function.forEachEntryPoint(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 | |
155 | APInt 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 | |
170 | size_t BoltAddressTranslation::getNumEqualOffsets(const MapTy &Map, |
171 | uint32_t Skew) const { |
172 | size_t EqualOffsets = 0; |
173 | for (const std::pair<const uint32_t, uint32_t> &KeyVal : Map) { |
174 | const uint32_t OutputOffset = KeyVal.first; |
175 | const uint32_t InputOffset = KeyVal.second >> 1; |
176 | if (OutputOffset == InputOffset - Skew) |
177 | ++EqualOffsets; |
178 | else |
179 | break; |
180 | } |
181 | return EqualOffsets; |
182 | } |
183 | |
184 | template <bool Cold> |
185 | void BoltAddressTranslation::writeMaps(uint64_t &PrevAddress, raw_ostream &OS) { |
186 | const uint32_t NumFuncs = |
187 | llvm::count_if(llvm::make_first_range(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 | |
294 | std::error_code BoltAddressTranslation::parse(raw_ostream &OS, StringRef Buf) { |
295 | DataExtractor DE = DataExtractor(Buf, true, 8); |
296 | uint64_t Offset = 0; |
297 | if (Buf.size() < 12) |
298 | return make_error_code(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 | |
321 | template <bool Cold> |
322 | void BoltAddressTranslation::(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 | |
437 | void BoltAddressTranslation::dump(raw_ostream &OS) const { |
438 | const size_t NumTables = Maps.size(); |
439 | OS << "BAT tables for " << NumTables << " functions:\n" ; |
440 | for (const auto &MapEntry : Maps) { |
441 | const uint64_t Address = MapEntry.first; |
442 | const uint64_t HotAddress = fetchParentAddress(Address); |
443 | const bool IsHotFunction = HotAddress == 0; |
444 | OS << "Function Address: 0x" << Twine::utohexstr(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 | |
489 | uint64_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 | |
512 | std::optional<BoltAddressTranslation::FallthroughListTy> |
513 | BoltAddressTranslation::getFallthroughsInTrace(uint64_t FuncAddress, |
514 | uint64_t From, |
515 | uint64_t To) const { |
516 | SmallVector<std::pair<uint64_t, uint64_t>, 16> Res; |
517 | |
518 | // Filter out trivial case |
519 | if (From >= To) |
520 | return Res; |
521 | |
522 | From -= FuncAddress; |
523 | To -= FuncAddress; |
524 | |
525 | auto Iter = Maps.find(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 | |
566 | bool BoltAddressTranslation::enabledFor( |
567 | llvm::object::ELFObjectFileBase *InputFile) const { |
568 | for (const SectionRef &Section : InputFile->sections()) { |
569 | Expected<StringRef> SectionNameOrErr = Section.getName(); |
570 | if (Error E = SectionNameOrErr.takeError()) |
571 | continue; |
572 | |
573 | if (SectionNameOrErr.get() == SECTION_NAME) |
574 | return true; |
575 | } |
576 | return false; |
577 | } |
578 | |
579 | void BoltAddressTranslation::saveMetadata(BinaryContext &BC) { |
580 | for (BinaryFunction &BF : llvm::make_second_range(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 | |
596 | unsigned |
597 | BoltAddressTranslation::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 | |
611 | std::pair<const BinaryFunction *, unsigned> |
612 | BoltAddressTranslation::translateSymbol(const BinaryContext &BC, |
613 | const MCSymbol &Symbol, |
614 | uint32_t Offset) const { |
615 | // The symbol could be a secondary entry in a cold fragment. |
616 | uint64_t SymbolValue = cantFail(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 | |