summaryrefslogtreecommitdiff
path: root/lib/CodeGen/ShrinkWrap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/ShrinkWrap.cpp')
-rw-r--r--lib/CodeGen/ShrinkWrap.cpp171
1 files changed, 98 insertions, 73 deletions
diff --git a/lib/CodeGen/ShrinkWrap.cpp b/lib/CodeGen/ShrinkWrap.cpp
index b35bf6ba3a7b..d3454ca6ba6a 100644
--- a/lib/CodeGen/ShrinkWrap.cpp
+++ b/lib/CodeGen/ShrinkWrap.cpp
@@ -53,6 +53,7 @@
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFG.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
@@ -62,11 +63,13 @@
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/Attributes.h"
@@ -97,7 +100,7 @@ EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
namespace {
-/// \brief Class to determine where the safe point to insert the
+/// Class to determine where the safe point to insert the
/// prologue and epilogue are.
/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
/// shrink-wrapping term for prologue/epilogue placement, this pass
@@ -128,6 +131,9 @@ class ShrinkWrap : public MachineFunctionPass {
/// are in the same loop.
MachineLoopInfo *MLI;
+ // Emit remarks.
+ MachineOptimizationRemarkEmitter *ORE = nullptr;
+
/// Frequency of the Entry block.
uint64_t EntryFreq;
@@ -137,6 +143,9 @@ class ShrinkWrap : public MachineFunctionPass {
/// Current opcode for frame destroy.
unsigned FrameDestroyOpcode;
+ /// Stack pointer register, used by llvm.{savestack,restorestack}
+ unsigned SP;
+
/// Entry block.
const MachineBasicBlock *Entry;
@@ -148,7 +157,7 @@ class ShrinkWrap : public MachineFunctionPass {
/// Current MachineFunction.
MachineFunction *MachineFunc;
- /// \brief Check if \p MI uses or defines a callee-saved register or
+ /// Check if \p MI uses or defines a callee-saved register or
/// a frame index. If this is the case, this means \p MI must happen
/// after Save and before Restore.
bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const;
@@ -168,14 +177,14 @@ class ShrinkWrap : public MachineFunctionPass {
return CurrentCSRs;
}
- /// \brief Update the Save and Restore points such that \p MBB is in
+ /// Update the Save and Restore points such that \p MBB is in
/// the region that is dominated by Save and post-dominated by Restore
/// and Save and Restore still match the safe point definition.
/// Such point may not exist and Save and/or Restore may be null after
/// this call.
void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
- /// \brief Initialize the pass for \p MF.
+ /// Initialize the pass for \p MF.
void init(MachineFunction &MF) {
RCI.runOnMachineFunction(MF);
MDT = &getAnalysis<MachineDominatorTree>();
@@ -184,10 +193,13 @@ class ShrinkWrap : public MachineFunctionPass {
Restore = nullptr;
MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
MLI = &getAnalysis<MachineLoopInfo>();
+ ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
EntryFreq = MBFI->getEntryFreq();
- const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
+ const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
+ const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
FrameSetupOpcode = TII.getCallFrameSetupOpcode();
FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
+ SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore();
Entry = &MF.front();
CurrentCSRs.clear();
MachineFunc = &MF;
@@ -199,7 +211,7 @@ class ShrinkWrap : public MachineFunctionPass {
/// shrink-wrapping.
bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
- /// \brief Check if shrink wrapping is enabled for this target and function.
+ /// Check if shrink wrapping is enabled for this target and function.
static bool isShrinkWrapEnabled(const MachineFunction &MF);
public:
@@ -215,12 +227,18 @@ public:
AU.addRequired<MachineDominatorTree>();
AU.addRequired<MachinePostDominatorTree>();
AU.addRequired<MachineLoopInfo>();
+ AU.addRequired<MachineOptimizationRemarkEmitterPass>();
MachineFunctionPass::getAnalysisUsage(AU);
}
+ MachineFunctionProperties getRequiredProperties() const override {
+ return MachineFunctionProperties().set(
+ MachineFunctionProperties::Property::NoVRegs);
+ }
+
StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
- /// \brief Perform the shrink-wrapping analysis and update
+ /// Perform the shrink-wrapping analysis and update
/// the MachineFrameInfo attached to \p MF with the results.
bool runOnMachineFunction(MachineFunction &MF) override;
};
@@ -236,28 +254,34 @@ INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI,
RegScavenger *RS) const {
- // Ignore DBG_VALUE and other meta instructions that must not affect codegen.
- if (MI.isMetaInstruction())
- return false;
-
if (MI.getOpcode() == FrameSetupOpcode ||
MI.getOpcode() == FrameDestroyOpcode) {
- DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
+ LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
return true;
}
for (const MachineOperand &MO : MI.operands()) {
bool UseOrDefCSR = false;
if (MO.isReg()) {
+ // Ignore instructions like DBG_VALUE which don't read/def the register.
+ if (!MO.isDef() && !MO.readsReg())
+ continue;
unsigned PhysReg = MO.getReg();
if (!PhysReg)
continue;
assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
"Unallocated register?!");
- UseOrDefCSR = RCI.getLastCalleeSavedAlias(PhysReg);
+ // The stack pointer is not normally described as a callee-saved register
+ // in calling convention definitions, so we need to watch for it
+ // separately. An SP mentioned by a call instruction, we can ignore,
+ // though, as it's harmless and we do not want to effectively disable tail
+ // calls by forcing the restore point to post-dominate them.
+ UseOrDefCSR = (!MI.isCall() && PhysReg == SP) ||
+ RCI.getLastCalleeSavedAlias(PhysReg);
} else if (MO.isRegMask()) {
// Check if this regmask clobbers any of the CSRs.
for (unsigned Reg : getCurrentCSRs(RS)) {
@@ -267,16 +291,17 @@ bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI,
}
}
}
- if (UseOrDefCSR || MO.isFI()) {
- DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
- << MO.isFI() << "): " << MI << '\n');
+ // Skip FrameIndex operands in DBG_VALUE instructions.
+ if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
+ LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
+ << MO.isFI() << "): " << MI << '\n');
return true;
}
}
return false;
}
-/// \brief Helper function to find the immediate (post) dominator.
+/// Helper function to find the immediate (post) dominator.
template <typename ListOfBBs, typename DominanceAnalysis>
static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
DominanceAnalysis &Dom) {
@@ -300,7 +325,7 @@ void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
Save = MDT->findNearestCommonDominator(Save, &MBB);
if (!Save) {
- DEBUG(dbgs() << "Found a block that is not reachable from Entry\n");
+ LLVM_DEBUG(dbgs() << "Found a block that is not reachable from Entry\n");
return;
}
@@ -334,7 +359,8 @@ void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
}
if (!Restore) {
- DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n");
+ LLVM_DEBUG(
+ dbgs() << "Restore point needs to be spanned on several blocks\n");
return;
}
@@ -413,38 +439,16 @@ void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
}
}
-/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI.
-/// I.e., check if it exists a loop that contains SrcBB and where DestBB is the
-/// loop header.
-static bool isProperBackedge(const MachineLoopInfo &MLI,
- const MachineBasicBlock *SrcBB,
- const MachineBasicBlock *DestBB) {
- for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop;
- Loop = Loop->getParentLoop()) {
- if (Loop->getHeader() == DestBB)
- return true;
- }
- return false;
-}
+static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE,
+ StringRef RemarkName, StringRef RemarkMessage,
+ const DiagnosticLocation &Loc,
+ const MachineBasicBlock *MBB) {
+ ORE->emit([&]() {
+ return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)
+ << RemarkMessage;
+ });
-/// Check if the CFG of \p MF is irreducible.
-static bool isIrreducibleCFG(const MachineFunction &MF,
- const MachineLoopInfo &MLI) {
- const MachineBasicBlock *Entry = &*MF.begin();
- ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry);
- BitVector VisitedBB(MF.getNumBlockIDs());
- for (const MachineBasicBlock *MBB : RPOT) {
- VisitedBB.set(MBB->getNumber());
- for (const MachineBasicBlock *SuccBB : MBB->successors()) {
- if (!VisitedBB.test(SuccBB->getNumber()))
- continue;
- // We already visited SuccBB, thus MBB->SuccBB must be a backedge.
- // Check that the head matches what we have in the loop information.
- // Otherwise, we have an irreducible graph.
- if (!isProperBackedge(MLI, MBB, SuccBB))
- return true;
- }
- }
+ LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
return false;
}
@@ -452,19 +456,21 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF))
return false;
- DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
+ LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
init(MF);
- if (isIrreducibleCFG(MF, *MLI)) {
+ ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
+ if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {
// If MF is irreducible, a block may be in a loop without
// MachineLoopInfo reporting it. I.e., we may use the
// post-dominance property in loops, which lead to incorrect
// results. Moreover, we may miss that the prologue and
// epilogue are not in the same loop, leading to unbalanced
// construction/deconstruction of the stack frame.
- DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n");
- return false;
+ return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG",
+ "Irreducible CFGs are not supported yet.",
+ MF.getFunction().getSubprogram(), &MF.front());
}
const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
@@ -472,12 +478,28 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
for (MachineBasicBlock &MBB : MF) {
- DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName()
- << '\n');
-
- if (MBB.isEHFuncletEntry()) {
- DEBUG(dbgs() << "EH Funclets are not supported yet.\n");
- return false;
+ LLVM_DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' '
+ << MBB.getName() << '\n');
+
+ if (MBB.isEHFuncletEntry())
+ return giveUpWithRemarks(ORE, "UnsupportedEHFunclets",
+ "EH Funclets are not supported yet.",
+ MBB.front().getDebugLoc(), &MBB);
+
+ if (MBB.isEHPad()) {
+ // Push the prologue and epilogue outside of
+ // the region that may throw by making sure
+ // that all the landing pads are at least at the
+ // boundary of the save and restore points.
+ // The problem with exceptions is that the throw
+ // is not properly modeled and in particular, a
+ // basic block can jump out from the middle.
+ updateSaveRestorePoints(MBB, RS.get());
+ if (!ArePointsInteresting()) {
+ LLVM_DEBUG(dbgs() << "EHPad prevents shrink-wrapping\n");
+ return false;
+ }
+ continue;
}
for (const MachineInstr &MI : MBB) {
@@ -489,7 +511,7 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
// If we are at a point where we cannot improve the placement of
// save/restore instructions, just give up.
if (!ArePointsInteresting()) {
- DEBUG(dbgs() << "No Shrink wrap candidate found\n");
+ LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
return false;
}
// No need to look for other instructions, this basic block
@@ -502,20 +524,21 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
// because it means we did not encounter any frame/CSR related code.
// Otherwise, we would have returned from the previous loop.
assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
- DEBUG(dbgs() << "Nothing to shrink-wrap\n");
+ LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
return false;
}
- DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
- << '\n');
+ LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
+ << '\n');
const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
do {
- DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
- << Save->getNumber() << ' ' << Save->getName() << ' '
- << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: "
- << Restore->getNumber() << ' ' << Restore->getName() << ' '
- << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
+ LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
+ << Save->getNumber() << ' ' << Save->getName() << ' '
+ << MBFI->getBlockFreq(Save).getFrequency()
+ << "\nRestore: " << Restore->getNumber() << ' '
+ << Restore->getName() << ' '
+ << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
@@ -523,7 +546,8 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
TFI->canUseAsEpilogue(*Restore)))
break;
- DEBUG(dbgs() << "New points are too expensive or invalid for the target\n");
+ LLVM_DEBUG(
+ dbgs() << "New points are too expensive or invalid for the target\n");
MachineBasicBlock *NewBB;
if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
@@ -545,9 +569,10 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
return false;
}
- DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber()
- << ' ' << Save->getName() << "\nRestore: "
- << Restore->getNumber() << ' ' << Restore->getName() << '\n');
+ LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
+ << Save->getNumber() << ' ' << Save->getName()
+ << "\nRestore: " << Restore->getNumber() << ' '
+ << Restore->getName() << '\n');
MachineFrameInfo &MFI = MF.getFrameInfo();
MFI.setSavePoint(Save);
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-09 14:37:45 +0000