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