1047 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This pass looks for safe point where the prologue and epilogue can be10// inserted.11// The safe point for the prologue (resp. epilogue) is called Save12// (resp. Restore).13// A point is safe for prologue (resp. epilogue) if and only if14// it 1) dominates (resp. post-dominates) all the frame related operations and15// between 2) two executions of the Save (resp. Restore) point there is an16// 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// Save21// ...22// Restore23// }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// Save28// ...29// }30// for (int i = 0; i < 10; ++i) {31// ...32// Restore33// }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 regular37// entry and exits blocks.38//39// Property #1 is ensured via the use of MachineDominatorTree and40// MachinePostDominatorTree.41// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both42// 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, then46// MachineFrameInfo is updated with this information.47//48//===----------------------------------------------------------------------===//49 50#include "llvm/CodeGen/ShrinkWrap.h"51#include "llvm/ADT/BitVector.h"52#include "llvm/ADT/PostOrderIterator.h"53#include "llvm/ADT/SetVector.h"54#include "llvm/ADT/SmallVector.h"55#include "llvm/ADT/Statistic.h"56#include "llvm/Analysis/CFG.h"57#include "llvm/Analysis/ValueTracking.h"58#include "llvm/CodeGen/MachineBasicBlock.h"59#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"60#include "llvm/CodeGen/MachineDominators.h"61#include "llvm/CodeGen/MachineFrameInfo.h"62#include "llvm/CodeGen/MachineFunction.h"63#include "llvm/CodeGen/MachineFunctionPass.h"64#include "llvm/CodeGen/MachineInstr.h"65#include "llvm/CodeGen/MachineLoopInfo.h"66#include "llvm/CodeGen/MachineOperand.h"67#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"68#include "llvm/CodeGen/MachinePostDominators.h"69#include "llvm/CodeGen/RegisterClassInfo.h"70#include "llvm/CodeGen/RegisterScavenging.h"71#include "llvm/CodeGen/TargetFrameLowering.h"72#include "llvm/CodeGen/TargetInstrInfo.h"73#include "llvm/CodeGen/TargetLowering.h"74#include "llvm/CodeGen/TargetRegisterInfo.h"75#include "llvm/CodeGen/TargetSubtargetInfo.h"76#include "llvm/IR/Attributes.h"77#include "llvm/IR/Function.h"78#include "llvm/InitializePasses.h"79#include "llvm/MC/MCAsmInfo.h"80#include "llvm/Pass.h"81#include "llvm/Support/CommandLine.h"82#include "llvm/Support/Debug.h"83#include "llvm/Support/ErrorHandling.h"84#include "llvm/Support/raw_ostream.h"85#include "llvm/Target/TargetMachine.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 98static cl::opt<cl::boolOrDefault>99EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,100 cl::desc("enable the shrink-wrapping pass"));101static cl::opt<bool> EnablePostShrinkWrapOpt(102 "enable-shrink-wrap-region-split", cl::init(true), cl::Hidden,103 cl::desc("enable splitting of the restore block if possible"));104 105namespace {106 107/// Class to determine where the safe point to insert the108/// prologue and epilogue are.109/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the110/// shrink-wrapping term for prologue/epilogue placement, this pass111/// does not rely on expensive data-flow analysis. Instead we use the112/// dominance properties and loop information to decide which point113/// are safe for such insertion.114class ShrinkWrapImpl {115 /// Hold callee-saved information.116 RegisterClassInfo RCI;117 MachineDominatorTree *MDT = nullptr;118 MachinePostDominatorTree *MPDT = nullptr;119 120 /// Current safe point found for the prologue.121 /// The prologue will be inserted before the first instruction122 /// in this basic block.123 MachineBasicBlock *Save = nullptr;124 125 /// Current safe point found for the epilogue.126 /// The epilogue will be inserted before the first terminator instruction127 /// in this basic block.128 MachineBasicBlock *Restore = nullptr;129 130 /// Hold the information of the basic block frequency.131 /// Use to check the profitability of the new points.132 MachineBlockFrequencyInfo *MBFI = nullptr;133 134 /// Hold the loop information. Used to determine if Save and Restore135 /// are in the same loop.136 MachineLoopInfo *MLI = nullptr;137 138 // Emit remarks.139 MachineOptimizationRemarkEmitter *ORE = nullptr;140 141 /// Frequency of the Entry block.142 BlockFrequency EntryFreq;143 144 /// Current opcode for frame setup.145 unsigned FrameSetupOpcode = ~0u;146 147 /// Current opcode for frame destroy.148 unsigned FrameDestroyOpcode = ~0u;149 150 /// Stack pointer register, used by llvm.{savestack,restorestack}151 Register SP;152 153 /// Entry block.154 const MachineBasicBlock *Entry = nullptr;155 156 using SetOfRegs = SmallSetVector<unsigned, 16>;157 158 /// Registers that need to be saved for the current function.159 mutable SetOfRegs CurrentCSRs;160 161 /// Current MachineFunction.162 MachineFunction *MachineFunc = nullptr;163 164 /// Is `true` for the block numbers where we assume possible stack accesses165 /// or computation of stack-relative addresses on any CFG path including the166 /// block itself. Is `false` for basic blocks where we can guarantee the167 /// opposite. False positives won't lead to incorrect analysis results,168 /// therefore this approach is fair.169 BitVector StackAddressUsedBlockInfo;170 171 /// Check if \p MI uses or defines a callee-saved register or172 /// a frame index. If this is the case, this means \p MI must happen173 /// after Save and before Restore.174 bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,175 bool StackAddressUsed) const;176 177 const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {178 if (CurrentCSRs.empty()) {179 BitVector SavedRegs;180 const TargetFrameLowering *TFI =181 MachineFunc->getSubtarget().getFrameLowering();182 183 TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS);184 185 for (int Reg = SavedRegs.find_first(); Reg != -1;186 Reg = SavedRegs.find_next(Reg))187 CurrentCSRs.insert((unsigned)Reg);188 }189 return CurrentCSRs;190 }191 192 /// Update the Save and Restore points such that \p MBB is in193 /// the region that is dominated by Save and post-dominated by Restore194 /// and Save and Restore still match the safe point definition.195 /// Such point may not exist and Save and/or Restore may be null after196 /// this call.197 void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);198 199 // Try to find safe point based on dominance and block frequency without200 // any change in IR.201 bool performShrinkWrapping(202 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,203 RegScavenger *RS);204 205 /// This function tries to split the restore point if doing so can shrink the206 /// save point further. \return True if restore point is split.207 bool postShrinkWrapping(bool HasCandidate, MachineFunction &MF,208 RegScavenger *RS);209 210 /// This function analyzes if the restore point can split to create a new211 /// restore point. This function collects212 /// 1. Any preds of current restore that are reachable by callee save/FI213 /// blocks214 /// - indicated by DirtyPreds215 /// 2. Any preds of current restore that are not DirtyPreds - indicated by216 /// CleanPreds217 /// Both sets should be non-empty for considering restore point split.218 bool checkIfRestoreSplittable(219 const MachineBasicBlock *CurRestore,220 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,221 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,222 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,223 const TargetInstrInfo *TII, RegScavenger *RS);224 225 /// Initialize the pass for \p MF.226 void init(MachineFunction &MF) {227 RCI.runOnMachineFunction(MF);228 Save = nullptr;229 Restore = nullptr;230 EntryFreq = MBFI->getEntryFreq();231 const TargetSubtargetInfo &Subtarget = MF.getSubtarget();232 const TargetInstrInfo &TII = *Subtarget.getInstrInfo();233 FrameSetupOpcode = TII.getCallFrameSetupOpcode();234 FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();235 SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore();236 Entry = &MF.front();237 CurrentCSRs.clear();238 MachineFunc = &MF;239 240 ++NumFunc;241 }242 243 /// Check whether or not Save and Restore points are still interesting for244 /// shrink-wrapping.245 bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }246 247public:248 ShrinkWrapImpl(MachineDominatorTree *MDT, MachinePostDominatorTree *MPDT,249 MachineBlockFrequencyInfo *MBFI, MachineLoopInfo *MLI,250 MachineOptimizationRemarkEmitter *ORE)251 : MDT(MDT), MPDT(MPDT), MBFI(MBFI), MLI(MLI), ORE(ORE) {}252 253 /// Check if shrink wrapping is enabled for this target and function.254 static bool isShrinkWrapEnabled(const MachineFunction &MF);255 256 bool run(MachineFunction &MF);257};258 259class ShrinkWrapLegacy : public MachineFunctionPass {260public:261 static char ID;262 263 ShrinkWrapLegacy() : MachineFunctionPass(ID) {264 initializeShrinkWrapLegacyPass(*PassRegistry::getPassRegistry());265 }266 267 void getAnalysisUsage(AnalysisUsage &AU) const override {268 AU.setPreservesAll();269 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();270 AU.addRequired<MachineDominatorTreeWrapperPass>();271 AU.addRequired<MachinePostDominatorTreeWrapperPass>();272 AU.addRequired<MachineLoopInfoWrapperPass>();273 AU.addRequired<MachineOptimizationRemarkEmitterPass>();274 MachineFunctionPass::getAnalysisUsage(AU);275 }276 277 MachineFunctionProperties getRequiredProperties() const override {278 return MachineFunctionProperties().setNoVRegs();279 }280 281 StringRef getPassName() const override { return "Shrink Wrapping analysis"; }282 283 /// Perform the shrink-wrapping analysis and update284 /// the MachineFrameInfo attached to \p MF with the results.285 bool runOnMachineFunction(MachineFunction &MF) override;286};287 288} // end anonymous namespace289 290char ShrinkWrapLegacy::ID = 0;291 292char &llvm::ShrinkWrapID = ShrinkWrapLegacy::ID;293 294INITIALIZE_PASS_BEGIN(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,295 false)296INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)297INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)298INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)299INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)300INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)301INITIALIZE_PASS_END(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,302 false)303 304bool ShrinkWrapImpl::useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,305 bool StackAddressUsed) const {306 /// Check if \p Op is known to access an address not on the function's stack .307 /// At the moment, accesses where the underlying object is a global, function308 /// argument, or jump table are considered non-stack accesses. Note that the309 /// caller's stack may get accessed when passing an argument via the stack,310 /// but not the stack of the current function.311 ///312 auto IsKnownNonStackPtr = [](MachineMemOperand *Op) {313 if (Op->getValue()) {314 const Value *UO = getUnderlyingObject(Op->getValue());315 if (!UO)316 return false;317 if (auto *Arg = dyn_cast<Argument>(UO))318 return !Arg->hasPassPointeeByValueCopyAttr();319 return isa<GlobalValue>(UO);320 }321 if (const PseudoSourceValue *PSV = Op->getPseudoValue())322 return PSV->isJumpTable() || PSV->isConstantPool();323 return false;324 };325 // Load/store operations may access the stack indirectly when we previously326 // computed an address to a stack location.327 if (StackAddressUsed && MI.mayLoadOrStore() &&328 (MI.isCall() || MI.hasUnmodeledSideEffects() || MI.memoperands_empty() ||329 !all_of(MI.memoperands(), IsKnownNonStackPtr)))330 return true;331 332 if (MI.getOpcode() == FrameSetupOpcode ||333 MI.getOpcode() == FrameDestroyOpcode) {334 LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');335 return true;336 }337 const MachineFunction *MF = MI.getParent()->getParent();338 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();339 for (const MachineOperand &MO : MI.operands()) {340 bool UseOrDefCSR = false;341 if (MO.isReg()) {342 // Ignore instructions like DBG_VALUE which don't read/def the register.343 if (!MO.isDef() && !MO.readsReg())344 continue;345 Register PhysReg = MO.getReg();346 if (!PhysReg)347 continue;348 assert(PhysReg.isPhysical() && "Unallocated register?!");349 // The stack pointer is not normally described as a callee-saved register350 // in calling convention definitions, so we need to watch for it351 // separately. An SP mentioned by a call instruction, we can ignore,352 // though, as it's harmless and we do not want to effectively disable tail353 // calls by forcing the restore point to post-dominate them.354 // PPC's LR is also not normally described as a callee-saved register in355 // calling convention definitions, so we need to watch for it, too. An LR356 // mentioned implicitly by a return (or "branch to link register")357 // instruction we can ignore, otherwise we may pessimize shrinkwrapping.358 // PPC's Frame pointer (FP) is also not described as a callee-saved359 // register. Until the FP is assigned a Physical Register PPC's FP needs360 // to be checked separately.361 UseOrDefCSR = (!MI.isCall() && PhysReg == SP) ||362 RCI.getLastCalleeSavedAlias(PhysReg) ||363 (!MI.isReturn() &&364 TRI->isNonallocatableRegisterCalleeSave(PhysReg)) ||365 TRI->isVirtualFrameRegister(PhysReg);366 } else if (MO.isRegMask()) {367 // Check if this regmask clobbers any of the CSRs.368 for (unsigned Reg : getCurrentCSRs(RS)) {369 if (MO.clobbersPhysReg(Reg)) {370 UseOrDefCSR = true;371 break;372 }373 }374 }375 // Skip FrameIndex operands in DBG_VALUE instructions.376 if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {377 LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("378 << MO.isFI() << "): " << MI << '\n');379 return true;380 }381 }382 return false;383}384 385/// Helper function to find the immediate (post) dominator.386template <typename ListOfBBs, typename DominanceAnalysis>387static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,388 DominanceAnalysis &Dom, bool Strict = true) {389 MachineBasicBlock *IDom = Dom.findNearestCommonDominator(iterator_range(BBs));390 if (Strict && IDom == &Block)391 return nullptr;392 return IDom;393}394 395static bool isAnalyzableBB(const TargetInstrInfo &TII,396 MachineBasicBlock &Entry) {397 // Check if the block is analyzable.398 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;399 SmallVector<MachineOperand, 4> Cond;400 return !TII.analyzeBranch(Entry, TBB, FBB, Cond);401}402 403/// Determines if any predecessor of MBB is on the path from block that has use404/// or def of CSRs/FI to MBB.405/// ReachableByDirty: All blocks reachable from block that has use or def of406/// CSR/FI.407static bool408hasDirtyPred(const DenseSet<const MachineBasicBlock *> &ReachableByDirty,409 const MachineBasicBlock &MBB) {410 for (const MachineBasicBlock *PredBB : MBB.predecessors())411 if (ReachableByDirty.count(PredBB))412 return true;413 return false;414}415 416/// Derives the list of all the basic blocks reachable from MBB.417static void markAllReachable(DenseSet<const MachineBasicBlock *> &Visited,418 const MachineBasicBlock &MBB) {419 SmallVector<MachineBasicBlock *, 4> Worklist(MBB.successors());420 Visited.insert(&MBB);421 while (!Worklist.empty()) {422 MachineBasicBlock *SuccMBB = Worklist.pop_back_val();423 if (!Visited.insert(SuccMBB).second)424 continue;425 Worklist.append(SuccMBB->succ_begin(), SuccMBB->succ_end());426 }427}428 429/// Collect blocks reachable by use or def of CSRs/FI.430static void collectBlocksReachableByDirty(431 const DenseSet<const MachineBasicBlock *> &DirtyBBs,432 DenseSet<const MachineBasicBlock *> &ReachableByDirty) {433 for (const MachineBasicBlock *MBB : DirtyBBs) {434 if (ReachableByDirty.count(MBB))435 continue;436 // Mark all offsprings as reachable.437 markAllReachable(ReachableByDirty, *MBB);438 }439}440 441/// \return true if there is a clean path from SavePoint to the original442/// Restore.443static bool444isSaveReachableThroughClean(const MachineBasicBlock *SavePoint,445 ArrayRef<MachineBasicBlock *> CleanPreds) {446 DenseSet<const MachineBasicBlock *> Visited;447 SmallVector<MachineBasicBlock *, 4> Worklist(CleanPreds);448 while (!Worklist.empty()) {449 MachineBasicBlock *CleanBB = Worklist.pop_back_val();450 if (CleanBB == SavePoint)451 return true;452 if (!Visited.insert(CleanBB).second || !CleanBB->pred_size())453 continue;454 Worklist.append(CleanBB->pred_begin(), CleanBB->pred_end());455 }456 return false;457}458 459/// This function updates the branches post restore point split.460///461/// Restore point has been split.462/// Old restore point: MBB463/// New restore point: NMBB464/// Any basic block(say BBToUpdate) which had a fallthrough to MBB465/// previously should466/// 1. Fallthrough to NMBB iff NMBB is inserted immediately above MBB in the467/// block layout OR468/// 2. Branch unconditionally to NMBB iff NMBB is inserted at any other place.469static void updateTerminator(MachineBasicBlock *BBToUpdate,470 MachineBasicBlock *NMBB,471 const TargetInstrInfo *TII) {472 DebugLoc DL = BBToUpdate->findBranchDebugLoc();473 // if NMBB isn't the new layout successor for BBToUpdate, insert unconditional474 // branch to it475 if (!BBToUpdate->isLayoutSuccessor(NMBB))476 TII->insertUnconditionalBranch(*BBToUpdate, NMBB, DL);477}478 479/// This function splits the restore point and returns new restore point/BB.480///481/// DirtyPreds: Predessors of \p MBB that are ReachableByDirty482///483/// Decision has been made to split the restore point.484/// old restore point: \p MBB485/// new restore point: \p NMBB486/// This function makes the necessary block layout changes so that487/// 1. \p NMBB points to \p MBB unconditionally488/// 2. All dirtyPreds that previously pointed to \p MBB point to \p NMBB489static MachineBasicBlock *490tryToSplitRestore(MachineBasicBlock *MBB,491 ArrayRef<MachineBasicBlock *> DirtyPreds,492 const TargetInstrInfo *TII) {493 MachineFunction *MF = MBB->getParent();494 495 // get the list of DirtyPreds who have a fallthrough to MBB496 // before the block layout change. This is just to ensure that if the NMBB is497 // inserted after MBB, then we create unconditional branch from498 // DirtyPred/CleanPred to NMBB499 SmallPtrSet<MachineBasicBlock *, 8> MBBFallthrough;500 for (MachineBasicBlock *BB : DirtyPreds)501 if (BB->getFallThrough(false) == MBB)502 MBBFallthrough.insert(BB);503 504 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();505 // Insert this block at the end of the function. Inserting in between may506 // interfere with control flow optimizer decisions.507 MF->insert(MF->end(), NMBB);508 509 for (const MachineBasicBlock::RegisterMaskPair &LI : MBB->liveins())510 NMBB->addLiveIn(LI.PhysReg);511 512 TII->insertUnconditionalBranch(*NMBB, MBB, DebugLoc());513 514 // After splitting, all predecessors of the restore point should be dirty515 // blocks.516 for (MachineBasicBlock *SuccBB : DirtyPreds)517 SuccBB->ReplaceUsesOfBlockWith(MBB, NMBB);518 519 NMBB->addSuccessor(MBB);520 521 for (MachineBasicBlock *BBToUpdate : MBBFallthrough)522 updateTerminator(BBToUpdate, NMBB, TII);523 524 return NMBB;525}526 527/// This function undoes the restore point split done earlier.528///529/// DirtyPreds: All predecessors of \p NMBB that are ReachableByDirty.530///531/// Restore point was split and the change needs to be unrolled. Make necessary532/// changes to reset restore point from \p NMBB to \p MBB.533static void rollbackRestoreSplit(MachineFunction &MF, MachineBasicBlock *NMBB,534 MachineBasicBlock *MBB,535 ArrayRef<MachineBasicBlock *> DirtyPreds,536 const TargetInstrInfo *TII) {537 // For a BB, if NMBB is fallthrough in the current layout, then in the new538 // layout a. BB should fallthrough to MBB OR b. BB should undconditionally539 // branch to MBB540 SmallPtrSet<MachineBasicBlock *, 8> NMBBFallthrough;541 for (MachineBasicBlock *BB : DirtyPreds)542 if (BB->getFallThrough(false) == NMBB)543 NMBBFallthrough.insert(BB);544 545 NMBB->removeSuccessor(MBB);546 for (MachineBasicBlock *SuccBB : DirtyPreds)547 SuccBB->ReplaceUsesOfBlockWith(NMBB, MBB);548 549 NMBB->erase(NMBB->begin(), NMBB->end());550 NMBB->eraseFromParent();551 552 for (MachineBasicBlock *BBToUpdate : NMBBFallthrough)553 updateTerminator(BBToUpdate, MBB, TII);554}555 556// A block is deemed fit for restore point split iff there exist557// 1. DirtyPreds - preds of CurRestore reachable from use or def of CSR/FI558// 2. CleanPreds - preds of CurRestore that arent DirtyPreds559bool ShrinkWrapImpl::checkIfRestoreSplittable(560 const MachineBasicBlock *CurRestore,561 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,562 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,563 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,564 const TargetInstrInfo *TII, RegScavenger *RS) {565 for (const MachineInstr &MI : *CurRestore)566 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true))567 return false;568 569 for (MachineBasicBlock *PredBB : CurRestore->predecessors()) {570 if (!isAnalyzableBB(*TII, *PredBB))571 return false;572 573 if (ReachableByDirty.count(PredBB))574 DirtyPreds.push_back(PredBB);575 else576 CleanPreds.push_back(PredBB);577 }578 579 return !(CleanPreds.empty() || DirtyPreds.empty());580}581 582bool ShrinkWrapImpl::postShrinkWrapping(bool HasCandidate, MachineFunction &MF,583 RegScavenger *RS) {584 if (!EnablePostShrinkWrapOpt)585 return false;586 587 MachineBasicBlock *InitSave = nullptr;588 MachineBasicBlock *InitRestore = nullptr;589 590 if (HasCandidate) {591 InitSave = Save;592 InitRestore = Restore;593 } else {594 InitRestore = nullptr;595 InitSave = &MF.front();596 for (MachineBasicBlock &MBB : MF) {597 if (MBB.isEHFuncletEntry())598 return false;599 if (MBB.isReturnBlock()) {600 // Do not support multiple restore points.601 if (InitRestore)602 return false;603 InitRestore = &MBB;604 }605 }606 }607 608 if (!InitSave || !InitRestore || InitRestore == InitSave ||609 !MDT->dominates(InitSave, InitRestore) ||610 !MPDT->dominates(InitRestore, InitSave))611 return false;612 613 // Bail out of the optimization if any of the basic block is target of614 // INLINEASM_BR instruction615 for (MachineBasicBlock &MBB : MF)616 if (MBB.isInlineAsmBrIndirectTarget())617 return false;618 619 DenseSet<const MachineBasicBlock *> DirtyBBs;620 for (MachineBasicBlock &MBB : MF) {621 if (MBB.isEHPad()) {622 DirtyBBs.insert(&MBB);623 continue;624 }625 for (const MachineInstr &MI : MBB)626 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true)) {627 DirtyBBs.insert(&MBB);628 break;629 }630 }631 632 // Find blocks reachable from the use or def of CSRs/FI.633 DenseSet<const MachineBasicBlock *> ReachableByDirty;634 collectBlocksReachableByDirty(DirtyBBs, ReachableByDirty);635 636 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();637 SmallVector<MachineBasicBlock *, 2> DirtyPreds;638 SmallVector<MachineBasicBlock *, 2> CleanPreds;639 if (!checkIfRestoreSplittable(InitRestore, ReachableByDirty, DirtyPreds,640 CleanPreds, TII, RS))641 return false;642 643 // Trying to reach out to the new save point which dominates all dirty blocks.644 MachineBasicBlock *NewSave =645 FindIDom<>(**DirtyPreds.begin(), DirtyPreds, *MDT, false);646 647 while (NewSave && (hasDirtyPred(ReachableByDirty, *NewSave) ||648 EntryFreq < MBFI->getBlockFreq(NewSave) ||649 /*Entry freq has been observed more than a loop block in650 some cases*/651 MLI->getLoopFor(NewSave)))652 NewSave = FindIDom<>(**NewSave->pred_begin(), NewSave->predecessors(), *MDT,653 false);654 655 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();656 if (!NewSave || NewSave == InitSave ||657 isSaveReachableThroughClean(NewSave, CleanPreds) ||658 !TFI->canUseAsPrologue(*NewSave))659 return false;660 661 // Now we know that splitting a restore point can isolate the restore point662 // from clean blocks and doing so can shrink the save point.663 MachineBasicBlock *NewRestore =664 tryToSplitRestore(InitRestore, DirtyPreds, TII);665 666 // Make sure if the new restore point is valid as an epilogue, depending on667 // targets.668 if (!TFI->canUseAsEpilogue(*NewRestore)) {669 rollbackRestoreSplit(MF, NewRestore, InitRestore, DirtyPreds, TII);670 return false;671 }672 673 Save = NewSave;674 Restore = NewRestore;675 676 MDT->recalculate(MF);677 MPDT->recalculate(MF);678 679 assert((MDT->dominates(Save, Restore) && MPDT->dominates(Restore, Save)) &&680 "Incorrect save or restore point due to dominance relations");681 assert((!MLI->getLoopFor(Save) && !MLI->getLoopFor(Restore)) &&682 "Unexpected save or restore point in a loop");683 assert((EntryFreq >= MBFI->getBlockFreq(Save) &&684 EntryFreq >= MBFI->getBlockFreq(Restore)) &&685 "Incorrect save or restore point based on block frequency");686 return true;687}688 689void ShrinkWrapImpl::updateSaveRestorePoints(MachineBasicBlock &MBB,690 RegScavenger *RS) {691 // Get rid of the easy cases first.692 if (!Save)693 Save = &MBB;694 else695 Save = MDT->findNearestCommonDominator(Save, &MBB);696 assert(Save);697 698 if (!Restore)699 Restore = &MBB;700 else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it701 // means the block never returns. If that's the702 // case, we don't want to call703 // `findNearestCommonDominator`, which will704 // return `Restore`.705 Restore = MPDT->findNearestCommonDominator(Restore, &MBB);706 else707 Restore = nullptr; // Abort, we can't find a restore point in this case.708 709 // Make sure we would be able to insert the restore code before the710 // terminator.711 if (Restore == &MBB) {712 for (const MachineInstr &Terminator : MBB.terminators()) {713 if (!useOrDefCSROrFI(Terminator, RS, /*StackAddressUsed=*/true))714 continue;715 // One of the terminator needs to happen before the restore point.716 if (MBB.succ_empty()) {717 Restore = nullptr; // Abort, we can't find a restore point in this case.718 break;719 }720 // Look for a restore point that post-dominates all the successors.721 // The immediate post-dominator is what we are looking for.722 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);723 break;724 }725 }726 727 if (!Restore) {728 LLVM_DEBUG(729 dbgs() << "Restore point needs to be spanned on several blocks\n");730 return;731 }732 733 // Make sure Save and Restore are suitable for shrink-wrapping:734 // 1. all path from Save needs to lead to Restore before exiting.735 // 2. all path to Restore needs to go through Save from Entry.736 // We achieve that by making sure that:737 // A. Save dominates Restore.738 // B. Restore post-dominates Save.739 // C. Save and Restore are in the same loop.740 bool SaveDominatesRestore = false;741 bool RestorePostDominatesSave = false;742 while (Restore &&743 (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||744 !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||745 // Post-dominance is not enough in loops to ensure that all uses/defs746 // are after the prologue and before the epilogue at runtime.747 // E.g.,748 // while(1) {749 // Save750 // Restore751 // if (...)752 // break;753 // use/def CSRs754 // }755 // All the uses/defs of CSRs are dominated by Save and post-dominated756 // by Restore. However, the CSRs uses are still reachable after757 // Restore and before Save are executed.758 //759 // For now, just push the restore/save points outside of loops.760 // FIXME: Refine the criteria to still find interesting cases761 // for loops.762 MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {763 // Fix (A).764 if (!SaveDominatesRestore) {765 Save = MDT->findNearestCommonDominator(Save, Restore);766 continue;767 }768 // Fix (B).769 if (!RestorePostDominatesSave)770 Restore = MPDT->findNearestCommonDominator(Restore, Save);771 772 // Fix (C).773 if (Restore && (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {774 if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) {775 // Push Save outside of this loop if immediate dominator is different776 // from save block. If immediate dominator is not different, bail out.777 Save = FindIDom<>(*Save, Save->predecessors(), *MDT);778 if (!Save)779 break;780 } else {781 // If the loop does not exit, there is no point in looking782 // for a post-dominator outside the loop.783 SmallVector<MachineBasicBlock*, 4> ExitBlocks;784 MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks);785 // Push Restore outside of this loop.786 // Look for the immediate post-dominator of the loop exits.787 MachineBasicBlock *IPdom = Restore;788 for (MachineBasicBlock *LoopExitBB: ExitBlocks) {789 IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);790 if (!IPdom)791 break;792 }793 // If the immediate post-dominator is not in a less nested loop,794 // then we are stuck in a program with an infinite loop.795 // In that case, we will not find a safe point, hence, bail out.796 if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore))797 Restore = IPdom;798 else {799 Restore = nullptr;800 break;801 }802 }803 }804 }805}806 807static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE,808 StringRef RemarkName, StringRef RemarkMessage,809 const DiagnosticLocation &Loc,810 const MachineBasicBlock *MBB) {811 ORE->emit([&]() {812 return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)813 << RemarkMessage;814 });815 816 LLVM_DEBUG(dbgs() << RemarkMessage << '\n');817 return false;818}819 820bool ShrinkWrapImpl::performShrinkWrapping(821 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,822 RegScavenger *RS) {823 for (MachineBasicBlock *MBB : RPOT) {824 LLVM_DEBUG(dbgs() << "Look into: " << printMBBReference(*MBB) << '\n');825 826 if (MBB->isEHFuncletEntry())827 return giveUpWithRemarks(ORE, "UnsupportedEHFunclets",828 "EH Funclets are not supported yet.",829 MBB->front().getDebugLoc(), MBB);830 831 if (MBB->isEHPad() || MBB->isInlineAsmBrIndirectTarget()) {832 // Push the prologue and epilogue outside of the region that may throw (or833 // jump out via inlineasm_br), by making sure that all the landing pads834 // are at least at the boundary of the save and restore points. The835 // problem is that a basic block can jump out from the middle in these836 // cases, which we do not handle.837 updateSaveRestorePoints(*MBB, RS);838 if (!ArePointsInteresting()) {839 LLVM_DEBUG(dbgs() << "EHPad/inlineasm_br prevents shrink-wrapping\n");840 return false;841 }842 continue;843 }844 845 bool StackAddressUsed = false;846 // Check if we found any stack accesses in the predecessors. We are not847 // doing a full dataflow analysis here to keep things simple but just848 // rely on a reverse portorder traversal (RPOT) to guarantee predecessors849 // are already processed except for loops (and accept the conservative850 // result for loops).851 for (const MachineBasicBlock *Pred : MBB->predecessors()) {852 if (StackAddressUsedBlockInfo.test(Pred->getNumber())) {853 StackAddressUsed = true;854 break;855 }856 }857 858 for (const MachineInstr &MI : *MBB) {859 if (useOrDefCSROrFI(MI, RS, StackAddressUsed)) {860 // Save (resp. restore) point must dominate (resp. post dominate)861 // MI. Look for the proper basic block for those.862 updateSaveRestorePoints(*MBB, RS);863 // If we are at a point where we cannot improve the placement of864 // save/restore instructions, just give up.865 if (!ArePointsInteresting()) {866 LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");867 return false;868 }869 // No need to look for other instructions, this basic block870 // will already be part of the handled region.871 StackAddressUsed = true;872 break;873 }874 }875 StackAddressUsedBlockInfo[MBB->getNumber()] = StackAddressUsed;876 }877 if (!ArePointsInteresting()) {878 // If the points are not interesting at this point, then they must be null879 // because it means we did not encounter any frame/CSR related code.880 // Otherwise, we would have returned from the previous loop.881 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");882 LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");883 return false;884 }885 886 LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: "887 << EntryFreq.getFrequency() << '\n');888 889 const TargetFrameLowering *TFI =890 MachineFunc->getSubtarget().getFrameLowering();891 do {892 LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "893 << printMBBReference(*Save) << ' '894 << printBlockFreq(*MBFI, *Save)895 << "\nRestore: " << printMBBReference(*Restore) << ' '896 << printBlockFreq(*MBFI, *Restore) << '\n');897 898 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;899 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save)) &&900 EntryFreq >= MBFI->getBlockFreq(Restore)) &&901 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&902 TFI->canUseAsEpilogue(*Restore)))903 break;904 LLVM_DEBUG(905 dbgs() << "New points are too expensive or invalid for the target\n");906 MachineBasicBlock *NewBB;907 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {908 Save = FindIDom<>(*Save, Save->predecessors(), *MDT);909 if (!Save)910 break;911 NewBB = Save;912 } else {913 // Restore is expensive.914 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);915 if (!Restore)916 break;917 NewBB = Restore;918 }919 updateSaveRestorePoints(*NewBB, RS);920 } while (Save && Restore);921 922 if (!ArePointsInteresting()) {923 ++NumCandidatesDropped;924 return false;925 }926 return true;927}928 929bool ShrinkWrapImpl::run(MachineFunction &MF) {930 LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');931 932 init(MF);933 934 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());935 if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {936 // If MF is irreducible, a block may be in a loop without937 // MachineLoopInfo reporting it. I.e., we may use the938 // post-dominance property in loops, which lead to incorrect939 // results. Moreover, we may miss that the prologue and940 // epilogue are not in the same loop, leading to unbalanced941 // construction/deconstruction of the stack frame.942 return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG",943 "Irreducible CFGs are not supported yet.",944 MF.getFunction().getSubprogram(), &MF.front());945 }946 947 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();948 std::unique_ptr<RegScavenger> RS(949 TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);950 951 bool Changed = false;952 953 // Initially, conservatively assume that stack addresses can be used in each954 // basic block and change the state only for those basic blocks for which we955 // were able to prove the opposite.956 StackAddressUsedBlockInfo.resize(MF.getNumBlockIDs(), true);957 bool HasCandidate = performShrinkWrapping(RPOT, RS.get());958 StackAddressUsedBlockInfo.clear();959 Changed = postShrinkWrapping(HasCandidate, MF, RS.get());960 if (!HasCandidate && !Changed)961 return false;962 if (!ArePointsInteresting())963 return Changed;964 965 LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "966 << printMBBReference(*Save) << ' '967 << "\nRestore: " << printMBBReference(*Restore) << '\n');968 969 MachineFrameInfo &MFI = MF.getFrameInfo();970 971 // List of CalleeSavedInfo for registers will be added during prologepilog972 // pass973 SaveRestorePoints SavePoints({{Save, {}}});974 SaveRestorePoints RestorePoints({{Restore, {}}});975 976 MFI.setSavePoints(SavePoints);977 MFI.setRestorePoints(RestorePoints);978 ++NumCandidates;979 return Changed;980}981 982bool ShrinkWrapLegacy::runOnMachineFunction(MachineFunction &MF) {983 if (skipFunction(MF.getFunction()) || MF.empty() ||984 !ShrinkWrapImpl::isShrinkWrapEnabled(MF))985 return false;986 987 MachineDominatorTree *MDT =988 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();989 MachinePostDominatorTree *MPDT =990 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();991 MachineBlockFrequencyInfo *MBFI =992 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();993 MachineLoopInfo *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();994 MachineOptimizationRemarkEmitter *ORE =995 &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();996 997 return ShrinkWrapImpl(MDT, MPDT, MBFI, MLI, ORE).run(MF);998}999 1000PreservedAnalyses ShrinkWrapPass::run(MachineFunction &MF,1001 MachineFunctionAnalysisManager &MFAM) {1002 MFPropsModifier _(*this, MF);1003 if (MF.empty() || !ShrinkWrapImpl::isShrinkWrapEnabled(MF))1004 return PreservedAnalyses::all();1005 1006 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(MF);1007 MachinePostDominatorTree &MPDT =1008 MFAM.getResult<MachinePostDominatorTreeAnalysis>(MF);1009 MachineBlockFrequencyInfo &MBFI =1010 MFAM.getResult<MachineBlockFrequencyAnalysis>(MF);1011 MachineLoopInfo &MLI = MFAM.getResult<MachineLoopAnalysis>(MF);1012 MachineOptimizationRemarkEmitter &ORE =1013 MFAM.getResult<MachineOptimizationRemarkEmitterAnalysis>(MF);1014 1015 ShrinkWrapImpl(&MDT, &MPDT, &MBFI, &MLI, &ORE).run(MF);1016 return PreservedAnalyses::all();1017}1018 1019bool ShrinkWrapImpl::isShrinkWrapEnabled(const MachineFunction &MF) {1020 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();1021 1022 switch (EnableShrinkWrapOpt) {1023 case cl::BOU_UNSET:1024 return TFI->enableShrinkWrapping(MF) &&1025 // Windows with CFI has some limitations that make it impossible1026 // to use shrink-wrapping.1027 !MF.getTarget().getMCAsmInfo()->usesWindowsCFI() &&1028 // Sanitizers look at the value of the stack at the location1029 // of the crash. Since a crash can happen anywhere, the1030 // frame must be lowered before anything else happen for the1031 // sanitizers to be able to get a correct stack frame.1032 !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) ||1033 MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) ||1034 MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) ||1035 MF.getFunction().hasFnAttribute(Attribute::SanitizeType) ||1036 MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress));1037 // If EnableShrinkWrap is set, it takes precedence on whatever the1038 // target sets. The rational is that we assume we want to test1039 // something related to shrink-wrapping.1040 case cl::BOU_TRUE:1041 return true;1042 case cl::BOU_FALSE:1043 return false;1044 }1045 llvm_unreachable("Invalid shrink-wrapping state");1046}1047