91#define DEBUG_TYPE "shrink-wrap"
94STATISTIC(NumCandidates,
"Number of shrink-wrapping candidates");
96 "Number of shrink-wrapping candidates dropped because of frequency");
100 cl::desc(
"enable the shrink-wrapping pass"));
103 cl::desc(
"enable splitting of the restore block if possible"));
145 unsigned FrameSetupOpcode = ~0u;
148 unsigned FrameDestroyOpcode = ~0u;
159 mutable SetOfRegs CurrentCSRs;
173 bool StackAddressUsed)
const;
175 const SetOfRegs &getCurrentCSRs(
RegScavenger *RS)
const {
176 if (CurrentCSRs.empty()) {
183 for (
int Reg = SavedRegs.
find_first(); Reg != -1;
185 CurrentCSRs.insert((
unsigned)Reg);
199 bool performShrinkWrapping(
216 bool checkIfRestoreSplittable(
226 MDT = &getAnalysis<MachineDominatorTree>();
227 MPDT = &getAnalysis<MachinePostDominatorTree>();
230 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
231 MLI = &getAnalysis<MachineLoopInfo>();
232 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
236 FrameSetupOpcode =
TII.getCallFrameSetupOpcode();
237 FrameDestroyOpcode =
TII.getCallFrameDestroyOpcode();
248 bool ArePointsInteresting()
const {
return Save != Entry && Save && Restore; }
272 MachineFunctionProperties::Property::NoVRegs);
284char ShrinkWrap::ID = 0;
297 bool StackAddressUsed)
const {
305 if (
Op->getValue()) {
309 if (
auto *Arg = dyn_cast<Argument>(UO))
310 return !Arg->hasPassPointeeByValueCopyAttr();
311 return isa<GlobalValue>(UO);
314 return PSV->isJumpTable();
319 if (StackAddressUsed &&
MI.mayLoadOrStore() &&
320 (
MI.isCall() ||
MI.hasUnmodeledSideEffects() ||
MI.memoperands_empty() ||
321 !
all_of(
MI.memoperands(), IsKnownNonStackPtr)))
324 if (
MI.getOpcode() == FrameSetupOpcode ||
325 MI.getOpcode() == FrameDestroyOpcode) {
332 bool UseOrDefCSR =
false;
335 if (!MO.isDef() && !MO.readsReg())
351 (!
MI.isCall() && PhysReg == SP) ||
353 (!
MI.isReturn() &&
TRI->isNonallocatableRegisterCalleeSave(PhysReg));
354 }
else if (MO.isRegMask()) {
356 for (
unsigned Reg : getCurrentCSRs(RS)) {
357 if (MO.clobbersPhysReg(Reg)) {
364 if (UseOrDefCSR || (MO.isFI() && !
MI.isDebugValue())) {
365 LLVM_DEBUG(
dbgs() <<
"Use or define CSR(" << UseOrDefCSR <<
") or FI("
366 << MO.isFI() <<
"): " <<
MI <<
'\n');
374template <
typename ListOfBBs,
typename DominanceAnalysis>
376 DominanceAnalysis &Dom,
bool Strict =
true) {
379 IDom = Dom.findNearestCommonDominator(IDom, BB);
383 if (Strict && IDom == &
Block)
404 if (ReachableByDirty.
count(PredBB))
415 while (!Worklist.
empty()) {
417 if (!Visited.
insert(SuccMBB).second)
443 while (!Worklist.
empty()) {
445 if (CleanBB == SavePoint)
471 TII->insertUnconditionalBranch(*BBToUpdate, NMBB,
DL);
496 if (BB->getFallThrough(
false) ==
MBB)
497 MBBFallthrough.
insert(BB);
512 SuccBB->ReplaceUsesOfBlockWith(
MBB, NMBB);
537 if (BB->getFallThrough(
false) == NMBB)
538 NMBBFallthrough.
insert(BB);
542 SuccBB->ReplaceUsesOfBlockWith(NMBB,
MBB);
554bool ShrinkWrap::checkIfRestoreSplittable(
561 if (useOrDefCSROrFI(
MI, RS,
true))
568 if (ReachableByDirty.
count(PredBB))
574 return !(CleanPreds.
empty() || DirtyPreds.
empty());
577bool ShrinkWrap::postShrinkWrapping(
bool HasCandidate,
MachineFunction &MF,
587 InitRestore = Restore;
589 InitRestore =
nullptr;
590 InitSave = &MF.
front();
603 if (!InitSave || !InitRestore || InitRestore == InitSave ||
604 !MDT->
dominates(InitSave, InitRestore) ||
621 if (useOrDefCSROrFI(
MI, RS,
true)) {
634 if (!checkIfRestoreSplittable(InitRestore, ReachableByDirty, DirtyPreds,
635 CleanPreds,
TII, RS))
640 FindIDom<>(**DirtyPreds.
begin(), DirtyPreds, *MDT,
false);
642 while (NewSave && (
hasDirtyPred(ReachableByDirty, *NewSave) ||
643 EntryFreq < MBFI->getBlockFreq(NewSave).getFrequency() ||
651 if (!NewSave || NewSave == InitSave ||
669 Restore = NewRestore;
675 "Incorrect save or restore point due to dominance relations");
677 "Unexpected save or restore point in a loop");
680 "Incorrect save or restore point based on block frequency");
706 if (Restore == &
MBB) {
708 if (!useOrDefCSROrFI(Terminator, RS,
true))
717 Restore = FindIDom<>(*Restore, Restore->
successors(), *MPDT);
724 dbgs() <<
"Restore point needs to be spanned on several blocks\n");
735 bool SaveDominatesRestore =
false;
736 bool RestorePostDominatesSave =
false;
738 (!(SaveDominatesRestore = MDT->
dominates(Save, Restore)) ||
739 !(RestorePostDominatesSave = MPDT->
dominates(Restore, Save)) ||
759 if (!SaveDominatesRestore) {
764 if (!RestorePostDominatesSave)
784 IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);
815bool ShrinkWrap::performShrinkWrapping(
823 "EH Funclets are not supported yet.",
832 updateSaveRestorePoints(*
MBB, RS);
833 if (!ArePointsInteresting()) {
834 LLVM_DEBUG(
dbgs() <<
"EHPad/inlineasm_br prevents shrink-wrapping\n");
840 bool StackAddressUsed =
false;
847 if (StackAddressUsedBlockInfo.
test(Pred->getNumber())) {
848 StackAddressUsed =
true;
854 if (useOrDefCSROrFI(
MI, RS, StackAddressUsed)) {
857 updateSaveRestorePoints(*
MBB, RS);
860 if (!ArePointsInteresting()) {
866 StackAddressUsed =
true;
870 StackAddressUsedBlockInfo[
MBB->
getNumber()] = StackAddressUsed;
872 if (!ArePointsInteresting()) {
876 assert(!Save && !Restore &&
"We miss a shrink-wrap opportunity?!");
881 LLVM_DEBUG(
dbgs() <<
"\n ** Results **\nFrequency of the Entry: " << EntryFreq
887 LLVM_DEBUG(
dbgs() <<
"Shrink wrap candidates (#, Name, Freq):\nSave: "
893 bool IsSaveCheap, TargetCanUseSaveAsPrologue =
false;
900 dbgs() <<
"New points are too expensive or invalid for the target\n");
902 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
909 Restore = FindIDom<>(*Restore, Restore->
successors(), *MPDT);
914 updateSaveRestorePoints(*NewBB, RS);
915 }
while (Save && Restore);
917 if (!ArePointsInteresting()) {
918 ++NumCandidatesDropped;
925 if (skipFunction(MF.
getFunction()) || MF.
empty() || !isShrinkWrapEnabled(MF))
933 if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {
941 "Irreducible CFGs are not supported yet.",
946 std::unique_ptr<RegScavenger> RS(
949 bool Changed =
false;
952 bool HasCandidate = performShrinkWrapping(RPOT, RS.get());
953 StackAddressUsedBlockInfo.
clear();
954 Changed = postShrinkWrapping(HasCandidate, MF, RS.get());
955 if (!HasCandidate && !Changed)
957 if (!ArePointsInteresting())
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.
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
This file declares the machine register scavenger class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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 cl::opt< bool > EnablePostShrinkWrapOpt("enable-shrink-wrap-region-split", cl::init(true), cl::Hidden, cl::desc("enable splitting of the restore block if possible"))
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 cl::opt< cl::boolOrDefault > EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, cl::desc("enable the shrink-wrapping pass"))
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)
This file describes how to lower LLVM code to machine code.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool test(unsigned Idx) const
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
This class represents an Operation in the Expression.
Implements a dense probed hash-table based set.
DISubprogram * getSubprogram() const
Get the attached subprogram.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
bool usesWindowsCFI() const
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
succ_iterator succ_begin()
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.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
pred_iterator pred_begin()
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
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.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< iterator > terminators()
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...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
uint64_t getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
void setRestorePoint(MachineBasicBlock *NewRestore)
void setSavePoint(MachineBasicBlock *NewSave)
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.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
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.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const MachineBasicBlock & front() const
void insert(iterator MBBI, MachineBasicBlock *MBB)
Representation of each machine instruction.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B) const
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Special value supplied for machine level alias analysis.
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Wrapper class representing virtual and physical registers.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
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.
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)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
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...
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetFrameLowering * getFrameLowering() const
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetLowering * getTargetLowering() const
LLVM Value Representation.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
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.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
char & ShrinkWrapID
ShrinkWrap pass. Look for the best place to insert save and restore.
void initializeShrinkWrapPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
DWARFExpression::Operation Op
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Pair of physical register and lane mask.