1//===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===//
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 pass looks for safe point where the prologue and epilogue can be
10// inserted.
11// The safe point for the prologue (resp. epilogue) is called Save
12// (resp. Restore).
13// A point is safe for prologue (resp. epilogue) if and only if
14// it 1) dominates (resp. post-dominates) all the frame related operations and
15// between 2) two executions of the Save (resp. Restore) point there is an
16// execution of the Restore (resp. Save) point.
17//
18// For instance, the following points are safe:
19// for (int i = 0; i < 10; ++i) {
20// Save
21// ...
22// Restore
23// }
24// Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
25// And the following points are not:
26// for (int i = 0; i < 10; ++i) {
27// Save
28// ...
29// }
30// for (int i = 0; i < 10; ++i) {
31// ...
32// Restore
33// }
34// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
35//
36// This pass also ensures that the safe points are 3) cheaper than the regular
37// entry and exits blocks.
38//
39// Property #1 is ensured via the use of MachineDominatorTree and
40// MachinePostDominatorTree.
41// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
42// points must be in the same loop.
43// Property #3 is ensured via the MachineBlockFrequencyInfo.
44//
45// If this pass found points matching all these properties, then
46// MachineFrameInfo is updated with this information.
47//
48//===----------------------------------------------------------------------===//
49
50#include "llvm/CodeGen/ShrinkWrap.h"
51#include "CodeGenOptions.h"
52#include "llvm/ADT/BitVector.h"
53#include "llvm/ADT/PostOrderIterator.h"
54#include "llvm/ADT/SetVector.h"
55#include "llvm/ADT/SmallVector.h"
56#include "llvm/ADT/Statistic.h"
57#include "llvm/Analysis/CFG.h"
58#include "llvm/Analysis/ValueTracking.h"
59#include "llvm/CodeGen/MachineBasicBlock.h"
60#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
61#include "llvm/CodeGen/MachineDominators.h"
62#include "llvm/CodeGen/MachineFrameInfo.h"
63#include "llvm/CodeGen/MachineFunction.h"
64#include "llvm/CodeGen/MachineFunctionPass.h"
65#include "llvm/CodeGen/MachineInstr.h"
66#include "llvm/CodeGen/MachineLoopInfo.h"
67#include "llvm/CodeGen/MachineOperand.h"
68#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
69#include "llvm/CodeGen/MachinePostDominators.h"
70#include "llvm/CodeGen/RegisterClassInfo.h"
71#include "llvm/CodeGen/RegisterScavenging.h"
72#include "llvm/CodeGen/TargetFrameLowering.h"
73#include "llvm/CodeGen/TargetInstrInfo.h"
74#include "llvm/CodeGen/TargetLowering.h"
75#include "llvm/CodeGen/TargetRegisterInfo.h"
76#include "llvm/CodeGen/TargetSubtargetInfo.h"
77#include "llvm/IR/Attributes.h"
78#include "llvm/IR/Function.h"
79#include "llvm/InitializePasses.h"
80#include "llvm/MC/MCAsmInfo.h"
81#include "llvm/Pass.h"
82#include "llvm/Support/Debug.h"
83#include "llvm/Support/ErrorHandling.h"
84#include "llvm/Support/raw_ostream.h"
85#include "llvm/Target/TargetMachine.h"
86#include <cassert>
87#include <memory>
88
89using namespace llvm;
90
91#define DEBUG_TYPE "shrink-wrap"
92
93STATISTIC(NumFunc, "Number of functions");
94STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
95STATISTIC(NumCandidatesDropped,
96 "Number of shrink-wrapping candidates dropped because of frequency");
97
98namespace {
99
100/// Class to determine where the safe point to insert the
101/// prologue and epilogue are.
102/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
103/// shrink-wrapping term for prologue/epilogue placement, this pass
104/// does not rely on expensive data-flow analysis. Instead we use the
105/// dominance properties and loop information to decide which point
106/// are safe for such insertion.
107class ShrinkWrapImpl {
108 /// Hold callee-saved information.
109 const RegisterClassInfo *RCI = nullptr;
110 MachineDominatorTree *MDT = nullptr;
111 MachinePostDominatorTree *MPDT = nullptr;
112
113 /// Current safe point found for the prologue.
114 /// The prologue will be inserted before the first instruction
115 /// in this basic block.
116 MachineBasicBlock *Save = nullptr;
117
118 /// Current safe point found for the epilogue.
119 /// The epilogue will be inserted before the first terminator instruction
120 /// in this basic block.
121 MachineBasicBlock *Restore = nullptr;
122
123 /// Hold the information of the basic block frequency.
124 /// Use to check the profitability of the new points.
125 MachineBlockFrequencyInfo *MBFI = nullptr;
126
127 /// Hold the loop information. Used to determine if Save and Restore
128 /// are in the same loop.
129 MachineLoopInfo *MLI = nullptr;
130
131 // Emit remarks.
132 MachineOptimizationRemarkEmitter *ORE = nullptr;
133
134 /// Frequency of the Entry block.
135 BlockFrequency EntryFreq;
136
137 /// Current opcode for frame setup.
138 unsigned FrameSetupOpcode = ~0u;
139
140 /// Current opcode for frame destroy.
141 unsigned FrameDestroyOpcode = ~0u;
142
143 /// Stack pointer register, used by llvm.{savestack,restorestack}
144 Register SP;
145
146 /// Entry block.
147 const MachineBasicBlock *Entry = nullptr;
148
149 using SetOfRegs = SmallSetVector<unsigned, 16>;
150
151 /// Registers that need to be saved for the current function.
152 mutable SetOfRegs CurrentCSRs;
153
154 /// Current MachineFunction.
155 MachineFunction *MachineFunc = nullptr;
156
157 /// Is `true` for the block numbers where we assume possible stack accesses
158 /// or computation of stack-relative addresses on any CFG path including the
159 /// block itself. Is `false` for basic blocks where we can guarantee the
160 /// opposite. False positives won't lead to incorrect analysis results,
161 /// therefore this approach is fair.
162 BitVector StackAddressUsedBlockInfo;
163
164 /// Check if \p MI uses or defines a callee-saved register or
165 /// a frame index. If this is the case, this means \p MI must happen
166 /// after Save and before Restore.
167 bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
168 bool StackAddressUsed) const;
169
170 const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {
171 if (CurrentCSRs.empty()) {
172 BitVector SavedRegs;
173 const TargetFrameLowering *TFI =
174 MachineFunc->getSubtarget().getFrameLowering();
175
176 TFI->determineCalleeSaves(MF&: *MachineFunc, SavedRegs, RS);
177
178 for (int Reg = SavedRegs.find_first(); Reg != -1;
179 Reg = SavedRegs.find_next(Prev: Reg))
180 CurrentCSRs.insert(X: (unsigned)Reg);
181 }
182 return CurrentCSRs;
183 }
184
185 /// Update the Save and Restore points such that \p MBB is in
186 /// the region that is dominated by Save and post-dominated by Restore
187 /// and Save and Restore still match the safe point definition.
188 /// Such point may not exist and Save and/or Restore may be null after
189 /// this call.
190 void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
191
192 // Try to find safe point based on dominance and block frequency without
193 // any change in IR.
194 bool performShrinkWrapping(
195 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
196 RegScavenger *RS);
197
198 /// This function tries to split the restore point if doing so can shrink the
199 /// save point further. \return True if restore point is split.
200 bool postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
201 RegScavenger *RS);
202
203 /// This function analyzes if the restore point can split to create a new
204 /// restore point. This function collects
205 /// 1. Any preds of current restore that are reachable by callee save/FI
206 /// blocks
207 /// - indicated by DirtyPreds
208 /// 2. Any preds of current restore that are not DirtyPreds - indicated by
209 /// CleanPreds
210 /// Both sets should be non-empty for considering restore point split.
211 bool checkIfRestoreSplittable(
212 const MachineBasicBlock *CurRestore,
213 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
214 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,
215 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,
216 const TargetInstrInfo *TII, RegScavenger *RS);
217
218 /// Initialize the pass for \p MF.
219 void init(MachineFunction &MF) {
220 Save = nullptr;
221 Restore = nullptr;
222 EntryFreq = MBFI->getEntryFreq();
223 const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
224 const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
225 FrameSetupOpcode = TII.getCallFrameSetupOpcode();
226 FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
227 SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore();
228 Entry = &MF.front();
229 CurrentCSRs.clear();
230 MachineFunc = &MF;
231
232 ++NumFunc;
233 }
234
235 /// Check whether or not Save and Restore points are still interesting for
236 /// shrink-wrapping.
237 bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
238
239public:
240 ShrinkWrapImpl(const RegisterClassInfo *RCI, MachineDominatorTree *MDT,
241 MachinePostDominatorTree *MPDT,
242 MachineBlockFrequencyInfo *MBFI, MachineLoopInfo *MLI,
243 MachineOptimizationRemarkEmitter *ORE)
244 : RCI(RCI), MDT(MDT), MPDT(MPDT), MBFI(MBFI), MLI(MLI), ORE(ORE) {}
245
246 /// Check if shrink wrapping is enabled for this target and function.
247 static bool isShrinkWrapEnabled(const MachineFunction &MF);
248
249 bool run(MachineFunction &MF);
250};
251
252class ShrinkWrapLegacy : public MachineFunctionPass {
253public:
254 static char ID;
255
256 ShrinkWrapLegacy() : MachineFunctionPass(ID) {}
257
258 void getAnalysisUsage(AnalysisUsage &AU) const override {
259 AU.setPreservesAll();
260 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
261 AU.addRequired<MachineDominatorTreeWrapperPass>();
262 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
263 AU.addRequired<MachineLoopInfoWrapperPass>();
264 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
265 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
266 MachineFunctionPass::getAnalysisUsage(AU);
267 }
268
269 MachineFunctionProperties getRequiredProperties() const override {
270 return MachineFunctionProperties().setNoVRegs();
271 }
272
273 StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
274
275 /// Perform the shrink-wrapping analysis and update
276 /// the MachineFrameInfo attached to \p MF with the results.
277 bool runOnMachineFunction(MachineFunction &MF) override;
278};
279
280} // end anonymous namespace
281
282char ShrinkWrapLegacy::ID = 0;
283
284char &llvm::ShrinkWrapID = ShrinkWrapLegacy::ID;
285
286INITIALIZE_PASS_BEGIN(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,
287 false)
288INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
289INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
290INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
291INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
292INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
293INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
294INITIALIZE_PASS_END(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,
295 false)
296
297bool ShrinkWrapImpl::useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
298 bool StackAddressUsed) const {
299 /// Check if \p Op is known to access an address not on the function's stack .
300 /// At the moment, accesses where the underlying object is a global, function
301 /// argument, or jump table are considered non-stack accesses. Note that the
302 /// caller's stack may get accessed when passing an argument via the stack,
303 /// but not the stack of the current function.
304 ///
305 auto IsKnownNonStackPtr = [](MachineMemOperand *Op) {
306 if (Op->getValue()) {
307 SmallVector<const Value *, 2> Objs;
308 getUnderlyingObjects(V: Op->getValue(), Objects&: Objs);
309 return !Objs.empty() && all_of(Range&: Objs, P: [](const Value *UO) {
310 if (auto *Arg = dyn_cast<Argument>(Val: UO))
311 return !Arg->hasPassPointeeByValueCopyAttr();
312 return isa<GlobalValue>(Val: UO);
313 });
314 }
315 if (const PseudoSourceValue *PSV = Op->getPseudoValue())
316 return PSV->isJumpTable() || PSV->isConstantPool();
317 return false;
318 };
319 // Load/store operations may access the stack indirectly when we previously
320 // computed an address to a stack location.
321 if (StackAddressUsed && MI.mayLoadOrStore() &&
322 (MI.isCall() || MI.hasUnmodeledSideEffects() || MI.memoperands_empty() ||
323 !all_of(Range: MI.memoperands(), P: IsKnownNonStackPtr)))
324 return true;
325
326 if (MI.getOpcode() == FrameSetupOpcode ||
327 MI.getOpcode() == FrameDestroyOpcode) {
328 LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
329 return true;
330 }
331 const MachineFunction *MF = MI.getParent()->getParent();
332 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
333 for (const MachineOperand &MO : MI.operands()) {
334 bool UseOrDefCSR = false;
335 if (MO.isReg()) {
336 // Ignore instructions like DBG_VALUE which don't read/def the register.
337 if (!MO.isDef() && !MO.readsReg())
338 continue;
339 Register PhysReg = MO.getReg();
340 if (!PhysReg)
341 continue;
342 assert(PhysReg.isPhysical() && "Unallocated register?!");
343 // The stack pointer is not normally described as a callee-saved register
344 // in calling convention definitions, so we need to watch for it
345 // separately. An SP mentioned by a call instruction, we can ignore,
346 // though, as it's harmless and we do not want to effectively disable tail
347 // calls by forcing the restore point to post-dominate them.
348 // PPC's LR is also not normally described as a callee-saved register in
349 // calling convention definitions, so we need to watch for it, too. An LR
350 // mentioned implicitly by a return (or "branch to link register")
351 // instruction we can ignore, otherwise we may pessimize shrinkwrapping.
352 // PPC's Frame pointer (FP) is also not described as a callee-saved
353 // register. Until the FP is assigned a Physical Register PPC's FP needs
354 // to be checked separately.
355 UseOrDefCSR = (!MI.isCall() && PhysReg == SP) ||
356 RCI->getLastCalleeSavedAlias(PhysReg) ||
357 (!MI.isReturn() &&
358 TRI->isNonallocatableRegisterCalleeSave(Reg: PhysReg)) ||
359 TRI->isVirtualFrameRegister(Reg: PhysReg);
360 } else if (MO.isRegMask()) {
361 // Check if this regmask clobbers any of the CSRs.
362 for (unsigned Reg : getCurrentCSRs(RS)) {
363 if (MO.clobbersPhysReg(PhysReg: Reg)) {
364 UseOrDefCSR = true;
365 break;
366 }
367 }
368 }
369 // Skip FrameIndex operands in DBG_VALUE instructions.
370 if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
371 LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
372 << MO.isFI() << "): " << MI << '\n');
373 return true;
374 }
375 }
376 return false;
377}
378
379/// Helper function to find the immediate (post) dominator.
380template <typename ListOfBBs, typename DominanceAnalysis>
381static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
382 DominanceAnalysis &Dom, bool Strict = true) {
383 if (BBs.begin() == BBs.end())
384 return Strict ? nullptr : &Block;
385 MachineBasicBlock *IDom = Dom.findNearestCommonDominator(iterator_range(BBs));
386 if (Strict && IDom == &Block)
387 return nullptr;
388 return IDom;
389}
390
391static bool isAnalyzableBB(const TargetInstrInfo &TII,
392 MachineBasicBlock &Entry) {
393 // Check if the block is analyzable.
394 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
395 SmallVector<MachineOperand, 4> Cond;
396 return !TII.analyzeBranch(MBB&: Entry, TBB, FBB, Cond);
397}
398
399/// Determines if any predecessor of MBB is on the path from block that has use
400/// or def of CSRs/FI to MBB.
401/// ReachableByDirty: All blocks reachable from block that has use or def of
402/// CSR/FI.
403static bool
404hasDirtyPred(const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
405 const MachineBasicBlock &MBB) {
406 for (const MachineBasicBlock *PredBB : MBB.predecessors())
407 if (ReachableByDirty.count(V: PredBB))
408 return true;
409 return false;
410}
411
412/// Derives the list of all the basic blocks reachable from MBB.
413static void markAllReachable(DenseSet<const MachineBasicBlock *> &Visited,
414 const MachineBasicBlock &MBB) {
415 SmallVector<MachineBasicBlock *, 4> Worklist(MBB.successors());
416 Visited.insert(V: &MBB);
417 while (!Worklist.empty()) {
418 MachineBasicBlock *SuccMBB = Worklist.pop_back_val();
419 if (!Visited.insert(V: SuccMBB).second)
420 continue;
421 Worklist.append(in_start: SuccMBB->succ_begin(), in_end: SuccMBB->succ_end());
422 }
423}
424
425/// Collect blocks reachable by use or def of CSRs/FI.
426static void collectBlocksReachableByDirty(
427 const DenseSet<const MachineBasicBlock *> &DirtyBBs,
428 DenseSet<const MachineBasicBlock *> &ReachableByDirty) {
429 for (const MachineBasicBlock *MBB : DirtyBBs) {
430 if (ReachableByDirty.count(V: MBB))
431 continue;
432 // Mark all offsprings as reachable.
433 markAllReachable(Visited&: ReachableByDirty, MBB: *MBB);
434 }
435}
436
437/// \return true if there is a clean path from SavePoint to the original
438/// Restore.
439static bool
440isSaveReachableThroughClean(const MachineBasicBlock *SavePoint,
441 ArrayRef<MachineBasicBlock *> CleanPreds) {
442 DenseSet<const MachineBasicBlock *> Visited;
443 SmallVector<MachineBasicBlock *, 4> Worklist(CleanPreds);
444 while (!Worklist.empty()) {
445 MachineBasicBlock *CleanBB = Worklist.pop_back_val();
446 if (CleanBB == SavePoint)
447 return true;
448 if (!Visited.insert(V: CleanBB).second || !CleanBB->pred_size())
449 continue;
450 Worklist.append(in_start: CleanBB->pred_begin(), in_end: CleanBB->pred_end());
451 }
452 return false;
453}
454
455/// This function updates the branches post restore point split.
456///
457/// Restore point has been split.
458/// Old restore point: MBB
459/// New restore point: NMBB
460/// Any basic block(say BBToUpdate) which had a fallthrough to MBB
461/// previously should
462/// 1. Fallthrough to NMBB iff NMBB is inserted immediately above MBB in the
463/// block layout OR
464/// 2. Branch unconditionally to NMBB iff NMBB is inserted at any other place.
465static void updateTerminator(MachineBasicBlock *BBToUpdate,
466 MachineBasicBlock *NMBB,
467 const TargetInstrInfo *TII) {
468 DebugLoc DL = BBToUpdate->findBranchDebugLoc();
469 // if NMBB isn't the new layout successor for BBToUpdate, insert unconditional
470 // branch to it
471 if (!BBToUpdate->isLayoutSuccessor(MBB: NMBB))
472 TII->insertUnconditionalBranch(MBB&: *BBToUpdate, DestBB: NMBB, DL);
473}
474
475/// This function splits the restore point and returns new restore point/BB.
476///
477/// DirtyPreds: Predessors of \p MBB that are ReachableByDirty
478///
479/// Decision has been made to split the restore point.
480/// old restore point: \p MBB
481/// new restore point: \p NMBB
482/// This function makes the necessary block layout changes so that
483/// 1. \p NMBB points to \p MBB unconditionally
484/// 2. All dirtyPreds that previously pointed to \p MBB point to \p NMBB
485static MachineBasicBlock *
486tryToSplitRestore(MachineBasicBlock *MBB,
487 ArrayRef<MachineBasicBlock *> DirtyPreds,
488 const TargetInstrInfo *TII) {
489 MachineFunction *MF = MBB->getParent();
490
491 // get the list of DirtyPreds who have a fallthrough to MBB
492 // before the block layout change. This is just to ensure that if the NMBB is
493 // inserted after MBB, then we create unconditional branch from
494 // DirtyPred/CleanPred to NMBB
495 SmallPtrSet<MachineBasicBlock *, 8> MBBFallthrough;
496 for (MachineBasicBlock *BB : DirtyPreds)
497 if (BB->getFallThrough(JumpToFallThrough: false) == MBB)
498 MBBFallthrough.insert(Ptr: BB);
499
500 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
501 // Insert this block at the end of the function. Inserting in between may
502 // interfere with control flow optimizer decisions.
503 MF->insert(MBBI: MF->end(), MBB: NMBB);
504
505 for (const MachineBasicBlock::RegisterMaskPair &LI : MBB->liveins())
506 NMBB->addLiveIn(PhysReg: LI.PhysReg);
507
508 TII->insertUnconditionalBranch(MBB&: *NMBB, DestBB: MBB, DL: DebugLoc());
509
510 // After splitting, all predecessors of the restore point should be dirty
511 // blocks.
512 for (MachineBasicBlock *SuccBB : DirtyPreds)
513 SuccBB->ReplaceUsesOfBlockWith(Old: MBB, New: NMBB);
514
515 NMBB->addSuccessor(Succ: MBB);
516
517 for (MachineBasicBlock *BBToUpdate : MBBFallthrough)
518 updateTerminator(BBToUpdate, NMBB, TII);
519
520 return NMBB;
521}
522
523/// This function undoes the restore point split done earlier.
524///
525/// DirtyPreds: All predecessors of \p NMBB that are ReachableByDirty.
526///
527/// Restore point was split and the change needs to be unrolled. Make necessary
528/// changes to reset restore point from \p NMBB to \p MBB.
529static void rollbackRestoreSplit(MachineFunction &MF, MachineBasicBlock *NMBB,
530 MachineBasicBlock *MBB,
531 ArrayRef<MachineBasicBlock *> DirtyPreds,
532 const TargetInstrInfo *TII) {
533 // For a BB, if NMBB is fallthrough in the current layout, then in the new
534 // layout a. BB should fallthrough to MBB OR b. BB should undconditionally
535 // branch to MBB
536 SmallPtrSet<MachineBasicBlock *, 8> NMBBFallthrough;
537 for (MachineBasicBlock *BB : DirtyPreds)
538 if (BB->getFallThrough(JumpToFallThrough: false) == NMBB)
539 NMBBFallthrough.insert(Ptr: BB);
540
541 NMBB->removeSuccessor(Succ: MBB);
542 for (MachineBasicBlock *SuccBB : DirtyPreds)
543 SuccBB->ReplaceUsesOfBlockWith(Old: NMBB, New: MBB);
544
545 NMBB->erase(I: NMBB->begin(), E: NMBB->end());
546 NMBB->eraseFromParent();
547
548 for (MachineBasicBlock *BBToUpdate : NMBBFallthrough)
549 updateTerminator(BBToUpdate, NMBB: MBB, TII);
550}
551
552// A block is deemed fit for restore point split iff there exist
553// 1. DirtyPreds - preds of CurRestore reachable from use or def of CSR/FI
554// 2. CleanPreds - preds of CurRestore that arent DirtyPreds
555bool ShrinkWrapImpl::checkIfRestoreSplittable(
556 const MachineBasicBlock *CurRestore,
557 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
558 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,
559 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,
560 const TargetInstrInfo *TII, RegScavenger *RS) {
561 for (const MachineInstr &MI : *CurRestore)
562 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true))
563 return false;
564
565 for (MachineBasicBlock *PredBB : CurRestore->predecessors()) {
566 if (!isAnalyzableBB(TII: *TII, Entry&: *PredBB))
567 return false;
568
569 if (ReachableByDirty.count(V: PredBB))
570 DirtyPreds.push_back(Elt: PredBB);
571 else
572 CleanPreds.push_back(Elt: PredBB);
573 }
574
575 return !(CleanPreds.empty() || DirtyPreds.empty());
576}
577
578bool ShrinkWrapImpl::postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
579 RegScavenger *RS) {
580 if (!getCodeGenOptions(MF).shrink_wrap_region_split)
581 return false;
582
583 MachineBasicBlock *InitSave = nullptr;
584 MachineBasicBlock *InitRestore = nullptr;
585
586 if (HasCandidate) {
587 InitSave = Save;
588 InitRestore = Restore;
589 } else {
590 InitRestore = nullptr;
591 InitSave = &MF.front();
592 for (MachineBasicBlock &MBB : MF) {
593 if (MBB.isEHFuncletEntry())
594 return false;
595 if (MBB.isReturnBlock()) {
596 // Do not support multiple restore points.
597 if (InitRestore)
598 return false;
599 InitRestore = &MBB;
600 }
601 }
602 }
603
604 if (!InitSave || !InitRestore || InitRestore == InitSave ||
605 !MDT->dominates(A: InitSave, B: InitRestore) ||
606 !MPDT->dominates(A: InitRestore, B: InitSave))
607 return false;
608
609 // Bail out of the optimization if any of the basic block is target of
610 // INLINEASM_BR instruction
611 for (MachineBasicBlock &MBB : MF)
612 if (MBB.isInlineAsmBrIndirectTarget())
613 return false;
614
615 DenseSet<const MachineBasicBlock *> DirtyBBs;
616 for (MachineBasicBlock &MBB : MF) {
617 if (!MDT->isReachableFromEntry(A: &MBB))
618 continue;
619 if (MBB.isEHPad()) {
620 DirtyBBs.insert(V: &MBB);
621 continue;
622 }
623 for (const MachineInstr &MI : MBB)
624 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true)) {
625 DirtyBBs.insert(V: &MBB);
626 break;
627 }
628 }
629
630 // Find blocks reachable from the use or def of CSRs/FI.
631 DenseSet<const MachineBasicBlock *> ReachableByDirty;
632 collectBlocksReachableByDirty(DirtyBBs, ReachableByDirty);
633
634 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
635 SmallVector<MachineBasicBlock *, 2> DirtyPreds;
636 SmallVector<MachineBasicBlock *, 2> CleanPreds;
637 if (!checkIfRestoreSplittable(CurRestore: InitRestore, ReachableByDirty, DirtyPreds,
638 CleanPreds, TII, RS))
639 return false;
640
641 // Trying to reach out to the new save point which dominates all dirty blocks.
642 MachineBasicBlock *NewSave =
643 FindIDom<>(Block&: **DirtyPreds.begin(), BBs: DirtyPreds, Dom&: *MDT, Strict: false);
644
645 while (NewSave && (hasDirtyPred(ReachableByDirty, MBB: *NewSave) ||
646 EntryFreq < MBFI->getBlockFreq(MBB: NewSave) ||
647 /*Entry freq has been observed more than a loop block in
648 some cases*/
649 MLI->getLoopFor(BB: NewSave))) {
650 SmallVector<MachineBasicBlock*> ReachablePreds;
651 for (auto BB: NewSave->predecessors())
652 if (MDT->isReachableFromEntry(A: BB))
653 ReachablePreds.push_back(Elt: BB);
654 if (ReachablePreds.empty())
655 break;
656
657 NewSave = FindIDom<>(Block&: **ReachablePreds.begin(), BBs: ReachablePreds, Dom&: *MDT,
658 Strict: false);
659 }
660
661 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
662 if (!NewSave || NewSave == InitSave ||
663 isSaveReachableThroughClean(SavePoint: NewSave, CleanPreds) ||
664 !TFI->canUseAsPrologue(MBB: *NewSave))
665 return false;
666
667 // Now we know that splitting a restore point can isolate the restore point
668 // from clean blocks and doing so can shrink the save point.
669 MachineBasicBlock *NewRestore =
670 tryToSplitRestore(MBB: InitRestore, DirtyPreds, TII);
671
672 // Make sure if the new restore point is valid as an epilogue, depending on
673 // targets.
674 if (!TFI->canUseAsEpilogue(MBB: *NewRestore)) {
675 rollbackRestoreSplit(MF, NMBB: NewRestore, MBB: InitRestore, DirtyPreds, TII);
676 return false;
677 }
678
679 Save = NewSave;
680 Restore = NewRestore;
681
682 MDT->recalculate(Func&: MF);
683 MPDT->recalculate(Func&: MF);
684
685 assert((MDT->dominates(Save, Restore) && MPDT->dominates(Restore, Save)) &&
686 "Incorrect save or restore point due to dominance relations");
687 assert((!MLI->getLoopFor(Save) && !MLI->getLoopFor(Restore)) &&
688 "Unexpected save or restore point in a loop");
689 assert((EntryFreq >= MBFI->getBlockFreq(Save) &&
690 EntryFreq >= MBFI->getBlockFreq(Restore)) &&
691 "Incorrect save or restore point based on block frequency");
692 return true;
693}
694
695void ShrinkWrapImpl::updateSaveRestorePoints(MachineBasicBlock &MBB,
696 RegScavenger *RS) {
697 // Get rid of the easy cases first.
698 if (!Save)
699 Save = &MBB;
700 else
701 Save = MDT->findNearestCommonDominator(A: Save, B: &MBB);
702 assert(Save);
703
704 if (!Restore)
705 Restore = &MBB;
706 else if (MPDT->getNode(BB: &MBB)) // If the block is not in the post dom tree, it
707 // means the block never returns. If that's the
708 // case, we don't want to call
709 // `findNearestCommonDominator`, which will
710 // return `Restore`.
711 Restore = MPDT->findNearestCommonDominator(A: Restore, B: &MBB);
712 else
713 Restore = nullptr; // Abort, we can't find a restore point in this case.
714
715 // Make sure we would be able to insert the restore code before the
716 // terminator.
717 if (Restore == &MBB) {
718 for (const MachineInstr &Terminator : MBB.terminators()) {
719 if (!useOrDefCSROrFI(MI: Terminator, RS, /*StackAddressUsed=*/true))
720 continue;
721 // One of the terminator needs to happen before the restore point.
722 if (MBB.succ_empty()) {
723 Restore = nullptr; // Abort, we can't find a restore point in this case.
724 break;
725 }
726 // Look for a restore point that post-dominates all the successors.
727 // The immediate post-dominator is what we are looking for.
728 Restore = FindIDom<>(Block&: *Restore, BBs: Restore->successors(), Dom&: *MPDT);
729 break;
730 }
731 }
732
733 if (!Restore) {
734 LLVM_DEBUG(
735 dbgs() << "Restore point needs to be spanned on several blocks\n");
736 return;
737 }
738
739 // Make sure Save and Restore are suitable for shrink-wrapping:
740 // 1. all path from Save needs to lead to Restore before exiting.
741 // 2. all path to Restore needs to go through Save from Entry.
742 // We achieve that by making sure that:
743 // A. Save dominates Restore.
744 // B. Restore post-dominates Save.
745 // C. Save and Restore are in the same loop.
746 bool SaveDominatesRestore = false;
747 bool RestorePostDominatesSave = false;
748 while (Restore &&
749 (!(SaveDominatesRestore = MDT->dominates(A: Save, B: Restore)) ||
750 !(RestorePostDominatesSave = MPDT->dominates(A: Restore, B: Save)) ||
751 // Post-dominance is not enough in loops to ensure that all uses/defs
752 // are after the prologue and before the epilogue at runtime.
753 // E.g.,
754 // while(1) {
755 // Save
756 // Restore
757 // if (...)
758 // break;
759 // use/def CSRs
760 // }
761 // All the uses/defs of CSRs are dominated by Save and post-dominated
762 // by Restore. However, the CSRs uses are still reachable after
763 // Restore and before Save are executed.
764 //
765 // For now, just push the restore/save points outside of loops.
766 // FIXME: Refine the criteria to still find interesting cases
767 // for loops.
768 MLI->getLoopFor(BB: Save) || MLI->getLoopFor(BB: Restore))) {
769 // Fix (A).
770 if (!SaveDominatesRestore) {
771 Save = MDT->findNearestCommonDominator(A: Save, B: Restore);
772 continue;
773 }
774 // Fix (B).
775 if (!RestorePostDominatesSave)
776 Restore = MPDT->findNearestCommonDominator(A: Restore, B: Save);
777
778 // Fix (C).
779 if (Restore && (MLI->getLoopFor(BB: Save) || MLI->getLoopFor(BB: Restore))) {
780 if (MLI->getLoopDepth(BB: Save) > MLI->getLoopDepth(BB: Restore)) {
781 // Push Save outside of this loop if immediate dominator is different
782 // from save block. If immediate dominator is not different, bail out.
783 SmallVector<MachineBasicBlock *> Preds;
784 for (auto *PBB : Save->predecessors())
785 if (MDT->isReachableFromEntry(A: PBB))
786 Preds.push_back(Elt: PBB);
787 Save = FindIDom<>(Block&: *Save, BBs: Preds, Dom&: *MDT);
788 if (!Save)
789 break;
790 } else {
791 // If the loop does not exit, there is no point in looking
792 // for a post-dominator outside the loop.
793 SmallVector<MachineBasicBlock*, 4> ExitBlocks;
794 MLI->getLoopFor(BB: Restore)->getExitingBlocks(ExitingBlocks&: ExitBlocks);
795 // Push Restore outside of this loop.
796 // Look for the immediate post-dominator of the loop exits.
797 MachineBasicBlock *IPdom = Restore;
798 for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
799 IPdom = FindIDom<>(Block&: *IPdom, BBs: LoopExitBB->successors(), Dom&: *MPDT);
800 if (!IPdom)
801 break;
802 }
803 // If the immediate post-dominator is not in a less nested loop,
804 // then we are stuck in a program with an infinite loop.
805 // In that case, we will not find a safe point, hence, bail out.
806 if (IPdom && MLI->getLoopDepth(BB: IPdom) < MLI->getLoopDepth(BB: Restore))
807 Restore = IPdom;
808 else {
809 Restore = nullptr;
810 break;
811 }
812 }
813 }
814 }
815}
816
817static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE,
818 StringRef RemarkName, StringRef RemarkMessage,
819 const DiagnosticLocation &Loc,
820 const MachineBasicBlock *MBB) {
821 ORE->emit(RemarkBuilder: [&]() {
822 return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)
823 << RemarkMessage;
824 });
825
826 LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
827 return false;
828}
829
830bool ShrinkWrapImpl::performShrinkWrapping(
831 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
832 RegScavenger *RS) {
833 for (MachineBasicBlock *MBB : RPOT) {
834 LLVM_DEBUG(dbgs() << "Look into: " << printMBBReference(*MBB) << '\n');
835
836 if (MBB->isEHFuncletEntry())
837 return giveUpWithRemarks(ORE, RemarkName: "UnsupportedEHFunclets",
838 RemarkMessage: "EH Funclets are not supported yet.",
839 Loc: MBB->front().getDebugLoc(), MBB);
840
841 if (MBB->isEHPad() || MBB->isInlineAsmBrIndirectTarget()) {
842 // Push the prologue and epilogue outside of the region that may throw (or
843 // jump out via inlineasm_br), by making sure that all the landing pads
844 // are at least at the boundary of the save and restore points. The
845 // problem is that a basic block can jump out from the middle in these
846 // cases, which we do not handle.
847 updateSaveRestorePoints(MBB&: *MBB, RS);
848 if (!ArePointsInteresting()) {
849 LLVM_DEBUG(dbgs() << "EHPad/inlineasm_br prevents shrink-wrapping\n");
850 return false;
851 }
852 continue;
853 }
854
855 bool StackAddressUsed = false;
856 // Check if we found any stack accesses in the predecessors. We are not
857 // doing a full dataflow analysis here to keep things simple but just
858 // rely on a reverse portorder traversal (RPOT) to guarantee predecessors
859 // are already processed except for loops (and accept the conservative
860 // result for loops).
861 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
862 if (StackAddressUsedBlockInfo.test(Idx: Pred->getNumber())) {
863 StackAddressUsed = true;
864 break;
865 }
866 }
867
868 for (const MachineInstr &MI : *MBB) {
869 if (useOrDefCSROrFI(MI, RS, StackAddressUsed)) {
870 // Save (resp. restore) point must dominate (resp. post dominate)
871 // MI. Look for the proper basic block for those.
872 updateSaveRestorePoints(MBB&: *MBB, RS);
873 // If we are at a point where we cannot improve the placement of
874 // save/restore instructions, just give up.
875 if (!ArePointsInteresting()) {
876 LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
877 return false;
878 }
879 // No need to look for other instructions, this basic block
880 // will already be part of the handled region.
881 StackAddressUsed = true;
882 break;
883 }
884 }
885 StackAddressUsedBlockInfo[MBB->getNumber()] = StackAddressUsed;
886 }
887 if (!ArePointsInteresting()) {
888 // If the points are not interesting at this point, then they must be null
889 // because it means we did not encounter any frame/CSR related code.
890 // Otherwise, we would have returned from the previous loop.
891 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
892 LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
893 return false;
894 }
895
896 LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: "
897 << EntryFreq.getFrequency() << '\n');
898
899 const TargetFrameLowering *TFI =
900 MachineFunc->getSubtarget().getFrameLowering();
901 do {
902 LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
903 << printMBBReference(*Save) << ' '
904 << printBlockFreq(*MBFI, *Save)
905 << "\nRestore: " << printMBBReference(*Restore) << ' '
906 << printBlockFreq(*MBFI, *Restore) << '\n');
907
908 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
909 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(MBB: Save)) &&
910 EntryFreq >= MBFI->getBlockFreq(MBB: Restore)) &&
911 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(MBB: *Save)) &&
912 TFI->canUseAsEpilogue(MBB: *Restore)))
913 break;
914 LLVM_DEBUG(
915 dbgs() << "New points are too expensive or invalid for the target\n");
916 MachineBasicBlock *NewBB;
917 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
918 Save = FindIDom<>(Block&: *Save, BBs: Save->predecessors(), Dom&: *MDT);
919 if (!Save)
920 break;
921 NewBB = Save;
922 } else {
923 // Restore is expensive.
924 Restore = FindIDom<>(Block&: *Restore, BBs: Restore->successors(), Dom&: *MPDT);
925 if (!Restore)
926 break;
927 NewBB = Restore;
928 }
929 updateSaveRestorePoints(MBB&: *NewBB, RS);
930 } while (Save && Restore);
931
932 if (!ArePointsInteresting()) {
933 ++NumCandidatesDropped;
934 return false;
935 }
936 return true;
937}
938
939bool ShrinkWrapImpl::run(MachineFunction &MF) {
940 LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
941
942 init(MF);
943
944 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
945 if (containsIrreducibleCFG<MachineBasicBlock *>(RPOTraversal&: RPOT, LI: *MLI)) {
946 // If MF is irreducible, a block may be in a loop without
947 // MachineLoopInfo reporting it. I.e., we may use the
948 // post-dominance property in loops, which lead to incorrect
949 // results. Moreover, we may miss that the prologue and
950 // epilogue are not in the same loop, leading to unbalanced
951 // construction/deconstruction of the stack frame.
952 return giveUpWithRemarks(ORE, RemarkName: "UnsupportedIrreducibleCFG",
953 RemarkMessage: "Irreducible CFGs are not supported yet.",
954 Loc: MF.getFunction().getSubprogram(), MBB: &MF.front());
955 }
956
957 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
958 std::unique_ptr<RegScavenger> RS(
959 TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
960
961 bool Changed = false;
962
963 // Initially, conservatively assume that stack addresses can be used in each
964 // basic block and change the state only for those basic blocks for which we
965 // were able to prove the opposite.
966 StackAddressUsedBlockInfo.resize(N: MF.getNumBlockIDs(), t: true);
967 bool HasCandidate = performShrinkWrapping(RPOT, RS: RS.get());
968 StackAddressUsedBlockInfo.clear();
969 Changed = postShrinkWrapping(HasCandidate, MF, RS: RS.get());
970 if (!HasCandidate && !Changed)
971 return false;
972 if (!ArePointsInteresting())
973 return Changed;
974
975 LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
976 << printMBBReference(*Save) << ' '
977 << "\nRestore: " << printMBBReference(*Restore) << '\n');
978
979 MachineFrameInfo &MFI = MF.getFrameInfo();
980
981 // List of CalleeSavedInfo for registers will be added during prologepilog
982 // pass
983 SaveRestorePoints SavePoints({{Save, {}}});
984 SaveRestorePoints RestorePoints({{Restore, {}}});
985
986 MFI.setSavePoints(SavePoints);
987 MFI.setRestorePoints(RestorePoints);
988 ++NumCandidates;
989 return Changed;
990}
991
992bool ShrinkWrapLegacy::runOnMachineFunction(MachineFunction &MF) {
993 if (skipFunction(F: MF.getFunction()) || MF.empty() ||
994 !ShrinkWrapImpl::isShrinkWrapEnabled(MF))
995 return false;
996
997 const RegisterClassInfo *RCI =
998 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
999 MachineDominatorTree *MDT =
1000 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1001 MachinePostDominatorTree *MPDT =
1002 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
1003 MachineBlockFrequencyInfo *MBFI =
1004 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
1005 MachineLoopInfo *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1006 MachineOptimizationRemarkEmitter *ORE =
1007 &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
1008
1009 return ShrinkWrapImpl(RCI, MDT, MPDT, MBFI, MLI, ORE).run(MF);
1010}
1011
1012PreservedAnalyses ShrinkWrapPass::run(MachineFunction &MF,
1013 MachineFunctionAnalysisManager &MFAM) {
1014 MFPropsModifier _(*this, MF);
1015 if (MF.empty() || !ShrinkWrapImpl::isShrinkWrapEnabled(MF))
1016 return PreservedAnalyses::all();
1017
1018 const RegisterClassInfo &RCI =
1019 MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
1020 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
1021 MachinePostDominatorTree &MPDT =
1022 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
1023 MachineBlockFrequencyInfo &MBFI =
1024 MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
1025 MachineLoopInfo &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
1026 MachineOptimizationRemarkEmitter &ORE =
1027 MFAM.getResult<MachineOptimizationRemarkEmitterAnalysis>(IR&: MF);
1028
1029 ShrinkWrapImpl(&RCI, &MDT, &MPDT, &MBFI, &MLI, &ORE).run(MF);
1030 return PreservedAnalyses::all();
1031}
1032
1033bool ShrinkWrapImpl::isShrinkWrapEnabled(const MachineFunction &MF) {
1034 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
1035
1036 switch (getCodeGenOptions(MF).shrink_wrap) {
1037 case BoolOrDefault::Default:
1038 return TFI->enableShrinkWrapping(MF) &&
1039 // Windows with CFI has some limitations that make it impossible
1040 // to use shrink-wrapping.
1041 !MF.usesWindowsUnwindInfo() &&
1042 // Sanitizers look at the value of the stack at the location
1043 // of the crash. Since a crash can happen anywhere, the
1044 // frame must be lowered before anything else happen for the
1045 // sanitizers to be able to get a correct stack frame.
1046 !(MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
1047 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeThread) ||
1048 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeConcurrency) ||
1049 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeMemory) ||
1050 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeType) ||
1051 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeHWAddress));
1052 // If EnableShrinkWrap is set, it takes precedence on whatever the
1053 // target sets. The rational is that we assume we want to test
1054 // something related to shrink-wrapping.
1055 case BoolOrDefault::True:
1056 return true;
1057 case BoolOrDefault::False:
1058 return false;
1059 }
1060 llvm_unreachable("Invalid shrink-wrapping state");
1061}
1062