1 | //===- bolt/Core/BinaryFunction.h - Low-level function ----------*- C++ -*-===// |
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 | // This file contains the declaration of the BinaryFunction class. It represents |
10 | // a function at the lowest IR level. Typically, a BinaryFunction represents a |
11 | // function object in a compiled and linked binary file. However, a |
12 | // BinaryFunction can also be constructed manually, e.g. for injecting into a |
13 | // binary file. |
14 | // |
15 | // A BinaryFunction could be in one of the several states described in |
16 | // BinaryFunction::State. While in the disassembled state, it will contain a |
17 | // list of instructions with their offsets. In the CFG state, it will contain a |
18 | // list of BinaryBasicBlocks that form a control-flow graph. This state is best |
19 | // suited for binary analysis and optimizations. However, sometimes it's |
20 | // impossible to build the precise CFG due to the ambiguity of indirect |
21 | // branches. |
22 | // |
23 | //===----------------------------------------------------------------------===// |
24 | |
25 | #ifndef BOLT_CORE_BINARY_FUNCTION_H |
26 | #define BOLT_CORE_BINARY_FUNCTION_H |
27 | |
28 | #include "bolt/Core/BinaryBasicBlock.h" |
29 | #include "bolt/Core/BinaryContext.h" |
30 | #include "bolt/Core/BinaryDomTree.h" |
31 | #include "bolt/Core/BinaryLoop.h" |
32 | #include "bolt/Core/BinarySection.h" |
33 | #include "bolt/Core/DebugData.h" |
34 | #include "bolt/Core/FunctionLayout.h" |
35 | #include "bolt/Core/JumpTable.h" |
36 | #include "bolt/Core/MCPlus.h" |
37 | #include "bolt/Utils/NameResolver.h" |
38 | #include "llvm/ADT/STLExtras.h" |
39 | #include "llvm/ADT/SmallString.h" |
40 | #include "llvm/ADT/StringRef.h" |
41 | #include "llvm/ADT/iterator.h" |
42 | #include "llvm/ADT/iterator_range.h" |
43 | #include "llvm/BinaryFormat/Dwarf.h" |
44 | #include "llvm/MC/MCContext.h" |
45 | #include "llvm/MC/MCDwarf.h" |
46 | #include "llvm/MC/MCInst.h" |
47 | #include "llvm/MC/MCSymbol.h" |
48 | #include "llvm/Object/ObjectFile.h" |
49 | #include "llvm/Support/RWMutex.h" |
50 | #include "llvm/Support/raw_ostream.h" |
51 | #include <algorithm> |
52 | #include <iterator> |
53 | #include <limits> |
54 | #include <unordered_map> |
55 | #include <utility> |
56 | #include <vector> |
57 | |
58 | using namespace llvm::object; |
59 | |
60 | namespace llvm { |
61 | |
62 | class DWARFUnit; |
63 | |
64 | namespace bolt { |
65 | |
66 | using InputOffsetToAddressMapTy = std::unordered_multimap<uint64_t, uint64_t>; |
67 | |
68 | /// Types of macro-fusion alignment corrections. |
69 | enum MacroFusionType { MFT_NONE, MFT_HOT, MFT_ALL }; |
70 | |
71 | enum IndirectCallPromotionType : char { |
72 | ICP_NONE, /// Don't perform ICP. |
73 | ICP_CALLS, /// Perform ICP on indirect calls. |
74 | ICP_JUMP_TABLES, /// Perform ICP on jump tables. |
75 | ICP_ALL /// Perform ICP on calls and jump tables. |
76 | }; |
77 | |
78 | /// Hash functions supported for BF/BB hashing. |
79 | enum class HashFunction : char { |
80 | StdHash, /// std::hash, implementation is platform-dependent. Provided for |
81 | /// backwards compatibility. |
82 | XXH3, /// llvm::xxh3_64bits, the default. |
83 | Default = XXH3, |
84 | }; |
85 | |
86 | /// Information on a single indirect call to a particular callee. |
87 | struct IndirectCallProfile { |
88 | MCSymbol *Symbol; |
89 | uint32_t Offset; |
90 | uint64_t Count; |
91 | uint64_t Mispreds; |
92 | |
93 | IndirectCallProfile(MCSymbol *Symbol, uint64_t Count, uint64_t Mispreds, |
94 | uint32_t Offset = 0) |
95 | : Symbol(Symbol), Offset(Offset), Count(Count), Mispreds(Mispreds) {} |
96 | |
97 | bool operator==(const IndirectCallProfile &Other) const { |
98 | return Symbol == Other.Symbol && Offset == Other.Offset; |
99 | } |
100 | }; |
101 | |
102 | /// Aggregated information for an indirect call site. |
103 | using IndirectCallSiteProfile = SmallVector<IndirectCallProfile, 4>; |
104 | |
105 | inline raw_ostream &operator<<(raw_ostream &OS, |
106 | const bolt::IndirectCallSiteProfile &ICSP) { |
107 | std::string TempString; |
108 | raw_string_ostream SS(TempString); |
109 | |
110 | const char *Sep = "\n " ; |
111 | uint64_t TotalCount = 0; |
112 | uint64_t TotalMispreds = 0; |
113 | for (const IndirectCallProfile &CSP : ICSP) { |
114 | SS << Sep << "{ " << (CSP.Symbol ? CSP.Symbol->getName() : "<unknown>" ) |
115 | << ": " << CSP.Count << " (" << CSP.Mispreds << " misses) }" ; |
116 | Sep = ",\n " ; |
117 | TotalCount += CSP.Count; |
118 | TotalMispreds += CSP.Mispreds; |
119 | } |
120 | SS.flush(); |
121 | |
122 | OS << TotalCount << " (" << TotalMispreds << " misses) :" << TempString; |
123 | return OS; |
124 | } |
125 | |
126 | /// BinaryFunction is a representation of machine-level function. |
127 | /// |
128 | /// In the input binary, an instance of BinaryFunction can represent a fragment |
129 | /// of a function if the higher-level function was split, e.g. into hot and cold |
130 | /// parts. The fragment containing the main entry point is called a parent |
131 | /// or the main fragment. |
132 | class BinaryFunction { |
133 | public: |
134 | enum class State : char { |
135 | Empty = 0, /// Function body is empty. |
136 | Disassembled, /// Function have been disassembled. |
137 | CFG, /// Control flow graph has been built. |
138 | CFG_Finalized, /// CFG is finalized. No optimizations allowed. |
139 | EmittedCFG, /// Instructions have been emitted to output. |
140 | Emitted, /// Same as above plus CFG is destroyed. |
141 | }; |
142 | |
143 | /// Types of profile the function can use. Could be a combination. |
144 | enum { |
145 | PF_NONE = 0, /// No profile. |
146 | PF_LBR = 1, /// Profile is based on last branch records. |
147 | PF_SAMPLE = 2, /// Non-LBR sample-based profile. |
148 | PF_MEMEVENT = 4, /// Profile has mem events. |
149 | }; |
150 | |
151 | /// Struct for tracking exception handling ranges. |
152 | struct CallSite { |
153 | const MCSymbol *Start; |
154 | const MCSymbol *End; |
155 | const MCSymbol *LP; |
156 | uint64_t Action; |
157 | }; |
158 | |
159 | using CallSitesList = SmallVector<std::pair<FragmentNum, CallSite>, 0>; |
160 | using CallSitesRange = iterator_range<CallSitesList::const_iterator>; |
161 | |
162 | using IslandProxiesType = |
163 | std::map<BinaryFunction *, std::map<const MCSymbol *, MCSymbol *>>; |
164 | |
165 | struct IslandInfo { |
166 | /// Temporary holder of offsets that are data markers (used in AArch) |
167 | /// It is possible to have data in code sections. To ease the identification |
168 | /// of data in code sections, the ABI requires the symbol table to have |
169 | /// symbols named "$d" identifying the start of data inside code and "$x" |
170 | /// identifying the end of a chunk of data inside code. DataOffsets contain |
171 | /// all offsets of $d symbols and CodeOffsets all offsets of $x symbols. |
172 | std::set<uint64_t> DataOffsets; |
173 | std::set<uint64_t> CodeOffsets; |
174 | |
175 | /// List of relocations associated with data in the constant island |
176 | std::map<uint64_t, Relocation> Relocations; |
177 | |
178 | /// Set true if constant island contains dynamic relocations, which may |
179 | /// happen if binary is linked with -z notext option. |
180 | bool HasDynamicRelocations{false}; |
181 | |
182 | /// Offsets in function that are data values in a constant island identified |
183 | /// after disassembling |
184 | std::map<uint64_t, MCSymbol *> Offsets; |
185 | SmallPtrSet<MCSymbol *, 4> Symbols; |
186 | DenseMap<const MCSymbol *, BinaryFunction *> ProxySymbols; |
187 | DenseMap<const MCSymbol *, MCSymbol *> ColdSymbols; |
188 | /// Keeps track of other functions we depend on because there is a reference |
189 | /// to the constant islands in them. |
190 | IslandProxiesType Proxies, ColdProxies; |
191 | SmallPtrSet<BinaryFunction *, 1> Dependency; // The other way around |
192 | |
193 | mutable MCSymbol *FunctionConstantIslandLabel{nullptr}; |
194 | mutable MCSymbol *FunctionColdConstantIslandLabel{nullptr}; |
195 | |
196 | // Returns constant island alignment |
197 | uint16_t getAlignment() const { return sizeof(uint64_t); } |
198 | }; |
199 | |
200 | static constexpr uint64_t COUNT_NO_PROFILE = |
201 | BinaryBasicBlock::COUNT_NO_PROFILE; |
202 | |
203 | static const char TimerGroupName[]; |
204 | static const char TimerGroupDesc[]; |
205 | |
206 | using BasicBlockOrderType = SmallVector<BinaryBasicBlock *, 0>; |
207 | |
208 | /// Mark injected functions |
209 | bool IsInjected = false; |
210 | |
211 | using LSDATypeTableTy = SmallVector<uint64_t, 0>; |
212 | |
213 | /// List of DWARF CFI instructions. Original CFI from the binary must be |
214 | /// sorted w.r.t. offset that it appears. We rely on this to replay CFIs |
215 | /// if needed (to fix state after reordering BBs). |
216 | using CFIInstrMapType = SmallVector<MCCFIInstruction, 0>; |
217 | using cfi_iterator = CFIInstrMapType::iterator; |
218 | using const_cfi_iterator = CFIInstrMapType::const_iterator; |
219 | |
220 | private: |
221 | /// Current state of the function. |
222 | State CurrentState{State::Empty}; |
223 | |
224 | /// A list of symbols associated with the function entry point. |
225 | /// |
226 | /// Multiple symbols would typically result from identical code-folding |
227 | /// optimization. |
228 | typedef SmallVector<MCSymbol *, 1> SymbolListTy; |
229 | SymbolListTy Symbols; |
230 | |
231 | /// The list of names this function is known under. Used for fuzzy-matching |
232 | /// the function to its name in a profile, command line, etc. |
233 | SmallVector<std::string, 0> Aliases; |
234 | |
235 | /// Containing section in the input file. |
236 | BinarySection *OriginSection = nullptr; |
237 | |
238 | /// Address of the function in memory. Also could be an offset from |
239 | /// base address for position independent binaries. |
240 | uint64_t Address; |
241 | |
242 | /// Original size of the function. |
243 | uint64_t Size; |
244 | |
245 | /// Address of the function in output. |
246 | uint64_t OutputAddress{0}; |
247 | |
248 | /// Size of the function in the output file. |
249 | uint64_t OutputSize{0}; |
250 | |
251 | /// Maximum size this function is allowed to have. |
252 | uint64_t MaxSize{std::numeric_limits<uint64_t>::max()}; |
253 | |
254 | /// Alignment requirements for the function. |
255 | uint16_t Alignment{2}; |
256 | |
257 | /// Maximum number of bytes used for alignment of hot part of the function. |
258 | uint16_t MaxAlignmentBytes{0}; |
259 | |
260 | /// Maximum number of bytes used for alignment of cold part of the function. |
261 | uint16_t MaxColdAlignmentBytes{0}; |
262 | |
263 | const MCSymbol *PersonalityFunction{nullptr}; |
264 | uint8_t PersonalityEncoding{dwarf::DW_EH_PE_sdata4 | dwarf::DW_EH_PE_pcrel}; |
265 | |
266 | BinaryContext &BC; |
267 | |
268 | std::unique_ptr<BinaryLoopInfo> BLI; |
269 | std::unique_ptr<BinaryDominatorTree> BDT; |
270 | |
271 | /// All labels in the function that are referenced via relocations from |
272 | /// data objects. Typically these are jump table destinations and computed |
273 | /// goto labels. |
274 | std::set<uint64_t> ExternallyReferencedOffsets; |
275 | |
276 | /// Offsets of indirect branches with unknown destinations. |
277 | std::set<uint64_t> UnknownIndirectBranchOffsets; |
278 | |
279 | /// A set of local and global symbols corresponding to secondary entry points. |
280 | /// Each additional function entry point has a corresponding entry in the map. |
281 | /// The key is a local symbol corresponding to a basic block and the value |
282 | /// is a global symbol corresponding to an external entry point. |
283 | DenseMap<const MCSymbol *, MCSymbol *> SecondaryEntryPoints; |
284 | |
285 | /// False if the function is too complex to reconstruct its control |
286 | /// flow graph. |
287 | /// In relocation mode we still disassemble and re-assemble such functions. |
288 | bool IsSimple{true}; |
289 | |
290 | /// Indication that the function should be ignored for optimization purposes. |
291 | /// If we can skip emission of some functions, then ignored functions could |
292 | /// be not fully disassembled and will not be emitted. |
293 | bool IsIgnored{false}; |
294 | |
295 | /// Pseudo functions should not be disassembled or emitted. |
296 | bool IsPseudo{false}; |
297 | |
298 | /// True if the original function code has all necessary relocations to track |
299 | /// addresses of functions emitted to new locations. Typically set for |
300 | /// functions that we are not going to emit. |
301 | bool HasExternalRefRelocations{false}; |
302 | |
303 | /// True if the function has an indirect branch with unknown destination. |
304 | bool HasUnknownControlFlow{false}; |
305 | |
306 | /// The code from inside the function references one of the code locations |
307 | /// from the same function as a data, i.e. it's possible the label is used |
308 | /// inside an address calculation or could be referenced from outside. |
309 | bool HasInternalLabelReference{false}; |
310 | |
311 | /// In AArch64, preserve nops to maintain code equal to input (assuming no |
312 | /// optimizations are done). |
313 | bool PreserveNops{false}; |
314 | |
315 | /// Indicate if this function has associated exception handling metadata. |
316 | bool HasEHRanges{false}; |
317 | |
318 | /// True if the function uses DW_CFA_GNU_args_size CFIs. |
319 | bool UsesGnuArgsSize{false}; |
320 | |
321 | /// True if the function might have a profile available externally. |
322 | /// Used to check if processing of the function is required under certain |
323 | /// conditions. |
324 | bool HasProfileAvailable{false}; |
325 | |
326 | bool HasMemoryProfile{false}; |
327 | |
328 | /// Execution halts whenever this function is entered. |
329 | bool TrapsOnEntry{false}; |
330 | |
331 | /// True if the function is a fragment of another function. This means that |
332 | /// this function could only be entered via its parent or one of its sibling |
333 | /// fragments. It could be entered at any basic block. It can also return |
334 | /// the control to any basic block of its parent or its sibling. |
335 | bool IsFragment{false}; |
336 | |
337 | /// Indicate that the function body has SDT marker |
338 | bool HasSDTMarker{false}; |
339 | |
340 | /// Indicate that the function body has Pseudo Probe |
341 | bool HasPseudoProbe{BC.getUniqueSectionByName(SectionName: ".pseudo_probe_desc" ) && |
342 | BC.getUniqueSectionByName(SectionName: ".pseudo_probe" )}; |
343 | |
344 | /// True if the function uses ORC format for stack unwinding. |
345 | bool HasORC{false}; |
346 | |
347 | /// True if the original entry point was patched. |
348 | bool IsPatched{false}; |
349 | |
350 | /// True if the function contains explicit or implicit indirect branch to its |
351 | /// split fragments, e.g., split jump table, landing pad in split fragment |
352 | bool HasIndirectTargetToSplitFragment{false}; |
353 | |
354 | /// True if there are no control-flow edges with successors in other functions |
355 | /// (i.e. if tail calls have edges to function-local basic blocks). |
356 | /// Set to false by SCTC. Dynostats can't be reliably computed for |
357 | /// functions with non-canonical CFG. |
358 | /// This attribute is only valid when hasCFG() == true. |
359 | bool HasCanonicalCFG{true}; |
360 | |
361 | /// True if another function body was merged into this one. |
362 | bool HasFunctionsFoldedInto{false}; |
363 | |
364 | /// Name for the section this function code should reside in. |
365 | std::string CodeSectionName; |
366 | |
367 | /// Name for the corresponding cold code section. |
368 | std::string ColdCodeSectionName; |
369 | |
370 | /// Parent function fragment for split function fragments. |
371 | using FragmentsSetTy = SmallPtrSet<BinaryFunction *, 1>; |
372 | FragmentsSetTy ParentFragments; |
373 | |
374 | /// Indicate if the function body was folded into another function. |
375 | /// Used by ICF optimization. |
376 | BinaryFunction *FoldedIntoFunction{nullptr}; |
377 | |
378 | /// All fragments for a parent function. |
379 | FragmentsSetTy Fragments; |
380 | |
381 | /// The profile data for the number of times the function was executed. |
382 | uint64_t ExecutionCount{COUNT_NO_PROFILE}; |
383 | |
384 | /// Profile match ratio. |
385 | float ProfileMatchRatio{0.0f}; |
386 | |
387 | /// Raw branch count for this function in the profile. |
388 | uint64_t RawBranchCount{0}; |
389 | |
390 | /// Indicates the type of profile the function is using. |
391 | uint16_t ProfileFlags{PF_NONE}; |
392 | |
393 | /// True if the function's input profile data has been inaccurate but has |
394 | /// been adjusted by the profile inference algorithm. |
395 | bool HasInferredProfile{false}; |
396 | |
397 | /// For functions with mismatched profile we store all call profile |
398 | /// information at a function level (as opposed to tying it to |
399 | /// specific call sites). |
400 | IndirectCallSiteProfile AllCallSites; |
401 | |
402 | /// Score of the function (estimated number of instructions executed, |
403 | /// according to profile data). -1 if the score has not been calculated yet. |
404 | mutable int64_t FunctionScore{-1}; |
405 | |
406 | /// Original LSDA address for the function. |
407 | uint64_t LSDAAddress{0}; |
408 | |
409 | /// Original LSDA type encoding |
410 | unsigned LSDATypeEncoding{dwarf::DW_EH_PE_omit}; |
411 | |
412 | /// Containing compilation unit for the function. |
413 | DWARFUnit *DwarfUnit{nullptr}; |
414 | |
415 | /// Last computed hash value. Note that the value could be recomputed using |
416 | /// different parameters by every pass. |
417 | mutable uint64_t Hash{0}; |
418 | |
419 | /// For PLT functions it contains a symbol associated with a function |
420 | /// reference. It is nullptr for non-PLT functions. |
421 | const MCSymbol *PLTSymbol{nullptr}; |
422 | |
423 | /// Function order for streaming into the destination binary. |
424 | uint32_t Index{-1U}; |
425 | |
426 | /// Get basic block index assuming it belongs to this function. |
427 | unsigned getIndex(const BinaryBasicBlock *BB) const { |
428 | assert(BB->getIndex() < BasicBlocks.size()); |
429 | return BB->getIndex(); |
430 | } |
431 | |
432 | /// Release memory taken by the list. |
433 | template <typename T> BinaryFunction &clearList(T &List) { |
434 | T TempList; |
435 | TempList.swap(List); |
436 | return *this; |
437 | } |
438 | |
439 | /// Update the indices of all the basic blocks starting at StartIndex. |
440 | void updateBBIndices(const unsigned StartIndex); |
441 | |
442 | /// Annotate each basic block entry with its current CFI state. This is |
443 | /// run right after the construction of CFG while basic blocks are in their |
444 | /// original order. |
445 | void annotateCFIState(); |
446 | |
447 | /// Associate DW_CFA_GNU_args_size info with invoke instructions |
448 | /// (call instructions with non-empty landing pad). |
449 | void propagateGnuArgsSizeInfo(MCPlusBuilder::AllocatorIdTy AllocId); |
450 | |
451 | /// Synchronize branch instructions with CFG. |
452 | void postProcessBranches(); |
453 | |
454 | /// The address offset where we emitted the constant island, that is, the |
455 | /// chunk of data in the function code area (AArch only) |
456 | int64_t OutputDataOffset{0}; |
457 | int64_t OutputColdDataOffset{0}; |
458 | |
459 | /// Map labels to corresponding basic blocks. |
460 | DenseMap<const MCSymbol *, BinaryBasicBlock *> LabelToBB; |
461 | |
462 | using BranchListType = SmallVector<std::pair<uint32_t, uint32_t>, 0>; |
463 | BranchListType TakenBranches; /// All local taken branches. |
464 | BranchListType IgnoredBranches; /// Branches ignored by CFG purposes. |
465 | |
466 | /// Map offset in the function to a label. |
467 | /// Labels are used for building CFG for simple functions. For non-simple |
468 | /// function in relocation mode we need to emit them for relocations |
469 | /// referencing function internals to work (e.g. jump tables). |
470 | using LabelsMapType = std::map<uint32_t, MCSymbol *>; |
471 | LabelsMapType Labels; |
472 | |
473 | /// Temporary holder of instructions before CFG is constructed. |
474 | /// Map offset in the function to MCInst. |
475 | using InstrMapType = std::map<uint32_t, MCInst>; |
476 | InstrMapType Instructions; |
477 | |
478 | /// We don't decode Call Frame Info encoded in DWARF program state |
479 | /// machine. Instead we define a "CFI State" - a frame information that |
480 | /// is a result of executing FDE CFI program up to a given point. The |
481 | /// program consists of opaque Call Frame Instructions: |
482 | /// |
483 | /// CFI #0 |
484 | /// CFI #1 |
485 | /// .... |
486 | /// CFI #N |
487 | /// |
488 | /// When we refer to "CFI State K" - it corresponds to a row in an abstract |
489 | /// Call Frame Info table. This row is reached right before executing CFI #K. |
490 | /// |
491 | /// At any point of execution in a function we are in any one of (N + 2) |
492 | /// states described in the original FDE program. We can't have more states |
493 | /// without intelligent processing of CFIs. |
494 | /// |
495 | /// When the final layout of basic blocks is known, and we finalize CFG, |
496 | /// we modify the original program to make sure the same state could be |
497 | /// reached even when basic blocks containing CFI instructions are executed |
498 | /// in a different order. |
499 | CFIInstrMapType FrameInstructions; |
500 | |
501 | /// A map of restore state CFI instructions to their equivalent CFI |
502 | /// instructions that produce the same state, in order to eliminate |
503 | /// remember-restore CFI instructions when rewriting CFI. |
504 | DenseMap<int32_t, SmallVector<int32_t, 4>> FrameRestoreEquivalents; |
505 | |
506 | // For tracking exception handling ranges. |
507 | CallSitesList CallSites; |
508 | |
509 | /// Binary blobs representing action, type, and type index tables for this |
510 | /// function' LSDA (exception handling). |
511 | ArrayRef<uint8_t> LSDAActionTable; |
512 | ArrayRef<uint8_t> LSDATypeIndexTable; |
513 | |
514 | /// Vector of addresses of types referenced by LSDA. |
515 | LSDATypeTableTy LSDATypeTable; |
516 | |
517 | /// Vector of addresses of entries in LSDATypeTable used for indirect |
518 | /// addressing. |
519 | LSDATypeTableTy LSDATypeAddressTable; |
520 | |
521 | /// Marking for the beginnings of language-specific data areas for each |
522 | /// fragment of the function. |
523 | SmallVector<MCSymbol *, 0> LSDASymbols; |
524 | |
525 | /// Map to discover which CFIs are attached to a given instruction offset. |
526 | /// Maps an instruction offset into a FrameInstructions offset. |
527 | /// This is only relevant to the buildCFG phase and is discarded afterwards. |
528 | std::multimap<uint32_t, uint32_t> OffsetToCFI; |
529 | |
530 | /// List of CFI instructions associated with the CIE (common to more than one |
531 | /// function and that apply before the entry basic block). |
532 | CFIInstrMapType CIEFrameInstructions; |
533 | |
534 | /// All compound jump tables for this function. This duplicates what's stored |
535 | /// in the BinaryContext, but additionally it gives quick access for all |
536 | /// jump tables used by this function. |
537 | /// |
538 | /// <OriginalAddress> -> <JumpTable *> |
539 | std::map<uint64_t, JumpTable *> JumpTables; |
540 | |
541 | /// All jump table sites in the function before CFG is built. |
542 | SmallVector<std::pair<uint64_t, uint64_t>, 0> JTSites; |
543 | |
544 | /// List of relocations in this function. |
545 | std::map<uint64_t, Relocation> Relocations; |
546 | |
547 | /// Information on function constant islands. |
548 | std::unique_ptr<IslandInfo> Islands; |
549 | |
550 | // Blocks are kept sorted in the layout order. If we need to change the |
551 | // layout (if BasicBlocksLayout stores a different order than BasicBlocks), |
552 | // the terminating instructions need to be modified. |
553 | using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>; |
554 | BasicBlockListType BasicBlocks; |
555 | BasicBlockListType DeletedBasicBlocks; |
556 | |
557 | FunctionLayout Layout; |
558 | |
559 | /// BasicBlockOffsets are used during CFG construction to map from code |
560 | /// offsets to BinaryBasicBlocks. Any modifications made to the CFG |
561 | /// after initial construction are not reflected in this data structure. |
562 | using BasicBlockOffset = std::pair<uint64_t, BinaryBasicBlock *>; |
563 | struct CompareBasicBlockOffsets { |
564 | bool operator()(const BasicBlockOffset &A, |
565 | const BasicBlockOffset &B) const { |
566 | return A.first < B.first; |
567 | } |
568 | }; |
569 | SmallVector<BasicBlockOffset, 0> BasicBlockOffsets; |
570 | |
571 | SmallVector<MCSymbol *, 0> ColdSymbols; |
572 | |
573 | /// Symbol at the end of each fragment of a split function. |
574 | mutable SmallVector<MCSymbol *, 0> FunctionEndLabels; |
575 | |
576 | /// Unique number associated with the function. |
577 | uint64_t FunctionNumber; |
578 | |
579 | /// Count the number of functions created. |
580 | static uint64_t Count; |
581 | |
582 | /// Register alternative function name. |
583 | void addAlternativeName(std::string NewName) { |
584 | Aliases.push_back(Elt: std::move(NewName)); |
585 | } |
586 | |
587 | /// Return a label at a given \p Address in the function. If the label does |
588 | /// not exist - create it. Assert if the \p Address does not belong to |
589 | /// the function. If \p CreatePastEnd is true, then return the function |
590 | /// end label when the \p Address points immediately past the last byte |
591 | /// of the function. |
592 | /// NOTE: the function always returns a local (temp) symbol, even if there's |
593 | /// a global symbol that corresponds to an entry at this address. |
594 | MCSymbol *getOrCreateLocalLabel(uint64_t Address, bool CreatePastEnd = false); |
595 | |
596 | /// Register an data entry at a given \p Offset into the function. |
597 | void markDataAtOffset(uint64_t Offset) { |
598 | if (!Islands) |
599 | Islands = std::make_unique<IslandInfo>(); |
600 | Islands->DataOffsets.emplace(args&: Offset); |
601 | } |
602 | |
603 | /// Register an entry point at a given \p Offset into the function. |
604 | void markCodeAtOffset(uint64_t Offset) { |
605 | if (!Islands) |
606 | Islands = std::make_unique<IslandInfo>(); |
607 | Islands->CodeOffsets.emplace(args&: Offset); |
608 | } |
609 | |
610 | /// Register an internal offset in a function referenced from outside. |
611 | void registerReferencedOffset(uint64_t Offset) { |
612 | ExternallyReferencedOffsets.emplace(args&: Offset); |
613 | } |
614 | |
615 | /// True if there are references to internals of this function from data, |
616 | /// e.g. from jump tables. |
617 | bool hasInternalReference() const { |
618 | return !ExternallyReferencedOffsets.empty(); |
619 | } |
620 | |
621 | /// Return an entry ID corresponding to a symbol known to belong to |
622 | /// the function. |
623 | /// |
624 | /// Prefer to use BinaryContext::getFunctionForSymbol(EntrySymbol, &ID) |
625 | /// instead of calling this function directly. |
626 | uint64_t getEntryIDForSymbol(const MCSymbol *EntrySymbol) const; |
627 | |
628 | /// If the function represents a secondary split function fragment, set its |
629 | /// parent fragment to \p BF. |
630 | void addParentFragment(BinaryFunction &BF) { |
631 | assert(this != &BF); |
632 | assert(IsFragment && "function must be a fragment to have a parent" ); |
633 | ParentFragments.insert(Ptr: &BF); |
634 | } |
635 | |
636 | /// Register a child fragment for the main fragment of a split function. |
637 | void addFragment(BinaryFunction &BF) { |
638 | assert(this != &BF); |
639 | Fragments.insert(Ptr: &BF); |
640 | } |
641 | |
642 | void addInstruction(uint64_t Offset, MCInst &&Instruction) { |
643 | Instructions.emplace(args&: Offset, args: std::forward<MCInst>(t&: Instruction)); |
644 | } |
645 | |
646 | /// Convert CFI instructions to a standard form (remove remember/restore). |
647 | void normalizeCFIState(); |
648 | |
649 | /// Analyze and process indirect branch \p Instruction before it is |
650 | /// added to Instructions list. |
651 | IndirectBranchType processIndirectBranch(MCInst &Instruction, unsigned Size, |
652 | uint64_t Offset, |
653 | uint64_t &TargetAddress); |
654 | |
655 | BinaryFunction &operator=(const BinaryFunction &) = delete; |
656 | BinaryFunction(const BinaryFunction &) = delete; |
657 | |
658 | friend class MachORewriteInstance; |
659 | friend class RewriteInstance; |
660 | friend class BinaryContext; |
661 | friend class DataReader; |
662 | friend class DataAggregator; |
663 | |
664 | static std::string buildCodeSectionName(StringRef Name, |
665 | const BinaryContext &BC); |
666 | static std::string buildColdCodeSectionName(StringRef Name, |
667 | const BinaryContext &BC); |
668 | |
669 | /// Creation should be handled by RewriteInstance or BinaryContext |
670 | BinaryFunction(const std::string &Name, BinarySection &Section, |
671 | uint64_t Address, uint64_t Size, BinaryContext &BC) |
672 | : OriginSection(&Section), Address(Address), Size(Size), BC(BC), |
673 | CodeSectionName(buildCodeSectionName(Name, BC)), |
674 | ColdCodeSectionName(buildColdCodeSectionName(Name, BC)), |
675 | FunctionNumber(++Count) { |
676 | Symbols.push_back(Elt: BC.Ctx->getOrCreateSymbol(Name)); |
677 | } |
678 | |
679 | /// This constructor is used to create an injected function |
680 | BinaryFunction(const std::string &Name, BinaryContext &BC, bool IsSimple) |
681 | : Address(0), Size(0), BC(BC), IsSimple(IsSimple), |
682 | CodeSectionName(buildCodeSectionName(Name, BC)), |
683 | ColdCodeSectionName(buildColdCodeSectionName(Name, BC)), |
684 | FunctionNumber(++Count) { |
685 | Symbols.push_back(Elt: BC.Ctx->getOrCreateSymbol(Name)); |
686 | IsInjected = true; |
687 | } |
688 | |
689 | /// Create a basic block at a given \p Offset in the function and append it |
690 | /// to the end of list of blocks. Used during CFG construction only. |
691 | BinaryBasicBlock *addBasicBlockAt(uint64_t Offset, MCSymbol *Label) { |
692 | assert(CurrentState == State::Disassembled && |
693 | "Cannot add block with an offset in non-disassembled state." ); |
694 | assert(!getBasicBlockAtOffset(Offset) && |
695 | "Basic block already exists at the offset." ); |
696 | |
697 | BasicBlocks.emplace_back(Args: createBasicBlock(Label).release()); |
698 | BinaryBasicBlock *BB = BasicBlocks.back(); |
699 | |
700 | BB->setIndex(BasicBlocks.size() - 1); |
701 | BB->setOffset(Offset); |
702 | |
703 | BasicBlockOffsets.emplace_back(Args&: Offset, Args&: BB); |
704 | assert(llvm::is_sorted(BasicBlockOffsets, CompareBasicBlockOffsets()) && |
705 | llvm::is_sorted(blocks())); |
706 | |
707 | return BB; |
708 | } |
709 | |
710 | /// Clear state of the function that could not be disassembled or if its |
711 | /// disassembled state was later invalidated. |
712 | void clearDisasmState(); |
713 | |
714 | /// Release memory allocated for CFG and instructions. |
715 | /// We still keep basic blocks for address translation/mapping purposes. |
716 | void releaseCFG() { |
717 | for (BinaryBasicBlock *BB : BasicBlocks) |
718 | BB->releaseCFG(); |
719 | for (BinaryBasicBlock *BB : DeletedBasicBlocks) |
720 | BB->releaseCFG(); |
721 | |
722 | clearList(List&: CallSites); |
723 | clearList(List&: LSDATypeTable); |
724 | clearList(List&: LSDATypeAddressTable); |
725 | |
726 | clearList(List&: LabelToBB); |
727 | |
728 | if (!isMultiEntry()) |
729 | clearList(List&: Labels); |
730 | |
731 | clearList(List&: FrameInstructions); |
732 | clearList(List&: FrameRestoreEquivalents); |
733 | } |
734 | |
735 | public: |
736 | BinaryFunction(BinaryFunction &&) = default; |
737 | |
738 | using iterator = pointee_iterator<BasicBlockListType::iterator>; |
739 | using const_iterator = pointee_iterator<BasicBlockListType::const_iterator>; |
740 | using reverse_iterator = |
741 | pointee_iterator<BasicBlockListType::reverse_iterator>; |
742 | using const_reverse_iterator = |
743 | pointee_iterator<BasicBlockListType::const_reverse_iterator>; |
744 | |
745 | // CFG iterators. |
746 | iterator begin() { return BasicBlocks.begin(); } |
747 | const_iterator begin() const { return BasicBlocks.begin(); } |
748 | iterator end () { return BasicBlocks.end(); } |
749 | const_iterator end () const { return BasicBlocks.end(); } |
750 | |
751 | reverse_iterator rbegin() { return BasicBlocks.rbegin(); } |
752 | const_reverse_iterator rbegin() const { return BasicBlocks.rbegin(); } |
753 | reverse_iterator rend () { return BasicBlocks.rend(); } |
754 | const_reverse_iterator rend () const { return BasicBlocks.rend(); } |
755 | |
756 | size_t size() const { return BasicBlocks.size();} |
757 | bool empty() const { return BasicBlocks.empty(); } |
758 | const BinaryBasicBlock &front() const { return *BasicBlocks.front(); } |
759 | BinaryBasicBlock &front() { return *BasicBlocks.front(); } |
760 | const BinaryBasicBlock & back() const { return *BasicBlocks.back(); } |
761 | BinaryBasicBlock & back() { return *BasicBlocks.back(); } |
762 | inline iterator_range<iterator> blocks() { |
763 | return iterator_range<iterator>(begin(), end()); |
764 | } |
765 | inline iterator_range<const_iterator> blocks() const { |
766 | return iterator_range<const_iterator>(begin(), end()); |
767 | } |
768 | |
769 | // Iterators by pointer. |
770 | BasicBlockListType::iterator pbegin() { return BasicBlocks.begin(); } |
771 | BasicBlockListType::iterator pend() { return BasicBlocks.end(); } |
772 | |
773 | cfi_iterator cie_begin() { return CIEFrameInstructions.begin(); } |
774 | const_cfi_iterator cie_begin() const { return CIEFrameInstructions.begin(); } |
775 | cfi_iterator cie_end() { return CIEFrameInstructions.end(); } |
776 | const_cfi_iterator cie_end() const { return CIEFrameInstructions.end(); } |
777 | bool cie_empty() const { return CIEFrameInstructions.empty(); } |
778 | |
779 | inline iterator_range<cfi_iterator> cie() { |
780 | return iterator_range<cfi_iterator>(cie_begin(), cie_end()); |
781 | } |
782 | inline iterator_range<const_cfi_iterator> cie() const { |
783 | return iterator_range<const_cfi_iterator>(cie_begin(), cie_end()); |
784 | } |
785 | |
786 | /// Iterate over all jump tables associated with this function. |
787 | iterator_range<std::map<uint64_t, JumpTable *>::const_iterator> |
788 | jumpTables() const { |
789 | return make_range(x: JumpTables.begin(), y: JumpTables.end()); |
790 | } |
791 | |
792 | /// Return relocation associated with a given \p Offset in the function, |
793 | /// or nullptr if no such relocation exists. |
794 | const Relocation *getRelocationAt(uint64_t Offset) const { |
795 | assert(CurrentState == State::Empty && |
796 | "Relocations unavailable in the current function state." ); |
797 | auto RI = Relocations.find(x: Offset); |
798 | return (RI == Relocations.end()) ? nullptr : &RI->second; |
799 | } |
800 | |
801 | /// Return the first relocation in the function that starts at an address in |
802 | /// the [StartOffset, EndOffset) range. Return nullptr if no such relocation |
803 | /// exists. |
804 | const Relocation *getRelocationInRange(uint64_t StartOffset, |
805 | uint64_t EndOffset) const { |
806 | assert(CurrentState == State::Empty && |
807 | "Relocations unavailable in the current function state." ); |
808 | auto RI = Relocations.lower_bound(x: StartOffset); |
809 | if (RI != Relocations.end() && RI->first < EndOffset) |
810 | return &RI->second; |
811 | |
812 | return nullptr; |
813 | } |
814 | |
815 | /// Returns the raw binary encoding of this function. |
816 | ErrorOr<ArrayRef<uint8_t>> getData() const; |
817 | |
818 | BinaryFunction &updateState(BinaryFunction::State State) { |
819 | CurrentState = State; |
820 | return *this; |
821 | } |
822 | |
823 | FunctionLayout &getLayout() { return Layout; } |
824 | |
825 | const FunctionLayout &getLayout() const { return Layout; } |
826 | |
827 | /// Recompute landing pad information for the function and all its blocks. |
828 | void recomputeLandingPads(); |
829 | |
830 | /// Return a list of basic blocks sorted using DFS and update layout indices |
831 | /// using the same order. Does not modify the current layout. |
832 | BasicBlockListType dfs() const; |
833 | |
834 | /// Find the loops in the CFG of the function and store information about |
835 | /// them. |
836 | void calculateLoopInfo(); |
837 | |
838 | /// Calculate missed macro-fusion opportunities and update BinaryContext |
839 | /// stats. |
840 | void calculateMacroOpFusionStats(); |
841 | |
842 | /// Returns if BinaryDominatorTree has been constructed for this function. |
843 | bool hasDomTree() const { return BDT != nullptr; } |
844 | |
845 | BinaryDominatorTree &getDomTree() { return *BDT.get(); } |
846 | |
847 | /// Constructs DomTree for this function. |
848 | void constructDomTree(); |
849 | |
850 | /// Returns if loop detection has been run for this function. |
851 | bool hasLoopInfo() const { return BLI != nullptr; } |
852 | |
853 | const BinaryLoopInfo &getLoopInfo() { return *BLI.get(); } |
854 | |
855 | bool isLoopFree() { |
856 | if (!hasLoopInfo()) |
857 | calculateLoopInfo(); |
858 | return BLI->empty(); |
859 | } |
860 | |
861 | /// Print loop information about the function. |
862 | void printLoopInfo(raw_ostream &OS) const; |
863 | |
864 | /// View CFG in graphviz program |
865 | void viewGraph() const; |
866 | |
867 | /// Dump CFG in graphviz format |
868 | void dumpGraph(raw_ostream &OS) const; |
869 | |
870 | /// Dump CFG in graphviz format to file. |
871 | void dumpGraphToFile(std::string Filename) const; |
872 | |
873 | /// Dump CFG in graphviz format to a file with a filename that is derived |
874 | /// from the function name and Annotation strings. Useful for dumping the |
875 | /// CFG after an optimization pass. |
876 | void dumpGraphForPass(std::string Annotation = "" ) const; |
877 | |
878 | /// Return BinaryContext for the function. |
879 | const BinaryContext &getBinaryContext() const { return BC; } |
880 | |
881 | /// Return BinaryContext for the function. |
882 | BinaryContext &getBinaryContext() { return BC; } |
883 | |
884 | /// Attempt to validate CFG invariants. |
885 | bool validateCFG() const; |
886 | |
887 | BinaryBasicBlock *getBasicBlockForLabel(const MCSymbol *Label) { |
888 | return LabelToBB.lookup(Val: Label); |
889 | } |
890 | |
891 | const BinaryBasicBlock *getBasicBlockForLabel(const MCSymbol *Label) const { |
892 | return LabelToBB.lookup(Val: Label); |
893 | } |
894 | |
895 | /// Return basic block that originally contained offset \p Offset |
896 | /// from the function start. |
897 | BinaryBasicBlock *getBasicBlockContainingOffset(uint64_t Offset); |
898 | |
899 | const BinaryBasicBlock *getBasicBlockContainingOffset(uint64_t Offset) const { |
900 | return const_cast<BinaryFunction *>(this)->getBasicBlockContainingOffset( |
901 | Offset); |
902 | } |
903 | |
904 | /// Return basic block that started at offset \p Offset. |
905 | BinaryBasicBlock *getBasicBlockAtOffset(uint64_t Offset) { |
906 | BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset); |
907 | return BB && BB->getOffset() == Offset ? BB : nullptr; |
908 | } |
909 | |
910 | /// Retrieve the landing pad BB associated with invoke instruction \p Invoke |
911 | /// that is in \p BB. Return nullptr if none exists |
912 | BinaryBasicBlock *getLandingPadBBFor(const BinaryBasicBlock &BB, |
913 | const MCInst &InvokeInst) const { |
914 | assert(BC.MIB->isInvoke(InvokeInst) && "must be invoke instruction" ); |
915 | const std::optional<MCPlus::MCLandingPad> LP = |
916 | BC.MIB->getEHInfo(Inst: InvokeInst); |
917 | if (LP && LP->first) { |
918 | BinaryBasicBlock *LBB = BB.getLandingPad(Label: LP->first); |
919 | assert(LBB && "Landing pad should be defined" ); |
920 | return LBB; |
921 | } |
922 | return nullptr; |
923 | } |
924 | |
925 | /// Return instruction at a given offset in the function. Valid before |
926 | /// CFG is constructed or while instruction offsets are available in CFG. |
927 | MCInst *getInstructionAtOffset(uint64_t Offset); |
928 | |
929 | const MCInst *getInstructionAtOffset(uint64_t Offset) const { |
930 | return const_cast<BinaryFunction *>(this)->getInstructionAtOffset(Offset); |
931 | } |
932 | |
933 | /// Return offset for the first instruction. If there is data at the |
934 | /// beginning of a function then offset of the first instruction could |
935 | /// be different from 0 |
936 | uint64_t getFirstInstructionOffset() const { |
937 | if (Instructions.empty()) |
938 | return 0; |
939 | return Instructions.begin()->first; |
940 | } |
941 | |
942 | /// Return jump table that covers a given \p Address in memory. |
943 | JumpTable *getJumpTableContainingAddress(uint64_t Address) { |
944 | auto JTI = JumpTables.upper_bound(x: Address); |
945 | if (JTI == JumpTables.begin()) |
946 | return nullptr; |
947 | --JTI; |
948 | if (JTI->first + JTI->second->getSize() > Address) |
949 | return JTI->second; |
950 | if (JTI->second->getSize() == 0 && JTI->first == Address) |
951 | return JTI->second; |
952 | return nullptr; |
953 | } |
954 | |
955 | const JumpTable *getJumpTableContainingAddress(uint64_t Address) const { |
956 | return const_cast<BinaryFunction *>(this)->getJumpTableContainingAddress( |
957 | Address); |
958 | } |
959 | |
960 | /// Return the name of the function if the function has just one name. |
961 | /// If the function has multiple names - return one followed |
962 | /// by "(*#<numnames>)". |
963 | /// |
964 | /// We should use getPrintName() for diagnostics and use |
965 | /// hasName() to match function name against a given string. |
966 | /// |
967 | /// NOTE: for disambiguating names of local symbols we use the following |
968 | /// naming schemes: |
969 | /// primary: <function>/<id> |
970 | /// alternative: <function>/<file>/<id2> |
971 | std::string getPrintName() const { |
972 | const size_t NumNames = Symbols.size() + Aliases.size(); |
973 | return NumNames == 1 |
974 | ? getOneName().str() |
975 | : (getOneName().str() + "(*" + std::to_string(val: NumNames) + ")" ); |
976 | } |
977 | |
978 | /// The function may have many names. For that reason, we avoid having |
979 | /// getName() method as most of the time the user needs a different |
980 | /// interface, such as forEachName(), hasName(), hasNameRegex(), etc. |
981 | /// In some cases though, we need just a name uniquely identifying |
982 | /// the function, and that's what this method is for. |
983 | StringRef getOneName() const { return Symbols[0]->getName(); } |
984 | |
985 | /// Return the name of the function as getPrintName(), but also trying |
986 | /// to demangle it. |
987 | std::string getDemangledName() const; |
988 | |
989 | /// Call \p Callback for every name of this function as long as the Callback |
990 | /// returns false. Stop if Callback returns true or all names have been used. |
991 | /// Return the name for which the Callback returned true if any. |
992 | template <typename FType> |
993 | std::optional<StringRef> forEachName(FType Callback) const { |
994 | for (MCSymbol *Symbol : Symbols) |
995 | if (Callback(Symbol->getName())) |
996 | return Symbol->getName(); |
997 | |
998 | for (const std::string &Name : Aliases) |
999 | if (Callback(StringRef(Name))) |
1000 | return StringRef(Name); |
1001 | |
1002 | return std::nullopt; |
1003 | } |
1004 | |
1005 | /// Check if (possibly one out of many) function name matches the given |
1006 | /// string. Use this member function instead of direct name comparison. |
1007 | bool hasName(const std::string &FunctionName) const { |
1008 | auto Res = |
1009 | forEachName(Callback: [&](StringRef Name) { return Name == FunctionName; }); |
1010 | return Res.has_value(); |
1011 | } |
1012 | |
1013 | /// Check if any of function names matches the given regex. |
1014 | std::optional<StringRef> hasNameRegex(const StringRef NameRegex) const; |
1015 | |
1016 | /// Check if any of restored function names matches the given regex. |
1017 | /// Restored name means stripping BOLT-added suffixes like "/1", |
1018 | std::optional<StringRef> |
1019 | hasRestoredNameRegex(const StringRef NameRegex) const; |
1020 | |
1021 | /// Return a vector of all possible names for the function. |
1022 | std::vector<StringRef> getNames() const { |
1023 | std::vector<StringRef> AllNames; |
1024 | forEachName(Callback: [&AllNames](StringRef Name) { |
1025 | AllNames.push_back(x: Name); |
1026 | return false; |
1027 | }); |
1028 | |
1029 | return AllNames; |
1030 | } |
1031 | |
1032 | /// Return a state the function is in (see BinaryFunction::State definition |
1033 | /// for description). |
1034 | State getState() const { return CurrentState; } |
1035 | |
1036 | /// Return true if function has a control flow graph available. |
1037 | bool hasCFG() const { |
1038 | return getState() == State::CFG || getState() == State::CFG_Finalized || |
1039 | getState() == State::EmittedCFG; |
1040 | } |
1041 | |
1042 | /// Return true if the function state implies that it includes instructions. |
1043 | bool hasInstructions() const { |
1044 | return getState() == State::Disassembled || hasCFG(); |
1045 | } |
1046 | |
1047 | bool isEmitted() const { |
1048 | return getState() == State::EmittedCFG || getState() == State::Emitted; |
1049 | } |
1050 | |
1051 | /// Return the section in the input binary this function originated from or |
1052 | /// nullptr if the function did not originate from the file. |
1053 | BinarySection *getOriginSection() const { return OriginSection; } |
1054 | |
1055 | void setOriginSection(BinarySection *Section) { OriginSection = Section; } |
1056 | |
1057 | /// Return true if the function did not originate from the primary input file. |
1058 | bool isInjected() const { return IsInjected; } |
1059 | |
1060 | /// Return original address of the function (or offset from base for PIC). |
1061 | uint64_t getAddress() const { return Address; } |
1062 | |
1063 | uint64_t getOutputAddress() const { return OutputAddress; } |
1064 | |
1065 | uint64_t getOutputSize() const { return OutputSize; } |
1066 | |
1067 | /// Does this function have a valid streaming order index? |
1068 | bool hasValidIndex() const { return Index != -1U; } |
1069 | |
1070 | /// Get the streaming order index for this function. |
1071 | uint32_t getIndex() const { return Index; } |
1072 | |
1073 | /// Set the streaming order index for this function. |
1074 | void setIndex(uint32_t Idx) { |
1075 | assert(!hasValidIndex()); |
1076 | Index = Idx; |
1077 | } |
1078 | |
1079 | /// Return offset of the function body in the binary file. |
1080 | uint64_t getFileOffset() const { |
1081 | return getLayout().getMainFragment().getFileOffset(); |
1082 | } |
1083 | |
1084 | /// Return (original) byte size of the function. |
1085 | uint64_t getSize() const { return Size; } |
1086 | |
1087 | /// Return the maximum size the body of the function could have. |
1088 | uint64_t getMaxSize() const { return MaxSize; } |
1089 | |
1090 | /// Return the number of emitted instructions for this function. |
1091 | uint32_t getNumNonPseudos() const { |
1092 | uint32_t N = 0; |
1093 | for (const BinaryBasicBlock &BB : blocks()) |
1094 | N += BB.getNumNonPseudos(); |
1095 | return N; |
1096 | } |
1097 | |
1098 | /// Return true if function has instructions to emit. |
1099 | bool hasNonPseudoInstructions() const { |
1100 | for (const BinaryBasicBlock &BB : blocks()) |
1101 | if (BB.getNumNonPseudos() > 0) |
1102 | return true; |
1103 | return false; |
1104 | } |
1105 | |
1106 | /// Return MC symbol associated with the function. |
1107 | /// All references to the function should use this symbol. |
1108 | MCSymbol *getSymbol(const FragmentNum Fragment = FragmentNum::main()) { |
1109 | if (Fragment == FragmentNum::main()) |
1110 | return Symbols[0]; |
1111 | |
1112 | size_t ColdSymbolIndex = Fragment.get() - 1; |
1113 | if (ColdSymbolIndex >= ColdSymbols.size()) |
1114 | ColdSymbols.resize(N: ColdSymbolIndex + 1); |
1115 | |
1116 | MCSymbol *&ColdSymbol = ColdSymbols[ColdSymbolIndex]; |
1117 | if (ColdSymbol == nullptr) { |
1118 | SmallString<10> Appendix = formatv(Fmt: ".cold.{0}" , Vals&: ColdSymbolIndex); |
1119 | ColdSymbol = BC.Ctx->getOrCreateSymbol( |
1120 | Name: NameResolver::append(UniqueName: Symbols[0]->getName(), Suffix: Appendix)); |
1121 | } |
1122 | |
1123 | return ColdSymbol; |
1124 | } |
1125 | |
1126 | /// Return MC symbol associated with the function (const version). |
1127 | /// All references to the function should use this symbol. |
1128 | const MCSymbol *getSymbol() const { return Symbols[0]; } |
1129 | |
1130 | /// Return a list of symbols associated with the main entry of the function. |
1131 | SymbolListTy &getSymbols() { return Symbols; } |
1132 | const SymbolListTy &getSymbols() const { return Symbols; } |
1133 | |
1134 | /// If a local symbol \p BBLabel corresponds to a basic block that is a |
1135 | /// secondary entry point into the function, then return a global symbol |
1136 | /// that represents the secondary entry point. Otherwise return nullptr. |
1137 | MCSymbol *getSecondaryEntryPointSymbol(const MCSymbol *BBLabel) const { |
1138 | return SecondaryEntryPoints.lookup(Val: BBLabel); |
1139 | } |
1140 | |
1141 | /// If the basic block serves as a secondary entry point to the function, |
1142 | /// return a global symbol representing the entry. Otherwise return nullptr. |
1143 | MCSymbol *getSecondaryEntryPointSymbol(const BinaryBasicBlock &BB) const { |
1144 | return getSecondaryEntryPointSymbol(BBLabel: BB.getLabel()); |
1145 | } |
1146 | |
1147 | /// Return true if the basic block is an entry point into the function |
1148 | /// (either primary or secondary). |
1149 | bool isEntryPoint(const BinaryBasicBlock &BB) const { |
1150 | if (&BB == BasicBlocks.front()) |
1151 | return true; |
1152 | return getSecondaryEntryPointSymbol(BB); |
1153 | } |
1154 | |
1155 | /// Return MC symbol corresponding to an enumerated entry for multiple-entry |
1156 | /// functions. |
1157 | MCSymbol *getSymbolForEntryID(uint64_t EntryNum); |
1158 | const MCSymbol *getSymbolForEntryID(uint64_t EntryNum) const { |
1159 | return const_cast<BinaryFunction *>(this)->getSymbolForEntryID(EntryNum); |
1160 | } |
1161 | |
1162 | using EntryPointCallbackTy = function_ref<bool(uint64_t, const MCSymbol *)>; |
1163 | |
1164 | /// Invoke \p Callback function for every entry point in the function starting |
1165 | /// with the main entry and using entries in the ascending address order. |
1166 | /// Stop calling the function after false is returned by the callback. |
1167 | /// |
1168 | /// Pass an offset of the entry point in the input binary and a corresponding |
1169 | /// global symbol to the callback function. |
1170 | /// |
1171 | /// Return true if all callbacks returned true, false otherwise. |
1172 | bool forEachEntryPoint(EntryPointCallbackTy Callback) const; |
1173 | |
1174 | /// Return MC symbol associated with the end of the function. |
1175 | MCSymbol * |
1176 | getFunctionEndLabel(const FragmentNum Fragment = FragmentNum::main()) const { |
1177 | assert(BC.Ctx && "cannot be called with empty context" ); |
1178 | |
1179 | size_t LabelIndex = Fragment.get(); |
1180 | if (LabelIndex >= FunctionEndLabels.size()) { |
1181 | FunctionEndLabels.resize(N: LabelIndex + 1); |
1182 | } |
1183 | |
1184 | MCSymbol *&FunctionEndLabel = FunctionEndLabels[LabelIndex]; |
1185 | if (!FunctionEndLabel) { |
1186 | std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex); |
1187 | if (Fragment == FragmentNum::main()) |
1188 | FunctionEndLabel = BC.Ctx->createNamedTempSymbol(Name: "func_end" ); |
1189 | else |
1190 | FunctionEndLabel = BC.Ctx->createNamedTempSymbol( |
1191 | Name: formatv(Fmt: "func_cold_end.{0}" , Vals: Fragment.get() - 1)); |
1192 | } |
1193 | return FunctionEndLabel; |
1194 | } |
1195 | |
1196 | /// Return a label used to identify where the constant island was emitted |
1197 | /// (AArch only). This is used to update the symbol table accordingly, |
1198 | /// emitting data marker symbols as required by the ABI. |
1199 | MCSymbol *getFunctionConstantIslandLabel() const { |
1200 | assert(Islands && "function expected to have constant islands" ); |
1201 | |
1202 | if (!Islands->FunctionConstantIslandLabel) { |
1203 | Islands->FunctionConstantIslandLabel = |
1204 | BC.Ctx->getOrCreateSymbol(Name: "func_const_island@" + getOneName()); |
1205 | } |
1206 | return Islands->FunctionConstantIslandLabel; |
1207 | } |
1208 | |
1209 | MCSymbol *getFunctionColdConstantIslandLabel() const { |
1210 | assert(Islands && "function expected to have constant islands" ); |
1211 | |
1212 | if (!Islands->FunctionColdConstantIslandLabel) { |
1213 | Islands->FunctionColdConstantIslandLabel = |
1214 | BC.Ctx->getOrCreateSymbol(Name: "func_cold_const_island@" + getOneName()); |
1215 | } |
1216 | return Islands->FunctionColdConstantIslandLabel; |
1217 | } |
1218 | |
1219 | /// Return true if this is a function representing a PLT entry. |
1220 | bool isPLTFunction() const { return PLTSymbol != nullptr; } |
1221 | |
1222 | /// Return PLT function reference symbol for PLT functions and nullptr for |
1223 | /// non-PLT functions. |
1224 | const MCSymbol *getPLTSymbol() const { return PLTSymbol; } |
1225 | |
1226 | /// Set function PLT reference symbol for PLT functions. |
1227 | void setPLTSymbol(const MCSymbol *Symbol) { |
1228 | assert(Size == 0 && "function size should be 0 for PLT functions" ); |
1229 | PLTSymbol = Symbol; |
1230 | IsPseudo = true; |
1231 | } |
1232 | |
1233 | /// Update output values of the function based on the final \p Layout. |
1234 | void updateOutputValues(const BOLTLinker &Linker); |
1235 | |
1236 | /// Register relocation type \p RelType at a given \p Address in the function |
1237 | /// against \p Symbol. |
1238 | /// Assert if the \p Address is not inside this function. |
1239 | void addRelocation(uint64_t Address, MCSymbol *Symbol, uint64_t RelType, |
1240 | uint64_t Addend, uint64_t Value); |
1241 | |
1242 | /// Return the name of the section this function originated from. |
1243 | std::optional<StringRef> getOriginSectionName() const { |
1244 | if (!OriginSection) |
1245 | return std::nullopt; |
1246 | return OriginSection->getName(); |
1247 | } |
1248 | |
1249 | /// Return internal section name for this function. |
1250 | SmallString<32> |
1251 | getCodeSectionName(const FragmentNum Fragment = FragmentNum::main()) const { |
1252 | if (Fragment == FragmentNum::main()) |
1253 | return SmallString<32>(CodeSectionName); |
1254 | if (Fragment == FragmentNum::cold()) |
1255 | return SmallString<32>(ColdCodeSectionName); |
1256 | if (BC.HasWarmSection && Fragment == FragmentNum::warm()) |
1257 | return SmallString<32>(BC.getWarmCodeSectionName()); |
1258 | return formatv(Fmt: "{0}.{1}" , Vals: ColdCodeSectionName, Vals: Fragment.get() - 1); |
1259 | } |
1260 | |
1261 | /// Assign a code section name to the function. |
1262 | void setCodeSectionName(const StringRef Name) { |
1263 | CodeSectionName = Name.str(); |
1264 | } |
1265 | |
1266 | /// Get output code section. |
1267 | ErrorOr<BinarySection &> |
1268 | getCodeSection(const FragmentNum Fragment = FragmentNum::main()) const { |
1269 | return BC.getUniqueSectionByName(SectionName: getCodeSectionName(Fragment)); |
1270 | } |
1271 | |
1272 | /// Assign a section name for the cold part of the function. |
1273 | void setColdCodeSectionName(const StringRef Name) { |
1274 | ColdCodeSectionName = Name.str(); |
1275 | } |
1276 | |
1277 | /// Return true iif the function will halt execution on entry. |
1278 | bool trapsOnEntry() const { return TrapsOnEntry; } |
1279 | |
1280 | /// Make the function always trap on entry. Other than the trap instruction, |
1281 | /// the function body will be empty. |
1282 | void setTrapOnEntry(); |
1283 | |
1284 | /// Return true if the function could be correctly processed. |
1285 | bool isSimple() const { return IsSimple; } |
1286 | |
1287 | /// Return true if the function should be ignored for optimization purposes. |
1288 | bool isIgnored() const { return IsIgnored; } |
1289 | |
1290 | /// Return true if the function should not be disassembled, emitted, or |
1291 | /// otherwise processed. |
1292 | bool isPseudo() const { return IsPseudo; } |
1293 | |
1294 | /// Return true if the function contains explicit or implicit indirect branch |
1295 | /// to its split fragments, e.g., split jump table, landing pad in split |
1296 | /// fragment. |
1297 | bool hasIndirectTargetToSplitFragment() const { |
1298 | return HasIndirectTargetToSplitFragment; |
1299 | } |
1300 | |
1301 | /// Return true if all CFG edges have local successors. |
1302 | bool hasCanonicalCFG() const { return HasCanonicalCFG; } |
1303 | |
1304 | /// Return true if the original function code has all necessary relocations |
1305 | /// to track addresses of functions emitted to new locations. |
1306 | bool hasExternalRefRelocations() const { return HasExternalRefRelocations; } |
1307 | |
1308 | /// Return true if the function has instruction(s) with unknown control flow. |
1309 | bool hasUnknownControlFlow() const { return HasUnknownControlFlow; } |
1310 | |
1311 | /// Return true if the function body is non-contiguous. |
1312 | bool isSplit() const { return isSimple() && getLayout().isSplit(); } |
1313 | |
1314 | bool shouldPreserveNops() const { return PreserveNops; } |
1315 | |
1316 | /// Return true if the function has exception handling tables. |
1317 | bool hasEHRanges() const { return HasEHRanges; } |
1318 | |
1319 | /// Return true if the function uses DW_CFA_GNU_args_size CFIs. |
1320 | bool usesGnuArgsSize() const { return UsesGnuArgsSize; } |
1321 | |
1322 | /// Return true if the function has more than one entry point. |
1323 | bool isMultiEntry() const { return !SecondaryEntryPoints.empty(); } |
1324 | |
1325 | /// Return true if the function might have a profile available externally, |
1326 | /// but not yet populated into the function. |
1327 | bool hasProfileAvailable() const { return HasProfileAvailable; } |
1328 | |
1329 | bool hasMemoryProfile() const { return HasMemoryProfile; } |
1330 | |
1331 | /// Return true if the body of the function was merged into another function. |
1332 | bool isFolded() const { return FoldedIntoFunction != nullptr; } |
1333 | |
1334 | /// Return true if other functions were folded into this one. |
1335 | bool hasFunctionsFoldedInto() const { return HasFunctionsFoldedInto; } |
1336 | |
1337 | /// If this function was folded, return the function it was folded into. |
1338 | BinaryFunction *getFoldedIntoFunction() const { return FoldedIntoFunction; } |
1339 | |
1340 | /// Return true if the function uses jump tables. |
1341 | bool hasJumpTables() const { return !JumpTables.empty(); } |
1342 | |
1343 | /// Return true if the function has SDT marker |
1344 | bool hasSDTMarker() const { return HasSDTMarker; } |
1345 | |
1346 | /// Return true if the function has Pseudo Probe |
1347 | bool hasPseudoProbe() const { return HasPseudoProbe; } |
1348 | |
1349 | /// Return true if the function uses ORC format for stack unwinding. |
1350 | bool hasORC() const { return HasORC; } |
1351 | |
1352 | /// Return true if the original entry point was patched. |
1353 | bool isPatched() const { return IsPatched; } |
1354 | |
1355 | const JumpTable *getJumpTable(const MCInst &Inst) const { |
1356 | const uint64_t Address = BC.MIB->getJumpTable(Inst); |
1357 | return getJumpTableContainingAddress(Address); |
1358 | } |
1359 | |
1360 | JumpTable *getJumpTable(const MCInst &Inst) { |
1361 | const uint64_t Address = BC.MIB->getJumpTable(Inst); |
1362 | return getJumpTableContainingAddress(Address); |
1363 | } |
1364 | |
1365 | const MCSymbol *getPersonalityFunction() const { return PersonalityFunction; } |
1366 | |
1367 | uint8_t getPersonalityEncoding() const { return PersonalityEncoding; } |
1368 | |
1369 | CallSitesRange getCallSites(const FragmentNum F) const { |
1370 | return make_range(p: std::equal_range(first: CallSites.begin(), last: CallSites.end(), |
1371 | val: std::make_pair(x: F, y: CallSite()), |
1372 | comp: llvm::less_first())); |
1373 | } |
1374 | |
1375 | void |
1376 | addCallSites(const ArrayRef<std::pair<FragmentNum, CallSite>> NewCallSites) { |
1377 | llvm::copy(Range: NewCallSites, Out: std::back_inserter(x&: CallSites)); |
1378 | llvm::stable_sort(Range&: CallSites, C: llvm::less_first()); |
1379 | } |
1380 | |
1381 | ArrayRef<uint8_t> getLSDAActionTable() const { return LSDAActionTable; } |
1382 | |
1383 | const LSDATypeTableTy &getLSDATypeTable() const { return LSDATypeTable; } |
1384 | |
1385 | unsigned getLSDATypeEncoding() const { return LSDATypeEncoding; } |
1386 | |
1387 | const LSDATypeTableTy &getLSDATypeAddressTable() const { |
1388 | return LSDATypeAddressTable; |
1389 | } |
1390 | |
1391 | ArrayRef<uint8_t> getLSDATypeIndexTable() const { return LSDATypeIndexTable; } |
1392 | |
1393 | IslandInfo &getIslandInfo() { |
1394 | assert(Islands && "function expected to have constant islands" ); |
1395 | return *Islands; |
1396 | } |
1397 | |
1398 | const IslandInfo &getIslandInfo() const { |
1399 | assert(Islands && "function expected to have constant islands" ); |
1400 | return *Islands; |
1401 | } |
1402 | |
1403 | /// Return true if the function has CFI instructions |
1404 | bool hasCFI() const { |
1405 | return !FrameInstructions.empty() || !CIEFrameInstructions.empty() || |
1406 | IsInjected; |
1407 | } |
1408 | |
1409 | /// Return unique number associated with the function. |
1410 | uint64_t getFunctionNumber() const { return FunctionNumber; } |
1411 | |
1412 | /// Return true if the given address \p PC is inside the function body. |
1413 | bool containsAddress(uint64_t PC, bool UseMaxSize = false) const { |
1414 | if (UseMaxSize) |
1415 | return Address <= PC && PC < Address + MaxSize; |
1416 | return Address <= PC && PC < Address + Size; |
1417 | } |
1418 | |
1419 | /// Create a basic block in the function. The new block is *NOT* inserted |
1420 | /// into the CFG. The caller must use insertBasicBlocks() to add any new |
1421 | /// blocks to the CFG. |
1422 | std::unique_ptr<BinaryBasicBlock> |
1423 | createBasicBlock(MCSymbol *Label = nullptr) { |
1424 | if (!Label) { |
1425 | std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex); |
1426 | Label = BC.Ctx->createNamedTempSymbol(Name: "BB" ); |
1427 | } |
1428 | auto BB = |
1429 | std::unique_ptr<BinaryBasicBlock>(new BinaryBasicBlock(this, Label)); |
1430 | |
1431 | LabelToBB[Label] = BB.get(); |
1432 | |
1433 | return BB; |
1434 | } |
1435 | |
1436 | /// Create a new basic block with an optional \p Label and add it to the list |
1437 | /// of basic blocks of this function. |
1438 | BinaryBasicBlock *addBasicBlock(MCSymbol *Label = nullptr) { |
1439 | assert(CurrentState == State::CFG && "Can only add blocks in CFG state" ); |
1440 | |
1441 | BasicBlocks.emplace_back(Args: createBasicBlock(Label).release()); |
1442 | BinaryBasicBlock *BB = BasicBlocks.back(); |
1443 | |
1444 | BB->setIndex(BasicBlocks.size() - 1); |
1445 | Layout.addBasicBlock(BB); |
1446 | |
1447 | return BB; |
1448 | } |
1449 | |
1450 | /// Add basic block \BB as an entry point to the function. Return global |
1451 | /// symbol associated with the entry. |
1452 | MCSymbol *addEntryPoint(const BinaryBasicBlock &BB); |
1453 | |
1454 | /// Register secondary entry point at a given \p Offset into the function. |
1455 | /// Return global symbol for use by extern function references. |
1456 | MCSymbol *addEntryPointAtOffset(uint64_t Offset); |
1457 | |
1458 | /// Mark all blocks that are unreachable from a root (entry point |
1459 | /// or landing pad) as invalid. |
1460 | void markUnreachableBlocks(); |
1461 | |
1462 | /// Rebuilds BBs layout, ignoring dead BBs. Returns the number of removed |
1463 | /// BBs and the removed number of bytes of code. |
1464 | std::pair<unsigned, uint64_t> |
1465 | eraseInvalidBBs(const MCCodeEmitter *Emitter = nullptr); |
1466 | |
1467 | /// Get the relative order between two basic blocks in the original |
1468 | /// layout. The result is > 0 if B occurs before A and < 0 if B |
1469 | /// occurs after A. If A and B are the same block, the result is 0. |
1470 | signed getOriginalLayoutRelativeOrder(const BinaryBasicBlock *A, |
1471 | const BinaryBasicBlock *B) const { |
1472 | return getIndex(BB: A) - getIndex(BB: B); |
1473 | } |
1474 | |
1475 | /// Insert the BBs contained in NewBBs into the basic blocks for this |
1476 | /// function. Update the associated state of all blocks as needed, i.e. |
1477 | /// BB offsets and BB indices. The new BBs are inserted after Start. |
1478 | /// This operation could affect fallthrough branches for Start. |
1479 | /// |
1480 | void |
1481 | insertBasicBlocks(BinaryBasicBlock *Start, |
1482 | std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs, |
1483 | const bool UpdateLayout = true, |
1484 | const bool UpdateCFIState = true, |
1485 | const bool RecomputeLandingPads = true); |
1486 | |
1487 | iterator insertBasicBlocks( |
1488 | iterator StartBB, std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs, |
1489 | const bool UpdateLayout = true, const bool UpdateCFIState = true, |
1490 | const bool RecomputeLandingPads = true); |
1491 | |
1492 | /// Update the basic block layout for this function. The BBs from |
1493 | /// [Start->Index, Start->Index + NumNewBlocks) are inserted into the |
1494 | /// layout after the BB indicated by Start. |
1495 | void updateLayout(BinaryBasicBlock *Start, const unsigned NumNewBlocks); |
1496 | |
1497 | /// Recompute the CFI state for NumNewBlocks following Start after inserting |
1498 | /// new blocks into the CFG. This must be called after updateLayout. |
1499 | void updateCFIState(BinaryBasicBlock *Start, const unsigned NumNewBlocks); |
1500 | |
1501 | /// Return true if we detected ambiguous jump tables in this function, which |
1502 | /// happen when one JT is used in more than one indirect jumps. This precludes |
1503 | /// us from splitting edges for this JT unless we duplicate the JT (see |
1504 | /// disambiguateJumpTables). |
1505 | bool checkForAmbiguousJumpTables(); |
1506 | |
1507 | /// Detect when two distinct indirect jumps are using the same jump table and |
1508 | /// duplicate it, allocating a separate JT for each indirect branch. This is |
1509 | /// necessary for code transformations on the CFG that change an edge induced |
1510 | /// by an indirect branch, e.g.: instrumentation or shrink wrapping. However, |
1511 | /// this is only possible if we are not updating jump tables in place, but are |
1512 | /// writing it to a new location (moving them). |
1513 | void disambiguateJumpTables(MCPlusBuilder::AllocatorIdTy AllocId); |
1514 | |
1515 | /// Change \p OrigDest to \p NewDest in the jump table used at the end of |
1516 | /// \p BB. Returns false if \p OrigDest couldn't be find as a valid target |
1517 | /// and no replacement took place. |
1518 | bool replaceJumpTableEntryIn(BinaryBasicBlock *BB, BinaryBasicBlock *OldDest, |
1519 | BinaryBasicBlock *NewDest); |
1520 | |
1521 | /// Split the CFG edge <From, To> by inserting an intermediate basic block. |
1522 | /// Returns a pointer to this new intermediate basic block. BB "From" will be |
1523 | /// updated to jump to the intermediate block, which in turn will have an |
1524 | /// unconditional branch to BB "To". |
1525 | /// User needs to manually call fixBranches(). This function only creates the |
1526 | /// correct CFG edges. |
1527 | BinaryBasicBlock *splitEdge(BinaryBasicBlock *From, BinaryBasicBlock *To); |
1528 | |
1529 | /// We may have built an overly conservative CFG for functions with calls |
1530 | /// to functions that the compiler knows will never return. In this case, |
1531 | /// clear all successors from these blocks. |
1532 | void deleteConservativeEdges(); |
1533 | |
1534 | /// Determine direction of the branch based on the current layout. |
1535 | /// Callee is responsible of updating basic block indices prior to using |
1536 | /// this function (e.g. by calling BinaryFunction::updateLayoutIndices()). |
1537 | static bool isForwardBranch(const BinaryBasicBlock *From, |
1538 | const BinaryBasicBlock *To) { |
1539 | assert(From->getFunction() == To->getFunction() && |
1540 | "basic blocks should be in the same function" ); |
1541 | return To->getLayoutIndex() > From->getLayoutIndex(); |
1542 | } |
1543 | |
1544 | /// Determine direction of the call to callee symbol relative to the start |
1545 | /// of this function. |
1546 | /// Note: this doesn't take function splitting into account. |
1547 | bool isForwardCall(const MCSymbol *CalleeSymbol) const; |
1548 | |
1549 | /// Dump function information to debug output. If \p PrintInstructions |
1550 | /// is true - include instruction disassembly. |
1551 | void dump() const; |
1552 | |
1553 | /// Print function information to the \p OS stream. |
1554 | void print(raw_ostream &OS, std::string Annotation = "" ); |
1555 | |
1556 | /// Print all relocations between \p Offset and \p Offset + \p Size in |
1557 | /// this function. |
1558 | void printRelocations(raw_ostream &OS, uint64_t Offset, uint64_t Size) const; |
1559 | |
1560 | /// Return true if function has a profile, even if the profile does not |
1561 | /// match CFG 100%. |
1562 | bool hasProfile() const { return ExecutionCount != COUNT_NO_PROFILE; } |
1563 | |
1564 | /// Return true if function profile is present and accurate. |
1565 | bool hasValidProfile() const { |
1566 | return ExecutionCount != COUNT_NO_PROFILE && ProfileMatchRatio == 1.0f; |
1567 | } |
1568 | |
1569 | /// Mark this function as having a valid profile. |
1570 | void markProfiled(uint16_t Flags) { |
1571 | if (ExecutionCount == COUNT_NO_PROFILE) |
1572 | ExecutionCount = 0; |
1573 | ProfileFlags = Flags; |
1574 | ProfileMatchRatio = 1.0f; |
1575 | } |
1576 | |
1577 | /// Return flags describing a profile for this function. |
1578 | uint16_t getProfileFlags() const { return ProfileFlags; } |
1579 | |
1580 | /// Return true if the function's input profile data has been inaccurate but |
1581 | /// has been corrected by the profile inference algorithm. |
1582 | bool hasInferredProfile() const { return HasInferredProfile; } |
1583 | |
1584 | void setHasInferredProfile(bool Inferred) { HasInferredProfile = Inferred; } |
1585 | |
1586 | void addCFIInstruction(uint64_t Offset, MCCFIInstruction &&Inst) { |
1587 | assert(!Instructions.empty()); |
1588 | |
1589 | // Fix CFI instructions skipping NOPs. We need to fix this because changing |
1590 | // CFI state after a NOP, besides being wrong and inaccurate, makes it |
1591 | // harder for us to recover this information, since we can create empty BBs |
1592 | // with NOPs and then reorder it away. |
1593 | // We fix this by moving the CFI instruction just before any NOPs. |
1594 | auto I = Instructions.lower_bound(x: Offset); |
1595 | if (Offset == getSize()) { |
1596 | assert(I == Instructions.end() && "unexpected iterator value" ); |
1597 | // Sometimes compiler issues restore_state after all instructions |
1598 | // in the function (even after nop). |
1599 | --I; |
1600 | Offset = I->first; |
1601 | } |
1602 | assert(I->first == Offset && "CFI pointing to unknown instruction" ); |
1603 | if (I == Instructions.begin()) { |
1604 | CIEFrameInstructions.emplace_back(Args: std::forward<MCCFIInstruction>(t&: Inst)); |
1605 | return; |
1606 | } |
1607 | |
1608 | --I; |
1609 | while (I != Instructions.begin() && BC.MIB->isNoop(Inst: I->second)) { |
1610 | Offset = I->first; |
1611 | --I; |
1612 | } |
1613 | OffsetToCFI.emplace(args&: Offset, args: FrameInstructions.size()); |
1614 | FrameInstructions.emplace_back(Args: std::forward<MCCFIInstruction>(t&: Inst)); |
1615 | } |
1616 | |
1617 | BinaryBasicBlock::iterator addCFIInstruction(BinaryBasicBlock *BB, |
1618 | BinaryBasicBlock::iterator Pos, |
1619 | MCCFIInstruction &&Inst) { |
1620 | size_t Idx = FrameInstructions.size(); |
1621 | FrameInstructions.emplace_back(Args: std::forward<MCCFIInstruction>(t&: Inst)); |
1622 | return addCFIPseudo(BB, Pos, Offset: Idx); |
1623 | } |
1624 | |
1625 | /// Insert a CFI pseudo instruction in a basic block. This pseudo instruction |
1626 | /// is a placeholder that refers to a real MCCFIInstruction object kept by |
1627 | /// this function that will be emitted at that position. |
1628 | BinaryBasicBlock::iterator addCFIPseudo(BinaryBasicBlock *BB, |
1629 | BinaryBasicBlock::iterator Pos, |
1630 | uint32_t Offset) { |
1631 | MCInst CFIPseudo; |
1632 | BC.MIB->createCFI(Inst&: CFIPseudo, Offset); |
1633 | return BB->insertPseudoInstr(Pos, Instr&: CFIPseudo); |
1634 | } |
1635 | |
1636 | /// Retrieve the MCCFIInstruction object associated with a CFI pseudo. |
1637 | const MCCFIInstruction *getCFIFor(const MCInst &Instr) const { |
1638 | if (!BC.MIB->isCFI(Inst: Instr)) |
1639 | return nullptr; |
1640 | uint32_t Offset = Instr.getOperand(i: 0).getImm(); |
1641 | assert(Offset < FrameInstructions.size() && "Invalid CFI offset" ); |
1642 | return &FrameInstructions[Offset]; |
1643 | } |
1644 | |
1645 | void setCFIFor(const MCInst &Instr, MCCFIInstruction &&CFIInst) { |
1646 | assert(BC.MIB->isCFI(Instr) && |
1647 | "attempting to change CFI in a non-CFI inst" ); |
1648 | uint32_t Offset = Instr.getOperand(i: 0).getImm(); |
1649 | assert(Offset < FrameInstructions.size() && "Invalid CFI offset" ); |
1650 | FrameInstructions[Offset] = std::move(CFIInst); |
1651 | } |
1652 | |
1653 | void mutateCFIRegisterFor(const MCInst &Instr, MCPhysReg NewReg); |
1654 | |
1655 | const MCCFIInstruction *mutateCFIOffsetFor(const MCInst &Instr, |
1656 | int64_t NewOffset); |
1657 | |
1658 | BinaryFunction &setFileOffset(uint64_t Offset) { |
1659 | getLayout().getMainFragment().setFileOffset(Offset); |
1660 | return *this; |
1661 | } |
1662 | |
1663 | BinaryFunction &setSize(uint64_t S) { |
1664 | Size = S; |
1665 | return *this; |
1666 | } |
1667 | |
1668 | BinaryFunction &setMaxSize(uint64_t Size) { |
1669 | MaxSize = Size; |
1670 | return *this; |
1671 | } |
1672 | |
1673 | BinaryFunction &setOutputAddress(uint64_t Address) { |
1674 | OutputAddress = Address; |
1675 | return *this; |
1676 | } |
1677 | |
1678 | BinaryFunction &setOutputSize(uint64_t Size) { |
1679 | OutputSize = Size; |
1680 | return *this; |
1681 | } |
1682 | |
1683 | BinaryFunction &setSimple(bool Simple) { |
1684 | IsSimple = Simple; |
1685 | return *this; |
1686 | } |
1687 | |
1688 | void setPseudo(bool Pseudo) { IsPseudo = Pseudo; } |
1689 | |
1690 | BinaryFunction &setUsesGnuArgsSize(bool Uses = true) { |
1691 | UsesGnuArgsSize = Uses; |
1692 | return *this; |
1693 | } |
1694 | |
1695 | BinaryFunction &setHasProfileAvailable(bool V = true) { |
1696 | HasProfileAvailable = V; |
1697 | return *this; |
1698 | } |
1699 | |
1700 | /// Mark function that should not be emitted. |
1701 | void setIgnored(); |
1702 | |
1703 | void setIsPatched(bool V) { IsPatched = V; } |
1704 | |
1705 | void setHasIndirectTargetToSplitFragment(bool V) { |
1706 | HasIndirectTargetToSplitFragment = V; |
1707 | } |
1708 | |
1709 | void setHasCanonicalCFG(bool V) { HasCanonicalCFG = V; } |
1710 | |
1711 | void setFolded(BinaryFunction *BF) { FoldedIntoFunction = BF; } |
1712 | |
1713 | /// Indicate that another function body was merged with this function. |
1714 | void setHasFunctionsFoldedInto() { HasFunctionsFoldedInto = true; } |
1715 | |
1716 | void setHasSDTMarker(bool V) { HasSDTMarker = V; } |
1717 | |
1718 | /// Mark the function as using ORC format for stack unwinding. |
1719 | void setHasORC(bool V) { HasORC = V; } |
1720 | |
1721 | BinaryFunction &setPersonalityFunction(uint64_t Addr) { |
1722 | assert(!PersonalityFunction && "can't set personality function twice" ); |
1723 | PersonalityFunction = BC.getOrCreateGlobalSymbol(Address: Addr, Prefix: "FUNCat" ); |
1724 | return *this; |
1725 | } |
1726 | |
1727 | BinaryFunction &setPersonalityEncoding(uint8_t Encoding) { |
1728 | PersonalityEncoding = Encoding; |
1729 | return *this; |
1730 | } |
1731 | |
1732 | BinaryFunction &setAlignment(uint16_t Align) { |
1733 | Alignment = Align; |
1734 | return *this; |
1735 | } |
1736 | |
1737 | uint16_t getMinAlignment() const { |
1738 | // Align data in code BFs minimum to CI alignment |
1739 | if (!size() && hasIslandsInfo()) |
1740 | return getConstantIslandAlignment(); |
1741 | return BC.MIB->getMinFunctionAlignment(); |
1742 | } |
1743 | |
1744 | Align getMinAlign() const { return Align(getMinAlignment()); } |
1745 | |
1746 | uint16_t getAlignment() const { return Alignment; } |
1747 | Align getAlign() const { return Align(getAlignment()); } |
1748 | |
1749 | BinaryFunction &setMaxAlignmentBytes(uint16_t MaxAlignBytes) { |
1750 | MaxAlignmentBytes = MaxAlignBytes; |
1751 | return *this; |
1752 | } |
1753 | |
1754 | uint16_t getMaxAlignmentBytes() const { return MaxAlignmentBytes; } |
1755 | |
1756 | BinaryFunction &setMaxColdAlignmentBytes(uint16_t MaxAlignBytes) { |
1757 | MaxColdAlignmentBytes = MaxAlignBytes; |
1758 | return *this; |
1759 | } |
1760 | |
1761 | uint16_t getMaxColdAlignmentBytes() const { return MaxColdAlignmentBytes; } |
1762 | |
1763 | BinaryFunction &setImageAddress(uint64_t Address) { |
1764 | getLayout().getMainFragment().setImageAddress(Address); |
1765 | return *this; |
1766 | } |
1767 | |
1768 | /// Return the address of this function' image in memory. |
1769 | uint64_t getImageAddress() const { |
1770 | return getLayout().getMainFragment().getImageAddress(); |
1771 | } |
1772 | |
1773 | BinaryFunction &setImageSize(uint64_t Size) { |
1774 | getLayout().getMainFragment().setImageSize(Size); |
1775 | return *this; |
1776 | } |
1777 | |
1778 | /// Return the size of this function' image in memory. |
1779 | uint64_t getImageSize() const { |
1780 | return getLayout().getMainFragment().getImageSize(); |
1781 | } |
1782 | |
1783 | /// Return true if the function is a secondary fragment of another function. |
1784 | bool isFragment() const { return IsFragment; } |
1785 | |
1786 | /// Returns if this function is a child of \p Other function. |
1787 | bool isChildOf(const BinaryFunction &Other) const { |
1788 | return ParentFragments.contains(Ptr: &Other); |
1789 | } |
1790 | |
1791 | /// Returns if this function is a parent of \p Other function. |
1792 | bool isParentOf(const BinaryFunction &Other) const { |
1793 | return Fragments.contains(Ptr: &Other); |
1794 | } |
1795 | |
1796 | /// Return the child fragment form parent function |
1797 | iterator_range<FragmentsSetTy::const_iterator> getFragments() const { |
1798 | return iterator_range<FragmentsSetTy::const_iterator>(Fragments.begin(), |
1799 | Fragments.end()); |
1800 | } |
1801 | |
1802 | /// Return the parent function for split function fragments. |
1803 | FragmentsSetTy *getParentFragments() { return &ParentFragments; } |
1804 | |
1805 | /// Returns if this function is a parent or child of \p Other function. |
1806 | bool isParentOrChildOf(const BinaryFunction &Other) const { |
1807 | return isChildOf(Other) || isParentOf(Other); |
1808 | } |
1809 | |
1810 | /// Set the profile data for the number of times the function was called. |
1811 | BinaryFunction &setExecutionCount(uint64_t Count) { |
1812 | ExecutionCount = Count; |
1813 | return *this; |
1814 | } |
1815 | |
1816 | /// Adjust execution count for the function by a given \p Count. The value |
1817 | /// \p Count will be subtracted from the current function count. |
1818 | /// |
1819 | /// The function will proportionally adjust execution count for all |
1820 | /// basic blocks and edges in the control flow graph. |
1821 | void adjustExecutionCount(uint64_t Count); |
1822 | |
1823 | /// Set LSDA address for the function. |
1824 | BinaryFunction &setLSDAAddress(uint64_t Address) { |
1825 | LSDAAddress = Address; |
1826 | return *this; |
1827 | } |
1828 | |
1829 | /// Set main LSDA symbol for the function. |
1830 | BinaryFunction &setLSDASymbol(MCSymbol *Symbol) { |
1831 | if (LSDASymbols.empty()) |
1832 | LSDASymbols.resize(N: 1); |
1833 | LSDASymbols.front() = Symbol; |
1834 | return *this; |
1835 | } |
1836 | |
1837 | /// Return the profile information about the number of times |
1838 | /// the function was executed. |
1839 | /// |
1840 | /// Return COUNT_NO_PROFILE if there's no profile info. |
1841 | uint64_t getExecutionCount() const { return ExecutionCount; } |
1842 | |
1843 | /// Return the raw profile information about the number of branch |
1844 | /// executions corresponding to this function. |
1845 | uint64_t getRawBranchCount() const { return RawBranchCount; } |
1846 | |
1847 | /// Set the profile data about the number of branch executions corresponding |
1848 | /// to this function. |
1849 | void setRawBranchCount(uint64_t Count) { RawBranchCount = Count; } |
1850 | |
1851 | /// Return the execution count for functions with known profile. |
1852 | /// Return 0 if the function has no profile. |
1853 | uint64_t getKnownExecutionCount() const { |
1854 | return ExecutionCount == COUNT_NO_PROFILE ? 0 : ExecutionCount; |
1855 | } |
1856 | |
1857 | /// Return original LSDA address for the function or NULL. |
1858 | uint64_t getLSDAAddress() const { return LSDAAddress; } |
1859 | |
1860 | /// Return symbol pointing to function's LSDA. |
1861 | MCSymbol *getLSDASymbol(const FragmentNum F) { |
1862 | if (F.get() < LSDASymbols.size() && LSDASymbols[F.get()] != nullptr) |
1863 | return LSDASymbols[F.get()]; |
1864 | if (getCallSites(F).empty()) |
1865 | return nullptr; |
1866 | |
1867 | if (F.get() >= LSDASymbols.size()) |
1868 | LSDASymbols.resize(N: F.get() + 1); |
1869 | |
1870 | SmallString<256> SymbolName; |
1871 | if (F == FragmentNum::main()) |
1872 | SymbolName = formatv(Fmt: "GCC_except_table{0:x-}" , Vals: getFunctionNumber()); |
1873 | else |
1874 | SymbolName = formatv(Fmt: "GCC_cold_except_table{0:x-}.{1}" , |
1875 | Vals: getFunctionNumber(), Vals: F.get()); |
1876 | |
1877 | LSDASymbols[F.get()] = BC.Ctx->getOrCreateSymbol(Name: SymbolName); |
1878 | |
1879 | return LSDASymbols[F.get()]; |
1880 | } |
1881 | |
1882 | void setOutputDataAddress(uint64_t Address) { OutputDataOffset = Address; } |
1883 | |
1884 | uint64_t getOutputDataAddress() const { return OutputDataOffset; } |
1885 | |
1886 | void setOutputColdDataAddress(uint64_t Address) { |
1887 | OutputColdDataOffset = Address; |
1888 | } |
1889 | |
1890 | uint64_t getOutputColdDataAddress() const { return OutputColdDataOffset; } |
1891 | |
1892 | /// If \p Address represents an access to a constant island managed by this |
1893 | /// function, return a symbol so code can safely refer to it. Otherwise, |
1894 | /// return nullptr. First return value is the symbol for reference in the |
1895 | /// hot code area while the second return value is the symbol for reference |
1896 | /// in the cold code area, as when the function is split the islands are |
1897 | /// duplicated. |
1898 | MCSymbol *getOrCreateIslandAccess(uint64_t Address) { |
1899 | if (!Islands) |
1900 | return nullptr; |
1901 | |
1902 | MCSymbol *Symbol; |
1903 | if (!isInConstantIsland(Address)) |
1904 | return nullptr; |
1905 | |
1906 | // Register our island at global namespace |
1907 | Symbol = BC.getOrCreateGlobalSymbol(Address, Prefix: "ISLANDat" ); |
1908 | |
1909 | // Internal bookkeeping |
1910 | const uint64_t Offset = Address - getAddress(); |
1911 | assert((!Islands->Offsets.count(Offset) || |
1912 | Islands->Offsets[Offset] == Symbol) && |
1913 | "Inconsistent island symbol management" ); |
1914 | if (!Islands->Offsets.count(x: Offset)) { |
1915 | Islands->Offsets[Offset] = Symbol; |
1916 | Islands->Symbols.insert(Ptr: Symbol); |
1917 | } |
1918 | return Symbol; |
1919 | } |
1920 | |
1921 | /// Support dynamic relocations in constant islands, which may happen if |
1922 | /// binary is linked with -z notext option. |
1923 | Error markIslandDynamicRelocationAtAddress(uint64_t Address) { |
1924 | if (!isInConstantIsland(Address)) |
1925 | return createFatalBOLTError( |
1926 | S: Twine("dynamic relocation found for text section at 0x" ) + |
1927 | Twine::utohexstr(Val: Address) + Twine("\n" )); |
1928 | |
1929 | // Mark island to have dynamic relocation |
1930 | Islands->HasDynamicRelocations = true; |
1931 | |
1932 | // Create island access, so we would emit the label and |
1933 | // move binary data during updateOutputValues, making us emit |
1934 | // dynamic relocation with the right offset value. |
1935 | getOrCreateIslandAccess(Address); |
1936 | return Error::success(); |
1937 | } |
1938 | |
1939 | bool hasDynamicRelocationAtIsland() const { |
1940 | return !!(Islands && Islands->HasDynamicRelocations); |
1941 | } |
1942 | |
1943 | /// Called by an external function which wishes to emit references to constant |
1944 | /// island symbols of this function. We create a proxy for it, so we emit |
1945 | /// separate symbols when emitting our constant island on behalf of this other |
1946 | /// function. |
1947 | MCSymbol *getOrCreateProxyIslandAccess(uint64_t Address, |
1948 | BinaryFunction &Referrer) { |
1949 | MCSymbol *Symbol = getOrCreateIslandAccess(Address); |
1950 | if (!Symbol) |
1951 | return nullptr; |
1952 | |
1953 | MCSymbol *Proxy; |
1954 | if (!Islands->Proxies[&Referrer].count(x: Symbol)) { |
1955 | Proxy = BC.Ctx->getOrCreateSymbol(Name: Symbol->getName() + ".proxy.for." + |
1956 | Referrer.getPrintName()); |
1957 | Islands->Proxies[&Referrer][Symbol] = Proxy; |
1958 | Islands->Proxies[&Referrer][Proxy] = Symbol; |
1959 | } |
1960 | Proxy = Islands->Proxies[&Referrer][Symbol]; |
1961 | return Proxy; |
1962 | } |
1963 | |
1964 | /// Make this function depend on \p BF because we have a reference to its |
1965 | /// constant island. When emitting this function, we will also emit |
1966 | // \p BF's constants. This only happens in custom AArch64 assembly code. |
1967 | void createIslandDependency(MCSymbol *Island, BinaryFunction *BF) { |
1968 | if (!Islands) |
1969 | Islands = std::make_unique<IslandInfo>(); |
1970 | |
1971 | Islands->Dependency.insert(Ptr: BF); |
1972 | Islands->ProxySymbols[Island] = BF; |
1973 | } |
1974 | |
1975 | /// Detects whether \p Address is inside a data region in this function |
1976 | /// (constant islands). |
1977 | bool isInConstantIsland(uint64_t Address) const { |
1978 | if (!Islands) |
1979 | return false; |
1980 | |
1981 | if (Address < getAddress()) |
1982 | return false; |
1983 | |
1984 | uint64_t Offset = Address - getAddress(); |
1985 | |
1986 | if (Offset >= getMaxSize()) |
1987 | return false; |
1988 | |
1989 | auto DataIter = Islands->DataOffsets.upper_bound(x: Offset); |
1990 | if (DataIter == Islands->DataOffsets.begin()) |
1991 | return false; |
1992 | DataIter = std::prev(x: DataIter); |
1993 | |
1994 | auto CodeIter = Islands->CodeOffsets.upper_bound(x: Offset); |
1995 | if (CodeIter == Islands->CodeOffsets.begin()) |
1996 | return true; |
1997 | |
1998 | return *std::prev(x: CodeIter) <= *DataIter; |
1999 | } |
2000 | |
2001 | uint16_t getConstantIslandAlignment() const { |
2002 | return Islands ? Islands->getAlignment() : 1; |
2003 | } |
2004 | |
2005 | uint64_t |
2006 | estimateConstantIslandSize(const BinaryFunction *OnBehalfOf = nullptr) const { |
2007 | if (!Islands) |
2008 | return 0; |
2009 | |
2010 | uint64_t Size = 0; |
2011 | for (auto DataIter = Islands->DataOffsets.begin(); |
2012 | DataIter != Islands->DataOffsets.end(); ++DataIter) { |
2013 | auto NextData = std::next(x: DataIter); |
2014 | auto CodeIter = Islands->CodeOffsets.lower_bound(x: *DataIter); |
2015 | if (CodeIter == Islands->CodeOffsets.end() && |
2016 | NextData == Islands->DataOffsets.end()) { |
2017 | Size += getMaxSize() - *DataIter; |
2018 | continue; |
2019 | } |
2020 | |
2021 | uint64_t NextMarker; |
2022 | if (CodeIter == Islands->CodeOffsets.end()) |
2023 | NextMarker = *NextData; |
2024 | else if (NextData == Islands->DataOffsets.end()) |
2025 | NextMarker = *CodeIter; |
2026 | else |
2027 | NextMarker = (*CodeIter > *NextData) ? *NextData : *CodeIter; |
2028 | |
2029 | Size += NextMarker - *DataIter; |
2030 | } |
2031 | |
2032 | if (!OnBehalfOf) { |
2033 | for (BinaryFunction *ExternalFunc : Islands->Dependency) { |
2034 | Size = alignTo(Value: Size, Align: ExternalFunc->getConstantIslandAlignment()); |
2035 | Size += ExternalFunc->estimateConstantIslandSize(OnBehalfOf: this); |
2036 | } |
2037 | } |
2038 | |
2039 | return Size; |
2040 | } |
2041 | |
2042 | bool hasIslandsInfo() const { |
2043 | return Islands && (hasConstantIsland() || !Islands->Dependency.empty()); |
2044 | } |
2045 | |
2046 | bool hasConstantIsland() const { |
2047 | return Islands && !Islands->DataOffsets.empty(); |
2048 | } |
2049 | |
2050 | /// Return true iff the symbol could be seen inside this function otherwise |
2051 | /// it is probably another function. |
2052 | bool isSymbolValidInScope(const SymbolRef &Symbol, uint64_t SymbolSize) const; |
2053 | |
2054 | /// Disassemble function from raw data. |
2055 | /// If successful, this function will populate the list of instructions |
2056 | /// for this function together with offsets from the function start |
2057 | /// in the input. It will also populate Labels with destinations for |
2058 | /// local branches, and TakenBranches with [from, to] info. |
2059 | /// |
2060 | /// The Function should be properly initialized before this function |
2061 | /// is called. I.e. function address and size should be set. |
2062 | /// |
2063 | /// Returns true on successful disassembly, and updates the current |
2064 | /// state to State:Disassembled. |
2065 | /// |
2066 | /// Returns false if disassembly failed. |
2067 | Error disassemble(); |
2068 | |
2069 | /// An external interface to register a branch while the function is in |
2070 | /// disassembled state. Allows to make custom modifications to the |
2071 | /// disassembler. E.g., a pre-CFG pass can add an instruction and register |
2072 | /// a branch that will later be used during the CFG construction. |
2073 | /// |
2074 | /// Return a label at the branch destination. |
2075 | MCSymbol *registerBranch(uint64_t Src, uint64_t Dst); |
2076 | |
2077 | Error handlePCRelOperand(MCInst &Instruction, uint64_t Address, |
2078 | uint64_t Size); |
2079 | |
2080 | MCSymbol *handleExternalReference(MCInst &Instruction, uint64_t Size, |
2081 | uint64_t Offset, uint64_t TargetAddress, |
2082 | bool &IsCall); |
2083 | |
2084 | void handleIndirectBranch(MCInst &Instruction, uint64_t Size, |
2085 | uint64_t Offset); |
2086 | |
2087 | // Check for linker veneers, which lack relocations and need manual |
2088 | // adjustments. |
2089 | void handleAArch64IndirectCall(MCInst &Instruction, const uint64_t Offset); |
2090 | |
2091 | /// Scan function for references to other functions. In relocation mode, |
2092 | /// add relocations for external references. In non-relocation mode, detect |
2093 | /// and mark new entry points. |
2094 | /// |
2095 | /// Return true on success. False if the disassembly failed or relocations |
2096 | /// could not be created. |
2097 | bool scanExternalRefs(); |
2098 | |
2099 | /// Return the size of a data object located at \p Offset in the function. |
2100 | /// Return 0 if there is no data object at the \p Offset. |
2101 | size_t getSizeOfDataInCodeAt(uint64_t Offset) const; |
2102 | |
2103 | /// Verify that starting at \p Offset function contents are filled with |
2104 | /// zero-value bytes. |
2105 | bool isZeroPaddingAt(uint64_t Offset) const; |
2106 | |
2107 | /// Check that entry points have an associated instruction at their |
2108 | /// offsets after disassembly. |
2109 | void postProcessEntryPoints(); |
2110 | |
2111 | /// Post-processing for jump tables after disassembly. Since their |
2112 | /// boundaries are not known until all call sites are seen, we need this |
2113 | /// extra pass to perform any final adjustments. |
2114 | void postProcessJumpTables(); |
2115 | |
2116 | /// Builds a list of basic blocks with successor and predecessor info. |
2117 | /// |
2118 | /// The function should in Disassembled state prior to call. |
2119 | /// |
2120 | /// Returns true on success and update the current function state to |
2121 | /// State::CFG. Returns false if CFG cannot be built. |
2122 | Error buildCFG(MCPlusBuilder::AllocatorIdTy); |
2123 | |
2124 | /// Perform post-processing of the CFG. |
2125 | void postProcessCFG(); |
2126 | |
2127 | /// Verify that any assumptions we've made about indirect branches were |
2128 | /// correct and also make any necessary changes to unknown indirect branches. |
2129 | /// |
2130 | /// Catch-22: we need to know indirect branch targets to build CFG, and |
2131 | /// in order to determine the value for indirect branches we need to know CFG. |
2132 | /// |
2133 | /// As such, the process of decoding indirect branches is broken into 2 steps: |
2134 | /// first we make our best guess about a branch without knowing the CFG, |
2135 | /// and later after we have the CFG for the function, we verify our earlier |
2136 | /// assumptions and also do our best at processing unknown indirect branches. |
2137 | /// |
2138 | /// Return true upon successful processing, or false if the control flow |
2139 | /// cannot be statically evaluated for any given indirect branch. |
2140 | bool postProcessIndirectBranches(MCPlusBuilder::AllocatorIdTy AllocId); |
2141 | |
2142 | /// Validate that all data references to function offsets are claimed by |
2143 | /// recognized jump tables. Register externally referenced blocks as entry |
2144 | /// points. Returns true if there are no unclaimed externally referenced |
2145 | /// offsets. |
2146 | bool validateExternallyReferencedOffsets(); |
2147 | |
2148 | /// Return all call site profile info for this function. |
2149 | IndirectCallSiteProfile &getAllCallSites() { return AllCallSites; } |
2150 | |
2151 | const IndirectCallSiteProfile &getAllCallSites() const { |
2152 | return AllCallSites; |
2153 | } |
2154 | |
2155 | /// Walks the list of basic blocks filling in missing information about |
2156 | /// edge frequency for fall-throughs. |
2157 | /// |
2158 | /// Assumes the CFG has been built and edge frequency for taken branches |
2159 | /// has been filled with LBR data. |
2160 | void inferFallThroughCounts(); |
2161 | |
2162 | /// Clear execution profile of the function. |
2163 | void clearProfile(); |
2164 | |
2165 | /// Converts conditional tail calls to unconditional tail calls. We do this to |
2166 | /// handle conditional tail calls correctly and to give a chance to the |
2167 | /// simplify conditional tail call pass to decide whether to re-optimize them |
2168 | /// using profile information. |
2169 | void removeConditionalTailCalls(); |
2170 | |
2171 | // Convert COUNT_NO_PROFILE to 0 |
2172 | void removeTagsFromProfile(); |
2173 | |
2174 | /// Computes a function hotness score: the sum of the products of BB frequency |
2175 | /// and size. |
2176 | uint64_t getFunctionScore() const; |
2177 | |
2178 | /// Get the number of instructions within this function. |
2179 | uint64_t getInstructionCount() const; |
2180 | |
2181 | const CFIInstrMapType &getFDEProgram() const { return FrameInstructions; } |
2182 | |
2183 | void moveRememberRestorePair(BinaryBasicBlock *BB); |
2184 | |
2185 | bool replayCFIInstrs(int32_t FromState, int32_t ToState, |
2186 | BinaryBasicBlock *InBB, |
2187 | BinaryBasicBlock::iterator InsertIt); |
2188 | |
2189 | /// unwindCFIState is used to unwind from a higher to a lower state number |
2190 | /// without using remember-restore instructions. We do that by keeping track |
2191 | /// of what values have been changed from state A to B and emitting |
2192 | /// instructions that undo this change. |
2193 | SmallVector<int32_t, 4> unwindCFIState(int32_t FromState, int32_t ToState, |
2194 | BinaryBasicBlock *InBB, |
2195 | BinaryBasicBlock::iterator &InsertIt); |
2196 | |
2197 | /// After reordering, this function checks the state of CFI and fixes it if it |
2198 | /// is corrupted. If it is unable to fix it, it returns false. |
2199 | bool finalizeCFIState(); |
2200 | |
2201 | /// Return true if this function needs an address-translation table after |
2202 | /// its code emission. |
2203 | bool requiresAddressTranslation() const; |
2204 | |
2205 | /// Return true if the linker needs to generate an address map for this |
2206 | /// function. Used for keeping track of the mapping from input to out |
2207 | /// addresses of basic blocks. |
2208 | bool requiresAddressMap() const; |
2209 | |
2210 | /// Adjust branch instructions to match the CFG. |
2211 | /// |
2212 | /// As it comes to internal branches, the CFG represents "the ultimate source |
2213 | /// of truth". Transformations on functions and blocks have to update the CFG |
2214 | /// and fixBranches() would make sure the correct branch instructions are |
2215 | /// inserted at the end of basic blocks. |
2216 | /// |
2217 | /// We do require a conditional branch at the end of the basic block if |
2218 | /// the block has 2 successors as CFG currently lacks the conditional |
2219 | /// code support (it will probably stay that way). We only use this |
2220 | /// branch instruction for its conditional code, the destination is |
2221 | /// determined by CFG - first successor representing true/taken branch, |
2222 | /// while the second successor - false/fall-through branch. |
2223 | /// |
2224 | /// When we reverse the branch condition, the CFG is updated accordingly. |
2225 | void fixBranches(); |
2226 | |
2227 | /// Mark function as finalized. No further optimizations are permitted. |
2228 | void setFinalized() { CurrentState = State::CFG_Finalized; } |
2229 | |
2230 | void setEmitted(bool KeepCFG = false) { |
2231 | CurrentState = State::EmittedCFG; |
2232 | if (!KeepCFG) { |
2233 | releaseCFG(); |
2234 | CurrentState = State::Emitted; |
2235 | } |
2236 | } |
2237 | |
2238 | /// Process LSDA information for the function. |
2239 | Error parseLSDA(ArrayRef<uint8_t> LSDAData, uint64_t LSDAAddress); |
2240 | |
2241 | /// Update exception handling ranges for the function. |
2242 | void updateEHRanges(); |
2243 | |
2244 | /// Traverse cold basic blocks and replace references to constants in islands |
2245 | /// with a proxy symbol for the duplicated constant island that is going to be |
2246 | /// emitted in the cold region. |
2247 | void duplicateConstantIslands(); |
2248 | |
2249 | /// Merge profile data of this function into those of the given |
2250 | /// function. The functions should have been proven identical with |
2251 | /// isIdenticalWith. |
2252 | void mergeProfileDataInto(BinaryFunction &BF) const; |
2253 | |
2254 | /// Returns the last computed hash value of the function. |
2255 | size_t getHash() const { return Hash; } |
2256 | |
2257 | using OperandHashFuncTy = |
2258 | function_ref<typename std::string(const MCOperand &)>; |
2259 | |
2260 | /// Compute the hash value of the function based on its contents. |
2261 | /// |
2262 | /// If \p UseDFS is set, process basic blocks in DFS order. Otherwise, use |
2263 | /// the existing layout order. |
2264 | /// \p HashFunction specifies which function is used for BF hashing. |
2265 | /// |
2266 | /// By default, instruction operands are ignored while calculating the hash. |
2267 | /// The caller can change this via passing \p OperandHashFunc function. |
2268 | /// The return result of this function will be mixed with internal hash. |
2269 | size_t computeHash( |
2270 | bool UseDFS = false, HashFunction HashFunction = HashFunction::Default, |
2271 | OperandHashFuncTy OperandHashFunc = [](const MCOperand &) { |
2272 | return std::string(); |
2273 | }) const; |
2274 | |
2275 | /// Compute hash values for each block of the function. |
2276 | /// \p HashFunction specifies which function is used for BB hashing. |
2277 | void |
2278 | computeBlockHashes(HashFunction HashFunction = HashFunction::Default) const; |
2279 | |
2280 | void setDWARFUnit(DWARFUnit *Unit) { DwarfUnit = Unit; } |
2281 | |
2282 | /// Return DWARF compile unit for this function. |
2283 | DWARFUnit *getDWARFUnit() const { return DwarfUnit; } |
2284 | |
2285 | /// Return line info table for this function. |
2286 | const DWARFDebugLine::LineTable *getDWARFLineTable() const { |
2287 | return getDWARFUnit() ? BC.DwCtx->getLineTableForUnit(U: getDWARFUnit()) |
2288 | : nullptr; |
2289 | } |
2290 | |
2291 | /// Finalize profile for the function. |
2292 | void postProcessProfile(); |
2293 | |
2294 | /// Returns an estimate of the function's hot part after splitting. |
2295 | /// This is a very rough estimate, as with C++ exceptions there are |
2296 | /// blocks we don't move, and it makes no attempt at estimating the size |
2297 | /// of the added/removed branch instructions. |
2298 | /// Note that this size is optimistic and the actual size may increase |
2299 | /// after relaxation. |
2300 | size_t estimateHotSize(const bool UseSplitSize = true) const { |
2301 | size_t Estimate = 0; |
2302 | if (UseSplitSize && isSplit()) { |
2303 | for (const BinaryBasicBlock &BB : blocks()) |
2304 | if (!BB.isCold()) |
2305 | Estimate += BC.computeCodeSize(Beg: BB.begin(), End: BB.end()); |
2306 | } else { |
2307 | for (const BinaryBasicBlock &BB : blocks()) |
2308 | if (BB.getKnownExecutionCount() != 0) |
2309 | Estimate += BC.computeCodeSize(Beg: BB.begin(), End: BB.end()); |
2310 | } |
2311 | return Estimate; |
2312 | } |
2313 | |
2314 | size_t estimateColdSize() const { |
2315 | if (!isSplit()) |
2316 | return estimateSize(); |
2317 | size_t Estimate = 0; |
2318 | for (const BinaryBasicBlock &BB : blocks()) |
2319 | if (BB.isCold()) |
2320 | Estimate += BC.computeCodeSize(Beg: BB.begin(), End: BB.end()); |
2321 | return Estimate; |
2322 | } |
2323 | |
2324 | size_t estimateSize() const { |
2325 | size_t Estimate = 0; |
2326 | for (const BinaryBasicBlock &BB : blocks()) |
2327 | Estimate += BC.computeCodeSize(Beg: BB.begin(), End: BB.end()); |
2328 | return Estimate; |
2329 | } |
2330 | |
2331 | /// Return output address ranges for a function. |
2332 | DebugAddressRangesVector getOutputAddressRanges() const; |
2333 | |
2334 | /// Given an address corresponding to an instruction in the input binary, |
2335 | /// return an address of this instruction in output binary. |
2336 | /// |
2337 | /// Return 0 if no matching address could be found or the instruction was |
2338 | /// removed. |
2339 | uint64_t translateInputToOutputAddress(uint64_t Address) const; |
2340 | |
2341 | /// Translate a contiguous range of addresses in the input binary into a set |
2342 | /// of ranges in the output binary. |
2343 | DebugAddressRangesVector |
2344 | translateInputToOutputRange(DebugAddressRange InRange) const; |
2345 | |
2346 | /// Return true if the function is an AArch64 linker inserted veneer |
2347 | bool isAArch64Veneer() const; |
2348 | |
2349 | virtual ~BinaryFunction(); |
2350 | }; |
2351 | |
2352 | inline raw_ostream &operator<<(raw_ostream &OS, |
2353 | const BinaryFunction &Function) { |
2354 | OS << Function.getPrintName(); |
2355 | return OS; |
2356 | } |
2357 | |
2358 | } // namespace bolt |
2359 | |
2360 | // GraphTraits specializations for function basic block graphs (CFGs) |
2361 | template <> |
2362 | struct GraphTraits<bolt::BinaryFunction *> |
2363 | : public GraphTraits<bolt::BinaryBasicBlock *> { |
2364 | static NodeRef getEntryNode(bolt::BinaryFunction *F) { |
2365 | return F->getLayout().block_front(); |
2366 | } |
2367 | |
2368 | using nodes_iterator = pointer_iterator<bolt::BinaryFunction::iterator>; |
2369 | |
2370 | static nodes_iterator nodes_begin(bolt::BinaryFunction *F) { |
2371 | llvm_unreachable("Not implemented" ); |
2372 | return nodes_iterator(F->begin()); |
2373 | } |
2374 | static nodes_iterator nodes_end(bolt::BinaryFunction *F) { |
2375 | llvm_unreachable("Not implemented" ); |
2376 | return nodes_iterator(F->end()); |
2377 | } |
2378 | static size_t size(bolt::BinaryFunction *F) { return F->size(); } |
2379 | }; |
2380 | |
2381 | template <> |
2382 | struct GraphTraits<const bolt::BinaryFunction *> |
2383 | : public GraphTraits<const bolt::BinaryBasicBlock *> { |
2384 | static NodeRef getEntryNode(const bolt::BinaryFunction *F) { |
2385 | return F->getLayout().block_front(); |
2386 | } |
2387 | |
2388 | using nodes_iterator = pointer_iterator<bolt::BinaryFunction::const_iterator>; |
2389 | |
2390 | static nodes_iterator nodes_begin(const bolt::BinaryFunction *F) { |
2391 | llvm_unreachable("Not implemented" ); |
2392 | return nodes_iterator(F->begin()); |
2393 | } |
2394 | static nodes_iterator nodes_end(const bolt::BinaryFunction *F) { |
2395 | llvm_unreachable("Not implemented" ); |
2396 | return nodes_iterator(F->end()); |
2397 | } |
2398 | static size_t size(const bolt::BinaryFunction *F) { return F->size(); } |
2399 | }; |
2400 | |
2401 | template <> |
2402 | struct GraphTraits<Inverse<bolt::BinaryFunction *>> |
2403 | : public GraphTraits<Inverse<bolt::BinaryBasicBlock *>> { |
2404 | static NodeRef getEntryNode(Inverse<bolt::BinaryFunction *> G) { |
2405 | return G.Graph->getLayout().block_front(); |
2406 | } |
2407 | }; |
2408 | |
2409 | template <> |
2410 | struct GraphTraits<Inverse<const bolt::BinaryFunction *>> |
2411 | : public GraphTraits<Inverse<const bolt::BinaryBasicBlock *>> { |
2412 | static NodeRef getEntryNode(Inverse<const bolt::BinaryFunction *> G) { |
2413 | return G.Graph->getLayout().block_front(); |
2414 | } |
2415 | }; |
2416 | |
2417 | } // namespace llvm |
2418 | |
2419 | #endif |
2420 | |