Bug Summary

File:build/source/bolt/lib/Passes/ShrinkWrapping.cpp
Warning:line 1651, column 19
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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