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

          Line data    Source code
       1             : //===- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function ---===//
       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 is responsible for finalizing the functions frame layout, saving
      11             : // callee saved registers, and for emitting prolog & epilog code for the
      12             : // function.
      13             : //
      14             : // This pass must be run after register allocation.  After this pass is
      15             : // executed, it is illegal to construct MO_FrameIndex operands.
      16             : //
      17             : //===----------------------------------------------------------------------===//
      18             : 
      19             : #include "llvm/ADT/ArrayRef.h"
      20             : #include "llvm/ADT/BitVector.h"
      21             : #include "llvm/ADT/DepthFirstIterator.h"
      22             : #include "llvm/ADT/STLExtras.h"
      23             : #include "llvm/ADT/SetVector.h"
      24             : #include "llvm/ADT/SmallPtrSet.h"
      25             : #include "llvm/ADT/SmallSet.h"
      26             : #include "llvm/ADT/SmallVector.h"
      27             : #include "llvm/ADT/Statistic.h"
      28             : #include "llvm/Analysis/OptimizationRemarkEmitter.h"
      29             : #include "llvm/CodeGen/MachineBasicBlock.h"
      30             : #include "llvm/CodeGen/MachineDominators.h"
      31             : #include "llvm/CodeGen/MachineFrameInfo.h"
      32             : #include "llvm/CodeGen/MachineFunction.h"
      33             : #include "llvm/CodeGen/MachineFunctionPass.h"
      34             : #include "llvm/CodeGen/MachineInstr.h"
      35             : #include "llvm/CodeGen/MachineLoopInfo.h"
      36             : #include "llvm/CodeGen/MachineModuleInfo.h"
      37             : #include "llvm/CodeGen/MachineOperand.h"
      38             : #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
      39             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      40             : #include "llvm/CodeGen/RegisterScavenging.h"
      41             : #include "llvm/CodeGen/StackProtector.h"
      42             : #include "llvm/CodeGen/TargetFrameLowering.h"
      43             : #include "llvm/CodeGen/TargetInstrInfo.h"
      44             : #include "llvm/CodeGen/TargetOpcodes.h"
      45             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      46             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      47             : #include "llvm/CodeGen/WinEHFuncInfo.h"
      48             : #include "llvm/IR/Attributes.h"
      49             : #include "llvm/IR/CallingConv.h"
      50             : #include "llvm/IR/DebugInfoMetadata.h"
      51             : #include "llvm/IR/DiagnosticInfo.h"
      52             : #include "llvm/IR/Function.h"
      53             : #include "llvm/IR/InlineAsm.h"
      54             : #include "llvm/IR/LLVMContext.h"
      55             : #include "llvm/MC/MCRegisterInfo.h"
      56             : #include "llvm/Pass.h"
      57             : #include "llvm/Support/CodeGen.h"
      58             : #include "llvm/Support/CommandLine.h"
      59             : #include "llvm/Support/Debug.h"
      60             : #include "llvm/Support/ErrorHandling.h"
      61             : #include "llvm/Support/MathExtras.h"
      62             : #include "llvm/Support/raw_ostream.h"
      63             : #include "llvm/Target/TargetMachine.h"
      64             : #include "llvm/Target/TargetOptions.h"
      65             : #include <algorithm>
      66             : #include <cassert>
      67             : #include <cstdint>
      68             : #include <functional>
      69             : #include <limits>
      70             : #include <utility>
      71             : #include <vector>
      72             : 
      73             : using namespace llvm;
      74             : 
      75             : #define DEBUG_TYPE "prologepilog"
      76             : 
      77             : using MBBVector = SmallVector<MachineBasicBlock *, 4>;
      78             : 
      79             : namespace {
      80             : 
      81       55419 : class PEI : public MachineFunctionPass {
      82             : public:
      83             :   static char ID;
      84             : 
      85       37144 :   PEI() : MachineFunctionPass(ID) {
      86       18572 :     initializePEIPass(*PassRegistry::getPassRegistry());
      87       18572 :   }
      88             : 
      89             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
      90             : 
      91             :   /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
      92             :   /// frame indexes with appropriate references.
      93             :   bool runOnMachineFunction(MachineFunction &Fn) override;
      94             : 
      95             : private:
      96             :   RegScavenger *RS;
      97             : 
      98             :   // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
      99             :   // stack frame indexes.
     100             :   unsigned MinCSFrameIndex = std::numeric_limits<unsigned>::max();
     101             :   unsigned MaxCSFrameIndex = 0;
     102             : 
     103             :   // Save and Restore blocks of the current function. Typically there is a
     104             :   // single save block, unless Windows EH funclets are involved.
     105             :   MBBVector SaveBlocks;
     106             :   MBBVector RestoreBlocks;
     107             : 
     108             :   // Flag to control whether to use the register scavenger to resolve
     109             :   // frame index materialization registers. Set according to
     110             :   // TRI->requiresFrameIndexScavenging() for the current function.
     111             :   bool FrameIndexVirtualScavenging;
     112             : 
     113             :   // Flag to control whether the scavenger should be passed even though
     114             :   // FrameIndexVirtualScavenging is used.
     115             :   bool FrameIndexEliminationScavenging;
     116             : 
     117             :   // Emit remarks.
     118             :   MachineOptimizationRemarkEmitter *ORE = nullptr;
     119             : 
     120             :   void calculateCallFrameInfo(MachineFunction &Fn);
     121             :   void calculateSaveRestoreBlocks(MachineFunction &Fn);
     122             :   void spillCalleeSavedRegs(MachineFunction &MF);
     123             : 
     124             :   void calculateFrameObjectOffsets(MachineFunction &Fn);
     125             :   void replaceFrameIndices(MachineFunction &Fn);
     126             :   void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
     127             :                            int &SPAdj);
     128             :   void insertPrologEpilogCode(MachineFunction &Fn);
     129             : };
     130             : 
     131             : } // end anonymous namespace
     132             : 
     133             : char PEI::ID = 0;
     134             : 
     135             : char &llvm::PrologEpilogCodeInserterID = PEI::ID;
     136             : 
     137             : static cl::opt<unsigned>
     138      245058 : WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
     139       81686 :               cl::desc("Warn for stack size bigger than the given"
     140       81686 :                        " number"));
     141             : 
     142       22315 : INITIALIZE_PASS_BEGIN(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion", false,
     143             :                       false)
     144       22315 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     145       22315 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     146       22315 : INITIALIZE_PASS_DEPENDENCY(StackProtector)
     147       22315 : INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
     148      163600 : INITIALIZE_PASS_END(PEI, DEBUG_TYPE,
     149             :                     "Prologue/Epilogue Insertion & Frame Finalization", false,
     150             :                     false)
     151             : 
     152       18567 : MachineFunctionPass *llvm::createPrologEpilogInserterPass() {
     153       18567 :   return new PEI();
     154             : }
     155             : 
     156             : STATISTIC(NumBytesStackSpace,
     157             :           "Number of bytes used for stack in all functions");
     158             : 
     159       18448 : void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
     160       18448 :   AU.setPreservesCFG();
     161             :   AU.addPreserved<MachineLoopInfo>();
     162             :   AU.addPreserved<MachineDominatorTree>();
     163             :   AU.addRequired<StackProtector>();
     164             :   AU.addRequired<MachineOptimizationRemarkEmitterPass>();
     165       18448 :   MachineFunctionPass::getAnalysisUsage(AU);
     166       18448 : }
     167             : 
     168             : /// StackObjSet - A set of stack object indexes
     169             : using StackObjSet = SmallSetVector<int, 8>;
     170             : 
     171             : /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
     172             : /// frame indexes with appropriate references.
     173      165690 : bool PEI::runOnMachineFunction(MachineFunction &Fn) {
     174      165690 :   const Function &F = Fn.getFunction();
     175      165690 :   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
     176      165690 :   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
     177             : 
     178      331380 :   RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : nullptr;
     179      165690 :   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
     180      330698 :   FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) ||
     181      165008 :     TRI->requiresFrameIndexReplacementScavenging(Fn);
     182      331380 :   ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
     183             : 
     184             :   // Calculate the MaxCallFrameSize and AdjustsStack variables for the
     185             :   // function's frame information. Also eliminates call frame pseudo
     186             :   // instructions.
     187      165690 :   calculateCallFrameInfo(Fn);
     188             : 
     189             :   // Determine placement of CSR spill/restore code and prolog/epilog code:
     190             :   // place all spills in the entry block, all restores in return blocks.
     191      165690 :   calculateSaveRestoreBlocks(Fn);
     192             : 
     193             :   // Handle CSR spilling and restoring, for targets that need it.
     194      165690 :   if (Fn.getTarget().usesPhysRegsForPEI())
     195      165690 :     spillCalleeSavedRegs(Fn);
     196             : 
     197             :   // Allow the target machine to make final modifications to the function
     198             :   // before the frame layout is finalized.
     199      165690 :   TFI->processFunctionBeforeFrameFinalized(Fn, RS);
     200             : 
     201             :   // Calculate actual frame offsets for all abstract stack objects...
     202      165690 :   calculateFrameObjectOffsets(Fn);
     203             : 
     204             :   // Add prolog and epilog code to the function.  This function is required
     205             :   // to align the stack frame as necessary for any stack variables or
     206             :   // called functions.  Because of this, calculateCalleeSavedRegisters()
     207             :   // must be called before this function in order to set the AdjustsStack
     208             :   // and MaxCallFrameSize variables.
     209      165690 :   if (!F.hasFnAttribute(Attribute::Naked))
     210      165611 :     insertPrologEpilogCode(Fn);
     211             : 
     212             :   // Replace all MO_FrameIndex operands with physical register references
     213             :   // and actual offsets.
     214             :   //
     215      165683 :   replaceFrameIndices(Fn);
     216             : 
     217             :   // If register scavenging is needed, as we've enabled doing it as a
     218             :   // post-pass, scavenge the virtual registers that frame index elimination
     219             :   // inserted.
     220      165683 :   if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
     221       58641 :     scavengeFrameVirtualRegs(Fn, *RS);
     222             : 
     223             :   // Warn on stack size when we exceeds the given limit.
     224      165683 :   MachineFrameInfo &MFI = Fn.getFrameInfo();
     225      165683 :   uint64_t StackSize = MFI.getStackSize();
     226      165717 :   if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
     227             :     DiagnosticInfoStackSize DiagStackSize(F, StackSize);
     228          20 :     F.getContext().diagnose(DiagStackSize);
     229             :   }
     230      165903 :   ORE->emit([&]() {
     231         440 :     return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize",
     232         440 :                                              Fn.getFunction().getSubprogram(),
     233             :                                              &Fn.front())
     234         660 :            << ore::NV("NumStackBytes", StackSize) << " stack bytes in function";
     235         220 :   });
     236             : 
     237      165682 :   delete RS;
     238             :   SaveBlocks.clear();
     239             :   RestoreBlocks.clear();
     240             :   MFI.setSavePoint(nullptr);
     241             :   MFI.setRestorePoint(nullptr);
     242      165682 :   return true;
     243             : }
     244             : 
     245             : /// Calculate the MaxCallFrameSize and AdjustsStack
     246             : /// variables for the function's frame information and eliminate call frame
     247             : /// pseudo instructions.
     248      165690 : void PEI::calculateCallFrameInfo(MachineFunction &Fn) {
     249      165690 :   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
     250      165690 :   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
     251      165690 :   MachineFrameInfo &MFI = Fn.getFrameInfo();
     252             : 
     253             :   unsigned MaxCallFrameSize = 0;
     254      165690 :   bool AdjustsStack = MFI.adjustsStack();
     255             : 
     256             :   // Get the function call frame set-up and tear-down instruction opcode
     257      165690 :   unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
     258      165690 :   unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
     259             : 
     260             :   // Early exit for targets which have no call frame setup/destroy pseudo
     261             :   // instructions.
     262      165690 :   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
     263           0 :     return;
     264             : 
     265             :   std::vector<MachineBasicBlock::iterator> FrameSDOps;
     266      487976 :   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
     267     3951263 :     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
     268             :       if (TII.isFrameInstr(*I)) {
     269      389328 :         unsigned Size = TII.getFrameSize(*I);
     270      389328 :         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
     271             :         AdjustsStack = true;
     272      389328 :         FrameSDOps.push_back(I);
     273     2917363 :       } else if (I->isInlineAsm()) {
     274             :         // Some inline asm's need a stack frame, as indicated by operand 1.
     275       11956 :         unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
     276       11956 :         if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
     277             :           AdjustsStack = true;
     278             :       }
     279             : 
     280             :   assert(!MFI.isMaxCallFrameSizeComputed() ||
     281             :          (MFI.getMaxCallFrameSize() == MaxCallFrameSize &&
     282             :           MFI.adjustsStack() == AdjustsStack));
     283             :   MFI.setAdjustsStack(AdjustsStack);
     284             :   MFI.setMaxCallFrameSize(MaxCallFrameSize);
     285             : 
     286             :   for (std::vector<MachineBasicBlock::iterator>::iterator
     287      555018 :          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
     288      389328 :     MachineBasicBlock::iterator I = *i;
     289             : 
     290             :     // If call frames are not being included as part of the stack frame, and
     291             :     // the target doesn't indicate otherwise, remove the call frame pseudos
     292             :     // here. The sub/add sp instruction pairs are still inserted, but we don't
     293             :     // need to track the SP adjustment for frame index elimination.
     294      389328 :     if (TFI->canSimplifyCallFramePseudos(Fn))
     295      323322 :       TFI->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
     296             :   }
     297             : }
     298             : 
     299             : /// Compute the sets of entry and return blocks for saving and restoring
     300             : /// callee-saved registers, and placing prolog and epilog code.
     301      165690 : void PEI::calculateSaveRestoreBlocks(MachineFunction &Fn) {
     302      165690 :   const MachineFrameInfo &MFI = Fn.getFrameInfo();
     303             : 
     304             :   // Even when we do not change any CSR, we still want to insert the
     305             :   // prologue and epilogue of the function.
     306             :   // So set the save points for those.
     307             : 
     308             :   // Use the points found by shrink-wrapping, if any.
     309      165690 :   if (MFI.getSavePoint()) {
     310         425 :     SaveBlocks.push_back(MFI.getSavePoint());
     311             :     assert(MFI.getRestorePoint() && "Both restore and save must be set");
     312         425 :     MachineBasicBlock *RestoreBlock = MFI.getRestorePoint();
     313             :     // If RestoreBlock does not have any successor and is not a return block
     314             :     // then the end point is unreachable and we do not need to insert any
     315             :     // epilogue.
     316         425 :     if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock())
     317         366 :       RestoreBlocks.push_back(RestoreBlock);
     318             :     return;
     319             :   }
     320             : 
     321             :   // Save refs to entry and return blocks.
     322      330530 :   SaveBlocks.push_back(&Fn.front());
     323      485649 :   for (MachineBasicBlock &MBB : Fn) {
     324      320384 :     if (MBB.isEHFuncletEntry())
     325         117 :       SaveBlocks.push_back(&MBB);
     326      320384 :     if (MBB.isReturnBlock())
     327      166858 :       RestoreBlocks.push_back(&MBB);
     328             :   }
     329             : }
     330             : 
     331      165690 : static void assignCalleeSavedSpillSlots(MachineFunction &F,
     332             :                                         const BitVector &SavedRegs,
     333             :                                         unsigned &MinCSFrameIndex,
     334             :                                         unsigned &MaxCSFrameIndex) {
     335      165690 :   if (SavedRegs.empty())
     336       65832 :     return;
     337             : 
     338      165686 :   const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();
     339      165686 :   const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs();
     340             : 
     341             :   std::vector<CalleeSavedInfo> CSI;
     342     4473744 :   for (unsigned i = 0; CSRegs[i]; ++i) {
     343     2154029 :     unsigned Reg = CSRegs[i];
     344     2154029 :     if (SavedRegs.test(Reg))
     345       46205 :       CSI.push_back(CalleeSavedInfo(Reg));
     346             :   }
     347             : 
     348      165686 :   const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();
     349      165686 :   MachineFrameInfo &MFI = F.getFrameInfo();
     350      165686 :   if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
     351             :     // If target doesn't implement this, use generic code.
     352             : 
     353       74210 :     if (CSI.empty())
     354       65828 :       return; // Early exit if no callee saved registers are modified!
     355             : 
     356             :     unsigned NumFixedSpillSlots;
     357             :     const TargetFrameLowering::SpillSlot *FixedSpillSlots =
     358        8382 :         TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
     359             : 
     360             :     // Now that we know which registers need to be saved and restored, allocate
     361             :     // stack slots for them.
     362       33420 :     for (auto &CS : CSI) {
     363       25038 :       unsigned Reg = CS.getReg();
     364       25038 :       const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
     365             : 
     366             :       int FrameIdx;
     367       25108 :       if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {
     368          70 :         CS.setFrameIdx(FrameIdx);
     369          70 :         continue;
     370             :       }
     371             : 
     372             :       // Check to see if this physreg must be spilled to a particular stack slot
     373             :       // on this target.
     374             :       const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;
     375      216877 :       while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
     376       66449 :              FixedSlot->Reg != Reg)
     377       62730 :         ++FixedSlot;
     378             : 
     379             :       unsigned Size = RegInfo->getSpillSize(*RC);
     380       24968 :       if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
     381             :         // Nope, just spill it anywhere convenient.
     382       21249 :         unsigned Align = RegInfo->getSpillAlignment(*RC);
     383       21249 :         unsigned StackAlign = TFI->getStackAlignment();
     384             : 
     385             :         // We may not be able to satisfy the desired alignment specification of
     386             :         // the TargetRegisterClass if the stack alignment is smaller. Use the
     387             :         // min.
     388       21249 :         Align = std::min(Align, StackAlign);
     389       21249 :         FrameIdx = MFI.CreateStackObject(Size, Align, true);
     390       21249 :         if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
     391       21249 :         if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
     392             :       } else {
     393             :         // Spill it to the stack where we must.
     394        3719 :         FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset);
     395             :       }
     396             : 
     397       24968 :       CS.setFrameIdx(FrameIdx);
     398             :     }
     399             :   }
     400             : 
     401             :   MFI.setCalleeSavedInfo(CSI);
     402             : }
     403             : 
     404             : /// Helper function to update the liveness information for the callee-saved
     405             : /// registers.
     406       15336 : static void updateLiveness(MachineFunction &MF) {
     407       15336 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     408             :   // Visited will contain all the basic blocks that are in the region
     409             :   // where the callee saved registers are alive:
     410             :   // - Anything that is not Save or Restore -> LiveThrough.
     411             :   // - Save -> LiveIn.
     412             :   // - Restore -> LiveOut.
     413             :   // The live-out is not attached to the block, so no need to keep
     414             :   // Restore in this set.
     415             :   SmallPtrSet<MachineBasicBlock *, 8> Visited;
     416             :   SmallVector<MachineBasicBlock *, 8> WorkList;
     417       15336 :   MachineBasicBlock *Entry = &MF.front();
     418       15336 :   MachineBasicBlock *Save = MFI.getSavePoint();
     419             : 
     420       15336 :   if (!Save)
     421             :     Save = Entry;
     422             : 
     423       15336 :   if (Entry != Save) {
     424         227 :     WorkList.push_back(Entry);
     425         227 :     Visited.insert(Entry);
     426             :   }
     427       15336 :   Visited.insert(Save);
     428             : 
     429       15336 :   MachineBasicBlock *Restore = MFI.getRestorePoint();
     430       15336 :   if (Restore)
     431             :     // By construction Restore cannot be visited, otherwise it
     432             :     // means there exists a path to Restore that does not go
     433             :     // through Save.
     434         227 :     WorkList.push_back(Restore);
     435             : 
     436       16218 :   while (!WorkList.empty()) {
     437             :     const MachineBasicBlock *CurBB = WorkList.pop_back_val();
     438             :     // By construction, the region that is after the save point is
     439             :     // dominated by the Save and post-dominated by the Restore.
     440         882 :     if (CurBB == Save && Save != Restore)
     441           0 :       continue;
     442             :     // Enqueue all the successors not already visited.
     443             :     // Those are by construction either before Save or after Restore.
     444        1745 :     for (MachineBasicBlock *SuccBB : CurBB->successors())
     445         863 :       if (Visited.insert(SuccBB).second)
     446         428 :         WorkList.push_back(SuccBB);
     447             :   }
     448             : 
     449             :   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
     450             : 
     451       15336 :   MachineRegisterInfo &MRI = MF.getRegInfo();
     452       76821 :   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
     453       46149 :     for (MachineBasicBlock *MBB : Visited) {
     454       95166 :       MCPhysReg Reg = CSI[i].getReg();
     455             :       // Add the callee-saved register as live-in.
     456             :       // It's killed at the spill.
     457       47583 :       if (!MRI.isReserved(Reg) && !MBB->isLiveIn(Reg))
     458             :         MBB->addLiveIn(Reg);
     459             :     }
     460             :   }
     461       15336 : }
     462             : 
     463             : /// Insert restore code for the callee-saved registers used in the function.
     464       15336 : static void insertCSRSaves(MachineBasicBlock &SaveBlock,
     465             :                            ArrayRef<CalleeSavedInfo> CSI) {
     466       15336 :   MachineFunction &Fn = *SaveBlock.getParent();
     467       15336 :   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
     468       15336 :   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
     469       15336 :   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
     470             : 
     471       15336 :   MachineBasicBlock::iterator I = SaveBlock.begin();
     472       46008 :   if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) {
     473        1072 :     for (const CalleeSavedInfo &CS : CSI) {
     474             :       // Insert the spill to the stack frame.
     475         475 :       unsigned Reg = CS.getReg();
     476         475 :       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
     477         475 :       TII.storeRegToStackSlot(SaveBlock, I, Reg, true, CS.getFrameIdx(), RC,
     478         475 :                               TRI);
     479             :     }
     480             :   }
     481       15336 : }
     482             : 
     483             : /// Insert restore code for the callee-saved registers used in the function.
     484       15522 : static void insertCSRRestores(MachineBasicBlock &RestoreBlock,
     485             :                               std::vector<CalleeSavedInfo> &CSI) {
     486       15522 :   MachineFunction &Fn = *RestoreBlock.getParent();
     487       15522 :   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
     488       15522 :   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
     489       15522 :   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
     490             : 
     491             :   // Restore all registers immediately before the return and any
     492             :   // terminators that precede it.
     493       15522 :   MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator();
     494             : 
     495       15522 :   if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) {
     496        6159 :     for (const CalleeSavedInfo &CI : reverse(CSI)) {
     497        4111 :       unsigned Reg = CI.getReg();
     498        4111 :       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
     499        4111 :       TII.loadRegFromStackSlot(RestoreBlock, I, Reg, CI.getFrameIdx(), RC, TRI);
     500             :       assert(I != RestoreBlock.begin() &&
     501             :              "loadRegFromStackSlot didn't insert any code!");
     502             :       // Insert in reverse order.  loadRegFromStackSlot can insert
     503             :       // multiple instructions.
     504             :     }
     505             :   }
     506       15522 : }
     507             : 
     508      165690 : void PEI::spillCalleeSavedRegs(MachineFunction &Fn) {
     509             :   // We can't list this requirement in getRequiredProperties because some
     510             :   // targets (WebAssembly) use virtual registers past this point, and the pass
     511             :   // pipeline is set up without giving the passes a chance to look at the
     512             :   // TargetMachine.
     513             :   // FIXME: Find a way to express this in getRequiredProperties.
     514             :   assert(Fn.getProperties().hasProperty(
     515             :       MachineFunctionProperties::Property::NoVRegs));
     516             : 
     517      165690 :   const Function &F = Fn.getFunction();
     518      165690 :   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
     519      165690 :   MachineFrameInfo &MFI = Fn.getFrameInfo();
     520      165690 :   MinCSFrameIndex = std::numeric_limits<unsigned>::max();
     521      165690 :   MaxCSFrameIndex = 0;
     522             : 
     523             :   // Determine which of the registers in the callee save list should be saved.
     524             :   BitVector SavedRegs;
     525      165690 :   TFI->determineCalleeSaves(Fn, SavedRegs, RS);
     526             : 
     527             :   // Assign stack slots for any callee-saved registers that must be spilled.
     528      165690 :   assignCalleeSavedSpillSlots(Fn, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);
     529             : 
     530             :   // Add the code to save and restore the callee saved registers.
     531      165690 :   if (!F.hasFnAttribute(Attribute::Naked)) {
     532             :     MFI.setCalleeSavedInfoValid(true);
     533             : 
     534             :     std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
     535      165611 :     if (!CSI.empty()) {
     536       45962 :       for (MachineBasicBlock *SaveBlock : SaveBlocks) {
     537       15336 :         insertCSRSaves(*SaveBlock, CSI);
     538             :         // Update the live-in information of all the blocks up to the save
     539             :         // point.
     540       15336 :         updateLiveness(Fn);
     541             :       }
     542       46334 :       for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
     543       15522 :         insertCSRRestores(*RestoreBlock, CSI);
     544             :     }
     545             :   }
     546      165690 : }
     547             : 
     548             : /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
     549             : static inline void
     550       46340 : AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,
     551             :                   bool StackGrowsDown, int64_t &Offset,
     552             :                   unsigned &MaxAlign, unsigned Skew) {
     553             :   // If the stack grows down, add the object size to find the lowest address.
     554       46340 :   if (StackGrowsDown)
     555       43198 :     Offset += MFI.getObjectSize(FrameIdx);
     556             : 
     557       46340 :   unsigned Align = MFI.getObjectAlignment(FrameIdx);
     558             : 
     559             :   // If the alignment of this object is greater than that of the stack, then
     560             :   // increase the stack alignment to match.
     561       46340 :   MaxAlign = std::max(MaxAlign, Align);
     562             : 
     563             :   // Adjust to alignment boundary.
     564       92680 :   Offset = alignTo(Offset, Align, Skew);
     565             : 
     566       46340 :   if (StackGrowsDown) {
     567             :     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
     568       43198 :     MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset
     569             :   } else {
     570             :     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
     571             :     MFI.setObjectOffset(FrameIdx, Offset);
     572        3142 :     Offset += MFI.getObjectSize(FrameIdx);
     573             :   }
     574       46340 : }
     575             : 
     576             : /// Compute which bytes of fixed and callee-save stack area are unused and keep
     577             : /// track of them in StackBytesFree.
     578             : static inline void
     579         120 : computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown,
     580             :                       unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,
     581             :                       int64_t FixedCSEnd, BitVector &StackBytesFree) {
     582             :   // Avoid undefined int64_t -> int conversion below in extreme case.
     583         120 :   if (FixedCSEnd > std::numeric_limits<int>::max())
     584           0 :     return;
     585             : 
     586         120 :   StackBytesFree.resize(FixedCSEnd, true);
     587             : 
     588             :   SmallVector<int, 16> AllocatedFrameSlots;
     589             :   // Add fixed objects.
     590         275 :   for (int i = MFI.getObjectIndexBegin(); i != 0; ++i)
     591          35 :     AllocatedFrameSlots.push_back(i);
     592             :   // Add callee-save objects.
     593         300 :   for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i)
     594         180 :     AllocatedFrameSlots.push_back(i);
     595             : 
     596         550 :   for (int i : AllocatedFrameSlots) {
     597             :     // These are converted from int64_t, but they should always fit in int
     598             :     // because of the FixedCSEnd check above.
     599         215 :     int ObjOffset = MFI.getObjectOffset(i);
     600         215 :     int ObjSize = MFI.getObjectSize(i);
     601             :     int ObjStart, ObjEnd;
     602         215 :     if (StackGrowsDown) {
     603             :       // ObjOffset is negative when StackGrowsDown is true.
     604         215 :       ObjStart = -ObjOffset - ObjSize;
     605             :       ObjEnd = -ObjOffset;
     606             :     } else {
     607             :       ObjStart = ObjOffset;
     608           0 :       ObjEnd = ObjOffset + ObjSize;
     609             :     }
     610             :     // Ignore fixed holes that are in the previous stack frame.
     611         215 :     if (ObjEnd > 0)
     612         187 :       StackBytesFree.reset(ObjStart, ObjEnd);
     613             :   }
     614             : }
     615             : 
     616             : /// Assign frame object to an unused portion of the stack in the fixed stack
     617             : /// object range.  Return true if the allocation was successful.
     618       44280 : static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx,
     619             :                                      bool StackGrowsDown, unsigned MaxAlign,
     620             :                                      BitVector &StackBytesFree) {
     621       44280 :   if (MFI.isVariableSizedObjectIndex(FrameIdx))
     622             :     return false;
     623             : 
     624       43886 :   if (StackBytesFree.none()) {
     625             :     // clear it to speed up later scavengeStackSlot calls to
     626             :     // StackBytesFree.none()
     627             :     StackBytesFree.clear();
     628       43686 :     return false;
     629             :   }
     630             : 
     631             :   unsigned ObjAlign = MFI.getObjectAlignment(FrameIdx);
     632         200 :   if (ObjAlign > MaxAlign)
     633             :     return false;
     634             : 
     635             :   int64_t ObjSize = MFI.getObjectSize(FrameIdx);
     636             :   int FreeStart;
     637        2742 :   for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;
     638        1271 :        FreeStart = StackBytesFree.find_next(FreeStart)) {
     639             : 
     640             :     // Check that free space has suitable alignment.
     641        1314 :     unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart;
     642        2628 :     if (alignTo(ObjStart, ObjAlign) != ObjStart)
     643        1116 :       continue;
     644             : 
     645         198 :     if (FreeStart + ObjSize > StackBytesFree.size())
     646             :       return false;
     647             : 
     648             :     bool AllBytesFree = true;
     649        2863 :     for (unsigned Byte = 0; Byte < ObjSize; ++Byte)
     650        3000 :       if (!StackBytesFree.test(FreeStart + Byte)) {
     651             :         AllBytesFree = false;
     652             :         break;
     653             :       }
     654         173 :     if (AllBytesFree)
     655             :       break;
     656             :   }
     657             : 
     658         175 :   if (FreeStart == -1)
     659             :     return false;
     660             : 
     661          18 :   if (StackGrowsDown) {
     662          18 :     int ObjStart = -(FreeStart + ObjSize);
     663             :     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << ObjStart
     664             :                  << "]\n");
     665          18 :     MFI.setObjectOffset(FrameIdx, ObjStart);
     666             :   } else {
     667             :     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << FreeStart
     668             :                  << "]\n");
     669           0 :     MFI.setObjectOffset(FrameIdx, FreeStart);
     670             :   }
     671             : 
     672          18 :   StackBytesFree.reset(FreeStart, FreeStart + ObjSize);
     673          18 :   return true;
     674             : }
     675             : 
     676             : /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
     677             : /// those required to be close to the Stack Protector) to stack offsets.
     678             : static void
     679        1947 : AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
     680             :                       SmallSet<int, 16> &ProtectedObjs,
     681             :                       MachineFrameInfo &MFI, bool StackGrowsDown,
     682             :                       int64_t &Offset, unsigned &MaxAlign, unsigned Skew) {
     683             : 
     684         862 :   for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
     685        2809 :         E = UnassignedObjs.end(); I != E; ++I) {
     686         862 :     int i = *I;
     687         862 :     AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew);
     688         862 :     ProtectedObjs.insert(i);
     689             :   }
     690        1947 : }
     691             : 
     692             : /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
     693             : /// abstract stack objects.
     694      165690 : void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
     695      165690 :   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
     696      165690 :   StackProtector *SP = &getAnalysis<StackProtector>();
     697             : 
     698             :   bool StackGrowsDown =
     699      165690 :     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
     700             : 
     701             :   // Loop over all of the stack objects, assigning sequential addresses...
     702      165690 :   MachineFrameInfo &MFI = Fn.getFrameInfo();
     703             : 
     704             :   // Start at the beginning of the local area.
     705             :   // The Offset is the distance from the stack top in the direction
     706             :   // of stack growth -- so it's always nonnegative.
     707      165690 :   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
     708      165690 :   if (StackGrowsDown)
     709      146924 :     LocalAreaOffset = -LocalAreaOffset;
     710             :   assert(LocalAreaOffset >= 0
     711             :          && "Local area offset should be in direction of stack growth");
     712      165690 :   int64_t Offset = LocalAreaOffset;
     713             : 
     714             :   // Skew to be applied to alignment.
     715      165690 :   unsigned Skew = TFI.getStackAlignmentSkew(Fn);
     716             : 
     717             :   // If there are fixed sized objects that are preallocated in the local area,
     718             :   // non-fixed objects can't be allocated right at the start of local area.
     719             :   // Adjust 'Offset' to point to the end of last fixed sized preallocated
     720             :   // object.
     721      447608 :   for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) {
     722             :     int64_t FixedOff;
     723       58114 :     if (StackGrowsDown) {
     724             :       // The maximum distance from the stack pointer is at lower address of
     725             :       // the object -- which is given by offset. For down growing stack
     726             :       // the offset is negative, so we negate the offset to get the distance.
     727       57193 :       FixedOff = -MFI.getObjectOffset(i);
     728             :     } else {
     729             :       // The maximum distance from the start pointer is at the upper
     730             :       // address of the object.
     731         921 :       FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i);
     732             :     }
     733       58114 :     if (FixedOff > Offset) Offset = FixedOff;
     734             :   }
     735             : 
     736             :   // First assign frame offsets to stack objects that are used to spill
     737             :   // callee saved registers.
     738      165690 :   if (StackGrowsDown) {
     739      167776 :     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
     740             :       // If the stack grows down, we need to add the size to find the lowest
     741             :       // address of the object.
     742       20852 :       Offset += MFI.getObjectSize(i);
     743             : 
     744             :       unsigned Align = MFI.getObjectAlignment(i);
     745             :       // Adjust to alignment boundary
     746       41704 :       Offset = alignTo(Offset, Align, Skew);
     747             : 
     748             :       DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << -Offset << "]\n");
     749       20852 :       MFI.setObjectOffset(i, -Offset);        // Set the computed offset
     750             :     }
     751       18766 :   } else if (MaxCSFrameIndex >= MinCSFrameIndex) {
     752             :     // Be careful about underflow in comparisons agains MinCSFrameIndex.
     753         902 :     for (unsigned i = MaxCSFrameIndex; i != MinCSFrameIndex - 1; --i) {
     754         397 :       if (MFI.isDeadObjectIndex(i))
     755         291 :         continue;
     756             : 
     757             :       unsigned Align = MFI.getObjectAlignment(i);
     758             :       // Adjust to alignment boundary
     759         212 :       Offset = alignTo(Offset, Align, Skew);
     760             : 
     761             :       DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << Offset << "]\n");
     762             :       MFI.setObjectOffset(i, Offset);
     763         106 :       Offset += MFI.getObjectSize(i);
     764             :     }
     765             :   }
     766             : 
     767             :   // FixedCSEnd is the stack offset to the end of the fixed and callee-save
     768             :   // stack area.
     769      165690 :   int64_t FixedCSEnd = Offset;
     770      165690 :   unsigned MaxAlign = MFI.getMaxAlignment();
     771             : 
     772             :   // Make sure the special register scavenging spill slot is closest to the
     773             :   // incoming stack pointer if a frame pointer is required and is closer
     774             :   // to the incoming rather than the final stack pointer.
     775      165690 :   const TargetRegisterInfo *RegInfo = Fn.getSubtarget().getRegisterInfo();
     776      173063 :   bool EarlyScavengingSlots = (TFI.hasFP(Fn) &&
     777       14230 :                                TFI.isFPCloseToIncomingSP() &&
     778      179384 :                                RegInfo->useFPForScavengingIndex(Fn) &&
     779        6837 :                                !RegInfo->needsStackRealignment(Fn));
     780      165690 :   if (RS && EarlyScavengingSlots) {
     781             :     SmallVector<int, 2> SFIs;
     782             :     RS->getScavengingFrameIndices(SFIs);
     783          19 :     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
     784        4126 :            IE = SFIs.end(); I != IE; ++I)
     785          19 :       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
     786             :   }
     787             : 
     788             :   // FIXME: Once this is working, then enable flag will change to a target
     789             :   // check for whether the frame is large enough to want to use virtual
     790             :   // frame index registers. Functions which don't want/need this optimization
     791             :   // will continue to use the existing code path.
     792      165690 :   if (MFI.getUseLocalStackAllocationBlock()) {
     793          11 :     unsigned Align = MFI.getLocalFrameMaxAlign();
     794             : 
     795             :     // Adjust to alignment boundary.
     796          22 :     Offset = alignTo(Offset, Align, Skew);
     797             : 
     798             :     DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
     799             : 
     800             :     // Resolve offsets for objects in the local block.
     801         449 :     for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; ++i) {
     802         438 :       std::pair<int, int64_t> Entry = MFI.getLocalFrameObjectMap(i);
     803         438 :       int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
     804             :       DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" <<
     805             :             FIOffset << "]\n");
     806             :       MFI.setObjectOffset(Entry.first, FIOffset);
     807             :     }
     808             :     // Allocate the local block
     809          11 :     Offset += MFI.getLocalFrameSize();
     810             : 
     811          11 :     MaxAlign = std::max(Align, MaxAlign);
     812             :   }
     813             : 
     814             :   // Retrieve the Exception Handler registration node.
     815             :   int EHRegNodeFrameIndex = std::numeric_limits<int>::max();
     816      165690 :   if (const WinEHFuncInfo *FuncInfo = Fn.getWinEHFuncInfo())
     817          89 :     EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;
     818             : 
     819             :   // Make sure that the stack protector comes before the local variables on the
     820             :   // stack.
     821      165690 :   SmallSet<int, 16> ProtectedObjs;
     822      165690 :   if (MFI.getStackProtectorIndex() >= 0) {
     823             :     StackObjSet LargeArrayObjs;
     824             :     StackObjSet SmallArrayObjs;
     825             :     StackObjSet AddrOfObjs;
     826             : 
     827         649 :     AdjustStackOffset(MFI, MFI.getStackProtectorIndex(), StackGrowsDown,
     828             :                       Offset, MaxAlign, Skew);
     829             : 
     830             :     // Assign large stack objects first.
     831        5811 :     for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
     832        5324 :       if (MFI.isObjectPreAllocated(i) &&
     833         162 :           MFI.getUseLocalStackAllocationBlock())
     834           8 :         continue;
     835        2573 :       if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
     836         286 :         continue;
     837        2498 :       if (RS && RS->isScavengingFrameIndex((int)i))
     838          12 :         continue;
     839        2471 :       if (MFI.isDeadObjectIndex(i))
     840         196 :         continue;
     841        2724 :       if (MFI.getStackProtectorIndex() == (int)i ||
     842             :           EHRegNodeFrameIndex == (int)i)
     843         645 :         continue;
     844             : 
     845        2868 :       switch (SP->getSSPLayout(MFI.getObjectAllocation(i))) {
     846         572 :       case StackProtector::SSPLK_None:
     847         572 :         continue;
     848          82 :       case StackProtector::SSPLK_SmallArray:
     849          82 :         SmallArrayObjs.insert(i);
     850          82 :         continue;
     851         349 :       case StackProtector::SSPLK_AddrOf:
     852         349 :         AddrOfObjs.insert(i);
     853         349 :         continue;
     854         431 :       case StackProtector::SSPLK_LargeArray:
     855         431 :         LargeArrayObjs.insert(i);
     856         431 :         continue;
     857             :       }
     858           0 :       llvm_unreachable("Unexpected SSPLayoutKind.");
     859             :     }
     860             : 
     861         649 :     AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
     862             :                           Offset, MaxAlign, Skew);
     863         649 :     AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
     864             :                           Offset, MaxAlign, Skew);
     865         649 :     AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
     866             :                           Offset, MaxAlign, Skew);
     867             :   }
     868             : 
     869             :   SmallVector<int, 8> ObjectsToAllocate;
     870             : 
     871             :   // Then prepare to assign frame offsets to stack objects that are not used to
     872             :   // spill callee saved registers.
     873      327024 :   for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
     874      161772 :     if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())
     875         438 :       continue;
     876      101580 :     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
     877       21249 :       continue;
     878       76751 :     if (RS && RS->isScavengingFrameIndex((int)i))
     879         533 :       continue;
     880       71075 :     if (MFI.isDeadObjectIndex(i))
     881       12628 :       continue;
     882       46496 :     if (MFI.getStackProtectorIndex() == (int)i ||
     883             :         EHRegNodeFrameIndex == (int)i)
     884         677 :       continue;
     885       46004 :     if (ProtectedObjs.count(i))
     886         862 :       continue;
     887             : 
     888             :     // Add the objects that we need to allocate to our working set.
     889       44280 :     ObjectsToAllocate.push_back(i);
     890             :   }
     891             : 
     892             :   // Allocate the EH registration node first if one is present.
     893      165690 :   if (EHRegNodeFrameIndex != std::numeric_limits<int>::max())
     894          32 :     AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,
     895             :                       MaxAlign, Skew);
     896             : 
     897             :   // Give the targets a chance to order the objects the way they like it.
     898      324389 :   if (Fn.getTarget().getOptLevel() != CodeGenOpt::None &&
     899      158699 :       Fn.getTarget().Options.StackSymbolOrdering)
     900      158363 :     TFI.orderFrameObjects(Fn, ObjectsToAllocate);
     901             : 
     902             :   // Keep track of which bytes in the fixed and callee-save range are used so we
     903             :   // can use the holes when allocating later stack objects.  Only do this if
     904             :   // stack protector isn't being used and the target requests it and we're
     905             :   // optimizing.
     906             :   BitVector StackBytesFree;
     907      181821 :   if (!ObjectsToAllocate.empty() &&
     908       28466 :       Fn.getTarget().getOptLevel() != CodeGenOpt::None &&
     909      190080 :       MFI.getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(Fn))
     910         120 :     computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,
     911             :                           FixedCSEnd, StackBytesFree);
     912             : 
     913             :   // Now walk the objects and actually assign base offsets to them.
     914      254250 :   for (auto &Object : ObjectsToAllocate)
     915       44280 :     if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,
     916             :                            StackBytesFree))
     917       44262 :       AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew);
     918             : 
     919             :   // Make sure the special register scavenging spill slot is closest to the
     920             :   // stack pointer.
     921      165690 :   if (RS && !EarlyScavengingSlots) {
     922             :     SmallVector<int, 2> SFIs;
     923             :     RS->getScavengingFrameIndices(SFIs);
     924         516 :     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
     925       55734 :            IE = SFIs.end(); I != IE; ++I)
     926         516 :       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
     927             :   }
     928             : 
     929      165690 :   if (!TFI.targetHandlesStackFrameRounding()) {
     930             :     // If we have reserved argument space for call sites in the function
     931             :     // immediately on entry to the current function, count it as part of the
     932             :     // overall stack size.
     933      152816 :     if (MFI.adjustsStack() && TFI.hasReservedCallFrame(Fn))
     934       15412 :       Offset += MFI.getMaxCallFrameSize();
     935             : 
     936             :     // Round up the size to a multiple of the alignment.  If the function has
     937             :     // any calls or alloca's, align to the target's StackAlignment value to
     938             :     // ensure that the callee's frame or the alloca data is suitably aligned;
     939             :     // otherwise, for leaf functions, align to the TransientStackAlignment
     940             :     // value.
     941             :     unsigned StackAlign;
     942      288212 :     if (MFI.adjustsStack() || MFI.hasVarSizedObjects() ||
     943      136752 :         (RegInfo->needsStackRealignment(Fn) && MFI.getObjectIndexEnd() != 0))
     944       18714 :       StackAlign = TFI.getStackAlignment();
     945             :     else
     946      134102 :       StackAlign = TFI.getTransientStackAlignment();
     947             : 
     948             :     // If the frame pointer is eliminated, all frame offsets will be relative to
     949             :     // SP not FP. Align to MaxAlign so this works.
     950      152816 :     StackAlign = std::max(StackAlign, MaxAlign);
     951      305632 :     Offset = alignTo(Offset, StackAlign, Skew);
     952             :   }
     953             : 
     954             :   // Update frame info to pretend that this is part of the stack...
     955      165690 :   int64_t StackSize = Offset - LocalAreaOffset;
     956      165690 :   MFI.setStackSize(StackSize);
     957             :   NumBytesStackSpace += StackSize;
     958      165690 : }
     959             : 
     960             : /// insertPrologEpilogCode - Scan the function for modified callee saved
     961             : /// registers, insert spill code for these callee saved registers, then add
     962             : /// prolog and epilog code to the function.
     963      165611 : void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
     964      165611 :   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
     965             : 
     966             :   // Add prologue to the function...
     967      497057 :   for (MachineBasicBlock *SaveBlock : SaveBlocks)
     968      165728 :     TFI.emitPrologue(Fn, *SaveBlock);
     969             : 
     970             :   // Add epilogue to restore the callee-save registers in each exiting block.
     971      500012 :   for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
     972      167203 :     TFI.emitEpilogue(Fn, *RestoreBlock);
     973             : 
     974      497052 :   for (MachineBasicBlock *SaveBlock : SaveBlocks)
     975      165723 :     TFI.inlineStackProbe(Fn, *SaveBlock);
     976             : 
     977             :   // Emit additional code that is required to support segmented stacks, if
     978             :   // we've been asked for it.  This, when linked with a runtime with support
     979             :   // for segmented stacks (libgcc is one), will result in allocating stack
     980             :   // space in small chunks instead of one large contiguous block.
     981      165606 :   if (Fn.shouldSplitStack()) {
     982         644 :     for (MachineBasicBlock *SaveBlock : SaveBlocks)
     983         216 :       TFI.adjustForSegmentedStacks(Fn, *SaveBlock);
     984             :     // Record that there are split-stack functions, so we will emit a
     985             :     // special section to tell the linker.
     986         214 :     Fn.getMMI().setHasSplitStack(true);
     987             :   } else
     988      165390 :     Fn.getMMI().setHasNosplitStack(true);
     989             : 
     990             :   // Emit additional code that is required to explicitly handle the stack in
     991             :   // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
     992             :   // approach is rather similar to that of Segmented Stacks, but it uses a
     993             :   // different conditional check and another BIF for allocating more stack
     994             :   // space.
     995      331208 :   if (Fn.getFunction().getCallingConv() == CallingConv::HiPE)
     996          39 :     for (MachineBasicBlock *SaveBlock : SaveBlocks)
     997          13 :       TFI.adjustForHiPEPrologue(Fn, *SaveBlock);
     998      165604 : }
     999             : 
    1000             : /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
    1001             : /// register references and actual offsets.
    1002      165683 : void PEI::replaceFrameIndices(MachineFunction &Fn) {
    1003      165683 :   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
    1004      298585 :   if (!TFI.needsFrameIndexResolution(Fn)) return;
    1005             : 
    1006             :   // Store SPAdj at exit of a basic block.
    1007             :   SmallVector<int, 8> SPState;
    1008       32781 :   SPState.resize(Fn.getNumBlockIDs());
    1009             :   df_iterator_default_set<MachineBasicBlock*> Reachable;
    1010             : 
    1011             :   // Iterate over the reachable blocks in DFS order.
    1012       32781 :   for (auto DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable);
    1013      199824 :        DFI != DFE; ++DFI) {
    1014      167043 :     int SPAdj = 0;
    1015             :     // Check the exit state of the DFS stack predecessor.
    1016      167043 :     if (DFI.getPathLength() >= 2) {
    1017      134262 :       MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
    1018             :       assert(Reachable.count(StackPred) &&
    1019             :              "DFS stack predecessor is already visited.\n");
    1020      268524 :       SPAdj = SPState[StackPred->getNumber()];
    1021             :     }
    1022      167043 :     MachineBasicBlock *BB = *DFI;
    1023      167043 :     replaceFrameIndices(BB, Fn, SPAdj);
    1024      334086 :     SPState[BB->getNumber()] = SPAdj;
    1025             :   }
    1026             : 
    1027             :   // Handle the unreachable blocks.
    1028      199851 :   for (auto &BB : Fn) {
    1029      167070 :     if (Reachable.count(&BB))
    1030             :       // Already handled in DFS traversal.
    1031      167043 :       continue;
    1032          27 :     int SPAdj = 0;
    1033          27 :     replaceFrameIndices(&BB, Fn, SPAdj);
    1034             :   }
    1035             : }
    1036             : 
    1037      167070 : void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
    1038             :                               int &SPAdj) {
    1039             :   assert(Fn.getSubtarget().getRegisterInfo() &&
    1040             :          "getRegisterInfo() must be implemented!");
    1041      167070 :   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
    1042      167070 :   const TargetRegisterInfo &TRI = *Fn.getSubtarget().getRegisterInfo();
    1043      167070 :   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
    1044             : 
    1045      167070 :   if (RS && FrameIndexEliminationScavenging)
    1046         363 :     RS->enterBasicBlock(*BB);
    1047             : 
    1048             :   bool InsideCallSequence = false;
    1049             : 
    1050     2778315 :   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
    1051       66004 :     if (TII.isFrameInstr(*I)) {
    1052             :       InsideCallSequence = TII.isFrameSetup(*I);
    1053       66004 :       SPAdj += TII.getSPAdjust(*I);
    1054       66004 :       I = TFI->eliminateCallFramePseudoInstr(Fn, *BB, I);
    1055             :       continue;
    1056             :     }
    1057             : 
    1058             :     MachineInstr &MI = *I;
    1059             :     bool DoIncr = true;
    1060             :     bool DidFinishLoop = true;
    1061    24452706 :     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    1062    20137102 :       if (!MI.getOperand(i).isFI())
    1063             :         continue;
    1064             : 
    1065             :       // Frame indices in debug values are encoded in a target independent
    1066             :       // way with simply the frame index and offset rather than any
    1067             :       // target-specific addressing mode.
    1068      221744 :       if (MI.isDebugValue()) {
    1069             :         assert(i == 0 && "Frame indices can only appear as the first "
    1070             :                          "operand of a DBG_VALUE machine instruction");
    1071             :         unsigned Reg;
    1072             :         int64_t Offset =
    1073        1219 :             TFI->getFrameIndexReference(Fn, MI.getOperand(0).getIndex(), Reg);
    1074        1219 :         MI.getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
    1075        1219 :         auto *DIExpr = DIExpression::prepend(MI.getDebugExpression(),
    1076        1219 :                                              DIExpression::NoDeref, Offset);
    1077        1219 :         MI.getOperand(3).setMetadata(DIExpr);
    1078        1219 :         continue;
    1079             :       }
    1080             : 
    1081             :       // TODO: This code should be commoned with the code for
    1082             :       // PATCHPOINT. There's no good reason for the difference in
    1083             :       // implementation other than historical accident.  The only
    1084             :       // remaining difference is the unconditional use of the stack
    1085             :       // pointer as the base register.
    1086      220525 :       if (MI.getOpcode() == TargetOpcode::STATEPOINT) {
    1087             :         assert((!MI.isDebugValue() || i == 0) &&
    1088             :                "Frame indicies can only appear as the first operand of a "
    1089             :                "DBG_VALUE machine instruction");
    1090             :         unsigned Reg;
    1091         156 :         MachineOperand &Offset = MI.getOperand(i + 1);
    1092         156 :         int refOffset = TFI->getFrameIndexReferencePreferSP(
    1093         312 :             Fn, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false);
    1094         156 :         Offset.setImm(Offset.getImm() + refOffset);
    1095         312 :         MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
    1096         156 :         continue;
    1097             :       }
    1098             : 
    1099             :       // Some instructions (e.g. inline asm instructions) can have
    1100             :       // multiple frame indices and/or cause eliminateFrameIndex
    1101             :       // to insert more than one instruction. We need the register
    1102             :       // scavenger to go through all of these instructions so that
    1103             :       // it can update its register information. We keep the
    1104             :       // iterator at the point before insertion so that we can
    1105             :       // revisit them in full.
    1106             :       bool AtBeginning = (I == BB->begin());
    1107      220369 :       if (!AtBeginning) --I;
    1108             : 
    1109             :       // If this instruction has a FrameIndex operand, we need to
    1110             :       // use that target machine register info object to eliminate
    1111             :       // it.
    1112      440738 :       TRI.eliminateFrameIndex(MI, SPAdj, i,
    1113      220369 :                               FrameIndexEliminationScavenging ?  RS : nullptr);
    1114             : 
    1115             :       // Reset the iterator if we were at the beginning of the BB.
    1116      220369 :       if (AtBeginning) {
    1117       16467 :         I = BB->begin();
    1118             :         DoIncr = false;
    1119             :       }
    1120             : 
    1121             :       DidFinishLoop = false;
    1122             :       break;
    1123             :     }
    1124             : 
    1125             :     // If we are looking at a call sequence, we need to keep track of
    1126             :     // the SP adjustment made by each instruction in the sequence.
    1127             :     // This includes both the frame setup/destroy pseudos (handled above),
    1128             :     // as well as other instructions that have side effects w.r.t the SP.
    1129             :     // Note that this must come after eliminateFrameIndex, because
    1130             :     // if I itself referred to a frame index, we shouldn't count its own
    1131             :     // adjustment.
    1132     2378171 :     if (DidFinishLoop && InsideCallSequence)
    1133      256010 :       SPAdj += TII.getSPAdjust(MI);
    1134             : 
    1135     4739875 :     if (DoIncr && I != BB->end()) ++I;
    1136             : 
    1137             :     // Update register states.
    1138     2378171 :     if (RS && FrameIndexEliminationScavenging && DidFinishLoop)
    1139        4884 :       RS->forward(MI);
    1140             :   }
    1141      412128 : }

Generated by: LCOV version 1.13