LLVM  14.0.0git
ShrinkWrap.cpp
Go to the documentation of this file.
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"
52 #include "llvm/ADT/SetVector.h"
53 #include "llvm/ADT/SmallVector.h"
54 #include "llvm/ADT/Statistic.h"
55 #include "llvm/Analysis/CFG.h"
74 #include "llvm/IR/Attributes.h"
75 #include "llvm/IR/Function.h"
76 #include "llvm/InitializePasses.h"
77 #include "llvm/MC/MCAsmInfo.h"
78 #include "llvm/Pass.h"
80 #include "llvm/Support/Debug.h"
84 #include <cassert>
85 #include <cstdint>
86 #include <memory>
87 
88 using namespace llvm;
89 
90 #define DEBUG_TYPE "shrink-wrap"
91 
92 STATISTIC(NumFunc, "Number of functions");
93 STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
94 STATISTIC(NumCandidatesDropped,
95  "Number of shrink-wrapping candidates dropped because of frequency");
96 
98 EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
99  cl::desc("enable the shrink-wrapping pass"));
100 
101 namespace {
102 
103 /// Class to determine where the safe point to insert the
104 /// prologue and epilogue are.
105 /// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
106 /// shrink-wrapping term for prologue/epilogue placement, this pass
107 /// does not rely on expensive data-flow analysis. Instead we use the
108 /// dominance properties and loop information to decide which point
109 /// are safe for such insertion.
110 class ShrinkWrap : public MachineFunctionPass {
111  /// Hold callee-saved information.
112  RegisterClassInfo RCI;
115 
116  /// Current safe point found for the prologue.
117  /// The prologue will be inserted before the first instruction
118  /// in this basic block.
119  MachineBasicBlock *Save;
120 
121  /// Current safe point found for the epilogue.
122  /// The epilogue will be inserted before the first terminator instruction
123  /// in this basic block.
124  MachineBasicBlock *Restore;
125 
126  /// Hold the information of the basic block frequency.
127  /// Use to check the profitability of the new points.
129 
130  /// Hold the loop information. Used to determine if Save and Restore
131  /// are in the same loop.
132  MachineLoopInfo *MLI;
133 
134  // Emit remarks.
135  MachineOptimizationRemarkEmitter *ORE = nullptr;
136 
137  /// Frequency of the Entry block.
138  uint64_t EntryFreq;
139 
140  /// Current opcode for frame setup.
141  unsigned FrameSetupOpcode;
142 
143  /// Current opcode for frame destroy.
144  unsigned FrameDestroyOpcode;
145 
146  /// Stack pointer register, used by llvm.{savestack,restorestack}
147  Register SP;
148 
149  /// Entry block.
150  const MachineBasicBlock *Entry;
151 
152  using SetOfRegs = SmallSetVector<unsigned, 16>;
153 
154  /// Registers that need to be saved for the current function.
155  mutable SetOfRegs CurrentCSRs;
156 
157  /// Current MachineFunction.
158  MachineFunction *MachineFunc;
159 
160  /// Check if \p MI uses or defines a callee-saved register or
161  /// a frame index. If this is the case, this means \p MI must happen
162  /// after Save and before Restore.
163  bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const;
164 
165  const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {
166  if (CurrentCSRs.empty()) {
167  BitVector SavedRegs;
168  const TargetFrameLowering *TFI =
169  MachineFunc->getSubtarget().getFrameLowering();
170 
171  TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS);
172 
173  for (int Reg = SavedRegs.find_first(); Reg != -1;
174  Reg = SavedRegs.find_next(Reg))
175  CurrentCSRs.insert((unsigned)Reg);
176  }
177  return CurrentCSRs;
178  }
179 
180  /// Update the Save and Restore points such that \p MBB is in
181  /// the region that is dominated by Save and post-dominated by Restore
182  /// and Save and Restore still match the safe point definition.
183  /// Such point may not exist and Save and/or Restore may be null after
184  /// this call.
185  void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
186 
187  /// Initialize the pass for \p MF.
188  void init(MachineFunction &MF) {
189  RCI.runOnMachineFunction(MF);
190  MDT = &getAnalysis<MachineDominatorTree>();
191  MPDT = &getAnalysis<MachinePostDominatorTree>();
192  Save = nullptr;
193  Restore = nullptr;
194  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
195  MLI = &getAnalysis<MachineLoopInfo>();
196  ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
197  EntryFreq = MBFI->getEntryFreq();
198  const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
199  const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
200  FrameSetupOpcode = TII.getCallFrameSetupOpcode();
201  FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
203  Entry = &MF.front();
204  CurrentCSRs.clear();
205  MachineFunc = &MF;
206 
207  ++NumFunc;
208  }
209 
210  /// Check whether or not Save and Restore points are still interesting for
211  /// shrink-wrapping.
212  bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
213 
214  /// Check if shrink wrapping is enabled for this target and function.
215  static bool isShrinkWrapEnabled(const MachineFunction &MF);
216 
217 public:
218  static char ID;
219 
220  ShrinkWrap() : MachineFunctionPass(ID) {
222  }
223 
224  void getAnalysisUsage(AnalysisUsage &AU) const override {
225  AU.setPreservesAll();
232  }
233 
234  MachineFunctionProperties getRequiredProperties() const override {
237  }
238 
239  StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
240 
241  /// Perform the shrink-wrapping analysis and update
242  /// the MachineFrameInfo attached to \p MF with the results.
243  bool runOnMachineFunction(MachineFunction &MF) override;
244 };
245 
246 } // end anonymous namespace
247 
248 char ShrinkWrap::ID = 0;
249 
251 
252 INITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
258 INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
259 
260 bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI,
261  RegScavenger *RS) const {
262  // This prevents premature stack popping when occurs a indirect stack
263  // access. It is overly aggressive for the moment.
264  // TODO: - Obvious non-stack loads and store, such as global values,
265  // are known to not access the stack.
266  // - Further, data dependency and alias analysis can validate
267  // that load and stores never derive from the stack pointer.
268  if (MI.mayLoadOrStore())
269  return true;
270 
271  if (MI.getOpcode() == FrameSetupOpcode ||
272  MI.getOpcode() == FrameDestroyOpcode) {
273  LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
274  return true;
275  }
276  for (const MachineOperand &MO : MI.operands()) {
277  bool UseOrDefCSR = false;
278  if (MO.isReg()) {
279  // Ignore instructions like DBG_VALUE which don't read/def the register.
280  if (!MO.isDef() && !MO.readsReg())
281  continue;
282  Register PhysReg = MO.getReg();
283  if (!PhysReg)
284  continue;
285  assert(Register::isPhysicalRegister(PhysReg) && "Unallocated register?!");
286  // The stack pointer is not normally described as a callee-saved register
287  // in calling convention definitions, so we need to watch for it
288  // separately. An SP mentioned by a call instruction, we can ignore,
289  // though, as it's harmless and we do not want to effectively disable tail
290  // calls by forcing the restore point to post-dominate them.
291  UseOrDefCSR = (!MI.isCall() && PhysReg == SP) ||
292  RCI.getLastCalleeSavedAlias(PhysReg);
293  } else if (MO.isRegMask()) {
294  // Check if this regmask clobbers any of the CSRs.
295  for (unsigned Reg : getCurrentCSRs(RS)) {
296  if (MO.clobbersPhysReg(Reg)) {
297  UseOrDefCSR = true;
298  break;
299  }
300  }
301  }
302  // Skip FrameIndex operands in DBG_VALUE instructions.
303  if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
304  LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
305  << MO.isFI() << "): " << MI << '\n');
306  return true;
307  }
308  }
309  return false;
310 }
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  DominanceAnalysis &Dom) {
316  MachineBasicBlock *IDom = &Block;
317  for (MachineBasicBlock *BB : BBs) {
318  IDom = Dom.findNearestCommonDominator(IDom, BB);
319  if (!IDom)
320  break;
321  }
322  if (IDom == &Block)
323  return nullptr;
324  return IDom;
325 }
326 
327 void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
328  RegScavenger *RS) {
329  // Get rid of the easy cases first.
330  if (!Save)
331  Save = &MBB;
332  else
333  Save = MDT->findNearestCommonDominator(Save, &MBB);
334  assert(Save);
335 
336  if (!Restore)
337  Restore = &MBB;
338  else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it
339  // means the block never returns. If that's the
340  // case, we don't want to call
341  // `findNearestCommonDominator`, which will
342  // return `Restore`.
343  Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
344  else
345  Restore = nullptr; // Abort, we can't find a restore point in this case.
346 
347  // Make sure we would be able to insert the restore code before the
348  // terminator.
349  if (Restore == &MBB) {
350  for (const MachineInstr &Terminator : MBB.terminators()) {
351  if (!useOrDefCSROrFI(Terminator, RS))
352  continue;
353  // One of the terminator needs to happen before the restore point.
354  if (MBB.succ_empty()) {
355  Restore = nullptr; // Abort, we can't find a restore point in this case.
356  break;
357  }
358  // Look for a restore point that post-dominates all the successors.
359  // The immediate post-dominator is what we are looking for.
360  Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
361  break;
362  }
363  }
364 
365  if (!Restore) {
366  LLVM_DEBUG(
367  dbgs() << "Restore point needs to be spanned on several blocks\n");
368  return;
369  }
370 
371  // Make sure Save and Restore are suitable for shrink-wrapping:
372  // 1. all path from Save needs to lead to Restore before exiting.
373  // 2. all path to Restore needs to go through Save from Entry.
374  // We achieve that by making sure that:
375  // A. Save dominates Restore.
376  // B. Restore post-dominates Save.
377  // C. Save and Restore are in the same loop.
378  bool SaveDominatesRestore = false;
379  bool RestorePostDominatesSave = false;
380  while (Restore &&
381  (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||
382  !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||
383  // Post-dominance is not enough in loops to ensure that all uses/defs
384  // are after the prologue and before the epilogue at runtime.
385  // E.g.,
386  // while(1) {
387  // Save
388  // Restore
389  // if (...)
390  // break;
391  // use/def CSRs
392  // }
393  // All the uses/defs of CSRs are dominated by Save and post-dominated
394  // by Restore. However, the CSRs uses are still reachable after
395  // Restore and before Save are executed.
396  //
397  // For now, just push the restore/save points outside of loops.
398  // FIXME: Refine the criteria to still find interesting cases
399  // for loops.
400  MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
401  // Fix (A).
402  if (!SaveDominatesRestore) {
403  Save = MDT->findNearestCommonDominator(Save, Restore);
404  continue;
405  }
406  // Fix (B).
407  if (!RestorePostDominatesSave)
408  Restore = MPDT->findNearestCommonDominator(Restore, Save);
409 
410  // Fix (C).
411  if (Restore && (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
412  if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) {
413  // Push Save outside of this loop if immediate dominator is different
414  // from save block. If immediate dominator is not different, bail out.
415  Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
416  if (!Save)
417  break;
418  } else {
419  // If the loop does not exit, there is no point in looking
420  // for a post-dominator outside the loop.
422  MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks);
423  // Push Restore outside of this loop.
424  // Look for the immediate post-dominator of the loop exits.
425  MachineBasicBlock *IPdom = Restore;
426  for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
427  IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);
428  if (!IPdom)
429  break;
430  }
431  // If the immediate post-dominator is not in a less nested loop,
432  // then we are stuck in a program with an infinite loop.
433  // In that case, we will not find a safe point, hence, bail out.
434  if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore))
435  Restore = IPdom;
436  else {
437  Restore = nullptr;
438  break;
439  }
440  }
441  }
442  }
443 }
444 
446  StringRef RemarkName, StringRef RemarkMessage,
447  const DiagnosticLocation &Loc,
448  const MachineBasicBlock *MBB) {
449  ORE->emit([&]() {
450  return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)
451  << RemarkMessage;
452  });
453 
454  LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
455  return false;
456 }
457 
458 bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
459  if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF))
460  return false;
461 
462  LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
463 
464  init(MF);
465 
467  if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {
468  // If MF is irreducible, a block may be in a loop without
469  // MachineLoopInfo reporting it. I.e., we may use the
470  // post-dominance property in loops, which lead to incorrect
471  // results. Moreover, we may miss that the prologue and
472  // epilogue are not in the same loop, leading to unbalanced
473  // construction/deconstruction of the stack frame.
474  return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG",
475  "Irreducible CFGs are not supported yet.",
476  MF.getFunction().getSubprogram(), &MF.front());
477  }
478 
480  std::unique_ptr<RegScavenger> RS(
481  TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
482 
483  for (MachineBasicBlock &MBB : MF) {
484  LLVM_DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' '
485  << MBB.getName() << '\n');
486 
487  if (MBB.isEHFuncletEntry())
488  return giveUpWithRemarks(ORE, "UnsupportedEHFunclets",
489  "EH Funclets are not supported yet.",
490  MBB.front().getDebugLoc(), &MBB);
491 
493  // Push the prologue and epilogue outside of the region that may throw (or
494  // jump out via inlineasm_br), by making sure that all the landing pads
495  // are at least at the boundary of the save and restore points. The
496  // problem is that a basic block can jump out from the middle in these
497  // cases, which we do not handle.
498  updateSaveRestorePoints(MBB, RS.get());
499  if (!ArePointsInteresting()) {
500  LLVM_DEBUG(dbgs() << "EHPad/inlineasm_br prevents shrink-wrapping\n");
501  return false;
502  }
503  continue;
504  }
505 
506  for (const MachineInstr &MI : MBB) {
507  if (!useOrDefCSROrFI(MI, RS.get()))
508  continue;
509  // Save (resp. restore) point must dominate (resp. post dominate)
510  // MI. Look for the proper basic block for those.
511  updateSaveRestorePoints(MBB, RS.get());
512  // If we are at a point where we cannot improve the placement of
513  // save/restore instructions, just give up.
514  if (!ArePointsInteresting()) {
515  LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
516  return false;
517  }
518  // No need to look for other instructions, this basic block
519  // will already be part of the handled region.
520  break;
521  }
522  }
523  if (!ArePointsInteresting()) {
524  // If the points are not interesting at this point, then they must be null
525  // because it means we did not encounter any frame/CSR related code.
526  // Otherwise, we would have returned from the previous loop.
527  assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
528  LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
529  return false;
530  }
531 
532  LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
533  << '\n');
534 
535  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
536  do {
537  LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
538  << Save->getNumber() << ' ' << Save->getName() << ' '
539  << MBFI->getBlockFreq(Save).getFrequency()
540  << "\nRestore: " << Restore->getNumber() << ' '
541  << Restore->getName() << ' '
542  << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
543 
544  bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
545  if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
546  EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) &&
547  ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
548  TFI->canUseAsEpilogue(*Restore)))
549  break;
550  LLVM_DEBUG(
551  dbgs() << "New points are too expensive or invalid for the target\n");
552  MachineBasicBlock *NewBB;
553  if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
554  Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
555  if (!Save)
556  break;
557  NewBB = Save;
558  } else {
559  // Restore is expensive.
560  Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
561  if (!Restore)
562  break;
563  NewBB = Restore;
564  }
565  updateSaveRestorePoints(*NewBB, RS.get());
566  } while (Save && Restore);
567 
568  if (!ArePointsInteresting()) {
569  ++NumCandidatesDropped;
570  return false;
571  }
572 
573  LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
574  << Save->getNumber() << ' ' << Save->getName()
575  << "\nRestore: " << Restore->getNumber() << ' '
576  << Restore->getName() << '\n');
577 
578  MachineFrameInfo &MFI = MF.getFrameInfo();
579  MFI.setSavePoint(Save);
580  MFI.setRestorePoint(Restore);
581  ++NumCandidates;
582  return false;
583 }
584 
585 bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) {
587 
588  switch (EnableShrinkWrapOpt) {
589  case cl::BOU_UNSET:
590  return TFI->enableShrinkWrapping(MF) &&
591  // Windows with CFI has some limitations that make it impossible
592  // to use shrink-wrapping.
594  // Sanitizers look at the value of the stack at the location
595  // of the crash. Since a crash can happen anywhere, the
596  // frame must be lowered before anything else happen for the
597  // sanitizers to be able to get a correct stack frame.
598  !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) ||
599  MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) ||
600  MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) ||
601  MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress));
602  // If EnableShrinkWrap is set, it takes precedence on whatever the
603  // target sets. The rational is that we assume we want to test
604  // something related to shrink-wrapping.
605  case cl::BOU_TRUE:
606  return true;
607  case cl::BOU_FALSE:
608  return false;
609  }
610  llvm_unreachable("Invalid shrink-wrapping state");
611 }
llvm::MachineDominatorTree::findNearestCommonDominator
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
Definition: MachineDominators.h:155
llvm::TargetLoweringBase::getStackPointerRegisterToSaveRestore
Register getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
Definition: TargetLowering.h:1738
FindIDom
static MachineBasicBlock * FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, DominanceAnalysis &Dom)
Helper function to find the immediate (post) dominator.
Definition: ShrinkWrap.cpp:314
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
TargetFrameLowering.h
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:127
llvm::TargetFrameLowering
Information about stack frame layout on the target.
Definition: TargetFrameLowering.h:43
llvm::cl::BOU_FALSE
@ BOU_FALSE
Definition: CommandLine.h:623
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
llvm::MachineBasicBlock::clear
void clear()
Definition: MachineBasicBlock.h:942
llvm::MachineBasicBlock::isEHFuncletEntry
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
Definition: MachineBasicBlock.h:552
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1541
ErrorHandling.h
llvm::MachineOptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: MachineOptimizationRemarkEmitter.h:150
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
RegisterClassInfo.h
MachineBasicBlock.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
TargetInstrInfo.h
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
giveUpWithRemarks
static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE, StringRef RemarkName, StringRef RemarkMessage, const DiagnosticLocation &Loc, const MachineBasicBlock *MBB)
Definition: ShrinkWrap.cpp:445
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:109
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:288
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:230
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
TargetLowering.h
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:824
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
MachineLoopInfo.h
TargetMachine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::TargetFrameLowering::enableShrinkWrapping
virtual bool enableShrinkWrapping(const MachineFunction &MF) const
Returns true if the target will correctly handle shrink wrapping.
Definition: TargetFrameLowering.h:191
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::TargetFrameLowering::canUseAsEpilogue
virtual bool canUseAsEpilogue(const MachineBasicBlock &MBB) const
Check whether or not the given MBB can be used as a epilogue for the target.
Definition: TargetFrameLowering.h:409
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:173
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
BitVector.h
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:812
llvm::BitVector
Definition: BitVector.h:74
llvm::MachinePostDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
Definition: MachinePostDominators.h:50
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
MachineOptimizationRemarkEmitter.h
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:630
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:626
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:43
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:418
llvm::cl::BOU_UNSET
@ BOU_UNSET
Definition: CommandLine.h:623
llvm::MachineOptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Emit an optimization remark.
Definition: MachineOptimizationRemarkEmitter.cpp:49
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
uint64_t
llvm::MachineOptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: MachineOptimizationRemarkEmitter.h:82
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::RegScavenger
Definition: RegisterScavenging.h:34
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:35
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
MachineFunctionPass.h
llvm::MachineFrameInfo::setRestorePoint
void setRestorePoint(MachineBasicBlock *NewRestore)
Definition: MachineFrameInfo.h:775
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:542
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:30
MachinePostDominators.h
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:349
llvm::MachineFrameInfo::setSavePoint
void setSavePoint(MachineBasicBlock *NewSave)
Definition: MachineFrameInfo.h:773
llvm::MachineFunction
Definition: MachineFunction.h:234
CFG.h
llvm::MachineBasicBlock::succ_empty
bool succ_empty() const
Definition: MachineBasicBlock.h:347
llvm::TargetMachine::getMCAsmInfo
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
Definition: TargetMachine.h:207
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
MCAsmInfo.h
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:526
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
Shrink
This would be a win on but not x86 or ppc64 Shrink
Definition: README.txt:41
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::MachineOptimizationRemarkEmitterPass
The analysis pass.
Definition: MachineOptimizationRemarkEmitter.h:218
llvm::DiagnosticLocation
Definition: DiagnosticInfo.h:349
TargetSubtargetInfo.h
llvm::ShrinkWrapID
char & ShrinkWrapID
ShrinkWrap pass. Look for the best place to insert save and restore.
Definition: ShrinkWrap.cpp:250
llvm::initializeShrinkWrapPass
void initializeShrinkWrapPass(PassRegistry &)
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
llvm::MachinePostDominatorTree
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
Definition: MachinePostDominators.h:27
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::TargetFrameLowering::canUseAsPrologue
virtual bool canUseAsPrologue(const MachineBasicBlock &MBB) const
Check whether or not the given MBB can be used as a prologue for the target.
Definition: TargetFrameLowering.h:397
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
Attributes.h
llvm::MachinePostDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachinePostDominators.h:54
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:596
llvm::TargetSubtargetInfo::getFrameLowering
virtual const TargetFrameLowering * getFrameLowering() const
Definition: TargetSubtargetInfo.h:93
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::MachineFunction::getTarget
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Definition: MachineFunction.h:626
MachineFrameInfo.h
Function.h
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:247
llvm::MachineLoopInfo::getLoopDepth
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
Definition: MachineLoopInfo.h:137
llvm::BitVector::find_next
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:300
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
llvm::RegisterClassInfo::getLastCalleeSavedAlias
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
Definition: RegisterClassInfo.h:116
llvm::cl::BOU_TRUE
@ BOU_TRUE
Definition: CommandLine.h:623
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:107
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
PostOrderIterator.h
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
llvm::TargetSubtargetInfo::getTargetLowering
virtual const TargetLowering * getTargetLowering() const
Definition: TargetSubtargetInfo.h:96
llvm::TargetRegisterInfo::requiresRegisterScavenging
virtual bool requiresRegisterScavenging(const MachineFunction &MF) const
Returns true if the target requires (and can make use of) the register scavenger.
Definition: TargetRegisterInfo.h:883
SmallVector.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: ShrinkWrap.cpp:90
llvm::MachineBasicBlock::isInlineAsmBrIndirectTarget
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
Definition: MachineBasicBlock.h:594
llvm::BitVector::find_first
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:292
MachineOperand.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::TargetFrameLowering::determineCalleeSaves
virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const
This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...
Definition: TargetFrameLoweringImpl.cpp:78
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::MachinePostDominatorTree::findNearestCommonDominator
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B) const
Definition: MachinePostDominators.h:77
llvm::cl::desc
Definition: CommandLine.h:412
RegisterScavenging.h
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::MachineFunction::empty
bool empty() const
Definition: MachineFunction.h:823
MachineFunction.h
llvm::MachineBlockFrequencyInfo::getEntryFreq
uint64_t getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
Definition: MachineBlockFrequencyInfo.cpp:289
llvm::MCAsmInfo::usesWindowsCFI
bool usesWindowsCFI() const
Definition: MCAsmInfo.h:778
EnableShrinkWrapOpt
static cl::opt< cl::boolOrDefault > EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, cl::desc("enable the shrink-wrapping pass"))
InitializePasses.h
MachineBlockFrequencyInfo.h
llvm::MCID::Terminator
@ Terminator
Definition: MCInstrDesc.h:155
TargetRegisterInfo.h
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:314
Debug.h
SetVector.h
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37