LLVM 24.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
51#include "CodeGenOptions.h"
52#include "llvm/ADT/BitVector.h"
54#include "llvm/ADT/SetVector.h"
56#include "llvm/ADT/Statistic.h"
57#include "llvm/Analysis/CFG.h"
77#include "llvm/IR/Attributes.h"
78#include "llvm/IR/Function.h"
80#include "llvm/MC/MCAsmInfo.h"
81#include "llvm/Pass.h"
82#include "llvm/Support/Debug.h"
86#include <cassert>
87#include <memory>
88
89using namespace llvm;
90
91#define DEBUG_TYPE "shrink-wrap"
92
93STATISTIC(NumFunc, "Number of functions");
94STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
95STATISTIC(NumCandidatesDropped,
96 "Number of shrink-wrapping candidates dropped because of frequency");
97
98namespace {
99
100/// Class to determine where the safe point to insert the
101/// prologue and epilogue are.
102/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
103/// shrink-wrapping term for prologue/epilogue placement, this pass
104/// does not rely on expensive data-flow analysis. Instead we use the
105/// dominance properties and loop information to decide which point
106/// are safe for such insertion.
107class ShrinkWrapImpl {
108 /// Hold callee-saved information.
109 const RegisterClassInfo *RCI = nullptr;
110 MachineDominatorTree *MDT = nullptr;
111 MachinePostDominatorTree *MPDT = nullptr;
112
113 /// Current safe point found for the prologue.
114 /// The prologue will be inserted before the first instruction
115 /// in this basic block.
116 MachineBasicBlock *Save = nullptr;
117
118 /// Current safe point found for the epilogue.
119 /// The epilogue will be inserted before the first terminator instruction
120 /// in this basic block.
121 MachineBasicBlock *Restore = nullptr;
122
123 /// Hold the information of the basic block frequency.
124 /// Use to check the profitability of the new points.
125 MachineBlockFrequencyInfo *MBFI = nullptr;
126
127 /// Hold the loop information. Used to determine if Save and Restore
128 /// are in the same loop.
129 MachineLoopInfo *MLI = nullptr;
130
131 // Emit remarks.
133
134 /// Frequency of the Entry block.
135 BlockFrequency EntryFreq;
136
137 /// Current opcode for frame setup.
138 unsigned FrameSetupOpcode = ~0u;
139
140 /// Current opcode for frame destroy.
141 unsigned FrameDestroyOpcode = ~0u;
142
143 /// Stack pointer register, used by llvm.{savestack,restorestack}
144 Register SP;
145
146 /// Entry block.
147 const MachineBasicBlock *Entry = nullptr;
148
149 using SetOfRegs = SmallSetVector<unsigned, 16>;
150
151 /// Registers that need to be saved for the current function.
152 mutable SetOfRegs CurrentCSRs;
153
154 /// Current MachineFunction.
155 MachineFunction *MachineFunc = nullptr;
156
157 /// Is `true` for the block numbers where we assume possible stack accesses
158 /// or computation of stack-relative addresses on any CFG path including the
159 /// block itself. Is `false` for basic blocks where we can guarantee the
160 /// opposite. False positives won't lead to incorrect analysis results,
161 /// therefore this approach is fair.
162 BitVector StackAddressUsedBlockInfo;
163
164 /// Check if \p MI uses or defines a callee-saved register or
165 /// a frame index. If this is the case, this means \p MI must happen
166 /// after Save and before Restore.
167 bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
168 bool StackAddressUsed) const;
169
170 const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {
171 if (CurrentCSRs.empty()) {
172 BitVector SavedRegs;
173 const TargetFrameLowering *TFI =
174 MachineFunc->getSubtarget().getFrameLowering();
175
176 TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS);
177
178 for (int Reg = SavedRegs.find_first(); Reg != -1;
179 Reg = SavedRegs.find_next(Reg))
180 CurrentCSRs.insert((unsigned)Reg);
181 }
182 return CurrentCSRs;
183 }
184
185 /// Update the Save and Restore points such that \p MBB is in
186 /// the region that is dominated by Save and post-dominated by Restore
187 /// and Save and Restore still match the safe point definition.
188 /// Such point may not exist and Save and/or Restore may be null after
189 /// this call.
190 void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
191
192 // Try to find safe point based on dominance and block frequency without
193 // any change in IR.
194 bool performShrinkWrapping(
195 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
196 RegScavenger *RS);
197
198 /// This function tries to split the restore point if doing so can shrink the
199 /// save point further. \return True if restore point is split.
200 bool postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
201 RegScavenger *RS);
202
203 /// This function analyzes if the restore point can split to create a new
204 /// restore point. This function collects
205 /// 1. Any preds of current restore that are reachable by callee save/FI
206 /// blocks
207 /// - indicated by DirtyPreds
208 /// 2. Any preds of current restore that are not DirtyPreds - indicated by
209 /// CleanPreds
210 /// Both sets should be non-empty for considering restore point split.
211 bool checkIfRestoreSplittable(
212 const MachineBasicBlock *CurRestore,
213 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
214 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,
215 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,
216 const TargetInstrInfo *TII, RegScavenger *RS);
217
218 /// Initialize the pass for \p MF.
219 void init(MachineFunction &MF) {
220 Save = nullptr;
221 Restore = nullptr;
222 EntryFreq = MBFI->getEntryFreq();
223 const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
224 const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
225 FrameSetupOpcode = TII.getCallFrameSetupOpcode();
226 FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
228 Entry = &MF.front();
229 CurrentCSRs.clear();
230 MachineFunc = &MF;
231
232 ++NumFunc;
233 }
234
235 /// Check whether or not Save and Restore points are still interesting for
236 /// shrink-wrapping.
237 bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
238
239public:
240 ShrinkWrapImpl(const RegisterClassInfo *RCI, MachineDominatorTree *MDT,
241 MachinePostDominatorTree *MPDT,
242 MachineBlockFrequencyInfo *MBFI, MachineLoopInfo *MLI,
243 MachineOptimizationRemarkEmitter *ORE)
244 : RCI(RCI), MDT(MDT), MPDT(MPDT), MBFI(MBFI), MLI(MLI), ORE(ORE) {}
245
246 /// Check if shrink wrapping is enabled for this target and function.
247 static bool isShrinkWrapEnabled(const MachineFunction &MF);
248
249 bool run(MachineFunction &MF);
250};
251
252class ShrinkWrapLegacy : public MachineFunctionPass {
253public:
254 static char ID;
255
256 ShrinkWrapLegacy() : MachineFunctionPass(ID) {}
257
258 void getAnalysisUsage(AnalysisUsage &AU) const override {
259 AU.setPreservesAll();
260 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
261 AU.addRequired<MachineDominatorTreeWrapperPass>();
262 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
263 AU.addRequired<MachineLoopInfoWrapperPass>();
264 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
265 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
267 }
268
269 MachineFunctionProperties getRequiredProperties() const override {
270 return MachineFunctionProperties().setNoVRegs();
271 }
272
273 StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
274
275 /// Perform the shrink-wrapping analysis and update
276 /// the MachineFrameInfo attached to \p MF with the results.
277 bool runOnMachineFunction(MachineFunction &MF) override;
278};
279
280} // end anonymous namespace
281
282char ShrinkWrapLegacy::ID = 0;
283
284char &llvm::ShrinkWrapID = ShrinkWrapLegacy::ID;
285
286INITIALIZE_PASS_BEGIN(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,
287 false)
294INITIALIZE_PASS_END(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,
295 false)
296
297bool ShrinkWrapImpl::useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
298 bool StackAddressUsed) const {
299 /// Check if \p Op is known to access an address not on the function's stack .
300 /// At the moment, accesses where the underlying object is a global, function
301 /// argument, or jump table are considered non-stack accesses. Note that the
302 /// caller's stack may get accessed when passing an argument via the stack,
303 /// but not the stack of the current function.
304 ///
305 auto IsKnownNonStackPtr = [](MachineMemOperand *Op) {
306 if (Op->getValue()) {
308 getUnderlyingObjects(Op->getValue(), Objs);
309 return !Objs.empty() && all_of(Objs, [](const Value *UO) {
310 if (auto *Arg = dyn_cast<Argument>(UO))
311 return !Arg->hasPassPointeeByValueCopyAttr();
312 return isa<GlobalValue>(UO);
313 });
314 }
315 if (const PseudoSourceValue *PSV = Op->getPseudoValue())
316 return PSV->isJumpTable() || PSV->isConstantPool();
317 return false;
318 };
319 // Load/store operations may access the stack indirectly when we previously
320 // computed an address to a stack location.
321 if (StackAddressUsed && MI.mayLoadOrStore() &&
322 (MI.isCall() || MI.hasUnmodeledSideEffects() || MI.memoperands_empty() ||
323 !all_of(MI.memoperands(), IsKnownNonStackPtr)))
324 return true;
325
326 if (MI.getOpcode() == FrameSetupOpcode ||
327 MI.getOpcode() == FrameDestroyOpcode) {
328 LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
329 return true;
330 }
331 const MachineFunction *MF = MI.getParent()->getParent();
333 for (const MachineOperand &MO : MI.operands()) {
334 bool UseOrDefCSR = false;
335 if (MO.isReg()) {
336 // Ignore instructions like DBG_VALUE which don't read/def the register.
337 if (!MO.isDef() && !MO.readsReg())
338 continue;
339 Register PhysReg = MO.getReg();
340 if (!PhysReg)
341 continue;
342 assert(PhysReg.isPhysical() && "Unallocated register?!");
343 // The stack pointer is not normally described as a callee-saved register
344 // in calling convention definitions, so we need to watch for it
345 // separately. An SP mentioned by a call instruction, we can ignore,
346 // though, as it's harmless and we do not want to effectively disable tail
347 // calls by forcing the restore point to post-dominate them.
348 // PPC's LR is also not normally described as a callee-saved register in
349 // calling convention definitions, so we need to watch for it, too. An LR
350 // mentioned implicitly by a return (or "branch to link register")
351 // instruction we can ignore, otherwise we may pessimize shrinkwrapping.
352 // PPC's Frame pointer (FP) is also not described as a callee-saved
353 // register. Until the FP is assigned a Physical Register PPC's FP needs
354 // to be checked separately.
355 UseOrDefCSR = (!MI.isCall() && PhysReg == SP) ||
356 RCI->getLastCalleeSavedAlias(PhysReg) ||
357 (!MI.isReturn() &&
358 TRI->isNonallocatableRegisterCalleeSave(PhysReg)) ||
359 TRI->isVirtualFrameRegister(PhysReg);
360 } else if (MO.isRegMask()) {
361 // Check if this regmask clobbers any of the CSRs.
362 for (unsigned Reg : getCurrentCSRs(RS)) {
363 if (MO.clobbersPhysReg(Reg)) {
364 UseOrDefCSR = true;
365 break;
366 }
367 }
368 }
369 // Skip FrameIndex operands in DBG_VALUE instructions.
370 if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
371 LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
372 << MO.isFI() << "): " << MI << '\n');
373 return true;
374 }
375 }
376 return false;
377}
378
379/// Helper function to find the immediate (post) dominator.
380template <typename ListOfBBs, typename DominanceAnalysis>
382 DominanceAnalysis &Dom, bool Strict = true) {
383 if (BBs.begin() == BBs.end())
384 return Strict ? nullptr : &Block;
385 MachineBasicBlock *IDom = Dom.findNearestCommonDominator(iterator_range(BBs));
386 if (Strict && IDom == &Block)
387 return nullptr;
388 return IDom;
389}
390
392 MachineBasicBlock &Entry) {
393 // Check if the block is analyzable.
394 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
396 return !TII.analyzeBranch(Entry, TBB, FBB, Cond);
397}
398
399/// Determines if any predecessor of MBB is on the path from block that has use
400/// or def of CSRs/FI to MBB.
401/// ReachableByDirty: All blocks reachable from block that has use or def of
402/// CSR/FI.
403static bool
405 const MachineBasicBlock &MBB) {
406 for (const MachineBasicBlock *PredBB : MBB.predecessors())
407 if (ReachableByDirty.count(PredBB))
408 return true;
409 return false;
410}
411
412/// Derives the list of all the basic blocks reachable from MBB.
414 const MachineBasicBlock &MBB) {
415 SmallVector<MachineBasicBlock *, 4> Worklist(MBB.successors());
416 Visited.insert(&MBB);
417 while (!Worklist.empty()) {
418 MachineBasicBlock *SuccMBB = Worklist.pop_back_val();
419 if (!Visited.insert(SuccMBB).second)
420 continue;
421 Worklist.append(SuccMBB->succ_begin(), SuccMBB->succ_end());
422 }
423}
424
425/// Collect blocks reachable by use or def of CSRs/FI.
428 DenseSet<const MachineBasicBlock *> &ReachableByDirty) {
429 for (const MachineBasicBlock *MBB : DirtyBBs) {
430 if (ReachableByDirty.count(MBB))
431 continue;
432 // Mark all offsprings as reachable.
433 markAllReachable(ReachableByDirty, *MBB);
434 }
435}
436
437/// \return true if there is a clean path from SavePoint to the original
438/// Restore.
439static bool
443 SmallVector<MachineBasicBlock *, 4> Worklist(CleanPreds);
444 while (!Worklist.empty()) {
445 MachineBasicBlock *CleanBB = Worklist.pop_back_val();
446 if (CleanBB == SavePoint)
447 return true;
448 if (!Visited.insert(CleanBB).second || !CleanBB->pred_size())
449 continue;
450 Worklist.append(CleanBB->pred_begin(), CleanBB->pred_end());
451 }
452 return false;
453}
454
455/// This function updates the branches post restore point split.
456///
457/// Restore point has been split.
458/// Old restore point: MBB
459/// New restore point: NMBB
460/// Any basic block(say BBToUpdate) which had a fallthrough to MBB
461/// previously should
462/// 1. Fallthrough to NMBB iff NMBB is inserted immediately above MBB in the
463/// block layout OR
464/// 2. Branch unconditionally to NMBB iff NMBB is inserted at any other place.
465static void updateTerminator(MachineBasicBlock *BBToUpdate,
466 MachineBasicBlock *NMBB,
467 const TargetInstrInfo *TII) {
468 DebugLoc DL = BBToUpdate->findBranchDebugLoc();
469 // if NMBB isn't the new layout successor for BBToUpdate, insert unconditional
470 // branch to it
471 if (!BBToUpdate->isLayoutSuccessor(NMBB))
472 TII->insertUnconditionalBranch(*BBToUpdate, NMBB, DL);
473}
474
475/// This function splits the restore point and returns new restore point/BB.
476///
477/// DirtyPreds: Predessors of \p MBB that are ReachableByDirty
478///
479/// Decision has been made to split the restore point.
480/// old restore point: \p MBB
481/// new restore point: \p NMBB
482/// This function makes the necessary block layout changes so that
483/// 1. \p NMBB points to \p MBB unconditionally
484/// 2. All dirtyPreds that previously pointed to \p MBB point to \p NMBB
485static MachineBasicBlock *
488 const TargetInstrInfo *TII) {
489 MachineFunction *MF = MBB->getParent();
490
491 // get the list of DirtyPreds who have a fallthrough to MBB
492 // before the block layout change. This is just to ensure that if the NMBB is
493 // inserted after MBB, then we create unconditional branch from
494 // DirtyPred/CleanPred to NMBB
496 for (MachineBasicBlock *BB : DirtyPreds)
497 if (BB->getFallThrough(false) == MBB)
498 MBBFallthrough.insert(BB);
499
501 // Insert this block at the end of the function. Inserting in between may
502 // interfere with control flow optimizer decisions.
503 MF->insert(MF->end(), NMBB);
504
505 for (const MachineBasicBlock::RegisterMaskPair &LI : MBB->liveins())
506 NMBB->addLiveIn(LI.PhysReg);
507
508 TII->insertUnconditionalBranch(*NMBB, MBB, DebugLoc());
509
510 // After splitting, all predecessors of the restore point should be dirty
511 // blocks.
512 for (MachineBasicBlock *SuccBB : DirtyPreds)
513 SuccBB->ReplaceUsesOfBlockWith(MBB, NMBB);
514
515 NMBB->addSuccessor(MBB);
516
517 for (MachineBasicBlock *BBToUpdate : MBBFallthrough)
518 updateTerminator(BBToUpdate, NMBB, TII);
519
520 return NMBB;
521}
522
523/// This function undoes the restore point split done earlier.
524///
525/// DirtyPreds: All predecessors of \p NMBB that are ReachableByDirty.
526///
527/// Restore point was split and the change needs to be unrolled. Make necessary
528/// changes to reset restore point from \p NMBB to \p MBB.
532 const TargetInstrInfo *TII) {
533 // For a BB, if NMBB is fallthrough in the current layout, then in the new
534 // layout a. BB should fallthrough to MBB OR b. BB should undconditionally
535 // branch to MBB
537 for (MachineBasicBlock *BB : DirtyPreds)
538 if (BB->getFallThrough(false) == NMBB)
539 NMBBFallthrough.insert(BB);
540
541 NMBB->removeSuccessor(MBB);
542 for (MachineBasicBlock *SuccBB : DirtyPreds)
543 SuccBB->ReplaceUsesOfBlockWith(NMBB, MBB);
544
545 NMBB->erase(NMBB->begin(), NMBB->end());
546 NMBB->eraseFromParent();
547
548 for (MachineBasicBlock *BBToUpdate : NMBBFallthrough)
549 updateTerminator(BBToUpdate, MBB, TII);
550}
551
552// A block is deemed fit for restore point split iff there exist
553// 1. DirtyPreds - preds of CurRestore reachable from use or def of CSR/FI
554// 2. CleanPreds - preds of CurRestore that arent DirtyPreds
555bool ShrinkWrapImpl::checkIfRestoreSplittable(
556 const MachineBasicBlock *CurRestore,
557 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
560 const TargetInstrInfo *TII, RegScavenger *RS) {
561 for (const MachineInstr &MI : *CurRestore)
562 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true))
563 return false;
564
565 for (MachineBasicBlock *PredBB : CurRestore->predecessors()) {
566 if (!isAnalyzableBB(*TII, *PredBB))
567 return false;
568
569 if (ReachableByDirty.count(PredBB))
570 DirtyPreds.push_back(PredBB);
571 else
572 CleanPreds.push_back(PredBB);
573 }
574
575 return !(CleanPreds.empty() || DirtyPreds.empty());
576}
577
578bool ShrinkWrapImpl::postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
579 RegScavenger *RS) {
580 if (!getCodeGenOptions(MF).shrink_wrap_region_split)
581 return false;
582
583 MachineBasicBlock *InitSave = nullptr;
584 MachineBasicBlock *InitRestore = nullptr;
585
586 if (HasCandidate) {
587 InitSave = Save;
588 InitRestore = Restore;
589 } else {
590 InitRestore = nullptr;
591 InitSave = &MF.front();
592 for (MachineBasicBlock &MBB : MF) {
593 if (MBB.isEHFuncletEntry())
594 return false;
595 if (MBB.isReturnBlock()) {
596 // Do not support multiple restore points.
597 if (InitRestore)
598 return false;
599 InitRestore = &MBB;
600 }
601 }
602 }
603
604 if (!InitSave || !InitRestore || InitRestore == InitSave ||
605 !MDT->dominates(InitSave, InitRestore) ||
606 !MPDT->dominates(InitRestore, InitSave))
607 return false;
608
609 // Bail out of the optimization if any of the basic block is target of
610 // INLINEASM_BR instruction
611 for (MachineBasicBlock &MBB : MF)
613 return false;
614
615 DenseSet<const MachineBasicBlock *> DirtyBBs;
616 for (MachineBasicBlock &MBB : MF) {
617 if (!MDT->isReachableFromEntry(&MBB))
618 continue;
619 if (MBB.isEHPad()) {
620 DirtyBBs.insert(&MBB);
621 continue;
622 }
623 for (const MachineInstr &MI : MBB)
624 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true)) {
625 DirtyBBs.insert(&MBB);
626 break;
627 }
628 }
629
630 // Find blocks reachable from the use or def of CSRs/FI.
631 DenseSet<const MachineBasicBlock *> ReachableByDirty;
632 collectBlocksReachableByDirty(DirtyBBs, ReachableByDirty);
633
634 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
637 if (!checkIfRestoreSplittable(InitRestore, ReachableByDirty, DirtyPreds,
638 CleanPreds, TII, RS))
639 return false;
640
641 // Trying to reach out to the new save point which dominates all dirty blocks.
642 MachineBasicBlock *NewSave =
643 FindIDom<>(**DirtyPreds.begin(), DirtyPreds, *MDT, false);
644
645 while (NewSave && (hasDirtyPred(ReachableByDirty, *NewSave) ||
646 EntryFreq < MBFI->getBlockFreq(NewSave) ||
647 /*Entry freq has been observed more than a loop block in
648 some cases*/
649 MLI->getLoopFor(NewSave))) {
650 SmallVector<MachineBasicBlock*> ReachablePreds;
651 for (auto BB: NewSave->predecessors())
652 if (MDT->isReachableFromEntry(BB))
653 ReachablePreds.push_back(BB);
654 if (ReachablePreds.empty())
655 break;
656
657 NewSave = FindIDom<>(**ReachablePreds.begin(), ReachablePreds, *MDT,
658 false);
659 }
660
661 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
662 if (!NewSave || NewSave == InitSave ||
663 isSaveReachableThroughClean(NewSave, CleanPreds) ||
664 !TFI->canUseAsPrologue(*NewSave))
665 return false;
666
667 // Now we know that splitting a restore point can isolate the restore point
668 // from clean blocks and doing so can shrink the save point.
669 MachineBasicBlock *NewRestore =
670 tryToSplitRestore(InitRestore, DirtyPreds, TII);
671
672 // Make sure if the new restore point is valid as an epilogue, depending on
673 // targets.
674 if (!TFI->canUseAsEpilogue(*NewRestore)) {
675 rollbackRestoreSplit(MF, NewRestore, InitRestore, DirtyPreds, TII);
676 return false;
677 }
678
679 Save = NewSave;
680 Restore = NewRestore;
681
682 MDT->recalculate(MF);
683 MPDT->recalculate(MF);
684
685 assert((MDT->dominates(Save, Restore) && MPDT->dominates(Restore, Save)) &&
686 "Incorrect save or restore point due to dominance relations");
687 assert((!MLI->getLoopFor(Save) && !MLI->getLoopFor(Restore)) &&
688 "Unexpected save or restore point in a loop");
689 assert((EntryFreq >= MBFI->getBlockFreq(Save) &&
690 EntryFreq >= MBFI->getBlockFreq(Restore)) &&
691 "Incorrect save or restore point based on block frequency");
692 return true;
693}
694
695void ShrinkWrapImpl::updateSaveRestorePoints(MachineBasicBlock &MBB,
696 RegScavenger *RS) {
697 // Get rid of the easy cases first.
698 if (!Save)
699 Save = &MBB;
700 else
701 Save = MDT->findNearestCommonDominator(Save, &MBB);
702 assert(Save);
703
704 if (!Restore)
705 Restore = &MBB;
706 else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it
707 // means the block never returns. If that's the
708 // case, we don't want to call
709 // `findNearestCommonDominator`, which will
710 // return `Restore`.
711 Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
712 else
713 Restore = nullptr; // Abort, we can't find a restore point in this case.
714
715 // Make sure we would be able to insert the restore code before the
716 // terminator.
717 if (Restore == &MBB) {
718 for (const MachineInstr &Terminator : MBB.terminators()) {
719 if (!useOrDefCSROrFI(Terminator, RS, /*StackAddressUsed=*/true))
720 continue;
721 // One of the terminator needs to happen before the restore point.
722 if (MBB.succ_empty()) {
723 Restore = nullptr; // Abort, we can't find a restore point in this case.
724 break;
725 }
726 // Look for a restore point that post-dominates all the successors.
727 // The immediate post-dominator is what we are looking for.
728 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
729 break;
730 }
731 }
732
733 if (!Restore) {
735 dbgs() << "Restore point needs to be spanned on several blocks\n");
736 return;
737 }
738
739 // Make sure Save and Restore are suitable for shrink-wrapping:
740 // 1. all path from Save needs to lead to Restore before exiting.
741 // 2. all path to Restore needs to go through Save from Entry.
742 // We achieve that by making sure that:
743 // A. Save dominates Restore.
744 // B. Restore post-dominates Save.
745 // C. Save and Restore are in the same loop.
746 bool SaveDominatesRestore = false;
747 bool RestorePostDominatesSave = false;
748 while (Restore &&
749 (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||
750 !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||
751 // Post-dominance is not enough in loops to ensure that all uses/defs
752 // are after the prologue and before the epilogue at runtime.
753 // E.g.,
754 // while(1) {
755 // Save
756 // Restore
757 // if (...)
758 // break;
759 // use/def CSRs
760 // }
761 // All the uses/defs of CSRs are dominated by Save and post-dominated
762 // by Restore. However, the CSRs uses are still reachable after
763 // Restore and before Save are executed.
764 //
765 // For now, just push the restore/save points outside of loops.
766 // FIXME: Refine the criteria to still find interesting cases
767 // for loops.
768 MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
769 // Fix (A).
770 if (!SaveDominatesRestore) {
771 Save = MDT->findNearestCommonDominator(Save, Restore);
772 continue;
773 }
774 // Fix (B).
775 if (!RestorePostDominatesSave)
776 Restore = MPDT->findNearestCommonDominator(Restore, Save);
777
778 // Fix (C).
779 if (Restore && (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
780 if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) {
781 // Push Save outside of this loop if immediate dominator is different
782 // from save block. If immediate dominator is not different, bail out.
784 for (auto *PBB : Save->predecessors())
785 if (MDT->isReachableFromEntry(PBB))
786 Preds.push_back(PBB);
787 Save = FindIDom<>(*Save, Preds, *MDT);
788 if (!Save)
789 break;
790 } else {
791 // If the loop does not exit, there is no point in looking
792 // for a post-dominator outside the loop.
793 SmallVector<MachineBasicBlock*, 4> ExitBlocks;
794 MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks);
795 // Push Restore outside of this loop.
796 // Look for the immediate post-dominator of the loop exits.
797 MachineBasicBlock *IPdom = Restore;
798 for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
799 IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);
800 if (!IPdom)
801 break;
802 }
803 // If the immediate post-dominator is not in a less nested loop,
804 // then we are stuck in a program with an infinite loop.
805 // In that case, we will not find a safe point, hence, bail out.
806 if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore))
807 Restore = IPdom;
808 else {
809 Restore = nullptr;
810 break;
811 }
812 }
813 }
814 }
815}
816
818 StringRef RemarkName, StringRef RemarkMessage,
819 const DiagnosticLocation &Loc,
820 const MachineBasicBlock *MBB) {
821 ORE->emit([&]() {
823 << RemarkMessage;
824 });
825
826 LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
827 return false;
828}
829
830bool ShrinkWrapImpl::performShrinkWrapping(
831 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
832 RegScavenger *RS) {
833 for (MachineBasicBlock *MBB : RPOT) {
834 LLVM_DEBUG(dbgs() << "Look into: " << printMBBReference(*MBB) << '\n');
835
836 if (MBB->isEHFuncletEntry())
837 return giveUpWithRemarks(ORE, "UnsupportedEHFunclets",
838 "EH Funclets are not supported yet.",
839 MBB->front().getDebugLoc(), MBB);
840
842 // Push the prologue and epilogue outside of the region that may throw (or
843 // jump out via inlineasm_br), by making sure that all the landing pads
844 // are at least at the boundary of the save and restore points. The
845 // problem is that a basic block can jump out from the middle in these
846 // cases, which we do not handle.
847 updateSaveRestorePoints(*MBB, RS);
848 if (!ArePointsInteresting()) {
849 LLVM_DEBUG(dbgs() << "EHPad/inlineasm_br prevents shrink-wrapping\n");
850 return false;
851 }
852 continue;
853 }
854
855 bool StackAddressUsed = false;
856 // Check if we found any stack accesses in the predecessors. We are not
857 // doing a full dataflow analysis here to keep things simple but just
858 // rely on a reverse portorder traversal (RPOT) to guarantee predecessors
859 // are already processed except for loops (and accept the conservative
860 // result for loops).
861 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
862 if (StackAddressUsedBlockInfo.test(Pred->getNumber())) {
863 StackAddressUsed = true;
864 break;
865 }
866 }
867
868 for (const MachineInstr &MI : *MBB) {
869 if (useOrDefCSROrFI(MI, RS, StackAddressUsed)) {
870 // Save (resp. restore) point must dominate (resp. post dominate)
871 // MI. Look for the proper basic block for those.
872 updateSaveRestorePoints(*MBB, RS);
873 // If we are at a point where we cannot improve the placement of
874 // save/restore instructions, just give up.
875 if (!ArePointsInteresting()) {
876 LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
877 return false;
878 }
879 // No need to look for other instructions, this basic block
880 // will already be part of the handled region.
881 StackAddressUsed = true;
882 break;
883 }
884 }
885 StackAddressUsedBlockInfo[MBB->getNumber()] = StackAddressUsed;
886 }
887 if (!ArePointsInteresting()) {
888 // If the points are not interesting at this point, then they must be null
889 // because it means we did not encounter any frame/CSR related code.
890 // Otherwise, we would have returned from the previous loop.
891 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
892 LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
893 return false;
894 }
895
896 LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: "
897 << EntryFreq.getFrequency() << '\n');
898
899 const TargetFrameLowering *TFI =
900 MachineFunc->getSubtarget().getFrameLowering();
901 do {
902 LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
903 << printMBBReference(*Save) << ' '
904 << printBlockFreq(*MBFI, *Save)
905 << "\nRestore: " << printMBBReference(*Restore) << ' '
906 << printBlockFreq(*MBFI, *Restore) << '\n');
907
908 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
909 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save)) &&
910 EntryFreq >= MBFI->getBlockFreq(Restore)) &&
911 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
912 TFI->canUseAsEpilogue(*Restore)))
913 break;
915 dbgs() << "New points are too expensive or invalid for the target\n");
916 MachineBasicBlock *NewBB;
917 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
918 Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
919 if (!Save)
920 break;
921 NewBB = Save;
922 } else {
923 // Restore is expensive.
924 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
925 if (!Restore)
926 break;
927 NewBB = Restore;
928 }
929 updateSaveRestorePoints(*NewBB, RS);
930 } while (Save && Restore);
931
932 if (!ArePointsInteresting()) {
933 ++NumCandidatesDropped;
934 return false;
935 }
936 return true;
937}
938
939bool ShrinkWrapImpl::run(MachineFunction &MF) {
940 LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
941
942 init(MF);
943
944 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
946 // If MF is irreducible, a block may be in a loop without
947 // MachineLoopInfo reporting it. I.e., we may use the
948 // post-dominance property in loops, which lead to incorrect
949 // results. Moreover, we may miss that the prologue and
950 // epilogue are not in the same loop, leading to unbalanced
951 // construction/deconstruction of the stack frame.
952 return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG",
953 "Irreducible CFGs are not supported yet.",
954 MF.getFunction().getSubprogram(), &MF.front());
955 }
956
957 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
958 std::unique_ptr<RegScavenger> RS(
959 TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
960
961 bool Changed = false;
962
963 // Initially, conservatively assume that stack addresses can be used in each
964 // basic block and change the state only for those basic blocks for which we
965 // were able to prove the opposite.
966 StackAddressUsedBlockInfo.resize(MF.getNumBlockIDs(), true);
967 bool HasCandidate = performShrinkWrapping(RPOT, RS.get());
968 StackAddressUsedBlockInfo.clear();
969 Changed = postShrinkWrapping(HasCandidate, MF, RS.get());
970 if (!HasCandidate && !Changed)
971 return false;
972 if (!ArePointsInteresting())
973 return Changed;
974
975 LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
976 << printMBBReference(*Save) << ' '
977 << "\nRestore: " << printMBBReference(*Restore) << '\n');
978
979 MachineFrameInfo &MFI = MF.getFrameInfo();
980
981 // List of CalleeSavedInfo for registers will be added during prologepilog
982 // pass
983 SaveRestorePoints SavePoints({{Save, {}}});
984 SaveRestorePoints RestorePoints({{Restore, {}}});
985
986 MFI.setSavePoints(SavePoints);
987 MFI.setRestorePoints(RestorePoints);
988 ++NumCandidates;
989 return Changed;
990}
991
992bool ShrinkWrapLegacy::runOnMachineFunction(MachineFunction &MF) {
993 if (skipFunction(MF.getFunction()) || MF.empty() ||
994 !ShrinkWrapImpl::isShrinkWrapEnabled(MF))
995 return false;
996
997 const RegisterClassInfo *RCI =
998 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
999 MachineDominatorTree *MDT =
1000 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1001 MachinePostDominatorTree *MPDT =
1002 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
1003 MachineBlockFrequencyInfo *MBFI =
1004 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
1005 MachineLoopInfo *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1006 MachineOptimizationRemarkEmitter *ORE =
1007 &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
1008
1009 return ShrinkWrapImpl(RCI, MDT, MPDT, MBFI, MLI, ORE).run(MF);
1010}
1011
1014 MFPropsModifier _(*this, MF);
1015 if (MF.empty() || !ShrinkWrapImpl::isShrinkWrapEnabled(MF))
1016 return PreservedAnalyses::all();
1017
1018 const RegisterClassInfo &RCI =
1028
1029 ShrinkWrapImpl(&RCI, &MDT, &MPDT, &MBFI, &MLI, &ORE).run(MF);
1030 return PreservedAnalyses::all();
1031}
1032
1033bool ShrinkWrapImpl::isShrinkWrapEnabled(const MachineFunction &MF) {
1035
1036 switch (getCodeGenOptions(MF).shrink_wrap) {
1038 return TFI->enableShrinkWrapping(MF) &&
1039 // Windows with CFI has some limitations that make it impossible
1040 // to use shrink-wrapping.
1041 !MF.usesWindowsUnwindInfo() &&
1042 // Sanitizers look at the value of the stack at the location
1043 // of the crash. Since a crash can happen anywhere, the
1044 // frame must be lowered before anything else happen for the
1045 // sanitizers to be able to get a correct stack frame.
1046 !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) ||
1047 MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) ||
1048 MF.getFunction().hasFnAttribute(Attribute::SanitizeConcurrency) ||
1049 MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) ||
1050 MF.getFunction().hasFnAttribute(Attribute::SanitizeType) ||
1051 MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress));
1052 // If EnableShrinkWrap is set, it takes precedence on whatever the
1053 // target sets. The rational is that we assume we want to test
1054 // something related to shrink-wrapping.
1056 return true;
1058 return false;
1059 }
1060 llvm_unreachable("Invalid shrink-wrapping state");
1061}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
const AArch64Subtarget & Subtarget
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
aarch64 promote const
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
This file implements the BitVector class.
#define DEBUG_TYPE
const HexagonInstrInfo * TII
#define _
IRTranslator LLVM IR MI
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
Register Reg
Register const TargetRegisterInfo * TRI
if(PassOpts->AAPipeline)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
SmallVector< MachineOperand, 4 > Cond
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
This file declares the machine register scavenger class.
This file implements a set that has insertion order iteration characteristics.
static void markAllReachable(DenseSet< const MachineBasicBlock * > &Visited, const MachineBasicBlock &MBB)
Derives the list of all the basic blocks reachable from MBB.
static void updateTerminator(MachineBasicBlock *BBToUpdate, MachineBasicBlock *NMBB, const TargetInstrInfo *TII)
This function updates the branches post restore point split.
static MachineBasicBlock * tryToSplitRestore(MachineBasicBlock *MBB, ArrayRef< MachineBasicBlock * > DirtyPreds, const TargetInstrInfo *TII)
This function splits the restore point and returns new restore point/BB.
static bool hasDirtyPred(const DenseSet< const MachineBasicBlock * > &ReachableByDirty, const MachineBasicBlock &MBB)
Determines if any predecessor of MBB is on the path from block that has use or def of CSRs/FI to MBB.
static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE, StringRef RemarkName, StringRef RemarkMessage, const DiagnosticLocation &Loc, const MachineBasicBlock *MBB)
static void rollbackRestoreSplit(MachineFunction &MF, MachineBasicBlock *NMBB, MachineBasicBlock *MBB, ArrayRef< MachineBasicBlock * > DirtyPreds, const TargetInstrInfo *TII)
This function undoes the restore point split done earlier.
static bool isAnalyzableBB(const TargetInstrInfo &TII, MachineBasicBlock &Entry)
static bool isSaveReachableThroughClean(const MachineBasicBlock *SavePoint, ArrayRef< MachineBasicBlock * > CleanPreds)
static void collectBlocksReachableByDirty(const DenseSet< const MachineBasicBlock * > &DirtyBBs, DenseSet< const MachineBasicBlock * > &ReachableByDirty)
Collect blocks reachable by use or def of CSRs/FI.
static MachineBasicBlock * FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, DominanceAnalysis &Dom, bool Strict=true)
Helper function to find the immediate (post) dominator.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
This file describes how to lower LLVM code to machine code.
const AArch64InstrInfo * getInstrInfo() const override
const AArch64TargetLowering * getTargetLowering() const override
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
bool test(unsigned Idx) const
Returns true if bit Idx is set.
Definition BitVector.h:483
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
Definition BitVector.h:318
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
Definition BitVector.h:356
void clear()
Removes all bits from the bitvector.
Definition BitVector.h:350
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
Definition BitVector.h:325
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
A debug info location.
Definition DebugLoc.h:126
Implements a dense probed hash-table based set.
Definition DenseSet.h:283
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
DISubprogram * getSubprogram() const
Get the attached subprogram.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition Function.cpp:731
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
An RAII based helper class to modify MachineFunctionProperties when running pass.
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction.
LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
LLVM_ABI bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
LLVM_ABI void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< iterator > terminators()
LLVM_ABI DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
LLVM_ABI BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineInstr *A, const MachineInstr *B) const
void setSavePoints(SaveRestorePoints NewSavePoints)
void setRestorePoints(SaveRestorePoints NewRestorePoints)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Function & getFunction()
Return the LLVM function that this machine code represents.
bool usesWindowsUnwindInfo() const
True if this function describes its unwind information with Windows SEH unwind opcodes (....
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const MachineBasicBlock & front() const
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineInstr - Allocate a new MachineInstr.
void insert(iterator MBBI, MachineBasicBlock *MBB)
Representation of each machine instruction.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Analysis pass that exposes the MachineLoopInfo for a machine function.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Emit an optimization remark.
Diagnostic information for missed-optimization remarks.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
LLVM_ABI MachineBasicBlock * findNearestCommonDominator(ArrayRef< MachineBasicBlock * > Blocks) const
Returns the nearest common dominator of the given blocks.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Special value supplied for machine level alias analysis.
Wrapper class representing virtual and physical registers.
Definition Register.h:20
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:346
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Information about stack frame layout on the target.
virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const
This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...
virtual bool enableShrinkWrapping(const MachineFunction &MF) const
Returns true if the target will correctly handle shrink wrapping.
virtual bool canUseAsEpilogue(const MachineBasicBlock &MBB) const
Check whether or not the given MBB can be used as a epilogue for the target.
virtual bool canUseAsPrologue(const MachineBasicBlock &MBB) const
Check whether or not the given MBB can be used as a prologue for the target.
TargetInstrInfo - Interface to description of machine instruction set.
Register getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetFrameLowering * getFrameLowering() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
LLVM Value Representation.
Definition Value.h:75
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition DenseSet.h:188
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI char & ShrinkWrapID
ShrinkWrap pass. Look for the best place to insert save and restore.
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition CFG.h:154
DenseMap< MachineBasicBlock *, std::vector< CalleeSavedInfo > > SaveRestorePoints
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
DWARFExpression::Operation Op
LLVM_ABI Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)
Print the block frequency Freq relative to the current functions entry frequency.
LLVM_ABI void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, const LoopInfo *LI=nullptr, unsigned MaxLookup=MaxLookupSearchDepth)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
Pair of physical register and lane mask.