LCOV - code coverage report
Current view: top level - lib/CodeGen - PrologEpilogInserter.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 424 429 98.8 %
Date: 2018-07-13 00:08:38 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       65697 : class PEI : public MachineFunctionPass {
      82             : public:
      83             :   static char ID;
      84             : 
      85       44002 :   PEI() : MachineFunctionPass(ID) {
      86       22001 :     initializePEIPass(*PassRegistry::getPassRegistry());
      87       22001 :   }
      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 &MF) 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 &MF);
     121             :   void calculateSaveRestoreBlocks(MachineFunction &MF);
     122             :   void spillCalleeSavedRegs(MachineFunction &MF);
     123             : 
     124             :   void calculateFrameObjectOffsets(MachineFunction &MF);
     125             :   void replaceFrameIndices(MachineFunction &MF);
     126             :   void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
     127             :                            int &SPAdj);
     128             :   void insertPrologEpilogCode(MachineFunction &MF);
     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      299229 : WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
     139       99743 :               cl::desc("Warn for stack size bigger than the given"
     140       99743 :                        " number"));
     141             : 
     142       26316 : INITIALIZE_PASS_BEGIN(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion", false,
     143             :                       false)
     144       26316 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     145       26316 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     146       26316 : INITIALIZE_PASS_DEPENDENCY(StackProtector)
     147       26316 : INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
     148      190612 : INITIALIZE_PASS_END(PEI, DEBUG_TYPE,
     149             :                     "Prologue/Epilogue Insertion & Frame Finalization", false,
     150             :                     false)
     151             : 
     152       21989 : MachineFunctionPass *llvm::createPrologEpilogInserterPass() {
     153       21989 :   return new PEI();
     154             : }
     155             : 
     156             : STATISTIC(NumBytesStackSpace,
     157             :           "Number of bytes used for stack in all functions");
     158             : 
     159       21830 : void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
     160       21830 :   AU.setPreservesCFG();
     161             :   AU.addPreserved<MachineLoopInfo>();
     162             :   AU.addPreserved<MachineDominatorTree>();
     163             :   AU.addRequired<StackProtector>();
     164             :   AU.addRequired<MachineOptimizationRemarkEmitterPass>();
     165       21830 :   MachineFunctionPass::getAnalysisUsage(AU);
     166       21830 : }
     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      219801 : bool PEI::runOnMachineFunction(MachineFunction &MF) {
     174      219801 :   const Function &F = MF.getFunction();
     175      219801 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     176      219801 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     177             : 
     178      439602 :   RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr;
     179      219801 :   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(MF);
     180      438911 :   FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) ||
     181      219110 :     TRI->requiresFrameIndexReplacementScavenging(MF);
     182      439602 :   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      219801 :   calculateCallFrameInfo(MF);
     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      219801 :   calculateSaveRestoreBlocks(MF);
     192             : 
     193             :   // Handle CSR spilling and restoring, for targets that need it.
     194      219801 :   if (MF.getTarget().usesPhysRegsForPEI())
     195      218394 :     spillCalleeSavedRegs(MF);
     196             : 
     197             :   // Allow the target machine to make final modifications to the function
     198             :   // before the frame layout is finalized.
     199      219801 :   TFI->processFunctionBeforeFrameFinalized(MF, RS);
     200             : 
     201             :   // Calculate actual frame offsets for all abstract stack objects...
     202      219801 :   calculateFrameObjectOffsets(MF);
     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      219801 :   if (!F.hasFnAttribute(Attribute::Naked))
     210      219721 :     insertPrologEpilogCode(MF);
     211             : 
     212             :   // Replace all MO_FrameIndex operands with physical register references
     213             :   // and actual offsets.
     214             :   //
     215      219794 :   replaceFrameIndices(MF);
     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      219794 :   if (TRI->requiresRegisterScavenging(MF) && FrameIndexVirtualScavenging)
     221       63079 :     scavengeFrameVirtualRegs(MF, *RS);
     222             : 
     223             :   // Warn on stack size when we exceeds the given limit.
     224      219794 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     225      219794 :   uint64_t StackSize = MFI.getStackSize();
     226      219828 :   if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
     227             :     DiagnosticInfoStackSize DiagStackSize(F, StackSize);
     228          20 :     F.getContext().diagnose(DiagStackSize);
     229             :   }
     230      220042 :   ORE->emit([&]() {
     231         496 :     return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize",
     232         496 :                                              MF.getFunction().getSubprogram(),
     233             :                                              &MF.front())
     234         744 :            << ore::NV("NumStackBytes", StackSize) << " stack bytes in function";
     235         248 :   });
     236             : 
     237      219794 :   delete RS;
     238             :   SaveBlocks.clear();
     239             :   RestoreBlocks.clear();
     240             :   MFI.setSavePoint(nullptr);
     241             :   MFI.setRestorePoint(nullptr);
     242      219794 :   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      219801 : void PEI::calculateCallFrameInfo(MachineFunction &MF) {
     249      219801 :   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
     250      219801 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     251      219801 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     252             : 
     253             :   unsigned MaxCallFrameSize = 0;
     254      219801 :   bool AdjustsStack = MFI.adjustsStack();
     255             : 
     256             :   // Get the function call frame set-up and tear-down instruction opcode
     257      219801 :   unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
     258      219801 :   unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
     259             : 
     260             :   // Early exit for targets which have no call frame setup/destroy pseudo
     261             :   // instructions.
     262      219801 :   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
     263        2238 :     return;
     264             : 
     265             :   std::vector<MachineBasicBlock::iterator> FrameSDOps;
     266      641656 :   for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)
     267     4553808 :     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
     268             :       if (TII.isFrameInstr(*I)) {
     269      443106 :         unsigned Size = TII.getFrameSize(*I);
     270      443106 :         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
     271             :         AdjustsStack = true;
     272      443106 :         FrameSDOps.push_back(I);
     273     3262516 :       } else if (I->isInlineAsm()) {
     274             :         // Some inline asm's need a stack frame, as indicated by operand 1.
     275       16500 :         unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
     276       16500 :         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      660669 :          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
     288      443106 :     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      443106 :     if (TFI->canSimplifyCallFramePseudos(MF))
     295      415936 :       TFI->eliminateCallFramePseudoInstr(MF, *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      219801 : void PEI::calculateSaveRestoreBlocks(MachineFunction &MF) {
     302      219801 :   const MachineFrameInfo &MFI = MF.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      219801 :   if (MFI.getSavePoint()) {
     310         501 :     SaveBlocks.push_back(MFI.getSavePoint());
     311             :     assert(MFI.getRestorePoint() && "Both restore and save must be set");
     312         501 :     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         501 :     if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock())
     317         440 :       RestoreBlocks.push_back(RestoreBlock);
     318             :     return;
     319             :   }
     320             : 
     321             :   // Save refs to entry and return blocks.
     322      438600 :   SaveBlocks.push_back(&MF.front());
     323      643503 :   for (MachineBasicBlock &MBB : MF) {
     324      424203 :     if (MBB.isEHFuncletEntry())
     325         122 :       SaveBlocks.push_back(&MBB);
     326      424203 :     if (MBB.isReturnBlock())
     327      220741 :       RestoreBlocks.push_back(&MBB);
     328             :   }
     329             : }
     330             : 
     331      218394 : static void assignCalleeSavedSpillSlots(MachineFunction &F,
     332             :                                         const BitVector &SavedRegs,
     333             :                                         unsigned &MinCSFrameIndex,
     334             :                                         unsigned &MaxCSFrameIndex) {
     335      218394 :   if (SavedRegs.empty())
     336       70010 :     return;
     337             : 
     338      218388 :   const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();
     339      218388 :   const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs();
     340             : 
     341             :   std::vector<CalleeSavedInfo> CSI;
     342     5392282 :   for (unsigned i = 0; CSRegs[i]; ++i) {
     343     2586947 :     unsigned Reg = CSRegs[i];
     344     2586947 :     if (SavedRegs.test(Reg))
     345       49639 :       CSI.push_back(CalleeSavedInfo(Reg));
     346             :   }
     347             : 
     348      218388 :   const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();
     349      218388 :   MachineFrameInfo &MFI = F.getFrameInfo();
     350      218388 :   if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
     351             :     // If target doesn't implement this, use generic code.
     352             : 
     353       78651 :     if (CSI.empty())
     354       70004 :       return; // Early exit if no callee saved registers are modified!
     355             : 
     356             :     unsigned NumFixedSpillSlots;
     357             :     const TargetFrameLowering::SpillSlot *FixedSpillSlots =
     358        8647 :         TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
     359             : 
     360             :     // Now that we know which registers need to be saved and restored, allocate
     361             :     // stack slots for them.
     362       34914 :     for (auto &CS : CSI) {
     363       26267 :       unsigned Reg = CS.getReg();
     364       26267 :       const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
     365             : 
     366             :       int FrameIdx;
     367       26337 :       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      236188 :       while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
     376       72797 :              FixedSlot->Reg != Reg)
     377       68597 :         ++FixedSlot;
     378             : 
     379             :       unsigned Size = RegInfo->getSpillSize(*RC);
     380       26197 :       if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
     381             :         // Nope, just spill it anywhere convenient.
     382       21997 :         unsigned Align = RegInfo->getSpillAlignment(*RC);
     383       21997 :         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       21997 :         Align = std::min(Align, StackAlign);
     389       21997 :         FrameIdx = MFI.CreateStackObject(Size, Align, true);
     390       21997 :         if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
     391       21997 :         if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
     392             :       } else {
     393             :         // Spill it to the stack where we must.
     394        4200 :         FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset);
     395             :       }
     396             : 
     397       26197 :       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       16452 : static void updateLiveness(MachineFunction &MF) {
     407       16452 :   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       16452 :   MachineBasicBlock *Entry = &MF.front();
     418       16452 :   MachineBasicBlock *Save = MFI.getSavePoint();
     419             : 
     420       16452 :   if (!Save)
     421             :     Save = Entry;
     422             : 
     423       16452 :   if (Entry != Save) {
     424         287 :     WorkList.push_back(Entry);
     425         287 :     Visited.insert(Entry);
     426             :   }
     427       16452 :   Visited.insert(Save);
     428             : 
     429       16452 :   MachineBasicBlock *Restore = MFI.getRestorePoint();
     430       16452 :   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         287 :     WorkList.push_back(Restore);
     435             : 
     436       17505 :   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        1053 :     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        2067 :     for (MachineBasicBlock *SuccBB : CurBB->successors())
     445        1014 :       if (Visited.insert(SuccBB).second)
     446         479 :         WorkList.push_back(SuccBB);
     447             :   }
     448             : 
     449             :   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
     450             : 
     451       16452 :   MachineRegisterInfo &MRI = MF.getRegInfo();
     452       82378 :   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
     453       49474 :     for (MachineBasicBlock *MBB : Visited) {
     454      102196 :       MCPhysReg Reg = CSI[i].getReg();
     455             :       // Add the callee-saved register as live-in.
     456             :       // It's killed at the spill.
     457       51098 :       if (!MRI.isReserved(Reg) && !MBB->isLiveIn(Reg))
     458             :         MBB->addLiveIn(Reg);
     459             :     }
     460             :   }
     461       16452 : }
     462             : 
     463             : /// Insert restore code for the callee-saved registers used in the function.
     464       16452 : static void insertCSRSaves(MachineBasicBlock &SaveBlock,
     465             :                            ArrayRef<CalleeSavedInfo> CSI) {
     466       16452 :   MachineFunction &MF = *SaveBlock.getParent();
     467       16452 :   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
     468       16452 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     469       16452 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     470             : 
     471       16452 :   MachineBasicBlock::iterator I = SaveBlock.begin();
     472       49356 :   if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) {
     473        1313 :     for (const CalleeSavedInfo &CS : CSI) {
     474             :       // Insert the spill to the stack frame.
     475         593 :       unsigned Reg = CS.getReg();
     476         593 :       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
     477         593 :       TII.storeRegToStackSlot(SaveBlock, I, Reg, true, CS.getFrameIdx(), RC,
     478         593 :                               TRI);
     479             :     }
     480             :   }
     481       16452 : }
     482             : 
     483             : /// Insert restore code for the callee-saved registers used in the function.
     484       16639 : static void insertCSRRestores(MachineBasicBlock &RestoreBlock,
     485             :                               std::vector<CalleeSavedInfo> &CSI) {
     486       16639 :   MachineFunction &MF = *RestoreBlock.getParent();
     487       16639 :   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
     488       16639 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     489       16639 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     490             : 
     491             :   // Restore all registers immediately before the return and any
     492             :   // terminators that precede it.
     493       16639 :   MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator();
     494             : 
     495       16639 :   if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) {
     496        6327 :     for (const CalleeSavedInfo &CI : reverse(CSI)) {
     497        4256 :       unsigned Reg = CI.getReg();
     498        4256 :       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
     499        4256 :       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       16639 : }
     507             : 
     508      218394 : void PEI::spillCalleeSavedRegs(MachineFunction &MF) {
     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(MF.getProperties().hasProperty(
     515             :       MachineFunctionProperties::Property::NoVRegs));
     516             : 
     517      218394 :   const Function &F = MF.getFunction();
     518      218394 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
     519      218394 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     520      218394 :   MinCSFrameIndex = std::numeric_limits<unsigned>::max();
     521      218394 :   MaxCSFrameIndex = 0;
     522             : 
     523             :   // Determine which of the registers in the callee save list should be saved.
     524             :   BitVector SavedRegs;
     525      218394 :   TFI->determineCalleeSaves(MF, SavedRegs, RS);
     526             : 
     527             :   // Assign stack slots for any callee-saved registers that must be spilled.
     528      218394 :   assignCalleeSavedSpillSlots(MF, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);
     529             : 
     530             :   // Add the code to save and restore the callee saved registers.
     531      218394 :   if (!F.hasFnAttribute(Attribute::Naked)) {
     532             :     MFI.setCalleeSavedInfoValid(true);
     533             : 
     534             :     std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
     535      218314 :     if (!CSI.empty()) {
     536       49310 :       for (MachineBasicBlock *SaveBlock : SaveBlocks) {
     537       16452 :         insertCSRSaves(*SaveBlock, CSI);
     538             :         // Update the live-in information of all the blocks up to the save
     539             :         // point.
     540       16452 :         updateLiveness(MF);
     541             :       }
     542       49684 :       for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
     543       16639 :         insertCSRRestores(*RestoreBlock, CSI);
     544             :     }
     545             :   }
     546      218394 : }
     547             : 
     548             : /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
     549             : static inline void
     550      151548 : 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      151548 :   if (StackGrowsDown)
     555      148393 :     Offset += MFI.getObjectSize(FrameIdx);
     556             : 
     557      151548 :   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      151548 :   MaxAlign = std::max(MaxAlign, Align);
     562             : 
     563             :   // Adjust to alignment boundary.
     564      303096 :   Offset = alignTo(Offset, Align, Skew);
     565             : 
     566      151548 :   if (StackGrowsDown) {
     567             :     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset
     568             :                       << "]\n");
     569      148393 :     MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset
     570             :   } else {
     571             :     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset
     572             :                       << "]\n");
     573             :     MFI.setObjectOffset(FrameIdx, Offset);
     574        3155 :     Offset += MFI.getObjectSize(FrameIdx);
     575             :   }
     576      151548 : }
     577             : 
     578             : /// Compute which bytes of fixed and callee-save stack area are unused and keep
     579             : /// track of them in StackBytesFree.
     580             : static inline void
     581         128 : computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown,
     582             :                       unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,
     583             :                       int64_t FixedCSEnd, BitVector &StackBytesFree) {
     584             :   // Avoid undefined int64_t -> int conversion below in extreme case.
     585         128 :   if (FixedCSEnd > std::numeric_limits<int>::max())
     586           0 :     return;
     587             : 
     588         128 :   StackBytesFree.resize(FixedCSEnd, true);
     589             : 
     590             :   SmallVector<int, 16> AllocatedFrameSlots;
     591             :   // Add fixed objects.
     592         291 :   for (int i = MFI.getObjectIndexBegin(); i != 0; ++i)
     593          35 :     AllocatedFrameSlots.push_back(i);
     594             :   // Add callee-save objects.
     595         344 :   for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i)
     596         216 :     AllocatedFrameSlots.push_back(i);
     597             : 
     598         630 :   for (int i : AllocatedFrameSlots) {
     599             :     // These are converted from int64_t, but they should always fit in int
     600             :     // because of the FixedCSEnd check above.
     601         251 :     int ObjOffset = MFI.getObjectOffset(i);
     602         251 :     int ObjSize = MFI.getObjectSize(i);
     603             :     int ObjStart, ObjEnd;
     604         251 :     if (StackGrowsDown) {
     605             :       // ObjOffset is negative when StackGrowsDown is true.
     606         251 :       ObjStart = -ObjOffset - ObjSize;
     607             :       ObjEnd = -ObjOffset;
     608             :     } else {
     609             :       ObjStart = ObjOffset;
     610           0 :       ObjEnd = ObjOffset + ObjSize;
     611             :     }
     612             :     // Ignore fixed holes that are in the previous stack frame.
     613         251 :     if (ObjEnd > 0)
     614         223 :       StackBytesFree.reset(ObjStart, ObjEnd);
     615             :   }
     616             : }
     617             : 
     618             : /// Assign frame object to an unused portion of the stack in the fixed stack
     619             : /// object range.  Return true if the allocation was successful.
     620      149216 : static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx,
     621             :                                      bool StackGrowsDown, unsigned MaxAlign,
     622             :                                      BitVector &StackBytesFree) {
     623      149216 :   if (MFI.isVariableSizedObjectIndex(FrameIdx))
     624             :     return false;
     625             : 
     626      148797 :   if (StackBytesFree.none()) {
     627             :     // clear it to speed up later scavengeStackSlot calls to
     628             :     // StackBytesFree.none()
     629             :     StackBytesFree.clear();
     630      148585 :     return false;
     631             :   }
     632             : 
     633             :   unsigned ObjAlign = MFI.getObjectAlignment(FrameIdx);
     634         212 :   if (ObjAlign > MaxAlign)
     635             :     return false;
     636             : 
     637             :   int64_t ObjSize = MFI.getObjectSize(FrameIdx);
     638             :   int FreeStart;
     639        2848 :   for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;
     640        1318 :        FreeStart = StackBytesFree.find_next(FreeStart)) {
     641             : 
     642             :     // Check that free space has suitable alignment.
     643        1368 :     unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart;
     644        2736 :     if (alignTo(ObjStart, ObjAlign) != ObjStart)
     645        1159 :       continue;
     646             : 
     647         209 :     if (FreeStart + ObjSize > StackBytesFree.size())
     648             :       return false;
     649             : 
     650             :     bool AllBytesFree = true;
     651        2974 :     for (unsigned Byte = 0; Byte < ObjSize; ++Byte)
     652        3112 :       if (!StackBytesFree.test(FreeStart + Byte)) {
     653             :         AllBytesFree = false;
     654             :         break;
     655             :       }
     656         180 :     if (AllBytesFree)
     657             :       break;
     658             :   }
     659             : 
     660         183 :   if (FreeStart == -1)
     661             :     return false;
     662             : 
     663          21 :   if (StackGrowsDown) {
     664          21 :     int ObjStart = -(FreeStart + ObjSize);
     665             :     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["
     666             :                       << ObjStart << "]\n");
     667          21 :     MFI.setObjectOffset(FrameIdx, ObjStart);
     668             :   } else {
     669             :     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["
     670             :                       << FreeStart << "]\n");
     671           0 :     MFI.setObjectOffset(FrameIdx, FreeStart);
     672             :   }
     673             : 
     674          21 :   StackBytesFree.reset(FreeStart, FreeStart + ObjSize);
     675          21 :   return true;
     676             : }
     677             : 
     678             : /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
     679             : /// those required to be close to the Stack Protector) to stack offsets.
     680             : static void
     681        2343 : AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
     682             :                       SmallSet<int, 16> &ProtectedObjs,
     683             :                       MachineFrameInfo &MFI, bool StackGrowsDown,
     684             :                       int64_t &Offset, unsigned &MaxAlign, unsigned Skew) {
     685             : 
     686         996 :   for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
     687        3339 :         E = UnassignedObjs.end(); I != E; ++I) {
     688         996 :     int i = *I;
     689         996 :     AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew);
     690         996 :     ProtectedObjs.insert(i);
     691             :   }
     692        2343 : }
     693             : 
     694             : /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
     695             : /// abstract stack objects.
     696      219801 : void PEI::calculateFrameObjectOffsets(MachineFunction &MF) {
     697      219801 :   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
     698      219801 :   StackProtector *SP = &getAnalysis<StackProtector>();
     699             : 
     700             :   bool StackGrowsDown =
     701      219801 :     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
     702             : 
     703             :   // Loop over all of the stack objects, assigning sequential addresses...
     704      219801 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     705             : 
     706             :   // Start at the beginning of the local area.
     707             :   // The Offset is the distance from the stack top in the direction
     708             :   // of stack growth -- so it's always nonnegative.
     709      219801 :   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
     710      219801 :   if (StackGrowsDown)
     711      199689 :     LocalAreaOffset = -LocalAreaOffset;
     712             :   assert(LocalAreaOffset >= 0
     713             :          && "Local area offset should be in direction of stack growth");
     714      219801 :   int64_t Offset = LocalAreaOffset;
     715             : 
     716             :   // Skew to be applied to alignment.
     717      219801 :   unsigned Skew = TFI.getStackAlignmentSkew(MF);
     718             : 
     719             :   // If there are fixed sized objects that are preallocated in the local area,
     720             :   // non-fixed objects can't be allocated right at the start of local area.
     721             :   // Adjust 'Offset' to point to the end of last fixed sized preallocated
     722             :   // object.
     723      634048 :   for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) {
     724             :     int64_t FixedOff;
     725       97223 :     if (StackGrowsDown) {
     726             :       // The maximum distance from the stack pointer is at lower address of
     727             :       // the object -- which is given by offset. For down growing stack
     728             :       // the offset is negative, so we negate the offset to get the distance.
     729       96301 :       FixedOff = -MFI.getObjectOffset(i);
     730             :     } else {
     731             :       // The maximum distance from the start pointer is at the upper
     732             :       // address of the object.
     733         922 :       FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i);
     734             :     }
     735       97223 :     if (FixedOff > Offset) Offset = FixedOff;
     736             :   }
     737             : 
     738             :   // First assign frame offsets to stack objects that are used to spill
     739             :   // callee saved registers.
     740      219801 :   if (StackGrowsDown) {
     741      221171 :     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
     742             :       // If the stack grows down, we need to add the size to find the lowest
     743             :       // address of the object.
     744       21482 :       Offset += MFI.getObjectSize(i);
     745             : 
     746             :       unsigned Align = MFI.getObjectAlignment(i);
     747             :       // Adjust to alignment boundary
     748       42964 :       Offset = alignTo(Offset, Align, Skew);
     749             : 
     750             :       LLVM_DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << -Offset << "]\n");
     751       21482 :       MFI.setObjectOffset(i, -Offset);        // Set the computed offset
     752             :     }
     753       20112 :   } else if (MaxCSFrameIndex >= MinCSFrameIndex) {
     754             :     // Be careful about underflow in comparisons agains MinCSFrameIndex.
     755        1143 :     for (unsigned i = MaxCSFrameIndex; i != MinCSFrameIndex - 1; --i) {
     756         515 :       if (MFI.isDeadObjectIndex(i))
     757         409 :         continue;
     758             : 
     759             :       unsigned Align = MFI.getObjectAlignment(i);
     760             :       // Adjust to alignment boundary
     761         212 :       Offset = alignTo(Offset, Align, Skew);
     762             : 
     763             :       LLVM_DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << Offset << "]\n");
     764             :       MFI.setObjectOffset(i, Offset);
     765         106 :       Offset += MFI.getObjectSize(i);
     766             :     }
     767             :   }
     768             : 
     769             :   // FixedCSEnd is the stack offset to the end of the fixed and callee-save
     770             :   // stack area.
     771      219801 :   int64_t FixedCSEnd = Offset;
     772      219801 :   unsigned MaxAlign = MFI.getMaxAlignment();
     773             : 
     774             :   // Make sure the special register scavenging spill slot is closest to the
     775             :   // incoming stack pointer if a frame pointer is required and is closer
     776             :   // to the incoming rather than the final stack pointer.
     777      219801 :   const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
     778      256586 :   bool EarlyScavengingSlots = (TFI.hasFP(MF) &&
     779       73053 :                                TFI.isFPCloseToIncomingSP() &&
     780      292317 :                                RegInfo->useFPForScavengingIndex(MF) &&
     781       36248 :                                !RegInfo->needsStackRealignment(MF));
     782      219801 :   if (RS && EarlyScavengingSlots) {
     783             :     SmallVector<int, 2> SFIs;
     784             :     RS->getScavengingFrameIndices(SFIs);
     785          26 :     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
     786        4402 :            IE = SFIs.end(); I != IE; ++I)
     787          26 :       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
     788             :   }
     789             : 
     790             :   // FIXME: Once this is working, then enable flag will change to a target
     791             :   // check for whether the frame is large enough to want to use virtual
     792             :   // frame index registers. Functions which don't want/need this optimization
     793             :   // will continue to use the existing code path.
     794      219801 :   if (MFI.getUseLocalStackAllocationBlock()) {
     795          13 :     unsigned Align = MFI.getLocalFrameMaxAlign();
     796             : 
     797             :     // Adjust to alignment boundary.
     798          26 :     Offset = alignTo(Offset, Align, Skew);
     799             : 
     800             :     LLVM_DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
     801             : 
     802             :     // Resolve offsets for objects in the local block.
     803         459 :     for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; ++i) {
     804         446 :       std::pair<int, int64_t> Entry = MFI.getLocalFrameObjectMap(i);
     805         446 :       int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
     806             :       LLVM_DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << FIOffset
     807             :                         << "]\n");
     808             :       MFI.setObjectOffset(Entry.first, FIOffset);
     809             :     }
     810             :     // Allocate the local block
     811          13 :     Offset += MFI.getLocalFrameSize();
     812             : 
     813          13 :     MaxAlign = std::max(Align, MaxAlign);
     814             :   }
     815             : 
     816             :   // Retrieve the Exception Handler registration node.
     817             :   int EHRegNodeFrameIndex = std::numeric_limits<int>::max();
     818      219801 :   if (const WinEHFuncInfo *FuncInfo = MF.getWinEHFuncInfo())
     819          89 :     EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;
     820             : 
     821             :   // Make sure that the stack protector comes before the local variables on the
     822             :   // stack.
     823      219801 :   SmallSet<int, 16> ProtectedObjs;
     824      219801 :   if (MFI.getStackProtectorIndex() >= 0) {
     825             :     StackObjSet LargeArrayObjs;
     826             :     StackObjSet SmallArrayObjs;
     827             :     StackObjSet AddrOfObjs;
     828             : 
     829         781 :     AdjustStackOffset(MFI, MFI.getStackProtectorIndex(), StackGrowsDown,
     830             :                       Offset, MaxAlign, Skew);
     831             : 
     832             :     // Assign large stack objects first.
     833        6717 :     for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
     834        6100 :       if (MFI.isObjectPreAllocated(i) &&
     835         164 :           MFI.getUseLocalStackAllocationBlock())
     836           8 :         continue;
     837        2960 :       if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
     838         287 :         continue;
     839        2898 :       if (RS && RS->isScavengingFrameIndex((int)i))
     840          12 :         continue;
     841        2857 :       if (MFI.isDeadObjectIndex(i))
     842         196 :         continue;
     843        3242 :       if (MFI.getStackProtectorIndex() == (int)i ||
     844             :           EHRegNodeFrameIndex == (int)i)
     845         777 :         continue;
     846             : 
     847        3376 :       switch (SP->getSSPLayout(MFI.getObjectAllocation(i))) {
     848         692 :       case StackProtector::SSPLK_None:
     849         692 :         continue;
     850          98 :       case StackProtector::SSPLK_SmallArray:
     851          98 :         SmallArrayObjs.insert(i);
     852          98 :         continue;
     853         422 :       case StackProtector::SSPLK_AddrOf:
     854         422 :         AddrOfObjs.insert(i);
     855         422 :         continue;
     856         476 :       case StackProtector::SSPLK_LargeArray:
     857         476 :         LargeArrayObjs.insert(i);
     858         476 :         continue;
     859             :       }
     860           0 :       llvm_unreachable("Unexpected SSPLayoutKind.");
     861             :     }
     862             : 
     863         781 :     AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
     864             :                           Offset, MaxAlign, Skew);
     865         781 :     AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
     866             :                           Offset, MaxAlign, Skew);
     867         781 :     AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
     868             :                           Offset, MaxAlign, Skew);
     869             :   }
     870             : 
     871             :   SmallVector<int, 8> ObjectsToAllocate;
     872             : 
     873             :   // Then prepare to assign frame offsets to stack objects that are not used to
     874             :   // spill callee saved registers.
     875      593443 :   for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
     876      374088 :     if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())
     877         446 :       continue;
     878      208476 :     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
     879       21997 :       continue;
     880      182677 :     if (RS && RS->isScavengingFrameIndex((int)i))
     881         540 :       continue;
     882      176655 :     if (MFI.isDeadObjectIndex(i))
     883       12817 :       continue;
     884      151830 :     if (MFI.getStackProtectorIndex() == (int)i ||
     885             :         EHRegNodeFrameIndex == (int)i)
     886         809 :       continue;
     887      151208 :     if (ProtectedObjs.count(i))
     888         996 :       continue;
     889             : 
     890             :     // Add the objects that we need to allocate to our working set.
     891      149216 :     ObjectsToAllocate.push_back(i);
     892             :   }
     893             : 
     894             :   // Allocate the EH registration node first if one is present.
     895      219801 :   if (EHRegNodeFrameIndex != std::numeric_limits<int>::max())
     896          32 :     AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,
     897             :                       MaxAlign, Skew);
     898             : 
     899             :   // Give the targets a chance to order the objects the way they like it.
     900      402992 :   if (MF.getTarget().getOptLevel() != CodeGenOpt::None &&
     901      183191 :       MF.getTarget().Options.StackSymbolOrdering)
     902      182768 :     TFI.orderFrameObjects(MF, ObjectsToAllocate);
     903             : 
     904             :   // Keep track of which bytes in the fixed and callee-save range are used so we
     905             :   // can use the holes when allocating later stack objects.  Only do this if
     906             :   // stack protector isn't being used and the target requests it and we're
     907             :   // optimizing.
     908             :   BitVector StackBytesFree;
     909      265434 :   if (!ObjectsToAllocate.empty() &&
     910       58684 :       MF.getTarget().getOptLevel() != CodeGenOpt::None &&
     911      245552 :       MFI.getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(MF))
     912         128 :     computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,
     913             :                           FixedCSEnd, StackBytesFree);
     914             : 
     915             :   // Now walk the objects and actually assign base offsets to them.
     916      518233 :   for (auto &Object : ObjectsToAllocate)
     917      149216 :     if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,
     918             :                            StackBytesFree))
     919      149195 :       AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew);
     920             : 
     921             :   // Make sure the special register scavenging spill slot is closest to the
     922             :   // stack pointer.
     923      219801 :   if (RS && !EarlyScavengingSlots) {
     924             :     SmallVector<int, 2> SFIs;
     925             :     RS->getScavengingFrameIndices(SFIs);
     926         518 :     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
     927       59914 :            IE = SFIs.end(); I != IE; ++I)
     928         518 :       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
     929             :   }
     930             : 
     931      219801 :   if (!TFI.targetHandlesStackFrameRounding()) {
     932             :     // If we have reserved argument space for call sites in the function
     933             :     // immediately on entry to the current function, count it as part of the
     934             :     // overall stack size.
     935      204953 :     if (MFI.adjustsStack() && TFI.hasReservedCallFrame(MF))
     936       37060 :       Offset += MFI.getMaxCallFrameSize();
     937             : 
     938             :     // Round up the size to a multiple of the alignment.  If the function has
     939             :     // any calls or alloca's, align to the target's StackAlignment value to
     940             :     // ensure that the callee's frame or the alloca data is suitably aligned;
     941             :     // otherwise, for leaf functions, align to the TransientStackAlignment
     942             :     // value.
     943             :     unsigned StackAlign;
     944      370664 :     if (MFI.adjustsStack() || MFI.hasVarSizedObjects() ||
     945      166899 :         (RegInfo->needsStackRealignment(MF) && MFI.getObjectIndexEnd() != 0))
     946       40367 :       StackAlign = TFI.getStackAlignment();
     947             :     else
     948      164586 :       StackAlign = TFI.getTransientStackAlignment();
     949             : 
     950             :     // If the frame pointer is eliminated, all frame offsets will be relative to
     951             :     // SP not FP. Align to MaxAlign so this works.
     952      204953 :     StackAlign = std::max(StackAlign, MaxAlign);
     953      409906 :     Offset = alignTo(Offset, StackAlign, Skew);
     954             :   }
     955             : 
     956             :   // Update frame info to pretend that this is part of the stack...
     957      219801 :   int64_t StackSize = Offset - LocalAreaOffset;
     958      219801 :   MFI.setStackSize(StackSize);
     959             :   NumBytesStackSpace += StackSize;
     960      219801 : }
     961             : 
     962             : /// insertPrologEpilogCode - Scan the function for modified callee saved
     963             : /// registers, insert spill code for these callee saved registers, then add
     964             : /// prolog and epilog code to the function.
     965      219721 : void PEI::insertPrologEpilogCode(MachineFunction &MF) {
     966      219721 :   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
     967             : 
     968             :   // Add prologue to the function...
     969      659397 :   for (MachineBasicBlock *SaveBlock : SaveBlocks)
     970      219843 :     TFI.emitPrologue(MF, *SaveBlock);
     971             : 
     972             :   // Add epilogue to restore the callee-save registers in each exiting block.
     973      662054 :   for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
     974      221169 :     TFI.emitEpilogue(MF, *RestoreBlock);
     975             : 
     976      659392 :   for (MachineBasicBlock *SaveBlock : SaveBlocks)
     977      219838 :     TFI.inlineStackProbe(MF, *SaveBlock);
     978             : 
     979             :   // Emit additional code that is required to support segmented stacks, if
     980             :   // we've been asked for it.  This, when linked with a runtime with support
     981             :   // for segmented stacks (libgcc is one), will result in allocating stack
     982             :   // space in small chunks instead of one large contiguous block.
     983      219716 :   if (MF.shouldSplitStack()) {
     984         719 :     for (MachineBasicBlock *SaveBlock : SaveBlocks)
     985         241 :       TFI.adjustForSegmentedStacks(MF, *SaveBlock);
     986             :     // Record that there are split-stack functions, so we will emit a
     987             :     // special section to tell the linker.
     988         239 :     MF.getMMI().setHasSplitStack(true);
     989             :   } else
     990      219475 :     MF.getMMI().setHasNosplitStack(true);
     991             : 
     992             :   // Emit additional code that is required to explicitly handle the stack in
     993             :   // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
     994             :   // approach is rather similar to that of Segmented Stacks, but it uses a
     995             :   // different conditional check and another BIF for allocating more stack
     996             :   // space.
     997      439428 :   if (MF.getFunction().getCallingConv() == CallingConv::HiPE)
     998          39 :     for (MachineBasicBlock *SaveBlock : SaveBlocks)
     999          13 :       TFI.adjustForHiPEPrologue(MF, *SaveBlock);
    1000      219714 : }
    1001             : 
    1002             : /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
    1003             : /// register references and actual offsets.
    1004      219794 : void PEI::replaceFrameIndices(MachineFunction &MF) {
    1005      219794 :   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
    1006      371638 :   if (!TFI.needsFrameIndexResolution(MF)) return;
    1007             : 
    1008             :   // Store SPAdj at exit of a basic block.
    1009             :   SmallVector<int, 8> SPState;
    1010       67950 :   SPState.resize(MF.getNumBlockIDs());
    1011             :   df_iterator_default_set<MachineBasicBlock*> Reachable;
    1012             : 
    1013             :   // Iterate over the reachable blocks in DFS order.
    1014       67950 :   for (auto DFI = df_ext_begin(&MF, Reachable), DFE = df_ext_end(&MF, Reachable);
    1015      318457 :        DFI != DFE; ++DFI) {
    1016      250507 :     int SPAdj = 0;
    1017             :     // Check the exit state of the DFS stack predecessor.
    1018      250507 :     if (DFI.getPathLength() >= 2) {
    1019      182557 :       MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
    1020             :       assert(Reachable.count(StackPred) &&
    1021             :              "DFS stack predecessor is already visited.\n");
    1022      365114 :       SPAdj = SPState[StackPred->getNumber()];
    1023             :     }
    1024      250507 :     MachineBasicBlock *BB = *DFI;
    1025      250507 :     replaceFrameIndices(BB, MF, SPAdj);
    1026      501014 :     SPState[BB->getNumber()] = SPAdj;
    1027             :   }
    1028             : 
    1029             :   // Handle the unreachable blocks.
    1030      318484 :   for (auto &BB : MF) {
    1031      250534 :     if (Reachable.count(&BB))
    1032             :       // Already handled in DFS traversal.
    1033      250507 :       continue;
    1034          27 :     int SPAdj = 0;
    1035          27 :     replaceFrameIndices(&BB, MF, SPAdj);
    1036             :   }
    1037             : }
    1038             : 
    1039      250534 : void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
    1040             :                               int &SPAdj) {
    1041             :   assert(MF.getSubtarget().getRegisterInfo() &&
    1042             :          "getRegisterInfo() must be implemented!");
    1043      250534 :   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
    1044      250534 :   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
    1045      250534 :   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
    1046             : 
    1047      250534 :   if (RS && FrameIndexEliminationScavenging)
    1048         363 :     RS->enterBasicBlock(*BB);
    1049             : 
    1050             :   bool InsideCallSequence = false;
    1051             : 
    1052     3825634 :   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
    1053       27168 :     if (TII.isFrameInstr(*I)) {
    1054             :       InsideCallSequence = TII.isFrameSetup(*I);
    1055       27168 :       SPAdj += TII.getSPAdjust(*I);
    1056       27168 :       I = TFI->eliminateCallFramePseudoInstr(MF, *BB, I);
    1057             :       continue;
    1058             :     }
    1059             : 
    1060             :     MachineInstr &MI = *I;
    1061             :     bool DoIncr = true;
    1062             :     bool DidFinishLoop = true;
    1063    31919576 :     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    1064    26231216 :       if (!MI.getOperand(i).isFI())
    1065             :         continue;
    1066             : 
    1067             :       // Frame indices in debug values are encoded in a target independent
    1068             :       // way with simply the frame index and offset rather than any
    1069             :       // target-specific addressing mode.
    1070      455174 :       if (MI.isDebugValue()) {
    1071             :         assert(i == 0 && "Frame indices can only appear as the first "
    1072             :                          "operand of a DBG_VALUE machine instruction");
    1073             :         unsigned Reg;
    1074             :         int64_t Offset =
    1075        1800 :             TFI->getFrameIndexReference(MF, MI.getOperand(0).getIndex(), Reg);
    1076        1800 :         MI.getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
    1077        1800 :         MI.getOperand(0).setIsDebug();
    1078        1800 :         auto *DIExpr = DIExpression::prepend(MI.getDebugExpression(),
    1079        1800 :                                              DIExpression::NoDeref, Offset);
    1080        1800 :         MI.getOperand(3).setMetadata(DIExpr);
    1081        1800 :         continue;
    1082             :       }
    1083             : 
    1084             :       // TODO: This code should be commoned with the code for
    1085             :       // PATCHPOINT. There's no good reason for the difference in
    1086             :       // implementation other than historical accident.  The only
    1087             :       // remaining difference is the unconditional use of the stack
    1088             :       // pointer as the base register.
    1089      453374 :       if (MI.getOpcode() == TargetOpcode::STATEPOINT) {
    1090             :         assert((!MI.isDebugValue() || i == 0) &&
    1091             :                "Frame indicies can only appear as the first operand of a "
    1092             :                "DBG_VALUE machine instruction");
    1093             :         unsigned Reg;
    1094         156 :         MachineOperand &Offset = MI.getOperand(i + 1);
    1095         156 :         int refOffset = TFI->getFrameIndexReferencePreferSP(
    1096         312 :             MF, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false);
    1097         156 :         Offset.setImm(Offset.getImm() + refOffset);
    1098         312 :         MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
    1099         156 :         continue;
    1100             :       }
    1101             : 
    1102             :       // Some instructions (e.g. inline asm instructions) can have
    1103             :       // multiple frame indices and/or cause eliminateFrameIndex
    1104             :       // to insert more than one instruction. We need the register
    1105             :       // scavenger to go through all of these instructions so that
    1106             :       // it can update its register information. We keep the
    1107             :       // iterator at the point before insertion so that we can
    1108             :       // revisit them in full.
    1109             :       bool AtBeginning = (I == BB->begin());
    1110      453218 :       if (!AtBeginning) --I;
    1111             : 
    1112             :       // If this instruction has a FrameIndex operand, we need to
    1113             :       // use that target machine register info object to eliminate
    1114             :       // it.
    1115      906436 :       TRI.eliminateFrameIndex(MI, SPAdj, i,
    1116      453218 :                               FrameIndexEliminationScavenging ?  RS : nullptr);
    1117             : 
    1118             :       // Reset the iterator if we were at the beginning of the BB.
    1119      453218 :       if (AtBeginning) {
    1120       44360 :         I = BB->begin();
    1121             :         DoIncr = false;
    1122             :       }
    1123             : 
    1124             :       DidFinishLoop = false;
    1125             :       break;
    1126             :     }
    1127             : 
    1128             :     // If we are looking at a call sequence, we need to keep track of
    1129             :     // the SP adjustment made by each instruction in the sequence.
    1130             :     // This includes both the frame setup/destroy pseudos (handled above),
    1131             :     // as well as other instructions that have side effects w.r.t the SP.
    1132             :     // Note that this must come after eliminateFrameIndex, because
    1133             :     // if I itself referred to a frame index, we shouldn't count its own
    1134             :     // adjustment.
    1135     3297398 :     if (DidFinishLoop && InsideCallSequence)
    1136       74430 :       SPAdj += TII.getSPAdjust(MI);
    1137             : 
    1138     6550436 :     if (DoIncr && I != BB->end()) ++I;
    1139             : 
    1140             :     // Update register states.
    1141     3297398 :     if (RS && FrameIndexEliminationScavenging && DidFinishLoop)
    1142        4674 :       RS->forward(MI);
    1143             :   }
    1144      549763 : }

Generated by: LCOV version 1.13