1 //===-- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass looks for safe point where the prologue and epilogue can be
12 // The safe point for the prologue (resp. epilogue) is called Save
14 // A point is safe for prologue (resp. epilogue) if and only if
15 // it 1) dominates (resp. post-dominates) all the frame related operations and
16 // between 2) two executions of the Save (resp. Restore) point there is an
17 // execution of the Restore (resp. Save) point.
19 // For instance, the following points are safe:
20 // for (int i = 0; i < 10; ++i) {
25 // Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
26 // And the following points are not:
27 // for (int i = 0; i < 10; ++i) {
31 // for (int i = 0; i < 10; ++i) {
35 // Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
37 // This pass also ensures that the safe points are 3) cheaper than the regular
38 // entry and exits blocks.
40 // Property #1 is ensured via the use of MachineDominatorTree and
41 // MachinePostDominatorTree.
42 // Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
43 // points must be in the same loop.
44 // Property #3 is ensured via the MachineBlockFrequencyInfo.
46 // If this pass found points matching all this properties, then
47 // MachineFrameInfo is updated this that information.
48 //===----------------------------------------------------------------------===//
49 #include "llvm/ADT/Statistic.h"
50 // To check for profitability.
51 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
52 // For property #1 for Save.
53 #include "llvm/CodeGen/MachineDominators.h"
54 #include "llvm/CodeGen/MachineFunctionPass.h"
55 // To record the result of the analysis.
56 #include "llvm/CodeGen/MachineFrameInfo.h"
58 #include "llvm/CodeGen/MachineLoopInfo.h"
59 // For property #1 for Restore.
60 #include "llvm/CodeGen/MachinePostDominators.h"
61 #include "llvm/CodeGen/Passes.h"
62 // To know about callee-saved.
63 #include "llvm/CodeGen/RegisterClassInfo.h"
64 #include "llvm/Support/Debug.h"
65 // To query the target about frame lowering.
66 #include "llvm/Target/TargetFrameLowering.h"
67 // To know about frame setup operation.
68 #include "llvm/Target/TargetInstrInfo.h"
69 // To access TargetInstrInfo.
70 #include "llvm/Target/TargetSubtargetInfo.h"
71 #include "llvm/Support/CommandLine.h"
73 #define DEBUG_TYPE "shrink-wrap"
77 static cl::opt<cl::boolOrDefault>
78 EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
79 cl::desc("enable the shrink-wrapping pass"));
81 STATISTIC(NumFunc, "Number of functions");
82 STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
83 STATISTIC(NumCandidatesDropped,
84 "Number of shrink-wrapping candidates dropped because of frequency");
87 /// \brief Class to determine where the safe point to insert the
88 /// prologue and epilogue are.
89 /// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
90 /// shrink-wrapping term for prologue/epilogue placement, this pass
91 /// does not rely on expensive data-flow analysis. Instead we use the
92 /// dominance properties and loop information to decide which point
93 /// are safe for such insertion.
94 class ShrinkWrap : public MachineFunctionPass {
95 /// Hold callee-saved information.
96 RegisterClassInfo RCI;
97 MachineDominatorTree *MDT;
98 MachinePostDominatorTree *MPDT;
99 /// Current safe point found for the prologue.
100 /// The prologue will be inserted before the first instruction
101 /// in this basic block.
102 MachineBasicBlock *Save;
103 /// Current safe point found for the epilogue.
104 /// The epilogue will be inserted before the first terminator instruction
105 /// in this basic block.
106 MachineBasicBlock *Restore;
107 /// Hold the information of the basic block frequency.
108 /// Use to check the profitability of the new points.
109 MachineBlockFrequencyInfo *MBFI;
110 /// Hold the loop information. Used to determine if Save and Restore
111 /// are in the same loop.
112 MachineLoopInfo *MLI;
113 /// Frequency of the Entry block.
115 /// Current opcode for frame setup.
116 unsigned FrameSetupOpcode;
117 /// Current opcode for frame destroy.
118 unsigned FrameDestroyOpcode;
120 const MachineBasicBlock *Entry;
122 /// \brief Check if \p MI uses or defines a callee-saved register or
123 /// a frame index. If this is the case, this means \p MI must happen
124 /// after Save and before Restore.
125 bool useOrDefCSROrFI(const MachineInstr &MI) const;
127 /// \brief Update the Save and Restore points such that \p MBB is in
128 /// the region that is dominated by Save and post-dominated by Restore
129 /// and Save and Restore still match the safe point definition.
130 /// Such point may not exist and Save and/or Restore may be null after
132 void updateSaveRestorePoints(MachineBasicBlock &MBB);
134 /// \brief Initialize the pass for \p MF.
135 void init(MachineFunction &MF) {
136 RCI.runOnMachineFunction(MF);
137 MDT = &getAnalysis<MachineDominatorTree>();
138 MPDT = &getAnalysis<MachinePostDominatorTree>();
141 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
142 MLI = &getAnalysis<MachineLoopInfo>();
143 EntryFreq = MBFI->getEntryFreq();
144 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
145 FrameSetupOpcode = TII.getCallFrameSetupOpcode();
146 FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
152 /// Check whether or not Save and Restore points are still interesting for
154 bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
159 ShrinkWrap() : MachineFunctionPass(ID) {
160 initializeShrinkWrapPass(*PassRegistry::getPassRegistry());
163 ShrinkWrap(std::function<bool(const MachineFunction &)> Ftor) :
164 MachineFunctionPass(ID), PredicateFtor(Ftor) {
165 initializeShrinkWrapPass(*PassRegistry::getPassRegistry());
168 void getAnalysisUsage(AnalysisUsage &AU) const override {
169 AU.setPreservesAll();
170 AU.addRequired<MachineBlockFrequencyInfo>();
171 AU.addRequired<MachineDominatorTree>();
172 AU.addRequired<MachinePostDominatorTree>();
173 AU.addRequired<MachineLoopInfo>();
174 MachineFunctionPass::getAnalysisUsage(AU);
177 const char *getPassName() const override {
178 return "Shrink Wrapping analysis";
181 /// \brief Perform the shrink-wrapping analysis and update
182 /// the MachineFrameInfo attached to \p MF with the results.
183 bool runOnMachineFunction(MachineFunction &MF) override;
186 /// \brief Predicate function to determine if shrink wrapping should run.
188 /// This function will be run at the beginning of shrink wrapping and
189 /// determine whether shrink wrapping should run on the given MachineFunction.
190 /// \param[in] MF The MachineFunction to run shrink wrapping on.
191 /// \return true if shrink wrapping should be run, false otherwise.
192 std::function<bool(const MachineFunction &MF)> PredicateFtor;
194 } // End anonymous namespace.
196 char ShrinkWrap::ID = 0;
197 char &llvm::ShrinkWrapID = ShrinkWrap::ID;
199 INITIALIZE_PASS_BEGIN(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false,
201 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
202 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
203 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
204 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
205 INITIALIZE_PASS_END(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false, false)
207 bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI) const {
208 if (MI.getOpcode() == FrameSetupOpcode ||
209 MI.getOpcode() == FrameDestroyOpcode) {
210 DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
213 for (const MachineOperand &MO : MI.operands()) {
216 unsigned PhysReg = MO.getReg();
219 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
220 "Unallocated register?!");
221 UseCSR = RCI.getLastCalleeSavedAlias(PhysReg);
223 // TODO: Handle regmask more accurately.
224 // For now, be conservative about them.
225 if (UseCSR || MO.isFI() || MO.isRegMask()) {
226 DEBUG(dbgs() << "Use or define CSR(" << UseCSR << ") or FI(" << MO.isFI()
227 << "): " << MI << '\n');
234 /// \brief Helper function to find the immediate (post) dominator.
235 template <typename ListOfBBs, typename DominanceAnalysis>
236 MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
237 DominanceAnalysis &Dom) {
238 MachineBasicBlock *IDom = &Block;
239 for (MachineBasicBlock *BB : BBs) {
240 IDom = Dom.findNearestCommonDominator(IDom, BB);
247 void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB) {
248 // Get rid of the easy cases first.
252 Save = MDT->findNearestCommonDominator(Save, &MBB);
255 DEBUG(dbgs() << "Found a block that is not reachable from Entry\n");
262 Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
264 // Make sure we would be able to insert the restore code before the
266 if (Restore == &MBB) {
267 for (const MachineInstr &Terminator : MBB.terminators()) {
268 if (!useOrDefCSROrFI(Terminator))
270 // One of the terminator needs to happen before the restore point.
271 if (MBB.succ_empty()) {
275 // Look for a restore point that post-dominates all the successors.
276 // The immediate post-dominator is what we are looking for.
277 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
283 DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n");
287 // Make sure Save and Restore are suitable for shrink-wrapping:
288 // 1. all path from Save needs to lead to Restore before exiting.
289 // 2. all path to Restore needs to go through Save from Entry.
290 // We achieve that by making sure that:
291 // A. Save dominates Restore.
292 // B. Restore post-dominates Save.
293 // C. Save and Restore are in the same loop.
294 bool SaveDominatesRestore = false;
295 bool RestorePostDominatesSave = false;
296 while (Save && Restore &&
297 (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||
298 !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||
299 MLI->getLoopFor(Save) != MLI->getLoopFor(Restore))) {
301 if (!SaveDominatesRestore) {
302 Save = MDT->findNearestCommonDominator(Save, Restore);
306 if (!RestorePostDominatesSave)
307 Restore = MPDT->findNearestCommonDominator(Restore, Save);
310 if (Save && Restore && Save != Restore &&
311 MLI->getLoopFor(Save) != MLI->getLoopFor(Restore)) {
312 if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore))
313 // Push Save outside of this loop.
314 Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
316 // Push Restore outside of this loop.
317 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
322 bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
323 if (PredicateFtor && !PredicateFtor(MF))
326 if (MF.empty() || skipOptnoneFunction(*MF.getFunction()))
329 DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
333 for (MachineBasicBlock &MBB : MF) {
334 DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName()
337 for (const MachineInstr &MI : MBB) {
338 if (!useOrDefCSROrFI(MI))
340 // Save (resp. restore) point must dominate (resp. post dominate)
341 // MI. Look for the proper basic block for those.
342 updateSaveRestorePoints(MBB);
343 // If we are at a point where we cannot improve the placement of
344 // save/restore instructions, just give up.
345 if (!ArePointsInteresting()) {
346 DEBUG(dbgs() << "No Shrink wrap candidate found\n");
349 // No need to look for other instructions, this basic block
350 // will already be part of the handled region.
354 if (!ArePointsInteresting()) {
355 // If the points are not interesting at this point, then they must be null
356 // because it means we did not encounter any frame/CSR related code.
357 // Otherwise, we would have returned from the previous loop.
358 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
359 DEBUG(dbgs() << "Nothing to shrink-wrap\n");
363 DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
366 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
368 DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
369 << Save->getNumber() << ' ' << Save->getName() << ' '
370 << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: "
371 << Restore->getNumber() << ' ' << Restore->getName() << ' '
372 << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
374 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
375 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
376 EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) &&
377 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
378 TFI->canUseAsEpilogue(*Restore)))
380 DEBUG(dbgs() << "New points are too expensive or invalid for the target\n");
381 MachineBasicBlock *NewBB;
382 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
383 Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
388 // Restore is expensive.
389 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
394 updateSaveRestorePoints(*NewBB);
395 } while (Save && Restore);
397 if (!ArePointsInteresting()) {
398 ++NumCandidatesDropped;
402 DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber()
403 << ' ' << Save->getName() << "\nRestore: "
404 << Restore->getNumber() << ' ' << Restore->getName() << '\n');
406 MachineFrameInfo *MFI = MF.getFrameInfo();
407 MFI->setSavePoint(Save);
408 MFI->setRestorePoint(Restore);
413 /// If EnableShrinkWrap is set run shrink wrapping on the given Machine
414 /// Function. Otherwise, shrink wrapping is disabled.
415 /// This function can be overridden in each target-specific TargetPassConfig
416 /// class to allow different predicate logic for each target.
417 bool TargetPassConfig::runShrinkWrap(const MachineFunction &Fn) const {
418 switch (EnableShrinkWrapOpt) {
425 llvm_unreachable("Invalid shrink-wrapping state");
428 /// Create a ShrinkWrap FunctionPass using the runShrinkWrap predicate
430 FunctionPass *TargetPassConfig::createShrinkWrapPass() {
431 std::function<bool(const MachineFunction &Fn)> Ftor =
432 std::bind(&TargetPassConfig::runShrinkWrap, this, std::placeholders::_1);
433 return new ShrinkWrap(Ftor);