LCOV - code coverage report
Current view: top level - lib/CodeGen - ShrinkWrap.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 151 153 98.7 %
Date: 2018-02-23 15:42:53 Functions: 19 19 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This pass looks for safe point where the prologue and epilogue can be
      11             : // inserted.
      12             : // The safe point for the prologue (resp. epilogue) is called Save
      13             : // (resp. Restore).
      14             : // A point is safe for prologue (resp. epilogue) if and only if
      15             : // it 1) dominates (resp. post-dominates) all the frame related operations and
      16             : // between 2) two executions of the Save (resp. Restore) point there is an
      17             : // execution of the Restore (resp. Save) point.
      18             : //
      19             : // For instance, the following points are safe:
      20             : // for (int i = 0; i < 10; ++i) {
      21             : //   Save
      22             : //   ...
      23             : //   Restore
      24             : // }
      25             : // Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
      26             : // And the following points are not:
      27             : // for (int i = 0; i < 10; ++i) {
      28             : //   Save
      29             : //   ...
      30             : // }
      31             : // for (int i = 0; i < 10; ++i) {
      32             : //   ...
      33             : //   Restore
      34             : // }
      35             : // Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
      36             : //
      37             : // This pass also ensures that the safe points are 3) cheaper than the regular
      38             : // entry and exits blocks.
      39             : //
      40             : // Property #1 is ensured via the use of MachineDominatorTree and
      41             : // MachinePostDominatorTree.
      42             : // Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
      43             : // points must be in the same loop.
      44             : // Property #3 is ensured via the MachineBlockFrequencyInfo.
      45             : //
      46             : // If this pass found points matching all these properties, then
      47             : // MachineFrameInfo is updated with this information.
      48             : //
      49             : //===----------------------------------------------------------------------===//
      50             : 
      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/CodeGen/MachineBasicBlock.h"
      57             : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
      58             : #include "llvm/CodeGen/MachineDominators.h"
      59             : #include "llvm/CodeGen/MachineFrameInfo.h"
      60             : #include "llvm/CodeGen/MachineFunction.h"
      61             : #include "llvm/CodeGen/MachineFunctionPass.h"
      62             : #include "llvm/CodeGen/MachineInstr.h"
      63             : #include "llvm/CodeGen/MachineLoopInfo.h"
      64             : #include "llvm/CodeGen/MachineOperand.h"
      65             : #include "llvm/CodeGen/MachinePostDominators.h"
      66             : #include "llvm/CodeGen/RegisterClassInfo.h"
      67             : #include "llvm/CodeGen/RegisterScavenging.h"
      68             : #include "llvm/CodeGen/TargetFrameLowering.h"
      69             : #include "llvm/CodeGen/TargetInstrInfo.h"
      70             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      71             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      72             : #include "llvm/IR/Attributes.h"
      73             : #include "llvm/IR/Function.h"
      74             : #include "llvm/MC/MCAsmInfo.h"
      75             : #include "llvm/Pass.h"
      76             : #include "llvm/Support/CommandLine.h"
      77             : #include "llvm/Support/Debug.h"
      78             : #include "llvm/Support/ErrorHandling.h"
      79             : #include "llvm/Support/raw_ostream.h"
      80             : #include "llvm/Target/TargetMachine.h"
      81             : #include <cassert>
      82             : #include <cstdint>
      83             : #include <memory>
      84             : 
      85             : using namespace llvm;
      86             : 
      87             : #define DEBUG_TYPE "shrink-wrap"
      88             : 
      89             : STATISTIC(NumFunc, "Number of functions");
      90             : STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
      91             : STATISTIC(NumCandidatesDropped,
      92             :           "Number of shrink-wrapping candidates dropped because of frequency");
      93             : 
      94             : static cl::opt<cl::boolOrDefault>
      95       81686 : EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
      96       81686 :                     cl::desc("enable the shrink-wrapping pass"));
      97             : 
      98             : namespace {
      99             : 
     100             : /// \brief Class to determine where the safe point to insert the
     101             : /// prologue and epilogue are.
     102             : /// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
     103             : /// shrink-wrapping term for prologue/epilogue placement, this pass
     104             : /// does not rely on expensive data-flow analysis. Instead we use the
     105             : /// dominance properties and loop information to decide which point
     106             : /// are safe for such insertion.
     107       51906 : class ShrinkWrap : public MachineFunctionPass {
     108             :   /// Hold callee-saved information.
     109             :   RegisterClassInfo RCI;
     110             :   MachineDominatorTree *MDT;
     111             :   MachinePostDominatorTree *MPDT;
     112             : 
     113             :   /// Current safe point found for the prologue.
     114             :   /// The prologue will be inserted before the first instruction
     115             :   /// in this basic block.
     116             :   MachineBasicBlock *Save;
     117             : 
     118             :   /// Current safe point found for the epilogue.
     119             :   /// The epilogue will be inserted before the first terminator instruction
     120             :   /// in this basic block.
     121             :   MachineBasicBlock *Restore;
     122             : 
     123             :   /// Hold the information of the basic block frequency.
     124             :   /// Use to check the profitability of the new points.
     125             :   MachineBlockFrequencyInfo *MBFI;
     126             : 
     127             :   /// Hold the loop information. Used to determine if Save and Restore
     128             :   /// are in the same loop.
     129             :   MachineLoopInfo *MLI;
     130             : 
     131             :   /// Frequency of the Entry block.
     132             :   uint64_t EntryFreq;
     133             : 
     134             :   /// Current opcode for frame setup.
     135             :   unsigned FrameSetupOpcode;
     136             : 
     137             :   /// Current opcode for frame destroy.
     138             :   unsigned FrameDestroyOpcode;
     139             : 
     140             :   /// Entry block.
     141             :   const MachineBasicBlock *Entry;
     142             : 
     143             :   using SetOfRegs = SmallSetVector<unsigned, 16>;
     144             : 
     145             :   /// Registers that need to be saved for the current function.
     146             :   mutable SetOfRegs CurrentCSRs;
     147             : 
     148             :   /// Current MachineFunction.
     149             :   MachineFunction *MachineFunc;
     150             : 
     151             :   /// \brief Check if \p MI uses or defines a callee-saved register or
     152             :   /// a frame index. If this is the case, this means \p MI must happen
     153             :   /// after Save and before Restore.
     154             :   bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const;
     155             : 
     156        1220 :   const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {
     157        1220 :     if (CurrentCSRs.empty()) {
     158             :       BitVector SavedRegs;
     159             :       const TargetFrameLowering *TFI =
     160        1218 :           MachineFunc->getSubtarget().getFrameLowering();
     161             : 
     162        1218 :       TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS);
     163             : 
     164        2104 :       for (int Reg = SavedRegs.find_first(); Reg != -1;
     165             :            Reg = SavedRegs.find_next(Reg))
     166         443 :         CurrentCSRs.insert((unsigned)Reg);
     167             :     }
     168        1220 :     return CurrentCSRs;
     169             :   }
     170             : 
     171             :   /// \brief Update the Save and Restore points such that \p MBB is in
     172             :   /// the region that is dominated by Save and post-dominated by Restore
     173             :   /// and Save and Restore still match the safe point definition.
     174             :   /// Such point may not exist and Save and/or Restore may be null after
     175             :   /// this call.
     176             :   void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
     177             : 
     178             :   /// \brief Initialize the pass for \p MF.
     179       54554 :   void init(MachineFunction &MF) {
     180       54554 :     RCI.runOnMachineFunction(MF);
     181       54554 :     MDT = &getAnalysis<MachineDominatorTree>();
     182       54554 :     MPDT = &getAnalysis<MachinePostDominatorTree>();
     183       54554 :     Save = nullptr;
     184       54554 :     Restore = nullptr;
     185       54554 :     MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
     186       54554 :     MLI = &getAnalysis<MachineLoopInfo>();
     187       54554 :     EntryFreq = MBFI->getEntryFreq();
     188       54554 :     const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
     189       54554 :     FrameSetupOpcode = TII.getCallFrameSetupOpcode();
     190       54554 :     FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
     191       54554 :     Entry = &MF.front();
     192             :     CurrentCSRs.clear();
     193       54554 :     MachineFunc = &MF;
     194             : 
     195             :     ++NumFunc;
     196       54554 :   }
     197             : 
     198             :   /// Check whether or not Save and Restore points are still interesting for
     199             :   /// shrink-wrapping.
     200       55719 :   bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
     201             : 
     202             :   /// \brief Check if shrink wrapping is enabled for this target and function.
     203             :   static bool isShrinkWrapEnabled(const MachineFunction &MF);
     204             : 
     205             : public:
     206             :   static char ID;
     207             : 
     208       17403 :   ShrinkWrap() : MachineFunctionPass(ID) {
     209       17403 :     initializeShrinkWrapPass(*PassRegistry::getPassRegistry());
     210       17403 :   }
     211             : 
     212       17296 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     213             :     AU.setPreservesAll();
     214             :     AU.addRequired<MachineBlockFrequencyInfo>();
     215             :     AU.addRequired<MachineDominatorTree>();
     216             :     AU.addRequired<MachinePostDominatorTree>();
     217             :     AU.addRequired<MachineLoopInfo>();
     218       17296 :     MachineFunctionPass::getAnalysisUsage(AU);
     219       17296 :   }
     220             : 
     221       17317 :   StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
     222             : 
     223             :   /// \brief Perform the shrink-wrapping analysis and update
     224             :   /// the MachineFrameInfo attached to \p MF with the results.
     225             :   bool runOnMachineFunction(MachineFunction &MF) override;
     226             : };
     227             : 
     228             : } // end anonymous namespace
     229             : 
     230             : char ShrinkWrap::ID = 0;
     231             : 
     232             : char &llvm::ShrinkWrapID = ShrinkWrap::ID;
     233             : 
     234       22315 : INITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
     235       22315 : INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
     236       22315 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     237       22315 : INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
     238       22315 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     239      161262 : INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
     240             : 
     241      251985 : bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI,
     242             :                                  RegScavenger *RS) const {
     243      752251 :   if (MI.getOpcode() == FrameSetupOpcode ||
     244      248281 :       MI.getOpcode() == FrameDestroyOpcode) {
     245             :     DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
     246             :     return true;
     247             :   }
     248     1858243 :   for (const MachineOperand &MO : MI.operands()) {
     249             :     bool UseOrDefCSR = false;
     250      814972 :     if (MO.isReg()) {
     251             :       // Ignore instructions like DBG_VALUE which don't read/def the register.
     252      614186 :       if (!MO.isDef() && !MO.readsReg())
     253        2216 :         continue;
     254      609754 :       unsigned PhysReg = MO.getReg();
     255      695502 :       if (!PhysReg)
     256       85748 :         continue;
     257             :       assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
     258             :              "Unallocated register?!");
     259      524006 :       UseOrDefCSR = RCI.getLastCalleeSavedAlias(PhysReg);
     260      203002 :     } else if (MO.isRegMask()) {
     261             :       // Check if this regmask clobbers any of the CSRs.
     262        3030 :       for (unsigned Reg : getCurrentCSRs(RS)) {
     263         311 :         if (MO.clobbersPhysReg(Reg)) {
     264             :           UseOrDefCSR = true;
     265             :           break;
     266             :         }
     267             :       }
     268             :     }
     269             :     // Skip FrameIndex operands in DBG_VALUE instructions.
     270     1253764 :     if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
     271             :       DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
     272             :                    << MO.isFI() << "): " << MI << '\n');
     273             :       return true;
     274             :     }
     275             :   }
     276             :   return false;
     277             : }
     278             : 
     279             : /// \brief Helper function to find the immediate (post) dominator.
     280             : template <typename ListOfBBs, typename DominanceAnalysis>
     281         403 : static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
     282             :                                    DominanceAnalysis &Dom) {
     283             :   MachineBasicBlock *IDom = &Block;
     284        1211 :   for (MachineBasicBlock *BB : BBs) {
     285         456 :     IDom = Dom.findNearestCommonDominator(IDom, BB);
     286         811 :     if (!IDom)
     287             :       break;
     288             :   }
     289         403 :   if (IDom == &Block)
     290             :     return nullptr;
     291         397 :   return IDom;
     292             : }
     293             : 
     294       13597 : void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
     295             :                                          RegScavenger *RS) {
     296             :   // Get rid of the easy cases first.
     297       13597 :   if (!Save)
     298       13274 :     Save = &MBB;
     299             :   else
     300         646 :     Save = MDT->findNearestCommonDominator(Save, &MBB);
     301             : 
     302       13597 :   if (!Save) {
     303             :     DEBUG(dbgs() << "Found a block that is not reachable from Entry\n");
     304             :     return;
     305             :   }
     306             : 
     307       13597 :   if (!Restore)
     308       13274 :     Restore = &MBB;
     309         646 :   else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it
     310             :                                 // means the block never returns. If that's the
     311             :                                 // case, we don't want to call
     312             :                                 // `findNearestCommonDominator`, which will
     313             :                                 // return `Restore`.
     314         646 :     Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
     315             :   else
     316           0 :     Restore = nullptr; // Abort, we can't find a restore point in this case.
     317             : 
     318             :   // Make sure we would be able to insert the restore code before the
     319             :   // terminator.
     320       13597 :   if (Restore == &MBB) {
     321       40004 :     for (const MachineInstr &Terminator : MBB.terminators()) {
     322       13338 :       if (!useOrDefCSROrFI(Terminator, RS))
     323             :         continue;
     324             :       // One of the terminator needs to happen before the restore point.
     325         102 :       if (MBB.succ_empty()) {
     326          86 :         Restore = nullptr; // Abort, we can't find a restore point in this case.
     327          86 :         break;
     328             :       }
     329             :       // Look for a restore point that post-dominates all the successors.
     330             :       // The immediate post-dominator is what we are looking for.
     331          32 :       Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
     332          16 :       break;
     333             :     }
     334             :   }
     335             : 
     336       13597 :   if (!Restore) {
     337             :     DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n");
     338             :     return;
     339             :   }
     340             : 
     341             :   // Make sure Save and Restore are suitable for shrink-wrapping:
     342             :   // 1. all path from Save needs to lead to Restore before exiting.
     343             :   // 2. all path to Restore needs to go through Save from Entry.
     344             :   // We achieve that by making sure that:
     345             :   // A. Save dominates Restore.
     346             :   // B. Restore post-dominates Save.
     347             :   // C. Save and Restore are in the same loop.
     348             :   bool SaveDominatesRestore = false;
     349             :   bool RestorePostDominatesSave = false;
     350       41445 :   while (Save && Restore &&
     351       41401 :          (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||
     352       14140 :           !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||
     353             :           // Post-dominance is not enough in loops to ensure that all uses/defs
     354             :           // are after the prologue and before the epilogue at runtime.
     355             :           // E.g.,
     356             :           // while(1) {
     357             :           //  Save
     358             :           //  Restore
     359             :           //   if (...)
     360             :           //     break;
     361             :           //  use/def CSRs
     362             :           // }
     363             :           // All the uses/defs of CSRs are dominated by Save and post-dominated
     364             :           // by Restore. However, the CSRs uses are still reachable after
     365             :           // Restore and before Save are executed.
     366             :           //
     367             :           // For now, just push the restore/save points outside of loops.
     368             :           // FIXME: Refine the criteria to still find interesting cases
     369             :           // for loops.
     370       27284 :           MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
     371             :     // Fix (A).
     372         439 :     if (!SaveDominatesRestore) {
     373          44 :       Save = MDT->findNearestCommonDominator(Save, Restore);
     374          22 :       continue;
     375             :     }
     376             :     // Fix (B).
     377         395 :     if (!RestorePostDominatesSave)
     378           2 :       Restore = MPDT->findNearestCommonDominator(Restore, Save);
     379             : 
     380             :     // Fix (C).
     381         742 :     if (Save && Restore &&
     382         490 :         (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) {
     383        1182 :       if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) {
     384             :         // Push Save outside of this loop if immediate dominator is different
     385             :         // from save block. If immediate dominator is not different, bail out.
     386         342 :         Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
     387         171 :         if (!Save)
     388             :           break;
     389             :       } else {
     390             :         // If the loop does not exit, there is no point in looking
     391             :         // for a post-dominator outside the loop.
     392             :         SmallVector<MachineBasicBlock*, 4> ExitBlocks;
     393         446 :         MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks);
     394             :         // Push Restore outside of this loop.
     395             :         // Look for the immediate post-dominator of the loop exits.
     396         223 :         MachineBasicBlock *IPdom = Restore;
     397         631 :         for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
     398         424 :           IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);
     399         212 :           if (!IPdom)
     400             :             break;
     401             :         }
     402             :         // If the immediate post-dominator is not in a less nested loop,
     403             :         // then we are stuck in a program with an infinite loop.
     404             :         // In that case, we will not find a safe point, hence, bail out.
     405         653 :         if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore))
     406         198 :           Restore = IPdom;
     407             :         else {
     408          25 :           Restore = nullptr;
     409             :           break;
     410             :         }
     411             :       }
     412             :     }
     413             :   }
     414             : }
     415             : 
     416             : /// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI.
     417             : /// I.e., check if it exists a loop that contains SrcBB and where DestBB is the
     418             : /// loop header.
     419        2845 : static bool isProperBackedge(const MachineLoopInfo &MLI,
     420             :                              const MachineBasicBlock *SrcBB,
     421             :                              const MachineBasicBlock *DestBB) {
     422        2871 :   for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop;
     423             :        Loop = Loop->getParentLoop()) {
     424        2846 :     if (Loop->getHeader() == DestBB)
     425             :       return true;
     426             :   }
     427             :   return false;
     428             : }
     429             : 
     430             : /// Check if the CFG of \p MF is irreducible.
     431       54554 : static bool isIrreducibleCFG(const MachineFunction &MF,
     432             :                              const MachineLoopInfo &MLI) {
     433             :   const MachineBasicBlock *Entry = &*MF.begin();
     434             :   ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry);
     435       54554 :   BitVector VisitedBB(MF.getNumBlockIDs());
     436      130471 :   for (const MachineBasicBlock *MBB : RPOT) {
     437       75929 :     VisitedBB.set(MBB->getNumber());
     438      105897 :     for (const MachineBasicBlock *SuccBB : MBB->successors()) {
     439       59960 :       if (!VisitedBB.test(SuccBB->getNumber()))
     440       27135 :         continue;
     441             :       // We already visited SuccBB, thus MBB->SuccBB must be a backedge.
     442             :       // Check that the head matches what we have in the loop information.
     443             :       // Otherwise, we have an irreducible graph.
     444        2845 :       if (!isProperBackedge(MLI, MBB, SuccBB))
     445             :         return true;
     446             :     }
     447             :   }
     448             :   return false;
     449             : }
     450             : 
     451      159675 : bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
     452      319257 :   if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF))
     453             :     return false;
     454             : 
     455             :   DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
     456             : 
     457       54554 :   init(MF);
     458             : 
     459       54554 :   if (isIrreducibleCFG(MF, *MLI)) {
     460             :     // If MF is irreducible, a block may be in a loop without
     461             :     // MachineLoopInfo reporting it. I.e., we may use the
     462             :     // post-dominance property in loops, which lead to incorrect
     463             :     // results. Moreover, we may miss that the prologue and
     464             :     // epilogue are not in the same loop, leading to unbalanced
     465             :     // construction/deconstruction of the stack frame.
     466             :     DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n");
     467             :     return false;
     468             :   }
     469             : 
     470       54542 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     471             :   std::unique_ptr<RegScavenger> RS(
     472      109084 :       TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
     473             : 
     474      106273 :   for (MachineBasicBlock &MBB : MF) {
     475             :     DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName()
     476             :                  << '\n');
     477             : 
     478       64576 :     if (MBB.isEHFuncletEntry()) {
     479             :       DEBUG(dbgs() << "EH Funclets are not supported yet.\n");
     480             :       return false;
     481             :     }
     482             : 
     483      354204 :     for (const MachineInstr &MI : MBB) {
     484      238647 :       if (!useOrDefCSROrFI(MI, RS.get()))
     485             :         continue;
     486             :       // Save (resp. restore) point must dominate (resp. post dominate)
     487             :       // MI. Look for the proper basic block for those.
     488       13593 :       updateSaveRestorePoints(MBB, RS.get());
     489             :       // If we are at a point where we cannot improve the placement of
     490             :       // save/restore instructions, just give up.
     491             :       if (!ArePointsInteresting()) {
     492             :         DEBUG(dbgs() << "No Shrink wrap candidate found\n");
     493       12844 :         return false;
     494             :       }
     495             :       // No need to look for other instructions, this basic block
     496             :       // will already be part of the handled region.
     497             :       break;
     498             :     }
     499             :   }
     500             :   if (!ArePointsInteresting()) {
     501             :     // If the points are not interesting at this point, then they must be null
     502             :     // because it means we did not encounter any frame/CSR related code.
     503             :     // Otherwise, we would have returned from the previous loop.
     504             :     assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
     505             :     DEBUG(dbgs() << "Nothing to shrink-wrap\n");
     506             :     return false;
     507             :   }
     508             : 
     509             :   DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
     510             :                << '\n');
     511             : 
     512         429 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     513             :   do {
     514             :     DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
     515             :                  << Save->getNumber() << ' ' << Save->getName() << ' '
     516             :                  << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: "
     517             :                  << Restore->getNumber() << ' ' << Restore->getName() << ' '
     518             :                  << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
     519             : 
     520             :     bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
     521        1299 :     if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
     522        1299 :          EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) &&
     523         864 :         ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
     524         431 :          TFI->canUseAsEpilogue(*Restore)))
     525             :       break;
     526             :     DEBUG(dbgs() << "New points are too expensive or invalid for the target\n");
     527             :     MachineBasicBlock *NewBB;
     528           4 :     if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
     529           4 :       Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
     530           2 :       if (!Save)
     531             :         break;
     532             :       NewBB = Save;
     533             :     } else {
     534             :       // Restore is expensive.
     535           4 :       Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
     536           2 :       if (!Restore)
     537             :         break;
     538             :       NewBB = Restore;
     539             :     }
     540           4 :     updateSaveRestorePoints(*NewBB, RS.get());
     541           4 :   } while (Save && Restore);
     542             : 
     543             :   if (!ArePointsInteresting()) {
     544             :     ++NumCandidatesDropped;
     545             :     return false;
     546             :   }
     547             : 
     548             :   DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber()
     549             :                << ' ' << Save->getName() << "\nRestore: "
     550             :                << Restore->getNumber() << ' ' << Restore->getName() << '\n');
     551             : 
     552         426 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     553             :   MFI.setSavePoint(Save);
     554         426 :   MFI.setRestorePoint(Restore);
     555             :   ++NumCandidates;
     556         426 :   return false;
     557             : }
     558             : 
     559      159582 : bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) {
     560      159582 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     561             : 
     562      159582 :   switch (EnableShrinkWrapOpt) {
     563      159324 :   case cl::BOU_UNSET:
     564      159324 :     return TFI->enableShrinkWrapping(MF) &&
     565             :            // Windows with CFI has some limitations that make it impossible
     566             :            // to use shrink-wrapping.
     567      213770 :            !MF.getTarget().getMCAsmInfo()->usesWindowsCFI() &&
     568             :            // Sanitizers look at the value of the stack at the location
     569             :            // of the crash. Since a crash can happen anywhere, the
     570             :            // frame must be lowered before anything else happen for the
     571             :            // sanitizers to be able to get a correct stack frame.
     572      163310 :            !(MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress) ||
     573      108864 :              MF.getFunction().hasFnAttribute(Attribute::SanitizeThread) ||
     574       54432 :              MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory) ||
     575       54432 :              MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress));
     576             :   // If EnableShrinkWrap is set, it takes precedence on whatever the
     577             :   // target sets. The rational is that we assume we want to test
     578             :   // something related to shrink-wrapping.
     579             :   case cl::BOU_TRUE:
     580             :     return true;
     581         136 :   case cl::BOU_FALSE:
     582         136 :     return false;
     583             :   }
     584           0 :   llvm_unreachable("Invalid shrink-wrapping state");
     585      245058 : }

Generated by: LCOV version 1.13