/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/ShrinkWrap.cpp
Line | Count | Source (jump to first uncovered line) |
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/ADT/BitVector.h" |
51 | | #include "llvm/ADT/PostOrderIterator.h" |
52 | | #include "llvm/ADT/SetVector.h" |
53 | | #include "llvm/ADT/SmallVector.h" |
54 | | #include "llvm/ADT/Statistic.h" |
55 | | #include "llvm/Analysis/CFG.h" |
56 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
57 | | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
58 | | #include "llvm/CodeGen/MachineDominators.h" |
59 | | #include "llvm/CodeGen/MachineFrameInfo.h" |
60 | | #include "llvm/CodeGen/MachineFunction.h" |
61 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
62 | | #include "llvm/CodeGen/MachineInstr.h" |
63 | | #include "llvm/CodeGen/MachineLoopInfo.h" |
64 | | #include "llvm/CodeGen/MachineOperand.h" |
65 | | #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" |
66 | | #include "llvm/CodeGen/MachinePostDominators.h" |
67 | | #include "llvm/CodeGen/RegisterClassInfo.h" |
68 | | #include "llvm/CodeGen/RegisterScavenging.h" |
69 | | #include "llvm/CodeGen/TargetFrameLowering.h" |
70 | | #include "llvm/CodeGen/TargetInstrInfo.h" |
71 | | #include "llvm/CodeGen/TargetLowering.h" |
72 | | #include "llvm/CodeGen/TargetRegisterInfo.h" |
73 | | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
74 | | #include "llvm/IR/Attributes.h" |
75 | | #include "llvm/IR/Function.h" |
76 | | #include "llvm/MC/MCAsmInfo.h" |
77 | | #include "llvm/Pass.h" |
78 | | #include "llvm/Support/CommandLine.h" |
79 | | #include "llvm/Support/Debug.h" |
80 | | #include "llvm/Support/ErrorHandling.h" |
81 | | #include "llvm/Support/raw_ostream.h" |
82 | | #include "llvm/Target/TargetMachine.h" |
83 | | #include <cassert> |
84 | | #include <cstdint> |
85 | | #include <memory> |
86 | | |
87 | | using namespace llvm; |
88 | | |
89 | 2 | #define DEBUG_TYPE "shrink-wrap" |
90 | | |
91 | | STATISTIC(NumFunc, "Number of functions"); |
92 | | STATISTIC(NumCandidates, "Number of shrink-wrapping candidates"); |
93 | | STATISTIC(NumCandidatesDropped, |
94 | | "Number of shrink-wrapping candidates dropped because of frequency"); |
95 | | |
96 | | static cl::opt<cl::boolOrDefault> |
97 | | EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, |
98 | | cl::desc("enable the shrink-wrapping pass")); |
99 | | |
100 | | namespace { |
101 | | |
102 | | /// Class to determine where the safe point to insert the |
103 | | /// prologue and epilogue are. |
104 | | /// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the |
105 | | /// shrink-wrapping term for prologue/epilogue placement, this pass |
106 | | /// does not rely on expensive data-flow analysis. Instead we use the |
107 | | /// dominance properties and loop information to decide which point |
108 | | /// are safe for such insertion. |
109 | | class ShrinkWrap : public MachineFunctionPass { |
110 | | /// Hold callee-saved information. |
111 | | RegisterClassInfo RCI; |
112 | | MachineDominatorTree *MDT; |
113 | | MachinePostDominatorTree *MPDT; |
114 | | |
115 | | /// Current safe point found for the prologue. |
116 | | /// The prologue will be inserted before the first instruction |
117 | | /// in this basic block. |
118 | | MachineBasicBlock *Save; |
119 | | |
120 | | /// Current safe point found for the epilogue. |
121 | | /// The epilogue will be inserted before the first terminator instruction |
122 | | /// in this basic block. |
123 | | MachineBasicBlock *Restore; |
124 | | |
125 | | /// Hold the information of the basic block frequency. |
126 | | /// Use to check the profitability of the new points. |
127 | | MachineBlockFrequencyInfo *MBFI; |
128 | | |
129 | | /// Hold the loop information. Used to determine if Save and Restore |
130 | | /// are in the same loop. |
131 | | MachineLoopInfo *MLI; |
132 | | |
133 | | // Emit remarks. |
134 | | MachineOptimizationRemarkEmitter *ORE = nullptr; |
135 | | |
136 | | /// Frequency of the Entry block. |
137 | | uint64_t EntryFreq; |
138 | | |
139 | | /// Current opcode for frame setup. |
140 | | unsigned FrameSetupOpcode; |
141 | | |
142 | | /// Current opcode for frame destroy. |
143 | | unsigned FrameDestroyOpcode; |
144 | | |
145 | | /// Stack pointer register, used by llvm.{savestack,restorestack} |
146 | | unsigned SP; |
147 | | |
148 | | /// Entry block. |
149 | | const MachineBasicBlock *Entry; |
150 | | |
151 | | using SetOfRegs = SmallSetVector<unsigned, 16>; |
152 | | |
153 | | /// Registers that need to be saved for the current function. |
154 | | mutable SetOfRegs CurrentCSRs; |
155 | | |
156 | | /// Current MachineFunction. |
157 | | MachineFunction *MachineFunc; |
158 | | |
159 | | /// Check if \p MI uses or defines a callee-saved register or |
160 | | /// a frame index. If this is the case, this means \p MI must happen |
161 | | /// after Save and before Restore. |
162 | | bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const; |
163 | | |
164 | 22.1k | const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const { |
165 | 22.1k | if (CurrentCSRs.empty()) { |
166 | 19.0k | BitVector SavedRegs; |
167 | 19.0k | const TargetFrameLowering *TFI = |
168 | 19.0k | MachineFunc->getSubtarget().getFrameLowering(); |
169 | 19.0k | |
170 | 19.0k | TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS); |
171 | 19.0k | |
172 | 24.2k | for (int Reg = SavedRegs.find_first(); Reg != -1; |
173 | 19.0k | Reg = SavedRegs.find_next(Reg)5.19k ) |
174 | 5.19k | CurrentCSRs.insert((unsigned)Reg); |
175 | 19.0k | } |
176 | 22.1k | return CurrentCSRs; |
177 | 22.1k | } |
178 | | |
179 | | /// Update the Save and Restore points such that \p MBB is in |
180 | | /// the region that is dominated by Save and post-dominated by Restore |
181 | | /// and Save and Restore still match the safe point definition. |
182 | | /// Such point may not exist and Save and/or Restore may be null after |
183 | | /// this call. |
184 | | void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS); |
185 | | |
186 | | /// Initialize the pass for \p MF. |
187 | 362k | void init(MachineFunction &MF) { |
188 | 362k | RCI.runOnMachineFunction(MF); |
189 | 362k | MDT = &getAnalysis<MachineDominatorTree>(); |
190 | 362k | MPDT = &getAnalysis<MachinePostDominatorTree>(); |
191 | 362k | Save = nullptr; |
192 | 362k | Restore = nullptr; |
193 | 362k | MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); |
194 | 362k | MLI = &getAnalysis<MachineLoopInfo>(); |
195 | 362k | ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE(); |
196 | 362k | EntryFreq = MBFI->getEntryFreq(); |
197 | 362k | const TargetSubtargetInfo &Subtarget = MF.getSubtarget(); |
198 | 362k | const TargetInstrInfo &TII = *Subtarget.getInstrInfo(); |
199 | 362k | FrameSetupOpcode = TII.getCallFrameSetupOpcode(); |
200 | 362k | FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); |
201 | 362k | SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore(); |
202 | 362k | Entry = &MF.front(); |
203 | 362k | CurrentCSRs.clear(); |
204 | 362k | MachineFunc = &MF; |
205 | 362k | |
206 | 362k | ++NumFunc; |
207 | 362k | } |
208 | | |
209 | | /// Check whether or not Save and Restore points are still interesting for |
210 | | /// shrink-wrapping. |
211 | 426k | bool ArePointsInteresting() const { return Save != Entry && Save127k && Restore72.1k ; } |
212 | | |
213 | | /// Check if shrink wrapping is enabled for this target and function. |
214 | | static bool isShrinkWrapEnabled(const MachineFunction &MF); |
215 | | |
216 | | public: |
217 | | static char ID; |
218 | | |
219 | 33.8k | ShrinkWrap() : MachineFunctionPass(ID) { |
220 | 33.8k | initializeShrinkWrapPass(*PassRegistry::getPassRegistry()); |
221 | 33.8k | } |
222 | | |
223 | 33.6k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
224 | 33.6k | AU.setPreservesAll(); |
225 | 33.6k | AU.addRequired<MachineBlockFrequencyInfo>(); |
226 | 33.6k | AU.addRequired<MachineDominatorTree>(); |
227 | 33.6k | AU.addRequired<MachinePostDominatorTree>(); |
228 | 33.6k | AU.addRequired<MachineLoopInfo>(); |
229 | 33.6k | AU.addRequired<MachineOptimizationRemarkEmitterPass>(); |
230 | 33.6k | MachineFunctionPass::getAnalysisUsage(AU); |
231 | 33.6k | } |
232 | | |
233 | 33.6k | MachineFunctionProperties getRequiredProperties() const override { |
234 | 33.6k | return MachineFunctionProperties().set( |
235 | 33.6k | MachineFunctionProperties::Property::NoVRegs); |
236 | 33.6k | } |
237 | | |
238 | 518k | StringRef getPassName() const override { return "Shrink Wrapping analysis"; } |
239 | | |
240 | | /// Perform the shrink-wrapping analysis and update |
241 | | /// the MachineFrameInfo attached to \p MF with the results. |
242 | | bool runOnMachineFunction(MachineFunction &MF) override; |
243 | | }; |
244 | | |
245 | | } // end anonymous namespace |
246 | | |
247 | | char ShrinkWrap::ID = 0; |
248 | | |
249 | | char &llvm::ShrinkWrapID = ShrinkWrap::ID; |
250 | | |
251 | 42.3k | INITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) |
252 | 42.3k | INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) |
253 | 42.3k | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
254 | 42.3k | INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) |
255 | 42.3k | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
256 | 42.3k | INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass) |
257 | 42.3k | INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) |
258 | | |
259 | | bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI, |
260 | 1.36M | RegScavenger *RS) const { |
261 | 1.36M | // This prevents premature stack popping when occurs a indirect stack |
262 | 1.36M | // access. It is overly aggressive for the moment. |
263 | 1.36M | // TODO: - Obvious non-stack loads and store, such as global values, |
264 | 1.36M | // are known to not access the stack. |
265 | 1.36M | // - Further, data dependency and alias analysis can validate |
266 | 1.36M | // that load and stores never derive from the stack pointer. |
267 | 1.36M | if (MI.mayLoadOrStore()) |
268 | 143k | return true; |
269 | 1.21M | |
270 | 1.21M | if (MI.getOpcode() == FrameSetupOpcode || |
271 | 1.21M | MI.getOpcode() == FrameDestroyOpcode1.15M ) { |
272 | 64.4k | LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n'); |
273 | 64.4k | return true; |
274 | 64.4k | } |
275 | 2.49M | for (const MachineOperand &MO : MI.operands())1.15M { |
276 | 2.49M | bool UseOrDefCSR = false; |
277 | 2.49M | if (MO.isReg()) { |
278 | 1.67M | // Ignore instructions like DBG_VALUE which don't read/def the register. |
279 | 1.67M | if (!MO.isDef() && !MO.readsReg()988k ) |
280 | 2.28k | continue; |
281 | 1.66M | unsigned PhysReg = MO.getReg(); |
282 | 1.66M | if (!PhysReg) |
283 | 58.9k | continue; |
284 | 1.60M | assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && |
285 | 1.60M | "Unallocated register?!"); |
286 | 1.60M | // The stack pointer is not normally described as a callee-saved register |
287 | 1.60M | // in calling convention definitions, so we need to watch for it |
288 | 1.60M | // separately. An SP mentioned by a call instruction, we can ignore, |
289 | 1.60M | // though, as it's harmless and we do not want to effectively disable tail |
290 | 1.60M | // calls by forcing the restore point to post-dominate them. |
291 | 1.60M | UseOrDefCSR = (!MI.isCall() && PhysReg == SP1.53M ) || |
292 | 1.60M | RCI.getLastCalleeSavedAlias(PhysReg)1.60M ; |
293 | 1.60M | } else if (824k MO.isRegMask()824k ) { |
294 | 22.1k | // Check if this regmask clobbers any of the CSRs. |
295 | 23.0k | for (unsigned Reg : getCurrentCSRs(RS)) { |
296 | 23.0k | if (MO.clobbersPhysReg(Reg)) { |
297 | 13 | UseOrDefCSR = true; |
298 | 13 | break; |
299 | 13 | } |
300 | 23.0k | } |
301 | 22.1k | } |
302 | 2.49M | // Skip FrameIndex operands in DBG_VALUE instructions. |
303 | 2.49M | if (2.43M UseOrDefCSR2.43M || (2.26M MO.isFI()2.26M && !MI.isDebugValue()2.14k )) { |
304 | 172k | LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI(" |
305 | 172k | << MO.isFI() << "): " << MI << '\n'); |
306 | 172k | return true; |
307 | 172k | } |
308 | 2.43M | } |
309 | 1.15M | return false981k ; |
310 | 1.15M | } |
311 | | |
312 | | /// Helper function to find the immediate (post) dominator. |
313 | | template <typename ListOfBBs, typename DominanceAnalysis> |
314 | | static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, |
315 | 37.0k | DominanceAnalysis &Dom) { |
316 | 37.0k | MachineBasicBlock *IDom = &Block; |
317 | 72.4k | for (MachineBasicBlock *BB : BBs) { |
318 | 72.4k | IDom = Dom.findNearestCommonDominator(IDom, BB); |
319 | 72.4k | if (!IDom) |
320 | 1.71k | break; |
321 | 72.4k | } |
322 | 37.0k | if (IDom == &Block) |
323 | 429 | return nullptr; |
324 | 36.6k | return IDom; |
325 | 36.6k | } ShrinkWrap.cpp:llvm::MachineBasicBlock* FindIDom<llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachineDominatorTree>(llvm::MachineBasicBlock&, llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachineDominatorTree&) Line | Count | Source | 315 | 2.44k | DominanceAnalysis &Dom) { | 316 | 2.44k | MachineBasicBlock *IDom = &Block; | 317 | 4.88k | for (MachineBasicBlock *BB : BBs) { | 318 | 4.88k | IDom = Dom.findNearestCommonDominator(IDom, BB); | 319 | 4.88k | if (!IDom) | 320 | 0 | break; | 321 | 4.88k | } | 322 | 2.44k | if (IDom == &Block) | 323 | 0 | return nullptr; | 324 | 2.44k | return IDom; | 325 | 2.44k | } |
ShrinkWrap.cpp:llvm::MachineBasicBlock* FindIDom<llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachinePostDominatorTree>(llvm::MachineBasicBlock&, llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachinePostDominatorTree&) Line | Count | Source | 315 | 34.5k | DominanceAnalysis &Dom) { | 316 | 34.5k | MachineBasicBlock *IDom = &Block; | 317 | 67.5k | for (MachineBasicBlock *BB : BBs) { | 318 | 67.5k | IDom = Dom.findNearestCommonDominator(IDom, BB); | 319 | 67.5k | if (!IDom) | 320 | 1.71k | break; | 321 | 67.5k | } | 322 | 34.5k | if (IDom == &Block) | 323 | 429 | return nullptr; | 324 | 34.1k | return IDom; | 325 | 34.1k | } |
|
326 | | |
327 | | void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB, |
328 | 362k | RegScavenger *RS) { |
329 | 362k | // Get rid of the easy cases first. |
330 | 362k | if (!Save) |
331 | 307k | Save = &MBB; |
332 | 54.9k | else |
333 | 54.9k | Save = MDT->findNearestCommonDominator(Save, &MBB); |
334 | 362k | |
335 | 362k | if (!Save) { |
336 | 0 | LLVM_DEBUG(dbgs() << "Found a block that is not reachable from Entry\n"); |
337 | 0 | return; |
338 | 0 | } |
339 | 362k | |
340 | 362k | if (!Restore) |
341 | 307k | Restore = &MBB; |
342 | 54.9k | else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it |
343 | 54.9k | // means the block never returns. If that's the |
344 | 54.9k | // case, we don't want to call |
345 | 54.9k | // `findNearestCommonDominator`, which will |
346 | 54.9k | // return `Restore`. |
347 | 54.9k | Restore = MPDT->findNearestCommonDominator(Restore, &MBB); |
348 | 0 | else |
349 | 0 | Restore = nullptr; // Abort, we can't find a restore point in this case. |
350 | 362k | |
351 | 362k | // Make sure we would be able to insert the restore code before the |
352 | 362k | // terminator. |
353 | 362k | if (Restore == &MBB) { |
354 | 354k | for (const MachineInstr &Terminator : MBB.terminators()) { |
355 | 354k | if (!useOrDefCSROrFI(Terminator, RS)) |
356 | 335k | continue; |
357 | 18.2k | // One of the terminator needs to happen before the restore point. |
358 | 18.2k | if (MBB.succ_empty()) { |
359 | 164 | Restore = nullptr; // Abort, we can't find a restore point in this case. |
360 | 164 | break; |
361 | 164 | } |
362 | 18.0k | // Look for a restore point that post-dominates all the successors. |
363 | 18.0k | // The immediate post-dominator is what we are looking for. |
364 | 18.0k | Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); |
365 | 18.0k | break; |
366 | 18.0k | } |
367 | 334k | } |
368 | 362k | |
369 | 362k | if (!Restore) { |
370 | 9.04k | LLVM_DEBUG( |
371 | 9.04k | dbgs() << "Restore point needs to be spanned on several blocks\n"); |
372 | 9.04k | return; |
373 | 9.04k | } |
374 | 353k | |
375 | 353k | // Make sure Save and Restore are suitable for shrink-wrapping: |
376 | 353k | // 1. all path from Save needs to lead to Restore before exiting. |
377 | 353k | // 2. all path to Restore needs to go through Save from Entry. |
378 | 353k | // We achieve that by making sure that: |
379 | 353k | // A. Save dominates Restore. |
380 | 353k | // B. Restore post-dominates Save. |
381 | 353k | // C. Save and Restore are in the same loop. |
382 | 353k | bool SaveDominatesRestore = false; |
383 | 353k | bool RestorePostDominatesSave = false; |
384 | 378k | while (Save && Restore && |
385 | 378k | (378k !(SaveDominatesRestore = MDT->dominates(Save, Restore))378k || |
386 | 378k | !(RestorePostDominatesSave = MPDT->dominates(Restore, Save))371k || |
387 | 378k | // Post-dominance is not enough in loops to ensure that all uses/defs |
388 | 378k | // are after the prologue and before the epilogue at runtime. |
389 | 378k | // E.g., |
390 | 378k | // while(1) { |
391 | 378k | // Save |
392 | 378k | // Restore |
393 | 378k | // if (...) |
394 | 378k | // break; |
395 | 378k | // use/def CSRs |
396 | 378k | // } |
397 | 378k | // All the uses/defs of CSRs are dominated by Save and post-dominated |
398 | 378k | // by Restore. However, the CSRs uses are still reachable after |
399 | 378k | // Restore and before Save are executed. |
400 | 378k | // |
401 | 378k | // For now, just push the restore/save points outside of loops. |
402 | 378k | // FIXME: Refine the criteria to still find interesting cases |
403 | 378k | // for loops. |
404 | 378k | MLI->getLoopFor(Save)371k || MLI->getLoopFor(Restore)364k )) { |
405 | 25.5k | // Fix (A). |
406 | 25.5k | if (!SaveDominatesRestore) { |
407 | 6.92k | Save = MDT->findNearestCommonDominator(Save, Restore); |
408 | 6.92k | continue; |
409 | 6.92k | } |
410 | 18.5k | // Fix (B). |
411 | 18.5k | if (!RestorePostDominatesSave) |
412 | 23 | Restore = MPDT->findNearestCommonDominator(Restore, Save); |
413 | 18.5k | |
414 | 18.5k | // Fix (C). |
415 | 18.5k | if (Save && Restore && |
416 | 18.5k | (18.5k MLI->getLoopFor(Save)18.5k || MLI->getLoopFor(Restore)11.5k )) { |
417 | 18.5k | if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) { |
418 | 2.44k | // Push Save outside of this loop if immediate dominator is different |
419 | 2.44k | // from save block. If immediate dominator is not different, bail out. |
420 | 2.44k | Save = FindIDom<>(*Save, Save->predecessors(), *MDT); |
421 | 2.44k | if (!Save) |
422 | 0 | break; |
423 | 16.1k | } else { |
424 | 16.1k | // If the loop does not exit, there is no point in looking |
425 | 16.1k | // for a post-dominator outside the loop. |
426 | 16.1k | SmallVector<MachineBasicBlock*, 4> ExitBlocks; |
427 | 16.1k | MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks); |
428 | 16.1k | // Push Restore outside of this loop. |
429 | 16.1k | // Look for the immediate post-dominator of the loop exits. |
430 | 16.1k | MachineBasicBlock *IPdom = Restore; |
431 | 16.5k | for (MachineBasicBlock *LoopExitBB: ExitBlocks) { |
432 | 16.5k | IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT); |
433 | 16.5k | if (!IPdom) |
434 | 462 | break; |
435 | 16.5k | } |
436 | 16.1k | // If the immediate post-dominator is not in a less nested loop, |
437 | 16.1k | // then we are stuck in a program with an infinite loop. |
438 | 16.1k | // In that case, we will not find a safe point, hence, bail out. |
439 | 16.1k | if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)15.6k ) |
440 | 15.6k | Restore = IPdom; |
441 | 498 | else { |
442 | 498 | Restore = nullptr; |
443 | 498 | break; |
444 | 498 | } |
445 | 16.1k | } |
446 | 18.5k | } |
447 | 18.5k | } |
448 | 353k | } |
449 | | |
450 | | static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE, |
451 | | StringRef RemarkName, StringRef RemarkMessage, |
452 | | const DiagnosticLocation &Loc, |
453 | 52 | const MachineBasicBlock *MBB) { |
454 | 52 | ORE->emit([&]() { |
455 | 2 | return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB) |
456 | 2 | << RemarkMessage; |
457 | 2 | }); |
458 | 52 | |
459 | 52 | LLVM_DEBUG(dbgs() << RemarkMessage << '\n'); |
460 | 52 | return false; |
461 | 52 | } |
462 | | |
463 | 484k | bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) { |
464 | 484k | if (skipFunction(MF.getFunction()) || MF.empty()484k || !isShrinkWrapEnabled(MF)484k ) |
465 | 121k | return false; |
466 | 362k | |
467 | 362k | LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); |
468 | 362k | |
469 | 362k | init(MF); |
470 | 362k | |
471 | 362k | ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin()); |
472 | 362k | if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) { |
473 | 51 | // If MF is irreducible, a block may be in a loop without |
474 | 51 | // MachineLoopInfo reporting it. I.e., we may use the |
475 | 51 | // post-dominance property in loops, which lead to incorrect |
476 | 51 | // results. Moreover, we may miss that the prologue and |
477 | 51 | // epilogue are not in the same loop, leading to unbalanced |
478 | 51 | // construction/deconstruction of the stack frame. |
479 | 51 | return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG", |
480 | 51 | "Irreducible CFGs are not supported yet.", |
481 | 51 | MF.getFunction().getSubprogram(), &MF.front()); |
482 | 51 | } |
483 | 362k | |
484 | 362k | const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); |
485 | 362k | std::unique_ptr<RegScavenger> RS( |
486 | 362k | TRI->requiresRegisterScavenging(MF) ? new RegScavenger()302k : nullptr60.4k ); |
487 | 362k | |
488 | 529k | for (MachineBasicBlock &MBB : MF) { |
489 | 529k | LLVM_DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' |
490 | 529k | << MBB.getName() << '\n'); |
491 | 529k | |
492 | 529k | if (MBB.isEHFuncletEntry()) |
493 | 1 | return giveUpWithRemarks(ORE, "UnsupportedEHFunclets", |
494 | 1 | "EH Funclets are not supported yet.", |
495 | 1 | MBB.front().getDebugLoc(), &MBB); |
496 | 529k | |
497 | 529k | if (MBB.isEHPad()) { |
498 | 10 | // Push the prologue and epilogue outside of |
499 | 10 | // the region that may throw by making sure |
500 | 10 | // that all the landing pads are at least at the |
501 | 10 | // boundary of the save and restore points. |
502 | 10 | // The problem with exceptions is that the throw |
503 | 10 | // is not properly modeled and in particular, a |
504 | 10 | // basic block can jump out from the middle. |
505 | 10 | updateSaveRestorePoints(MBB, RS.get()); |
506 | 10 | if (!ArePointsInteresting()) { |
507 | 7 | LLVM_DEBUG(dbgs() << "EHPad prevents shrink-wrapping\n"); |
508 | 7 | return false; |
509 | 7 | } |
510 | 3 | continue; |
511 | 3 | } |
512 | 529k | |
513 | 1.00M | for (const MachineInstr &MI : MBB)529k { |
514 | 1.00M | if (!useOrDefCSROrFI(MI, RS.get())) |
515 | 645k | continue; |
516 | 362k | // Save (resp. restore) point must dominate (resp. post dominate) |
517 | 362k | // MI. Look for the proper basic block for those. |
518 | 362k | updateSaveRestorePoints(MBB, RS.get()); |
519 | 362k | // If we are at a point where we cannot improve the placement of |
520 | 362k | // save/restore instructions, just give up. |
521 | 362k | if (!ArePointsInteresting()) { |
522 | 302k | LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n"); |
523 | 302k | return false; |
524 | 302k | } |
525 | 59.5k | // No need to look for other instructions, this basic block |
526 | 59.5k | // will already be part of the handled region. |
527 | 59.5k | break; |
528 | 59.5k | } |
529 | 529k | } |
530 | 362k | if (60.0k !ArePointsInteresting()60.0k ) { |
531 | 55.4k | // If the points are not interesting at this point, then they must be null |
532 | 55.4k | // because it means we did not encounter any frame/CSR related code. |
533 | 55.4k | // Otherwise, we would have returned from the previous loop. |
534 | 55.4k | assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!"); |
535 | 55.4k | LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n"); |
536 | 55.4k | return false; |
537 | 55.4k | } |
538 | 4.60k | |
539 | 4.60k | LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq |
540 | 4.60k | << '\n'); |
541 | 4.60k | |
542 | 4.60k | const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); |
543 | 4.60k | do { |
544 | 4.60k | LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: " |
545 | 4.60k | << Save->getNumber() << ' ' << Save->getName() << ' ' |
546 | 4.60k | << MBFI->getBlockFreq(Save).getFrequency() |
547 | 4.60k | << "\nRestore: " << Restore->getNumber() << ' ' |
548 | 4.60k | << Restore->getName() << ' ' |
549 | 4.60k | << MBFI->getBlockFreq(Restore).getFrequency() << '\n'); |
550 | 4.60k | |
551 | 4.60k | bool IsSaveCheap, TargetCanUseSaveAsPrologue = false; |
552 | 4.60k | if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) && |
553 | 4.60k | EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()4.60k ) && |
554 | 4.60k | (4.60k (TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save))4.60k && |
555 | 4.60k | TFI->canUseAsEpilogue(*Restore))) |
556 | 4.60k | break; |
557 | 2 | LLVM_DEBUG( |
558 | 2 | dbgs() << "New points are too expensive or invalid for the target\n"); |
559 | 2 | MachineBasicBlock *NewBB; |
560 | 2 | if (!IsSaveCheap || !TargetCanUseSaveAsPrologue1 ) { |
561 | 0 | Save = FindIDom<>(*Save, Save->predecessors(), *MDT); |
562 | 0 | if (!Save) |
563 | 0 | break; |
564 | 0 | NewBB = Save; |
565 | 2 | } else { |
566 | 2 | // Restore is expensive. |
567 | 2 | Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); |
568 | 2 | if (!Restore) |
569 | 0 | break; |
570 | 2 | NewBB = Restore; |
571 | 2 | } |
572 | 2 | updateSaveRestorePoints(*NewBB, RS.get()); |
573 | 2 | } while (Save && Restore1 ); |
574 | 4.60k | |
575 | 4.60k | if (!ArePointsInteresting()) { |
576 | 1 | ++NumCandidatesDropped; |
577 | 1 | return false; |
578 | 1 | } |
579 | 4.60k | |
580 | 4.60k | LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " |
581 | 4.60k | << Save->getNumber() << ' ' << Save->getName() |
582 | 4.60k | << "\nRestore: " << Restore->getNumber() << ' ' |
583 | 4.60k | << Restore->getName() << '\n'); |
584 | 4.60k | |
585 | 4.60k | MachineFrameInfo &MFI = MF.getFrameInfo(); |
586 | 4.60k | MFI.setSavePoint(Save); |
587 | 4.60k | MFI.setRestorePoint(Restore); |
588 | 4.60k | ++NumCandidates; |
589 | 4.60k | return false; |
590 | 4.60k | } |
591 | | |
592 | 484k | bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) { |
593 | 484k | const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); |
594 | 484k | |
595 | 484k | switch (EnableShrinkWrapOpt) { |
596 | 484k | case cl::BOU_UNSET: |
597 | 483k | return TFI->enableShrinkWrapping(MF) && |
598 | 483k | // Windows with CFI has some limitations that make it impossible |
599 | 483k | // to use shrink-wrapping. |
600 | 483k | !MF.getTarget().getMCAsmInfo()->usesWindowsCFI()363k && |
601 | 483k | // Sanitizers look at the value of the stack at the location |
602 | 483k | // of the crash. Since a crash can happen anywhere, the |
603 | 483k | // frame must be lowered before anything else happen for the |
604 | 483k | // sanitizers to be able to get a correct stack frame. |
605 | 483k | !(362k MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress)362k || |
606 | 362k | MF.getFunction().hasFnAttribute(Attribute::SanitizeThread)362k || |
607 | 362k | MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory)362k || |
608 | 362k | MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress)362k ); |
609 | 484k | // If EnableShrinkWrap is set, it takes precedence on whatever the |
610 | 484k | // target sets. The rational is that we assume we want to test |
611 | 484k | // something related to shrink-wrapping. |
612 | 484k | case cl::BOU_TRUE: |
613 | 138 | return true; |
614 | 484k | case cl::BOU_FALSE: |
615 | 154 | return false; |
616 | 0 | } |
617 | 0 | llvm_unreachable("Invalid shrink-wrapping state"); |
618 | 0 | } |