LLVM  16.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  const MachineFunction *MF = MI.getParent()->getParent();
278  for (const MachineOperand &MO : MI.operands()) {
279  bool UseOrDefCSR = false;
280  if (MO.isReg()) {
281  // Ignore instructions like DBG_VALUE which don't read/def the register.
282  if (!MO.isDef() && !MO.readsReg())
283  continue;
284  Register PhysReg = MO.getReg();
285  if (!PhysReg)
286  continue;
287  assert(Register::isPhysicalRegister(PhysReg) && "Unallocated register?!");
288  // The stack pointer is not normally described as a callee-saved register
289  // in calling convention definitions, so we need to watch for it
290  // separately. An SP mentioned by a call instruction, we can ignore,
291  // though, as it's harmless and we do not want to effectively disable tail
292  // calls by forcing the restore point to post-dominate them.
293  // PPC's LR is also not normally described as a callee-saved register in
294  // calling convention definitions, so we need to watch for it, too. An LR
295  // mentioned implicitly by a return (or "branch to link register")
296  // instruction we can ignore, otherwise we may pessimize shrinkwrapping.
297  UseOrDefCSR =
298  (!MI.isCall() && PhysReg == SP) ||
299  RCI.getLastCalleeSavedAlias(PhysReg) ||
300  (!MI.isReturn() && TRI->isNonallocatableRegisterCalleeSave(PhysReg));
301  } else if (MO.isRegMask()) {
302  // Check if this regmask clobbers any of the CSRs.
303  for (unsigned Reg : getCurrentCSRs(RS)) {
304  if (MO.clobbersPhysReg(Reg)) {
305  UseOrDefCSR = true;
306  break;
307  }
308  }
309  }
310  // Skip FrameIndex operands in DBG_VALUE instructions.
311  if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
312  LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
313  << MO.isFI() << "): " << MI << '\n');
314  return true;
315  }
316  }
317  return false;
318 }
319 
320 /// Helper function to find the immediate (post) dominator.
321 template <typename ListOfBBs, typename DominanceAnalysis>
322 static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
323  DominanceAnalysis &Dom) {
324  MachineBasicBlock *IDom = &Block;
325  for (MachineBasicBlock *BB : BBs) {
326  IDom = Dom.findNearestCommonDominator(IDom, BB);
327  if (!IDom)
328  break;
329  }
330  if (IDom == &Block)
331  return nullptr;
332  return IDom;
333 }
334 
335 void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
336  RegScavenger *RS) {
337  // Get rid of the easy cases first.
338  if (!Save)
339  Save = &MBB;
340  else
341  Save = MDT->findNearestCommonDominator(Save, &MBB);
342  assert(Save);
343 
344  if (!Restore)
345  Restore = &MBB;
346  else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it
347  // means the block never returns. If that's the
348  // case, we don't want to call
349  // `findNearestCommonDominator`, which will
350  // return `Restore`.
351  Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
352  else
353  Restore = nullptr; // Abort, we can't find a restore point in this case.
354 
355  // Make sure we would be able to insert the restore code before the
356  // terminator.
357  if (Restore == &MBB) {
358  for (const MachineInstr &Terminator : MBB.terminators()) {
359  if (!useOrDefCSROrFI(Terminator, RS))
360  continue;
361  // One of the terminator needs to happen before the restore point.
362  if (MBB.succ_empty()) {
363  Restore = nullptr; // Abort, we can't find a restore point in this case.
364  break;
365  }
366  // Look for a restore point that post-dominates all the successors.
367  // The immediate post-dominator is what we are looking for.
368  Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
369  break;
370  }
371  }
372 
373  if (!Restore) {
374  LLVM_DEBUG(
375  dbgs() << "Restore point needs to be spanned on several blocks\n");
376  return;
377  }
378 
379  // Make sure Save and Restore are suitable for shrink-wrapping:
380  // 1. all path from Save needs to lead to Restore before exiting.
381  // 2. all path to Restore needs to go through Save from Entry.
382  // We achieve that by making sure that:
383  // A. Save dominates Restore.
384  // B. Restore post-dominates Save.
385  // C. Save and Restore are in the same loop.
386  bool SaveDominatesRestore = false;
387  bool RestorePostDominatesSave = false;
388  while (Restore &&
389  (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||
390  !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||
391  // Post-dominance is not enough in loops to ensure that all uses/defs
392  // are after the prologue and before the epilogue at runtime.
393  // E.g.,
394  // while(1) {
395  // Save
396  // Restore
397  // if (...)
398  // break;
399  // use/def CSRs
400  // }
401  // All the uses/defs of CSRs are dominated by Save and post-dominated
402  // by Restore. However, the CSRs uses are still reachable after
403  // Restore and before Save are executed.
404  //
405  // For now, just push the restore/save points outside of loops.
406  // FIXME: Refine the criteria to still find interesting cases
407  // for loops.
408  MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
409  // Fix (A).
410  if (!SaveDominatesRestore) {
411  Save = MDT->findNearestCommonDominator(Save, Restore);
412  continue;
413  }
414  // Fix (B).
415  if (!RestorePostDominatesSave)
416  Restore = MPDT->findNearestCommonDominator(Restore, Save);
417 
418  // Fix (C).
419  if (Restore && (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
420  if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) {
421  // Push Save outside of this loop if immediate dominator is different
422  // from save block. If immediate dominator is not different, bail out.
423  Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
424  if (!Save)
425  break;
426  } else {
427  // If the loop does not exit, there is no point in looking
428  // for a post-dominator outside the loop.
430  MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks);
431  // Push Restore outside of this loop.
432  // Look for the immediate post-dominator of the loop exits.
433  MachineBasicBlock *IPdom = Restore;
434  for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
435  IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);
436  if (!IPdom)
437  break;
438  }
439  // If the immediate post-dominator is not in a less nested loop,
440  // then we are stuck in a program with an infinite loop.
441  // In that case, we will not find a safe point, hence, bail out.
442  if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore))
443  Restore = IPdom;
444  else {
445  Restore = nullptr;
446  break;
447  }
448  }
449  }
450  }
451 }
452 
454  StringRef RemarkName, StringRef RemarkMessage,
455  const DiagnosticLocation &Loc,
456  const MachineBasicBlock *MBB) {
457  ORE->emit([&]() {
458  return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)
459  << RemarkMessage;
460  });
461 
462  LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
463  return false;
464 }
465 
466 bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
467  if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF))
468  return false;
469 
470  LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
471 
472  init(MF);
473 
475  if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {
476  // If MF is irreducible, a block may be in a loop without
477  // MachineLoopInfo reporting it. I.e., we may use the
478  // post-dominance property in loops, which lead to incorrect
479  // results. Moreover, we may miss that the prologue and
480  // epilogue are not in the same loop, leading to unbalanced
481  // construction/deconstruction of the stack frame.
482  return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG",
483  "Irreducible CFGs are not supported yet.",
484  MF.getFunction().getSubprogram(), &MF.front());
485  }
486 
488  std::unique_ptr<RegScavenger> RS(
489  TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
490 
491  for (MachineBasicBlock &MBB : MF) {
492  LLVM_DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' '
493  << MBB.getName() << '\n');
494 
495  if (MBB.isEHFuncletEntry())
496  return giveUpWithRemarks(ORE, "UnsupportedEHFunclets",
497  "EH Funclets are not supported yet.",
498  MBB.front().getDebugLoc(), &MBB);
499 
501  // Push the prologue and epilogue outside of the region that may throw (or
502  // jump out via inlineasm_br), by making sure that all the landing pads
503  // are at least at the boundary of the save and restore points. The
504  // problem is that a basic block can jump out from the middle in these
505  // cases, which we do not handle.
506  updateSaveRestorePoints(MBB, RS.get());
507  if (!ArePointsInteresting()) {
508  LLVM_DEBUG(dbgs() << "EHPad/inlineasm_br prevents shrink-wrapping\n");
509  return false;
510  }
511  continue;
512  }
513 
514  for (const MachineInstr &MI : MBB) {
515  if (!useOrDefCSROrFI(MI, RS.get()))
516  continue;
517  // Save (resp. restore) point must dominate (resp. post dominate)
518  // MI. Look for the proper basic block for those.
519  updateSaveRestorePoints(MBB, RS.get());
520  // If we are at a point where we cannot improve the placement of
521  // save/restore instructions, just give up.
522  if (!ArePointsInteresting()) {
523  LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
524  return false;
525  }
526  // No need to look for other instructions, this basic block
527  // will already be part of the handled region.
528  break;
529  }
530  }
531  if (!ArePointsInteresting()) {
532  // If the points are not interesting at this point, then they must be null
533  // because it means we did not encounter any frame/CSR related code.
534  // Otherwise, we would have returned from the previous loop.
535  assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
536  LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
537  return false;
538  }
539 
540  LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
541  << '\n');
542 
543  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
544  do {
545  LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
546  << Save->getNumber() << ' ' << Save->getName() << ' '
547  << MBFI->getBlockFreq(Save).getFrequency()
548  << "\nRestore: " << Restore->getNumber() << ' '
549  << Restore->getName() << ' '
550  << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
551 
552  bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
553  if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
554  EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) &&
555  ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
556  TFI->canUseAsEpilogue(*Restore)))
557  break;
558  LLVM_DEBUG(
559  dbgs() << "New points are too expensive or invalid for the target\n");
560  MachineBasicBlock *NewBB;
561  if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
562  Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
563  if (!Save)
564  break;
565  NewBB = Save;
566  } else {
567  // Restore is expensive.
568  Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
569  if (!Restore)
570  break;
571  NewBB = Restore;
572  }
573  updateSaveRestorePoints(*NewBB, RS.get());
574  } while (Save && Restore);
575 
576  if (!ArePointsInteresting()) {
577  ++NumCandidatesDropped;
578  return false;
579  }
580 
581  LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
582  << Save->getNumber() << ' ' << Save->getName()
583  << "\nRestore: " << Restore->getNumber() << ' '
584  << Restore->getName() << '\n');
585 
586  MachineFrameInfo &MFI = MF.getFrameInfo();
587  MFI.setSavePoint(Save);
588  MFI.setRestorePoint(Restore);
589  ++NumCandidates;
590  return false;
591 }
592 
593 bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) {
595 
596  switch (EnableShrinkWrapOpt) {
597  case cl::BOU_UNSET:
598  return TFI->enableShrinkWrapping(MF) &&
599  // Windows with CFI has some limitations that make it impossible
600  // to use shrink-wrapping.
602  // Sanitizers look at the value of the stack at the location
603  // of the crash. Since a crash can happen anywhere, the
604  // frame must be lowered before anything else happen for the
605  // sanitizers to be able to get a correct stack frame.
606  !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) ||
607  MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) ||
608  MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) ||
609  MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress));
610  // If EnableShrinkWrap is set, it takes precedence on whatever the
611  // target sets. The rational is that we assume we want to test
612  // something related to shrink-wrapping.
613  case cl::BOU_TRUE:
614  return true;
615  case cl::BOU_FALSE:
616  return false;
617  }
618  llvm_unreachable("Invalid shrink-wrapping state");
619 }
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:160
llvm::TargetLoweringBase::getStackPointerRegisterToSaveRestore
Register getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
Definition: TargetLowering.h:1827
FindIDom
static MachineBasicBlock * FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, DominanceAnalysis &Dom)
Helper function to find the immediate (post) dominator.
Definition: ShrinkWrap.cpp:322
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
TargetFrameLowering.h
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:126
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::TargetFrameLowering
Information about stack frame layout on the target.
Definition: TargetFrameLowering.h:43
llvm::cl::BOU_FALSE
@ BOU_FALSE
Definition: CommandLine.h:631
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:95
llvm::MachineBasicBlock::clear
void clear()
Definition: MachineBasicBlock.h:1001
llvm::MachineBasicBlock::isEHFuncletEntry
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
Definition: MachineBasicBlock.h:602
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1626
ErrorHandling.h
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineOptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: MachineOptimizationRemarkEmitter.h:151
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:127
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
TargetInstrInfo.h
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
giveUpWithRemarks
static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE, StringRef RemarkName, StringRef RemarkMessage, const DiagnosticLocation &Loc, const MachineBasicBlock *MBB)
Definition: ShrinkWrap.cpp:453
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:114
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:325
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
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:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
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:866
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
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:24
llvm::TargetFrameLowering::enableShrinkWrapping
virtual bool enableShrinkWrapping(const MachineFunction &MF) const
Returns true if the target will correctly handle shrink wrapping.
Definition: TargetFrameLowering.h:194
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:427
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
llvm::TargetRegisterInfo::isNonallocatableRegisterCalleeSave
virtual bool isNonallocatableRegisterCalleeSave(MCRegister Reg) const
Some targets have non-allocatable registers that aren't technically part of the explicit callee saved...
Definition: TargetRegisterInfo.h:1149
false
Definition: StackSlotColoring.cpp:141
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
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:33
BitVector.h
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:854
llvm::BitVector
Definition: BitVector.h:75
llvm::MachinePostDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
Definition: MachinePostDominators.h:50
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
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:657
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:629
llvm::cl::opt
Definition: CommandLine.h:1412
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:42
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:445
llvm::cl::BOU_UNSET
@ BOU_UNSET
Definition: CommandLine.h:631
llvm::MachineOptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Emit an optimization remark.
Definition: MachineOptimizationRemarkEmitter.cpp:48
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
uint64_t
llvm::MachineOptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: MachineOptimizationRemarkEmitter.h:83
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:34
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
MachineFunctionPass.h
llvm::MachineFrameInfo::setRestorePoint
void setRestorePoint(MachineBasicBlock *NewRestore)
Definition: MachineFrameInfo.h:807
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:567
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:29
MachinePostDominators.h
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
llvm::MachineFrameInfo::setSavePoint
void setSavePoint(MachineBasicBlock *NewSave)
Definition: MachineFrameInfo.h:805
llvm::MachineFunction
Definition: MachineFunction.h:257
CFG.h
llvm::MachineBasicBlock::succ_empty
bool succ_empty() const
Definition: MachineBasicBlock.h:384
llvm::TargetMachine::getMCAsmInfo
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
Definition: TargetMachine.h:204
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
MCAsmInfo.h
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:576
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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:143
llvm::MachineOptimizationRemarkEmitterPass
The analysis pass.
Definition: MachineOptimizationRemarkEmitter.h:219
llvm::DiagnosticLocation
Definition: DiagnosticInfo.h:298
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:62
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:415
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:623
llvm::TargetSubtargetInfo::getFrameLowering
virtual const TargetFrameLowering * getFrameLowering() const
Definition: TargetSubtargetInfo.h:96
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:653
MachineFrameInfo.h
Function.h
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:284
llvm::MachineLoopInfo::getLoopDepth
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
Definition: MachineLoopInfo.h:136
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:301
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::RegisterClassInfo::getLastCalleeSavedAlias
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
Definition: RegisterClassInfo.h:118
llvm::cl::BOU_TRUE
@ BOU_TRUE
Definition: CommandLine.h:631
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:106
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:99
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:915
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:644
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:293
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:83
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:413
RegisterScavenging.h
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::MachineFunction::empty
bool empty() const
Definition: MachineFunction.h:865
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:793
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:157
TargetRegisterInfo.h
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:311
Debug.h
SetVector.h
MachineDominators.h