ShrinkWrap.cpp revision 327952
1327952Sdim//===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===// 2283625Sdim// 3283625Sdim// The LLVM Compiler Infrastructure 4283625Sdim// 5283625Sdim// This file is distributed under the University of Illinois Open Source 6283625Sdim// License. See LICENSE.TXT for details. 7283625Sdim// 8283625Sdim//===----------------------------------------------------------------------===// 9283625Sdim// 10283625Sdim// This pass looks for safe point where the prologue and epilogue can be 11283625Sdim// inserted. 12283625Sdim// The safe point for the prologue (resp. epilogue) is called Save 13283625Sdim// (resp. Restore). 14283625Sdim// A point is safe for prologue (resp. epilogue) if and only if 15283625Sdim// it 1) dominates (resp. post-dominates) all the frame related operations and 16283625Sdim// between 2) two executions of the Save (resp. Restore) point there is an 17283625Sdim// execution of the Restore (resp. Save) point. 18283625Sdim// 19283625Sdim// For instance, the following points are safe: 20283625Sdim// for (int i = 0; i < 10; ++i) { 21283625Sdim// Save 22283625Sdim// ... 23283625Sdim// Restore 24283625Sdim// } 25283625Sdim// Indeed, the execution looks like Save -> Restore -> Save -> Restore ... 26283625Sdim// And the following points are not: 27283625Sdim// for (int i = 0; i < 10; ++i) { 28283625Sdim// Save 29283625Sdim// ... 30283625Sdim// } 31283625Sdim// for (int i = 0; i < 10; ++i) { 32283625Sdim// ... 33283625Sdim// Restore 34283625Sdim// } 35283625Sdim// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore. 36283625Sdim// 37283625Sdim// This pass also ensures that the safe points are 3) cheaper than the regular 38283625Sdim// entry and exits blocks. 39283625Sdim// 40283625Sdim// Property #1 is ensured via the use of MachineDominatorTree and 41283625Sdim// MachinePostDominatorTree. 42283625Sdim// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both 43283625Sdim// points must be in the same loop. 44283625Sdim// Property #3 is ensured via the MachineBlockFrequencyInfo. 45283625Sdim// 46296417Sdim// If this pass found points matching all these properties, then 47296417Sdim// MachineFrameInfo is updated with this information. 48327952Sdim// 49283625Sdim//===----------------------------------------------------------------------===// 50327952Sdim 51296417Sdim#include "llvm/ADT/BitVector.h" 52296417Sdim#include "llvm/ADT/PostOrderIterator.h" 53296417Sdim#include "llvm/ADT/SetVector.h" 54327952Sdim#include "llvm/ADT/SmallVector.h" 55283625Sdim#include "llvm/ADT/Statistic.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" 65283625Sdim#include "llvm/CodeGen/MachinePostDominators.h" 66283625Sdim#include "llvm/CodeGen/RegisterClassInfo.h" 67296417Sdim#include "llvm/CodeGen/RegisterScavenging.h" 68327952Sdim#include "llvm/CodeGen/TargetFrameLowering.h" 69327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 70327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 71327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 72327952Sdim#include "llvm/IR/Attributes.h" 73327952Sdim#include "llvm/IR/Function.h" 74296417Sdim#include "llvm/MC/MCAsmInfo.h" 75327952Sdim#include "llvm/Pass.h" 76327952Sdim#include "llvm/Support/CommandLine.h" 77283625Sdim#include "llvm/Support/Debug.h" 78327952Sdim#include "llvm/Support/ErrorHandling.h" 79327952Sdim#include "llvm/Support/raw_ostream.h" 80296417Sdim#include "llvm/Target/TargetMachine.h" 81327952Sdim#include <cassert> 82327952Sdim#include <cstdint> 83327952Sdim#include <memory> 84283625Sdim 85327952Sdimusing namespace llvm; 86327952Sdim 87283625Sdim#define DEBUG_TYPE "shrink-wrap" 88283625Sdim 89283625SdimSTATISTIC(NumFunc, "Number of functions"); 90283625SdimSTATISTIC(NumCandidates, "Number of shrink-wrapping candidates"); 91283625SdimSTATISTIC(NumCandidatesDropped, 92283625Sdim "Number of shrink-wrapping candidates dropped because of frequency"); 93283625Sdim 94296417Sdimstatic cl::opt<cl::boolOrDefault> 95327952SdimEnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, 96327952Sdim cl::desc("enable the shrink-wrapping pass")); 97296417Sdim 98283625Sdimnamespace { 99327952Sdim 100283625Sdim/// \brief Class to determine where the safe point to insert the 101283625Sdim/// prologue and epilogue are. 102283625Sdim/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the 103283625Sdim/// shrink-wrapping term for prologue/epilogue placement, this pass 104283625Sdim/// does not rely on expensive data-flow analysis. Instead we use the 105283625Sdim/// dominance properties and loop information to decide which point 106283625Sdim/// are safe for such insertion. 107283625Sdimclass ShrinkWrap : public MachineFunctionPass { 108283625Sdim /// Hold callee-saved information. 109283625Sdim RegisterClassInfo RCI; 110283625Sdim MachineDominatorTree *MDT; 111283625Sdim MachinePostDominatorTree *MPDT; 112327952Sdim 113283625Sdim /// Current safe point found for the prologue. 114283625Sdim /// The prologue will be inserted before the first instruction 115283625Sdim /// in this basic block. 116283625Sdim MachineBasicBlock *Save; 117327952Sdim 118283625Sdim /// Current safe point found for the epilogue. 119283625Sdim /// The epilogue will be inserted before the first terminator instruction 120283625Sdim /// in this basic block. 121283625Sdim MachineBasicBlock *Restore; 122327952Sdim 123283625Sdim /// Hold the information of the basic block frequency. 124283625Sdim /// Use to check the profitability of the new points. 125283625Sdim MachineBlockFrequencyInfo *MBFI; 126327952Sdim 127283625Sdim /// Hold the loop information. Used to determine if Save and Restore 128283625Sdim /// are in the same loop. 129283625Sdim MachineLoopInfo *MLI; 130327952Sdim 131283625Sdim /// Frequency of the Entry block. 132283625Sdim uint64_t EntryFreq; 133327952Sdim 134283625Sdim /// Current opcode for frame setup. 135283625Sdim unsigned FrameSetupOpcode; 136327952Sdim 137283625Sdim /// Current opcode for frame destroy. 138283625Sdim unsigned FrameDestroyOpcode; 139327952Sdim 140283625Sdim /// Entry block. 141283625Sdim const MachineBasicBlock *Entry; 142327952Sdim 143327952Sdim using SetOfRegs = SmallSetVector<unsigned, 16>; 144327952Sdim 145296417Sdim /// Registers that need to be saved for the current function. 146296417Sdim mutable SetOfRegs CurrentCSRs; 147327952Sdim 148296417Sdim /// Current MachineFunction. 149296417Sdim MachineFunction *MachineFunc; 150283625Sdim 151283625Sdim /// \brief Check if \p MI uses or defines a callee-saved register or 152283625Sdim /// a frame index. If this is the case, this means \p MI must happen 153283625Sdim /// after Save and before Restore. 154296417Sdim bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const; 155283625Sdim 156296417Sdim const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const { 157296417Sdim if (CurrentCSRs.empty()) { 158296417Sdim BitVector SavedRegs; 159296417Sdim const TargetFrameLowering *TFI = 160296417Sdim MachineFunc->getSubtarget().getFrameLowering(); 161296417Sdim 162296417Sdim TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS); 163296417Sdim 164296417Sdim for (int Reg = SavedRegs.find_first(); Reg != -1; 165296417Sdim Reg = SavedRegs.find_next(Reg)) 166296417Sdim CurrentCSRs.insert((unsigned)Reg); 167296417Sdim } 168296417Sdim return CurrentCSRs; 169296417Sdim } 170296417Sdim 171283625Sdim /// \brief Update the Save and Restore points such that \p MBB is in 172283625Sdim /// the region that is dominated by Save and post-dominated by Restore 173283625Sdim /// and Save and Restore still match the safe point definition. 174283625Sdim /// Such point may not exist and Save and/or Restore may be null after 175283625Sdim /// this call. 176296417Sdim void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS); 177283625Sdim 178283625Sdim /// \brief Initialize the pass for \p MF. 179283625Sdim void init(MachineFunction &MF) { 180283625Sdim RCI.runOnMachineFunction(MF); 181283625Sdim MDT = &getAnalysis<MachineDominatorTree>(); 182283625Sdim MPDT = &getAnalysis<MachinePostDominatorTree>(); 183283625Sdim Save = nullptr; 184283625Sdim Restore = nullptr; 185283625Sdim MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 186283625Sdim MLI = &getAnalysis<MachineLoopInfo>(); 187283625Sdim EntryFreq = MBFI->getEntryFreq(); 188283625Sdim const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); 189283625Sdim FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 190283625Sdim FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 191283625Sdim Entry = &MF.front(); 192296417Sdim CurrentCSRs.clear(); 193296417Sdim MachineFunc = &MF; 194283625Sdim 195283625Sdim ++NumFunc; 196283625Sdim } 197283625Sdim 198283625Sdim /// Check whether or not Save and Restore points are still interesting for 199283625Sdim /// shrink-wrapping. 200283625Sdim bool ArePointsInteresting() const { return Save != Entry && Save && Restore; } 201283625Sdim 202296417Sdim /// \brief Check if shrink wrapping is enabled for this target and function. 203296417Sdim static bool isShrinkWrapEnabled(const MachineFunction &MF); 204296417Sdim 205283625Sdimpublic: 206283625Sdim static char ID; 207283625Sdim 208283625Sdim ShrinkWrap() : MachineFunctionPass(ID) { 209283625Sdim initializeShrinkWrapPass(*PassRegistry::getPassRegistry()); 210283625Sdim } 211283625Sdim 212283625Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 213283625Sdim AU.setPreservesAll(); 214283625Sdim AU.addRequired<MachineBlockFrequencyInfo>(); 215283625Sdim AU.addRequired<MachineDominatorTree>(); 216283625Sdim AU.addRequired<MachinePostDominatorTree>(); 217283625Sdim AU.addRequired<MachineLoopInfo>(); 218283625Sdim MachineFunctionPass::getAnalysisUsage(AU); 219283625Sdim } 220283625Sdim 221314564Sdim StringRef getPassName() const override { return "Shrink Wrapping analysis"; } 222283625Sdim 223283625Sdim /// \brief Perform the shrink-wrapping analysis and update 224283625Sdim /// the MachineFrameInfo attached to \p MF with the results. 225283625Sdim bool runOnMachineFunction(MachineFunction &MF) override; 226283625Sdim}; 227283625Sdim 228327952Sdim} // end anonymous namespace 229327952Sdim 230283625Sdimchar ShrinkWrap::ID = 0; 231327952Sdim 232283625Sdimchar &llvm::ShrinkWrapID = ShrinkWrap::ID; 233283625Sdim 234321369SdimINITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) 235283625SdimINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 236283625SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 237283625SdimINITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 238283625SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 239321369SdimINITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) 240283625Sdim 241296417Sdimbool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI, 242296417Sdim RegScavenger *RS) const { 243327952Sdim // Ignore DBG_VALUE and other meta instructions that must not affect codegen. 244327952Sdim if (MI.isMetaInstruction()) 245327952Sdim return false; 246327952Sdim 247283625Sdim if (MI.getOpcode() == FrameSetupOpcode || 248283625Sdim MI.getOpcode() == FrameDestroyOpcode) { 249283625Sdim DEBUG(dbgs() << "Frame instruction: " << MI << '\n'); 250283625Sdim return true; 251283625Sdim } 252283625Sdim for (const MachineOperand &MO : MI.operands()) { 253296417Sdim bool UseOrDefCSR = false; 254283625Sdim if (MO.isReg()) { 255283625Sdim unsigned PhysReg = MO.getReg(); 256283625Sdim if (!PhysReg) 257283625Sdim continue; 258283625Sdim assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 259283625Sdim "Unallocated register?!"); 260296417Sdim UseOrDefCSR = RCI.getLastCalleeSavedAlias(PhysReg); 261296417Sdim } else if (MO.isRegMask()) { 262296417Sdim // Check if this regmask clobbers any of the CSRs. 263296417Sdim for (unsigned Reg : getCurrentCSRs(RS)) { 264296417Sdim if (MO.clobbersPhysReg(Reg)) { 265296417Sdim UseOrDefCSR = true; 266296417Sdim break; 267296417Sdim } 268296417Sdim } 269283625Sdim } 270296417Sdim if (UseOrDefCSR || MO.isFI()) { 271296417Sdim DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI(" 272296417Sdim << MO.isFI() << "): " << MI << '\n'); 273283625Sdim return true; 274283625Sdim } 275283625Sdim } 276283625Sdim return false; 277283625Sdim} 278283625Sdim 279283625Sdim/// \brief Helper function to find the immediate (post) dominator. 280283625Sdimtemplate <typename ListOfBBs, typename DominanceAnalysis> 281314564Sdimstatic MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, 282314564Sdim DominanceAnalysis &Dom) { 283283625Sdim MachineBasicBlock *IDom = &Block; 284283625Sdim for (MachineBasicBlock *BB : BBs) { 285283625Sdim IDom = Dom.findNearestCommonDominator(IDom, BB); 286283625Sdim if (!IDom) 287283625Sdim break; 288283625Sdim } 289296417Sdim if (IDom == &Block) 290296417Sdim return nullptr; 291283625Sdim return IDom; 292283625Sdim} 293283625Sdim 294296417Sdimvoid ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB, 295296417Sdim RegScavenger *RS) { 296283625Sdim // Get rid of the easy cases first. 297283625Sdim if (!Save) 298283625Sdim Save = &MBB; 299283625Sdim else 300283625Sdim Save = MDT->findNearestCommonDominator(Save, &MBB); 301283625Sdim 302283625Sdim if (!Save) { 303283625Sdim DEBUG(dbgs() << "Found a block that is not reachable from Entry\n"); 304283625Sdim return; 305283625Sdim } 306283625Sdim 307283625Sdim if (!Restore) 308283625Sdim Restore = &MBB; 309321369Sdim else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it 310321369Sdim // means the block never returns. If that's the 311321369Sdim // case, we don't want to call 312321369Sdim // `findNearestCommonDominator`, which will 313321369Sdim // return `Restore`. 314321369Sdim Restore = MPDT->findNearestCommonDominator(Restore, &MBB); 315283625Sdim else 316321369Sdim Restore = nullptr; // Abort, we can't find a restore point in this case. 317283625Sdim 318283625Sdim // Make sure we would be able to insert the restore code before the 319283625Sdim // terminator. 320283625Sdim if (Restore == &MBB) { 321283625Sdim for (const MachineInstr &Terminator : MBB.terminators()) { 322296417Sdim if (!useOrDefCSROrFI(Terminator, RS)) 323283625Sdim continue; 324283625Sdim // One of the terminator needs to happen before the restore point. 325283625Sdim if (MBB.succ_empty()) { 326321369Sdim Restore = nullptr; // Abort, we can't find a restore point in this case. 327283625Sdim break; 328283625Sdim } 329283625Sdim // Look for a restore point that post-dominates all the successors. 330283625Sdim // The immediate post-dominator is what we are looking for. 331283625Sdim Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 332283625Sdim break; 333283625Sdim } 334283625Sdim } 335283625Sdim 336283625Sdim if (!Restore) { 337283625Sdim DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n"); 338283625Sdim return; 339283625Sdim } 340283625Sdim 341283625Sdim // Make sure Save and Restore are suitable for shrink-wrapping: 342283625Sdim // 1. all path from Save needs to lead to Restore before exiting. 343283625Sdim // 2. all path to Restore needs to go through Save from Entry. 344283625Sdim // We achieve that by making sure that: 345283625Sdim // A. Save dominates Restore. 346283625Sdim // B. Restore post-dominates Save. 347283625Sdim // C. Save and Restore are in the same loop. 348283625Sdim bool SaveDominatesRestore = false; 349283625Sdim bool RestorePostDominatesSave = false; 350283625Sdim while (Save && Restore && 351283625Sdim (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) || 352283625Sdim !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) || 353296417Sdim // Post-dominance is not enough in loops to ensure that all uses/defs 354296417Sdim // are after the prologue and before the epilogue at runtime. 355296417Sdim // E.g., 356296417Sdim // while(1) { 357296417Sdim // Save 358296417Sdim // Restore 359296417Sdim // if (...) 360296417Sdim // break; 361296417Sdim // use/def CSRs 362296417Sdim // } 363296417Sdim // All the uses/defs of CSRs are dominated by Save and post-dominated 364296417Sdim // by Restore. However, the CSRs uses are still reachable after 365296417Sdim // Restore and before Save are executed. 366296417Sdim // 367296417Sdim // For now, just push the restore/save points outside of loops. 368296417Sdim // FIXME: Refine the criteria to still find interesting cases 369296417Sdim // for loops. 370296417Sdim MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 371283625Sdim // Fix (A). 372283625Sdim if (!SaveDominatesRestore) { 373283625Sdim Save = MDT->findNearestCommonDominator(Save, Restore); 374283625Sdim continue; 375283625Sdim } 376283625Sdim // Fix (B). 377283625Sdim if (!RestorePostDominatesSave) 378283625Sdim Restore = MPDT->findNearestCommonDominator(Restore, Save); 379283625Sdim 380283625Sdim // Fix (C). 381296417Sdim if (Save && Restore && 382296417Sdim (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 383296417Sdim if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) { 384296417Sdim // Push Save outside of this loop if immediate dominator is different 385296417Sdim // from save block. If immediate dominator is not different, bail out. 386283625Sdim Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 387296417Sdim if (!Save) 388296417Sdim break; 389296417Sdim } else { 390296417Sdim // If the loop does not exit, there is no point in looking 391296417Sdim // for a post-dominator outside the loop. 392296417Sdim SmallVector<MachineBasicBlock*, 4> ExitBlocks; 393296417Sdim MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks); 394283625Sdim // Push Restore outside of this loop. 395296417Sdim // Look for the immediate post-dominator of the loop exits. 396296417Sdim MachineBasicBlock *IPdom = Restore; 397296417Sdim for (MachineBasicBlock *LoopExitBB: ExitBlocks) { 398296417Sdim IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT); 399296417Sdim if (!IPdom) 400296417Sdim break; 401296417Sdim } 402296417Sdim // If the immediate post-dominator is not in a less nested loop, 403296417Sdim // then we are stuck in a program with an infinite loop. 404296417Sdim // In that case, we will not find a safe point, hence, bail out. 405296417Sdim if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)) 406296417Sdim Restore = IPdom; 407296417Sdim else { 408296417Sdim Restore = nullptr; 409296417Sdim break; 410296417Sdim } 411296417Sdim } 412283625Sdim } 413283625Sdim } 414283625Sdim} 415283625Sdim 416296417Sdim/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI. 417296417Sdim/// I.e., check if it exists a loop that contains SrcBB and where DestBB is the 418296417Sdim/// loop header. 419296417Sdimstatic bool isProperBackedge(const MachineLoopInfo &MLI, 420296417Sdim const MachineBasicBlock *SrcBB, 421296417Sdim const MachineBasicBlock *DestBB) { 422296417Sdim for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop; 423296417Sdim Loop = Loop->getParentLoop()) { 424296417Sdim if (Loop->getHeader() == DestBB) 425296417Sdim return true; 426296417Sdim } 427296417Sdim return false; 428296417Sdim} 429296417Sdim 430296417Sdim/// Check if the CFG of \p MF is irreducible. 431296417Sdimstatic bool isIrreducibleCFG(const MachineFunction &MF, 432296417Sdim const MachineLoopInfo &MLI) { 433296417Sdim const MachineBasicBlock *Entry = &*MF.begin(); 434296417Sdim ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry); 435296417Sdim BitVector VisitedBB(MF.getNumBlockIDs()); 436296417Sdim for (const MachineBasicBlock *MBB : RPOT) { 437296417Sdim VisitedBB.set(MBB->getNumber()); 438296417Sdim for (const MachineBasicBlock *SuccBB : MBB->successors()) { 439296417Sdim if (!VisitedBB.test(SuccBB->getNumber())) 440296417Sdim continue; 441296417Sdim // We already visited SuccBB, thus MBB->SuccBB must be a backedge. 442296417Sdim // Check that the head matches what we have in the loop information. 443296417Sdim // Otherwise, we have an irreducible graph. 444296417Sdim if (!isProperBackedge(MLI, MBB, SuccBB)) 445296417Sdim return true; 446296417Sdim } 447296417Sdim } 448296417Sdim return false; 449296417Sdim} 450296417Sdim 451283625Sdimbool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) { 452327952Sdim if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF)) 453283625Sdim return false; 454296417Sdim 455283625Sdim DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 456283625Sdim 457283625Sdim init(MF); 458283625Sdim 459296417Sdim if (isIrreducibleCFG(MF, *MLI)) { 460296417Sdim // If MF is irreducible, a block may be in a loop without 461296417Sdim // MachineLoopInfo reporting it. I.e., we may use the 462296417Sdim // post-dominance property in loops, which lead to incorrect 463296417Sdim // results. Moreover, we may miss that the prologue and 464296417Sdim // epilogue are not in the same loop, leading to unbalanced 465296417Sdim // construction/deconstruction of the stack frame. 466296417Sdim DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n"); 467296417Sdim return false; 468296417Sdim } 469296417Sdim 470296417Sdim const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 471296417Sdim std::unique_ptr<RegScavenger> RS( 472296417Sdim TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr); 473296417Sdim 474283625Sdim for (MachineBasicBlock &MBB : MF) { 475283625Sdim DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName() 476283625Sdim << '\n'); 477283625Sdim 478296417Sdim if (MBB.isEHFuncletEntry()) { 479296417Sdim DEBUG(dbgs() << "EH Funclets are not supported yet.\n"); 480296417Sdim return false; 481296417Sdim } 482296417Sdim 483283625Sdim for (const MachineInstr &MI : MBB) { 484296417Sdim if (!useOrDefCSROrFI(MI, RS.get())) 485283625Sdim continue; 486283625Sdim // Save (resp. restore) point must dominate (resp. post dominate) 487283625Sdim // MI. Look for the proper basic block for those. 488296417Sdim updateSaveRestorePoints(MBB, RS.get()); 489283625Sdim // If we are at a point where we cannot improve the placement of 490283625Sdim // save/restore instructions, just give up. 491283625Sdim if (!ArePointsInteresting()) { 492283625Sdim DEBUG(dbgs() << "No Shrink wrap candidate found\n"); 493283625Sdim return false; 494283625Sdim } 495283625Sdim // No need to look for other instructions, this basic block 496283625Sdim // will already be part of the handled region. 497283625Sdim break; 498283625Sdim } 499283625Sdim } 500283625Sdim if (!ArePointsInteresting()) { 501283625Sdim // If the points are not interesting at this point, then they must be null 502283625Sdim // because it means we did not encounter any frame/CSR related code. 503283625Sdim // Otherwise, we would have returned from the previous loop. 504283625Sdim assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!"); 505283625Sdim DEBUG(dbgs() << "Nothing to shrink-wrap\n"); 506283625Sdim return false; 507283625Sdim } 508283625Sdim 509283625Sdim DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq 510283625Sdim << '\n'); 511283625Sdim 512283625Sdim const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 513283625Sdim do { 514283625Sdim DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: " 515283625Sdim << Save->getNumber() << ' ' << Save->getName() << ' ' 516283625Sdim << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: " 517283625Sdim << Restore->getNumber() << ' ' << Restore->getName() << ' ' 518283625Sdim << MBFI->getBlockFreq(Restore).getFrequency() << '\n'); 519283625Sdim 520283625Sdim bool IsSaveCheap, TargetCanUseSaveAsPrologue = false; 521283625Sdim if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) && 522283625Sdim EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) && 523283625Sdim ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) && 524283625Sdim TFI->canUseAsEpilogue(*Restore))) 525283625Sdim break; 526283625Sdim DEBUG(dbgs() << "New points are too expensive or invalid for the target\n"); 527283625Sdim MachineBasicBlock *NewBB; 528283625Sdim if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) { 529283625Sdim Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 530283625Sdim if (!Save) 531283625Sdim break; 532283625Sdim NewBB = Save; 533283625Sdim } else { 534283625Sdim // Restore is expensive. 535283625Sdim Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 536283625Sdim if (!Restore) 537283625Sdim break; 538283625Sdim NewBB = Restore; 539283625Sdim } 540296417Sdim updateSaveRestorePoints(*NewBB, RS.get()); 541283625Sdim } while (Save && Restore); 542283625Sdim 543283625Sdim if (!ArePointsInteresting()) { 544283625Sdim ++NumCandidatesDropped; 545283625Sdim return false; 546283625Sdim } 547283625Sdim 548283625Sdim DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber() 549283625Sdim << ' ' << Save->getName() << "\nRestore: " 550283625Sdim << Restore->getNumber() << ' ' << Restore->getName() << '\n'); 551283625Sdim 552314564Sdim MachineFrameInfo &MFI = MF.getFrameInfo(); 553314564Sdim MFI.setSavePoint(Save); 554314564Sdim MFI.setRestorePoint(Restore); 555283625Sdim ++NumCandidates; 556283625Sdim return false; 557283625Sdim} 558296417Sdim 559296417Sdimbool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) { 560296417Sdim const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 561296417Sdim 562296417Sdim switch (EnableShrinkWrapOpt) { 563296417Sdim case cl::BOU_UNSET: 564296417Sdim return TFI->enableShrinkWrapping(MF) && 565327952Sdim // Windows with CFI has some limitations that make it impossible 566327952Sdim // to use shrink-wrapping. 567327952Sdim !MF.getTarget().getMCAsmInfo()->usesWindowsCFI() && 568327952Sdim // Sanitizers look at the value of the stack at the location 569327952Sdim // of the crash. Since a crash can happen anywhere, the 570327952Sdim // frame must be lowered before anything else happen for the 571327952Sdim // sanitizers to be able to get a correct stack frame. 572327952Sdim !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) || 573327952Sdim MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) || 574327952Sdim MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) || 575327952Sdim MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress)); 576296417Sdim // If EnableShrinkWrap is set, it takes precedence on whatever the 577296417Sdim // target sets. The rational is that we assume we want to test 578296417Sdim // something related to shrink-wrapping. 579296417Sdim case cl::BOU_TRUE: 580296417Sdim return true; 581296417Sdim case cl::BOU_FALSE: 582296417Sdim return false; 583296417Sdim } 584296417Sdim llvm_unreachable("Invalid shrink-wrapping state"); 585296417Sdim} 586