1327952Sdim//===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===// 2283625Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6283625Sdim// 7283625Sdim//===----------------------------------------------------------------------===// 8283625Sdim// 9283625Sdim// This pass looks for safe point where the prologue and epilogue can be 10283625Sdim// inserted. 11283625Sdim// The safe point for the prologue (resp. epilogue) is called Save 12283625Sdim// (resp. Restore). 13283625Sdim// A point is safe for prologue (resp. epilogue) if and only if 14283625Sdim// it 1) dominates (resp. post-dominates) all the frame related operations and 15283625Sdim// between 2) two executions of the Save (resp. Restore) point there is an 16283625Sdim// execution of the Restore (resp. Save) point. 17283625Sdim// 18283625Sdim// For instance, the following points are safe: 19283625Sdim// for (int i = 0; i < 10; ++i) { 20283625Sdim// Save 21283625Sdim// ... 22283625Sdim// Restore 23283625Sdim// } 24283625Sdim// Indeed, the execution looks like Save -> Restore -> Save -> Restore ... 25283625Sdim// And the following points are not: 26283625Sdim// for (int i = 0; i < 10; ++i) { 27283625Sdim// Save 28283625Sdim// ... 29283625Sdim// } 30283625Sdim// for (int i = 0; i < 10; ++i) { 31283625Sdim// ... 32283625Sdim// Restore 33283625Sdim// } 34283625Sdim// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore. 35283625Sdim// 36283625Sdim// This pass also ensures that the safe points are 3) cheaper than the regular 37283625Sdim// entry and exits blocks. 38283625Sdim// 39283625Sdim// Property #1 is ensured via the use of MachineDominatorTree and 40283625Sdim// MachinePostDominatorTree. 41283625Sdim// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both 42283625Sdim// points must be in the same loop. 43283625Sdim// Property #3 is ensured via the MachineBlockFrequencyInfo. 44283625Sdim// 45296417Sdim// If this pass found points matching all these properties, then 46296417Sdim// MachineFrameInfo is updated with this information. 47327952Sdim// 48283625Sdim//===----------------------------------------------------------------------===// 49327952Sdim 50296417Sdim#include "llvm/ADT/BitVector.h" 51296417Sdim#include "llvm/ADT/PostOrderIterator.h" 52296417Sdim#include "llvm/ADT/SetVector.h" 53327952Sdim#include "llvm/ADT/SmallVector.h" 54283625Sdim#include "llvm/ADT/Statistic.h" 55341825Sdim#include "llvm/Analysis/CFG.h" 56327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 57283625Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 58283625Sdim#include "llvm/CodeGen/MachineDominators.h" 59327952Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 60327952Sdim#include "llvm/CodeGen/MachineFunction.h" 61283625Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 62327952Sdim#include "llvm/CodeGen/MachineInstr.h" 63283625Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 64327952Sdim#include "llvm/CodeGen/MachineOperand.h" 65341825Sdim#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 66283625Sdim#include "llvm/CodeGen/MachinePostDominators.h" 67283625Sdim#include "llvm/CodeGen/RegisterClassInfo.h" 68296417Sdim#include "llvm/CodeGen/RegisterScavenging.h" 69327952Sdim#include "llvm/CodeGen/TargetFrameLowering.h" 70327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 71341825Sdim#include "llvm/CodeGen/TargetLowering.h" 72327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 73327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 74327952Sdim#include "llvm/IR/Attributes.h" 75327952Sdim#include "llvm/IR/Function.h" 76360784Sdim#include "llvm/InitializePasses.h" 77296417Sdim#include "llvm/MC/MCAsmInfo.h" 78327952Sdim#include "llvm/Pass.h" 79327952Sdim#include "llvm/Support/CommandLine.h" 80283625Sdim#include "llvm/Support/Debug.h" 81327952Sdim#include "llvm/Support/ErrorHandling.h" 82327952Sdim#include "llvm/Support/raw_ostream.h" 83296417Sdim#include "llvm/Target/TargetMachine.h" 84327952Sdim#include <cassert> 85327952Sdim#include <cstdint> 86327952Sdim#include <memory> 87283625Sdim 88327952Sdimusing namespace llvm; 89327952Sdim 90283625Sdim#define DEBUG_TYPE "shrink-wrap" 91283625Sdim 92283625SdimSTATISTIC(NumFunc, "Number of functions"); 93283625SdimSTATISTIC(NumCandidates, "Number of shrink-wrapping candidates"); 94283625SdimSTATISTIC(NumCandidatesDropped, 95283625Sdim "Number of shrink-wrapping candidates dropped because of frequency"); 96283625Sdim 97296417Sdimstatic cl::opt<cl::boolOrDefault> 98327952SdimEnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, 99327952Sdim cl::desc("enable the shrink-wrapping pass")); 100296417Sdim 101283625Sdimnamespace { 102327952Sdim 103341825Sdim/// Class to determine where the safe point to insert the 104283625Sdim/// prologue and epilogue are. 105283625Sdim/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the 106283625Sdim/// shrink-wrapping term for prologue/epilogue placement, this pass 107283625Sdim/// does not rely on expensive data-flow analysis. Instead we use the 108283625Sdim/// dominance properties and loop information to decide which point 109283625Sdim/// are safe for such insertion. 110283625Sdimclass ShrinkWrap : public MachineFunctionPass { 111283625Sdim /// Hold callee-saved information. 112283625Sdim RegisterClassInfo RCI; 113283625Sdim MachineDominatorTree *MDT; 114283625Sdim MachinePostDominatorTree *MPDT; 115327952Sdim 116283625Sdim /// Current safe point found for the prologue. 117283625Sdim /// The prologue will be inserted before the first instruction 118283625Sdim /// in this basic block. 119283625Sdim MachineBasicBlock *Save; 120327952Sdim 121283625Sdim /// Current safe point found for the epilogue. 122283625Sdim /// The epilogue will be inserted before the first terminator instruction 123283625Sdim /// in this basic block. 124283625Sdim MachineBasicBlock *Restore; 125327952Sdim 126283625Sdim /// Hold the information of the basic block frequency. 127283625Sdim /// Use to check the profitability of the new points. 128283625Sdim MachineBlockFrequencyInfo *MBFI; 129327952Sdim 130283625Sdim /// Hold the loop information. Used to determine if Save and Restore 131283625Sdim /// are in the same loop. 132283625Sdim MachineLoopInfo *MLI; 133327952Sdim 134341825Sdim // Emit remarks. 135341825Sdim MachineOptimizationRemarkEmitter *ORE = nullptr; 136341825Sdim 137283625Sdim /// Frequency of the Entry block. 138283625Sdim uint64_t EntryFreq; 139327952Sdim 140283625Sdim /// Current opcode for frame setup. 141283625Sdim unsigned FrameSetupOpcode; 142327952Sdim 143283625Sdim /// Current opcode for frame destroy. 144283625Sdim unsigned FrameDestroyOpcode; 145327952Sdim 146341825Sdim /// Stack pointer register, used by llvm.{savestack,restorestack} 147341825Sdim unsigned SP; 148341825Sdim 149283625Sdim /// Entry block. 150283625Sdim const MachineBasicBlock *Entry; 151327952Sdim 152327952Sdim using SetOfRegs = SmallSetVector<unsigned, 16>; 153327952Sdim 154296417Sdim /// Registers that need to be saved for the current function. 155296417Sdim mutable SetOfRegs CurrentCSRs; 156327952Sdim 157296417Sdim /// Current MachineFunction. 158296417Sdim MachineFunction *MachineFunc; 159283625Sdim 160341825Sdim /// Check if \p MI uses or defines a callee-saved register or 161283625Sdim /// a frame index. If this is the case, this means \p MI must happen 162283625Sdim /// after Save and before Restore. 163296417Sdim bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const; 164283625Sdim 165296417Sdim const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const { 166296417Sdim if (CurrentCSRs.empty()) { 167296417Sdim BitVector SavedRegs; 168296417Sdim const TargetFrameLowering *TFI = 169296417Sdim MachineFunc->getSubtarget().getFrameLowering(); 170296417Sdim 171296417Sdim TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS); 172296417Sdim 173296417Sdim for (int Reg = SavedRegs.find_first(); Reg != -1; 174296417Sdim Reg = SavedRegs.find_next(Reg)) 175296417Sdim CurrentCSRs.insert((unsigned)Reg); 176296417Sdim } 177296417Sdim return CurrentCSRs; 178296417Sdim } 179296417Sdim 180341825Sdim /// Update the Save and Restore points such that \p MBB is in 181283625Sdim /// the region that is dominated by Save and post-dominated by Restore 182283625Sdim /// and Save and Restore still match the safe point definition. 183283625Sdim /// Such point may not exist and Save and/or Restore may be null after 184283625Sdim /// this call. 185296417Sdim void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS); 186283625Sdim 187341825Sdim /// Initialize the pass for \p MF. 188283625Sdim void init(MachineFunction &MF) { 189283625Sdim RCI.runOnMachineFunction(MF); 190283625Sdim MDT = &getAnalysis<MachineDominatorTree>(); 191283625Sdim MPDT = &getAnalysis<MachinePostDominatorTree>(); 192283625Sdim Save = nullptr; 193283625Sdim Restore = nullptr; 194283625Sdim MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 195283625Sdim MLI = &getAnalysis<MachineLoopInfo>(); 196341825Sdim ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE(); 197283625Sdim EntryFreq = MBFI->getEntryFreq(); 198341825Sdim const TargetSubtargetInfo &Subtarget = MF.getSubtarget(); 199341825Sdim const TargetInstrInfo &TII = *Subtarget.getInstrInfo(); 200283625Sdim FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 201283625Sdim FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 202341825Sdim SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore(); 203283625Sdim Entry = &MF.front(); 204296417Sdim CurrentCSRs.clear(); 205296417Sdim MachineFunc = &MF; 206283625Sdim 207283625Sdim ++NumFunc; 208283625Sdim } 209283625Sdim 210283625Sdim /// Check whether or not Save and Restore points are still interesting for 211283625Sdim /// shrink-wrapping. 212283625Sdim bool ArePointsInteresting() const { return Save != Entry && Save && Restore; } 213283625Sdim 214341825Sdim /// Check if shrink wrapping is enabled for this target and function. 215296417Sdim static bool isShrinkWrapEnabled(const MachineFunction &MF); 216296417Sdim 217283625Sdimpublic: 218283625Sdim static char ID; 219283625Sdim 220283625Sdim ShrinkWrap() : MachineFunctionPass(ID) { 221283625Sdim initializeShrinkWrapPass(*PassRegistry::getPassRegistry()); 222283625Sdim } 223283625Sdim 224283625Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 225283625Sdim AU.setPreservesAll(); 226283625Sdim AU.addRequired<MachineBlockFrequencyInfo>(); 227283625Sdim AU.addRequired<MachineDominatorTree>(); 228283625Sdim AU.addRequired<MachinePostDominatorTree>(); 229283625Sdim AU.addRequired<MachineLoopInfo>(); 230341825Sdim AU.addRequired<MachineOptimizationRemarkEmitterPass>(); 231283625Sdim MachineFunctionPass::getAnalysisUsage(AU); 232283625Sdim } 233283625Sdim 234341825Sdim MachineFunctionProperties getRequiredProperties() const override { 235341825Sdim return MachineFunctionProperties().set( 236341825Sdim MachineFunctionProperties::Property::NoVRegs); 237341825Sdim } 238341825Sdim 239314564Sdim StringRef getPassName() const override { return "Shrink Wrapping analysis"; } 240283625Sdim 241341825Sdim /// Perform the shrink-wrapping analysis and update 242283625Sdim /// the MachineFrameInfo attached to \p MF with the results. 243283625Sdim bool runOnMachineFunction(MachineFunction &MF) override; 244283625Sdim}; 245283625Sdim 246327952Sdim} // end anonymous namespace 247327952Sdim 248283625Sdimchar ShrinkWrap::ID = 0; 249327952Sdim 250283625Sdimchar &llvm::ShrinkWrapID = ShrinkWrap::ID; 251283625Sdim 252321369SdimINITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) 253283625SdimINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 254283625SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 255283625SdimINITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 256283625SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 257341825SdimINITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass) 258321369SdimINITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) 259283625Sdim 260296417Sdimbool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI, 261296417Sdim RegScavenger *RS) const { 262353358Sdim // This prevents premature stack popping when occurs a indirect stack 263353358Sdim // access. It is overly aggressive for the moment. 264353358Sdim // TODO: - Obvious non-stack loads and store, such as global values, 265353358Sdim // are known to not access the stack. 266353358Sdim // - Further, data dependency and alias analysis can validate 267353358Sdim // that load and stores never derive from the stack pointer. 268353358Sdim if (MI.mayLoadOrStore()) 269353358Sdim return true; 270353358Sdim 271283625Sdim if (MI.getOpcode() == FrameSetupOpcode || 272283625Sdim MI.getOpcode() == FrameDestroyOpcode) { 273341825Sdim LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n'); 274283625Sdim return true; 275283625Sdim } 276283625Sdim for (const MachineOperand &MO : MI.operands()) { 277296417Sdim bool UseOrDefCSR = false; 278283625Sdim if (MO.isReg()) { 279341825Sdim // Ignore instructions like DBG_VALUE which don't read/def the register. 280341825Sdim if (!MO.isDef() && !MO.readsReg()) 281341825Sdim continue; 282360784Sdim Register PhysReg = MO.getReg(); 283283625Sdim if (!PhysReg) 284283625Sdim continue; 285360784Sdim assert(Register::isPhysicalRegister(PhysReg) && "Unallocated register?!"); 286341825Sdim // The stack pointer is not normally described as a callee-saved register 287341825Sdim // in calling convention definitions, so we need to watch for it 288341825Sdim // separately. An SP mentioned by a call instruction, we can ignore, 289341825Sdim // though, as it's harmless and we do not want to effectively disable tail 290341825Sdim // calls by forcing the restore point to post-dominate them. 291341825Sdim UseOrDefCSR = (!MI.isCall() && PhysReg == SP) || 292341825Sdim RCI.getLastCalleeSavedAlias(PhysReg); 293296417Sdim } else if (MO.isRegMask()) { 294296417Sdim // Check if this regmask clobbers any of the CSRs. 295296417Sdim for (unsigned Reg : getCurrentCSRs(RS)) { 296296417Sdim if (MO.clobbersPhysReg(Reg)) { 297296417Sdim UseOrDefCSR = true; 298296417Sdim break; 299296417Sdim } 300296417Sdim } 301283625Sdim } 302341825Sdim // Skip FrameIndex operands in DBG_VALUE instructions. 303341825Sdim if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) { 304341825Sdim LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI(" 305341825Sdim << MO.isFI() << "): " << MI << '\n'); 306283625Sdim return true; 307283625Sdim } 308283625Sdim } 309283625Sdim return false; 310283625Sdim} 311283625Sdim 312341825Sdim/// Helper function to find the immediate (post) dominator. 313283625Sdimtemplate <typename ListOfBBs, typename DominanceAnalysis> 314314564Sdimstatic MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, 315314564Sdim DominanceAnalysis &Dom) { 316283625Sdim MachineBasicBlock *IDom = &Block; 317283625Sdim for (MachineBasicBlock *BB : BBs) { 318283625Sdim IDom = Dom.findNearestCommonDominator(IDom, BB); 319283625Sdim if (!IDom) 320283625Sdim break; 321283625Sdim } 322296417Sdim if (IDom == &Block) 323296417Sdim return nullptr; 324283625Sdim return IDom; 325283625Sdim} 326283625Sdim 327296417Sdimvoid ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB, 328296417Sdim RegScavenger *RS) { 329283625Sdim // Get rid of the easy cases first. 330283625Sdim if (!Save) 331283625Sdim Save = &MBB; 332283625Sdim else 333283625Sdim Save = MDT->findNearestCommonDominator(Save, &MBB); 334283625Sdim 335283625Sdim if (!Save) { 336341825Sdim LLVM_DEBUG(dbgs() << "Found a block that is not reachable from Entry\n"); 337283625Sdim return; 338283625Sdim } 339283625Sdim 340283625Sdim if (!Restore) 341283625Sdim Restore = &MBB; 342321369Sdim else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it 343321369Sdim // means the block never returns. If that's the 344321369Sdim // case, we don't want to call 345321369Sdim // `findNearestCommonDominator`, which will 346321369Sdim // return `Restore`. 347321369Sdim Restore = MPDT->findNearestCommonDominator(Restore, &MBB); 348283625Sdim else 349321369Sdim Restore = nullptr; // Abort, we can't find a restore point in this case. 350283625Sdim 351283625Sdim // Make sure we would be able to insert the restore code before the 352283625Sdim // terminator. 353283625Sdim if (Restore == &MBB) { 354283625Sdim for (const MachineInstr &Terminator : MBB.terminators()) { 355296417Sdim if (!useOrDefCSROrFI(Terminator, RS)) 356283625Sdim continue; 357283625Sdim // One of the terminator needs to happen before the restore point. 358283625Sdim if (MBB.succ_empty()) { 359321369Sdim Restore = nullptr; // Abort, we can't find a restore point in this case. 360283625Sdim break; 361283625Sdim } 362283625Sdim // Look for a restore point that post-dominates all the successors. 363283625Sdim // The immediate post-dominator is what we are looking for. 364283625Sdim Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 365283625Sdim break; 366283625Sdim } 367283625Sdim } 368283625Sdim 369283625Sdim if (!Restore) { 370341825Sdim LLVM_DEBUG( 371341825Sdim dbgs() << "Restore point needs to be spanned on several blocks\n"); 372283625Sdim return; 373283625Sdim } 374283625Sdim 375283625Sdim // Make sure Save and Restore are suitable for shrink-wrapping: 376283625Sdim // 1. all path from Save needs to lead to Restore before exiting. 377283625Sdim // 2. all path to Restore needs to go through Save from Entry. 378283625Sdim // We achieve that by making sure that: 379283625Sdim // A. Save dominates Restore. 380283625Sdim // B. Restore post-dominates Save. 381283625Sdim // C. Save and Restore are in the same loop. 382283625Sdim bool SaveDominatesRestore = false; 383283625Sdim bool RestorePostDominatesSave = false; 384283625Sdim while (Save && Restore && 385283625Sdim (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) || 386283625Sdim !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) || 387296417Sdim // Post-dominance is not enough in loops to ensure that all uses/defs 388296417Sdim // are after the prologue and before the epilogue at runtime. 389296417Sdim // E.g., 390296417Sdim // while(1) { 391296417Sdim // Save 392296417Sdim // Restore 393296417Sdim // if (...) 394296417Sdim // break; 395296417Sdim // use/def CSRs 396296417Sdim // } 397296417Sdim // All the uses/defs of CSRs are dominated by Save and post-dominated 398296417Sdim // by Restore. However, the CSRs uses are still reachable after 399296417Sdim // Restore and before Save are executed. 400296417Sdim // 401296417Sdim // For now, just push the restore/save points outside of loops. 402296417Sdim // FIXME: Refine the criteria to still find interesting cases 403296417Sdim // for loops. 404296417Sdim MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 405283625Sdim // Fix (A). 406283625Sdim if (!SaveDominatesRestore) { 407283625Sdim Save = MDT->findNearestCommonDominator(Save, Restore); 408283625Sdim continue; 409283625Sdim } 410283625Sdim // Fix (B). 411283625Sdim if (!RestorePostDominatesSave) 412283625Sdim Restore = MPDT->findNearestCommonDominator(Restore, Save); 413283625Sdim 414283625Sdim // Fix (C). 415296417Sdim if (Save && Restore && 416296417Sdim (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 417296417Sdim if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) { 418296417Sdim // Push Save outside of this loop if immediate dominator is different 419296417Sdim // from save block. If immediate dominator is not different, bail out. 420283625Sdim Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 421296417Sdim if (!Save) 422296417Sdim break; 423296417Sdim } else { 424296417Sdim // If the loop does not exit, there is no point in looking 425296417Sdim // for a post-dominator outside the loop. 426296417Sdim SmallVector<MachineBasicBlock*, 4> ExitBlocks; 427296417Sdim MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks); 428283625Sdim // Push Restore outside of this loop. 429296417Sdim // Look for the immediate post-dominator of the loop exits. 430296417Sdim MachineBasicBlock *IPdom = Restore; 431296417Sdim for (MachineBasicBlock *LoopExitBB: ExitBlocks) { 432296417Sdim IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT); 433296417Sdim if (!IPdom) 434296417Sdim break; 435296417Sdim } 436296417Sdim // If the immediate post-dominator is not in a less nested loop, 437296417Sdim // then we are stuck in a program with an infinite loop. 438296417Sdim // In that case, we will not find a safe point, hence, bail out. 439296417Sdim if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)) 440296417Sdim Restore = IPdom; 441296417Sdim else { 442296417Sdim Restore = nullptr; 443296417Sdim break; 444296417Sdim } 445296417Sdim } 446283625Sdim } 447283625Sdim } 448283625Sdim} 449283625Sdim 450341825Sdimstatic bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE, 451341825Sdim StringRef RemarkName, StringRef RemarkMessage, 452341825Sdim const DiagnosticLocation &Loc, 453341825Sdim const MachineBasicBlock *MBB) { 454341825Sdim ORE->emit([&]() { 455341825Sdim return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB) 456341825Sdim << RemarkMessage; 457341825Sdim }); 458296417Sdim 459341825Sdim LLVM_DEBUG(dbgs() << RemarkMessage << '\n'); 460296417Sdim return false; 461296417Sdim} 462296417Sdim 463283625Sdimbool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) { 464327952Sdim if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF)) 465283625Sdim return false; 466296417Sdim 467341825Sdim LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 468283625Sdim 469283625Sdim init(MF); 470283625Sdim 471341825Sdim ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin()); 472341825Sdim if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) { 473296417Sdim // If MF is irreducible, a block may be in a loop without 474296417Sdim // MachineLoopInfo reporting it. I.e., we may use the 475296417Sdim // post-dominance property in loops, which lead to incorrect 476296417Sdim // results. Moreover, we may miss that the prologue and 477296417Sdim // epilogue are not in the same loop, leading to unbalanced 478296417Sdim // construction/deconstruction of the stack frame. 479341825Sdim return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG", 480341825Sdim "Irreducible CFGs are not supported yet.", 481341825Sdim MF.getFunction().getSubprogram(), &MF.front()); 482296417Sdim } 483296417Sdim 484296417Sdim const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 485296417Sdim std::unique_ptr<RegScavenger> RS( 486296417Sdim TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr); 487296417Sdim 488283625Sdim for (MachineBasicBlock &MBB : MF) { 489341825Sdim LLVM_DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' 490341825Sdim << MBB.getName() << '\n'); 491283625Sdim 492341825Sdim if (MBB.isEHFuncletEntry()) 493341825Sdim return giveUpWithRemarks(ORE, "UnsupportedEHFunclets", 494341825Sdim "EH Funclets are not supported yet.", 495341825Sdim MBB.front().getDebugLoc(), &MBB); 496341825Sdim 497341825Sdim if (MBB.isEHPad()) { 498341825Sdim // Push the prologue and epilogue outside of 499341825Sdim // the region that may throw by making sure 500341825Sdim // that all the landing pads are at least at the 501341825Sdim // boundary of the save and restore points. 502341825Sdim // The problem with exceptions is that the throw 503341825Sdim // is not properly modeled and in particular, a 504341825Sdim // basic block can jump out from the middle. 505341825Sdim updateSaveRestorePoints(MBB, RS.get()); 506341825Sdim if (!ArePointsInteresting()) { 507341825Sdim LLVM_DEBUG(dbgs() << "EHPad prevents shrink-wrapping\n"); 508341825Sdim return false; 509341825Sdim } 510341825Sdim continue; 511296417Sdim } 512296417Sdim 513283625Sdim for (const MachineInstr &MI : MBB) { 514296417Sdim if (!useOrDefCSROrFI(MI, RS.get())) 515283625Sdim continue; 516283625Sdim // Save (resp. restore) point must dominate (resp. post dominate) 517283625Sdim // MI. Look for the proper basic block for those. 518296417Sdim updateSaveRestorePoints(MBB, RS.get()); 519283625Sdim // If we are at a point where we cannot improve the placement of 520283625Sdim // save/restore instructions, just give up. 521283625Sdim if (!ArePointsInteresting()) { 522341825Sdim LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n"); 523283625Sdim return false; 524283625Sdim } 525283625Sdim // No need to look for other instructions, this basic block 526283625Sdim // will already be part of the handled region. 527283625Sdim break; 528283625Sdim } 529283625Sdim } 530283625Sdim if (!ArePointsInteresting()) { 531283625Sdim // If the points are not interesting at this point, then they must be null 532283625Sdim // because it means we did not encounter any frame/CSR related code. 533283625Sdim // Otherwise, we would have returned from the previous loop. 534283625Sdim assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!"); 535341825Sdim LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n"); 536283625Sdim return false; 537283625Sdim } 538283625Sdim 539341825Sdim LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq 540341825Sdim << '\n'); 541283625Sdim 542283625Sdim const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 543283625Sdim do { 544341825Sdim LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: " 545341825Sdim << Save->getNumber() << ' ' << Save->getName() << ' ' 546341825Sdim << MBFI->getBlockFreq(Save).getFrequency() 547341825Sdim << "\nRestore: " << Restore->getNumber() << ' ' 548341825Sdim << Restore->getName() << ' ' 549341825Sdim << MBFI->getBlockFreq(Restore).getFrequency() << '\n'); 550283625Sdim 551283625Sdim bool IsSaveCheap, TargetCanUseSaveAsPrologue = false; 552283625Sdim if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) && 553283625Sdim EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) && 554283625Sdim ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) && 555283625Sdim TFI->canUseAsEpilogue(*Restore))) 556283625Sdim break; 557341825Sdim LLVM_DEBUG( 558341825Sdim dbgs() << "New points are too expensive or invalid for the target\n"); 559283625Sdim MachineBasicBlock *NewBB; 560283625Sdim if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) { 561283625Sdim Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 562283625Sdim if (!Save) 563283625Sdim break; 564283625Sdim NewBB = Save; 565283625Sdim } else { 566283625Sdim // Restore is expensive. 567283625Sdim Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 568283625Sdim if (!Restore) 569283625Sdim break; 570283625Sdim NewBB = Restore; 571283625Sdim } 572296417Sdim updateSaveRestorePoints(*NewBB, RS.get()); 573283625Sdim } while (Save && Restore); 574283625Sdim 575283625Sdim if (!ArePointsInteresting()) { 576283625Sdim ++NumCandidatesDropped; 577283625Sdim return false; 578283625Sdim } 579283625Sdim 580341825Sdim LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " 581341825Sdim << Save->getNumber() << ' ' << Save->getName() 582341825Sdim << "\nRestore: " << Restore->getNumber() << ' ' 583341825Sdim << Restore->getName() << '\n'); 584283625Sdim 585314564Sdim MachineFrameInfo &MFI = MF.getFrameInfo(); 586314564Sdim MFI.setSavePoint(Save); 587314564Sdim MFI.setRestorePoint(Restore); 588283625Sdim ++NumCandidates; 589283625Sdim return false; 590283625Sdim} 591296417Sdim 592296417Sdimbool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) { 593296417Sdim const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 594296417Sdim 595296417Sdim switch (EnableShrinkWrapOpt) { 596296417Sdim case cl::BOU_UNSET: 597296417Sdim return TFI->enableShrinkWrapping(MF) && 598327952Sdim // Windows with CFI has some limitations that make it impossible 599327952Sdim // to use shrink-wrapping. 600327952Sdim !MF.getTarget().getMCAsmInfo()->usesWindowsCFI() && 601327952Sdim // Sanitizers look at the value of the stack at the location 602327952Sdim // of the crash. Since a crash can happen anywhere, the 603327952Sdim // frame must be lowered before anything else happen for the 604327952Sdim // sanitizers to be able to get a correct stack frame. 605327952Sdim !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) || 606327952Sdim MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) || 607327952Sdim MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) || 608327952Sdim MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress)); 609296417Sdim // If EnableShrinkWrap is set, it takes precedence on whatever the 610296417Sdim // target sets. The rational is that we assume we want to test 611296417Sdim // something related to shrink-wrapping. 612296417Sdim case cl::BOU_TRUE: 613296417Sdim return true; 614296417Sdim case cl::BOU_FALSE: 615296417Sdim return false; 616296417Sdim } 617296417Sdim llvm_unreachable("Invalid shrink-wrapping state"); 618296417Sdim} 619