1	//===- bolt/Core/BinaryFunction.cpp - Low-level function ------------------===//
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 implements the BinaryFunction class.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "bolt/Core/BinaryFunction.h"
14	#include "bolt/Core/BinaryBasicBlock.h"
15	#include "bolt/Core/DynoStats.h"
16	#include "bolt/Core/HashUtilities.h"
17	#include "bolt/Core/MCPlusBuilder.h"
18	#include "bolt/Utils/NameResolver.h"
19	#include "bolt/Utils/NameShortener.h"
20	#include "bolt/Utils/Utils.h"
21	#include "llvm/ADT/STLExtras.h"
22	#include "llvm/ADT/SmallSet.h"
23	#include "llvm/ADT/StringExtras.h"
24	#include "llvm/ADT/StringRef.h"
25	#include "llvm/Demangle/Demangle.h"
26	#include "llvm/MC/MCAsmInfo.h"
27	#include "llvm/MC/MCContext.h"
28	#include "llvm/MC/MCDisassembler/MCDisassembler.h"
29	#include "llvm/MC/MCExpr.h"
30	#include "llvm/MC/MCInst.h"
31	#include "llvm/MC/MCInstPrinter.h"
32	#include "llvm/MC/MCRegisterInfo.h"
33	#include "llvm/MC/MCSymbol.h"
34	#include "llvm/Object/ObjectFile.h"
35	#include "llvm/Support/CommandLine.h"
36	#include "llvm/Support/Debug.h"
37	#include "llvm/Support/GenericDomTreeConstruction.h"
38	#include "llvm/Support/GenericLoopInfoImpl.h"
39	#include "llvm/Support/GraphWriter.h"
40	#include "llvm/Support/LEB128.h"
41	#include "llvm/Support/Regex.h"
42	#include "llvm/Support/Timer.h"
43	#include "llvm/Support/raw_ostream.h"
44	#include "llvm/Support/xxhash.h"
45	#include <functional>
46	#include <limits>
47	#include <numeric>
48	#include <string>
49
50	#define DEBUG_TYPE "bolt"
51
52	using namespace llvm;
53	using namespace bolt;
54
55	namespace opts {
56
57	extern cl::OptionCategory BoltCategory;
58	extern cl::OptionCategory BoltOptCategory;
59
60	extern cl::opt<bool> EnableBAT;
61	extern cl::opt<bool> Instrument;
62	extern cl::opt<bool> StrictMode;
63	extern cl::opt<bool> UpdateDebugSections;
64	extern cl::opt<unsigned> Verbosity;
65
66	extern bool processAllFunctions();
67
68	cl::opt<bool> CheckEncoding(
69	"check-encoding",
70	cl::desc("perform verification of LLVM instruction encoding/decoding. "
71	"Every instruction in the input is decoded and re-encoded. "
72	"If the resulting bytes do not match the input, a warning message "
73	"is printed."),
74	cl::Hidden, cl::cat(BoltCategory));
75
76	static cl::opt<bool> DotToolTipCode(
77	"dot-tooltip-code",
78	cl::desc("add basic block instructions as tool tips on nodes"), cl::Hidden,
79	cl::cat(BoltCategory));
80
81	cl::opt<JumpTableSupportLevel>
82	JumpTables("jump-tables",
83	cl::desc("jump tables support (default=basic)"),
84	cl::init(Val: JTS_BASIC),
85	cl::values(
86	clEnumValN(JTS_NONE, "none",
87	"do not optimize functions with jump tables"),
88	clEnumValN(JTS_BASIC, "basic",
89	"optimize functions with jump tables"),
90	clEnumValN(JTS_MOVE, "move",
91	"move jump tables to a separate section"),
92	clEnumValN(JTS_SPLIT, "split",
93	"split jump tables section into hot and cold based on "
94	"function execution frequency"),
95	clEnumValN(JTS_AGGRESSIVE, "aggressive",
96	"aggressively split jump tables section based on usage "
97	"of the tables")),
98	cl::ZeroOrMore,
99	cl::cat(BoltOptCategory));
100
101	static cl::opt<bool> NoScan(
102	"no-scan",
103	cl::desc(
104	"do not scan cold functions for external references (may result in "
105	"slower binary)"),
106	cl::Hidden, cl::cat(BoltOptCategory));
107
108	cl::opt<bool>
109	PreserveBlocksAlignment("preserve-blocks-alignment",
110	cl::desc("try to preserve basic block alignment"),
111	cl::cat(BoltOptCategory));
112
113	static cl::opt<bool> PrintOutputAddressRange(
114	"print-output-address-range",
115	cl::desc(
116	"print output address range for each basic block in the function when"
117	"BinaryFunction::print is called"),
118	cl::Hidden, cl::cat(BoltOptCategory));
119
120	cl::opt<bool>
121	PrintDynoStats("dyno-stats",
122	cl::desc("print execution info based on profile"),
123	cl::cat(BoltCategory));
124
125	static cl::opt<bool>
126	PrintDynoStatsOnly("print-dyno-stats-only",
127	cl::desc("while printing functions output dyno-stats and skip instructions"),
128	cl::init(Val: false),
129	cl::Hidden,
130	cl::cat(BoltCategory));
131
132	static cl::list<std::string>
133	PrintOnly("print-only",
134	cl::CommaSeparated,
135	cl::desc("list of functions to print"),
136	cl::value_desc("func1,func2,func3,..."),
137	cl::Hidden,
138	cl::cat(BoltCategory));
139
140	cl::opt<bool>
141	TimeBuild("time-build",
142	cl::desc("print time spent constructing binary functions"),
143	cl::Hidden, cl::cat(BoltCategory));
144
145	cl::opt<bool>
146	TrapOnAVX512("trap-avx512",
147	cl::desc("in relocation mode trap upon entry to any function that uses "
148	"AVX-512 instructions"),
149	cl::init(Val: false),
150	cl::ZeroOrMore,
151	cl::Hidden,
152	cl::cat(BoltCategory));
153
154	bool shouldPrint(const BinaryFunction &Function) {
155	if (Function.isIgnored())
156	return false;
157
158	if (PrintOnly.empty())
159	return true;
160
161	for (std::string &Name : opts::PrintOnly) {
162	if (Function.hasNameRegex(NameRegex: Name)) {
163	return true;
164	}
165	}
166
167	return false;
168	}
169
170	} // namespace opts
171
172	namespace llvm {
173	namespace bolt {
174
175	template <typename R> static bool emptyRange(const R &Range) {
176	return Range.begin() == Range.end();
177	}
178
179	/// Gets debug line information for the instruction located at the given
180	/// address in the original binary. The SMLoc's pointer is used
181	/// to point to this information, which is represented by a
182	/// DebugLineTableRowRef. The returned pointer is null if no debug line
183	/// information for this instruction was found.
184	static SMLoc findDebugLineInformationForInstructionAt(
185	uint64_t Address, DWARFUnit *Unit,
186	const DWARFDebugLine::LineTable *LineTable) {
187	// We use the pointer in SMLoc to store an instance of DebugLineTableRowRef,
188	// which occupies 64 bits. Thus, we can only proceed if the struct fits into
189	// the pointer itself.
190	static_assert(
191	sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef),
192	"Cannot fit instruction debug line information into SMLoc's pointer");
193
194	SMLoc NullResult = DebugLineTableRowRef::NULL_ROW.toSMLoc();
195	uint32_t RowIndex = LineTable->lookupAddress(
196	Address: {.Address: Address, .SectionIndex: object::SectionedAddress::UndefSection});
197	if (RowIndex == LineTable->UnknownRowIndex)
198	return NullResult;
199
200	assert(RowIndex < LineTable->Rows.size() &&
201	"Line Table lookup returned invalid index.");
202
203	decltype(SMLoc().getPointer()) Ptr;
204	DebugLineTableRowRef *InstructionLocation =
205	reinterpret_cast<DebugLineTableRowRef *>(&Ptr);
206
207	InstructionLocation->DwCompileUnitIndex = Unit->getOffset();
208	InstructionLocation->RowIndex = RowIndex + 1;
209
210	return SMLoc::getFromPointer(Ptr);
211	}
212
213	static std::string buildSectionName(StringRef Prefix, StringRef Name,
214	const BinaryContext &BC) {
215	if (BC.isELF())
216	return (Prefix + Name).str();
217	static NameShortener NS;
218	return (Prefix + Twine(NS.getID(Name))).str();
219	}
220
221	static raw_ostream &operator<<(raw_ostream &OS,
222	const BinaryFunction::State State) {
223	switch (State) {
224	case BinaryFunction::State::Empty: OS << "empty"; break;
225	case BinaryFunction::State::Disassembled: OS << "disassembled"; break;
226	case BinaryFunction::State::CFG: OS << "CFG constructed"; break;
227	case BinaryFunction::State::CFG_Finalized: OS << "CFG finalized"; break;
228	case BinaryFunction::State::EmittedCFG: OS << "emitted with CFG"; break;
229	case BinaryFunction::State::Emitted: OS << "emitted"; break;
230	}
231
232	return OS;
233	}
234
235	std::string BinaryFunction::buildCodeSectionName(StringRef Name,
236	const BinaryContext &BC) {
237	return buildSectionName(Prefix: BC.isELF() ? ".local.text." : ".l.text.", Name, BC);
238	}
239
240	std::string BinaryFunction::buildColdCodeSectionName(StringRef Name,
241	const BinaryContext &BC) {
242	return buildSectionName(Prefix: BC.isELF() ? ".local.cold.text." : ".l.c.text.", Name,
243	BC);
244	}
245
246	uint64_t BinaryFunction::Count = 0;
247
248	std::optional<StringRef>
249	BinaryFunction::hasNameRegex(const StringRef Name) const {
250	const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str();
251	Regex MatchName(RegexName);
252	return forEachName(
253	Callback: [&MatchName](StringRef Name) { return MatchName.match(String: Name); });
254	}
255
256	std::optional<StringRef>
257	BinaryFunction::hasRestoredNameRegex(const StringRef Name) const {
258	const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str();
259	Regex MatchName(RegexName);
260	return forEachName(Callback: [&MatchName](StringRef Name) {
261	return MatchName.match(String: NameResolver::restore(Name));
262	});
263	}
264
265	std::string BinaryFunction::getDemangledName() const {
266	StringRef MangledName = NameResolver::restore(Name: getOneName());
267	return demangle(MangledName: MangledName.str());
268	}
269
270	BinaryBasicBlock *
271	BinaryFunction::getBasicBlockContainingOffset(uint64_t Offset) {
272	if (Offset > Size)
273	return nullptr;
274
275	if (BasicBlockOffsets.empty())
276	return nullptr;
277
278	/*
279	* This is commented out because it makes BOLT too slow.
280	* assert(std::is_sorted(BasicBlockOffsets.begin(),
281	* BasicBlockOffsets.end(),
282	* CompareBasicBlockOffsets())));
283	*/
284	auto I =
285	llvm::upper_bound(Range&: BasicBlockOffsets, Value: BasicBlockOffset(Offset, nullptr),
286	C: CompareBasicBlockOffsets());
287	assert(I != BasicBlockOffsets.begin() && "first basic block not at offset 0");
288	--I;
289	BinaryBasicBlock *BB = I->second;
290	return (Offset < BB->getOffset() + BB->getOriginalSize()) ? BB : nullptr;
291	}
292
293	void BinaryFunction::markUnreachableBlocks() {
294	std::stack<BinaryBasicBlock *> Stack;
295
296	for (BinaryBasicBlock &BB : blocks())
297	BB.markValid(Valid: false);
298
299	// Add all entries and landing pads as roots.
300	for (BinaryBasicBlock *BB : BasicBlocks) {
301	if (isEntryPoint(BB: *BB) || BB->isLandingPad()) {
302	Stack.push(x: BB);
303	BB->markValid(Valid: true);
304	continue;
305	}
306	// FIXME:
307	// Also mark BBs with indirect jumps as reachable, since we do not
308	// support removing unused jump tables yet (GH-issue20).
309	for (const MCInst &Inst : *BB) {
310	if (BC.MIB->getJumpTable(Inst)) {
311	Stack.push(x: BB);
312	BB->markValid(Valid: true);
313	break;
314	}
315	}
316	}
317
318	// Determine reachable BBs from the entry point
319	while (!Stack.empty()) {
320	BinaryBasicBlock *BB = Stack.top();
321	Stack.pop();
322	for (BinaryBasicBlock *Succ : BB->successors()) {
323	if (Succ->isValid())
324	continue;
325	Succ->markValid(Valid: true);
326	Stack.push(x: Succ);
327	}
328	}
329	}
330
331	// Any unnecessary fallthrough jumps revealed after calling eraseInvalidBBs
332	// will be cleaned up by fixBranches().
333	std::pair<unsigned, uint64_t>
334	BinaryFunction::eraseInvalidBBs(const MCCodeEmitter *Emitter) {
335	DenseSet<const BinaryBasicBlock *> InvalidBBs;
336	unsigned Count = 0;
337	uint64_t Bytes = 0;
338	for (BinaryBasicBlock *const BB : BasicBlocks) {
339	if (!BB->isValid()) {
340	assert(!isEntryPoint(*BB) && "all entry blocks must be valid");
341	InvalidBBs.insert(V: BB);
342	++Count;
343	Bytes += BC.computeCodeSize(Beg: BB->begin(), End: BB->end(), Emitter);
344	}
345	}
346
347	Layout.eraseBasicBlocks(ToErase: InvalidBBs);
348
349	BasicBlockListType NewBasicBlocks;
350	for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
351	BinaryBasicBlock *BB = *I;
352	if (InvalidBBs.contains(V: BB)) {
353	// Make sure the block is removed from the list of predecessors.
354	BB->removeAllSuccessors();
355	DeletedBasicBlocks.push_back(Elt: BB);
356	} else {
357	NewBasicBlocks.push_back(Elt: BB);
358	}
359	}
360	BasicBlocks = std::move(NewBasicBlocks);
361
362	assert(BasicBlocks.size() == Layout.block_size());
363
364	// Update CFG state if needed
365	if (Count > 0)
366	recomputeLandingPads();
367
368	return std::make_pair(x&: Count, y&: Bytes);
369	}
370
371	bool BinaryFunction::isForwardCall(const MCSymbol *CalleeSymbol) const {
372	// This function should work properly before and after function reordering.
373	// In order to accomplish this, we use the function index (if it is valid).
374	// If the function indices are not valid, we fall back to the original
375	// addresses. This should be ok because the functions without valid indices
376	// should have been ordered with a stable sort.
377	const BinaryFunction *CalleeBF = BC.getFunctionForSymbol(Symbol: CalleeSymbol);
378	if (CalleeBF) {
379	if (CalleeBF->isInjected())
380	return true;
381
382	if (hasValidIndex() && CalleeBF->hasValidIndex()) {
383	return getIndex() < CalleeBF->getIndex();
384	} else if (hasValidIndex() && !CalleeBF->hasValidIndex()) {
385	return true;
386	} else if (!hasValidIndex() && CalleeBF->hasValidIndex()) {
387	return false;
388	} else {
389	return getAddress() < CalleeBF->getAddress();
390	}
391	} else {
392	// Absolute symbol.
393	ErrorOr<uint64_t> CalleeAddressOrError = BC.getSymbolValue(Symbol: *CalleeSymbol);
394	assert(CalleeAddressOrError && "unregistered symbol found");
395	return *CalleeAddressOrError > getAddress();
396	}
397	}
398
399	void BinaryFunction::dump() const {
400	// getDynoStats calls FunctionLayout::updateLayoutIndices and
401	// BasicBlock::analyzeBranch. The former cannot be const, but should be
402	// removed, the latter should be made const, but seems to require refactoring.
403	// Forcing all callers to have a non-const reference to BinaryFunction to call
404	// dump non-const however is not ideal either. Adding this const_cast is right
405	// now the best solution. It is safe, because BinaryFunction itself is not
406	// modified. Only BinaryBasicBlocks are actually modified (if it all) and we
407	// have mutable pointers to those regardless whether this function is
408	// const-qualified or not.
409	const_cast<BinaryFunction &>(*this).print(OS&: dbgs(), Annotation: "");
410	}
411
412	void BinaryFunction::print(raw_ostream &OS, std::string Annotation) {
413	if (!opts::shouldPrint(Function: *this))
414	return;
415
416	StringRef SectionName =
417	OriginSection ? OriginSection->getName() : "<no origin section>";
418	OS << "Binary Function \"" << *this << "\" " << Annotation << " {";
419	std::vector<StringRef> AllNames = getNames();
420	if (AllNames.size() > 1) {
421	OS << "\n All names : ";
422	const char *Sep = "";
423	for (const StringRef &Name : AllNames) {
424	OS << Sep << Name;
425	Sep = "\n ";
426	}
427	}
428	OS << "\n Number : " << FunctionNumber;
429	OS << "\n State : " << CurrentState;
430	OS << "\n Address : 0x" << Twine::utohexstr(Val: Address);
431	OS << "\n Size : 0x" << Twine::utohexstr(Val: Size);
432	OS << "\n MaxSize : 0x" << Twine::utohexstr(Val: MaxSize);
433	OS << "\n Offset : 0x" << Twine::utohexstr(Val: getFileOffset());
434	OS << "\n Section : " << SectionName;
435	OS << "\n Orc Section : " << getCodeSectionName();
436	OS << "\n LSDA : 0x" << Twine::utohexstr(Val: getLSDAAddress());
437	OS << "\n IsSimple : " << IsSimple;
438	OS << "\n IsMultiEntry: " << isMultiEntry();
439	OS << "\n IsSplit : " << isSplit();
440	OS << "\n BB Count : " << size();
441
442	if (HasUnknownControlFlow)
443	OS << "\n Unknown CF : true";
444	if (getPersonalityFunction())
445	OS << "\n Personality : " << getPersonalityFunction()->getName();
446	if (IsFragment)
447	OS << "\n IsFragment : true";
448	if (isFolded())
449	OS << "\n FoldedInto : " << *getFoldedIntoFunction();
450	for (BinaryFunction *ParentFragment : ParentFragments)
451	OS << "\n Parent : " << *ParentFragment;
452	if (!Fragments.empty()) {
453	OS << "\n Fragments : ";
454	ListSeparator LS;
455	for (BinaryFunction *Frag : Fragments)
456	OS << LS << *Frag;
457	}
458	if (hasCFG())
459	OS << "\n Hash : " << Twine::utohexstr(Val: computeHash());
460	if (isMultiEntry()) {
461	OS << "\n Secondary Entry Points : ";
462	ListSeparator LS;
463	for (const auto &KV : SecondaryEntryPoints)
464	OS << LS << KV.second->getName();
465	}
466	if (FrameInstructions.size())
467	OS << "\n CFI Instrs : " << FrameInstructions.size();
468	if (!Layout.block_empty()) {
469	OS << "\n BB Layout : ";
470	ListSeparator LS;
471	for (const BinaryBasicBlock *BB : Layout.blocks())
472	OS << LS << BB->getName();
473	}
474	if (getImageAddress())
475	OS << "\n Image : 0x" << Twine::utohexstr(Val: getImageAddress());
476	if (ExecutionCount != COUNT_NO_PROFILE) {
477	OS << "\n Exec Count : " << ExecutionCount;
478	OS << "\n Branch Count: " << RawBranchCount;
479	OS << "\n Profile Acc : " << format(Fmt: "%.1f%%", Vals: ProfileMatchRatio * 100.0f);
480	}
481
482	if (opts::PrintDynoStats && !getLayout().block_empty()) {
483	OS << '\n';
484	DynoStats dynoStats = getDynoStats(BF&: *this);
485	OS << dynoStats;
486	}
487
488	OS << "\n}\n";
489
490	if (opts::PrintDynoStatsOnly || !BC.InstPrinter)
491	return;
492
493	// Offset of the instruction in function.
494	uint64_t Offset = 0;
495
496	if (BasicBlocks.empty() && !Instructions.empty()) {
497	// Print before CFG was built.
498	for (const std::pair<const uint32_t, MCInst> &II : Instructions) {
499	Offset = II.first;
500
501	// Print label if exists at this offset.
502	auto LI = Labels.find(x: Offset);
503	if (LI != Labels.end()) {
504	if (const MCSymbol *EntrySymbol =
505	getSecondaryEntryPointSymbol(BBLabel: LI->second))
506	OS << EntrySymbol->getName() << " (Entry Point):\n";
507	OS << LI->second->getName() << ":\n";
508	}
509
510	BC.printInstruction(OS, Instruction: II.second, Offset, Function: this);
511	}
512	}
513
514	StringRef SplitPointMsg = "";
515	for (const FunctionFragment &FF : Layout.fragments()) {
516	OS << SplitPointMsg;
517	SplitPointMsg = "------- HOT-COLD SPLIT POINT -------\n\n";
518	for (const BinaryBasicBlock *BB : FF) {
519	OS << BB->getName() << " (" << BB->size()
520	<< " instructions, align : " << BB->getAlignment() << ")\n";
521
522	if (opts::PrintOutputAddressRange)
523	OS << formatv(Fmt: " Output Address Range: [{0:x}, {1:x}) ({2} bytes)\n",
524	Vals: BB->getOutputAddressRange().first,
525	Vals: BB->getOutputAddressRange().second, Vals: BB->getOutputSize());
526
527	if (isEntryPoint(BB: *BB)) {
528	if (MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB: *BB))
529	OS << " Secondary Entry Point: " << EntrySymbol->getName() << '\n';
530	else
531	OS << " Entry Point\n";
532	}
533
534	if (BB->isLandingPad())
535	OS << " Landing Pad\n";
536
537	uint64_t BBExecCount = BB->getExecutionCount();
538	if (hasValidProfile()) {
539	OS << " Exec Count : ";
540	if (BB->getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE)
541	OS << BBExecCount << '\n';
542	else
543	OS << "<unknown>\n";
544	}
545	if (BB->getCFIState() >= 0)
546	OS << " CFI State : " << BB->getCFIState() << '\n';
547	if (opts::EnableBAT) {
548	OS << " Input offset: 0x" << Twine::utohexstr(Val: BB->getInputOffset())
549	<< "\n";
550	}
551	if (!BB->pred_empty()) {
552	OS << " Predecessors: ";
553	ListSeparator LS;
554	for (BinaryBasicBlock *Pred : BB->predecessors())
555	OS << LS << Pred->getName();
556	OS << '\n';
557	}
558	if (!BB->throw_empty()) {
559	OS << " Throwers: ";
560	ListSeparator LS;
561	for (BinaryBasicBlock *Throw : BB->throwers())
562	OS << LS << Throw->getName();
563	OS << '\n';
564	}
565
566	Offset = alignTo(Value: Offset, Align: BB->getAlignment());
567
568	// Note: offsets are imprecise since this is happening prior to
569	// relaxation.
570	Offset = BC.printInstructions(OS, Begin: BB->begin(), End: BB->end(), Offset, Function: this);
571
572	if (!BB->succ_empty()) {
573	OS << " Successors: ";
574	// For more than 2 successors, sort them based on frequency.
575	std::vector<uint64_t> Indices(BB->succ_size());
576	std::iota(first: Indices.begin(), last: Indices.end(), value: 0);
577	if (BB->succ_size() > 2 && BB->getKnownExecutionCount()) {
578	llvm::stable_sort(Range&: Indices, C: [&](const uint64_t A, const uint64_t B) {
579	return BB->BranchInfo[B] < BB->BranchInfo[A];
580	});
581	}
582	ListSeparator LS;
583	for (unsigned I = 0; I < Indices.size(); ++I) {
584	BinaryBasicBlock *Succ = BB->Successors[Indices[I]];
585	const BinaryBasicBlock::BinaryBranchInfo &BI =
586	BB->BranchInfo[Indices[I]];
587	OS << LS << Succ->getName();
588	if (ExecutionCount != COUNT_NO_PROFILE &&
589	BI.MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
590	OS << " (mispreds: " << BI.MispredictedCount
591	<< ", count: " << BI.Count << ")";
592	} else if (ExecutionCount != COUNT_NO_PROFILE &&
593	BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
594	OS << " (inferred count: " << BI.Count << ")";
595	}
596	}
597	OS << '\n';
598	}
599
600	if (!BB->lp_empty()) {
601	OS << " Landing Pads: ";
602	ListSeparator LS;
603	for (BinaryBasicBlock *LP : BB->landing_pads()) {
604	OS << LS << LP->getName();
605	if (ExecutionCount != COUNT_NO_PROFILE) {
606	OS << " (count: " << LP->getExecutionCount() << ")";
607	}
608	}
609	OS << '\n';
610	}
611
612	// In CFG_Finalized state we can miscalculate CFI state at exit.
613	if (CurrentState == State::CFG) {
614	const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
615	if (CFIStateAtExit >= 0)
616	OS << " CFI State: " << CFIStateAtExit << '\n';
617	}
618
619	OS << '\n';
620	}
621	}
622
623	// Dump new exception ranges for the function.
624	if (!CallSites.empty()) {
625	OS << "EH table:\n";
626	for (const FunctionFragment &FF : getLayout().fragments()) {
627	for (const auto &FCSI : getCallSites(F: FF.getFragmentNum())) {
628	const CallSite &CSI = FCSI.second;
629	OS << " [" << *CSI.Start << ", " << *CSI.End << ") landing pad : ";
630	if (CSI.LP)
631	OS << *CSI.LP;
632	else
633	OS << "0";
634	OS << ", action : " << CSI.Action << '\n';
635	}
636	}
637	OS << '\n';
638	}
639
640	// Print all jump tables.
641	for (const std::pair<const uint64_t, JumpTable *> &JTI : JumpTables)
642	JTI.second->print(OS);
643
644	OS << "DWARF CFI Instructions:\n";
645	if (OffsetToCFI.size()) {
646	// Pre-buildCFG information
647	for (const std::pair<const uint32_t, uint32_t> &Elmt : OffsetToCFI) {
648	OS << format(Fmt: " %08x:\t", Vals: Elmt.first);
649	assert(Elmt.second < FrameInstructions.size() && "Incorrect CFI offset");
650	BinaryContext::printCFI(OS, Inst: FrameInstructions[Elmt.second]);
651	OS << "\n";
652	}
653	} else {
654	// Post-buildCFG information
655	for (uint32_t I = 0, E = FrameInstructions.size(); I != E; ++I) {
656	const MCCFIInstruction &CFI = FrameInstructions[I];
657	OS << format(Fmt: " %d:\t", Vals: I);
658	BinaryContext::printCFI(OS, Inst: CFI);
659	OS << "\n";
660	}
661	}
662	if (FrameInstructions.empty())
663	OS << " <empty>\n";
664
665	OS << "End of Function \"" << *this << "\"\n\n";
666	}
667
668	void BinaryFunction::printRelocations(raw_ostream &OS, uint64_t Offset,
669	uint64_t Size) const {
670	const char *Sep = " # Relocs: ";
671
672	auto RI = Relocations.lower_bound(x: Offset);
673	while (RI != Relocations.end() && RI->first < Offset + Size) {
674	OS << Sep << "(R: " << RI->second << ")";
675	Sep = ", ";
676	++RI;
677	}
678	}
679
680	static std::string mutateDWARFExpressionTargetReg(const MCCFIInstruction &Instr,
681	MCPhysReg NewReg) {
682	StringRef ExprBytes = Instr.getValues();
683	assert(ExprBytes.size() > 1 && "DWARF expression CFI is too short");
684	uint8_t Opcode = ExprBytes[0];
685	assert((Opcode == dwarf::DW_CFA_expression ||
686	Opcode == dwarf::DW_CFA_val_expression) &&
687	"invalid DWARF expression CFI");
688	(void)Opcode;
689	const uint8_t *const Start =
690	reinterpret_cast<const uint8_t *>(ExprBytes.drop_front(N: 1).data());
691	const uint8_t *const End =
692	reinterpret_cast<const uint8_t *>(Start + ExprBytes.size() - 1);
693	unsigned Size = 0;
694	decodeULEB128(p: Start, n: &Size, end: End);
695	assert(Size > 0 && "Invalid reg encoding for DWARF expression CFI");
696	SmallString<8> Tmp;
697	raw_svector_ostream OSE(Tmp);
698	encodeULEB128(Value: NewReg, OS&: OSE);
699	return Twine(ExprBytes.slice(Start: 0, End: 1))
700	.concat(Suffix: OSE.str())
701	.concat(Suffix: ExprBytes.drop_front(N: 1 + Size))
702	.str();
703	}
704
705	void BinaryFunction::mutateCFIRegisterFor(const MCInst &Instr,
706	MCPhysReg NewReg) {
707	const MCCFIInstruction *OldCFI = getCFIFor(Instr);
708	assert(OldCFI && "invalid CFI instr");
709	switch (OldCFI->getOperation()) {
710	default:
711	llvm_unreachable("Unexpected instruction");
712	case MCCFIInstruction::OpDefCfa:
713	setCFIFor(Instr, CFIInst: MCCFIInstruction::cfiDefCfa(L: nullptr, Register: NewReg,
714	Offset: OldCFI->getOffset()));
715	break;
716	case MCCFIInstruction::OpDefCfaRegister:
717	setCFIFor(Instr, CFIInst: MCCFIInstruction::createDefCfaRegister(L: nullptr, Register: NewReg));
718	break;
719	case MCCFIInstruction::OpOffset:
720	setCFIFor(Instr, CFIInst: MCCFIInstruction::createOffset(L: nullptr, Register: NewReg,
721	Offset: OldCFI->getOffset()));
722	break;
723	case MCCFIInstruction::OpRegister:
724	setCFIFor(Instr, CFIInst: MCCFIInstruction::createRegister(L: nullptr, Register1: NewReg,
725	Register2: OldCFI->getRegister2()));
726	break;
727	case MCCFIInstruction::OpSameValue:
728	setCFIFor(Instr, CFIInst: MCCFIInstruction::createSameValue(L: nullptr, Register: NewReg));
729	break;
730	case MCCFIInstruction::OpEscape:
731	setCFIFor(Instr,
732	CFIInst: MCCFIInstruction::createEscape(
733	L: nullptr,
734	Vals: StringRef(mutateDWARFExpressionTargetReg(Instr: *OldCFI, NewReg))));
735	break;
736	case MCCFIInstruction::OpRestore:
737	setCFIFor(Instr, CFIInst: MCCFIInstruction::createRestore(L: nullptr, Register: NewReg));
738	break;
739	case MCCFIInstruction::OpUndefined:
740	setCFIFor(Instr, CFIInst: MCCFIInstruction::createUndefined(L: nullptr, Register: NewReg));
741	break;
742	}
743	}
744
745	const MCCFIInstruction *BinaryFunction::mutateCFIOffsetFor(const MCInst &Instr,
746	int64_t NewOffset) {
747	const MCCFIInstruction *OldCFI = getCFIFor(Instr);
748	assert(OldCFI && "invalid CFI instr");
749	switch (OldCFI->getOperation()) {
750	default:
751	llvm_unreachable("Unexpected instruction");
752	case MCCFIInstruction::OpDefCfaOffset:
753	setCFIFor(Instr, CFIInst: MCCFIInstruction::cfiDefCfaOffset(L: nullptr, Offset: NewOffset));
754	break;
755	case MCCFIInstruction::OpAdjustCfaOffset:
756	setCFIFor(Instr,
757	CFIInst: MCCFIInstruction::createAdjustCfaOffset(L: nullptr, Adjustment: NewOffset));
758	break;
759	case MCCFIInstruction::OpDefCfa:
760	setCFIFor(Instr, CFIInst: MCCFIInstruction::cfiDefCfa(L: nullptr, Register: OldCFI->getRegister(),
761	Offset: NewOffset));
762	break;
763	case MCCFIInstruction::OpOffset:
764	setCFIFor(Instr, CFIInst: MCCFIInstruction::createOffset(
765	L: nullptr, Register: OldCFI->getRegister(), Offset: NewOffset));
766	break;
767	}
768	return getCFIFor(Instr);
769	}
770
771	IndirectBranchType
772	BinaryFunction::processIndirectBranch(MCInst &Instruction, unsigned Size,
773	uint64_t Offset,
774	uint64_t &TargetAddress) {
775	const unsigned PtrSize = BC.AsmInfo->getCodePointerSize();
776
777	// The instruction referencing memory used by the branch instruction.
778	// It could be the branch instruction itself or one of the instructions
779	// setting the value of the register used by the branch.
780	MCInst *MemLocInstr;
781
782	// Address of the table referenced by MemLocInstr. Could be either an
783	// array of function pointers, or a jump table.
784	uint64_t ArrayStart = 0;
785
786	unsigned BaseRegNum, IndexRegNum;
787	int64_t DispValue;
788	const MCExpr *DispExpr;
789
790	// In AArch, identify the instruction adding the PC-relative offset to
791	// jump table entries to correctly decode it.
792	MCInst *PCRelBaseInstr;
793	uint64_t PCRelAddr = 0;
794
795	auto Begin = Instructions.begin();
796	if (BC.isAArch64()) {
797	PreserveNops = BC.HasRelocations;
798	// Start at the last label as an approximation of the current basic block.
799	// This is a heuristic, since the full set of labels have yet to be
800	// determined
801	for (const uint32_t Offset :
802	llvm::make_first_range(c: llvm::reverse(C&: Labels))) {
803	auto II = Instructions.find(x: Offset);
804	if (II != Instructions.end()) {
805	Begin = II;
806	break;
807	}
808	}
809	}
810
811	IndirectBranchType BranchType = BC.MIB->analyzeIndirectBranch(
812	Instruction, Begin, End: Instructions.end(), PtrSize, MemLocInstr, BaseRegNum,
813	IndexRegNum, DispValue, DispExpr, PCRelBaseOut&: PCRelBaseInstr);
814
815	if (BranchType == IndirectBranchType::UNKNOWN && !MemLocInstr)
816	return BranchType;
817
818	if (MemLocInstr != &Instruction)
819	IndexRegNum = BC.MIB->getNoRegister();
820
821	if (BC.isAArch64()) {
822	const MCSymbol *Sym = BC.MIB->getTargetSymbol(Inst: *PCRelBaseInstr, OpNum: 1);
823	assert(Sym && "Symbol extraction failed");
824	ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(Symbol: *Sym);
825	if (SymValueOrError) {
826	PCRelAddr = *SymValueOrError;
827	} else {
828	for (std::pair<const uint32_t, MCSymbol *> &Elmt : Labels) {
829	if (Elmt.second == Sym) {
830	PCRelAddr = Elmt.first + getAddress();
831	break;
832	}
833	}
834	}
835	uint64_t InstrAddr = 0;
836	for (auto II = Instructions.rbegin(); II != Instructions.rend(); ++II) {
837	if (&II->second == PCRelBaseInstr) {
838	InstrAddr = II->first + getAddress();
839	break;
840	}
841	}
842	assert(InstrAddr != 0 && "instruction not found");
843	// We do this to avoid spurious references to code locations outside this
844	// function (for example, if the indirect jump lives in the last basic
845	// block of the function, it will create a reference to the next function).
846	// This replaces a symbol reference with an immediate.
847	BC.MIB->replaceMemOperandDisp(Inst&: *PCRelBaseInstr,
848	Operand: MCOperand::createImm(Val: PCRelAddr - InstrAddr));
849	// FIXME: Disable full jump table processing for AArch64 until we have a
850	// proper way of determining the jump table limits.
851	return IndirectBranchType::UNKNOWN;
852	}
853
854	// RIP-relative addressing should be converted to symbol form by now
855	// in processed instructions (but not in jump).
856	if (DispExpr) {
857	const MCSymbol *TargetSym;
858	uint64_t TargetOffset;
859	std::tie(args&: TargetSym, args&: TargetOffset) = BC.MIB->getTargetSymbolInfo(Expr: DispExpr);
860	ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(Symbol: *TargetSym);
861	assert(SymValueOrError && "global symbol needs a value");
862	ArrayStart = *SymValueOrError + TargetOffset;
863	BaseRegNum = BC.MIB->getNoRegister();
864	if (BC.isAArch64()) {
865	ArrayStart &= ~0xFFFULL;
866	ArrayStart += DispValue & 0xFFFULL;
867	}
868	} else {
869	ArrayStart = static_cast<uint64_t>(DispValue);
870	}
871
872	if (BaseRegNum == BC.MRI->getProgramCounter())
873	ArrayStart += getAddress() + Offset + Size;
874
875	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: addressed memory is 0x"
876	<< Twine::utohexstr(ArrayStart) << '\n');
877
878	ErrorOr<BinarySection &> Section = BC.getSectionForAddress(Address: ArrayStart);
879	if (!Section) {
880	// No section - possibly an absolute address. Since we don't allow
881	// internal function addresses to escape the function scope - we
882	// consider it a tail call.
883	if (opts::Verbosity >= 1) {
884	BC.errs() << "BOLT-WARNING: no section for address 0x"
885	<< Twine::utohexstr(Val: ArrayStart) << " referenced from function "
886	<< *this << '\n';
887	}
888	return IndirectBranchType::POSSIBLE_TAIL_CALL;
889	}
890	if (Section->isVirtual()) {
891	// The contents are filled at runtime.
892	return IndirectBranchType::POSSIBLE_TAIL_CALL;
893	}
894
895	if (BranchType == IndirectBranchType::POSSIBLE_FIXED_BRANCH) {
896	ErrorOr<uint64_t> Value = BC.getPointerAtAddress(Address: ArrayStart);
897	if (!Value)
898	return IndirectBranchType::UNKNOWN;
899
900	if (BC.getSectionForAddress(Address: ArrayStart)->isWritable())
901	return IndirectBranchType::UNKNOWN;
902
903	BC.outs() << "BOLT-INFO: fixed indirect branch detected in " << *this
904	<< " at 0x" << Twine::utohexstr(Val: getAddress() + Offset)
905	<< " referencing data at 0x" << Twine::utohexstr(Val: ArrayStart)
906	<< " the destination value is 0x" << Twine::utohexstr(Val: *Value)
907	<< '\n';
908
909	TargetAddress = *Value;
910	return BranchType;
911	}
912
913	// Check if there's already a jump table registered at this address.
914	MemoryContentsType MemType;
915	if (JumpTable *JT = BC.getJumpTableContainingAddress(Address: ArrayStart)) {
916	switch (JT->Type) {
917	case JumpTable::JTT_NORMAL:
918	MemType = MemoryContentsType::POSSIBLE_JUMP_TABLE;
919	break;
920	case JumpTable::JTT_PIC:
921	MemType = MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE;
922	break;
923	}
924	} else {
925	MemType = BC.analyzeMemoryAt(Address: ArrayStart, BF&: *this);
926	}
927
928	// Check that jump table type in instruction pattern matches memory contents.
929	JumpTable::JumpTableType JTType;
930	if (BranchType == IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE) {
931	if (MemType != MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE)
932	return IndirectBranchType::UNKNOWN;
933	JTType = JumpTable::JTT_PIC;
934	} else {
935	if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE)
936	return IndirectBranchType::UNKNOWN;
937
938	if (MemType == MemoryContentsType::UNKNOWN)
939	return IndirectBranchType::POSSIBLE_TAIL_CALL;
940
941	BranchType = IndirectBranchType::POSSIBLE_JUMP_TABLE;
942	JTType = JumpTable::JTT_NORMAL;
943	}
944
945	// Convert the instruction into jump table branch.
946	const MCSymbol *JTLabel = BC.getOrCreateJumpTable(Function&: *this, Address: ArrayStart, Type: JTType);
947	BC.MIB->replaceMemOperandDisp(Inst&: *MemLocInstr, Label: JTLabel, Ctx: BC.Ctx.get());
948	BC.MIB->setJumpTable(Inst&: Instruction, Value: ArrayStart, IndexReg: IndexRegNum);
949
950	JTSites.emplace_back(Args&: Offset, Args&: ArrayStart);
951
952	return BranchType;
953	}
954
955	MCSymbol *BinaryFunction::getOrCreateLocalLabel(uint64_t Address,
956	bool CreatePastEnd) {
957	const uint64_t Offset = Address - getAddress();
958
959	if ((Offset == getSize()) && CreatePastEnd)
960	return getFunctionEndLabel();
961
962	auto LI = Labels.find(x: Offset);
963	if (LI != Labels.end())
964	return LI->second;
965
966	// For AArch64, check if this address is part of a constant island.
967	if (BC.isAArch64()) {
968	if (MCSymbol *IslandSym = getOrCreateIslandAccess(Address))
969	return IslandSym;
970	}
971
972	MCSymbol *Label = BC.Ctx->createNamedTempSymbol();
973	Labels[Offset] = Label;
974
975	return Label;
976	}
977
978	ErrorOr<ArrayRef<uint8_t>> BinaryFunction::getData() const {
979	BinarySection &Section = *getOriginSection();
980	assert(Section.containsRange(getAddress(), getMaxSize()) &&
981	"wrong section for function");
982
983	if (!Section.isText() || Section.isVirtual() || !Section.getSize())
984	return std::make_error_code(e: std::errc::bad_address);
985
986	StringRef SectionContents = Section.getContents();
987
988	assert(SectionContents.size() == Section.getSize() &&
989	"section size mismatch");
990
991	// Function offset from the section start.
992	uint64_t Offset = getAddress() - Section.getAddress();
993	auto *Bytes = reinterpret_cast<const uint8_t *>(SectionContents.data());
994	return ArrayRef<uint8_t>(Bytes + Offset, getMaxSize());
995	}
996
997	size_t BinaryFunction::getSizeOfDataInCodeAt(uint64_t Offset) const {
998	if (!Islands)
999	return 0;
1000
1001	if (!llvm::is_contained(Range&: Islands->DataOffsets, Element: Offset))
1002	return 0;
1003
1004	auto Iter = Islands->CodeOffsets.upper_bound(x: Offset);
1005	if (Iter != Islands->CodeOffsets.end())
1006	return *Iter - Offset;
1007	return getSize() - Offset;
1008	}
1009
1010	bool BinaryFunction::isZeroPaddingAt(uint64_t Offset) const {
1011	ArrayRef<uint8_t> FunctionData = *getData();
1012	uint64_t EndOfCode = getSize();
1013	if (Islands) {
1014	auto Iter = Islands->DataOffsets.upper_bound(x: Offset);
1015	if (Iter != Islands->DataOffsets.end())
1016	EndOfCode = *Iter;
1017	}
1018	for (uint64_t I = Offset; I < EndOfCode; ++I)
1019	if (FunctionData[I] != 0)
1020	return false;
1021
1022	return true;
1023	}
1024
1025	Error BinaryFunction::handlePCRelOperand(MCInst &Instruction, uint64_t Address,
1026	uint64_t Size) {
1027	auto &MIB = BC.MIB;
1028	uint64_t TargetAddress = 0;
1029	if (!MIB->evaluateMemOperandTarget(Inst: Instruction, Target&: TargetAddress, Address,
1030	Size)) {
1031	std::string Msg;
1032	raw_string_ostream SS(Msg);
1033	SS << "BOLT-ERROR: PC-relative operand can't be evaluated:\n";
1034	BC.InstPrinter->printInst(MI: &Instruction, Address: 0, Annot: "", STI: *BC.STI, OS&: SS);
1035	SS << '\n';
1036	Instruction.dump_pretty(OS&: SS, Printer: BC.InstPrinter.get());
1037	SS << '\n';
1038	SS << "BOLT-ERROR: cannot handle PC-relative operand at 0x"
1039	<< Twine::utohexstr(Val: Address) << ". Skipping function " << *this << ".\n";
1040	if (BC.HasRelocations)
1041	return createFatalBOLTError(S: Msg);
1042	IsSimple = false;
1043	return createNonFatalBOLTError(S: Msg);
1044	}
1045	if (TargetAddress == 0 && opts::Verbosity >= 1) {
1046	BC.outs() << "BOLT-INFO: PC-relative operand is zero in function " << *this
1047	<< '\n';
1048	}
1049
1050	const MCSymbol *TargetSymbol;
1051	uint64_t TargetOffset;
1052	std::tie(args&: TargetSymbol, args&: TargetOffset) =
1053	BC.handleAddressRef(Address: TargetAddress, BF&: *this, /*IsPCRel*/ true);
1054
1055	bool ReplaceSuccess = MIB->replaceMemOperandDisp(
1056	Inst&: Instruction, Label: TargetSymbol, Addend: static_cast<int64_t>(TargetOffset), Ctx: &*BC.Ctx);
1057	(void)ReplaceSuccess;
1058	assert(ReplaceSuccess && "Failed to replace mem operand with symbol+off.");
1059	return Error::success();
1060	}
1061
1062	MCSymbol *BinaryFunction::handleExternalReference(MCInst &Instruction,
1063	uint64_t Size,
1064	uint64_t Offset,
1065	uint64_t TargetAddress,
1066	bool &IsCall) {
1067	auto &MIB = BC.MIB;
1068
1069	const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1070	BC.addInterproceduralReference(Function: this, Address: TargetAddress);
1071	if (opts::Verbosity >= 2 && !IsCall && Size == 2 && !BC.HasRelocations) {
1072	BC.errs() << "BOLT-WARNING: relaxed tail call detected at 0x"
1073	<< Twine::utohexstr(Val: AbsoluteInstrAddr) << " in function " << *this
1074	<< ". Code size will be increased.\n";
1075	}
1076
1077	assert(!MIB->isTailCall(Instruction) &&
1078	"synthetic tail call instruction found");
1079
1080	// This is a call regardless of the opcode.
1081	// Assign proper opcode for tail calls, so that they could be
1082	// treated as calls.
1083	if (!IsCall) {
1084	if (!MIB->convertJmpToTailCall(Inst&: Instruction)) {
1085	assert(MIB->isConditionalBranch(Instruction) &&
1086	"unknown tail call instruction");
1087	if (opts::Verbosity >= 2) {
1088	BC.errs() << "BOLT-WARNING: conditional tail call detected in "
1089	<< "function " << *this << " at 0x"
1090	<< Twine::utohexstr(Val: AbsoluteInstrAddr) << ".\n";
1091	}
1092	}
1093	IsCall = true;
1094	}
1095
1096	if (opts::Verbosity >= 2 && TargetAddress == 0) {
1097	// We actually see calls to address 0 in presence of weak
1098	// symbols originating from libraries. This code is never meant
1099	// to be executed.
1100	BC.outs() << "BOLT-INFO: Function " << *this
1101	<< " has a call to address zero.\n";
1102	}
1103
1104	return BC.getOrCreateGlobalSymbol(Address: TargetAddress, Prefix: "FUNCat");
1105	}
1106
1107	void BinaryFunction::handleIndirectBranch(MCInst &Instruction, uint64_t Size,
1108	uint64_t Offset) {
1109	auto &MIB = BC.MIB;
1110	uint64_t IndirectTarget = 0;
1111	IndirectBranchType Result =
1112	processIndirectBranch(Instruction, Size, Offset, TargetAddress&: IndirectTarget);
1113	switch (Result) {
1114	default:
1115	llvm_unreachable("unexpected result");
1116	case IndirectBranchType::POSSIBLE_TAIL_CALL: {
1117	bool Result = MIB->convertJmpToTailCall(Inst&: Instruction);
1118	(void)Result;
1119	assert(Result);
1120	break;
1121	}
1122	case IndirectBranchType::POSSIBLE_JUMP_TABLE:
1123	case IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE:
1124	if (opts::JumpTables == JTS_NONE)
1125	IsSimple = false;
1126	break;
1127	case IndirectBranchType::POSSIBLE_FIXED_BRANCH: {
1128	if (containsAddress(PC: IndirectTarget)) {
1129	const MCSymbol *TargetSymbol = getOrCreateLocalLabel(Address: IndirectTarget);
1130	Instruction.clear();
1131	MIB->createUncondBranch(Inst&: Instruction, TBB: TargetSymbol, Ctx: BC.Ctx.get());
1132	TakenBranches.emplace_back(Args&: Offset, Args: IndirectTarget - getAddress());
1133	addEntryPointAtOffset(Offset: IndirectTarget - getAddress());
1134	} else {
1135	MIB->convertJmpToTailCall(Inst&: Instruction);
1136	BC.addInterproceduralReference(Function: this, Address: IndirectTarget);
1137	}
1138	break;
1139	}
1140	case IndirectBranchType::UNKNOWN:
1141	// Keep processing. We'll do more checks and fixes in
1142	// postProcessIndirectBranches().
1143	UnknownIndirectBranchOffsets.emplace(args&: Offset);
1144	break;
1145	}
1146	}
1147
1148	void BinaryFunction::handleAArch64IndirectCall(MCInst &Instruction,
1149	const uint64_t Offset) {
1150	auto &MIB = BC.MIB;
1151	const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1152	MCInst *TargetHiBits, *TargetLowBits;
1153	uint64_t TargetAddress, Count;
1154	Count = MIB->matchLinkerVeneer(Begin: Instructions.begin(), End: Instructions.end(),
1155	Address: AbsoluteInstrAddr, CurInst: Instruction, TargetHiBits,
1156	TargetLowBits, Target&: TargetAddress);
1157	if (Count) {
1158	MIB->addAnnotation(Inst&: Instruction, Name: "AArch64Veneer", Val: true);
1159	--Count;
1160	for (auto It = std::prev(x: Instructions.end()); Count != 0;
1161	It = std::prev(x: It), --Count) {
1162	MIB->addAnnotation(Inst&: It->second, Name: "AArch64Veneer", Val: true);
1163	}
1164
1165	BC.addAdrpAddRelocAArch64(BF&: *this, LoadLowBits&: *TargetLowBits, LoadHiBits&: *TargetHiBits,
1166	Target: TargetAddress);
1167	}
1168	}
1169
1170	Error BinaryFunction::disassemble() {
1171	NamedRegionTimer T("disassemble", "Disassemble function", "buildfuncs",
1172	"Build Binary Functions", opts::TimeBuild);
1173	ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData();
1174	assert(ErrorOrFunctionData && "function data is not available");
1175	ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData;
1176	assert(FunctionData.size() == getMaxSize() &&
1177	"function size does not match raw data size");
1178
1179	auto &Ctx = BC.Ctx;
1180	auto &MIB = BC.MIB;
1181
1182	BC.SymbolicDisAsm->setSymbolizer(MIB->createTargetSymbolizer(Function&: *this));
1183
1184	// Insert a label at the beginning of the function. This will be our first
1185	// basic block.
1186	Labels[0] = Ctx->createNamedTempSymbol(Name: "BB0");
1187
1188	// Map offsets in the function to a label that should always point to the
1189	// corresponding instruction. This is used for labels that shouldn't point to
1190	// the start of a basic block but always to a specific instruction. This is
1191	// used, for example, on RISC-V where %pcrel_lo relocations point to the
1192	// corresponding %pcrel_hi.
1193	LabelsMapType InstructionLabels;
1194
1195	uint64_t Size = 0; // instruction size
1196	for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
1197	MCInst Instruction;
1198	const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1199
1200	// Check for data inside code and ignore it
1201	if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) {
1202	Size = DataInCodeSize;
1203	continue;
1204	}
1205
1206	if (!BC.SymbolicDisAsm->getInstruction(Instr&: Instruction, Size,
1207	Bytes: FunctionData.slice(N: Offset),
1208	Address: AbsoluteInstrAddr, CStream&: nulls())) {
1209	// Functions with "soft" boundaries, e.g. coming from assembly source,
1210	// can have 0-byte padding at the end.
1211	if (isZeroPaddingAt(Offset))
1212	break;
1213
1214	BC.errs()
1215	<< "BOLT-WARNING: unable to disassemble instruction at offset 0x"
1216	<< Twine::utohexstr(Val: Offset) << " (address 0x"
1217	<< Twine::utohexstr(Val: AbsoluteInstrAddr) << ") in function " << *this
1218	<< '\n';
1219	// Some AVX-512 instructions could not be disassembled at all.
1220	if (BC.HasRelocations && opts::TrapOnAVX512 && BC.isX86()) {
1221	setTrapOnEntry();
1222	BC.TrappedFunctions.push_back(x: this);
1223	} else {
1224	setIgnored();
1225	}
1226
1227	break;
1228	}
1229
1230	// Check integrity of LLVM assembler/disassembler.
1231	if (opts::CheckEncoding && !BC.MIB->isBranch(Inst: Instruction) &&
1232	!BC.MIB->isCall(Inst: Instruction) && !BC.MIB->isNoop(Inst: Instruction)) {
1233	if (!BC.validateInstructionEncoding(Sequence: FunctionData.slice(N: Offset, M: Size))) {
1234	BC.errs() << "BOLT-WARNING: mismatching LLVM encoding detected in "
1235	<< "function " << *this << " for instruction :\n";
1236	BC.printInstruction(OS&: BC.errs(), Instruction, Offset: AbsoluteInstrAddr);
1237	BC.errs() << '\n';
1238	}
1239	}
1240
1241	// Special handling for AVX-512 instructions.
1242	if (MIB->hasEVEXEncoding(Inst: Instruction)) {
1243	if (BC.HasRelocations && opts::TrapOnAVX512) {
1244	setTrapOnEntry();
1245	BC.TrappedFunctions.push_back(x: this);
1246	break;
1247	}
1248
1249	if (!BC.validateInstructionEncoding(Sequence: FunctionData.slice(N: Offset, M: Size))) {
1250	BC.errs() << "BOLT-WARNING: internal assembler/disassembler error "
1251	"detected for AVX512 instruction:\n";
1252	BC.printInstruction(OS&: BC.errs(), Instruction, Offset: AbsoluteInstrAddr);
1253	BC.errs() << " in function " << *this << '\n';
1254	setIgnored();
1255	break;
1256	}
1257	}
1258
1259	if (MIB->isBranch(Inst: Instruction) || MIB->isCall(Inst: Instruction)) {
1260	uint64_t TargetAddress = 0;
1261	if (MIB->evaluateBranch(Inst: Instruction, Addr: AbsoluteInstrAddr, Size,
1262	Target&: TargetAddress)) {
1263	// Check if the target is within the same function. Otherwise it's
1264	// a call, possibly a tail call.
1265	//
1266	// If the target *is* the function address it could be either a branch
1267	// or a recursive call.
1268	bool IsCall = MIB->isCall(Inst: Instruction);
1269	const bool IsCondBranch = MIB->isConditionalBranch(Inst: Instruction);
1270	MCSymbol *TargetSymbol = nullptr;
1271
1272	if (BC.MIB->isUnsupportedBranch(Inst: Instruction)) {
1273	setIgnored();
1274	if (BinaryFunction *TargetFunc =
1275	BC.getBinaryFunctionContainingAddress(Address: TargetAddress))
1276	TargetFunc->setIgnored();
1277	}
1278
1279	if (IsCall && containsAddress(PC: TargetAddress)) {
1280	if (TargetAddress == getAddress()) {
1281	// Recursive call.
1282	TargetSymbol = getSymbol();
1283	} else {
1284	if (BC.isX86()) {
1285	// Dangerous old-style x86 PIC code. We may need to freeze this
1286	// function, so preserve the function as is for now.
1287	PreserveNops = true;
1288	} else {
1289	BC.errs() << "BOLT-WARNING: internal call detected at 0x"
1290	<< Twine::utohexstr(Val: AbsoluteInstrAddr)
1291	<< " in function " << *this << ". Skipping.\n";
1292	IsSimple = false;
1293	}
1294	}
1295	}
1296
1297	if (!TargetSymbol) {
1298	// Create either local label or external symbol.
1299	if (containsAddress(PC: TargetAddress)) {
1300	TargetSymbol = getOrCreateLocalLabel(Address: TargetAddress);
1301	} else {
1302	if (TargetAddress == getAddress() + getSize() &&
1303	TargetAddress < getAddress() + getMaxSize() &&
1304	!(BC.isAArch64() &&
1305	BC.handleAArch64Veneer(Address: TargetAddress, /*MatchOnly*/ true))) {
1306	// Result of __builtin_unreachable().
1307	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: jump past end detected at 0x"
1308	<< Twine::utohexstr(AbsoluteInstrAddr)
1309	<< " in function " << *this
1310	<< " : replacing with nop.\n");
1311	BC.MIB->createNoop(Inst&: Instruction);
1312	if (IsCondBranch) {
1313	// Register branch offset for profile validation.
1314	IgnoredBranches.emplace_back(Args&: Offset, Args: Offset + Size);
1315	}
1316	goto add_instruction;
1317	}
1318	// May update Instruction and IsCall
1319	TargetSymbol = handleExternalReference(Instruction, Size, Offset,
1320	TargetAddress, IsCall);
1321	}
1322	}
1323
1324	if (!IsCall) {
1325	// Add taken branch info.
1326	TakenBranches.emplace_back(Args&: Offset, Args: TargetAddress - getAddress());
1327	}
1328	BC.MIB->replaceBranchTarget(Inst&: Instruction, TBB: TargetSymbol, Ctx: &*Ctx);
1329
1330	// Mark CTC.
1331	if (IsCondBranch && IsCall)
1332	MIB->setConditionalTailCall(Inst&: Instruction, Dest: TargetAddress);
1333	} else {
1334	// Could not evaluate branch. Should be an indirect call or an
1335	// indirect branch. Bail out on the latter case.
1336	if (MIB->isIndirectBranch(Inst: Instruction))
1337	handleIndirectBranch(Instruction, Size, Offset);
1338	// Indirect call. We only need to fix it if the operand is RIP-relative.
1339	if (IsSimple && MIB->hasPCRelOperand(Inst: Instruction)) {
1340	if (auto NewE = handleErrors(
1341	E: handlePCRelOperand(Instruction, Address: AbsoluteInstrAddr, Size),
1342	Hs: [&](const BOLTError &E) -> Error {
1343	if (E.isFatal())
1344	return Error(std::make_unique<BOLTError>(args: std::move(E)));
1345	if (!E.getMessage().empty())
1346	E.log(OS&: BC.errs());
1347	return Error::success();
1348	})) {
1349	return Error(std::move(NewE));
1350	}
1351	}
1352
1353	if (BC.isAArch64())
1354	handleAArch64IndirectCall(Instruction, Offset);
1355	}
1356	} else if (BC.isAArch64() || BC.isRISCV()) {
1357	// Check if there's a relocation associated with this instruction.
1358	bool UsedReloc = false;
1359	for (auto Itr = Relocations.lower_bound(x: Offset),
1360	ItrE = Relocations.lower_bound(x: Offset + Size);
1361	Itr != ItrE; ++Itr) {
1362	const Relocation &Relocation = Itr->second;
1363	MCSymbol *Symbol = Relocation.Symbol;
1364
1365	if (Relocation::isInstructionReference(Type: Relocation.Type)) {
1366	uint64_t RefOffset = Relocation.Value - getAddress();
1367	LabelsMapType::iterator LI = InstructionLabels.find(x: RefOffset);
1368
1369	if (LI == InstructionLabels.end()) {
1370	Symbol = BC.Ctx->createNamedTempSymbol();
1371	InstructionLabels.emplace(args&: RefOffset, args&: Symbol);
1372	} else {
1373	Symbol = LI->second;
1374	}
1375	}
1376
1377	int64_t Value = Relocation.Value;
1378	const bool Result = BC.MIB->replaceImmWithSymbolRef(
1379	Inst&: Instruction, Symbol, Addend: Relocation.Addend, Ctx: Ctx.get(), Value,
1380	RelType: Relocation.Type);
1381	(void)Result;
1382	assert(Result && "cannot replace immediate with relocation");
1383
1384	// For aarch64, if we replaced an immediate with a symbol from a
1385	// relocation, we mark it so we do not try to further process a
1386	// pc-relative operand. All we need is the symbol.
1387	UsedReloc = true;
1388	}
1389
1390	if (!BC.isRISCV() && MIB->hasPCRelOperand(Inst: Instruction) && !UsedReloc) {
1391	if (auto NewE = handleErrors(
1392	E: handlePCRelOperand(Instruction, Address: AbsoluteInstrAddr, Size),
1393	Hs: [&](const BOLTError &E) -> Error {
1394	if (E.isFatal())
1395	return Error(std::make_unique<BOLTError>(args: std::move(E)));
1396	if (!E.getMessage().empty())
1397	E.log(OS&: BC.errs());
1398	return Error::success();
1399	}))
1400	return Error(std::move(NewE));
1401	}
1402	}
1403
1404	add_instruction:
1405	if (getDWARFLineTable()) {
1406	Instruction.setLoc(findDebugLineInformationForInstructionAt(
1407	Address: AbsoluteInstrAddr, Unit: getDWARFUnit(), LineTable: getDWARFLineTable()));
1408	}
1409
1410	// Record offset of the instruction for profile matching.
1411	if (BC.keepOffsetForInstruction(Inst: Instruction))
1412	MIB->setOffset(Inst&: Instruction, Offset: static_cast<uint32_t>(Offset));
1413
1414	if (BC.isX86() && BC.MIB->isNoop(Inst: Instruction)) {
1415	// NOTE: disassembly loses the correct size information for noops on x86.
1416	// E.g. nopw 0x0(%rax,%rax,1) is 9 bytes, but re-encoded it's only
1417	// 5 bytes. Preserve the size info using annotations.
1418	MIB->setSize(Inst&: Instruction, Size);
1419	}
1420
1421	addInstruction(Offset, Instruction: std::move(Instruction));
1422	}
1423
1424	for (auto [Offset, Label] : InstructionLabels) {
1425	InstrMapType::iterator II = Instructions.find(x: Offset);
1426	assert(II != Instructions.end() && "reference to non-existing instruction");
1427
1428	BC.MIB->setInstLabel(Inst&: II->second, Label);
1429	}
1430
1431	// Reset symbolizer for the disassembler.
1432	BC.SymbolicDisAsm->setSymbolizer(nullptr);
1433
1434	if (uint64_t Offset = getFirstInstructionOffset())
1435	Labels[Offset] = BC.Ctx->createNamedTempSymbol();
1436
1437	clearList(List&: Relocations);
1438
1439	if (!IsSimple) {
1440	clearList(List&: Instructions);
1441	return createNonFatalBOLTError(S: "");
1442	}
1443
1444	updateState(State: State::Disassembled);
1445
1446	return Error::success();
1447	}
1448
1449	MCSymbol *BinaryFunction::registerBranch(uint64_t Src, uint64_t Dst) {
1450	assert(CurrentState == State::Disassembled &&
1451	"Cannot register branch unless function is in disassembled state.");
1452	assert(containsAddress(Src) && containsAddress(Dst) &&
1453	"Cannot register external branch.");
1454	MCSymbol *Target = getOrCreateLocalLabel(Address: Dst);
1455	TakenBranches.emplace_back(Args: Src - getAddress(), Args: Dst - getAddress());
1456	return Target;
1457	}
1458
1459	bool BinaryFunction::scanExternalRefs() {
1460	bool Success = true;
1461	bool DisassemblyFailed = false;
1462
1463	// Ignore pseudo functions.
1464	if (isPseudo())
1465	return Success;
1466
1467	if (opts::NoScan) {
1468	clearList(List&: Relocations);
1469	clearList(List&: ExternallyReferencedOffsets);
1470
1471	return false;
1472	}
1473
1474	// List of external references for this function.
1475	std::vector<Relocation> FunctionRelocations;
1476
1477	static BinaryContext::IndependentCodeEmitter Emitter =
1478	BC.createIndependentMCCodeEmitter();
1479
1480	ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData();
1481	assert(ErrorOrFunctionData && "function data is not available");
1482	ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData;
1483	assert(FunctionData.size() == getMaxSize() &&
1484	"function size does not match raw data size");
1485
1486	BC.SymbolicDisAsm->setSymbolizer(
1487	BC.MIB->createTargetSymbolizer(Function&: *this, /*CreateSymbols*/ CreateNewSymbols: false));
1488
1489	// Disassemble contents of the function. Detect code entry points and create
1490	// relocations for references to code that will be moved.
1491	uint64_t Size = 0; // instruction size
1492	for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
1493	// Check for data inside code and ignore it
1494	if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) {
1495	Size = DataInCodeSize;
1496	continue;
1497	}
1498
1499	const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1500	MCInst Instruction;
1501	if (!BC.SymbolicDisAsm->getInstruction(Instr&: Instruction, Size,
1502	Bytes: FunctionData.slice(N: Offset),
1503	Address: AbsoluteInstrAddr, CStream&: nulls())) {
1504	if (opts::Verbosity >= 1 && !isZeroPaddingAt(Offset)) {
1505	BC.errs()
1506	<< "BOLT-WARNING: unable to disassemble instruction at offset 0x"
1507	<< Twine::utohexstr(Val: Offset) << " (address 0x"
1508	<< Twine::utohexstr(Val: AbsoluteInstrAddr) << ") in function " << *this
1509	<< '\n';
1510	}
1511	Success = false;
1512	DisassemblyFailed = true;
1513	break;
1514	}
1515
1516	// Return true if we can skip handling the Target function reference.
1517	auto ignoreFunctionRef = [&](const BinaryFunction &Target) {
1518	if (&Target == this)
1519	return true;
1520
1521	// Note that later we may decide not to emit Target function. In that
1522	// case, we conservatively create references that will be ignored or
1523	// resolved to the same function.
1524	if (!BC.shouldEmit(Function: Target))
1525	return true;
1526
1527	return false;
1528	};
1529
1530	// Return true if we can ignore reference to the symbol.
1531	auto ignoreReference = [&](const MCSymbol *TargetSymbol) {
1532	if (!TargetSymbol)
1533	return true;
1534
1535	if (BC.forceSymbolRelocations(SymbolName: TargetSymbol->getName()))
1536	return false;
1537
1538	BinaryFunction *TargetFunction = BC.getFunctionForSymbol(Symbol: TargetSymbol);
1539	if (!TargetFunction)
1540	return true;
1541
1542	return ignoreFunctionRef(*TargetFunction);
1543	};
1544
1545	// Handle calls and branches separately as symbolization doesn't work for
1546	// them yet.
1547	MCSymbol *BranchTargetSymbol = nullptr;
1548	if (BC.MIB->isCall(Inst: Instruction) || BC.MIB->isBranch(Inst: Instruction)) {
1549	uint64_t TargetAddress = 0;
1550	BC.MIB->evaluateBranch(Inst: Instruction, Addr: AbsoluteInstrAddr, Size,
1551	Target&: TargetAddress);
1552
1553	// Create an entry point at reference address if needed.
1554	BinaryFunction *TargetFunction =
1555	BC.getBinaryFunctionContainingAddress(Address: TargetAddress);
1556
1557	if (!TargetFunction || ignoreFunctionRef(*TargetFunction))
1558	continue;
1559
1560	const uint64_t FunctionOffset =
1561	TargetAddress - TargetFunction->getAddress();
1562	BranchTargetSymbol =
1563	FunctionOffset ? TargetFunction->addEntryPointAtOffset(Offset: FunctionOffset)
1564	: TargetFunction->getSymbol();
1565	}
1566
1567	// Can't find more references. Not creating relocations since we are not
1568	// moving code.
1569	if (!BC.HasRelocations)
1570	continue;
1571
1572	if (BranchTargetSymbol) {
1573	BC.MIB->replaceBranchTarget(Inst&: Instruction, TBB: BranchTargetSymbol,
1574	Ctx: Emitter.LocalCtx.get());
1575	} else if (!llvm::any_of(Range&: Instruction,
1576	P: [](const MCOperand &Op) { return Op.isExpr(); })) {
1577	// Skip assembly if the instruction may not have any symbolic operands.
1578	continue;
1579	}
1580
1581	// Emit the instruction using temp emitter and generate relocations.
1582	SmallString<256> Code;
1583	SmallVector<MCFixup, 4> Fixups;
1584	Emitter.MCE->encodeInstruction(Inst: Instruction, CB&: Code, Fixups, STI: *BC.STI);
1585
1586	// Create relocation for every fixup.
1587	for (const MCFixup &Fixup : Fixups) {
1588	std::optional<Relocation> Rel = BC.MIB->createRelocation(Fixup, MAB: *BC.MAB);
1589	if (!Rel) {
1590	Success = false;
1591	continue;
1592	}
1593
1594	if (ignoreReference(Rel->Symbol))
1595	continue;
1596
1597	if (Relocation::getSizeForType(Type: Rel->Type) < 4) {
1598	// If the instruction uses a short form, then we might not be able
1599	// to handle the rewrite without relaxation, and hence cannot reliably
1600	// create an external reference relocation.
1601	Success = false;
1602	continue;
1603	}
1604	Rel->Offset += getAddress() - getOriginSection()->getAddress() + Offset;
1605	FunctionRelocations.push_back(x: *Rel);
1606	}
1607
1608	if (!Success)
1609	break;
1610	}
1611
1612	// Reset symbolizer for the disassembler.
1613	BC.SymbolicDisAsm->setSymbolizer(nullptr);
1614
1615	// Add relocations unless disassembly failed for this function.
1616	if (!DisassemblyFailed)
1617	for (Relocation &Rel : FunctionRelocations)
1618	getOriginSection()->addPendingRelocation(Rel);
1619
1620	// Inform BinaryContext that this function symbols will not be defined and
1621	// relocations should not be created against them.
1622	if (BC.HasRelocations) {
1623	for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
1624	BC.UndefinedSymbols.insert(x: LI.second);
1625	for (MCSymbol *const EndLabel : FunctionEndLabels)
1626	if (EndLabel)
1627	BC.UndefinedSymbols.insert(x: EndLabel);
1628	}
1629
1630	clearList(List&: Relocations);
1631	clearList(List&: ExternallyReferencedOffsets);
1632
1633	if (Success && BC.HasRelocations)
1634	HasExternalRefRelocations = true;
1635
1636	if (opts::Verbosity >= 1 && !Success)
1637	BC.outs() << "BOLT-INFO: failed to scan refs for " << *this << '\n';
1638
1639	return Success;
1640	}
1641
1642	void BinaryFunction::postProcessEntryPoints() {
1643	if (!isSimple())
1644	return;
1645
1646	for (auto &KV : Labels) {
1647	MCSymbol *Label = KV.second;
1648	if (!getSecondaryEntryPointSymbol(BBLabel: Label))
1649	continue;
1650
1651	// In non-relocation mode there's potentially an external undetectable
1652	// reference to the entry point and hence we cannot move this entry
1653	// point. Optimizing without moving could be difficult.
1654	if (!BC.HasRelocations)
1655	setSimple(false);
1656
1657	const uint32_t Offset = KV.first;
1658
1659	// If we are at Offset 0 and there is no instruction associated with it,
1660	// this means this is an empty function. Just ignore. If we find an
1661	// instruction at this offset, this entry point is valid.
1662	if (!Offset || getInstructionAtOffset(Offset))
1663	continue;
1664
1665	// On AArch64 there are legitimate reasons to have references past the
1666	// end of the function, e.g. jump tables.
1667	if (BC.isAArch64() && Offset == getSize())
1668	continue;
1669
1670	BC.errs() << "BOLT-WARNING: reference in the middle of instruction "
1671	"detected in function "
1672	<< *this << " at offset 0x" << Twine::utohexstr(Val: Offset) << '\n';
1673	if (BC.HasRelocations)
1674	setIgnored();
1675	setSimple(false);
1676	return;
1677	}
1678	}
1679
1680	void BinaryFunction::postProcessJumpTables() {
1681	// Create labels for all entries.
1682	for (auto &JTI : JumpTables) {
1683	JumpTable &JT = *JTI.second;
1684	if (JT.Type == JumpTable::JTT_PIC && opts::JumpTables == JTS_BASIC) {
1685	opts::JumpTables = JTS_MOVE;
1686	BC.outs() << "BOLT-INFO: forcing -jump-tables=move as PIC jump table was "
1687	"detected in function "
1688	<< *this << '\n';
1689	}
1690	const uint64_t BDSize =
1691	BC.getBinaryDataAtAddress(Address: JT.getAddress())->getSize();
1692	if (!BDSize) {
1693	BC.setBinaryDataSize(Address: JT.getAddress(), Size: JT.getSize());
1694	} else {
1695	assert(BDSize >= JT.getSize() &&
1696	"jump table cannot be larger than the containing object");
1697	}
1698	if (!JT.Entries.empty())
1699	continue;
1700
1701	bool HasOneParent = (JT.Parents.size() == 1);
1702	for (uint64_t EntryAddress : JT.EntriesAsAddress) {
1703	// builtin_unreachable does not belong to any function
1704	// Need to handle separately
1705	bool IsBuiltinUnreachable =
1706	llvm::any_of(Range&: JT.Parents, P: [&](const BinaryFunction *Parent) {
1707	return EntryAddress == Parent->getAddress() + Parent->getSize();
1708	});
1709	if (IsBuiltinUnreachable) {
1710	MCSymbol *Label = getOrCreateLocalLabel(Address: EntryAddress, CreatePastEnd: true);
1711	JT.Entries.push_back(x: Label);
1712	continue;
1713	}
1714	// Create a local label for targets that cannot be reached by other
1715	// fragments. Otherwise, create a secondary entry point in the target
1716	// function.
1717	BinaryFunction *TargetBF =
1718	BC.getBinaryFunctionContainingAddress(Address: EntryAddress);
1719	MCSymbol *Label;
1720	if (HasOneParent && TargetBF == this) {
1721	Label = getOrCreateLocalLabel(Address: EntryAddress, CreatePastEnd: true);
1722	} else {
1723	const uint64_t Offset = EntryAddress - TargetBF->getAddress();
1724	Label = Offset ? TargetBF->addEntryPointAtOffset(Offset)
1725	: TargetBF->getSymbol();
1726	}
1727	JT.Entries.push_back(x: Label);
1728	}
1729	}
1730
1731	// Add TakenBranches from JumpTables.
1732	//
1733	// We want to do it after initial processing since we don't know jump tables'
1734	// boundaries until we process them all.
1735	for (auto &JTSite : JTSites) {
1736	const uint64_t JTSiteOffset = JTSite.first;
1737	const uint64_t JTAddress = JTSite.second;
1738	const JumpTable *JT = getJumpTableContainingAddress(Address: JTAddress);
1739	assert(JT && "cannot find jump table for address");
1740
1741	uint64_t EntryOffset = JTAddress - JT->getAddress();
1742	while (EntryOffset < JT->getSize()) {
1743	uint64_t EntryAddress = JT->EntriesAsAddress[EntryOffset / JT->EntrySize];
1744	uint64_t TargetOffset = EntryAddress - getAddress();
1745	if (TargetOffset < getSize()) {
1746	TakenBranches.emplace_back(Args: JTSiteOffset, Args&: TargetOffset);
1747
1748	if (opts::StrictMode)
1749	registerReferencedOffset(Offset: TargetOffset);
1750	}
1751
1752	EntryOffset += JT->EntrySize;
1753
1754	// A label at the next entry means the end of this jump table.
1755	if (JT->Labels.count(x: EntryOffset))
1756	break;
1757	}
1758	}
1759	clearList(List&: JTSites);
1760
1761	// Conservatively populate all possible destinations for unknown indirect
1762	// branches.
1763	if (opts::StrictMode && hasInternalReference()) {
1764	for (uint64_t Offset : UnknownIndirectBranchOffsets) {
1765	for (uint64_t PossibleDestination : ExternallyReferencedOffsets) {
1766	// Ignore __builtin_unreachable().
1767	if (PossibleDestination == getSize())
1768	continue;
1769	TakenBranches.emplace_back(Args&: Offset, Args&: PossibleDestination);
1770	}
1771	}
1772	}
1773	}
1774
1775	bool BinaryFunction::validateExternallyReferencedOffsets() {
1776	SmallPtrSet<MCSymbol *, 4> JTTargets;
1777	for (const JumpTable *JT : llvm::make_second_range(c&: JumpTables))
1778	JTTargets.insert(I: JT->Entries.begin(), E: JT->Entries.end());
1779
1780	bool HasUnclaimedReference = false;
1781	for (uint64_t Destination : ExternallyReferencedOffsets) {
1782	// Ignore __builtin_unreachable().
1783	if (Destination == getSize())
1784	continue;
1785	// Ignore constant islands
1786	if (isInConstantIsland(Address: Destination + getAddress()))
1787	continue;
1788
1789	if (BinaryBasicBlock *BB = getBasicBlockAtOffset(Offset: Destination)) {
1790	// Check if the externally referenced offset is a recognized jump table
1791	// target.
1792	if (JTTargets.contains(Ptr: BB->getLabel()))
1793	continue;
1794
1795	if (opts::Verbosity >= 1) {
1796	BC.errs() << "BOLT-WARNING: unclaimed data to code reference (possibly "
1797	<< "an unrecognized jump table entry) to " << BB->getName()
1798	<< " in " << *this << "\n";
1799	}
1800	auto L = BC.scopeLock();
1801	addEntryPoint(BB: *BB);
1802	} else {
1803	BC.errs() << "BOLT-WARNING: unknown data to code reference to offset "
1804	<< Twine::utohexstr(Val: Destination) << " in " << *this << "\n";
1805	setIgnored();
1806	}
1807	HasUnclaimedReference = true;
1808	}
1809	return !HasUnclaimedReference;
1810	}
1811
1812	bool BinaryFunction::postProcessIndirectBranches(
1813	MCPlusBuilder::AllocatorIdTy AllocId) {
1814	auto addUnknownControlFlow = [&](BinaryBasicBlock &BB) {
1815	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: adding unknown control flow in " << *this
1816	<< " for " << BB.getName() << "\n");
1817	HasUnknownControlFlow = true;
1818	BB.removeAllSuccessors();
1819	for (uint64_t PossibleDestination : ExternallyReferencedOffsets)
1820	if (BinaryBasicBlock *SuccBB = getBasicBlockAtOffset(Offset: PossibleDestination))
1821	BB.addSuccessor(Succ: SuccBB);
1822	};
1823
1824	uint64_t NumIndirectJumps = 0;
1825	MCInst *LastIndirectJump = nullptr;
1826	BinaryBasicBlock *LastIndirectJumpBB = nullptr;
1827	uint64_t LastJT = 0;
1828	uint16_t LastJTIndexReg = BC.MIB->getNoRegister();
1829	for (BinaryBasicBlock &BB : blocks()) {
1830	for (BinaryBasicBlock::iterator II = BB.begin(); II != BB.end(); ++II) {
1831	MCInst &Instr = *II;
1832	if (!BC.MIB->isIndirectBranch(Inst: Instr))
1833	continue;
1834
1835	// If there's an indirect branch in a single-block function -
1836	// it must be a tail call.
1837	if (BasicBlocks.size() == 1) {
1838	BC.MIB->convertJmpToTailCall(Inst&: Instr);
1839	return true;
1840	}
1841
1842	++NumIndirectJumps;
1843
1844	if (opts::StrictMode && !hasInternalReference()) {
1845	BC.MIB->convertJmpToTailCall(Inst&: Instr);
1846	break;
1847	}
1848
1849	// Validate the tail call or jump table assumptions now that we know
1850	// basic block boundaries.
1851	if (BC.MIB->isTailCall(Inst: Instr) || BC.MIB->getJumpTable(Inst: Instr)) {
1852	const unsigned PtrSize = BC.AsmInfo->getCodePointerSize();
1853	MCInst *MemLocInstr;
1854	unsigned BaseRegNum, IndexRegNum;
1855	int64_t DispValue;
1856	const MCExpr *DispExpr;
1857	MCInst *PCRelBaseInstr;
1858	IndirectBranchType Type = BC.MIB->analyzeIndirectBranch(
1859	Instruction&: Instr, Begin: BB.begin(), End: II, PtrSize, MemLocInstr, BaseRegNum,
1860	IndexRegNum, DispValue, DispExpr, PCRelBaseOut&: PCRelBaseInstr);
1861	if (Type != IndirectBranchType::UNKNOWN || MemLocInstr != nullptr)
1862	continue;
1863
1864	if (!opts::StrictMode)
1865	return false;
1866
1867	if (BC.MIB->isTailCall(Inst: Instr)) {
1868	BC.MIB->convertTailCallToJmp(Inst&: Instr);
1869	} else {
1870	LastIndirectJump = &Instr;
1871	LastIndirectJumpBB = &BB;
1872	LastJT = BC.MIB->getJumpTable(Inst: Instr);
1873	LastJTIndexReg = BC.MIB->getJumpTableIndexReg(Inst: Instr);
1874	BC.MIB->unsetJumpTable(Inst&: Instr);
1875
1876	JumpTable *JT = BC.getJumpTableContainingAddress(Address: LastJT);
1877	if (JT->Type == JumpTable::JTT_NORMAL) {
1878	// Invalidating the jump table may also invalidate other jump table
1879	// boundaries. Until we have/need a support for this, mark the
1880	// function as non-simple.
1881	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: rejected jump table reference"
1882	<< JT->getName() << " in " << *this << '\n');
1883	return false;
1884	}
1885	}
1886
1887	addUnknownControlFlow(BB);
1888	continue;
1889	}
1890
1891	// If this block contains an epilogue code and has an indirect branch,
1892	// then most likely it's a tail call. Otherwise, we cannot tell for sure
1893	// what it is and conservatively reject the function's CFG.
1894	bool IsEpilogue = llvm::any_of(Range&: BB, P: [&](const MCInst &Instr) {
1895	return BC.MIB->isLeave(Inst: Instr) || BC.MIB->isPop(Inst: Instr);
1896	});
1897	if (IsEpilogue) {
1898	BC.MIB->convertJmpToTailCall(Inst&: Instr);
1899	BB.removeAllSuccessors();
1900	continue;
1901	}
1902
1903	if (opts::Verbosity >= 2) {
1904	BC.outs() << "BOLT-INFO: rejected potential indirect tail call in "
1905	<< "function " << *this << " in basic block " << BB.getName()
1906	<< ".\n";
1907	LLVM_DEBUG(BC.printInstructions(dbgs(), BB.begin(), BB.end(),
1908	BB.getOffset(), this, true));
1909	}
1910
1911	if (!opts::StrictMode)
1912	return false;
1913
1914	addUnknownControlFlow(BB);
1915	}
1916	}
1917
1918	if (HasInternalLabelReference)
1919	return false;
1920
1921	// If there's only one jump table, and one indirect jump, and no other
1922	// references, then we should be able to derive the jump table even if we
1923	// fail to match the pattern.
1924	if (HasUnknownControlFlow && NumIndirectJumps == 1 &&
1925	JumpTables.size() == 1 && LastIndirectJump &&
1926	!BC.getJumpTableContainingAddress(Address: LastJT)->IsSplit) {
1927	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: unsetting unknown control flow in "
1928	<< *this << '\n');
1929	BC.MIB->setJumpTable(Inst&: *LastIndirectJump, Value: LastJT, IndexReg: LastJTIndexReg, AllocId);
1930	HasUnknownControlFlow = false;
1931
1932	LastIndirectJumpBB->updateJumpTableSuccessors();
1933	}
1934
1935	// Validate that all data references to function offsets are claimed by
1936	// recognized jump tables. Register externally referenced blocks as entry
1937	// points.
1938	if (!opts::StrictMode && hasInternalReference()) {
1939	if (!validateExternallyReferencedOffsets())
1940	return false;
1941	}
1942
1943	if (HasUnknownControlFlow && !BC.HasRelocations)
1944	return false;
1945
1946	return true;
1947	}
1948
1949	void BinaryFunction::recomputeLandingPads() {
1950	updateBBIndices(StartIndex: 0);
1951
1952	for (BinaryBasicBlock *BB : BasicBlocks) {
1953	BB->LandingPads.clear();
1954	BB->Throwers.clear();
1955	}
1956
1957	for (BinaryBasicBlock *BB : BasicBlocks) {
1958	std::unordered_set<const BinaryBasicBlock *> BBLandingPads;
1959	for (MCInst &Instr : *BB) {
1960	if (!BC.MIB->isInvoke(Inst: Instr))
1961	continue;
1962
1963	const std::optional<MCPlus::MCLandingPad> EHInfo =
1964	BC.MIB->getEHInfo(Inst: Instr);
1965	if (!EHInfo || !EHInfo->first)
1966	continue;
1967
1968	BinaryBasicBlock *LPBlock = getBasicBlockForLabel(Label: EHInfo->first);
1969	if (!BBLandingPads.count(x: LPBlock)) {
1970	BBLandingPads.insert(x: LPBlock);
1971	BB->LandingPads.emplace_back(Args&: LPBlock);
1972	LPBlock->Throwers.emplace_back(Args&: BB);
1973	}
1974	}
1975	}
1976	}
1977
1978	Error BinaryFunction::buildCFG(MCPlusBuilder::AllocatorIdTy AllocatorId) {
1979	auto &MIB = BC.MIB;
1980
1981	if (!isSimple()) {
1982	assert(!BC.HasRelocations &&
1983	"cannot process file with non-simple function in relocs mode");
1984	return createNonFatalBOLTError(S: "");
1985	}
1986
1987	if (CurrentState != State::Disassembled)
1988	return createNonFatalBOLTError(S: "");
1989
1990	assert(BasicBlocks.empty() && "basic block list should be empty");
1991	assert((Labels.find(getFirstInstructionOffset()) != Labels.end()) &&
1992	"first instruction should always have a label");
1993
1994	// Create basic blocks in the original layout order:
1995	//
1996	// * Every instruction with associated label marks
1997	// the beginning of a basic block.
1998	// * Conditional instruction marks the end of a basic block,
1999	// except when the following instruction is an
2000	// unconditional branch, and the unconditional branch is not
2001	// a destination of another branch. In the latter case, the
2002	// basic block will consist of a single unconditional branch
2003	// (missed "double-jump" optimization).
2004	//
2005	// Created basic blocks are sorted in layout order since they are
2006	// created in the same order as instructions, and instructions are
2007	// sorted by offsets.
2008	BinaryBasicBlock *InsertBB = nullptr;
2009	BinaryBasicBlock *PrevBB = nullptr;
2010	bool IsLastInstrNop = false;
2011	// Offset of the last non-nop instruction.
2012	uint64_t LastInstrOffset = 0;
2013
2014	auto addCFIPlaceholders = [this](uint64_t CFIOffset,
2015	BinaryBasicBlock *InsertBB) {
2016	for (auto FI = OffsetToCFI.lower_bound(x: CFIOffset),
2017	FE = OffsetToCFI.upper_bound(x: CFIOffset);
2018	FI != FE; ++FI) {
2019	addCFIPseudo(BB: InsertBB, Pos: InsertBB->end(), Offset: FI->second);
2020	}
2021	};
2022
2023	// For profiling purposes we need to save the offset of the last instruction
2024	// in the basic block.
2025	// NOTE: nops always have an Offset annotation. Annotate the last non-nop as
2026	// older profiles ignored nops.
2027	auto updateOffset = [&](uint64_t Offset) {
2028	assert(PrevBB && PrevBB != InsertBB && "invalid previous block");
2029	MCInst *LastNonNop = nullptr;
2030	for (BinaryBasicBlock::reverse_iterator RII = PrevBB->getLastNonPseudo(),
2031	E = PrevBB->rend();
2032	RII != E; ++RII) {
2033	if (!BC.MIB->isPseudo(Inst: *RII) && !BC.MIB->isNoop(Inst: *RII)) {
2034	LastNonNop = &*RII;
2035	break;
2036	}
2037	}
2038	if (LastNonNop && !MIB->getOffset(Inst: *LastNonNop))
2039	MIB->setOffset(Inst&: *LastNonNop, Offset: static_cast<uint32_t>(Offset));
2040	};
2041
2042	for (auto I = Instructions.begin(), E = Instructions.end(); I != E; ++I) {
2043	const uint32_t Offset = I->first;
2044	MCInst &Instr = I->second;
2045
2046	auto LI = Labels.find(x: Offset);
2047	if (LI != Labels.end()) {
2048	// Always create new BB at branch destination.
2049	PrevBB = InsertBB ? InsertBB : PrevBB;
2050	InsertBB = addBasicBlockAt(Offset: LI->first, Label: LI->second);
2051	if (opts::PreserveBlocksAlignment && IsLastInstrNop)
2052	InsertBB->setDerivedAlignment();
2053
2054	if (PrevBB)
2055	updateOffset(LastInstrOffset);
2056	}
2057
2058	// Mark all nops with Offset for profile tracking purposes.
2059	if (MIB->isNoop(Inst: Instr) && !MIB->getOffset(Inst: Instr)) {
2060	// If "Offset" annotation is not present, set it and mark the nop for
2061	// deletion.
2062	MIB->setOffset(Inst&: Instr, Offset: static_cast<uint32_t>(Offset));
2063	// Annotate ordinary nops, so we can safely delete them if required.
2064	MIB->addAnnotation(Inst&: Instr, Name: "NOP", Val: static_cast<uint32_t>(1), AllocatorId);
2065	}
2066
2067	if (!InsertBB) {
2068	// It must be a fallthrough or unreachable code. Create a new block unless
2069	// we see an unconditional branch following a conditional one. The latter
2070	// should not be a conditional tail call.
2071	assert(PrevBB && "no previous basic block for a fall through");
2072	MCInst *PrevInstr = PrevBB->getLastNonPseudoInstr();
2073	assert(PrevInstr && "no previous instruction for a fall through");
2074	if (MIB->isUnconditionalBranch(Inst: Instr) &&
2075	!MIB->isIndirectBranch(Inst: *PrevInstr) &&
2076	!MIB->isUnconditionalBranch(Inst: *PrevInstr) &&
2077	!MIB->getConditionalTailCall(Inst: *PrevInstr) &&
2078	!MIB->isReturn(Inst: *PrevInstr)) {
2079	// Temporarily restore inserter basic block.
2080	InsertBB = PrevBB;
2081	} else {
2082	MCSymbol *Label;
2083	{
2084	auto L = BC.scopeLock();
2085	Label = BC.Ctx->createNamedTempSymbol(Name: "FT");
2086	}
2087	InsertBB = addBasicBlockAt(Offset, Label);
2088	if (opts::PreserveBlocksAlignment && IsLastInstrNop)
2089	InsertBB->setDerivedAlignment();
2090	updateOffset(LastInstrOffset);
2091	}
2092	}
2093	if (Offset == getFirstInstructionOffset()) {
2094	// Add associated CFI pseudos in the first offset
2095	addCFIPlaceholders(Offset, InsertBB);
2096	}
2097
2098	const bool IsBlockEnd = MIB->isTerminator(Inst: Instr);
2099	IsLastInstrNop = MIB->isNoop(Inst: Instr);
2100	if (!IsLastInstrNop)
2101	LastInstrOffset = Offset;
2102	InsertBB->addInstruction(Inst: std::move(Instr));
2103
2104	// Add associated CFI instrs. We always add the CFI instruction that is
2105	// located immediately after this instruction, since the next CFI
2106	// instruction reflects the change in state caused by this instruction.
2107	auto NextInstr = std::next(x: I);
2108	uint64_t CFIOffset;
2109	if (NextInstr != E)
2110	CFIOffset = NextInstr->first;
2111	else
2112	CFIOffset = getSize();
2113
2114	// Note: this potentially invalidates instruction pointers/iterators.
2115	addCFIPlaceholders(CFIOffset, InsertBB);
2116
2117	if (IsBlockEnd) {
2118	PrevBB = InsertBB;
2119	InsertBB = nullptr;
2120	}
2121	}
2122
2123	if (BasicBlocks.empty()) {
2124	setSimple(false);
2125	return createNonFatalBOLTError(S: "");
2126	}
2127
2128	// Intermediate dump.
2129	LLVM_DEBUG(print(dbgs(), "after creating basic blocks"));
2130
2131	// TODO: handle properly calls to no-return functions,
2132	// e.g. exit(3), etc. Otherwise we'll see a false fall-through
2133	// blocks.
2134
2135	// Remove duplicates branches. We can get a bunch of them from jump tables.
2136	// Without doing jump table value profiling we don't have a use for extra
2137	// (duplicate) branches.
2138	llvm::sort(C&: TakenBranches);
2139	auto NewEnd = std::unique(first: TakenBranches.begin(), last: TakenBranches.end());
2140	TakenBranches.erase(CS: NewEnd, CE: TakenBranches.end());
2141
2142	for (std::pair<uint32_t, uint32_t> &Branch : TakenBranches) {
2143	LLVM_DEBUG(dbgs() << "registering branch [0x"
2144	<< Twine::utohexstr(Branch.first) << "] -> [0x"
2145	<< Twine::utohexstr(Branch.second) << "]\n");
2146	BinaryBasicBlock *FromBB = getBasicBlockContainingOffset(Offset: Branch.first);
2147	BinaryBasicBlock *ToBB = getBasicBlockAtOffset(Offset: Branch.second);
2148	if (!FromBB || !ToBB) {
2149	if (!FromBB)
2150	BC.errs() << "BOLT-ERROR: cannot find BB containing the branch.\n";
2151	if (!ToBB)
2152	BC.errs()
2153	<< "BOLT-ERROR: cannot find BB containing branch destination.\n";
2154	return createFatalBOLTError(S: BC.generateBugReportMessage(
2155	Message: "disassembly failed - inconsistent branch found.", Function: *this));
2156	}
2157
2158	FromBB->addSuccessor(Succ: ToBB);
2159	}
2160
2161	// Add fall-through branches.
2162	PrevBB = nullptr;
2163	bool IsPrevFT = false; // Is previous block a fall-through.
2164	for (BinaryBasicBlock *BB : BasicBlocks) {
2165	if (IsPrevFT)
2166	PrevBB->addSuccessor(Succ: BB);
2167
2168	if (BB->empty()) {
2169	IsPrevFT = true;
2170	PrevBB = BB;
2171	continue;
2172	}
2173
2174	MCInst *LastInstr = BB->getLastNonPseudoInstr();
2175	assert(LastInstr &&
2176	"should have non-pseudo instruction in non-empty block");
2177
2178	if (BB->succ_size() == 0) {
2179	// Since there's no existing successors, we know the last instruction is
2180	// not a conditional branch. Thus if it's a terminator, it shouldn't be a
2181	// fall-through.
2182	//
2183	// Conditional tail call is a special case since we don't add a taken
2184	// branch successor for it.
2185	IsPrevFT = !MIB->isTerminator(Inst: *LastInstr) ||
2186	MIB->getConditionalTailCall(Inst: *LastInstr);
2187	} else if (BB->succ_size() == 1) {
2188	IsPrevFT = MIB->isConditionalBranch(Inst: *LastInstr);
2189	} else {
2190	IsPrevFT = false;
2191	}
2192
2193	PrevBB = BB;
2194	}
2195
2196	// Assign landing pads and throwers info.
2197	recomputeLandingPads();
2198
2199	// Assign CFI information to each BB entry.
2200	annotateCFIState();
2201
2202	// Annotate invoke instructions with GNU_args_size data.
2203	propagateGnuArgsSizeInfo(AllocId: AllocatorId);
2204
2205	// Set the basic block layout to the original order and set end offsets.
2206	PrevBB = nullptr;
2207	for (BinaryBasicBlock *BB : BasicBlocks) {
2208	Layout.addBasicBlock(BB);
2209	if (PrevBB)
2210	PrevBB->setEndOffset(BB->getOffset());
2211	PrevBB = BB;
2212	}
2213	PrevBB->setEndOffset(getSize());
2214
2215	Layout.updateLayoutIndices();
2216
2217	normalizeCFIState();
2218
2219	// Clean-up memory taken by intermediate structures.
2220	//
2221	// NB: don't clear Labels list as we may need them if we mark the function
2222	// as non-simple later in the process of discovering extra entry points.
2223	clearList(List&: Instructions);
2224	clearList(List&: OffsetToCFI);
2225	clearList(List&: TakenBranches);
2226
2227	// Update the state.
2228	CurrentState = State::CFG;
2229
2230	// Make any necessary adjustments for indirect branches.
2231	if (!postProcessIndirectBranches(AllocId: AllocatorId)) {
2232	if (opts::Verbosity) {
2233	BC.errs() << "BOLT-WARNING: failed to post-process indirect branches for "
2234	<< *this << '\n';
2235	}
2236	// In relocation mode we want to keep processing the function but avoid
2237	// optimizing it.
2238	setSimple(false);
2239	}
2240
2241	clearList(List&: ExternallyReferencedOffsets);
2242	clearList(List&: UnknownIndirectBranchOffsets);
2243
2244	return Error::success();
2245	}
2246
2247	void BinaryFunction::postProcessCFG() {
2248	if (isSimple() && !BasicBlocks.empty()) {
2249	// Convert conditional tail call branches to conditional branches that jump
2250	// to a tail call.
2251	removeConditionalTailCalls();
2252
2253	postProcessProfile();
2254
2255	// Eliminate inconsistencies between branch instructions and CFG.
2256	postProcessBranches();
2257	}
2258
2259	calculateMacroOpFusionStats();
2260
2261	// The final cleanup of intermediate structures.
2262	clearList(List&: IgnoredBranches);
2263
2264	// Remove "Offset" annotations, unless we need an address-translation table
2265	// later. This has no cost, since annotations are allocated by a bumpptr
2266	// allocator and won't be released anyway until late in the pipeline.
2267	if (!requiresAddressTranslation() && !opts::Instrument) {
2268	for (BinaryBasicBlock &BB : blocks())
2269	for (MCInst &Inst : BB)
2270	BC.MIB->clearOffset(Inst);
2271	}
2272
2273	assert((!isSimple() || validateCFG()) &&
2274	"invalid CFG detected after post-processing");
2275	}
2276
2277	void BinaryFunction::calculateMacroOpFusionStats() {
2278	if (!getBinaryContext().isX86())
2279	return;
2280	for (const BinaryBasicBlock &BB : blocks()) {
2281	auto II = BB.getMacroOpFusionPair();
2282	if (II == BB.end())
2283	continue;
2284
2285	// Check offset of the second instruction.
2286	// FIXME: arch-specific.
2287	const uint32_t Offset = BC.MIB->getOffsetWithDefault(Inst: *std::next(x: II), Default: 0);
2288	if (!Offset || (getAddress() + Offset) % 64)
2289	continue;
2290
2291	LLVM_DEBUG(dbgs() << "\nmissed macro-op fusion at address 0x"
2292	<< Twine::utohexstr(getAddress() + Offset)
2293	<< " in function " << *this << "; executed "
2294	<< BB.getKnownExecutionCount() << " times.\n");
2295	++BC.Stats.MissedMacroFusionPairs;
2296	BC.Stats.MissedMacroFusionExecCount += BB.getKnownExecutionCount();
2297	}
2298	}
2299
2300	void BinaryFunction::removeTagsFromProfile() {
2301	for (BinaryBasicBlock *BB : BasicBlocks) {
2302	if (BB->ExecutionCount == BinaryBasicBlock::COUNT_NO_PROFILE)
2303	BB->ExecutionCount = 0;
2304	for (BinaryBasicBlock::BinaryBranchInfo &BI : BB->branch_info()) {
2305	if (BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
2306	BI.MispredictedCount != BinaryBasicBlock::COUNT_NO_PROFILE)
2307	continue;
2308	BI.Count = 0;
2309	BI.MispredictedCount = 0;
2310	}
2311	}
2312	}
2313
2314	void BinaryFunction::removeConditionalTailCalls() {
2315	// Blocks to be appended at the end.
2316	std::vector<std::unique_ptr<BinaryBasicBlock>> NewBlocks;
2317
2318	for (auto BBI = begin(); BBI != end(); ++BBI) {
2319	BinaryBasicBlock &BB = *BBI;
2320	MCInst *CTCInstr = BB.getLastNonPseudoInstr();
2321	if (!CTCInstr)
2322	continue;
2323
2324	std::optional<uint64_t> TargetAddressOrNone =
2325	BC.MIB->getConditionalTailCall(Inst: *CTCInstr);
2326	if (!TargetAddressOrNone)
2327	continue;
2328
2329	// Gather all necessary information about CTC instruction before
2330	// annotations are destroyed.
2331	const int32_t CFIStateBeforeCTC = BB.getCFIStateAtInstr(Instr: CTCInstr);
2332	uint64_t CTCTakenCount = BinaryBasicBlock::COUNT_NO_PROFILE;
2333	uint64_t CTCMispredCount = BinaryBasicBlock::COUNT_NO_PROFILE;
2334	if (hasValidProfile()) {
2335	CTCTakenCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
2336	Inst: *CTCInstr, Name: "CTCTakenCount");
2337	CTCMispredCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
2338	Inst: *CTCInstr, Name: "CTCMispredCount");
2339	}
2340
2341	// Assert that the tail call does not throw.
2342	assert(!BC.MIB->getEHInfo(*CTCInstr) &&
2343	"found tail call with associated landing pad");
2344
2345	// Create a basic block with an unconditional tail call instruction using
2346	// the same destination.
2347	const MCSymbol *CTCTargetLabel = BC.MIB->getTargetSymbol(Inst: *CTCInstr);
2348	assert(CTCTargetLabel && "symbol expected for conditional tail call");
2349	MCInst TailCallInstr;
2350	BC.MIB->createTailCall(Inst&: TailCallInstr, Target: CTCTargetLabel, Ctx: BC.Ctx.get());
2351
2352	// Move offset from CTCInstr to TailCallInstr.
2353	if (const std::optional<uint32_t> Offset = BC.MIB->getOffset(Inst: *CTCInstr)) {
2354	BC.MIB->setOffset(Inst&: TailCallInstr, Offset: *Offset);
2355	BC.MIB->clearOffset(Inst&: *CTCInstr);
2356	}
2357
2358	// Link new BBs to the original input offset of the BB where the CTC
2359	// is, so we can map samples recorded in new BBs back to the original BB
2360	// seem in the input binary (if using BAT)
2361	std::unique_ptr<BinaryBasicBlock> TailCallBB =
2362	createBasicBlock(Label: BC.Ctx->createNamedTempSymbol(Name: "TC"));
2363	TailCallBB->setOffset(BB.getInputOffset());
2364	TailCallBB->addInstruction(Inst: TailCallInstr);
2365	TailCallBB->setCFIState(CFIStateBeforeCTC);
2366
2367	// Add CFG edge with profile info from BB to TailCallBB.
2368	BB.addSuccessor(Succ: TailCallBB.get(), Count: CTCTakenCount, MispredictedCount: CTCMispredCount);
2369
2370	// Add execution count for the block.
2371	TailCallBB->setExecutionCount(CTCTakenCount);
2372
2373	BC.MIB->convertTailCallToJmp(Inst&: *CTCInstr);
2374
2375	BC.MIB->replaceBranchTarget(Inst&: *CTCInstr, TBB: TailCallBB->getLabel(),
2376	Ctx: BC.Ctx.get());
2377
2378	// Add basic block to the list that will be added to the end.
2379	NewBlocks.emplace_back(args: std::move(TailCallBB));
2380
2381	// Swap edges as the TailCallBB corresponds to the taken branch.
2382	BB.swapConditionalSuccessors();
2383
2384	// This branch is no longer a conditional tail call.
2385	BC.MIB->unsetConditionalTailCall(Inst&: *CTCInstr);
2386	}
2387
2388	insertBasicBlocks(StartBB: std::prev(x: end()), NewBBs: std::move(NewBlocks),
2389	/* UpdateLayout */ true,
2390	/* UpdateCFIState */ false);
2391	}
2392
2393	uint64_t BinaryFunction::getFunctionScore() const {
2394	if (FunctionScore != -1)
2395	return FunctionScore;
2396
2397	if (!isSimple() || !hasValidProfile()) {
2398	FunctionScore = 0;
2399	return FunctionScore;
2400	}
2401
2402	uint64_t TotalScore = 0ULL;
2403	for (const BinaryBasicBlock &BB : blocks()) {
2404	uint64_t BBExecCount = BB.getExecutionCount();
2405	if (BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
2406	continue;
2407	TotalScore += BBExecCount * BB.getNumNonPseudos();
2408	}
2409	FunctionScore = TotalScore;
2410	return FunctionScore;
2411	}
2412
2413	void BinaryFunction::annotateCFIState() {
2414	assert(CurrentState == State::Disassembled && "unexpected function state");
2415	assert(!BasicBlocks.empty() && "basic block list should not be empty");
2416
2417	// This is an index of the last processed CFI in FDE CFI program.
2418	uint32_t State = 0;
2419
2420	// This is an index of RememberState CFI reflecting effective state right
2421	// after execution of RestoreState CFI.
2422	//
2423	// It differs from State iff the CFI at (State-1)
2424	// was RestoreState (modulo GNU_args_size CFIs, which are ignored).
2425	//
2426	// This allows us to generate shorter replay sequences when producing new
2427	// CFI programs.
2428	uint32_t EffectiveState = 0;
2429
2430	// For tracking RememberState/RestoreState sequences.
2431	std::stack<uint32_t> StateStack;
2432
2433	for (BinaryBasicBlock *BB : BasicBlocks) {
2434	BB->setCFIState(EffectiveState);
2435
2436	for (const MCInst &Instr : *BB) {
2437	const MCCFIInstruction *CFI = getCFIFor(Instr);
2438	if (!CFI)
2439	continue;
2440
2441	++State;
2442
2443	switch (CFI->getOperation()) {
2444	case MCCFIInstruction::OpRememberState:
2445	StateStack.push(x: EffectiveState);
2446	EffectiveState = State;
2447	break;
2448	case MCCFIInstruction::OpRestoreState:
2449	assert(!StateStack.empty() && "corrupt CFI stack");
2450	EffectiveState = StateStack.top();
2451	StateStack.pop();
2452	break;
2453	case MCCFIInstruction::OpGnuArgsSize:
2454	// OpGnuArgsSize CFIs do not affect the CFI state.
2455	break;
2456	default:
2457	// Any other CFI updates the state.
2458	EffectiveState = State;
2459	break;
2460	}
2461	}
2462	}
2463
2464	assert(StateStack.empty() && "corrupt CFI stack");
2465	}
2466
2467	namespace {
2468
2469	/// Our full interpretation of a DWARF CFI machine state at a given point
2470	struct CFISnapshot {
2471	/// CFA register number and offset defining the canonical frame at this
2472	/// point, or the number of a rule (CFI state) that computes it with a
2473	/// DWARF expression. This number will be negative if it refers to a CFI
2474	/// located in the CIE instead of the FDE.
2475	uint32_t CFAReg;
2476	int32_t CFAOffset;
2477	int32_t CFARule;
2478	/// Mapping of rules (CFI states) that define the location of each
2479	/// register. If absent, no rule defining the location of such register
2480	/// was ever read. This number will be negative if it refers to a CFI
2481	/// located in the CIE instead of the FDE.
2482	DenseMap<int32_t, int32_t> RegRule;
2483
2484	/// References to CIE, FDE and expanded instructions after a restore state
2485	const BinaryFunction::CFIInstrMapType &CIE;
2486	const BinaryFunction::CFIInstrMapType &FDE;
2487	const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents;
2488
2489	/// Current FDE CFI number representing the state where the snapshot is at
2490	int32_t CurState;
2491
2492	/// Used when we don't have information about which state/rule to apply
2493	/// to recover the location of either the CFA or a specific register
2494	constexpr static int32_t UNKNOWN = std::numeric_limits<int32_t>::min();
2495
2496	private:
2497	/// Update our snapshot by executing a single CFI
2498	void update(const MCCFIInstruction &Instr, int32_t RuleNumber) {
2499	switch (Instr.getOperation()) {
2500	case MCCFIInstruction::OpSameValue:
2501	case MCCFIInstruction::OpRelOffset:
2502	case MCCFIInstruction::OpOffset:
2503	case MCCFIInstruction::OpRestore:
2504	case MCCFIInstruction::OpUndefined:
2505	case MCCFIInstruction::OpRegister:
2506	RegRule[Instr.getRegister()] = RuleNumber;
2507	break;
2508	case MCCFIInstruction::OpDefCfaRegister:
2509	CFAReg = Instr.getRegister();
2510	CFARule = UNKNOWN;
2511
2512	// This shouldn't happen according to the spec but GNU binutils on RISC-V
2513	// emits a DW_CFA_def_cfa_register in CIE's which leaves the offset
2514	// unspecified. Both readelf and llvm-dwarfdump interpret the offset as 0
2515	// in this case so let's do the same.
2516	if (CFAOffset == UNKNOWN)
2517	CFAOffset = 0;
2518	break;
2519	case MCCFIInstruction::OpDefCfaOffset:
2520	CFAOffset = Instr.getOffset();
2521	CFARule = UNKNOWN;
2522	break;
2523	case MCCFIInstruction::OpDefCfa:
2524	CFAReg = Instr.getRegister();
2525	CFAOffset = Instr.getOffset();
2526	CFARule = UNKNOWN;
2527	break;
2528	case MCCFIInstruction::OpEscape: {
2529	std::optional<uint8_t> Reg =
2530	readDWARFExpressionTargetReg(ExprBytes: Instr.getValues());
2531	// Handle DW_CFA_def_cfa_expression
2532	if (!Reg) {
2533	CFARule = RuleNumber;
2534	break;
2535	}
2536	RegRule[*Reg] = RuleNumber;
2537	break;
2538	}
2539	case MCCFIInstruction::OpAdjustCfaOffset:
2540	case MCCFIInstruction::OpWindowSave:
2541	case MCCFIInstruction::OpNegateRAState:
2542	case MCCFIInstruction::OpLLVMDefAspaceCfa:
2543	llvm_unreachable("unsupported CFI opcode");
2544	break;
2545	case MCCFIInstruction::OpRememberState:
2546	case MCCFIInstruction::OpRestoreState:
2547	case MCCFIInstruction::OpGnuArgsSize:
2548	// do not affect CFI state
2549	break;
2550	}
2551	}
2552
2553	public:
2554	/// Advance state reading FDE CFI instructions up to State number
2555	void advanceTo(int32_t State) {
2556	for (int32_t I = CurState, E = State; I != E; ++I) {
2557	const MCCFIInstruction &Instr = FDE[I];
2558	if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) {
2559	update(Instr, RuleNumber: I);
2560	continue;
2561	}
2562	// If restore state instruction, fetch the equivalent CFIs that have
2563	// the same effect of this restore. This is used to ensure remember-
2564	// restore pairs are completely removed.
2565	auto Iter = FrameRestoreEquivalents.find(Val: I);
2566	if (Iter == FrameRestoreEquivalents.end())
2567	continue;
2568	for (int32_t RuleNumber : Iter->second)
2569	update(Instr: FDE[RuleNumber], RuleNumber);
2570	}
2571
2572	assert(((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) ||
2573	CFARule != UNKNOWN) &&
2574	"CIE did not define default CFA?");
2575
2576	CurState = State;
2577	}
2578
2579	/// Interpret all CIE and FDE instructions up until CFI State number and
2580	/// populate this snapshot
2581	CFISnapshot(
2582	const BinaryFunction::CFIInstrMapType &CIE,
2583	const BinaryFunction::CFIInstrMapType &FDE,
2584	const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents,
2585	int32_t State)
2586	: CIE(CIE), FDE(FDE), FrameRestoreEquivalents(FrameRestoreEquivalents) {
2587	CFAReg = UNKNOWN;
2588	CFAOffset = UNKNOWN;
2589	CFARule = UNKNOWN;
2590	CurState = 0;
2591
2592	for (int32_t I = 0, E = CIE.size(); I != E; ++I) {
2593	const MCCFIInstruction &Instr = CIE[I];
2594	update(Instr, RuleNumber: -I);
2595	}
2596
2597	advanceTo(State);
2598	}
2599	};
2600
2601	/// A CFI snapshot with the capability of checking if incremental additions to
2602	/// it are redundant. This is used to ensure we do not emit two CFI instructions
2603	/// back-to-back that are doing the same state change, or to avoid emitting a
2604	/// CFI at all when the state at that point would not be modified after that CFI
2605	struct CFISnapshotDiff : public CFISnapshot {
2606	bool RestoredCFAReg{false};
2607	bool RestoredCFAOffset{false};
2608	DenseMap<int32_t, bool> RestoredRegs;
2609
2610	CFISnapshotDiff(const CFISnapshot &S) : CFISnapshot(S) {}
2611
2612	CFISnapshotDiff(
2613	const BinaryFunction::CFIInstrMapType &CIE,
2614	const BinaryFunction::CFIInstrMapType &FDE,
2615	const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents,
2616	int32_t State)
2617	: CFISnapshot(CIE, FDE, FrameRestoreEquivalents, State) {}
2618
2619	/// Return true if applying Instr to this state is redundant and can be
2620	/// dismissed.
2621	bool isRedundant(const MCCFIInstruction &Instr) {
2622	switch (Instr.getOperation()) {
2623	case MCCFIInstruction::OpSameValue:
2624	case MCCFIInstruction::OpRelOffset:
2625	case MCCFIInstruction::OpOffset:
2626	case MCCFIInstruction::OpRestore:
2627	case MCCFIInstruction::OpUndefined:
2628	case MCCFIInstruction::OpRegister:
2629	case MCCFIInstruction::OpEscape: {
2630	uint32_t Reg;
2631	if (Instr.getOperation() != MCCFIInstruction::OpEscape) {
2632	Reg = Instr.getRegister();
2633	} else {
2634	std::optional<uint8_t> R =
2635	readDWARFExpressionTargetReg(ExprBytes: Instr.getValues());
2636	// Handle DW_CFA_def_cfa_expression
2637	if (!R) {
2638	if (RestoredCFAReg && RestoredCFAOffset)
2639	return true;
2640	RestoredCFAReg = true;
2641	RestoredCFAOffset = true;
2642	return false;
2643	}
2644	Reg = *R;
2645	}
2646	if (RestoredRegs[Reg])
2647	return true;
2648	RestoredRegs[Reg] = true;
2649	const int32_t CurRegRule = RegRule.contains(Val: Reg) ? RegRule[Reg] : UNKNOWN;
2650	if (CurRegRule == UNKNOWN) {
2651	if (Instr.getOperation() == MCCFIInstruction::OpRestore ||
2652	Instr.getOperation() == MCCFIInstruction::OpSameValue)
2653	return true;
2654	return false;
2655	}
2656	const MCCFIInstruction &LastDef =
2657	CurRegRule < 0 ? CIE[-CurRegRule] : FDE[CurRegRule];
2658	return LastDef == Instr;
2659	}
2660	case MCCFIInstruction::OpDefCfaRegister:
2661	if (RestoredCFAReg)
2662	return true;
2663	RestoredCFAReg = true;
2664	return CFAReg == Instr.getRegister();
2665	case MCCFIInstruction::OpDefCfaOffset:
2666	if (RestoredCFAOffset)
2667	return true;
2668	RestoredCFAOffset = true;
2669	return CFAOffset == Instr.getOffset();
2670	case MCCFIInstruction::OpDefCfa:
2671	if (RestoredCFAReg && RestoredCFAOffset)
2672	return true;
2673	RestoredCFAReg = true;
2674	RestoredCFAOffset = true;
2675	return CFAReg == Instr.getRegister() && CFAOffset == Instr.getOffset();
2676	case MCCFIInstruction::OpAdjustCfaOffset:
2677	case MCCFIInstruction::OpWindowSave:
2678	case MCCFIInstruction::OpNegateRAState:
2679	case MCCFIInstruction::OpLLVMDefAspaceCfa:
2680	llvm_unreachable("unsupported CFI opcode");
2681	return false;
2682	case MCCFIInstruction::OpRememberState:
2683	case MCCFIInstruction::OpRestoreState:
2684	case MCCFIInstruction::OpGnuArgsSize:
2685	// do not affect CFI state
2686	return true;
2687	}
2688	return false;
2689	}
2690	};
2691
2692	} // end anonymous namespace
2693
2694	bool BinaryFunction::replayCFIInstrs(int32_t FromState, int32_t ToState,
2695	BinaryBasicBlock *InBB,
2696	BinaryBasicBlock::iterator InsertIt) {
2697	if (FromState == ToState)
2698	return true;
2699	assert(FromState < ToState && "can only replay CFIs forward");
2700
2701	CFISnapshotDiff CFIDiff(CIEFrameInstructions, FrameInstructions,
2702	FrameRestoreEquivalents, FromState);
2703
2704	std::vector<uint32_t> NewCFIs;
2705	for (int32_t CurState = FromState; CurState < ToState; ++CurState) {
2706	MCCFIInstruction *Instr = &FrameInstructions[CurState];
2707	if (Instr->getOperation() == MCCFIInstruction::OpRestoreState) {
2708	auto Iter = FrameRestoreEquivalents.find(Val: CurState);
2709	assert(Iter != FrameRestoreEquivalents.end());
2710	NewCFIs.insert(position: NewCFIs.end(), first: Iter->second.begin(), last: Iter->second.end());
2711	// RestoreState / Remember will be filtered out later by CFISnapshotDiff,
2712	// so we might as well fall-through here.
2713	}
2714	NewCFIs.push_back(x: CurState);
2715	}
2716
2717	// Replay instructions while avoiding duplicates
2718	for (int32_t State : llvm::reverse(C&: NewCFIs)) {
2719	if (CFIDiff.isRedundant(Instr: FrameInstructions[State]))
2720	continue;
2721	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: State);
2722	}
2723
2724	return true;
2725	}
2726
2727	SmallVector<int32_t, 4>
2728	BinaryFunction::unwindCFIState(int32_t FromState, int32_t ToState,
2729	BinaryBasicBlock *InBB,
2730	BinaryBasicBlock::iterator &InsertIt) {
2731	SmallVector<int32_t, 4> NewStates;
2732
2733	CFISnapshot ToCFITable(CIEFrameInstructions, FrameInstructions,
2734	FrameRestoreEquivalents, ToState);
2735	CFISnapshotDiff FromCFITable(ToCFITable);
2736	FromCFITable.advanceTo(State: FromState);
2737
2738	auto undoStateDefCfa = [&]() {
2739	if (ToCFITable.CFARule == CFISnapshot::UNKNOWN) {
2740	FrameInstructions.emplace_back(Args: MCCFIInstruction::cfiDefCfa(
2741	L: nullptr, Register: ToCFITable.CFAReg, Offset: ToCFITable.CFAOffset));
2742	if (FromCFITable.isRedundant(Instr: FrameInstructions.back())) {
2743	FrameInstructions.pop_back();
2744	return;
2745	}
2746	NewStates.push_back(Elt: FrameInstructions.size() - 1);
2747	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: FrameInstructions.size() - 1);
2748	++InsertIt;
2749	} else if (ToCFITable.CFARule < 0) {
2750	if (FromCFITable.isRedundant(Instr: CIEFrameInstructions[-ToCFITable.CFARule]))
2751	return;
2752	NewStates.push_back(Elt: FrameInstructions.size());
2753	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: FrameInstructions.size());
2754	++InsertIt;
2755	FrameInstructions.emplace_back(Args&: CIEFrameInstructions[-ToCFITable.CFARule]);
2756	} else if (!FromCFITable.isRedundant(
2757	Instr: FrameInstructions[ToCFITable.CFARule])) {
2758	NewStates.push_back(Elt: ToCFITable.CFARule);
2759	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: ToCFITable.CFARule);
2760	++InsertIt;
2761	}
2762	};
2763
2764	auto undoState = [&](const MCCFIInstruction &Instr) {
2765	switch (Instr.getOperation()) {
2766	case MCCFIInstruction::OpRememberState:
2767	case MCCFIInstruction::OpRestoreState:
2768	break;
2769	case MCCFIInstruction::OpSameValue:
2770	case MCCFIInstruction::OpRelOffset:
2771	case MCCFIInstruction::OpOffset:
2772	case MCCFIInstruction::OpRestore:
2773	case MCCFIInstruction::OpUndefined:
2774	case MCCFIInstruction::OpEscape:
2775	case MCCFIInstruction::OpRegister: {
2776	uint32_t Reg;
2777	if (Instr.getOperation() != MCCFIInstruction::OpEscape) {
2778	Reg = Instr.getRegister();
2779	} else {
2780	std::optional<uint8_t> R =
2781	readDWARFExpressionTargetReg(ExprBytes: Instr.getValues());
2782	// Handle DW_CFA_def_cfa_expression
2783	if (!R) {
2784	undoStateDefCfa();
2785	return;
2786	}
2787	Reg = *R;
2788	}
2789
2790	if (!ToCFITable.RegRule.contains(Val: Reg)) {
2791	FrameInstructions.emplace_back(
2792	Args: MCCFIInstruction::createRestore(L: nullptr, Register: Reg));
2793	if (FromCFITable.isRedundant(Instr: FrameInstructions.back())) {
2794	FrameInstructions.pop_back();
2795	break;
2796	}
2797	NewStates.push_back(Elt: FrameInstructions.size() - 1);
2798	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: FrameInstructions.size() - 1);
2799	++InsertIt;
2800	break;
2801	}
2802	const int32_t Rule = ToCFITable.RegRule[Reg];
2803	if (Rule < 0) {
2804	if (FromCFITable.isRedundant(Instr: CIEFrameInstructions[-Rule]))
2805	break;
2806	NewStates.push_back(Elt: FrameInstructions.size());
2807	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: FrameInstructions.size());
2808	++InsertIt;
2809	FrameInstructions.emplace_back(Args&: CIEFrameInstructions[-Rule]);
2810	break;
2811	}
2812	if (FromCFITable.isRedundant(Instr: FrameInstructions[Rule]))
2813	break;
2814	NewStates.push_back(Elt: Rule);
2815	InsertIt = addCFIPseudo(BB: InBB, Pos: InsertIt, Offset: Rule);
2816	++InsertIt;
2817	break;
2818	}
2819	case MCCFIInstruction::OpDefCfaRegister:
2820	case MCCFIInstruction::OpDefCfaOffset:
2821	case MCCFIInstruction::OpDefCfa:
2822	undoStateDefCfa();
2823	break;
2824	case MCCFIInstruction::OpAdjustCfaOffset:
2825	case MCCFIInstruction::OpWindowSave:
2826	case MCCFIInstruction::OpNegateRAState:
2827	case MCCFIInstruction::OpLLVMDefAspaceCfa:
2828	llvm_unreachable("unsupported CFI opcode");
2829	break;
2830	case MCCFIInstruction::OpGnuArgsSize:
2831	// do not affect CFI state
2832	break;
2833	}
2834	};
2835
2836	// Undo all modifications from ToState to FromState
2837	for (int32_t I = ToState, E = FromState; I != E; ++I) {
2838	const MCCFIInstruction &Instr = FrameInstructions[I];
2839	if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) {
2840	undoState(Instr);
2841	continue;
2842	}
2843	auto Iter = FrameRestoreEquivalents.find(Val: I);
2844	if (Iter == FrameRestoreEquivalents.end())
2845	continue;
2846	for (int32_t State : Iter->second)
2847	undoState(FrameInstructions[State]);
2848	}
2849
2850	return NewStates;
2851	}
2852
2853	void BinaryFunction::normalizeCFIState() {
2854	// Reordering blocks with remember-restore state instructions can be specially
2855	// tricky. When rewriting the CFI, we omit remember-restore state instructions
2856	// entirely. For restore state, we build a map expanding each restore to the
2857	// equivalent unwindCFIState sequence required at that point to achieve the
2858	// same effect of the restore. All remember state are then just ignored.
2859	std::stack<int32_t> Stack;
2860	for (BinaryBasicBlock *CurBB : Layout.blocks()) {
2861	for (auto II = CurBB->begin(); II != CurBB->end(); ++II) {
2862	if (const MCCFIInstruction *CFI = getCFIFor(Instr: *II)) {
2863	if (CFI->getOperation() == MCCFIInstruction::OpRememberState) {
2864	Stack.push(x: II->getOperand(i: 0).getImm());
2865	continue;
2866	}
2867	if (CFI->getOperation() == MCCFIInstruction::OpRestoreState) {
2868	const int32_t RememberState = Stack.top();
2869	const int32_t CurState = II->getOperand(i: 0).getImm();
2870	FrameRestoreEquivalents[CurState] =
2871	unwindCFIState(FromState: CurState, ToState: RememberState, InBB: CurBB, InsertIt&: II);
2872	Stack.pop();
2873	}
2874	}
2875	}
2876	}
2877	}
2878
2879	bool BinaryFunction::finalizeCFIState() {
2880	LLVM_DEBUG(
2881	dbgs() << "Trying to fix CFI states for each BB after reordering.\n");
2882	LLVM_DEBUG(dbgs() << "This is the list of CFI states for each BB of " << *this
2883	<< ": ");
2884
2885	const char *Sep = "";
2886	(void)Sep;
2887	for (FunctionFragment &FF : Layout.fragments()) {
2888	// Hot-cold border: at start of each region (with a different FDE) we need
2889	// to reset the CFI state.
2890	int32_t State = 0;
2891
2892	for (BinaryBasicBlock *BB : FF) {
2893	const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
2894
2895	// We need to recover the correct state if it doesn't match expected
2896	// state at BB entry point.
2897	if (BB->getCFIState() < State) {
2898	// In this case, State is currently higher than what this BB expect it
2899	// to be. To solve this, we need to insert CFI instructions to undo
2900	// the effect of all CFI from BB's state to current State.
2901	auto InsertIt = BB->begin();
2902	unwindCFIState(FromState: State, ToState: BB->getCFIState(), InBB: BB, InsertIt);
2903	} else if (BB->getCFIState() > State) {
2904	// If BB's CFI state is greater than State, it means we are behind in
2905	// the state. Just emit all instructions to reach this state at the
2906	// beginning of this BB. If this sequence of instructions involve
2907	// remember state or restore state, bail out.
2908	if (!replayCFIInstrs(FromState: State, ToState: BB->getCFIState(), InBB: BB, InsertIt: BB->begin()))
2909	return false;
2910	}
2911
2912	State = CFIStateAtExit;
2913	LLVM_DEBUG(dbgs() << Sep << State; Sep = ", ");
2914	}
2915	}
2916	LLVM_DEBUG(dbgs() << "\n");
2917
2918	for (BinaryBasicBlock &BB : blocks()) {
2919	for (auto II = BB.begin(); II != BB.end();) {
2920	const MCCFIInstruction *CFI = getCFIFor(Instr: *II);
2921	if (CFI && (CFI->getOperation() == MCCFIInstruction::OpRememberState ||
2922	CFI->getOperation() == MCCFIInstruction::OpRestoreState)) {
2923	II = BB.eraseInstruction(II);
2924	} else {
2925	++II;
2926	}
2927	}
2928	}
2929
2930	return true;
2931	}
2932
2933	bool BinaryFunction::requiresAddressTranslation() const {
2934	return opts::EnableBAT || hasSDTMarker() || hasPseudoProbe();
2935	}
2936
2937	bool BinaryFunction::requiresAddressMap() const {
2938	if (isInjected())
2939	return false;
2940
2941	return opts::UpdateDebugSections || isMultiEntry() ||
2942	requiresAddressTranslation();
2943	}
2944
2945	uint64_t BinaryFunction::getInstructionCount() const {
2946	uint64_t Count = 0;
2947	for (const BinaryBasicBlock &BB : blocks())
2948	Count += BB.getNumNonPseudos();
2949	return Count;
2950	}
2951
2952	void BinaryFunction::clearDisasmState() {
2953	clearList(List&: Instructions);
2954	clearList(List&: IgnoredBranches);
2955	clearList(List&: TakenBranches);
2956
2957	if (BC.HasRelocations) {
2958	for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
2959	BC.UndefinedSymbols.insert(x: LI.second);
2960	for (MCSymbol *const EndLabel : FunctionEndLabels)
2961	if (EndLabel)
2962	BC.UndefinedSymbols.insert(x: EndLabel);
2963	}
2964	}
2965
2966	void BinaryFunction::setTrapOnEntry() {
2967	clearDisasmState();
2968
2969	forEachEntryPoint(Callback: [&](uint64_t Offset, const MCSymbol *Label) -> bool {
2970	MCInst TrapInstr;
2971	BC.MIB->createTrap(Inst&: TrapInstr);
2972	addInstruction(Offset, Instruction: std::move(TrapInstr));
2973	return true;
2974	});
2975
2976	TrapsOnEntry = true;
2977	}
2978
2979	void BinaryFunction::setIgnored() {
2980	if (opts::processAllFunctions()) {
2981	// We can accept ignored functions before they've been disassembled.
2982	// In that case, they would still get disassembled and emited, but not
2983	// optimized.
2984	assert(CurrentState == State::Empty &&
2985	"cannot ignore non-empty functions in current mode");
2986	IsIgnored = true;
2987	return;
2988	}
2989
2990	clearDisasmState();
2991
2992	// Clear CFG state too.
2993	if (hasCFG()) {
2994	releaseCFG();
2995
2996	for (BinaryBasicBlock *BB : BasicBlocks)
2997	delete BB;
2998	clearList(List&: BasicBlocks);
2999
3000	for (BinaryBasicBlock *BB : DeletedBasicBlocks)
3001	delete BB;
3002	clearList(List&: DeletedBasicBlocks);
3003
3004	Layout.clear();
3005	}
3006
3007	CurrentState = State::Empty;
3008
3009	IsIgnored = true;
3010	IsSimple = false;
3011	LLVM_DEBUG(dbgs() << "Ignoring " << getPrintName() << '\n');
3012	}
3013
3014	void BinaryFunction::duplicateConstantIslands() {
3015	assert(Islands && "function expected to have constant islands");
3016
3017	for (BinaryBasicBlock *BB : getLayout().blocks()) {
3018	if (!BB->isCold())
3019	continue;
3020
3021	for (MCInst &Inst : *BB) {
3022	int OpNum = 0;
3023	for (MCOperand &Operand : Inst) {
3024	if (!Operand.isExpr()) {
3025	++OpNum;
3026	continue;
3027	}
3028	const MCSymbol *Symbol = BC.MIB->getTargetSymbol(Inst, OpNum);
3029	// Check if this is an island symbol
3030	if (!Islands->Symbols.count(Ptr: Symbol) &&
3031	!Islands->ProxySymbols.count(Val: Symbol))
3032	continue;
3033
3034	// Create cold symbol, if missing
3035	auto ISym = Islands->ColdSymbols.find(Val: Symbol);
3036	MCSymbol *ColdSymbol;
3037	if (ISym != Islands->ColdSymbols.end()) {
3038	ColdSymbol = ISym->second;
3039	} else {
3040	ColdSymbol = BC.Ctx->getOrCreateSymbol(Name: Symbol->getName() + ".cold");
3041	Islands->ColdSymbols[Symbol] = ColdSymbol;
3042	// Check if this is a proxy island symbol and update owner proxy map
3043	if (Islands->ProxySymbols.count(Val: Symbol)) {
3044	BinaryFunction *Owner = Islands->ProxySymbols[Symbol];
3045	auto IProxiedSym = Owner->Islands->Proxies[this].find(x: Symbol);
3046	Owner->Islands->ColdProxies[this][IProxiedSym->second] = ColdSymbol;
3047	}
3048	}
3049
3050	// Update instruction reference
3051	Operand = MCOperand::createExpr(Val: BC.MIB->getTargetExprFor(
3052	Inst,
3053	Expr: MCSymbolRefExpr::create(Symbol: ColdSymbol, Kind: MCSymbolRefExpr::VK_None,
3054	Ctx&: *BC.Ctx),
3055	Ctx&: *BC.Ctx, RelType: 0));
3056	++OpNum;
3057	}
3058	}
3059	}
3060	}
3061
3062	#ifndef MAX_PATH
3063	#define MAX_PATH 255
3064	#endif
3065
3066	static std::string constructFilename(std::string Filename,
3067	std::string Annotation,
3068	std::string Suffix) {
3069	std::replace(first: Filename.begin(), last: Filename.end(), old_value: '/', new_value: '-');
3070	if (!Annotation.empty())
3071	Annotation.insert(pos: 0, s: "-");
3072	if (Filename.size() + Annotation.size() + Suffix.size() > MAX_PATH) {
3073	assert(Suffix.size() + Annotation.size() <= MAX_PATH);
3074	Filename.resize(MAX_PATH - (Suffix.size() + Annotation.size()));
3075	}
3076	Filename += Annotation;
3077	Filename += Suffix;
3078	return Filename;
3079	}
3080
3081	static std::string formatEscapes(const std::string &Str) {
3082	std::string Result;
3083	for (unsigned I = 0; I < Str.size(); ++I) {
3084	char C = Str[I];
3085	switch (C) {
3086	case '\n':
3087	Result += "&#13;";
3088	break;
3089	case '"':
3090	break;
3091	default:
3092	Result += C;
3093	break;
3094	}
3095	}
3096	return Result;
3097	}
3098
3099	void BinaryFunction::dumpGraph(raw_ostream &OS) const {
3100	OS << "digraph \"" << getPrintName() << "\" {\n"
3101	<< "node [fontname=courier, shape=box, style=filled, colorscheme=brbg9]\n";
3102	uint64_t Offset = Address;
3103	for (BinaryBasicBlock *BB : BasicBlocks) {
3104	auto LayoutPos = find(Range: Layout.blocks(), Val: BB);
3105	unsigned LayoutIndex = LayoutPos - Layout.block_begin();
3106	const char *ColdStr = BB->isCold() ? " (cold)" : "";
3107	std::vector<std::string> Attrs;
3108	// Bold box for entry points
3109	if (isEntryPoint(BB: *BB))
3110	Attrs.push_back(x: "penwidth=2");
3111	if (BLI && BLI->getLoopFor(BB)) {
3112	// Distinguish innermost loops
3113	const BinaryLoop *Loop = BLI->getLoopFor(BB);
3114	if (Loop->isInnermost())
3115	Attrs.push_back(x: "fillcolor=6");
3116	else // some outer loop
3117	Attrs.push_back(x: "fillcolor=4");
3118	} else { // non-loopy code
3119	Attrs.push_back(x: "fillcolor=5");
3120	}
3121	ListSeparator LS;
3122	OS << "\"" << BB->getName() << "\" [";
3123	for (StringRef Attr : Attrs)
3124	OS << LS << Attr;
3125	OS << "]\n";
3126	OS << format(Fmt: "\"%s\" [label=\"%s%s\\n(C:%lu,O:%lu,I:%u,L:%u,CFI:%u)\\n",
3127	Vals: BB->getName().data(), Vals: BB->getName().data(), Vals: ColdStr,
3128	Vals: BB->getKnownExecutionCount(), Vals: BB->getOffset(), Vals: getIndex(BB),
3129	Vals: LayoutIndex, Vals: BB->getCFIState());
3130
3131	if (opts::DotToolTipCode) {
3132	std::string Str;
3133	raw_string_ostream CS(Str);
3134	Offset = BC.printInstructions(OS&: CS, Begin: BB->begin(), End: BB->end(), Offset, Function: this,
3135	/* PrintMCInst = */ false,
3136	/* PrintMemData = */ false,
3137	/* PrintRelocations = */ false,
3138	/* Endl = */ R"(\\l)");
3139	OS << formatEscapes(Str: CS.str()) << '\n';
3140	}
3141	OS << "\"]\n";
3142
3143	// analyzeBranch is just used to get the names of the branch
3144	// opcodes.
3145	const MCSymbol *TBB = nullptr;
3146	const MCSymbol *FBB = nullptr;
3147	MCInst *CondBranch = nullptr;
3148	MCInst *UncondBranch = nullptr;
3149	const bool Success = BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);
3150
3151	const MCInst *LastInstr = BB->getLastNonPseudoInstr();
3152	const bool IsJumpTable = LastInstr && BC.MIB->getJumpTable(Inst: *LastInstr);
3153
3154	auto BI = BB->branch_info_begin();
3155	for (BinaryBasicBlock *Succ : BB->successors()) {
3156	std::string Branch;
3157	if (Success) {
3158	if (Succ == BB->getConditionalSuccessor(Condition: true)) {
3159	Branch = CondBranch ? std::string(BC.InstPrinter->getOpcodeName(
3160	Opcode: CondBranch->getOpcode()))
3161	: "TB";
3162	} else if (Succ == BB->getConditionalSuccessor(Condition: false)) {
3163	Branch = UncondBranch ? std::string(BC.InstPrinter->getOpcodeName(
3164	Opcode: UncondBranch->getOpcode()))
3165	: "FB";
3166	} else {
3167	Branch = "FT";
3168	}
3169	}
3170	if (IsJumpTable)
3171	Branch = "JT";
3172	OS << format(Fmt: "\"%s\" -> \"%s\" [label=\"%s", Vals: BB->getName().data(),
3173	Vals: Succ->getName().data(), Vals: Branch.c_str());
3174
3175	if (BB->getExecutionCount() != COUNT_NO_PROFILE &&
3176	BI->MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
3177	OS << "\\n(C:" << BI->Count << ",M:" << BI->MispredictedCount << ")";
3178	} else if (ExecutionCount != COUNT_NO_PROFILE &&
3179	BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
3180	OS << "\\n(IC:" << BI->Count << ")";
3181	}
3182	OS << "\"]\n";
3183
3184	++BI;
3185	}
3186	for (BinaryBasicBlock *LP : BB->landing_pads()) {
3187	OS << format(Fmt: "\"%s\" -> \"%s\" [constraint=false style=dashed]\n",
3188	Vals: BB->getName().data(), Vals: LP->getName().data());
3189	}
3190	}
3191	OS << "}\n";
3192	}
3193
3194	void BinaryFunction::viewGraph() const {
3195	SmallString<MAX_PATH> Filename;
3196	if (std::error_code EC =
3197	sys::fs::createTemporaryFile(Prefix: "bolt-cfg", Suffix: "dot", ResultPath&: Filename)) {
3198	BC.errs() << "BOLT-ERROR: " << EC.message() << ", unable to create "
3199	<< " bolt-cfg-XXXXX.dot temporary file.\n";
3200	return;
3201	}
3202	dumpGraphToFile(Filename: std::string(Filename));
3203	if (DisplayGraph(Filename))
3204	BC.errs() << "BOLT-ERROR: Can't display " << Filename
3205	<< " with graphviz.\n";
3206	if (std::error_code EC = sys::fs::remove(path: Filename)) {
3207	BC.errs() << "BOLT-WARNING: " << EC.message() << ", failed to remove "
3208	<< Filename << "\n";
3209	}
3210	}
3211
3212	void BinaryFunction::dumpGraphForPass(std::string Annotation) const {
3213	if (!opts::shouldPrint(Function: *this))
3214	return;
3215
3216	std::string Filename = constructFilename(Filename: getPrintName(), Annotation, Suffix: ".dot");
3217	if (opts::Verbosity >= 1)
3218	BC.outs() << "BOLT-INFO: dumping CFG to " << Filename << "\n";
3219	dumpGraphToFile(Filename);
3220	}
3221
3222	void BinaryFunction::dumpGraphToFile(std::string Filename) const {
3223	std::error_code EC;
3224	raw_fd_ostream of(Filename, EC, sys::fs::OF_None);
3225	if (EC) {
3226	if (opts::Verbosity >= 1) {
3227	BC.errs() << "BOLT-WARNING: " << EC.message() << ", unable to open "
3228	<< Filename << " for output.\n";
3229	}
3230	return;
3231	}
3232	dumpGraph(OS&: of);
3233	}
3234
3235	bool BinaryFunction::validateCFG() const {
3236	// Skip the validation of CFG after it is finalized
3237	if (CurrentState == State::CFG_Finalized)
3238	return true;
3239
3240	bool Valid = true;
3241	for (BinaryBasicBlock *BB : BasicBlocks)
3242	Valid &= BB->validateSuccessorInvariants();
3243
3244	if (!Valid)
3245	return Valid;
3246
3247	// Make sure all blocks in CFG are valid.
3248	auto validateBlock = [this](const BinaryBasicBlock *BB, StringRef Desc) {
3249	if (!BB->isValid()) {
3250	BC.errs() << "BOLT-ERROR: deleted " << Desc << " " << BB->getName()
3251	<< " detected in:\n";
3252	this->dump();
3253	return false;
3254	}
3255	return true;
3256	};
3257	for (const BinaryBasicBlock *BB : BasicBlocks) {
3258	if (!validateBlock(BB, "block"))
3259	return false;
3260	for (const BinaryBasicBlock *PredBB : BB->predecessors())
3261	if (!validateBlock(PredBB, "predecessor"))
3262	return false;
3263	for (const BinaryBasicBlock *SuccBB : BB->successors())
3264	if (!validateBlock(SuccBB, "successor"))
3265	return false;
3266	for (const BinaryBasicBlock *LP : BB->landing_pads())
3267	if (!validateBlock(LP, "landing pad"))
3268	return false;
3269	for (const BinaryBasicBlock *Thrower : BB->throwers())
3270	if (!validateBlock(Thrower, "thrower"))
3271	return false;
3272	}
3273
3274	for (const BinaryBasicBlock *BB : BasicBlocks) {
3275	std::unordered_set<const BinaryBasicBlock *> BBLandingPads;
3276	for (const BinaryBasicBlock *LP : BB->landing_pads()) {
3277	if (BBLandingPads.count(x: LP)) {
3278	BC.errs() << "BOLT-ERROR: duplicate landing pad detected in"
3279	<< BB->getName() << " in function " << *this << '\n';
3280	return false;
3281	}
3282	BBLandingPads.insert(x: LP);
3283	}
3284
3285	std::unordered_set<const BinaryBasicBlock *> BBThrowers;
3286	for (const BinaryBasicBlock *Thrower : BB->throwers()) {
3287	if (BBThrowers.count(x: Thrower)) {
3288	BC.errs() << "BOLT-ERROR: duplicate thrower detected in"
3289	<< BB->getName() << " in function " << *this << '\n';
3290	return false;
3291	}
3292	BBThrowers.insert(x: Thrower);
3293	}
3294
3295	for (const BinaryBasicBlock *LPBlock : BB->landing_pads()) {
3296	if (!llvm::is_contained(Range: LPBlock->throwers(), Element: BB)) {
3297	BC.errs() << "BOLT-ERROR: inconsistent landing pad detected in "
3298	<< *this << ": " << BB->getName()
3299	<< " is in LandingPads but not in " << LPBlock->getName()
3300	<< " Throwers\n";
3301	return false;
3302	}
3303	}
3304	for (const BinaryBasicBlock *Thrower : BB->throwers()) {
3305	if (!llvm::is_contained(Range: Thrower->landing_pads(), Element: BB)) {
3306	BC.errs() << "BOLT-ERROR: inconsistent thrower detected in " << *this
3307	<< ": " << BB->getName() << " is in Throwers list but not in "
3308	<< Thrower->getName() << " LandingPads\n";
3309	return false;
3310	}
3311	}
3312	}
3313
3314	return Valid;
3315	}
3316
3317	void BinaryFunction::fixBranches() {
3318	auto &MIB = BC.MIB;
3319	MCContext *Ctx = BC.Ctx.get();
3320
3321	for (BinaryBasicBlock *BB : BasicBlocks) {
3322	const MCSymbol *TBB = nullptr;
3323	const MCSymbol *FBB = nullptr;
3324	MCInst *CondBranch = nullptr;
3325	MCInst *UncondBranch = nullptr;
3326	if (!BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch))
3327	continue;
3328
3329	// We will create unconditional branch with correct destination if needed.
3330	if (UncondBranch)
3331	BB->eraseInstruction(II: BB->findInstruction(Inst: UncondBranch));
3332
3333	// Basic block that follows the current one in the final layout.
3334	const BinaryBasicBlock *const NextBB =
3335	Layout.getBasicBlockAfter(BB, /*IgnoreSplits=*/false);
3336
3337	if (BB->succ_size() == 1) {
3338	// __builtin_unreachable() could create a conditional branch that
3339	// falls-through into the next function - hence the block will have only
3340	// one valid successor. Since behaviour is undefined - we replace
3341	// the conditional branch with an unconditional if required.
3342	if (CondBranch)
3343	BB->eraseInstruction(II: BB->findInstruction(Inst: CondBranch));
3344	if (BB->getSuccessor() == NextBB)
3345	continue;
3346	BB->addBranchInstruction(Successor: BB->getSuccessor());
3347	} else if (BB->succ_size() == 2) {
3348	assert(CondBranch && "conditional branch expected");
3349	const BinaryBasicBlock *TSuccessor = BB->getConditionalSuccessor(Condition: true);
3350	const BinaryBasicBlock *FSuccessor = BB->getConditionalSuccessor(Condition: false);
3351
3352	// Eliminate unnecessary conditional branch.
3353	if (TSuccessor == FSuccessor) {
3354	// FIXME: at the moment, we cannot safely remove static key branches.
3355	if (MIB->isDynamicBranch(Inst: *CondBranch)) {
3356	if (opts::Verbosity) {
3357	BC.outs()
3358	<< "BOLT-INFO: unable to remove redundant dynamic branch in "
3359	<< *this << '\n';
3360	}
3361	continue;
3362	}
3363
3364	BB->removeDuplicateConditionalSuccessor(CondBranch);
3365	if (TSuccessor != NextBB)
3366	BB->addBranchInstruction(Successor: TSuccessor);
3367	continue;
3368	}
3369
3370	// Reverse branch condition and swap successors.
3371	auto swapSuccessors = [&]() {
3372	if (MIB->isUnsupportedBranch(Inst: *CondBranch)) {
3373	if (opts::Verbosity) {
3374	BC.outs() << "BOLT-INFO: unable to swap successors in " << *this
3375	<< '\n';
3376	}
3377	return false;
3378	}
3379	std::swap(a&: TSuccessor, b&: FSuccessor);
3380	BB->swapConditionalSuccessors();
3381	auto L = BC.scopeLock();
3382	MIB->reverseBranchCondition(Inst&: *CondBranch, TBB: TSuccessor->getLabel(), Ctx);
3383	return true;
3384	};
3385
3386	// Check whether the next block is a "taken" target and try to swap it
3387	// with a "fall-through" target.
3388	if (TSuccessor == NextBB && swapSuccessors())
3389	continue;
3390
3391	// Update conditional branch destination if needed.
3392	if (MIB->getTargetSymbol(Inst: *CondBranch) != TSuccessor->getLabel()) {
3393	auto L = BC.scopeLock();
3394	MIB->replaceBranchTarget(Inst&: *CondBranch, TBB: TSuccessor->getLabel(), Ctx);
3395	}
3396
3397	// No need for the unconditional branch.
3398	if (FSuccessor == NextBB)
3399	continue;
3400
3401	if (BC.isX86()) {
3402	// We are going to generate two branches. Check if their targets are in
3403	// the same fragment as this block. If only one target is in the same
3404	// fragment, make it the destination of the conditional branch. There
3405	// is a chance it will be a short branch which takes 4 bytes fewer than
3406	// a long conditional branch. For unconditional branch, the difference
3407	// is 3 bytes.
3408	if (BB->getFragmentNum() != TSuccessor->getFragmentNum() &&
3409	BB->getFragmentNum() == FSuccessor->getFragmentNum())
3410	swapSuccessors();
3411	}
3412
3413	BB->addBranchInstruction(Successor: FSuccessor);
3414	}
3415	// Cases where the number of successors is 0 (block ends with a
3416	// terminator) or more than 2 (switch table) don't require branch
3417	// instruction adjustments.
3418	}
3419	assert((!isSimple() || validateCFG()) &&
3420	"Invalid CFG detected after fixing branches");
3421	}
3422
3423	void BinaryFunction::propagateGnuArgsSizeInfo(
3424	MCPlusBuilder::AllocatorIdTy AllocId) {
3425	assert(CurrentState == State::Disassembled && "unexpected function state");
3426
3427	if (!hasEHRanges() || !usesGnuArgsSize())
3428	return;
3429
3430	// The current value of DW_CFA_GNU_args_size affects all following
3431	// invoke instructions until the next CFI overrides it.
3432	// It is important to iterate basic blocks in the original order when
3433	// assigning the value.
3434	uint64_t CurrentGnuArgsSize = 0;
3435	for (BinaryBasicBlock *BB : BasicBlocks) {
3436	for (auto II = BB->begin(); II != BB->end();) {
3437	MCInst &Instr = *II;
3438	if (BC.MIB->isCFI(Inst: Instr)) {
3439	const MCCFIInstruction *CFI = getCFIFor(Instr);
3440	if (CFI->getOperation() == MCCFIInstruction::OpGnuArgsSize) {
3441	CurrentGnuArgsSize = CFI->getOffset();
3442	// Delete DW_CFA_GNU_args_size instructions and only regenerate
3443	// during the final code emission. The information is embedded
3444	// inside call instructions.
3445	II = BB->erasePseudoInstruction(II);
3446	continue;
3447	}
3448	} else if (BC.MIB->isInvoke(Inst: Instr)) {
3449	// Add the value of GNU_args_size as an extra operand to invokes.
3450	BC.MIB->addGnuArgsSize(Inst&: Instr, GnuArgsSize: CurrentGnuArgsSize);
3451	}
3452	++II;
3453	}
3454	}
3455	}
3456
3457	void BinaryFunction::postProcessBranches() {
3458	if (!isSimple())
3459	return;
3460	for (BinaryBasicBlock &BB : blocks()) {
3461	auto LastInstrRI = BB.getLastNonPseudo();
3462	if (BB.succ_size() == 1) {
3463	if (LastInstrRI != BB.rend() &&
3464	BC.MIB->isConditionalBranch(Inst: *LastInstrRI)) {
3465	// __builtin_unreachable() could create a conditional branch that
3466	// falls-through into the next function - hence the block will have only
3467	// one valid successor. Such behaviour is undefined and thus we remove
3468	// the conditional branch while leaving a valid successor.
3469	BB.eraseInstruction(II: std::prev(x: LastInstrRI.base()));
3470	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: erasing conditional branch in "
3471	<< BB.getName() << " in function " << *this << '\n');
3472	}
3473	} else if (BB.succ_size() == 0) {
3474	// Ignore unreachable basic blocks.
3475	if (BB.pred_size() == 0 || BB.isLandingPad())
3476	continue;
3477
3478	// If it's the basic block that does not end up with a terminator - we
3479	// insert a return instruction unless it's a call instruction.
3480	if (LastInstrRI == BB.rend()) {
3481	LLVM_DEBUG(
3482	dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "
3483	<< BB.getName() << " in function " << *this << '\n');
3484	continue;
3485	}
3486	if (!BC.MIB->isTerminator(Inst: *LastInstrRI) &&
3487	!BC.MIB->isCall(Inst: *LastInstrRI)) {
3488	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: adding return to basic block "
3489	<< BB.getName() << " in function " << *this << '\n');
3490	MCInst ReturnInstr;
3491	BC.MIB->createReturn(Inst&: ReturnInstr);
3492	BB.addInstruction(Inst: ReturnInstr);
3493	}
3494	}
3495	}
3496	assert(validateCFG() && "invalid CFG");
3497	}
3498
3499	MCSymbol *BinaryFunction::addEntryPointAtOffset(uint64_t Offset) {
3500	assert(Offset && "cannot add primary entry point");
3501	assert(CurrentState == State::Empty || CurrentState == State::Disassembled);
3502
3503	const uint64_t EntryPointAddress = getAddress() + Offset;
3504	MCSymbol *LocalSymbol = getOrCreateLocalLabel(Address: EntryPointAddress);
3505
3506	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BBLabel: LocalSymbol);
3507	if (EntrySymbol)
3508	return EntrySymbol;
3509
3510	if (BinaryData *EntryBD = BC.getBinaryDataAtAddress(Address: EntryPointAddress)) {
3511	EntrySymbol = EntryBD->getSymbol();
3512	} else {
3513	EntrySymbol = BC.getOrCreateGlobalSymbol(
3514	Address: EntryPointAddress, Prefix: Twine("__ENTRY_") + getOneName() + "@");
3515	}
3516	SecondaryEntryPoints[LocalSymbol] = EntrySymbol;
3517
3518	BC.setSymbolToFunctionMap(Sym: EntrySymbol, BF: this);
3519
3520	return EntrySymbol;
3521	}
3522
3523	MCSymbol *BinaryFunction::addEntryPoint(const BinaryBasicBlock &BB) {
3524	assert(CurrentState == State::CFG &&
3525	"basic block can be added as an entry only in a function with CFG");
3526
3527	if (&BB == BasicBlocks.front())
3528	return getSymbol();
3529
3530	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB);
3531	if (EntrySymbol)
3532	return EntrySymbol;
3533
3534	EntrySymbol =
3535	BC.Ctx->getOrCreateSymbol(Name: "__ENTRY_" + BB.getLabel()->getName());
3536
3537	SecondaryEntryPoints[BB.getLabel()] = EntrySymbol;
3538
3539	BC.setSymbolToFunctionMap(Sym: EntrySymbol, BF: this);
3540
3541	return EntrySymbol;
3542	}
3543
3544	MCSymbol *BinaryFunction::getSymbolForEntryID(uint64_t EntryID) {
3545	if (EntryID == 0)
3546	return getSymbol();
3547
3548	if (!isMultiEntry())
3549	return nullptr;
3550
3551	uint64_t NumEntries = 1;
3552	if (hasCFG()) {
3553	for (BinaryBasicBlock *BB : BasicBlocks) {
3554	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB: *BB);
3555	if (!EntrySymbol)
3556	continue;
3557	if (NumEntries == EntryID)
3558	return EntrySymbol;
3559	++NumEntries;
3560	}
3561	} else {
3562	for (std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
3563	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BBLabel: KV.second);
3564	if (!EntrySymbol)
3565	continue;
3566	if (NumEntries == EntryID)
3567	return EntrySymbol;
3568	++NumEntries;
3569	}
3570	}
3571
3572	return nullptr;
3573	}
3574
3575	uint64_t BinaryFunction::getEntryIDForSymbol(const MCSymbol *Symbol) const {
3576	if (!isMultiEntry())
3577	return 0;
3578
3579	for (const MCSymbol *FunctionSymbol : getSymbols())
3580	if (FunctionSymbol == Symbol)
3581	return 0;
3582
3583	// Check all secondary entries available as either basic blocks or lables.
3584	uint64_t NumEntries = 1;
3585	for (const BinaryBasicBlock *BB : BasicBlocks) {
3586	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB: *BB);
3587	if (!EntrySymbol)
3588	continue;
3589	if (EntrySymbol == Symbol)
3590	return NumEntries;
3591	++NumEntries;
3592	}
3593	NumEntries = 1;
3594	for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
3595	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BBLabel: KV.second);
3596	if (!EntrySymbol)
3597	continue;
3598	if (EntrySymbol == Symbol)
3599	return NumEntries;
3600	++NumEntries;
3601	}
3602
3603	llvm_unreachable("symbol not found");
3604	}
3605
3606	bool BinaryFunction::forEachEntryPoint(EntryPointCallbackTy Callback) const {
3607	bool Status = Callback(0, getSymbol());
3608	if (!isMultiEntry())
3609	return Status;
3610
3611	for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
3612	if (!Status)
3613	break;
3614
3615	MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BBLabel: KV.second);
3616	if (!EntrySymbol)
3617	continue;
3618
3619	Status = Callback(KV.first, EntrySymbol);
3620	}
3621
3622	return Status;
3623	}
3624
3625	BinaryFunction::BasicBlockListType BinaryFunction::dfs() const {
3626	BasicBlockListType DFS;
3627	unsigned Index = 0;
3628	std::stack<BinaryBasicBlock *> Stack;
3629
3630	// Push entry points to the stack in reverse order.
3631	//
3632	// NB: we rely on the original order of entries to match.
3633	SmallVector<BinaryBasicBlock *> EntryPoints;
3634	llvm::copy_if(Range: BasicBlocks, Out: std::back_inserter(x&: EntryPoints),
3635	P: [&](const BinaryBasicBlock *const BB) { return isEntryPoint(BB: *BB); });
3636	// Sort entry points by their offset to make sure we got them in the right
3637	// order.
3638	llvm::stable_sort(Range&: EntryPoints, C: [](const BinaryBasicBlock *const A,
3639	const BinaryBasicBlock *const B) {
3640	return A->getOffset() < B->getOffset();
3641	});
3642	for (BinaryBasicBlock *const BB : reverse(C&: EntryPoints))
3643	Stack.push(x: BB);
3644
3645	for (BinaryBasicBlock &BB : blocks())
3646	BB.setLayoutIndex(BinaryBasicBlock::InvalidIndex);
3647
3648	while (!Stack.empty()) {
3649	BinaryBasicBlock *BB = Stack.top();
3650	Stack.pop();
3651
3652	if (BB->getLayoutIndex() != BinaryBasicBlock::InvalidIndex)
3653	continue;
3654
3655	BB->setLayoutIndex(Index++);
3656	DFS.push_back(Elt: BB);
3657
3658	for (BinaryBasicBlock *SuccBB : BB->landing_pads()) {
3659	Stack.push(x: SuccBB);
3660	}
3661
3662	const MCSymbol *TBB = nullptr;
3663	const MCSymbol *FBB = nullptr;
3664	MCInst *CondBranch = nullptr;
3665	MCInst *UncondBranch = nullptr;
3666	if (BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch) && CondBranch &&
3667	BB->succ_size() == 2) {
3668	if (BC.MIB->getCanonicalBranchCondCode(CC: BC.MIB->getCondCode(
3669	Inst: *CondBranch)) == BC.MIB->getCondCode(Inst: *CondBranch)) {
3670	Stack.push(x: BB->getConditionalSuccessor(Condition: true));
3671	Stack.push(x: BB->getConditionalSuccessor(Condition: false));
3672	} else {
3673	Stack.push(x: BB->getConditionalSuccessor(Condition: false));
3674	Stack.push(x: BB->getConditionalSuccessor(Condition: true));
3675	}
3676	} else {
3677	for (BinaryBasicBlock *SuccBB : BB->successors()) {
3678	Stack.push(x: SuccBB);
3679	}
3680	}
3681	}
3682
3683	return DFS;
3684	}
3685
3686	size_t BinaryFunction::computeHash(bool UseDFS, HashFunction HashFunction,
3687	OperandHashFuncTy OperandHashFunc) const {
3688	if (size() == 0)
3689	return 0;
3690
3691	assert(hasCFG() && "function is expected to have CFG");
3692
3693	SmallVector<const BinaryBasicBlock *, 0> Order;
3694	if (UseDFS)
3695	llvm::copy(Range: dfs(), Out: std::back_inserter(x&: Order));
3696	else
3697	llvm::copy(Range: Layout.blocks(), Out: std::back_inserter(x&: Order));
3698
3699	// The hash is computed by creating a string of all instruction opcodes and
3700	// possibly their operands and then hashing that string with std::hash.
3701	std::string HashString;
3702	for (const BinaryBasicBlock *BB : Order)
3703	HashString.append(str: hashBlock(BC, BB: *BB, OperandHashFunc));
3704
3705	switch (HashFunction) {
3706	case HashFunction::StdHash:
3707	return Hash = std::hash<std::string>{}(HashString);
3708	case HashFunction::XXH3:
3709	return Hash = llvm::xxh3_64bits(data: HashString);
3710	}
3711	llvm_unreachable("Unhandled HashFunction");
3712	}
3713
3714	void BinaryFunction::insertBasicBlocks(
3715	BinaryBasicBlock *Start,
3716	std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs,
3717	const bool UpdateLayout, const bool UpdateCFIState,
3718	const bool RecomputeLandingPads) {
3719	const int64_t StartIndex = Start ? getIndex(BB: Start) : -1LL;
3720	const size_t NumNewBlocks = NewBBs.size();
3721
3722	BasicBlocks.insert(I: BasicBlocks.begin() + (StartIndex + 1), NumToInsert: NumNewBlocks,
3723	Elt: nullptr);
3724
3725	int64_t I = StartIndex + 1;
3726	for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) {
3727	assert(!BasicBlocks[I]);
3728	BasicBlocks[I++] = BB.release();
3729	}
3730
3731	if (RecomputeLandingPads)
3732	recomputeLandingPads();
3733	else
3734	updateBBIndices(StartIndex: 0);
3735
3736	if (UpdateLayout)
3737	updateLayout(Start, NumNewBlocks);
3738
3739	if (UpdateCFIState)
3740	updateCFIState(Start, NumNewBlocks);
3741	}
3742
3743	BinaryFunction::iterator BinaryFunction::insertBasicBlocks(
3744	BinaryFunction::iterator StartBB,
3745	std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs,
3746	const bool UpdateLayout, const bool UpdateCFIState,
3747	const bool RecomputeLandingPads) {
3748	const unsigned StartIndex = getIndex(BB: &*StartBB);
3749	const size_t NumNewBlocks = NewBBs.size();
3750
3751	BasicBlocks.insert(I: BasicBlocks.begin() + StartIndex + 1, NumToInsert: NumNewBlocks,
3752	Elt: nullptr);
3753	auto RetIter = BasicBlocks.begin() + StartIndex + 1;
3754
3755	unsigned I = StartIndex + 1;
3756	for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) {
3757	assert(!BasicBlocks[I]);
3758	BasicBlocks[I++] = BB.release();
3759	}
3760
3761	if (RecomputeLandingPads)
3762	recomputeLandingPads();
3763	else
3764	updateBBIndices(StartIndex: 0);
3765
3766	if (UpdateLayout)
3767	updateLayout(Start: *std::prev(x: RetIter), NumNewBlocks);
3768
3769	if (UpdateCFIState)
3770	updateCFIState(Start: *std::prev(x: RetIter), NumNewBlocks);
3771
3772	return RetIter;
3773	}
3774
3775	void BinaryFunction::updateBBIndices(const unsigned StartIndex) {
3776	for (unsigned I = StartIndex; I < BasicBlocks.size(); ++I)
3777	BasicBlocks[I]->Index = I;
3778	}
3779
3780	void BinaryFunction::updateCFIState(BinaryBasicBlock *Start,
3781	const unsigned NumNewBlocks) {
3782	const int32_t CFIState = Start->getCFIStateAtExit();
3783	const unsigned StartIndex = getIndex(BB: Start) + 1;
3784	for (unsigned I = 0; I < NumNewBlocks; ++I)
3785	BasicBlocks[StartIndex + I]->setCFIState(CFIState);
3786	}
3787
3788	void BinaryFunction::updateLayout(BinaryBasicBlock *Start,
3789	const unsigned NumNewBlocks) {
3790	BasicBlockListType::iterator Begin;
3791	BasicBlockListType::iterator End;
3792
3793	// If start not provided copy new blocks from the beginning of BasicBlocks
3794	if (!Start) {
3795	Begin = BasicBlocks.begin();
3796	End = BasicBlocks.begin() + NumNewBlocks;
3797	} else {
3798	unsigned StartIndex = getIndex(BB: Start);
3799	Begin = std::next(x: BasicBlocks.begin(), n: StartIndex + 1);
3800	End = std::next(x: BasicBlocks.begin(), n: StartIndex + NumNewBlocks + 1);
3801	}
3802
3803	// Insert new blocks in the layout immediately after Start.
3804	Layout.insertBasicBlocks(InsertAfter: Start, NewBlocks: {Begin, End});
3805	Layout.updateLayoutIndices();
3806	}
3807
3808	bool BinaryFunction::checkForAmbiguousJumpTables() {
3809	SmallSet<uint64_t, 4> JumpTables;
3810	for (BinaryBasicBlock *&BB : BasicBlocks) {
3811	for (MCInst &Inst : *BB) {
3812	if (!BC.MIB->isIndirectBranch(Inst))
3813	continue;
3814	uint64_t JTAddress = BC.MIB->getJumpTable(Inst);
3815	if (!JTAddress)
3816	continue;
3817	// This address can be inside another jump table, but we only consider
3818	// it ambiguous when the same start address is used, not the same JT
3819	// object.
3820	if (!JumpTables.count(V: JTAddress)) {
3821	JumpTables.insert(V: JTAddress);
3822	continue;
3823	}
3824	return true;
3825	}
3826	}
3827	return false;
3828	}
3829
3830	void BinaryFunction::disambiguateJumpTables(
3831	MCPlusBuilder::AllocatorIdTy AllocId) {
3832	assert((opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations);
3833	SmallPtrSet<JumpTable *, 4> JumpTables;
3834	for (BinaryBasicBlock *&BB : BasicBlocks) {
3835	for (MCInst &Inst : *BB) {
3836	if (!BC.MIB->isIndirectBranch(Inst))
3837	continue;
3838	JumpTable *JT = getJumpTable(Inst);
3839	if (!JT)
3840	continue;
3841	auto Iter = JumpTables.find(Ptr: JT);
3842	if (Iter == JumpTables.end()) {
3843	JumpTables.insert(Ptr: JT);
3844	continue;
3845	}
3846	// This instruction is an indirect jump using a jump table, but it is
3847	// using the same jump table of another jump. Try all our tricks to
3848	// extract the jump table symbol and make it point to a new, duplicated JT
3849	MCPhysReg BaseReg1;
3850	uint64_t Scale;
3851	const MCSymbol *Target;
3852	// In case we match if our first matcher, first instruction is the one to
3853	// patch
3854	MCInst *JTLoadInst = &Inst;
3855	// Try a standard indirect jump matcher, scale 8
3856	std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher =
3857	BC.MIB->matchIndJmp(Base: BC.MIB->matchReg(Reg&: BaseReg1),
3858	Scale: BC.MIB->matchImm(Imm&: Scale), Index: BC.MIB->matchReg(),
3859	/*Offset=*/BC.MIB->matchSymbol(Sym&: Target));
3860	if (!IndJmpMatcher->match(
3861	MRI: *BC.MRI, MIA&: *BC.MIB,
3862	InInstrWindow: MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), OpNum: -1) ||
3863	BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) {
3864	MCPhysReg BaseReg2;
3865	uint64_t Offset;
3866	// Standard JT matching failed. Trying now:
3867	// movq "jt.2397/1"(,%rax,8), %rax
3868	// jmpq *%rax
3869	std::unique_ptr<MCPlusBuilder::MCInstMatcher> LoadMatcherOwner =
3870	BC.MIB->matchLoad(Base: BC.MIB->matchReg(Reg&: BaseReg1),
3871	Scale: BC.MIB->matchImm(Imm&: Scale), Index: BC.MIB->matchReg(),
3872	/*Offset=*/BC.MIB->matchSymbol(Sym&: Target));
3873	MCPlusBuilder::MCInstMatcher *LoadMatcher = LoadMatcherOwner.get();
3874	std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher2 =
3875	BC.MIB->matchIndJmp(Target: std::move(LoadMatcherOwner));
3876	if (!IndJmpMatcher2->match(
3877	MRI: *BC.MRI, MIA&: *BC.MIB,
3878	InInstrWindow: MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), OpNum: -1) ||
3879	BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) {
3880	// JT matching failed. Trying now:
3881	// PIC-style matcher, scale 4
3882	// addq %rdx, %rsi
3883	// addq %rdx, %rdi
3884	// leaq DATAat0x402450(%rip), %r11
3885	// movslq (%r11,%rdx,4), %rcx
3886	// addq %r11, %rcx
3887	// jmpq *%rcx # JUMPTABLE @0x402450
3888	std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICIndJmpMatcher =
3889	BC.MIB->matchIndJmp(Target: BC.MIB->matchAdd(
3890	A: BC.MIB->matchReg(Reg&: BaseReg1),
3891	B: BC.MIB->matchLoad(Base: BC.MIB->matchReg(Reg&: BaseReg2),
3892	Scale: BC.MIB->matchImm(Imm&: Scale), Index: BC.MIB->matchReg(),
3893	Offset: BC.MIB->matchImm(Imm&: Offset))));
3894	std::unique_ptr<MCPlusBuilder::MCInstMatcher> LEAMatcherOwner =
3895	BC.MIB->matchLoadAddr(Target: BC.MIB->matchSymbol(Sym&: Target));
3896	MCPlusBuilder::MCInstMatcher *LEAMatcher = LEAMatcherOwner.get();
3897	std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICBaseAddrMatcher =
3898	BC.MIB->matchIndJmp(Target: BC.MIB->matchAdd(A: std::move(LEAMatcherOwner),
3899	B: BC.MIB->matchAnyOperand()));
3900	if (!PICIndJmpMatcher->match(
3901	MRI: *BC.MRI, MIA&: *BC.MIB,
3902	InInstrWindow: MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), OpNum: -1) ||
3903	Scale != 4 || BaseReg1 != BaseReg2 || Offset != 0 ||
3904	!PICBaseAddrMatcher->match(
3905	MRI: *BC.MRI, MIA&: *BC.MIB,
3906	InInstrWindow: MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), OpNum: -1)) {
3907	llvm_unreachable("Failed to extract jump table base");
3908	continue;
3909	}
3910	// Matched PIC, identify the instruction with the reference to the JT
3911	JTLoadInst = LEAMatcher->CurInst;
3912	} else {
3913	// Matched non-PIC
3914	JTLoadInst = LoadMatcher->CurInst;
3915	}
3916	}
3917
3918	uint64_t NewJumpTableID = 0;
3919	const MCSymbol *NewJTLabel;
3920	std::tie(args&: NewJumpTableID, args&: NewJTLabel) =
3921	BC.duplicateJumpTable(Function&: *this, JT, OldLabel: Target);
3922	{
3923	auto L = BC.scopeLock();
3924	BC.MIB->replaceMemOperandDisp(Inst&: *JTLoadInst, Label: NewJTLabel, Ctx: BC.Ctx.get());
3925	}
3926	// We use a unique ID with the high bit set as address for this "injected"
3927	// jump table (not originally in the input binary).
3928	BC.MIB->setJumpTable(Inst, Value: NewJumpTableID, IndexReg: 0, AllocId);
3929	}
3930	}
3931	}
3932
3933	bool BinaryFunction::replaceJumpTableEntryIn(BinaryBasicBlock *BB,
3934	BinaryBasicBlock *OldDest,
3935	BinaryBasicBlock *NewDest) {
3936	MCInst *Instr = BB->getLastNonPseudoInstr();
3937	if (!Instr || !BC.MIB->isIndirectBranch(Inst: *Instr))
3938	return false;
3939	uint64_t JTAddress = BC.MIB->getJumpTable(Inst: *Instr);
3940	assert(JTAddress && "Invalid jump table address");
3941	JumpTable *JT = getJumpTableContainingAddress(Address: JTAddress);
3942	assert(JT && "No jump table structure for this indirect branch");
3943	bool Patched = JT->replaceDestination(JTAddress, OldDest: OldDest->getLabel(),
3944	NewDest: NewDest->getLabel());
3945	(void)Patched;
3946	assert(Patched && "Invalid entry to be replaced in jump table");
3947	return true;
3948	}
3949
3950	BinaryBasicBlock *BinaryFunction::splitEdge(BinaryBasicBlock *From,
3951	BinaryBasicBlock *To) {
3952	// Create intermediate BB
3953	MCSymbol *Tmp;
3954	{
3955	auto L = BC.scopeLock();
3956	Tmp = BC.Ctx->createNamedTempSymbol(Name: "SplitEdge");
3957	}
3958	// Link new BBs to the original input offset of the From BB, so we can map
3959	// samples recorded in new BBs back to the original BB seem in the input
3960	// binary (if using BAT)
3961	std::unique_ptr<BinaryBasicBlock> NewBB = createBasicBlock(Label: Tmp);
3962	NewBB->setOffset(From->getInputOffset());
3963	BinaryBasicBlock *NewBBPtr = NewBB.get();
3964
3965	// Update "From" BB
3966	auto I = From->succ_begin();
3967	auto BI = From->branch_info_begin();
3968	for (; I != From->succ_end(); ++I) {
3969	if (*I == To)
3970	break;
3971	++BI;
3972	}
3973	assert(I != From->succ_end() && "Invalid CFG edge in splitEdge!");
3974	uint64_t OrigCount = BI->Count;
3975	uint64_t OrigMispreds = BI->MispredictedCount;
3976	replaceJumpTableEntryIn(BB: From, OldDest: To, NewDest: NewBBPtr);
3977	From->replaceSuccessor(Succ: To, NewSucc: NewBBPtr, Count: OrigCount, MispredictedCount: OrigMispreds);
3978
3979	NewBB->addSuccessor(Succ: To, Count: OrigCount, MispredictedCount: OrigMispreds);
3980	NewBB->setExecutionCount(OrigCount);
3981	NewBB->setIsCold(From->isCold());
3982
3983	// Update CFI and BB layout with new intermediate BB
3984	std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;
3985	NewBBs.emplace_back(args: std::move(NewBB));
3986	insertBasicBlocks(Start: From, NewBBs: std::move(NewBBs), UpdateLayout: true, UpdateCFIState: true,
3987	/*RecomputeLandingPads=*/false);
3988	return NewBBPtr;
3989	}
3990
3991	void BinaryFunction::deleteConservativeEdges() {
3992	// Our goal is to aggressively remove edges from the CFG that we believe are
3993	// wrong. This is used for instrumentation, where it is safe to remove
3994	// fallthrough edges because we won't reorder blocks.
3995	for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
3996	BinaryBasicBlock *BB = *I;
3997	if (BB->succ_size() != 1 || BB->size() == 0)
3998	continue;
3999
4000	auto NextBB = std::next(x: I);
4001	MCInst *Last = BB->getLastNonPseudoInstr();
4002	// Fallthrough is a landing pad? Delete this edge (as long as we don't
4003	// have a direct jump to it)
4004	if ((*BB->succ_begin())->isLandingPad() && NextBB != E &&
4005	*BB->succ_begin() == *NextBB && Last && !BC.MIB->isBranch(Inst: *Last)) {
4006	BB->removeAllSuccessors();
4007	continue;
4008	}
4009
4010	// Look for suspicious calls at the end of BB where gcc may optimize it and
4011	// remove the jump to the epilogue when it knows the call won't return.
4012	if (!Last || !BC.MIB->isCall(Inst: *Last))
4013	continue;
4014
4015	const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(Inst: *Last);
4016	if (!CalleeSymbol)
4017	continue;
4018
4019	StringRef CalleeName = CalleeSymbol->getName();
4020	if (CalleeName != "__cxa_throw@PLT" && CalleeName != "_Unwind_Resume@PLT" &&
4021	CalleeName != "__cxa_rethrow@PLT" && CalleeName != "exit@PLT" &&
4022	CalleeName != "abort@PLT")
4023	continue;
4024
4025	BB->removeAllSuccessors();
4026	}
4027	}
4028
4029	bool BinaryFunction::isSymbolValidInScope(const SymbolRef &Symbol,
4030	uint64_t SymbolSize) const {
4031	// If this symbol is in a different section from the one where the
4032	// function symbol is, don't consider it as valid.
4033	if (!getOriginSection()->containsAddress(
4034	Address: cantFail(ValOrErr: Symbol.getAddress(), Msg: "cannot get symbol address")))
4035	return false;
4036
4037	// Some symbols are tolerated inside function bodies, others are not.
4038	// The real function boundaries may not be known at this point.
4039	if (BC.isMarker(Symbol))
4040	return true;
4041
4042	// It's okay to have a zero-sized symbol in the middle of non-zero-sized
4043	// function.
4044	if (SymbolSize == 0 && containsAddress(PC: cantFail(ValOrErr: Symbol.getAddress())))
4045	return true;
4046
4047	if (cantFail(ValOrErr: Symbol.getType()) != SymbolRef::ST_Unknown)
4048	return false;
4049
4050	if (cantFail(ValOrErr: Symbol.getFlags()) & SymbolRef::SF_Global)
4051	return false;
4052
4053	return true;
4054	}
4055
4056	void BinaryFunction::adjustExecutionCount(uint64_t Count) {
4057	if (getKnownExecutionCount() == 0 || Count == 0)
4058	return;
4059
4060	if (ExecutionCount < Count)
4061	Count = ExecutionCount;
4062
4063	double AdjustmentRatio = ((double)ExecutionCount - Count) / ExecutionCount;
4064	if (AdjustmentRatio < 0.0)
4065	AdjustmentRatio = 0.0;
4066
4067	for (BinaryBasicBlock &BB : blocks())
4068	BB.adjustExecutionCount(Ratio: AdjustmentRatio);
4069
4070	ExecutionCount -= Count;
4071	}
4072
4073	BinaryFunction::~BinaryFunction() {
4074	for (BinaryBasicBlock *BB : BasicBlocks)
4075	delete BB;
4076	for (BinaryBasicBlock *BB : DeletedBasicBlocks)
4077	delete BB;
4078	}
4079
4080	void BinaryFunction::constructDomTree() {
4081	BDT.reset(p: new BinaryDominatorTree);
4082	BDT->recalculate(Func&: *this);
4083	}
4084
4085	void BinaryFunction::calculateLoopInfo() {
4086	if (!hasDomTree())
4087	constructDomTree();
4088	// Discover loops.
4089	BLI.reset(p: new BinaryLoopInfo());
4090	BLI->analyze(DomTree: getDomTree());
4091
4092	// Traverse discovered loops and add depth and profile information.
4093	std::stack<BinaryLoop *> St;
4094	for (auto I = BLI->begin(), E = BLI->end(); I != E; ++I) {
4095	St.push(x: *I);
4096	++BLI->OuterLoops;
4097	}
4098
4099	while (!St.empty()) {
4100	BinaryLoop *L = St.top();
4101	St.pop();
4102	++BLI->TotalLoops;
4103	BLI->MaximumDepth = std::max(a: L->getLoopDepth(), b: BLI->MaximumDepth);
4104
4105	// Add nested loops in the stack.
4106	for (BinaryLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
4107	St.push(x: *I);
4108
4109	// Skip if no valid profile is found.
4110	if (!hasValidProfile()) {
4111	L->EntryCount = COUNT_NO_PROFILE;
4112	L->ExitCount = COUNT_NO_PROFILE;
4113	L->TotalBackEdgeCount = COUNT_NO_PROFILE;
4114	continue;
4115	}
4116
4117	// Compute back edge count.
4118	SmallVector<BinaryBasicBlock *, 1> Latches;
4119	L->getLoopLatches(LoopLatches&: Latches);
4120
4121	for (BinaryBasicBlock *Latch : Latches) {
4122	auto BI = Latch->branch_info_begin();
4123	for (BinaryBasicBlock *Succ : Latch->successors()) {
4124	if (Succ == L->getHeader()) {
4125	assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
4126	"profile data not found");
4127	L->TotalBackEdgeCount += BI->Count;
4128	}
4129	++BI;
4130	}
4131	}
4132
4133	// Compute entry count.
4134	L->EntryCount = L->getHeader()->getExecutionCount() - L->TotalBackEdgeCount;
4135
4136	// Compute exit count.
4137	SmallVector<BinaryLoop::Edge, 1> ExitEdges;
4138	L->getExitEdges(ExitEdges);
4139	for (BinaryLoop::Edge &Exit : ExitEdges) {
4140	const BinaryBasicBlock *Exiting = Exit.first;
4141	const BinaryBasicBlock *ExitTarget = Exit.second;
4142	auto BI = Exiting->branch_info_begin();
4143	for (BinaryBasicBlock *Succ : Exiting->successors()) {
4144	if (Succ == ExitTarget) {
4145	assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
4146	"profile data not found");
4147	L->ExitCount += BI->Count;
4148	}
4149	++BI;
4150	}
4151	}
4152	}
4153	}
4154
4155	void BinaryFunction::updateOutputValues(const BOLTLinker &Linker) {
4156	if (!isEmitted()) {
4157	assert(!isInjected() && "injected function should be emitted");
4158	setOutputAddress(getAddress());
4159	setOutputSize(getSize());
4160	return;
4161	}
4162
4163	const auto SymbolInfo = Linker.lookupSymbolInfo(Name: getSymbol()->getName());
4164	assert(SymbolInfo && "Cannot find function entry symbol");
4165	setOutputAddress(SymbolInfo->Address);
4166	setOutputSize(SymbolInfo->Size);
4167
4168	if (BC.HasRelocations || isInjected()) {
4169	if (hasConstantIsland()) {
4170	const auto DataAddress =
4171	Linker.lookupSymbol(Name: getFunctionConstantIslandLabel()->getName());
4172	assert(DataAddress && "Cannot find function CI symbol");
4173	setOutputDataAddress(*DataAddress);
4174	for (auto It : Islands->Offsets) {
4175	const uint64_t OldOffset = It.first;
4176	BinaryData *BD = BC.getBinaryDataAtAddress(Address: getAddress() + OldOffset);
4177	if (!BD)
4178	continue;
4179
4180	MCSymbol *Symbol = It.second;
4181	const auto NewAddress = Linker.lookupSymbol(Name: Symbol->getName());
4182	assert(NewAddress && "Cannot find CI symbol");
4183	auto &Section = *getCodeSection();
4184	const auto NewOffset = *NewAddress - Section.getOutputAddress();
4185	BD->setOutputLocation(NewSection&: Section, NewOffset);
4186	}
4187	}
4188	if (isSplit()) {
4189	for (FunctionFragment &FF : getLayout().getSplitFragments()) {
4190	ErrorOr<BinarySection &> ColdSection =
4191	getCodeSection(Fragment: FF.getFragmentNum());
4192	// If fragment is empty, cold section might not exist
4193	if (FF.empty() && ColdSection.getError())
4194	continue;
4195
4196	const MCSymbol *ColdStartSymbol = getSymbol(Fragment: FF.getFragmentNum());
4197	// If fragment is empty, symbol might have not been emitted
4198	if (FF.empty() && (!ColdStartSymbol || !ColdStartSymbol->isDefined()) &&
4199	!hasConstantIsland())
4200	continue;
4201	assert(ColdStartSymbol && ColdStartSymbol->isDefined() &&
4202	"split function should have defined cold symbol");
4203	const auto ColdStartSymbolInfo =
4204	Linker.lookupSymbolInfo(Name: ColdStartSymbol->getName());
4205	assert(ColdStartSymbolInfo && "Cannot find cold start symbol");
4206	FF.setAddress(ColdStartSymbolInfo->Address);
4207	FF.setImageSize(ColdStartSymbolInfo->Size);
4208	if (hasConstantIsland()) {
4209	const auto DataAddress = Linker.lookupSymbol(
4210	Name: getFunctionColdConstantIslandLabel()->getName());
4211	assert(DataAddress && "Cannot find cold CI symbol");
4212	setOutputColdDataAddress(*DataAddress);
4213	}
4214	}
4215	}
4216	}
4217
4218	// Update basic block output ranges for the debug info, if we have
4219	// secondary entry points in the symbol table to update or if writing BAT.
4220	if (!requiresAddressMap())
4221	return;
4222
4223	// AArch64 may have functions that only contains a constant island (no code).
4224	if (getLayout().block_empty())
4225	return;
4226
4227	for (FunctionFragment &FF : getLayout().fragments()) {
4228	if (FF.empty())
4229	continue;
4230
4231	const uint64_t FragmentBaseAddress =
4232	getCodeSection(Fragment: isSimple() ? FF.getFragmentNum() : FragmentNum::main())
4233	->getOutputAddress();
4234
4235	BinaryBasicBlock *PrevBB = nullptr;
4236	for (BinaryBasicBlock *const BB : FF) {
4237	assert(BB->getLabel()->isDefined() && "symbol should be defined");
4238	if (!BC.HasRelocations) {
4239	if (BB->isSplit())
4240	assert(FragmentBaseAddress == FF.getAddress());
4241	else
4242	assert(FragmentBaseAddress == getOutputAddress());
4243	(void)FragmentBaseAddress;
4244	}
4245
4246	// Injected functions likely will fail lookup, as they have no
4247	// input range. Just assign the BB the output address of the
4248	// function.
4249	auto MaybeBBAddress = BC.getIOAddressMap().lookup(Symbol: BB->getLabel());
4250	const uint64_t BBAddress = MaybeBBAddress ? *MaybeBBAddress
4251	: BB->isSplit() ? FF.getAddress()
4252	: getOutputAddress();
4253	BB->setOutputStartAddress(BBAddress);
4254
4255	if (PrevBB) {
4256	assert(PrevBB->getOutputAddressRange().first <= BBAddress &&
4257	"Bad output address for basic block.");
4258	assert((PrevBB->getOutputAddressRange().first != BBAddress ||
4259	!hasInstructions() || !PrevBB->getNumNonPseudos()) &&
4260	"Bad output address for basic block.");
4261	PrevBB->setOutputEndAddress(BBAddress);
4262	}
4263	PrevBB = BB;
4264	}
4265
4266	PrevBB->setOutputEndAddress(PrevBB->isSplit()
4267	? FF.getAddress() + FF.getImageSize()
4268	: getOutputAddress() + getOutputSize());
4269	}
4270
4271	// Reset output addresses for deleted blocks.
4272	for (BinaryBasicBlock *BB : DeletedBasicBlocks) {
4273	BB->setOutputStartAddress(0);
4274	BB->setOutputEndAddress(0);
4275	}
4276	}
4277
4278	DebugAddressRangesVector BinaryFunction::getOutputAddressRanges() const {
4279	DebugAddressRangesVector OutputRanges;
4280
4281	if (isFolded())
4282	return OutputRanges;
4283
4284	if (IsFragment)
4285	return OutputRanges;
4286
4287	OutputRanges.emplace_back(Args: getOutputAddress(),
4288	Args: getOutputAddress() + getOutputSize());
4289	if (isSplit()) {
4290	assert(isEmitted() && "split function should be emitted");
4291	for (const FunctionFragment &FF : getLayout().getSplitFragments())
4292	OutputRanges.emplace_back(Args: FF.getAddress(),
4293	Args: FF.getAddress() + FF.getImageSize());
4294	}
4295
4296	if (isSimple())
4297	return OutputRanges;
4298
4299	for (BinaryFunction *Frag : Fragments) {
4300	assert(!Frag->isSimple() &&
4301	"fragment of non-simple function should also be non-simple");
4302	OutputRanges.emplace_back(Args: Frag->getOutputAddress(),
4303	Args: Frag->getOutputAddress() + Frag->getOutputSize());
4304	}
4305
4306	return OutputRanges;
4307	}
4308
4309	uint64_t BinaryFunction::translateInputToOutputAddress(uint64_t Address) const {
4310	if (isFolded())
4311	return 0;
4312
4313	// If the function hasn't changed return the same address.
4314	if (!isEmitted())
4315	return Address;
4316
4317	if (Address < getAddress())
4318	return 0;
4319
4320	// Check if the address is associated with an instruction that is tracked
4321	// by address translation.
4322	if (auto OutputAddress = BC.getIOAddressMap().lookup(InputAddress: Address))
4323	return *OutputAddress;
4324
4325	// FIXME: #18950828 - we rely on relative offsets inside basic blocks to stay
4326	// intact. Instead we can use pseudo instructions and/or annotations.
4327	const uint64_t Offset = Address - getAddress();
4328	const BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
4329	if (!BB) {
4330	// Special case for address immediately past the end of the function.
4331	if (Offset == getSize())
4332	return getOutputAddress() + getOutputSize();
4333
4334	return 0;
4335	}
4336
4337	return std::min(a: BB->getOutputAddressRange().first + Offset - BB->getOffset(),
4338	b: BB->getOutputAddressRange().second);
4339	}
4340
4341	DebugAddressRangesVector
4342	BinaryFunction::translateInputToOutputRange(DebugAddressRange InRange) const {
4343	DebugAddressRangesVector OutRanges;
4344
4345	// The function was removed from the output. Return an empty range.
4346	if (isFolded())
4347	return OutRanges;
4348
4349	// If the function hasn't changed return the same range.
4350	if (!isEmitted()) {
4351	OutRanges.emplace_back(Args&: InRange);
4352	return OutRanges;
4353	}
4354
4355	if (!containsAddress(PC: InRange.LowPC))
4356	return OutRanges;
4357
4358	// Special case of an empty range [X, X). Some tools expect X to be updated.
4359	if (InRange.LowPC == InRange.HighPC) {
4360	if (uint64_t NewPC = translateInputToOutputAddress(Address: InRange.LowPC))
4361	OutRanges.push_back(Elt: DebugAddressRange{NewPC, NewPC});
4362	return OutRanges;
4363	}
4364
4365	uint64_t InputOffset = InRange.LowPC - getAddress();
4366	const uint64_t InputEndOffset =
4367	std::min(a: InRange.HighPC - getAddress(), b: getSize());
4368
4369	auto BBI = llvm::upper_bound(Range: BasicBlockOffsets,
4370	Value: BasicBlockOffset(InputOffset, nullptr),
4371	C: CompareBasicBlockOffsets());
4372	assert(BBI != BasicBlockOffsets.begin());
4373
4374	// Iterate over blocks in the input order using BasicBlockOffsets.
4375	for (--BBI; InputOffset < InputEndOffset && BBI != BasicBlockOffsets.end();
4376	InputOffset = BBI->second->getEndOffset(), ++BBI) {
4377	const BinaryBasicBlock &BB = *BBI->second;
4378	if (InputOffset < BB.getOffset() || InputOffset >= BB.getEndOffset()) {
4379	LLVM_DEBUG(
4380	dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
4381	<< *this << " : [0x" << Twine::utohexstr(InRange.LowPC)
4382	<< ", 0x" << Twine::utohexstr(InRange.HighPC) << "]\n");
4383	break;
4384	}
4385
4386	// Skip the block if it wasn't emitted.
4387	if (!BB.getOutputAddressRange().first)
4388	continue;
4389
4390	// Find output address for an instruction with an offset greater or equal
4391	// to /p Offset. The output address should fall within the same basic
4392	// block boundaries.
4393	auto translateBlockOffset = [&](const uint64_t Offset) {
4394	const uint64_t OutAddress = BB.getOutputAddressRange().first + Offset;
4395	return std::min(a: OutAddress, b: BB.getOutputAddressRange().second);
4396	};
4397
4398	uint64_t OutLowPC = BB.getOutputAddressRange().first;
4399	if (InputOffset > BB.getOffset())
4400	OutLowPC = translateBlockOffset(InputOffset - BB.getOffset());
4401
4402	uint64_t OutHighPC = BB.getOutputAddressRange().second;
4403	if (InputEndOffset < BB.getEndOffset()) {
4404	assert(InputEndOffset >= BB.getOffset());
4405	OutHighPC = translateBlockOffset(InputEndOffset - BB.getOffset());
4406	}
4407
4408	// Check if we can expand the last translated range.
4409	if (!OutRanges.empty() && OutRanges.back().HighPC == OutLowPC)
4410	OutRanges.back().HighPC = std::max(a: OutRanges.back().HighPC, b: OutHighPC);
4411	else
4412	OutRanges.emplace_back(Args&: OutLowPC, Args: std::max(a: OutLowPC, b: OutHighPC));
4413	}
4414
4415	LLVM_DEBUG({
4416	dbgs() << "BOLT-DEBUG: translated address range " << InRange << " -> ";
4417	for (const DebugAddressRange &R : OutRanges)
4418	dbgs() << R << ' ';
4419	dbgs() << '\n';
4420	});
4421
4422	return OutRanges;
4423	}
4424
4425	MCInst *BinaryFunction::getInstructionAtOffset(uint64_t Offset) {
4426	if (CurrentState == State::Disassembled) {
4427	auto II = Instructions.find(x: Offset);
4428	return (II == Instructions.end()) ? nullptr : &II->second;
4429	} else if (CurrentState == State::CFG) {
4430	BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
4431	if (!BB)
4432	return nullptr;
4433
4434	for (MCInst &Inst : *BB) {
4435	constexpr uint32_t InvalidOffset = std::numeric_limits<uint32_t>::max();
4436	if (Offset == BC.MIB->getOffsetWithDefault(Inst, Default: InvalidOffset))
4437	return &Inst;
4438	}
4439
4440	if (MCInst *LastInstr = BB->getLastNonPseudoInstr()) {
4441	if (std::optional<uint32_t> Size = BC.MIB->getSize(Inst: *LastInstr)) {
4442	if (BB->getEndOffset() - Offset == Size) {
4443	return LastInstr;
4444	}
4445	}
4446	}
4447
4448	return nullptr;
4449	} else {
4450	llvm_unreachable("invalid CFG state to use getInstructionAtOffset()");
4451	}
4452	}
4453
4454	void BinaryFunction::printLoopInfo(raw_ostream &OS) const {
4455	if (!opts::shouldPrint(Function: *this))
4456	return;
4457
4458	OS << "Loop Info for Function \"" << *this << "\"";
4459	if (hasValidProfile())
4460	OS << " (count: " << getExecutionCount() << ")";
4461	OS << "\n";
4462
4463	std::stack<BinaryLoop *> St;
4464	for (BinaryLoop *L : *BLI)
4465	St.push(x: L);
4466	while (!St.empty()) {
4467	BinaryLoop *L = St.top();
4468	St.pop();
4469
4470	for (BinaryLoop *Inner : *L)
4471	St.push(x: Inner);
4472
4473	if (!hasValidProfile())
4474	continue;
4475
4476	OS << (L->getLoopDepth() > 1 ? "Nested" : "Outer")
4477	<< " loop header: " << L->getHeader()->getName();
4478	OS << "\n";
4479	OS << "Loop basic blocks: ";
4480	ListSeparator LS;
4481	for (BinaryBasicBlock *BB : L->blocks())
4482	OS << LS << BB->getName();
4483	OS << "\n";
4484	if (hasValidProfile()) {
4485	OS << "Total back edge count: " << L->TotalBackEdgeCount << "\n";
4486	OS << "Loop entry count: " << L->EntryCount << "\n";
4487	OS << "Loop exit count: " << L->ExitCount << "\n";
4488	if (L->EntryCount > 0) {
4489	OS << "Average iters per entry: "
4490	<< format(Fmt: "%.4lf", Vals: (double)L->TotalBackEdgeCount / L->EntryCount)
4491	<< "\n";
4492	}
4493	}
4494	OS << "----\n";
4495	}
4496
4497	OS << "Total number of loops: " << BLI->TotalLoops << "\n";
4498	OS << "Number of outer loops: " << BLI->OuterLoops << "\n";
4499	OS << "Maximum nested loop depth: " << BLI->MaximumDepth << "\n\n";
4500	}
4501
4502	bool BinaryFunction::isAArch64Veneer() const {
4503	if (empty() || hasIslandsInfo())
4504	return false;
4505
4506	BinaryBasicBlock &BB = **BasicBlocks.begin();
4507	for (MCInst &Inst : BB)
4508	if (!BC.MIB->hasAnnotation(Inst, Name: "AArch64Veneer"))
4509	return false;
4510
4511	for (auto I = BasicBlocks.begin() + 1, E = BasicBlocks.end(); I != E; ++I) {
4512	for (MCInst &Inst : **I)
4513	if (!BC.MIB->isNoop(Inst))
4514	return false;
4515	}
4516
4517	return true;
4518	}
4519
4520	void BinaryFunction::addRelocation(uint64_t Address, MCSymbol *Symbol,
4521	uint64_t RelType, uint64_t Addend,
4522	uint64_t Value) {
4523	assert(Address >= getAddress() && Address < getAddress() + getMaxSize() &&
4524	"address is outside of the function");
4525	uint64_t Offset = Address - getAddress();
4526	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: addRelocation in "
4527	<< formatv("{0}@{1:x} against {2}\n", *this, Offset,
4528	(Symbol ? Symbol->getName() : "<undef>")));
4529	bool IsCI = BC.isAArch64() && isInConstantIsland(Address);
4530	std::map<uint64_t, Relocation> &Rels =
4531	IsCI ? Islands->Relocations : Relocations;
4532	if (BC.MIB->shouldRecordCodeRelocation(RelType))
4533	Rels[Offset] = Relocation{.Offset: Offset, .Symbol: Symbol, .Type: RelType, .Addend: Addend, .Value: Value};
4534	}
4535
4536	} // namespace bolt
4537	} // namespace llvm
4538