/build/source/bolt/lib/Passes/ShrinkWrapping.cpp

Bug Summary

File:	build/source/bolt/lib/Passes/ShrinkWrapping.cpp
Warning:	line 1113, column 9 Value stored to 'Found' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ShrinkWrapping.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/bolt/lib/Passes -I /build/source/bolt/lib/Passes -I include -I /build/source/llvm/include -I /build/source/bolt/include -I tools/bolt/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-05-10-133810-16478-1 -x c++ /build/source/bolt/lib/Passes/ShrinkWrapping.cpp

1	//===- bolt/Passes/ShrinkWrapping.cpp -------------------------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// This file implements the ShrinkWrapping class.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "bolt/Passes/ShrinkWrapping.h"
14	#include "bolt/Core/MCPlus.h"
15	#include "bolt/Passes/DataflowInfoManager.h"
16	#include "bolt/Passes/MCF.h"
17	#include "bolt/Utils/CommandLineOpts.h"
18	#include <numeric>
19	#include <optional>
20	#include <stack>
21
22	#define DEBUG_TYPE"shrinkwrapping" "shrinkwrapping"
23
24	using namespace llvm;
25
26	namespace opts {
27
28	extern cl::opt<bool> TimeOpts;
29	extern cl::OptionCategory BoltOptCategory;
30
31	static cl::opt<unsigned> ShrinkWrappingThreshold(
32	"shrink-wrapping-threshold",
33	cl::desc("Percentage of prologue execution count to use as threshold when"
34	" evaluating whether a block is cold enough to be profitable to"
35	" move eligible spills there"),
36	cl::init(30), cl::ZeroOrMore, cl::cat(BoltOptCategory));
37	} // namespace opts
38
39	namespace llvm {
40	namespace bolt {
41
42	void CalleeSavedAnalysis::analyzeSaves() {
43	ReachingDefOrUse</Def=/true> &RD = Info.getReachingDefs();
44	StackReachingUses &SRU = Info.getStackReachingUses();
45	auto &InsnToBB = Info.getInsnToBBMap();
46	BitVector BlacklistedRegs(BC.MRI->getNumRegs(), false);
47
48	LLVM_DEBUG(dbgs() << "Checking spill locations\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Checking spill locations\n" ; } } while (false);
49	for (BinaryBasicBlock &BB : BF) {
50	LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\tNow at BB " << BB.getName() << "\n"; } } while (false);
51	const MCInst *Prev = nullptr;
52	for (MCInst &Inst : BB) {
53	if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {
54	// Blacklist weird stores we don't understand
55	if ((!FIE->IsSimple \|\| FIE->StackOffset >= 0) && FIE->IsStore &&
56	FIE->IsStoreFromReg) {
57	BlacklistedRegs.set(FIE->RegOrImm);
58	CalleeSaved.reset(FIE->RegOrImm);
59	Prev = &Inst;
60	continue;
61	}
62
63	if (!FIE->IsStore \|\| !FIE->IsStoreFromReg \|\|
64	BlacklistedRegs[FIE->RegOrImm]) {
65	Prev = &Inst;
66	continue;
67	}
68
69	// If this reg is defined locally, it is not a callee-saved reg
70	if (RD.isReachedBy(FIE->RegOrImm,
71	Prev ? RD.expr_begin(*Prev) : RD.expr_begin(BB))) {
72	BlacklistedRegs.set(FIE->RegOrImm);
73	CalleeSaved.reset(FIE->RegOrImm);
74	Prev = &Inst;
75	continue;
76	}
77
78	// If this stack position is accessed in another function, we are
79	// probably dealing with a parameter passed in a stack -- do not mess
80	// with it
81	if (SRU.isStoreUsed(*FIE,
82	Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB)),
83	/IncludeLocalAccesses=/false) {
84	BlacklistedRegs.set(FIE->RegOrImm);
85	CalleeSaved.reset(FIE->RegOrImm);
86	Prev = &Inst;
87	continue;
88	}
89
90	// If this stack position is loaded elsewhere in another reg, we can't
91	// update it, so blacklist it.
92	if (SRU.isLoadedInDifferentReg(FIE, Prev ? SRU.expr_begin(Prev)
93	: SRU.expr_begin(BB))) {
94	BlacklistedRegs.set(FIE->RegOrImm);
95	CalleeSaved.reset(FIE->RegOrImm);
96	Prev = &Inst;
97	continue;
98	}
99
100	// Ignore regs with multiple saves
101	if (CalleeSaved[FIE->RegOrImm]) {
102	BlacklistedRegs.set(FIE->RegOrImm);
103	CalleeSaved.reset(FIE->RegOrImm);
104	Prev = &Inst;
105	continue;
106	}
107
108	CalleeSaved.set(FIE->RegOrImm);
109	SaveFIEByReg[FIE->RegOrImm] = &*FIE;
110	SavingCost[FIE->RegOrImm] += InsnToBB[&Inst]->getKnownExecutionCount();
111	BC.MIB->addAnnotation(Inst, getSaveTag(), FIE->RegOrImm, AllocatorId);
112	OffsetsByReg[FIE->RegOrImm] = FIE->StackOffset;
113	LLVM_DEBUG(dbgs() << "Logging new candidate for Callee-Saved Reg: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Logging new candidate for Callee-Saved Reg: " << FIE->RegOrImm << "\n"; } } while (false)
114	<< FIE->RegOrImm << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Logging new candidate for Callee-Saved Reg: " << FIE->RegOrImm << "\n"; } } while (false);
115	}
116	Prev = &Inst;
117	}
118	}
119	}
120
121	void CalleeSavedAnalysis::analyzeRestores() {
122	ReachingDefOrUse</Def=/false> &RU = Info.getReachingUses();
123
124	// Now compute all restores of these callee-saved regs
125	for (BinaryBasicBlock &BB : BF) {
126	const MCInst *Prev = nullptr;
127	for (MCInst &Inst : llvm::reverse(BB)) {
128	if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {
129	if (!FIE->IsLoad \|\| !CalleeSaved[FIE->RegOrImm]) {
130	Prev = &Inst;
131	continue;
132	}
133
134	// If this reg is used locally after a restore, then we are probably
135	// not dealing with a callee-saved reg. Except if this use is by
136	// another store, but we don't cover this case yet.
137	// Also not callee-saved if this load accesses caller stack or isn't
138	// simple.
139	if (!FIE->IsSimple \|\| FIE->StackOffset >= 0 \|\|
140	RU.isReachedBy(FIE->RegOrImm,
141	Prev ? RU.expr_begin(*Prev) : RU.expr_begin(BB))) {
142	CalleeSaved.reset(FIE->RegOrImm);
143	Prev = &Inst;
144	continue;
145	}
146	// If stack offsets between saves/store don't agree with each other,
147	// we don't completely understand what's happening here
148	if (FIE->StackOffset != OffsetsByReg[FIE->RegOrImm]) {
149	CalleeSaved.reset(FIE->RegOrImm);
150	LLVM_DEBUG(dbgs() << "Dismissing Callee-Saved Reg because we found a "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found a " "mismatching restore: " << FIE->RegOrImm << "\n" ; } } while (false)
151	"mismatching restore: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found a " "mismatching restore: " << FIE->RegOrImm << "\n" ; } } while (false)
152	<< FIE->RegOrImm << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found a " "mismatching restore: " << FIE->RegOrImm << "\n" ; } } while (false);
153	Prev = &Inst;
154	continue;
155	}
156
157	LLVM_DEBUG(dbgs() << "Adding matching restore for: " << FIE->RegOrImmdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Adding matching restore for: " << FIE->RegOrImm << "\n"; } } while (false)
158	<< "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Adding matching restore for: " << FIE->RegOrImm << "\n"; } } while (false);
159	if (LoadFIEByReg[FIE->RegOrImm] == nullptr)
160	LoadFIEByReg[FIE->RegOrImm] = &*FIE;
161	BC.MIB->addAnnotation(Inst, getRestoreTag(), FIE->RegOrImm,
162	AllocatorId);
163	HasRestores.set(FIE->RegOrImm);
164	}
165	Prev = &Inst;
166	}
167	}
168	}
169
170	std::vector<MCInst *> CalleeSavedAnalysis::getSavesByReg(uint16_t Reg) {
171	std::vector<MCInst *> Results;
172	for (BinaryBasicBlock &BB : BF)
173	for (MCInst &Inst : BB)
174	if (getSavedReg(Inst) == Reg)
175	Results.push_back(&Inst);
176	return Results;
177	}
178
179	std::vector<MCInst *> CalleeSavedAnalysis::getRestoresByReg(uint16_t Reg) {
180	std::vector<MCInst *> Results;
181	for (BinaryBasicBlock &BB : BF)
182	for (MCInst &Inst : BB)
183	if (getRestoredReg(Inst) == Reg)
184	Results.push_back(&Inst);
185	return Results;
186	}
187
188	CalleeSavedAnalysis::~CalleeSavedAnalysis() {
189	for (BinaryBasicBlock &BB : BF) {
190	for (MCInst &Inst : BB) {
191	BC.MIB->removeAnnotation(Inst, getSaveTag());
192	BC.MIB->removeAnnotation(Inst, getRestoreTag());
193	}
194	}
195	}
196
197	void StackLayoutModifier::blacklistRegion(int64_t Offset, int64_t Size) {
198	if (BlacklistedRegions[Offset] < Size)
199	BlacklistedRegions[Offset] = Size;
200	}
201
202	bool StackLayoutModifier::isRegionBlacklisted(int64_t Offset, int64_t Size) {
203	for (std::pair<const int64_t, int64_t> Elem : BlacklistedRegions)
204	if (Offset + Size > Elem.first && Offset < Elem.first + Elem.second)
205	return true;
206	return false;
207	}
208
209	bool StackLayoutModifier::blacklistAllInConflictWith(int64_t Offset,
210	int64_t Size) {
211	bool HasConflict = false;
212	for (auto Iter = AvailableRegions.begin(); Iter != AvailableRegions.end();) {
213	std::pair<const int64_t, int64_t> &Elem = *Iter;
214	if (Offset + Size > Elem.first && Offset < Elem.first + Elem.second &&
215	(Offset != Elem.first \|\| Size != Elem.second)) {
216	Iter = AvailableRegions.erase(Iter);
217	HasConflict = true;
218	continue;
219	}
220	++Iter;
221	}
222	if (HasConflict) {
223	blacklistRegion(Offset, Size);
224	return true;
225	}
226	return false;
227	}
228
229	void StackLayoutModifier::checkFramePointerInitialization(MCInst &Point) {
230	StackPointerTracking &SPT = Info.getStackPointerTracking();
231	if (!BC.MII->get(Point.getOpcode())
232	.hasDefOfPhysReg(Point, BC.MIB->getFramePointer(), *BC.MRI))
233	return;
234
235	int SPVal, FPVal;
236	std::tie(SPVal, FPVal) = *SPT.getStateBefore(Point);
237	std::pair<MCPhysReg, int64_t> FP;
238
239	if (FPVal != SPT.EMPTY && FPVal != SPT.SUPERPOSITION)
240	FP = std::make_pair(BC.MIB->getFramePointer(), FPVal);
241	else
242	FP = std::make_pair(0, 0);
243	std::pair<MCPhysReg, int64_t> SP;
244
245	if (SPVal != SPT.EMPTY && SPVal != SPT.SUPERPOSITION)
246	SP = std::make_pair(BC.MIB->getStackPointer(), SPVal);
247	else
248	SP = std::make_pair(0, 0);
249
250	int64_t Output;
251	if (!BC.MIB->evaluateStackOffsetExpr(Point, Output, SP, FP))
252	return;
253
254	// Not your regular frame pointer initialization... bail
255	if (Output != SPVal)
256	blacklistRegion(0, 0);
257	}
258
259	void StackLayoutModifier::checkStackPointerRestore(MCInst &Point) {
260	StackPointerTracking &SPT = Info.getStackPointerTracking();
261	if (!BC.MII->get(Point.getOpcode())
262	.hasDefOfPhysReg(Point, BC.MIB->getStackPointer(), *BC.MRI))
263	return;
264	// Check if the definition of SP comes from FP -- in this case, this
265	// value may need to be updated depending on our stack layout changes
266	const MCInstrDesc &InstInfo = BC.MII->get(Point.getOpcode());
267	unsigned NumDefs = InstInfo.getNumDefs();
268	bool UsesFP = llvm::any_of(
269	llvm::drop_begin(MCPlus::primeOperands(Point), NumDefs),
270	[&](MCOperand &Op) {
271	return Op.isReg() && Op.getReg() == BC.MIB->getFramePointer();
272	});
273	if (!UsesFP)
274	return;
275
276	// Setting up evaluation
277	int SPVal, FPVal;
278	std::tie(SPVal, FPVal) = *SPT.getStateBefore(Point);
279	std::pair<MCPhysReg, int64_t> FP;
280
281	if (FPVal != SPT.EMPTY && FPVal != SPT.SUPERPOSITION)
282	FP = std::make_pair(BC.MIB->getFramePointer(), FPVal);
283	else
284	FP = std::make_pair(0, 0);
285	std::pair<MCPhysReg, int64_t> SP;
286
287	if (SPVal != SPT.EMPTY && SPVal != SPT.SUPERPOSITION)
288	SP = std::make_pair(BC.MIB->getStackPointer(), SPVal);
289	else
290	SP = std::make_pair(0, 0);
291
292	int64_t Output;
293	if (!BC.MIB->evaluateStackOffsetExpr(Point, Output, SP, FP))
294	return;
295
296	// If the value is the same of FP, no need to adjust it
297	if (Output == FPVal)
298	return;
299
300	// If an allocation happened through FP, bail
301	if (Output <= SPVal) {
302	blacklistRegion(0, 0);
303	return;
304	}
305
306	// We are restoring SP to an old value based on FP. Mark it as a stack
307	// access to be fixed later.
308	BC.MIB->addAnnotation(Point, getSlotTag(), Output, AllocatorId);
309	}
310
311	void StackLayoutModifier::classifyStackAccesses() {
312	// Understand when stack slots are being used non-locally
313	StackReachingUses &SRU = Info.getStackReachingUses();
314
315	for (BinaryBasicBlock &BB : BF) {
316	const MCInst *Prev = nullptr;
317	for (MCInst &Inst : llvm::reverse(BB)) {
318	checkFramePointerInitialization(Inst);
319	checkStackPointerRestore(Inst);
320	ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);
321	if (!FIEX) {
322	Prev = &Inst;
323	continue;
324	}
325	if (!FIEX->IsSimple \|\| (FIEX->IsStore && !FIEX->IsStoreFromReg)) {
326	blacklistRegion(FIEX->StackOffset, FIEX->Size);
327	Prev = &Inst;
328	continue;
329	}
330	// If this stack position is accessed in another function, we are
331	// probably dealing with a parameter passed in a stack -- do not mess
332	// with it
333	if (SRU.isStoreUsed(*FIEX,
334	Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB),
335	/IncludeLocalAccesses=/false)) {
336	blacklistRegion(FIEX->StackOffset, FIEX->Size);
337	Prev = &Inst;
338	continue;
339	}
340	// Now we have a clear stack slot access. Check if its blacklisted or if
341	// it conflicts with another chunk.
342	if (isRegionBlacklisted(FIEX->StackOffset, FIEX->Size) \|\|
343	blacklistAllInConflictWith(FIEX->StackOffset, FIEX->Size)) {
344	Prev = &Inst;
345	continue;
346	}
347	// We are free to go. Add it as available stack slot which we know how
348	// to move it.
349	AvailableRegions[FIEX->StackOffset] = FIEX->Size;
350	BC.MIB->addAnnotation(Inst, getSlotTag(), FIEX->StackOffset, AllocatorId);
351	RegionToRegMap[FIEX->StackOffset].insert(FIEX->RegOrImm);
352	RegToRegionMap[FIEX->RegOrImm].insert(FIEX->StackOffset);
353	LLVM_DEBUG(dbgs() << "Adding region " << FIEX->StackOffset << " size "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Adding region " << FIEX->StackOffset << " size " << (int)FIEX-> Size << "\n"; } } while (false)
354	<< (int)FIEX->Size << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Adding region " << FIEX->StackOffset << " size " << (int)FIEX-> Size << "\n"; } } while (false);
355	}
356	}
357	}
358
359	void StackLayoutModifier::classifyCFIs() {
360	std::stack<std::pair<int64_t, uint16_t>> CFIStack;
361	int64_t CfaOffset = -8;
362	uint16_t CfaReg = 7;
363
364	auto recordAccess = [&](MCInst *Inst, int64_t Offset) {
365	const uint16_t Reg = BC.MRI->getLLVMRegNum(CfaReg, /isEH=*/false);
366	if (Reg == BC.MIB->getStackPointer() \|\| Reg == BC.MIB->getFramePointer()) {
367	BC.MIB->addAnnotation(*Inst, getSlotTag(), Offset, AllocatorId);
368	LLVM_DEBUG(dbgs() << "Recording CFI " << Offset << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Recording CFI " << Offset << "\n"; } } while (false);
369	} else {
370	IsSimple = false;
371	return;
372	}
373	};
374
375	for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
376	for (MCInst &Inst : *BB) {
377	if (!BC.MIB->isCFI(Inst))
378	continue;
379	const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
380	switch (CFI->getOperation()) {
381	case MCCFIInstruction::OpDefCfa:
382	CfaOffset = -CFI->getOffset();
383	recordAccess(&Inst, CfaOffset);
384	[[fallthrough]];
385	case MCCFIInstruction::OpDefCfaRegister:
386	CfaReg = CFI->getRegister();
387	break;
388	case MCCFIInstruction::OpDefCfaOffset:
389	CfaOffset = -CFI->getOffset();
390	recordAccess(&Inst, CfaOffset);
391	break;
392	case MCCFIInstruction::OpOffset:
393	recordAccess(&Inst, CFI->getOffset());
394	BC.MIB->addAnnotation(Inst, getOffsetCFIRegTag(),
395	BC.MRI->getLLVMRegNum(CFI->getRegister(),
396	/isEH=/false),
397	AllocatorId);
398	break;
399	case MCCFIInstruction::OpSameValue:
400	BC.MIB->addAnnotation(Inst, getOffsetCFIRegTag(),
401	BC.MRI->getLLVMRegNum(CFI->getRegister(),
402	/isEH=/false),
403	AllocatorId);
404	break;
405	case MCCFIInstruction::OpRememberState:
406	CFIStack.push(std::make_pair(CfaOffset, CfaReg));
407	break;
408	case MCCFIInstruction::OpRestoreState: {
409	assert(!CFIStack.empty() && "Corrupt CFI stack")(static_cast <bool> (!CFIStack.empty() && "Corrupt CFI stack" ) ? void (0) : __assert_fail ("!CFIStack.empty() && \"Corrupt CFI stack\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 409, __extension__ __PRETTY_FUNCTION__ ));
410	std::pair<int64_t, uint16_t> &Elem = CFIStack.top();
411	CFIStack.pop();
412	CfaOffset = Elem.first;
413	CfaReg = Elem.second;
414	break;
415	}
416	case MCCFIInstruction::OpRelOffset:
417	case MCCFIInstruction::OpAdjustCfaOffset:
418	llvm_unreachable("Unhandled AdjustCfaOffset")::llvm::llvm_unreachable_internal("Unhandled AdjustCfaOffset" , "bolt/lib/Passes/ShrinkWrapping.cpp", 418);
419	break;
420	default:
421	break;
422	}
423	}
424	}
425	}
426
427	void StackLayoutModifier::scheduleChange(
428	MCInst &Inst, StackLayoutModifier::WorklistItem Item) {
429	auto &WList = BC.MIB->getOrCreateAnnotationAs<std::vector<WorklistItem>>(
430	Inst, getTodoTag(), AllocatorId);
431	WList.push_back(Item);
432	}
433
434	bool StackLayoutModifier::canCollapseRegion(MCInst *DeletedPush) {
435	if (!IsSimple \|\| !BC.MIB->isPush(*DeletedPush))
436	return false;
437
438	ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(*DeletedPush);
439	if (!FIE)
440	return false;
441
442	return canCollapseRegion(FIE->StackOffset);
443	}
444
445	bool StackLayoutModifier::canCollapseRegion(int64_t RegionAddr) {
446	if (!IsInitialized)
447	initialize();
448	if (!IsSimple)
449	return false;
450
451	if (CollapsedRegions.count(RegionAddr))
452	return true;
453
454	// Check if it is possible to readjust all accesses below RegionAddr
455	if (!BlacklistedRegions.empty())
456	return false;
457
458	return true;
459	}
460
461	bool StackLayoutModifier::collapseRegion(MCInst *DeletedPush) {
462	ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(*DeletedPush);
463	if (!FIE)
464	return false;
465	int64_t RegionAddr = FIE->StackOffset;
466	int64_t RegionSz = FIE->Size;
467	return collapseRegion(DeletedPush, RegionAddr, RegionSz);
468	}
469
470	bool StackLayoutModifier::collapseRegion(MCInst *Alloc, int64_t RegionAddr,
471	int64_t RegionSz) {
472	if (!canCollapseRegion(RegionAddr))
473	return false;
474
475	assert(IsInitialized)(static_cast <bool> (IsInitialized) ? void (0) : __assert_fail ("IsInitialized", "bolt/lib/Passes/ShrinkWrapping.cpp", 475, __extension__ __PRETTY_FUNCTION__));
476	StackAllocationAnalysis &SAA = Info.getStackAllocationAnalysis();
477
478	for (BinaryBasicBlock &BB : BF) {
479	for (MCInst &Inst : BB) {
480	if (!BC.MIB->hasAnnotation(Inst, getSlotTag()))
481	continue;
482	auto Slot =
483	BC.MIB->getAnnotationAs<decltype(FrameIndexEntry::StackOffset)>(
484	Inst, getSlotTag());
485	if (!AvailableRegions.count(Slot))
486	continue;
487	// We need to ensure this access is affected by the deleted push
488	if (!(*SAA.getStateBefore(Inst))[SAA.ExprToIdx[Alloc]])
489	continue;
490
491	if (BC.MIB->isCFI(Inst)) {
492	if (Slot > RegionAddr)
493	continue;
494	scheduleChange(Inst, WorklistItem(WorklistItem::AdjustCFI, RegionSz));
495	continue;
496	}
497	ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);
498	if (!FIE) {
499	if (Slot > RegionAddr)
500	continue;
501	// SP update based on frame pointer
502	scheduleChange(
503	Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, RegionSz));
504	continue;
505	}
506
507	if (Slot == RegionAddr) {
508	BC.MIB->addAnnotation(Inst, "AccessesDeletedPos", 0U, AllocatorId);
509	continue;
510	}
511	if (BC.MIB->isPush(Inst) \|\| BC.MIB->isPop(Inst))
512	continue;
513
514	if (FIE->StackPtrReg == BC.MIB->getStackPointer() && Slot < RegionAddr)
515	continue;
516
517	if (FIE->StackPtrReg == BC.MIB->getFramePointer() && Slot > RegionAddr)
518	continue;
519
520	scheduleChange(
521	Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, RegionSz));
522	}
523	}
524
525	CollapsedRegions.insert(RegionAddr);
526	return true;
527	}
528
529	void StackLayoutModifier::setOffsetForCollapsedAccesses(int64_t NewOffset) {
530	for (BinaryBasicBlock &BB : BF) {
531	for (MCInst &Inst : BB) {
532	if (!BC.MIB->hasAnnotation(Inst, "AccessesDeletedPos"))
533	continue;
534	BC.MIB->removeAnnotation(Inst, "AccessesDeletedPos");
535	scheduleChange(
536	Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, NewOffset));
537	}
538	}
539	}
540
541	bool StackLayoutModifier::canInsertRegion(ProgramPoint P) {
542	if (!IsInitialized)
543	initialize();
544	if (!IsSimple)
545	return false;
546
547	StackPointerTracking &SPT = Info.getStackPointerTracking();
548	int64_t RegionAddr = SPT.getStateBefore(P)->first;
549	if (RegionAddr == SPT.SUPERPOSITION \|\| RegionAddr == SPT.EMPTY)
550	return false;
551
552	if (InsertedRegions.count(RegionAddr))
553	return true;
554
555	// Check if we are going to screw up stack accesses at call sites that
556	// pass parameters via stack
557	if (!BlacklistedRegions.empty())
558	return false;
559
560	return true;
561	}
562
563	bool StackLayoutModifier::insertRegion(ProgramPoint P, int64_t RegionSz) {
564	if (!canInsertRegion(P))
565	return false;
566
567	assert(IsInitialized)(static_cast <bool> (IsInitialized) ? void (0) : __assert_fail ("IsInitialized", "bolt/lib/Passes/ShrinkWrapping.cpp", 567, __extension__ __PRETTY_FUNCTION__));
568	StackPointerTracking &SPT = Info.getStackPointerTracking();
569	// This RegionAddr is slightly different from the one seen in collapseRegion
570	// This is the value of SP before the allocation the user wants to make.
571	int64_t RegionAddr = SPT.getStateBefore(P)->first;
572	if (RegionAddr == SPT.SUPERPOSITION \|\| RegionAddr == SPT.EMPTY)
573	return false;
574
575	DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
576
577	for (BinaryBasicBlock &BB : BF) {
578	for (MCInst &Inst : BB) {
579	if (!BC.MIB->hasAnnotation(Inst, getSlotTag()))
580	continue;
581	auto Slot =
582	BC.MIB->getAnnotationAs<decltype(FrameIndexEntry::StackOffset)>(
583	Inst, getSlotTag());
584	if (!AvailableRegions.count(Slot))
585	continue;
586
587	if (!(DA.doesADominateB(P, Inst)))
588	continue;
589
590	if (BC.MIB->isCFI(Inst)) {
591	if (Slot >= RegionAddr)
592	continue;
593	scheduleChange(Inst, WorklistItem(WorklistItem::AdjustCFI, -RegionSz));
594	continue;
595	}
596	ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);
597	if (!FIE) {
598	if (Slot >= RegionAddr)
599	continue;
600	scheduleChange(
601	Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, -RegionSz));
602	continue;
603	}
604
605	if (FIE->StackPtrReg == BC.MIB->getStackPointer() && Slot < RegionAddr)
606	continue;
607	if (FIE->StackPtrReg == BC.MIB->getFramePointer() && Slot >= RegionAddr)
608	continue;
609	if (BC.MIB->isPush(Inst) \|\| BC.MIB->isPop(Inst))
610	continue;
611	scheduleChange(
612	Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, -RegionSz));
613	}
614	}
615
616	InsertedRegions.insert(RegionAddr);
617	return true;
618	}
619
620	void StackLayoutModifier::performChanges() {
621	std::set<uint32_t> ModifiedCFIIndices;
622	for (BinaryBasicBlock &BB : BF) {
623	for (MCInst &Inst : llvm::reverse(BB)) {
624	if (BC.MIB->hasAnnotation(Inst, "AccessesDeletedPos")) {
625	assert(BC.MIB->isPop(Inst) \|\| BC.MIB->isPush(Inst))(static_cast <bool> (BC.MIB->isPop(Inst) \|\| BC.MIB-> isPush(Inst)) ? void (0) : __assert_fail ("BC.MIB->isPop(Inst) \|\| BC.MIB->isPush(Inst)" , "bolt/lib/Passes/ShrinkWrapping.cpp", 625, __extension__ __PRETTY_FUNCTION__ ));
626	BC.MIB->removeAnnotation(Inst, "AccessesDeletedPos");
627	}
628	if (!BC.MIB->hasAnnotation(Inst, getTodoTag()))
629	continue;
630	auto &WList = BC.MIB->getAnnotationAs<std::vector<WorklistItem>>(
631	Inst, getTodoTag());
632	int64_t Adjustment = 0;
633	WorklistItem::ActionType AdjustmentType = WorklistItem::None;
634	for (WorklistItem &WI : WList) {
635	if (WI.Action == WorklistItem::None)
636	continue;
637	assert(WI.Action == WorklistItem::AdjustLoadStoreOffset \|\|(static_cast <bool> (WI.Action == WorklistItem::AdjustLoadStoreOffset \|\| WI.Action == WorklistItem::AdjustCFI) ? void (0) : __assert_fail ("WI.Action == WorklistItem::AdjustLoadStoreOffset \|\| WI.Action == WorklistItem::AdjustCFI" , "bolt/lib/Passes/ShrinkWrapping.cpp", 638, __extension__ __PRETTY_FUNCTION__ ))
638	WI.Action == WorklistItem::AdjustCFI)(static_cast <bool> (WI.Action == WorklistItem::AdjustLoadStoreOffset \|\| WI.Action == WorklistItem::AdjustCFI) ? void (0) : __assert_fail ("WI.Action == WorklistItem::AdjustLoadStoreOffset \|\| WI.Action == WorklistItem::AdjustCFI" , "bolt/lib/Passes/ShrinkWrapping.cpp", 638, __extension__ __PRETTY_FUNCTION__ ));
639	assert((AdjustmentType == WorklistItem::None \|\|(static_cast <bool> ((AdjustmentType == WorklistItem::None \|\| AdjustmentType == WI.Action) && "Conflicting actions requested at the same program point" ) ? void (0) : __assert_fail ("(AdjustmentType == WorklistItem::None \|\| AdjustmentType == WI.Action) && \"Conflicting actions requested at the same program point\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 641, __extension__ __PRETTY_FUNCTION__ ))
640	AdjustmentType == WI.Action) &&(static_cast <bool> ((AdjustmentType == WorklistItem::None \|\| AdjustmentType == WI.Action) && "Conflicting actions requested at the same program point" ) ? void (0) : __assert_fail ("(AdjustmentType == WorklistItem::None \|\| AdjustmentType == WI.Action) && \"Conflicting actions requested at the same program point\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 641, __extension__ __PRETTY_FUNCTION__ ))
641	"Conflicting actions requested at the same program point")(static_cast <bool> ((AdjustmentType == WorklistItem::None \|\| AdjustmentType == WI.Action) && "Conflicting actions requested at the same program point" ) ? void (0) : __assert_fail ("(AdjustmentType == WorklistItem::None \|\| AdjustmentType == WI.Action) && \"Conflicting actions requested at the same program point\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 641, __extension__ __PRETTY_FUNCTION__ ));
642	AdjustmentType = WI.Action;
643	Adjustment += WI.OffsetUpdate;
644	}
645	if (!Adjustment)
646	continue;
647	if (AdjustmentType != WorklistItem::AdjustLoadStoreOffset) {
648	assert(BC.MIB->isCFI(Inst))(static_cast <bool> (BC.MIB->isCFI(Inst)) ? void (0) : __assert_fail ("BC.MIB->isCFI(Inst)", "bolt/lib/Passes/ShrinkWrapping.cpp" , 648, __extension__ __PRETTY_FUNCTION__));
649	uint32_t CFINum = Inst.getOperand(0).getImm();
650	if (ModifiedCFIIndices.count(CFINum))
651	continue;
652	ModifiedCFIIndices.insert(CFINum);
653	const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
654	const MCCFIInstruction::OpType Operation = CFI->getOperation();
655	if (Operation == MCCFIInstruction::OpDefCfa \|\|
656	Operation == MCCFIInstruction::OpDefCfaOffset)
657	Adjustment = 0 - Adjustment;
658	LLVM_DEBUG(dbgs() << "Changing CFI offset from " << CFI->getOffset()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Changing CFI offset from " << CFI->getOffset() << " to " << (CFI-> getOffset() + Adjustment) << "\n"; } } while (false)
659	<< " to " << (CFI->getOffset() + Adjustment) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Changing CFI offset from " << CFI->getOffset() << " to " << (CFI-> getOffset() + Adjustment) << "\n"; } } while (false);
660	BF.mutateCFIOffsetFor(Inst, CFI->getOffset() + Adjustment);
661	continue;
662	}
663	int32_t SrcImm = 0;
664	MCPhysReg Reg = 0;
665	MCPhysReg StackPtrReg = 0;
666	int64_t StackOffset = 0;
667	bool IsIndexed = false;
668	bool IsLoad = false;
669	bool IsStore = false;
670	bool IsSimple = false;
671	bool IsStoreFromReg = false;
672	uint8_t Size = 0;
673	bool Success = false;
674	Success = BC.MIB->isStackAccess(Inst, IsLoad, IsStore, IsStoreFromReg,
675	Reg, SrcImm, StackPtrReg, StackOffset,
676	Size, IsSimple, IsIndexed);
677	if (!Success) {
678	// SP update based on FP value
679	Success = BC.MIB->addToImm(Inst, Adjustment, &*BC.Ctx);
680	assert(Success)(static_cast <bool> (Success) ? void (0) : __assert_fail ("Success", "bolt/lib/Passes/ShrinkWrapping.cpp", 680, __extension__ __PRETTY_FUNCTION__));
681	continue;
682	}
683	assert(Success && IsSimple && !IsIndexed && (!IsStore \|\| IsStoreFromReg))(static_cast <bool> (Success && IsSimple && !IsIndexed && (!IsStore \|\| IsStoreFromReg)) ? void ( 0) : __assert_fail ("Success && IsSimple && !IsIndexed && (!IsStore \|\| IsStoreFromReg)" , "bolt/lib/Passes/ShrinkWrapping.cpp", 683, __extension__ __PRETTY_FUNCTION__ ));
684	if (StackPtrReg != BC.MIB->getFramePointer())
685	Adjustment = -Adjustment;
686	if (IsLoad)
687	Success = BC.MIB->createRestoreFromStack(
688	Inst, StackPtrReg, StackOffset + Adjustment, Reg, Size);
689	else if (IsStore)
690	Success = BC.MIB->createSaveToStack(
691	Inst, StackPtrReg, StackOffset + Adjustment, Reg, Size);
692	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adjusted instruction: " ; Inst.dump(); }; } } while (false)
693	dbgs() << "Adjusted instruction: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adjusted instruction: " ; Inst.dump(); }; } } while (false)
694	Inst.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adjusted instruction: " ; Inst.dump(); }; } } while (false)
695	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adjusted instruction: " ; Inst.dump(); }; } } while (false);
696	assert(Success)(static_cast <bool> (Success) ? void (0) : __assert_fail ("Success", "bolt/lib/Passes/ShrinkWrapping.cpp", 696, __extension__ __PRETTY_FUNCTION__));
697	}
698	}
699	}
700
701	void StackLayoutModifier::initialize() {
702	classifyStackAccesses();
703	classifyCFIs();
704	IsInitialized = true;
705	}
706
707	std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedRegularMode{0};
708	std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedPushPopMode{0};
709	std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedDynamicCount{0};
710	std::atomic<std::uint64_t> ShrinkWrapping::SpillsFailedDynamicCount{0};
711	std::atomic<std::uint64_t> ShrinkWrapping::InstrDynamicCount{0};
712	std::atomic<std::uint64_t> ShrinkWrapping::StoreDynamicCount{0};
713
714	using BBIterTy = BinaryBasicBlock::iterator;
715
716	void ShrinkWrapping::classifyCSRUses() {
717	DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
718	StackPointerTracking &SPT = Info.getStackPointerTracking();
719	UsesByReg = std::vector<BitVector>(BC.MRI->getNumRegs(),
720	BitVector(DA.NumInstrs, false));
721
722	const BitVector &FPAliases = BC.MIB->getAliases(BC.MIB->getFramePointer());
723	for (BinaryBasicBlock &BB : BF) {
724	for (MCInst &Inst : BB) {
725	if (BC.MIB->isCFI(Inst))
726	continue;
727	BitVector BV = BitVector(BC.MRI->getNumRegs(), false);
728	BC.MIB->getTouchedRegs(Inst, BV);
729	BV &= CSA.CalleeSaved;
730	for (int I : BV.set_bits()) {
731	if (I == 0)
732	continue;
733	if (CSA.getSavedReg(Inst) != I && CSA.getRestoredReg(Inst) != I)
734	UsesByReg[I].set(DA.ExprToIdx[&Inst]);
735	}
736	if (!SPT.HasFramePointer \|\| !BC.MIB->isCall(Inst))
737	continue;
738	BV = CSA.CalleeSaved;
739	BV &= FPAliases;
740	for (int I : BV.set_bits())
741	UsesByReg[I].set(DA.ExprToIdx[&Inst]);
742	}
743	}
744	}
745
746	void ShrinkWrapping::pruneUnwantedCSRs() {
747	BitVector ParamRegs = BC.MIB->getRegsUsedAsParams();
748	for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
749	if (!CSA.CalleeSaved[I])
750	continue;
751	if (ParamRegs[I]) {
752	CSA.CalleeSaved.reset(I);
753	continue;
754	}
755	if (UsesByReg[I].empty()) {
756	LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:" << I << "\n"; } } while (false)
757	dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:" << I << "\n"; } } while (false)
758	<< "Dismissing Callee-Saved Reg because we found no uses of it:" << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:" << I << "\n"; } } while (false)
759	<< "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:" << I << "\n"; } } while (false);
760	CSA.CalleeSaved.reset(I);
761	continue;
762	}
763	if (!CSA.HasRestores[I]) {
764	LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have " "restores:" << I << "\n"; } } while (false)
765	dbgs() << "Dismissing Callee-Saved Reg because it does not have "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have " "restores:" << I << "\n"; } } while (false)
766	"restores:"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have " "restores:" << I << "\n"; } } while (false)
767	<< I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have " "restores:" << I << "\n"; } } while (false);
768	CSA.CalleeSaved.reset(I);
769	}
770	}
771	}
772
773	void ShrinkWrapping::computeSaveLocations() {
774	BestSavePos = std::vector<std::vector<MCInst *>>(BC.MRI->getNumRegs());
775	ReachingInsns<true> &RI = Info.getReachingInsnsBackwards();
776	DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
777	StackPointerTracking &SPT = Info.getStackPointerTracking();
778
779	LLVM_DEBUG(dbgs() << "Checking save/restore possibilities\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Checking save/restore possibilities\n" ; } } while (false);
780	for (BinaryBasicBlock &BB : BF) {
781	LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\tNow at BB " << BB.getName() << "\n"; } } while (false);
782
783	MCInst First = BB.begin() != BB.end() ? &BB.begin() : nullptr;
784	if (!First)
785	continue;
786
787	// Use reaching instructions to detect if we are inside a loop - if we
788	// are, do not consider this BB as valid placement for saves.
789	if (RI.isInLoop(BB))
790	continue;
791
792	const std::pair<int, int> SPFP = SPT.getStateBefore(First);
793	// If we don't know stack state at this point, bail
794	if ((SPFP.first == SPT.SUPERPOSITION \|\| SPFP.first == SPT.EMPTY) &&
795	(SPFP.second == SPT.SUPERPOSITION \|\| SPFP.second == SPT.EMPTY))
796	continue;
797
798	for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
799	if (!CSA.CalleeSaved[I])
800	continue;
801
802	BitVector BBDominatedUses = BitVector(DA.NumInstrs, false);
803	for (int J : UsesByReg[I].set_bits())
804	if (DA.doesADominateB(*First, J))
805	BBDominatedUses.set(J);
806	LLVM_DEBUG(dbgs() << "\t\tBB " << BB.getName() << " dominates "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName () << " dominates " << BBDominatedUses.count() << " uses for reg " << I << ". Total uses for reg is " << UsesByReg[I].count() << "\n"; } } while (false )
807	<< BBDominatedUses.count() << " uses for reg " << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName () << " dominates " << BBDominatedUses.count() << " uses for reg " << I << ". Total uses for reg is " << UsesByReg[I].count() << "\n"; } } while (false )
808	<< ". Total uses for reg is " << UsesByReg[I].count()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName () << " dominates " << BBDominatedUses.count() << " uses for reg " << I << ". Total uses for reg is " << UsesByReg[I].count() << "\n"; } } while (false )
809	<< "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName () << " dominates " << BBDominatedUses.count() << " uses for reg " << I << ". Total uses for reg is " << UsesByReg[I].count() << "\n"; } } while (false );
810	BBDominatedUses &= UsesByReg[I];
811	if (BBDominatedUses == UsesByReg[I]) {
812	LLVM_DEBUG(dbgs() << "\t\t\tAdded " << BB.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\t\t\tAdded " << BB.getName() << " as a save pos for " << I << "\n"; } } while (false)
813	<< " as a save pos for " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "\t\t\tAdded " << BB.getName() << " as a save pos for " << I << "\n"; } } while (false);
814	BestSavePos[I].push_back(First);
815	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
816	dbgs() << "Dominated uses are:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
817	for (int J : UsesByReg[I].set_bits()) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
818	dbgs() << "Idx " << J << ": ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
819	BC.printInstruction(dbgs(), DA.Expressions[J]);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
820	DA.Expressions[J]->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
821	}do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false)
822	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n" ; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx " << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions [J]); DA.Expressions[J]->dump(); } }; } } while (false);
823	}
824	}
825	}
826
827	BestSaveCount = std::vector<std::vector<uint64_t>>(BC.MRI->getNumRegs());
828
829	auto &InsnToBB = Info.getInsnToBBMap();
830	for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
831	if (!CSA.CalleeSaved[I])
832	continue;
833
834	std::stable_sort(BestSavePos[I].begin(), BestSavePos[I].end(),
835	[&](const MCInst A, const MCInst B) {
836	const BinaryBasicBlock *BBA = InsnToBB[A];
837	const BinaryBasicBlock *BBB = InsnToBB[B];
838	const uint64_t CountA = BBA->getKnownExecutionCount();
839	const uint64_t CountB = BBB->getKnownExecutionCount();
840	return CountB < CountA;
841	});
842
843	for (MCInst *Pos : BestSavePos[I]) {
844	const BinaryBasicBlock *BB = InsnToBB[Pos];
845	const uint64_t Count = BB->getKnownExecutionCount();
846	BestSaveCount[I].push_back(Count);
847	}
848	}
849	}
850
851	void ShrinkWrapping::computeDomOrder() {
852	DomOrder = std::vector<MCPhysReg>(BC.MRI->getNumRegs(), 0);
853	std::vector<MCPhysReg> Order;
854	for (MCPhysReg I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
855	Order.push_back(I);
856	}
857
858	DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
859	auto &InsnToBB = Info.getInsnToBBMap();
860	llvm::sort(Order, [&](const MCPhysReg &A, const MCPhysReg &B) {
861	BinaryBasicBlock *BBA =
862	BestSavePos[A].size() ? InsnToBB[BestSavePos[A].back()] : nullptr;
863	BinaryBasicBlock *BBB =
864	BestSavePos[B].size() ? InsnToBB[BestSavePos[B].back()] : nullptr;
865	if (BBA == BBB)
866	return A < B;
867	if (!BBA && BBB)
868	return false;
869	if (BBA && !BBB)
870	return true;
871	if (DA.doesADominateB(BestSavePos[A].back(), BestSavePos[B].back()))
872	return true;
873	if (DA.doesADominateB(BestSavePos[B].back(), BestSavePos[A].back()))
874	return false;
875	return A < B;
876	});
877
878	for (MCPhysReg I = 0, E = BC.MRI->getNumRegs(); I != E; ++I)
879	DomOrder[Order[I]] = I;
880	}
881
882	bool ShrinkWrapping::isBestSavePosCold(unsigned CSR, MCInst *&BestPosSave,
883	uint64_t &TotalEstimatedWin) {
884	const uint64_t CurSavingCost = CSA.SavingCost[CSR];
885	if (!CSA.CalleeSaved[CSR])
886	return false;
887
888	assert(BestSaveCount[CSR].size() == BestSavePos[CSR].size() &&(static_cast <bool> (BestSaveCount[CSR].size() == BestSavePos [CSR].size() && "save position vectors out of sync") ? void (0) : __assert_fail ("BestSaveCount[CSR].size() == BestSavePos[CSR].size() && \"save position vectors out of sync\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 889, __extension__ __PRETTY_FUNCTION__ ))
889	"save position vectors out of sync")(static_cast <bool> (BestSaveCount[CSR].size() == BestSavePos [CSR].size() && "save position vectors out of sync") ? void (0) : __assert_fail ("BestSaveCount[CSR].size() == BestSavePos[CSR].size() && \"save position vectors out of sync\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 889, __extension__ __PRETTY_FUNCTION__ ));
890	if (BestSaveCount[CSR].empty())
891	return false;
892
893	const uint64_t BestCount = BestSaveCount[CSR].back();
894	BestPosSave = BestSavePos[CSR].back();
895	if (BestCount >= (opts::ShrinkWrappingThreshold / 100.0) * CurSavingCost)
896	return false;
897
898	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false)
899	auto &InsnToBB = Info.getInsnToBBMap();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false)
900	dbgs() << "Better position for saves found in func " << BF.getPrintName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false)
901	<< " count << " << BF.getKnownExecutionCount() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false)
902	dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave]->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false)
903	<< " Freq reduction: " << (CurSavingCost - BestCount) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false)
904	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap (); dbgs() << "Better position for saves found in func " << BF.getPrintName() << " count << " << BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave ]->getName() << " Freq reduction: " << (CurSavingCost - BestCount) << "\n"; }; } } while (false);
905
906	TotalEstimatedWin = CurSavingCost - BestCount;
907	return true;
908	}
909
910	/// Auxiliar function used to create basic blocks for critical edges and update
911	/// the dominance frontier with these new locations
912	void ShrinkWrapping::splitFrontierCritEdges(
913	BinaryFunction *Func, SmallVector<ProgramPoint, 4> &Frontier,
914	const SmallVector<bool, 4> &IsCritEdge,
915	const SmallVector<BinaryBasicBlock *, 4> &From,
916	const SmallVector<SmallVector<BinaryBasicBlock *, 4>, 4> &To) {
917	LLVM_DEBUG(dbgs() << "splitFrontierCritEdges: Now handling func "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "splitFrontierCritEdges: Now handling func " << BF.getPrintName() << "\n"; } } while (false)
918	<< BF.getPrintName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "splitFrontierCritEdges: Now handling func " << BF.getPrintName() << "\n"; } } while (false);
919	// For every FromBB, there might be one or more critical edges, with
920	// To[I] containing destination BBs. It's important to memorize
921	// the original size of the Frontier as we may append to it while splitting
922	// critical edges originating with blocks with multiple destinations.
923	for (size_t I = 0, IE = Frontier.size(); I < IE; ++I) {
924	if (!IsCritEdge[I])
925	continue;
926	if (To[I].empty())
927	continue;
928	BinaryBasicBlock *FromBB = From[I];
929	LLVM_DEBUG(dbgs() << " - Now handling FrontierBB " << FromBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Now handling FrontierBB " << FromBB->getName() << "\n"; } } while (false )
930	<< "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Now handling FrontierBB " << FromBB->getName() << "\n"; } } while (false );
931	// Split edge for every DestinationBBs
932	for (size_t DI = 0, DIE = To[I].size(); DI < DIE; ++DI) {
933	BinaryBasicBlock *DestinationBB = To[I][DI];
934	LLVM_DEBUG(dbgs() << " - Dest : " << DestinationBB->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Dest : " << DestinationBB->getName() << "\n"; } } while (false);
935	BinaryBasicBlock *NewBB = Func->splitEdge(FromBB, DestinationBB);
936	// Insert dummy instruction so this BB is never empty (we need this for
937	// PredictiveStackPointerTracking to work, since it annotates instructions
938	// and not BBs).
939	if (NewBB->empty()) {
940	MCInst NewInst;
941	BC.MIB->createNoop(NewInst);
942	NewBB->addInstruction(std::move(NewInst));
943	scheduleChange(&*NewBB->begin(), WorklistItem(WorklistItem::Erase, 0));
944	}
945
946	// Update frontier
947	ProgramPoint NewFrontierPP = ProgramPoint::getLastPointAt(*NewBB);
948	if (DI == 0) {
949	// Update frontier inplace
950	Frontier[I] = NewFrontierPP;
951	LLVM_DEBUG(dbgs() << " - Update frontier with " << NewBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Update frontier with " << NewBB->getName() << '\n'; } } while (false )
952	<< '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Update frontier with " << NewBB->getName() << '\n'; } } while (false );
953	} else {
954	// Append new frontier to the end of the list
955	Frontier.push_back(NewFrontierPP);
956	LLVM_DEBUG(dbgs() << " - Append frontier " << NewBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Append frontier " << NewBB->getName() << '\n'; } } while (false )
957	<< '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << " - Append frontier " << NewBB->getName() << '\n'; } } while (false );
958	}
959	}
960	}
961	}
962
963	SmallVector<ProgramPoint, 4>
964	ShrinkWrapping::doRestorePlacement(MCInst *BestPosSave, unsigned CSR,
965	uint64_t TotalEstimatedWin) {
966	SmallVector<ProgramPoint, 4> Frontier;
967	SmallVector<bool, 4> IsCritEdge;
968	DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
969
970	SmallVector<BinaryBasicBlock *, 4> CritEdgesFrom;
971	SmallVector<SmallVector<BinaryBasicBlock *, 4>, 4> CritEdgesTo;
972	// In case of a critical edge, we need to create extra BBs to host restores
973	// into edges transitioning to the dominance frontier, otherwise we pull these
974	// restores to inside the dominated area.
975	Frontier = DA.getDominanceFrontierFor(*BestPosSave).takeVector();
976	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
977	dbgs() << "Dumping dominance frontier for ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
978	BC.printInstruction(dbgs(), BestPosSave);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), *PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
979	for (ProgramPoint &PP : Frontier)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
980	if (PP.isInst())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
981	BC.printInstruction(dbgs(), PP.getInst());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), *PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
982	elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
983	dbgs() << PP.getBB()->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false)
984	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for " ; BC.printInstruction(dbgs(), BestPosSave); for (ProgramPoint &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs (), PP.getInst()); else dbgs() << PP.getBB()->getName () << "\n"; }; } } while (false);
985	for (ProgramPoint &PP : Frontier) {
986	bool HasCritEdges = false;
987	if (PP.isInst() && BC.MIB->isTerminator(*PP.getInst()) &&
988	doesInstUsesCSR(*PP.getInst(), CSR)) {
989	Frontier.clear();
990	return Frontier;
991	}
992	BinaryBasicBlock *FrontierBB = Info.getParentBB(PP);
993	CritEdgesFrom.emplace_back(FrontierBB);
994	CritEdgesTo.emplace_back(0);
995	SmallVector<BinaryBasicBlock *, 4> &Dests = CritEdgesTo.back();
996	// Check for invoke instructions at the dominance frontier, which indicates
997	// the landing pad is not dominated.
998	if (PP.isInst() && BC.MIB->isInvoke(*PP.getInst())) {
999	Frontier.clear();
1000	return Frontier;
1001	}
1002	doForAllSuccs(*FrontierBB, [&](ProgramPoint P) {
1003	if (!DA.doesADominateB(*BestPosSave, P)) {
1004	Dests.emplace_back(Info.getParentBB(P));
1005	return;
1006	}
1007	HasCritEdges = true;
1008	});
1009	IsCritEdge.push_back(HasCritEdges);
1010	}
1011	// Restores cannot be placed in empty BBs because we have a dataflow
1012	// analysis that depends on insertions happening before real instructions
1013	// (PredictiveStackPointerTracking). Detect now for empty BBs and add a
1014	// dummy nop that is scheduled to be removed later.
1015	bool InvalidateRequired = false;
1016	for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
1017	if (BB->size() != 0)
1018	continue;
1019	MCInst NewInst;
1020	BC.MIB->createNoop(NewInst);
1021	auto II = BB->addInstruction(std::move(NewInst));
1022	scheduleChange(&*II, WorklistItem(WorklistItem::Erase, 0));
1023	InvalidateRequired = true;
1024	}
1025	if (std::accumulate(IsCritEdge.begin(), IsCritEdge.end(), 0)) {
1026	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1027	dbgs() << "Now detected critical edges in the following frontier:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1028	for (ProgramPoint &PP : Frontier) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1029	if (PP.isBB()) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1030	dbgs() << " BB: " << PP.getBB()->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1031	} else {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1032	dbgs() << " Inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1033	PP.getInst()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1034	}do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1035	}do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false)
1036	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n" ; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs () << " BB: " << PP.getBB()->getName() << "\n"; } else { dbgs() << " Inst: "; PP.getInst()-> dump(); } } }; } } while (false);
1037	splitFrontierCritEdges(&BF, Frontier, IsCritEdge, CritEdgesFrom,
1038	CritEdgesTo);
1039	InvalidateRequired = true;
1040	}
1041	if (InvalidateRequired) {
1042	// BitVectors that represent all insns of the function are invalid now
1043	// since we changed BBs/Insts. Re-run steps that depend on pointers being
1044	// valid
1045	Info.invalidateAll();
1046	classifyCSRUses();
1047	}
1048	return Frontier;
1049	}
1050
1051	bool ShrinkWrapping::validatePushPopsMode(unsigned CSR, MCInst *BestPosSave,
1052	int64_t SaveOffset) {
1053	if (FA.requiresAlignment(BF)) {
1054	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "alignment requirements.\n" ; }; } } while (false)
1055	dbgs() << "Reg " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "alignment requirements.\n" ; }; } } while (false)
1056	<< " is not using push/pops due to function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "alignment requirements.\n" ; }; } } while (false)
1057	"alignment requirements.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "alignment requirements.\n" ; }; } } while (false)
1058	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "alignment requirements.\n" ; }; } } while (false);
1059	return false;
1060	}
1061	if (FA.hasStackArithmetic(BF)) {
1062	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "taking the address of a stack position.\n" ; }; } } while (false)
1063	dbgs() << "Reg " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "taking the address of a stack position.\n" ; }; } } while (false)
1064	<< " is not using push/pops due to function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "taking the address of a stack position.\n" ; }; } } while (false)
1065	"taking the address of a stack position.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "taking the address of a stack position.\n" ; }; } } while (false)
1066	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " is not using push/pops due to function " "taking the address of a stack position.\n" ; }; } } while (false);
1067	return false;
1068	}
1069	for (MCInst *Save : CSA.getSavesByReg(CSR)) {
1070	if (!SLM.canCollapseRegion(Save)) {
1071	LLVM_DEBUG(dbgs() << "Reg " << CSR << " cannot collapse region.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Reg " << CSR << " cannot collapse region.\n"; } } while (false);
1072	return false;
1073	}
1074	}
1075	// Abort if one of the restores for this CSR is not a POP.
1076	for (MCInst *Load : CSA.getRestoresByReg(CSR)) {
1077	if (!BC.MIB->isPop(*Load)) {
1078	LLVM_DEBUG(dbgs() << "Reg " << CSR << " has a mismatching restore.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Reg " << CSR << " has a mismatching restore.\n"; } } while (false);
1079	return false;
1080	}
1081	}
1082
1083	StackPointerTracking &SPT = Info.getStackPointerTracking();
1084	// Abort if we are inserting a push into an entry BB (offset -8) and this
1085	// func sets up a frame pointer.
1086	if (!SLM.canInsertRegion(BestPosSave) \|\| SaveOffset == SPT.SUPERPOSITION \|\|
1087	SaveOffset == SPT.EMPTY \|\| (SaveOffset == -8 && SPT.HasFramePointer)) {
1088	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " cannot insert region or we are " "trying to insert a push into entry bb.\n" ; }; } } while (false)
1089	dbgs() << "Reg " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " cannot insert region or we are " "trying to insert a push into entry bb.\n" ; }; } } while (false)
1090	<< " cannot insert region or we are "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " cannot insert region or we are " "trying to insert a push into entry bb.\n" ; }; } } while (false)
1091	"trying to insert a push into entry bb.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " cannot insert region or we are " "trying to insert a push into entry bb.\n" ; }; } } while (false)
1092	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Reg " << CSR << " cannot insert region or we are " "trying to insert a push into entry bb.\n" ; }; } } while (false);
1093	return false;
1094	}
1095	return true;
1096	}
1097
1098	SmallVector<ProgramPoint, 4> ShrinkWrapping::fixPopsPlacements(
1099	const SmallVector<ProgramPoint, 4> &RestorePoints, int64_t SaveOffset,
1100	unsigned CSR) {
1101	SmallVector<ProgramPoint, 4> FixedRestorePoints = RestorePoints;
1102	// Moving pop locations to the correct sp offset
1103	ReachingInsns<true> &RI = Info.getReachingInsnsBackwards();
1104	StackPointerTracking &SPT = Info.getStackPointerTracking();
1105	for (ProgramPoint &PP : FixedRestorePoints) {
1106	BinaryBasicBlock *BB = Info.getParentBB(PP);
1107	bool Found = false;
1108	if (SPT.getStateAt(ProgramPoint::getLastPointAt(*BB))->first ==
1109	SaveOffset) {
1110	BitVector BV = RI.getStateAt(ProgramPoint::getLastPointAt(BB));
1111	BV &= UsesByReg[CSR];
1112	if (!BV.any()) {
1113	Found = true;
	Value stored to 'Found' is never read
1114	PP = BB;
1115	continue;
1116	}
1117	}
1118	for (MCInst &Inst : llvm::reverse(*BB)) {
1119	if (SPT.getStateBefore(Inst)->first == SaveOffset) {
1120	BitVector BV = *RI.getStateAt(Inst);
1121	BV &= UsesByReg[CSR];
1122	if (!BV.any()) {
1123	Found = true;
1124	PP = &Inst;
1125	break;
1126	}
1127	}
1128	}
1129	if (!Found) {
1130	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for " << CSR << ", falling back to load/store mode\n"; }; } } while (false)
1131	dbgs() << "Could not find restore insertion point for " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for " << CSR << ", falling back to load/store mode\n"; }; } } while (false)
1132	<< ", falling back to load/store mode\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for " << CSR << ", falling back to load/store mode\n"; }; } } while (false)
1133	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for " << CSR << ", falling back to load/store mode\n"; }; } } while (false);
1134	FixedRestorePoints.clear();
1135	return FixedRestorePoints;
1136	}
1137	}
1138	return FixedRestorePoints;
1139	}
1140
1141	void ShrinkWrapping::scheduleOldSaveRestoresRemoval(unsigned CSR,
1142	bool UsePushPops) {
1143
1144	for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
1145	std::vector<MCInst *> CFIs;
1146	for (MCInst &Inst : llvm::reverse(*BB)) {
1147	if (BC.MIB->isCFI(Inst)) {
1148	// Delete all offset CFIs related to this CSR
1149	if (SLM.getOffsetCFIReg(Inst) == CSR) {
1150	HasDeletedOffsetCFIs[CSR] = true;
1151	scheduleChange(&Inst, WorklistItem(WorklistItem::Erase, CSR));
1152	continue;
1153	}
1154	CFIs.push_back(&Inst);
1155	continue;
1156	}
1157
1158	uint16_t SavedReg = CSA.getSavedReg(Inst);
1159	uint16_t RestoredReg = CSA.getRestoredReg(Inst);
1160	if (SavedReg != CSR && RestoredReg != CSR) {
1161	CFIs.clear();
1162	continue;
1163	}
1164
1165	scheduleChange(&Inst, WorklistItem(UsePushPops
1166	? WorklistItem::Erase
1167	: WorklistItem::ChangeToAdjustment,
1168	CSR));
1169
1170	// Delete associated CFIs
1171	const bool RecordDeletedPushCFIs =
1172	SavedReg == CSR && DeletedPushCFIs[CSR].empty();
1173	const bool RecordDeletedPopCFIs =
1174	RestoredReg == CSR && DeletedPopCFIs[CSR].empty();
1175	for (MCInst *CFI : CFIs) {
1176	const MCCFIInstruction MCCFI = BF.getCFIFor(CFI);
1177	// Do not touch these...
1178	if (MCCFI->getOperation() == MCCFIInstruction::OpRestoreState \|\|
1179	MCCFI->getOperation() == MCCFIInstruction::OpRememberState)
1180	continue;
1181	scheduleChange(CFI, WorklistItem(WorklistItem::Erase, CSR));
1182	if (RecordDeletedPushCFIs) {
1183	// Do not record this to be replayed later because we are going to
1184	// rebuild it.
1185	if (MCCFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
1186	continue;
1187	DeletedPushCFIs[CSR].push_back(CFI->getOperand(0).getImm());
1188	}
1189	if (RecordDeletedPopCFIs) {
1190	if (MCCFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
1191	continue;
1192	DeletedPopCFIs[CSR].push_back(CFI->getOperand(0).getImm());
1193	}
1194	}
1195	CFIs.clear();
1196	}
1197	}
1198	}
1199
1200	bool ShrinkWrapping::doesInstUsesCSR(const MCInst &Inst, uint16_t CSR) {
1201	if (BC.MIB->isCFI(Inst) \|\| CSA.getSavedReg(Inst) == CSR \|\|
1202	CSA.getRestoredReg(Inst) == CSR)
1203	return false;
1204	BitVector BV = BitVector(BC.MRI->getNumRegs(), false);
1205	BC.MIB->getTouchedRegs(Inst, BV);
1206	return BV[CSR];
1207	}
1208
1209	void ShrinkWrapping::scheduleSaveRestoreInsertions(
1210	unsigned CSR, MCInst *BestPosSave,
1211	SmallVector<ProgramPoint, 4> &RestorePoints, bool UsePushPops) {
1212	auto &InsnToBB = Info.getInsnToBBMap();
1213	const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[CSR];
1214	const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[CSR];
1215	assert(FIESave && FIELoad && "Invalid CSR")(static_cast <bool> (FIESave && FIELoad && "Invalid CSR") ? void (0) : __assert_fail ("FIESave && FIELoad && \"Invalid CSR\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1215, __extension__ __PRETTY_FUNCTION__ ));
1216
1217	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: " ; BestPosSave->dump(); }; } } while (false)
1218	dbgs() << "Scheduling save insertion at: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: " ; BestPosSave->dump(); }; } } while (false)
1219	BestPosSave->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: " ; BestPosSave->dump(); }; } } while (false)
1220	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: " ; BestPosSave->dump(); }; } } while (false);
1221
1222	scheduleChange(BestPosSave,
1223	UsePushPops ? WorklistItem::InsertPushOrPop
1224	: WorklistItem::InsertLoadOrStore,
1225	*FIESave, CSR);
1226
1227	for (ProgramPoint &PP : RestorePoints) {
1228	BinaryBasicBlock *FrontierBB = Info.getParentBB(PP);
1229	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false)
1230	dbgs() << "Scheduling restore insertion at: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false)
1231	if (PP.isInst())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false)
1232	PP.getInst()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false)
1233	elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false)
1234	dbgs() << PP.getBB()->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false)
1235	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: " ; if (PP.isInst()) PP.getInst()->dump(); else dbgs() << PP.getBB()->getName() << "\n"; }; } } while (false);
1236	MCInst *Term =
1237	FrontierBB->getTerminatorBefore(PP.isInst() ? PP.getInst() : nullptr);
1238	if (Term)
1239	PP = Term;
1240	bool PrecededByPrefix = false;
1241	if (PP.isInst()) {
1242	auto Iter = FrontierBB->findInstruction(PP.getInst());
1243	if (Iter != FrontierBB->end() && Iter != FrontierBB->begin()) {
1244	--Iter;
1245	PrecededByPrefix = BC.MIB->isPrefix(*Iter);
1246	}
1247	}
1248	if (PP.isInst() &&
1249	(doesInstUsesCSR(*PP.getInst(), CSR) \|\| PrecededByPrefix)) {
1250	assert(!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) &&(static_cast <bool> (!InsnToBB[PP.getInst()]->hasTerminatorAfter (PP.getInst()) && "cannot move to end of bb") ? void ( 0) : __assert_fail ("!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) && \"cannot move to end of bb\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1251, __extension__ __PRETTY_FUNCTION__ ))
1251	"cannot move to end of bb")(static_cast <bool> (!InsnToBB[PP.getInst()]->hasTerminatorAfter (PP.getInst()) && "cannot move to end of bb") ? void ( 0) : __assert_fail ("!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) && \"cannot move to end of bb\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1251, __extension__ __PRETTY_FUNCTION__ ));
1252	scheduleChange(InsnToBB[PP.getInst()],
1253	UsePushPops ? WorklistItem::InsertPushOrPop
1254	: WorklistItem::InsertLoadOrStore,
1255	*FIELoad, CSR);
1256	continue;
1257	}
1258	scheduleChange(PP,
1259	UsePushPops ? WorklistItem::InsertPushOrPop
1260	: WorklistItem::InsertLoadOrStore,
1261	*FIELoad, CSR);
1262	}
1263	}
1264
1265	void ShrinkWrapping::moveSaveRestores() {
1266	bool DisablePushPopMode = false;
1267	bool UsedPushPopMode = false;
1268	// Keeps info about successfully moved regs: reg index, save position and
1269	// save size
1270	std::vector<std::tuple<unsigned, MCInst *, size_t>> MovedRegs;
1271	uint64_t TotalEstimatedWin = 0;
1272
1273	computeDomOrder();
1274	for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
1275	MCInst *BestPosSave = nullptr;
1276	uint64_t EstimatedWin = 0;
1277	SmallVector<ProgramPoint, 4> RestorePoints;
1278	while (RestorePoints.empty() &&
1279	isBestSavePosCold(I, BestPosSave, EstimatedWin)) {
1280	RestorePoints = doRestorePlacement(BestPosSave, I, EstimatedWin);
1281	if (RestorePoints.empty()) {
1282	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed" " -- total est. freq reduc: " << EstimatedWin << ". Will try " << (BestSaveCount[I].size() - 1) << " more times.\n"; }; } } while (false)
1283	dbgs() << "Dropping opportunity because restore placement failed"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed" " -- total est. freq reduc: " << EstimatedWin << ". Will try " << (BestSaveCount[I].size() - 1) << " more times.\n"; }; } } while (false)
1284	" -- total est. freq reduc: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed" " -- total est. freq reduc: " << EstimatedWin << ". Will try " << (BestSaveCount[I].size() - 1) << " more times.\n"; }; } } while (false)
1285	<< EstimatedWin << ". Will try "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed" " -- total est. freq reduc: " << EstimatedWin << ". Will try " << (BestSaveCount[I].size() - 1) << " more times.\n"; }; } } while (false)
1286	<< (BestSaveCount[I].size() - 1) << " more times.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed" " -- total est. freq reduc: " << EstimatedWin << ". Will try " << (BestSaveCount[I].size() - 1) << " more times.\n"; }; } } while (false)
1287	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed" " -- total est. freq reduc: " << EstimatedWin << ". Will try " << (BestSaveCount[I].size() - 1) << " more times.\n"; }; } } while (false);
1288	BestSaveCount[I].pop_back();
1289	BestSavePos[I].pop_back();
1290	computeDomOrder();
1291	}
1292	}
1293	if (RestorePoints.empty()) {
1294	SpillsFailedDynamicCount += EstimatedWin;
1295	continue;
1296	}
1297
1298	const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[I];
1299	const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[I];
1300	(void)FIELoad;
1301	assert(FIESave && FIELoad)(static_cast <bool> (FIESave && FIELoad) ? void (0) : __assert_fail ("FIESave && FIELoad", "bolt/lib/Passes/ShrinkWrapping.cpp" , 1301, __extension__ __PRETTY_FUNCTION__));
1302	StackPointerTracking &SPT = Info.getStackPointerTracking();
1303	const std::pair<int, int> SPFP = SPT.getStateBefore(BestPosSave);
1304	int SaveOffset = SPFP.first;
1305	uint8_t SaveSize = FIESave->Size;
1306
1307	// If we don't know stack state at this point, bail
1308	if ((SPFP.first == SPT.SUPERPOSITION \|\| SPFP.first == SPT.EMPTY) &&
1309	(SPFP.second == SPT.SUPERPOSITION \|\| SPFP.second == SPT.EMPTY)) {
1310	SpillsFailedDynamicCount += EstimatedWin;
1311	continue;
1312	}
1313
1314	// Operation mode: if true, will insert push/pops instead of loads/restores
1315	bool UsePushPops = validatePushPopsMode(I, BestPosSave, SaveOffset);
1316
1317	if (UsePushPops) {
1318	SmallVector<ProgramPoint, 4> FixedRestorePoints =
1319	fixPopsPlacements(RestorePoints, SaveOffset, I);
1320	if (FixedRestorePoints.empty())
1321	UsePushPops = false;
1322	else
1323	RestorePoints = FixedRestorePoints;
1324	}
1325
1326	// Disable push-pop mode for all CSRs in this function
1327	if (!UsePushPops)
1328	DisablePushPopMode = true;
1329	else
1330	UsedPushPopMode = true;
1331
1332	scheduleOldSaveRestoresRemoval(I, UsePushPops);
1333	scheduleSaveRestoreInsertions(I, BestPosSave, RestorePoints, UsePushPops);
1334	MovedRegs.emplace_back(std::make_tuple(I, BestPosSave, SaveSize));
1335	TotalEstimatedWin += EstimatedWin;
1336	}
1337
1338	// Revert push-pop mode if it failed for a single CSR
1339	if (DisablePushPopMode && UsedPushPopMode) {
1340	UsedPushPopMode = false;
1341	for (BinaryBasicBlock &BB : BF) {
1342	auto WRI = Todo.find(&BB);
1343	if (WRI != Todo.end()) {
1344	std::vector<WorklistItem> &TodoList = WRI->second;
1345	for (WorklistItem &Item : TodoList)
1346	if (Item.Action == WorklistItem::InsertPushOrPop)
1347	Item.Action = WorklistItem::InsertLoadOrStore;
1348	}
1349	for (MCInst &Inst : llvm::reverse(BB)) {
1350	auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(
1351	Inst, getAnnotationIndex());
1352	if (!TodoList)
1353	continue;
1354	bool isCFI = BC.MIB->isCFI(Inst);
1355	for (WorklistItem &Item : *TodoList) {
1356	if (Item.Action == WorklistItem::InsertPushOrPop)
1357	Item.Action = WorklistItem::InsertLoadOrStore;
1358	if (!isCFI && Item.Action == WorklistItem::Erase)
1359	Item.Action = WorklistItem::ChangeToAdjustment;
1360	}
1361	}
1362	}
1363	}
1364	SpillsMovedDynamicCount += TotalEstimatedWin;
1365
1366	// Update statistics
1367	if (!UsedPushPopMode) {
1368	SpillsMovedRegularMode += MovedRegs.size();
1369	return;
1370	}
1371
1372	// Schedule modifications to stack-accessing instructions via
1373	// StackLayoutModifier.
1374	SpillsMovedPushPopMode += MovedRegs.size();
1375	for (std::tuple<unsigned, MCInst *, size_t> &I : MovedRegs) {
1376	unsigned RegNdx;
1377	MCInst *SavePos;
1378	size_t SaveSize;
1379	std::tie(RegNdx, SavePos, SaveSize) = I;
1380	for (MCInst *Save : CSA.getSavesByReg(RegNdx))
1381	SLM.collapseRegion(Save);
1382	SLM.insertRegion(SavePos, SaveSize);
1383	}
1384	}
1385
1386	namespace {
1387	/// Helper function to identify whether two basic blocks created by splitting
1388	/// a critical edge have the same contents.
1389	bool isIdenticalSplitEdgeBB(const BinaryContext &BC, const BinaryBasicBlock &A,
1390	const BinaryBasicBlock &B) {
1391	if (A.succ_size() != B.succ_size())
1392	return false;
1393	if (A.succ_size() != 1)
1394	return false;
1395
1396	if (A.succ_begin() != B.succ_begin())
1397	return false;
1398
1399	if (A.size() != B.size())
1400	return false;
1401
1402	// Compare instructions
1403	auto I = A.begin(), E = A.end();
1404	auto OtherI = B.begin(), OtherE = B.end();
1405	while (I != E && OtherI != OtherE) {
1406	if (I->getOpcode() != OtherI->getOpcode())
1407	return false;
1408	if (!BC.MIB->equals(I, OtherI, [](const MCSymbol A, const MCSymbol B) {
1409	return true;
1410	}))
1411	return false;
1412	++I;
1413	++OtherI;
1414	}
1415	return true;
1416	}
1417	} // namespace
1418
1419	bool ShrinkWrapping::foldIdenticalSplitEdges() {
1420	bool Changed = false;
1421	for (auto Iter = BF.begin(); Iter != BF.end(); ++Iter) {
1422	BinaryBasicBlock &BB = *Iter;
1423	if (!BB.getName().startswith(".LSplitEdge"))
1424	continue;
1425	for (BinaryBasicBlock &RBB : llvm::reverse(BF)) {
1426	if (&RBB == &BB)
1427	break;
1428	if (!RBB.getName().startswith(".LSplitEdge") \|\| !RBB.isValid() \|\|
1429	!isIdenticalSplitEdgeBB(BC, *Iter, RBB))
1430	continue;
1431	assert(RBB.pred_size() == 1 && "Invalid split edge BB")(static_cast <bool> (RBB.pred_size() == 1 && "Invalid split edge BB" ) ? void (0) : __assert_fail ("RBB.pred_size() == 1 && \"Invalid split edge BB\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1431, __extension__ __PRETTY_FUNCTION__ ));
1432	BinaryBasicBlock Pred = RBB.pred_begin();
1433	uint64_t OrigCount = Pred->branch_info_begin()->Count;
1434	uint64_t OrigMispreds = Pred->branch_info_begin()->MispredictedCount;
1435	BF.replaceJumpTableEntryIn(Pred, &RBB, &BB);
1436	Pred->replaceSuccessor(&RBB, &BB, OrigCount, OrigMispreds);
1437	Changed = true;
1438	// Remove the block from CFG
1439	RBB.markValid(false);
1440	}
1441	}
1442
1443	return Changed;
1444	}
1445
1446	namespace {
1447
1448	// A special StackPointerTracking that compensates for our future plans
1449	// in removing/adding insn.
1450	class PredictiveStackPointerTracking
1451	: public StackPointerTrackingBase<PredictiveStackPointerTracking> {
1452	friend class DataflowAnalysis<PredictiveStackPointerTracking,
1453	std::pair<int, int>>;
1454	decltype(ShrinkWrapping::Todo) &TodoMap;
1455	DataflowInfoManager &Info;
1456
1457	std::optional<unsigned> AnnotationIndex;
1458
1459	protected:
1460	void compNextAux(const MCInst &Point,
1461	const std::vector<ShrinkWrapping::WorklistItem> &TodoItems,
1462	std::pair<int, int> &Res) {
1463	for (const ShrinkWrapping::WorklistItem &Item : TodoItems) {
1464	if (Item.Action == ShrinkWrapping::WorklistItem::Erase &&
1465	BC.MIB->isPush(Point)) {
1466	Res.first += BC.MIB->getPushSize(Point);
1467	continue;
1468	}
1469	if (Item.Action == ShrinkWrapping::WorklistItem::Erase &&
1470	BC.MIB->isPop(Point)) {
1471	Res.first -= BC.MIB->getPopSize(Point);
1472	continue;
1473	}
1474	if (Item.Action == ShrinkWrapping::WorklistItem::InsertPushOrPop &&
1475	Item.FIEToInsert.IsStore) {
1476	Res.first -= Item.FIEToInsert.Size;
1477	continue;
1478	}
1479	if (Item.Action == ShrinkWrapping::WorklistItem::InsertPushOrPop &&
1480	Item.FIEToInsert.IsLoad) {
1481	Res.first += Item.FIEToInsert.Size;
1482	continue;
1483	}
1484	}
1485	}
1486
1487	std::pair<int, int> computeNext(const MCInst &Point,
1488	const std::pair<int, int> &Cur) {
1489	std::pair<int, int> Res =
1490	StackPointerTrackingBase<PredictiveStackPointerTracking>::computeNext(
1491	Point, Cur);
1492	if (Res.first == StackPointerTracking::SUPERPOSITION \|\|
1493	Res.first == StackPointerTracking::EMPTY)
1494	return Res;
1495	auto TodoItems =
1496	BC.MIB->tryGetAnnotationAs<std::vector<ShrinkWrapping::WorklistItem>>(
1497	Point, ShrinkWrapping::getAnnotationName());
1498	if (TodoItems)
1499	compNextAux(Point, *TodoItems, Res);
1500	auto &InsnToBBMap = Info.getInsnToBBMap();
1501	if (&*InsnToBBMap[&Point]->rbegin() != &Point)
1502	return Res;
1503	auto WRI = TodoMap.find(InsnToBBMap[&Point]);
1504	if (WRI == TodoMap.end())
1505	return Res;
1506	compNextAux(Point, WRI->second, Res);
1507	return Res;
1508	}
1509
1510	StringRef getAnnotationName() const {
1511	return StringRef("PredictiveStackPointerTracking");
1512	}
1513
1514	public:
1515	PredictiveStackPointerTracking(BinaryFunction &BF,
1516	decltype(ShrinkWrapping::Todo) &TodoMap,
1517	DataflowInfoManager &Info,
1518	MCPlusBuilder::AllocatorIdTy AllocatorId = 0)
1519	: StackPointerTrackingBase<PredictiveStackPointerTracking>(BF,
1520	AllocatorId),
1521	TodoMap(TodoMap), Info(Info) {}
1522
1523	void run() {
1524	StackPointerTrackingBase<PredictiveStackPointerTracking>::run();
1525	}
1526	};
1527
1528	} // end anonymous namespace
1529
1530	void ShrinkWrapping::insertUpdatedCFI(unsigned CSR, int SPValPush,
1531	int SPValPop) {
1532	MCInst *SavePoint = nullptr;
1533	for (BinaryBasicBlock &BB : BF) {
1534	for (MCInst &Inst : llvm::reverse(BB)) {
1535	int32_t SrcImm = 0;
1536	MCPhysReg Reg = 0;
1537	MCPhysReg StackPtrReg = 0;
1538	int64_t StackOffset = 0;
1539	bool IsIndexed = false;
1540	bool IsLoad = false;
1541	bool IsStore = false;
1542	bool IsSimple = false;
1543	bool IsStoreFromReg = false;
1544	uint8_t Size = 0;
1545	if (!BC.MIB->isStackAccess(Inst, IsLoad, IsStore, IsStoreFromReg, Reg,
1546	SrcImm, StackPtrReg, StackOffset, Size,
1547	IsSimple, IsIndexed))
1548	continue;
1549	if (Reg != CSR \|\| !IsStore \|\| !IsSimple)
1550	continue;
1551	SavePoint = &Inst;
1552	break;
1553	}
1554	if (SavePoint)
1555	break;
1556	}
1557	assert(SavePoint)(static_cast <bool> (SavePoint) ? void (0) : __assert_fail ("SavePoint", "bolt/lib/Passes/ShrinkWrapping.cpp", 1557, __extension__ __PRETTY_FUNCTION__));
1558	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now using as save point for reg " << CSR << " :"; SavePoint->dump(); }; } } while (false)
1559	dbgs() << "Now using as save point for reg " << CSR << " :";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now using as save point for reg " << CSR << " :"; SavePoint->dump(); }; } } while (false)
1560	SavePoint->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now using as save point for reg " << CSR << " :"; SavePoint->dump(); }; } } while (false)
1561	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now using as save point for reg " << CSR << " :"; SavePoint->dump(); }; } } while (false);
1562	bool PrevAffectedZone = false;
1563	BinaryBasicBlock *PrevBB = nullptr;
1564	DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
1565	for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
1566	if (BB->size() == 0)
1567	continue;
1568	const bool InAffectedZoneAtEnd = DA.count(BB->rbegin(), SavePoint);
1569	const bool InAffectedZoneAtBegin =
1570	(DA.getStateBefore(BB->begin()))[DA.ExprToIdx[SavePoint]];
1571	bool InAffectedZone = InAffectedZoneAtBegin;
1572	for (auto InstIter = BB->begin(); InstIter != BB->end(); ++InstIter) {
1573	const bool CurZone = DA.count(InstIter, SavePoint);
1574	if (InAffectedZone != CurZone) {
1575	auto InsertionIter = InstIter;
1576	++InsertionIter;
1577	InAffectedZone = CurZone;
1578	if (InAffectedZone)
1579	InstIter = insertCFIsForPushOrPop(*BB, InsertionIter, CSR, true, 0,
1580	SPValPop);
1581	else
1582	InstIter = insertCFIsForPushOrPop(*BB, InsertionIter, CSR, false, 0,
1583	SPValPush);
1584	--InstIter;
1585	}
1586	}
1587	// Are we at the first basic block or hot-cold split point?
1588	if (!PrevBB \|\| (BF.isSplit() && BB->isCold() != PrevBB->isCold())) {
1589	if (InAffectedZoneAtBegin)
1590	insertCFIsForPushOrPop(*BB, BB->begin(), CSR, true, 0, SPValPush);
1591	} else if (InAffectedZoneAtBegin != PrevAffectedZone) {
1592	if (InAffectedZoneAtBegin)
1593	insertCFIsForPushOrPop(*PrevBB, PrevBB->end(), CSR, true, 0, SPValPush);
1594	else
1595	insertCFIsForPushOrPop(*PrevBB, PrevBB->end(), CSR, false, 0, SPValPop);
1596	}
1597	PrevAffectedZone = InAffectedZoneAtEnd;
1598	PrevBB = BB;
1599	}
1600	}
1601
1602	void ShrinkWrapping::rebuildCFIForSP() {
1603	for (BinaryBasicBlock &BB : BF) {
1604	for (MCInst &Inst : BB) {
1605	if (!BC.MIB->isCFI(Inst))
1606	continue;
1607	const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
1608	if (CFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
1609	BC.MIB->addAnnotation(Inst, "DeleteMe", 0U, AllocatorId);
1610	}
1611	}
1612
1613	int PrevSPVal = -8;
1614	BinaryBasicBlock *PrevBB = nullptr;
1615	StackPointerTracking &SPT = Info.getStackPointerTracking();
1616	for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
1617	if (BB->size() == 0)
1618	continue;
1619	const int SPValAtEnd = SPT.getStateAt(*BB->rbegin())->first;
1620	const int SPValAtBegin = SPT.getStateBefore(*BB->begin())->first;
1621	int SPVal = SPValAtBegin;
1622	for (auto Iter = BB->begin(); Iter != BB->end(); ++Iter) {
1623	const int CurVal = SPT.getStateAt(*Iter)->first;
1624	if (SPVal != CurVal) {
1625	auto InsertionIter = Iter;
1626	++InsertionIter;
1627	Iter = BF.addCFIInstruction(
1628	BB, InsertionIter,
1629	MCCFIInstruction::cfiDefCfaOffset(nullptr, -CurVal));
1630	SPVal = CurVal;
1631	}
1632	}
1633	if (BF.isSplit() && PrevBB && BB->isCold() != PrevBB->isCold())
1634	BF.addCFIInstruction(
1635	BB, BB->begin(),
1636	MCCFIInstruction::cfiDefCfaOffset(nullptr, -SPValAtBegin));
1637	else if (SPValAtBegin != PrevSPVal)
1638	BF.addCFIInstruction(
1639	PrevBB, PrevBB->end(),
1640	MCCFIInstruction::cfiDefCfaOffset(nullptr, -SPValAtBegin));
1641	PrevSPVal = SPValAtEnd;
1642	PrevBB = BB;
1643	}
1644
1645	for (BinaryBasicBlock &BB : BF)
1646	for (auto I = BB.begin(); I != BB.end();)
1647	if (BC.MIB->hasAnnotation(*I, "DeleteMe"))
1648	I = BB.eraseInstruction(I);
1649	else
1650	++I;
1651	}
1652
1653	MCInst ShrinkWrapping::createStackAccess(int SPVal, int FPVal,
1654	const FrameIndexEntry &FIE,
1655	bool CreatePushOrPop) {
1656	MCInst NewInst;
1657	if (SPVal != StackPointerTracking::SUPERPOSITION &&
1658	SPVal != StackPointerTracking::EMPTY) {
1659	if (FIE.IsLoad) {
1660	if (!BC.MIB->createRestoreFromStack(NewInst, BC.MIB->getStackPointer(),
1661	FIE.StackOffset - SPVal, FIE.RegOrImm,
1662	FIE.Size)) {
1663	errs() << "createRestoreFromStack: not supported on this platform\n";
1664	abort();
1665	}
1666	} else {
1667	if (!BC.MIB->createSaveToStack(NewInst, BC.MIB->getStackPointer(),
1668	FIE.StackOffset - SPVal, FIE.RegOrImm,
1669	FIE.Size)) {
1670	errs() << "createSaveToStack: not supported on this platform\n";
1671	abort();
1672	}
1673	}
1674	if (CreatePushOrPop)
1675	BC.MIB->changeToPushOrPop(NewInst);
1676	return NewInst;
1677	}
1678	assert(FPVal != StackPointerTracking::SUPERPOSITION &&(static_cast <bool> (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY) ? void (0) : __assert_fail ("FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1679, __extension__ __PRETTY_FUNCTION__ ))
1679	FPVal != StackPointerTracking::EMPTY)(static_cast <bool> (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY) ? void (0) : __assert_fail ("FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1679, __extension__ __PRETTY_FUNCTION__ ));
1680
1681	if (FIE.IsLoad) {
1682	if (!BC.MIB->createRestoreFromStack(NewInst, BC.MIB->getFramePointer(),
1683	FIE.StackOffset - FPVal, FIE.RegOrImm,
1684	FIE.Size)) {
1685	errs() << "createRestoreFromStack: not supported on this platform\n";
1686	abort();
1687	}
1688	} else {
1689	if (!BC.MIB->createSaveToStack(NewInst, BC.MIB->getFramePointer(),
1690	FIE.StackOffset - FPVal, FIE.RegOrImm,
1691	FIE.Size)) {
1692	errs() << "createSaveToStack: not supported on this platform\n";
1693	abort();
1694	}
1695	}
1696	return NewInst;
1697	}
1698
1699	void ShrinkWrapping::updateCFIInstOffset(MCInst &Inst, int64_t NewOffset) {
1700	const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
1701	if (UpdatedCFIs.count(CFI))
1702	return;
1703
1704	switch (CFI->getOperation()) {
1705	case MCCFIInstruction::OpDefCfa:
1706	case MCCFIInstruction::OpDefCfaRegister:
1707	case MCCFIInstruction::OpDefCfaOffset:
1708	CFI = BF.mutateCFIOffsetFor(Inst, -NewOffset);
1709	break;
1710	case MCCFIInstruction::OpOffset:
1711	default:
1712	break;
1713	}
1714
1715	UpdatedCFIs.insert(CFI);
1716	}
1717
1718	BBIterTy ShrinkWrapping::insertCFIsForPushOrPop(BinaryBasicBlock &BB,
1719	BBIterTy Pos, unsigned Reg,
1720	bool isPush, int Sz,
1721	int64_t NewOffset) {
1722	if (isPush) {
1723	for (uint32_t Idx : DeletedPushCFIs[Reg]) {
1724	Pos = BF.addCFIPseudo(&BB, Pos, Idx);
1725	updateCFIInstOffset(*Pos++, NewOffset);
1726	}
1727	if (HasDeletedOffsetCFIs[Reg]) {
1728	Pos = BF.addCFIInstruction(
1729	&BB, Pos,
1730	MCCFIInstruction::createOffset(
1731	nullptr, BC.MRI->getDwarfRegNum(Reg, false), NewOffset));
1732	++Pos;
1733	}
1734	} else {
1735	for (uint32_t Idx : DeletedPopCFIs[Reg]) {
1736	Pos = BF.addCFIPseudo(&BB, Pos, Idx);
1737	updateCFIInstOffset(*Pos++, NewOffset);
1738	}
1739	if (HasDeletedOffsetCFIs[Reg]) {
1740	Pos = BF.addCFIInstruction(
1741	&BB, Pos,
1742	MCCFIInstruction::createSameValue(
1743	nullptr, BC.MRI->getDwarfRegNum(Reg, false)));
1744	++Pos;
1745	}
1746	}
1747	return Pos;
1748	}
1749
1750	BBIterTy ShrinkWrapping::processInsertion(BBIterTy InsertionPoint,
1751	BinaryBasicBlock *CurBB,
1752	const WorklistItem &Item,
1753	int64_t SPVal, int64_t FPVal) {
1754	// Trigger CFI reconstruction for this CSR if necessary - writing to
1755	// PushOffsetByReg/PopOffsetByReg will trigger CFI update
1756	if ((Item.FIEToInsert.IsStore &&
1757	!DeletedPushCFIs[Item.AffectedReg].empty()) \|\|
1758	(Item.FIEToInsert.IsLoad && !DeletedPopCFIs[Item.AffectedReg].empty()) \|\|
1759	HasDeletedOffsetCFIs[Item.AffectedReg]) {
1760	if (Item.Action == WorklistItem::InsertPushOrPop) {
1761	if (Item.FIEToInsert.IsStore)
1762	PushOffsetByReg[Item.AffectedReg] = SPVal - Item.FIEToInsert.Size;
1763	else
1764	PopOffsetByReg[Item.AffectedReg] = SPVal;
1765	} else {
1766	if (Item.FIEToInsert.IsStore)
1767	PushOffsetByReg[Item.AffectedReg] = Item.FIEToInsert.StackOffset;
1768	else
1769	PopOffsetByReg[Item.AffectedReg] = Item.FIEToInsert.StackOffset;
1770	}
1771	}
1772
1773	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = " << SPVal << "; stack offset = " << Item.FIEToInsert .StackOffset << " Is push = " << (Item.Action == WorklistItem ::InsertPushOrPop) << "\n"; }; } } while (false)
1774	dbgs() << "Creating stack access with SPVal = " << SPValdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = " << SPVal << "; stack offset = " << Item.FIEToInsert .StackOffset << " Is push = " << (Item.Action == WorklistItem ::InsertPushOrPop) << "\n"; }; } } while (false)
1775	<< "; stack offset = " << Item.FIEToInsert.StackOffsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = " << SPVal << "; stack offset = " << Item.FIEToInsert .StackOffset << " Is push = " << (Item.Action == WorklistItem ::InsertPushOrPop) << "\n"; }; } } while (false)
1776	<< " Is push = " << (Item.Action == WorklistItem::InsertPushOrPop)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = " << SPVal << "; stack offset = " << Item.FIEToInsert .StackOffset << " Is push = " << (Item.Action == WorklistItem ::InsertPushOrPop) << "\n"; }; } } while (false)
1777	<< "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = " << SPVal << "; stack offset = " << Item.FIEToInsert .StackOffset << " Is push = " << (Item.Action == WorklistItem ::InsertPushOrPop) << "\n"; }; } } while (false)
1778	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = " << SPVal << "; stack offset = " << Item.FIEToInsert .StackOffset << " Is push = " << (Item.Action == WorklistItem ::InsertPushOrPop) << "\n"; }; } } while (false);
1779	MCInst NewInst =
1780	createStackAccess(SPVal, FPVal, Item.FIEToInsert,
1781	Item.Action == WorklistItem::InsertPushOrPop);
1782	if (InsertionPoint != CurBB->end()) {
1783	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adding before Inst: " ; InsertionPoint->dump(); dbgs() << "the following inst: " ; NewInst.dump(); }; } } while (false)
1784	dbgs() << "Adding before Inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adding before Inst: " ; InsertionPoint->dump(); dbgs() << "the following inst: " ; NewInst.dump(); }; } } while (false)
1785	InsertionPoint->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adding before Inst: " ; InsertionPoint->dump(); dbgs() << "the following inst: " ; NewInst.dump(); }; } } while (false)
1786	dbgs() << "the following inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adding before Inst: " ; InsertionPoint->dump(); dbgs() << "the following inst: " ; NewInst.dump(); }; } } while (false)
1787	NewInst.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adding before Inst: " ; InsertionPoint->dump(); dbgs() << "the following inst: " ; NewInst.dump(); }; } } while (false)
1788	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Adding before Inst: " ; InsertionPoint->dump(); dbgs() << "the following inst: " ; NewInst.dump(); }; } } while (false);
1789	BBIterTy Iter =
1790	CurBB->insertInstruction(InsertionPoint, std::move(NewInst));
1791	return ++Iter;
1792	}
1793	CurBB->addInstruction(std::move(NewInst));
1794	LLVM_DEBUG(dbgs() << "Adding to BB!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Adding to BB!\n"; } } while (false);
1795	return CurBB->end();
1796	}
1797
1798	BBIterTy ShrinkWrapping::processInsertionsList(
1799	BBIterTy InsertionPoint, BinaryBasicBlock *CurBB,
1800	std::vector<WorklistItem> &TodoList, int64_t SPVal, int64_t FPVal) {
1801	bool HasInsertions = llvm::any_of(TodoList, [&](WorklistItem &Item) {
1802	return Item.Action == WorklistItem::InsertLoadOrStore \|\|
1803	Item.Action == WorklistItem::InsertPushOrPop;
1804	});
1805
1806	if (!HasInsertions)
1807	return InsertionPoint;
1808
1809	assert(((SPVal != StackPointerTracking::SUPERPOSITION &&(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking ::EMPTY)) && "Cannot insert if we have no idea of the stack state here" ) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__ ))
1810	SPVal != StackPointerTracking::EMPTY) \|\|(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking ::EMPTY)) && "Cannot insert if we have no idea of the stack state here" ) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__ ))
1811	(FPVal != StackPointerTracking::SUPERPOSITION &&(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking ::EMPTY)) && "Cannot insert if we have no idea of the stack state here" ) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__ ))
1812	FPVal != StackPointerTracking::EMPTY)) &&(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking ::EMPTY)) && "Cannot insert if we have no idea of the stack state here" ) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__ ))
1813	"Cannot insert if we have no idea of the stack state here")(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking ::EMPTY)) && "Cannot insert if we have no idea of the stack state here" ) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) \|\| (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\"" , "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__ ));
1814
1815	// Revert the effect of PSPT for this location, we want SP Value before
1816	// insertions
1817	if (InsertionPoint == CurBB->end()) {
1818	for (WorklistItem &Item : TodoList) {
1819	if (Item.Action != WorklistItem::InsertPushOrPop)
1820	continue;
1821	if (Item.FIEToInsert.IsStore)
1822	SPVal += Item.FIEToInsert.Size;
1823	if (Item.FIEToInsert.IsLoad)
1824	SPVal -= Item.FIEToInsert.Size;
1825	}
1826	}
1827
1828	// Reorder POPs to obey the correct dominance relation between them
1829	llvm::stable_sort(TodoList, [&](const WorklistItem &A,
1830	const WorklistItem &B) {
1831	if ((A.Action != WorklistItem::InsertPushOrPop \|\| !A.FIEToInsert.IsLoad) &&
1832	(B.Action != WorklistItem::InsertPushOrPop \|\| !B.FIEToInsert.IsLoad))
1833	return false;
1834	if ((A.Action != WorklistItem::InsertPushOrPop \|\| !A.FIEToInsert.IsLoad))
1835	return true;
1836	if ((B.Action != WorklistItem::InsertPushOrPop \|\| !B.FIEToInsert.IsLoad))
1837	return false;
1838	return DomOrder[B.AffectedReg] < DomOrder[A.AffectedReg];
1839	});
1840
1841	// Process insertions
1842	for (WorklistItem &Item : TodoList) {
1843	if (Item.Action == WorklistItem::Erase \|\|
1844	Item.Action == WorklistItem::ChangeToAdjustment)
1845	continue;
1846
1847	InsertionPoint =
1848	processInsertion(InsertionPoint, CurBB, Item, SPVal, FPVal);
1849	if (Item.Action == WorklistItem::InsertPushOrPop &&
1850	Item.FIEToInsert.IsStore)
1851	SPVal -= Item.FIEToInsert.Size;
1852	if (Item.Action == WorklistItem::InsertPushOrPop &&
1853	Item.FIEToInsert.IsLoad)
1854	SPVal += Item.FIEToInsert.Size;
1855	}
1856	return InsertionPoint;
1857	}
1858
1859	bool ShrinkWrapping::processInsertions() {
1860	PredictiveStackPointerTracking PSPT(BF, Todo, Info, AllocatorId);
1861	PSPT.run();
1862
1863	bool Changes = false;
1864	for (BinaryBasicBlock &BB : BF) {
1865	// Process insertions before some inst.
1866	for (auto I = BB.begin(); I != BB.end(); ++I) {
1867	MCInst &Inst = *I;
1868	auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(
1869	Inst, getAnnotationIndex());
1870	if (!TodoList)
1871	continue;
1872	Changes = true;
1873	std::vector<WorklistItem> List = *TodoList;
1874	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now processing insertions in " << BB.getName() << " before inst: "; Inst.dump() ; }; } } while (false)
1875	dbgs() << "Now processing insertions in " << BB.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now processing insertions in " << BB.getName() << " before inst: "; Inst.dump() ; }; } } while (false)
1876	<< " before inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now processing insertions in " << BB.getName() << " before inst: "; Inst.dump() ; }; } } while (false)
1877	Inst.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now processing insertions in " << BB.getName() << " before inst: "; Inst.dump() ; }; } } while (false)
1878	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Now processing insertions in " << BB.getName() << " before inst: "; Inst.dump() ; }; } } while (false);
1879	auto Iter = I;
1880	std::pair<int, int> SPTState =
1881	PSPT.getStateAt(Iter == BB.begin() ? (ProgramPoint)&BB : &(--Iter));
1882	I = processInsertionsList(I, &BB, List, SPTState.first, SPTState.second);
1883	}
1884	// Process insertions at the end of bb
1885	auto WRI = Todo.find(&BB);
1886	if (WRI != Todo.end()) {
1887	std::pair<int, int> SPTState = PSPT.getStateAt(BB.rbegin());
1888	processInsertionsList(BB.end(), &BB, WRI->second, SPTState.first,
1889	SPTState.second);
1890	Changes = true;
1891	}
1892	}
1893	return Changes;
1894	}
1895
1896	void ShrinkWrapping::processDeletions() {
1897	LivenessAnalysis &LA = Info.getLivenessAnalysis();
1898	for (BinaryBasicBlock &BB : BF) {
1899	for (auto II = BB.begin(); II != BB.end(); ++II) {
1900	MCInst &Inst = *II;
1901	auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(
1902	Inst, getAnnotationIndex());
1903	if (!TodoList)
1904	continue;
1905	// Process all deletions
1906	for (WorklistItem &Item : *TodoList) {
1907	if (Item.Action != WorklistItem::Erase &&
1908	Item.Action != WorklistItem::ChangeToAdjustment)
1909	continue;
1910
1911	if (Item.Action == WorklistItem::ChangeToAdjustment) {
1912	// Is flag reg alive across this func?
1913	bool DontClobberFlags = LA.isAlive(&Inst, BC.MIB->getFlagsReg());
1914	if (int Sz = BC.MIB->getPushSize(Inst)) {
1915	BC.MIB->createStackPointerIncrement(Inst, Sz, DontClobberFlags);
1916	continue;
1917	}
1918	if (int Sz = BC.MIB->getPopSize(Inst)) {
1919	BC.MIB->createStackPointerDecrement(Inst, Sz, DontClobberFlags);
1920	continue;
1921	}
1922	}
1923
1924	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction (dbgs(), Inst); }; } } while (false)
1925	dbgs() << "Erasing: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction (dbgs(), Inst); }; } } while (false)
1926	BC.printInstruction(dbgs(), Inst);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction (dbgs(), Inst); }; } } while (false)
1927	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction (dbgs(), Inst); }; } } while (false);
1928	II = std::prev(BB.eraseInstruction(II));
1929	break;
1930	}
1931	}
1932	}
1933	}
1934
1935	void ShrinkWrapping::rebuildCFI() {
1936	const bool FP = Info.getStackPointerTracking().HasFramePointer;
1937	Info.invalidateAll();
1938	if (!FP) {
1939	rebuildCFIForSP();
1940	Info.invalidateAll();
1941	}
1942	for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
1943	if (PushOffsetByReg[I] == 0 \|\| PopOffsetByReg[I] == 0)
1944	continue;
1945	const int64_t SPValPush = PushOffsetByReg[I];
1946	const int64_t SPValPop = PopOffsetByReg[I];
1947	insertUpdatedCFI(I, SPValPush, SPValPop);
1948	Info.invalidateAll();
1949	}
1950	}
1951
1952	bool ShrinkWrapping::perform(bool HotOnly) {
1953	HasDeletedOffsetCFIs = BitVector(BC.MRI->getNumRegs(), false);
1954	PushOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
1955	PopOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
1956
1957	// Update pass statistics
1958	uint64_t TotalInstrs = 0ULL;
1959	uint64_t TotalStoreInstrs = 0ULL;
1960	for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
1961	uint64_t BBExecCount = BB->getExecutionCount();
1962	if (!BBExecCount \|\| BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
1963	continue;
1964	for (const auto &Instr : *BB) {
1965	if (BC.MIB->isPseudo(Instr))
1966	continue;
1967	if (BC.MIB->isStore(Instr))
1968	TotalStoreInstrs += BBExecCount;
1969	TotalInstrs += BBExecCount;
1970	}
1971	}
1972	InstrDynamicCount += TotalInstrs;
1973	StoreDynamicCount += TotalStoreInstrs;
1974
1975	if (!FA.hasFrameInfo(BF))
1976	return false;
1977
1978	if (HotOnly && (BF.getKnownExecutionCount() < BC.getHotThreshold()))
1979	return false;
1980
1981	if (opts::EqualizeBBCounts)
1982	equalizeBBCounts(Info, BF);
1983
1984	if (BF.checkForAmbiguousJumpTables()) {
1985	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName() << ".\n"; } } while (false)
1986	<< ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName() << ".\n"; } } while (false);
1987	// We could call disambiguateJumpTables here, but it is probably not worth
1988	// the cost (of duplicating potentially large jump tables that could regress
1989	// dcache misses). Moreover, ambiguous JTs are rare and coming from code
1990	// written in assembly language. Just bail.
1991	return false;
1992	}
1993	SLM.initialize();
1994	CSA.compute();
1995	classifyCSRUses();
1996	pruneUnwantedCSRs();
1997	computeSaveLocations();
1998	moveSaveRestores();
1999	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n" ; BF.dump(); }; } } while (false)
2000	dbgs() << "Func before shrink-wrapping: \n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n" ; BF.dump(); }; } } while (false)
2001	BF.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n" ; BF.dump(); }; } } while (false)
2002	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n" ; BF.dump(); }; } } while (false);
2003	SLM.performChanges();
2004	// Early exit if processInsertions doesn't detect any todo items
2005	if (!processInsertions())
2006	return false;
2007	processDeletions();
2008	if (foldIdenticalSplitEdges()) {
2009	const std::pair<unsigned, uint64_t> Stats = BF.eraseInvalidBBs();
2010	(void)Stats;
2011	LLVM_DEBUG(dbgs() << "Deleted " << Stats.firstdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Deleted " << Stats .first << " redundant split edge BBs (" << Stats. second << " bytes) for " << BF.getPrintName() << "\n"; } } while (false)
2012	<< " redundant split edge BBs (" << Stats.seconddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Deleted " << Stats .first << " redundant split edge BBs (" << Stats. second << " bytes) for " << BF.getPrintName() << "\n"; } } while (false)
2013	<< " bytes) for " << BF.getPrintName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { dbgs() << "Deleted " << Stats .first << " redundant split edge BBs (" << Stats. second << " bytes) for " << BF.getPrintName() << "\n"; } } while (false);
2014	}
2015	rebuildCFI();
2016	// We may have split edges, creating BBs that need correct branching
2017	BF.fixBranches();
2018	LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n" ; BF.dump(); }; } } while (false)
2019	dbgs() << "Func after shrink-wrapping: \n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n" ; BF.dump(); }; } } while (false)
2020	BF.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n" ; BF.dump(); }; } } while (false)
2021	})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n" ; BF.dump(); }; } } while (false);
2022	return true;
2023	}
2024
2025	void ShrinkWrapping::printStats() {
2026	outs() << "BOLT-INFO: Shrink wrapping moved " << SpillsMovedRegularMode
2027	<< " spills inserting load/stores and " << SpillsMovedPushPopMode
2028	<< " spills inserting push/pops\n";
2029	if (!InstrDynamicCount \|\| !StoreDynamicCount)
2030	return;
2031	outs() << "BOLT-INFO: Shrink wrapping reduced " << SpillsMovedDynamicCount
2032	<< " store executions ("
2033	<< format("%.1lf%%",
2034	(100.0 * SpillsMovedDynamicCount / InstrDynamicCount))
2035	<< " total instructions executed, "
2036	<< format("%.1lf%%",
2037	(100.0 * SpillsMovedDynamicCount / StoreDynamicCount))
2038	<< " store instructions)\n";
2039	outs() << "BOLT-INFO: Shrink wrapping failed at reducing "
2040	<< SpillsFailedDynamicCount << " store executions ("
2041	<< format("%.1lf%%",
2042	(100.0 * SpillsFailedDynamicCount / InstrDynamicCount))
2043	<< " total instructions executed, "
2044	<< format("%.1lf%%",
2045	(100.0 * SpillsFailedDynamicCount / StoreDynamicCount))
2046	<< " store instructions)\n";
2047	}
2048
2049	// Operators necessary as a result of using MCAnnotation
2050	raw_ostream &operator<<(raw_ostream &OS,
2051	const std::vector<ShrinkWrapping::WorklistItem> &Vec) {
2052	OS << "SWTodo[";
2053	const char *Sep = "";
2054	for (const ShrinkWrapping::WorklistItem &Item : Vec) {
2055	OS << Sep;
2056	switch (Item.Action) {
2057	case ShrinkWrapping::WorklistItem::Erase:
2058	OS << "Erase";
2059	break;
2060	case ShrinkWrapping::WorklistItem::ChangeToAdjustment:
2061	OS << "ChangeToAdjustment";
2062	break;
2063	case ShrinkWrapping::WorklistItem::InsertLoadOrStore:
2064	OS << "InsertLoadOrStore";
2065	break;
2066	case ShrinkWrapping::WorklistItem::InsertPushOrPop:
2067	OS << "InsertPushOrPop";
2068	break;
2069	}
2070	Sep = ", ";
2071	}
2072	OS << "]";
2073	return OS;
2074	}
2075
2076	raw_ostream &
2077	operator<<(raw_ostream &OS,
2078	const std::vector<StackLayoutModifier::WorklistItem> &Vec) {
2079	OS << "SLMTodo[";
2080	const char *Sep = "";
2081	for (const StackLayoutModifier::WorklistItem &Item : Vec) {
2082	OS << Sep;
2083	switch (Item.Action) {
2084	case StackLayoutModifier::WorklistItem::None:
2085	OS << "None";
2086	break;
2087	case StackLayoutModifier::WorklistItem::AdjustLoadStoreOffset:
2088	OS << "AdjustLoadStoreOffset";
2089	break;
2090	case StackLayoutModifier::WorklistItem::AdjustCFI:
2091	OS << "AdjustCFI";
2092	break;
2093	}
2094	Sep = ", ";
2095	}
2096	OS << "]";
2097	return OS;
2098	}
2099
2100	bool operator==(const ShrinkWrapping::WorklistItem &A,
2101	const ShrinkWrapping::WorklistItem &B) {
2102	return (A.Action == B.Action && A.AffectedReg == B.AffectedReg &&
2103	A.Adjustment == B.Adjustment &&
2104	A.FIEToInsert.IsLoad == B.FIEToInsert.IsLoad &&
2105	A.FIEToInsert.IsStore == B.FIEToInsert.IsStore &&
2106	A.FIEToInsert.RegOrImm == B.FIEToInsert.RegOrImm &&
2107	A.FIEToInsert.Size == B.FIEToInsert.Size &&
2108	A.FIEToInsert.IsSimple == B.FIEToInsert.IsSimple &&
2109	A.FIEToInsert.StackOffset == B.FIEToInsert.StackOffset);
2110	}
2111
2112	bool operator==(const StackLayoutModifier::WorklistItem &A,
2113	const StackLayoutModifier::WorklistItem &B) {
2114	return (A.Action == B.Action && A.OffsetUpdate == B.OffsetUpdate);
2115	}
2116
2117	} // end namespace bolt
2118	} // end namespace llvm