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