xref: /llvm-project/llvm/lib/CodeGen/PrologEpilogInserter.cpp (revision c3df69faa03404ad912f4f613edc19c067ab91f6)
1 //===- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass is responsible for finalizing the functions frame layout, saving
10 // callee saved registers, and for emitting prolog & epilog code for the
11 // function.
12 //
13 // This pass must be run after register allocation.  After this pass is
14 // executed, it is illegal to construct MO_FrameIndex operands.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
28 #include "llvm/CodeGen/MachineBasicBlock.h"
29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFrameInfo.h"
31 #include "llvm/CodeGen/MachineFunction.h"
32 #include "llvm/CodeGen/MachineFunctionPass.h"
33 #include "llvm/CodeGen/MachineInstr.h"
34 #include "llvm/CodeGen/MachineInstrBuilder.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/TargetFrameLowering.h"
42 #include "llvm/CodeGen/TargetInstrInfo.h"
43 #include "llvm/CodeGen/TargetOpcodes.h"
44 #include "llvm/CodeGen/TargetRegisterInfo.h"
45 #include "llvm/CodeGen/TargetSubtargetInfo.h"
46 #include "llvm/CodeGen/WinEHFuncInfo.h"
47 #include "llvm/IR/Attributes.h"
48 #include "llvm/IR/CallingConv.h"
49 #include "llvm/IR/DebugInfoMetadata.h"
50 #include "llvm/IR/DiagnosticInfo.h"
51 #include "llvm/IR/Function.h"
52 #include "llvm/IR/InlineAsm.h"
53 #include "llvm/IR/LLVMContext.h"
54 #include "llvm/InitializePasses.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 STATISTIC(NumLeafFuncWithSpills, "Number of leaf functions with CSRs");
80 STATISTIC(NumFuncSeen, "Number of functions seen in PEI");
81 
82 
83 namespace {
84 
85 class PEI : public MachineFunctionPass {
86 public:
87   static char ID;
88 
89   PEI() : MachineFunctionPass(ID) {
90     initializePEIPass(*PassRegistry::getPassRegistry());
91   }
92 
93   void getAnalysisUsage(AnalysisUsage &AU) const override;
94 
95   /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
96   /// frame indexes with appropriate references.
97   bool runOnMachineFunction(MachineFunction &MF) override;
98 
99 private:
100   RegScavenger *RS;
101 
102   // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
103   // stack frame indexes.
104   unsigned MinCSFrameIndex = std::numeric_limits<unsigned>::max();
105   unsigned MaxCSFrameIndex = 0;
106 
107   // Save and Restore blocks of the current function. Typically there is a
108   // single save block, unless Windows EH funclets are involved.
109   MBBVector SaveBlocks;
110   MBBVector RestoreBlocks;
111 
112   // Flag to control whether to use the register scavenger to resolve
113   // frame index materialization registers. Set according to
114   // TRI->requiresFrameIndexScavenging() for the current function.
115   bool FrameIndexVirtualScavenging;
116 
117   // Flag to control whether the scavenger should be passed even though
118   // FrameIndexVirtualScavenging is used.
119   bool FrameIndexEliminationScavenging;
120 
121   // Emit remarks.
122   MachineOptimizationRemarkEmitter *ORE = nullptr;
123 
124   void calculateCallFrameInfo(MachineFunction &MF);
125   void calculateSaveRestoreBlocks(MachineFunction &MF);
126   void spillCalleeSavedRegs(MachineFunction &MF);
127 
128   void calculateFrameObjectOffsets(MachineFunction &MF);
129   void replaceFrameIndices(MachineFunction &MF);
130   void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
131                            int &SPAdj);
132   void insertPrologEpilogCode(MachineFunction &MF);
133 };
134 
135 } // end anonymous namespace
136 
137 char PEI::ID = 0;
138 
139 char &llvm::PrologEpilogCodeInserterID = PEI::ID;
140 
141 static cl::opt<unsigned>
142 WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
143               cl::desc("Warn for stack size bigger than the given"
144                        " number"));
145 
146 INITIALIZE_PASS_BEGIN(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion", false,
147                       false)
148 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
149 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
150 INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
151 INITIALIZE_PASS_END(PEI, DEBUG_TYPE,
152                     "Prologue/Epilogue Insertion & Frame Finalization", false,
153                     false)
154 
155 MachineFunctionPass *llvm::createPrologEpilogInserterPass() {
156   return new PEI();
157 }
158 
159 STATISTIC(NumBytesStackSpace,
160           "Number of bytes used for stack in all functions");
161 
162 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
163   AU.setPreservesCFG();
164   AU.addPreserved<MachineLoopInfo>();
165   AU.addPreserved<MachineDominatorTree>();
166   AU.addRequired<MachineOptimizationRemarkEmitterPass>();
167   MachineFunctionPass::getAnalysisUsage(AU);
168 }
169 
170 /// StackObjSet - A set of stack object indexes
171 using StackObjSet = SmallSetVector<int, 8>;
172 
173 using SavedDbgValuesMap =
174     SmallDenseMap<MachineBasicBlock *, SmallVector<MachineInstr *, 4>, 4>;
175 
176 /// Stash DBG_VALUEs that describe parameters and which are placed at the start
177 /// of the block. Later on, after the prologue code has been emitted, the
178 /// stashed DBG_VALUEs will be reinserted at the start of the block.
179 static void stashEntryDbgValues(MachineBasicBlock &MBB,
180                                 SavedDbgValuesMap &EntryDbgValues) {
181   SmallVector<const MachineInstr *, 4> FrameIndexValues;
182 
183   for (auto &MI : MBB) {
184     if (!MI.isDebugInstr())
185       break;
186     if (!MI.isDebugValue() || !MI.getDebugVariable()->isParameter())
187       continue;
188     if (MI.getOperand(0).isFI()) {
189       // We can only emit valid locations for frame indices after the frame
190       // setup, so do not stash away them.
191       FrameIndexValues.push_back(&MI);
192       continue;
193     }
194     const DILocalVariable *Var = MI.getDebugVariable();
195     const DIExpression *Expr = MI.getDebugExpression();
196     auto Overlaps = [Var, Expr](const MachineInstr *DV) {
197       return Var == DV->getDebugVariable() &&
198              Expr->fragmentsOverlap(DV->getDebugExpression());
199     };
200     // See if the debug value overlaps with any preceding debug value that will
201     // not be stashed. If that is the case, then we can't stash this value, as
202     // we would then reorder the values at reinsertion.
203     if (llvm::none_of(FrameIndexValues, Overlaps))
204       EntryDbgValues[&MBB].push_back(&MI);
205   }
206 
207   // Remove stashed debug values from the block.
208   if (EntryDbgValues.count(&MBB))
209     for (auto *MI : EntryDbgValues[&MBB])
210       MI->removeFromParent();
211 }
212 
213 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
214 /// frame indexes with appropriate references.
215 bool PEI::runOnMachineFunction(MachineFunction &MF) {
216   NumFuncSeen++;
217   const Function &F = MF.getFunction();
218   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
219   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
220 
221   RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr;
222   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(MF);
223   ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
224 
225   // Calculate the MaxCallFrameSize and AdjustsStack variables for the
226   // function's frame information. Also eliminates call frame pseudo
227   // instructions.
228   calculateCallFrameInfo(MF);
229 
230   // Determine placement of CSR spill/restore code and prolog/epilog code:
231   // place all spills in the entry block, all restores in return blocks.
232   calculateSaveRestoreBlocks(MF);
233 
234   // Stash away DBG_VALUEs that should not be moved by insertion of prolog code.
235   SavedDbgValuesMap EntryDbgValues;
236   for (MachineBasicBlock *SaveBlock : SaveBlocks)
237     stashEntryDbgValues(*SaveBlock, EntryDbgValues);
238 
239   // Handle CSR spilling and restoring, for targets that need it.
240   if (MF.getTarget().usesPhysRegsForValues())
241     spillCalleeSavedRegs(MF);
242 
243   // Allow the target machine to make final modifications to the function
244   // before the frame layout is finalized.
245   TFI->processFunctionBeforeFrameFinalized(MF, RS);
246 
247   // Calculate actual frame offsets for all abstract stack objects...
248   calculateFrameObjectOffsets(MF);
249 
250   // Add prolog and epilog code to the function.  This function is required
251   // to align the stack frame as necessary for any stack variables or
252   // called functions.  Because of this, calculateCalleeSavedRegisters()
253   // must be called before this function in order to set the AdjustsStack
254   // and MaxCallFrameSize variables.
255   if (!F.hasFnAttribute(Attribute::Naked))
256     insertPrologEpilogCode(MF);
257 
258   // Reinsert stashed debug values at the start of the entry blocks.
259   for (auto &I : EntryDbgValues)
260     I.first->insert(I.first->begin(), I.second.begin(), I.second.end());
261 
262   // Allow the target machine to make final modifications to the function
263   // before the frame layout is finalized.
264   TFI->processFunctionBeforeFrameIndicesReplaced(MF, RS);
265 
266   // Replace all MO_FrameIndex operands with physical register references
267   // and actual offsets.
268   //
269   replaceFrameIndices(MF);
270 
271   // If register scavenging is needed, as we've enabled doing it as a
272   // post-pass, scavenge the virtual registers that frame index elimination
273   // inserted.
274   if (TRI->requiresRegisterScavenging(MF) && FrameIndexVirtualScavenging)
275     scavengeFrameVirtualRegs(MF, *RS);
276 
277   // Warn on stack size when we exceeds the given limit.
278   MachineFrameInfo &MFI = MF.getFrameInfo();
279   uint64_t StackSize = MFI.getStackSize();
280   if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
281     DiagnosticInfoStackSize DiagStackSize(F, StackSize);
282     F.getContext().diagnose(DiagStackSize);
283   }
284   ORE->emit([&]() {
285     return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize",
286                                              MF.getFunction().getSubprogram(),
287                                              &MF.front())
288            << ore::NV("NumStackBytes", StackSize) << " stack bytes in function";
289   });
290 
291   delete RS;
292   SaveBlocks.clear();
293   RestoreBlocks.clear();
294   MFI.setSavePoint(nullptr);
295   MFI.setRestorePoint(nullptr);
296   return true;
297 }
298 
299 /// Calculate the MaxCallFrameSize and AdjustsStack
300 /// variables for the function's frame information and eliminate call frame
301 /// pseudo instructions.
302 void PEI::calculateCallFrameInfo(MachineFunction &MF) {
303   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
304   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
305   MachineFrameInfo &MFI = MF.getFrameInfo();
306 
307   unsigned MaxCallFrameSize = 0;
308   bool AdjustsStack = MFI.adjustsStack();
309 
310   // Get the function call frame set-up and tear-down instruction opcode
311   unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
312   unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
313 
314   // Early exit for targets which have no call frame setup/destroy pseudo
315   // instructions.
316   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
317     return;
318 
319   std::vector<MachineBasicBlock::iterator> FrameSDOps;
320   for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)
321     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
322       if (TII.isFrameInstr(*I)) {
323         unsigned Size = TII.getFrameSize(*I);
324         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
325         AdjustsStack = true;
326         FrameSDOps.push_back(I);
327       } else if (I->isInlineAsm()) {
328         // Some inline asm's need a stack frame, as indicated by operand 1.
329         unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
330         if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
331           AdjustsStack = true;
332       }
333 
334   assert(!MFI.isMaxCallFrameSizeComputed() ||
335          (MFI.getMaxCallFrameSize() == MaxCallFrameSize &&
336           MFI.adjustsStack() == AdjustsStack));
337   MFI.setAdjustsStack(AdjustsStack);
338   MFI.setMaxCallFrameSize(MaxCallFrameSize);
339 
340   for (std::vector<MachineBasicBlock::iterator>::iterator
341          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
342     MachineBasicBlock::iterator I = *i;
343 
344     // If call frames are not being included as part of the stack frame, and
345     // the target doesn't indicate otherwise, remove the call frame pseudos
346     // here. The sub/add sp instruction pairs are still inserted, but we don't
347     // need to track the SP adjustment for frame index elimination.
348     if (TFI->canSimplifyCallFramePseudos(MF))
349       TFI->eliminateCallFramePseudoInstr(MF, *I->getParent(), I);
350   }
351 }
352 
353 /// Compute the sets of entry and return blocks for saving and restoring
354 /// callee-saved registers, and placing prolog and epilog code.
355 void PEI::calculateSaveRestoreBlocks(MachineFunction &MF) {
356   const MachineFrameInfo &MFI = MF.getFrameInfo();
357 
358   // Even when we do not change any CSR, we still want to insert the
359   // prologue and epilogue of the function.
360   // So set the save points for those.
361 
362   // Use the points found by shrink-wrapping, if any.
363   if (MFI.getSavePoint()) {
364     SaveBlocks.push_back(MFI.getSavePoint());
365     assert(MFI.getRestorePoint() && "Both restore and save must be set");
366     MachineBasicBlock *RestoreBlock = MFI.getRestorePoint();
367     // If RestoreBlock does not have any successor and is not a return block
368     // then the end point is unreachable and we do not need to insert any
369     // epilogue.
370     if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock())
371       RestoreBlocks.push_back(RestoreBlock);
372     return;
373   }
374 
375   // Save refs to entry and return blocks.
376   SaveBlocks.push_back(&MF.front());
377   for (MachineBasicBlock &MBB : MF) {
378     if (MBB.isEHFuncletEntry())
379       SaveBlocks.push_back(&MBB);
380     if (MBB.isReturnBlock())
381       RestoreBlocks.push_back(&MBB);
382   }
383 }
384 
385 static void assignCalleeSavedSpillSlots(MachineFunction &F,
386                                         const BitVector &SavedRegs,
387                                         unsigned &MinCSFrameIndex,
388                                         unsigned &MaxCSFrameIndex) {
389   if (SavedRegs.empty())
390     return;
391 
392   const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();
393   const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs();
394 
395   std::vector<CalleeSavedInfo> CSI;
396   for (unsigned i = 0; CSRegs[i]; ++i) {
397     unsigned Reg = CSRegs[i];
398     if (SavedRegs.test(Reg))
399       CSI.push_back(CalleeSavedInfo(Reg));
400   }
401 
402   const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();
403   MachineFrameInfo &MFI = F.getFrameInfo();
404   if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
405     // If target doesn't implement this, use generic code.
406 
407     if (CSI.empty())
408       return; // Early exit if no callee saved registers are modified!
409 
410     unsigned NumFixedSpillSlots;
411     const TargetFrameLowering::SpillSlot *FixedSpillSlots =
412         TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
413 
414     // Now that we know which registers need to be saved and restored, allocate
415     // stack slots for them.
416     for (auto &CS : CSI) {
417       // If the target has spilled this register to another register, we don't
418       // need to allocate a stack slot.
419       if (CS.isSpilledToReg())
420         continue;
421 
422       unsigned Reg = CS.getReg();
423       const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
424 
425       int FrameIdx;
426       if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {
427         CS.setFrameIdx(FrameIdx);
428         continue;
429       }
430 
431       // Check to see if this physreg must be spilled to a particular stack slot
432       // on this target.
433       const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;
434       while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
435              FixedSlot->Reg != Reg)
436         ++FixedSlot;
437 
438       unsigned Size = RegInfo->getSpillSize(*RC);
439       if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
440         // Nope, just spill it anywhere convenient.
441         unsigned Align = RegInfo->getSpillAlignment(*RC);
442         unsigned StackAlign = TFI->getStackAlignment();
443 
444         // We may not be able to satisfy the desired alignment specification of
445         // the TargetRegisterClass if the stack alignment is smaller. Use the
446         // min.
447         Align = std::min(Align, StackAlign);
448         FrameIdx = MFI.CreateStackObject(Size, Align, true);
449         if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
450         if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
451       } else {
452         // Spill it to the stack where we must.
453         FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset);
454       }
455 
456       CS.setFrameIdx(FrameIdx);
457     }
458   }
459 
460   MFI.setCalleeSavedInfo(CSI);
461 }
462 
463 /// Helper function to update the liveness information for the callee-saved
464 /// registers.
465 static void updateLiveness(MachineFunction &MF) {
466   MachineFrameInfo &MFI = MF.getFrameInfo();
467   // Visited will contain all the basic blocks that are in the region
468   // where the callee saved registers are alive:
469   // - Anything that is not Save or Restore -> LiveThrough.
470   // - Save -> LiveIn.
471   // - Restore -> LiveOut.
472   // The live-out is not attached to the block, so no need to keep
473   // Restore in this set.
474   SmallPtrSet<MachineBasicBlock *, 8> Visited;
475   SmallVector<MachineBasicBlock *, 8> WorkList;
476   MachineBasicBlock *Entry = &MF.front();
477   MachineBasicBlock *Save = MFI.getSavePoint();
478 
479   if (!Save)
480     Save = Entry;
481 
482   if (Entry != Save) {
483     WorkList.push_back(Entry);
484     Visited.insert(Entry);
485   }
486   Visited.insert(Save);
487 
488   MachineBasicBlock *Restore = MFI.getRestorePoint();
489   if (Restore)
490     // By construction Restore cannot be visited, otherwise it
491     // means there exists a path to Restore that does not go
492     // through Save.
493     WorkList.push_back(Restore);
494 
495   while (!WorkList.empty()) {
496     const MachineBasicBlock *CurBB = WorkList.pop_back_val();
497     // By construction, the region that is after the save point is
498     // dominated by the Save and post-dominated by the Restore.
499     if (CurBB == Save && Save != Restore)
500       continue;
501     // Enqueue all the successors not already visited.
502     // Those are by construction either before Save or after Restore.
503     for (MachineBasicBlock *SuccBB : CurBB->successors())
504       if (Visited.insert(SuccBB).second)
505         WorkList.push_back(SuccBB);
506   }
507 
508   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
509 
510   MachineRegisterInfo &MRI = MF.getRegInfo();
511   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
512     for (MachineBasicBlock *MBB : Visited) {
513       MCPhysReg Reg = CSI[i].getReg();
514       // Add the callee-saved register as live-in.
515       // It's killed at the spill.
516       if (!MRI.isReserved(Reg) && !MBB->isLiveIn(Reg))
517         MBB->addLiveIn(Reg);
518     }
519     // If callee-saved register is spilled to another register rather than
520     // spilling to stack, the destination register has to be marked as live for
521     // each MBB between the prologue and epilogue so that it is not clobbered
522     // before it is reloaded in the epilogue. The Visited set contains all
523     // blocks outside of the region delimited by prologue/epilogue.
524     if (CSI[i].isSpilledToReg()) {
525       for (MachineBasicBlock &MBB : MF) {
526         if (Visited.count(&MBB))
527           continue;
528         MCPhysReg DstReg = CSI[i].getDstReg();
529         if (!MBB.isLiveIn(DstReg))
530           MBB.addLiveIn(DstReg);
531       }
532     }
533   }
534 
535 }
536 
537 /// Insert restore code for the callee-saved registers used in the function.
538 static void insertCSRSaves(MachineBasicBlock &SaveBlock,
539                            ArrayRef<CalleeSavedInfo> CSI) {
540   MachineFunction &MF = *SaveBlock.getParent();
541   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
542   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
543   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
544 
545   MachineBasicBlock::iterator I = SaveBlock.begin();
546   if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) {
547     for (const CalleeSavedInfo &CS : CSI) {
548       // Insert the spill to the stack frame.
549       unsigned Reg = CS.getReg();
550 
551       if (CS.isSpilledToReg()) {
552         BuildMI(SaveBlock, I, DebugLoc(),
553                 TII.get(TargetOpcode::COPY), CS.getDstReg())
554           .addReg(Reg, getKillRegState(true));
555       } else {
556         const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
557         TII.storeRegToStackSlot(SaveBlock, I, Reg, true, CS.getFrameIdx(), RC,
558                                 TRI);
559       }
560     }
561   }
562 }
563 
564 /// Insert restore code for the callee-saved registers used in the function.
565 static void insertCSRRestores(MachineBasicBlock &RestoreBlock,
566                               std::vector<CalleeSavedInfo> &CSI) {
567   MachineFunction &MF = *RestoreBlock.getParent();
568   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
569   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
570   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
571 
572   // Restore all registers immediately before the return and any
573   // terminators that precede it.
574   MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator();
575 
576   if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) {
577     for (const CalleeSavedInfo &CI : reverse(CSI)) {
578       unsigned Reg = CI.getReg();
579       if (CI.isSpilledToReg()) {
580         BuildMI(RestoreBlock, I, DebugLoc(), TII.get(TargetOpcode::COPY), Reg)
581           .addReg(CI.getDstReg(), getKillRegState(true));
582       } else {
583         const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
584         TII.loadRegFromStackSlot(RestoreBlock, I, Reg, CI.getFrameIdx(), RC, TRI);
585         assert(I != RestoreBlock.begin() &&
586                "loadRegFromStackSlot didn't insert any code!");
587         // Insert in reverse order.  loadRegFromStackSlot can insert
588         // multiple instructions.
589       }
590     }
591   }
592 }
593 
594 void PEI::spillCalleeSavedRegs(MachineFunction &MF) {
595   // We can't list this requirement in getRequiredProperties because some
596   // targets (WebAssembly) use virtual registers past this point, and the pass
597   // pipeline is set up without giving the passes a chance to look at the
598   // TargetMachine.
599   // FIXME: Find a way to express this in getRequiredProperties.
600   assert(MF.getProperties().hasProperty(
601       MachineFunctionProperties::Property::NoVRegs));
602 
603   const Function &F = MF.getFunction();
604   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
605   MachineFrameInfo &MFI = MF.getFrameInfo();
606   MinCSFrameIndex = std::numeric_limits<unsigned>::max();
607   MaxCSFrameIndex = 0;
608 
609   // Determine which of the registers in the callee save list should be saved.
610   BitVector SavedRegs;
611   TFI->determineCalleeSaves(MF, SavedRegs, RS);
612 
613   // Assign stack slots for any callee-saved registers that must be spilled.
614   assignCalleeSavedSpillSlots(MF, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);
615 
616   // Add the code to save and restore the callee saved registers.
617   if (!F.hasFnAttribute(Attribute::Naked)) {
618     MFI.setCalleeSavedInfoValid(true);
619 
620     std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
621     if (!CSI.empty()) {
622       if (!MFI.hasCalls())
623         NumLeafFuncWithSpills++;
624 
625       for (MachineBasicBlock *SaveBlock : SaveBlocks) {
626         insertCSRSaves(*SaveBlock, CSI);
627         // Update the live-in information of all the blocks up to the save
628         // point.
629         updateLiveness(MF);
630       }
631       for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
632         insertCSRRestores(*RestoreBlock, CSI);
633     }
634   }
635 }
636 
637 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
638 static inline void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,
639                                      bool StackGrowsDown, int64_t &Offset,
640                                      Align &MaxAlign, unsigned Skew) {
641   // If the stack grows down, add the object size to find the lowest address.
642   if (StackGrowsDown)
643     Offset += MFI.getObjectSize(FrameIdx);
644 
645   Align Alignment = MFI.getObjectAlign(FrameIdx);
646 
647   // If the alignment of this object is greater than that of the stack, then
648   // increase the stack alignment to match.
649   MaxAlign = std::max(MaxAlign, Alignment);
650 
651   // Adjust to alignment boundary.
652   Offset = alignTo(Offset, Alignment, Skew);
653 
654   if (StackGrowsDown) {
655     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset
656                       << "]\n");
657     MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset
658   } else {
659     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset
660                       << "]\n");
661     MFI.setObjectOffset(FrameIdx, Offset);
662     Offset += MFI.getObjectSize(FrameIdx);
663   }
664 }
665 
666 /// Compute which bytes of fixed and callee-save stack area are unused and keep
667 /// track of them in StackBytesFree.
668 static inline void
669 computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown,
670                       unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,
671                       int64_t FixedCSEnd, BitVector &StackBytesFree) {
672   // Avoid undefined int64_t -> int conversion below in extreme case.
673   if (FixedCSEnd > std::numeric_limits<int>::max())
674     return;
675 
676   StackBytesFree.resize(FixedCSEnd, true);
677 
678   SmallVector<int, 16> AllocatedFrameSlots;
679   // Add fixed objects.
680   for (int i = MFI.getObjectIndexBegin(); i != 0; ++i)
681     // StackSlot scavenging is only implemented for the default stack.
682     if (MFI.getStackID(i) == TargetStackID::Default)
683       AllocatedFrameSlots.push_back(i);
684   // Add callee-save objects.
685   for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i)
686     if (MFI.getStackID(i) == TargetStackID::Default)
687       AllocatedFrameSlots.push_back(i);
688 
689   for (int i : AllocatedFrameSlots) {
690     // These are converted from int64_t, but they should always fit in int
691     // because of the FixedCSEnd check above.
692     int ObjOffset = MFI.getObjectOffset(i);
693     int ObjSize = MFI.getObjectSize(i);
694     int ObjStart, ObjEnd;
695     if (StackGrowsDown) {
696       // ObjOffset is negative when StackGrowsDown is true.
697       ObjStart = -ObjOffset - ObjSize;
698       ObjEnd = -ObjOffset;
699     } else {
700       ObjStart = ObjOffset;
701       ObjEnd = ObjOffset + ObjSize;
702     }
703     // Ignore fixed holes that are in the previous stack frame.
704     if (ObjEnd > 0)
705       StackBytesFree.reset(ObjStart, ObjEnd);
706   }
707 }
708 
709 /// Assign frame object to an unused portion of the stack in the fixed stack
710 /// object range.  Return true if the allocation was successful.
711 static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx,
712                                      bool StackGrowsDown, Align MaxAlign,
713                                      BitVector &StackBytesFree) {
714   if (MFI.isVariableSizedObjectIndex(FrameIdx))
715     return false;
716 
717   if (StackBytesFree.none()) {
718     // clear it to speed up later scavengeStackSlot calls to
719     // StackBytesFree.none()
720     StackBytesFree.clear();
721     return false;
722   }
723 
724   Align ObjAlign = MFI.getObjectAlign(FrameIdx);
725   if (ObjAlign > MaxAlign)
726     return false;
727 
728   int64_t ObjSize = MFI.getObjectSize(FrameIdx);
729   int FreeStart;
730   for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;
731        FreeStart = StackBytesFree.find_next(FreeStart)) {
732 
733     // Check that free space has suitable alignment.
734     unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart;
735     if (alignTo(ObjStart, ObjAlign) != ObjStart)
736       continue;
737 
738     if (FreeStart + ObjSize > StackBytesFree.size())
739       return false;
740 
741     bool AllBytesFree = true;
742     for (unsigned Byte = 0; Byte < ObjSize; ++Byte)
743       if (!StackBytesFree.test(FreeStart + Byte)) {
744         AllBytesFree = false;
745         break;
746       }
747     if (AllBytesFree)
748       break;
749   }
750 
751   if (FreeStart == -1)
752     return false;
753 
754   if (StackGrowsDown) {
755     int ObjStart = -(FreeStart + ObjSize);
756     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["
757                       << ObjStart << "]\n");
758     MFI.setObjectOffset(FrameIdx, ObjStart);
759   } else {
760     LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["
761                       << FreeStart << "]\n");
762     MFI.setObjectOffset(FrameIdx, FreeStart);
763   }
764 
765   StackBytesFree.reset(FreeStart, FreeStart + ObjSize);
766   return true;
767 }
768 
769 /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
770 /// those required to be close to the Stack Protector) to stack offsets.
771 static void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
772                                   SmallSet<int, 16> &ProtectedObjs,
773                                   MachineFrameInfo &MFI, bool StackGrowsDown,
774                                   int64_t &Offset, Align &MaxAlign,
775                                   unsigned Skew) {
776 
777   for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
778         E = UnassignedObjs.end(); I != E; ++I) {
779     int i = *I;
780     AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew);
781     ProtectedObjs.insert(i);
782   }
783 }
784 
785 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
786 /// abstract stack objects.
787 void PEI::calculateFrameObjectOffsets(MachineFunction &MF) {
788   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
789 
790   bool StackGrowsDown =
791     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
792 
793   // Loop over all of the stack objects, assigning sequential addresses...
794   MachineFrameInfo &MFI = MF.getFrameInfo();
795 
796   // Start at the beginning of the local area.
797   // The Offset is the distance from the stack top in the direction
798   // of stack growth -- so it's always nonnegative.
799   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
800   if (StackGrowsDown)
801     LocalAreaOffset = -LocalAreaOffset;
802   assert(LocalAreaOffset >= 0
803          && "Local area offset should be in direction of stack growth");
804   int64_t Offset = LocalAreaOffset;
805 
806   // Skew to be applied to alignment.
807   unsigned Skew = TFI.getStackAlignmentSkew(MF);
808 
809 #ifdef EXPENSIVE_CHECKS
810   for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i)
811     if (!MFI.isDeadObjectIndex(i) &&
812         MFI.getStackID(i) == TargetStackID::Default)
813       assert(MFI.getObjectAlignment(i) <= MFI.getMaxAlignment() &&
814              "MaxAlignment is invalid");
815 #endif
816 
817   // If there are fixed sized objects that are preallocated in the local area,
818   // non-fixed objects can't be allocated right at the start of local area.
819   // Adjust 'Offset' to point to the end of last fixed sized preallocated
820   // object.
821   for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) {
822     if (MFI.getStackID(i) !=
823         TargetStackID::Default) // Only allocate objects on the default stack.
824       continue;
825 
826     int64_t FixedOff;
827     if (StackGrowsDown) {
828       // The maximum distance from the stack pointer is at lower address of
829       // the object -- which is given by offset. For down growing stack
830       // the offset is negative, so we negate the offset to get the distance.
831       FixedOff = -MFI.getObjectOffset(i);
832     } else {
833       // The maximum distance from the start pointer is at the upper
834       // address of the object.
835       FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i);
836     }
837     if (FixedOff > Offset) Offset = FixedOff;
838   }
839 
840   // First assign frame offsets to stack objects that are used to spill
841   // callee saved registers.
842   if (StackGrowsDown) {
843     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
844       if (MFI.getStackID(i) !=
845           TargetStackID::Default) // Only allocate objects on the default stack.
846         continue;
847 
848       // If the stack grows down, we need to add the size to find the lowest
849       // address of the object.
850       Offset += MFI.getObjectSize(i);
851 
852       // Adjust to alignment boundary
853       Offset = alignTo(Offset, MFI.getObjectAlign(i), Skew);
854 
855       LLVM_DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << -Offset << "]\n");
856       MFI.setObjectOffset(i, -Offset);        // Set the computed offset
857     }
858   } else if (MaxCSFrameIndex >= MinCSFrameIndex) {
859     // Be careful about underflow in comparisons agains MinCSFrameIndex.
860     for (unsigned i = MaxCSFrameIndex; i != MinCSFrameIndex - 1; --i) {
861       if (MFI.getStackID(i) !=
862           TargetStackID::Default) // Only allocate objects on the default stack.
863         continue;
864 
865       if (MFI.isDeadObjectIndex(i))
866         continue;
867 
868       // Adjust to alignment boundary
869       Offset = alignTo(Offset, MFI.getObjectAlign(i), Skew);
870 
871       LLVM_DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << Offset << "]\n");
872       MFI.setObjectOffset(i, Offset);
873       Offset += MFI.getObjectSize(i);
874     }
875   }
876 
877   // FixedCSEnd is the stack offset to the end of the fixed and callee-save
878   // stack area.
879   int64_t FixedCSEnd = Offset;
880   Align MaxAlign = MFI.getMaxAlign();
881 
882   // Make sure the special register scavenging spill slot is closest to the
883   // incoming stack pointer if a frame pointer is required and is closer
884   // to the incoming rather than the final stack pointer.
885   const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
886   bool EarlyScavengingSlots = (TFI.hasFP(MF) &&
887                                TFI.isFPCloseToIncomingSP() &&
888                                RegInfo->useFPForScavengingIndex(MF) &&
889                                !RegInfo->needsStackRealignment(MF));
890   if (RS && EarlyScavengingSlots) {
891     SmallVector<int, 2> SFIs;
892     RS->getScavengingFrameIndices(SFIs);
893     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
894            IE = SFIs.end(); I != IE; ++I)
895       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
896   }
897 
898   // FIXME: Once this is working, then enable flag will change to a target
899   // check for whether the frame is large enough to want to use virtual
900   // frame index registers. Functions which don't want/need this optimization
901   // will continue to use the existing code path.
902   if (MFI.getUseLocalStackAllocationBlock()) {
903     Align Alignment = MFI.getLocalFrameMaxAlign();
904 
905     // Adjust to alignment boundary.
906     Offset = alignTo(Offset, Alignment, Skew);
907 
908     LLVM_DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
909 
910     // Resolve offsets for objects in the local block.
911     for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; ++i) {
912       std::pair<int, int64_t> Entry = MFI.getLocalFrameObjectMap(i);
913       int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
914       LLVM_DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << FIOffset
915                         << "]\n");
916       MFI.setObjectOffset(Entry.first, FIOffset);
917     }
918     // Allocate the local block
919     Offset += MFI.getLocalFrameSize();
920 
921     MaxAlign = std::max(Alignment, MaxAlign);
922   }
923 
924   // Retrieve the Exception Handler registration node.
925   int EHRegNodeFrameIndex = std::numeric_limits<int>::max();
926   if (const WinEHFuncInfo *FuncInfo = MF.getWinEHFuncInfo())
927     EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;
928 
929   // Make sure that the stack protector comes before the local variables on the
930   // stack.
931   SmallSet<int, 16> ProtectedObjs;
932   if (MFI.hasStackProtectorIndex()) {
933     int StackProtectorFI = MFI.getStackProtectorIndex();
934     StackObjSet LargeArrayObjs;
935     StackObjSet SmallArrayObjs;
936     StackObjSet AddrOfObjs;
937 
938     // If we need a stack protector, we need to make sure that
939     // LocalStackSlotPass didn't already allocate a slot for it.
940     // If we are told to use the LocalStackAllocationBlock, the stack protector
941     // is expected to be already pre-allocated.
942     if (!MFI.getUseLocalStackAllocationBlock())
943       AdjustStackOffset(MFI, StackProtectorFI, StackGrowsDown, Offset, MaxAlign,
944                         Skew);
945     else if (!MFI.isObjectPreAllocated(MFI.getStackProtectorIndex()))
946       llvm_unreachable(
947           "Stack protector not pre-allocated by LocalStackSlotPass.");
948 
949     // Assign large stack objects first.
950     for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
951       if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())
952         continue;
953       if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
954         continue;
955       if (RS && RS->isScavengingFrameIndex((int)i))
956         continue;
957       if (MFI.isDeadObjectIndex(i))
958         continue;
959       if (StackProtectorFI == (int)i || EHRegNodeFrameIndex == (int)i)
960         continue;
961       if (MFI.getStackID(i) !=
962           TargetStackID::Default) // Only allocate objects on the default stack.
963         continue;
964 
965       switch (MFI.getObjectSSPLayout(i)) {
966       case MachineFrameInfo::SSPLK_None:
967         continue;
968       case MachineFrameInfo::SSPLK_SmallArray:
969         SmallArrayObjs.insert(i);
970         continue;
971       case MachineFrameInfo::SSPLK_AddrOf:
972         AddrOfObjs.insert(i);
973         continue;
974       case MachineFrameInfo::SSPLK_LargeArray:
975         LargeArrayObjs.insert(i);
976         continue;
977       }
978       llvm_unreachable("Unexpected SSPLayoutKind.");
979     }
980 
981     // We expect **all** the protected stack objects to be pre-allocated by
982     // LocalStackSlotPass. If it turns out that PEI still has to allocate some
983     // of them, we may end up messing up the expected order of the objects.
984     if (MFI.getUseLocalStackAllocationBlock() &&
985         !(LargeArrayObjs.empty() && SmallArrayObjs.empty() &&
986           AddrOfObjs.empty()))
987       llvm_unreachable("Found protected stack objects not pre-allocated by "
988                        "LocalStackSlotPass.");
989 
990     AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
991                           Offset, MaxAlign, Skew);
992     AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
993                           Offset, MaxAlign, Skew);
994     AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
995                           Offset, MaxAlign, Skew);
996   }
997 
998   SmallVector<int, 8> ObjectsToAllocate;
999 
1000   // Then prepare to assign frame offsets to stack objects that are not used to
1001   // spill callee saved registers.
1002   for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
1003     if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())
1004       continue;
1005     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
1006       continue;
1007     if (RS && RS->isScavengingFrameIndex((int)i))
1008       continue;
1009     if (MFI.isDeadObjectIndex(i))
1010       continue;
1011     if (MFI.getStackProtectorIndex() == (int)i || EHRegNodeFrameIndex == (int)i)
1012       continue;
1013     if (ProtectedObjs.count(i))
1014       continue;
1015     if (MFI.getStackID(i) !=
1016         TargetStackID::Default) // Only allocate objects on the default stack.
1017       continue;
1018 
1019     // Add the objects that we need to allocate to our working set.
1020     ObjectsToAllocate.push_back(i);
1021   }
1022 
1023   // Allocate the EH registration node first if one is present.
1024   if (EHRegNodeFrameIndex != std::numeric_limits<int>::max())
1025     AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,
1026                       MaxAlign, Skew);
1027 
1028   // Give the targets a chance to order the objects the way they like it.
1029   if (MF.getTarget().getOptLevel() != CodeGenOpt::None &&
1030       MF.getTarget().Options.StackSymbolOrdering)
1031     TFI.orderFrameObjects(MF, ObjectsToAllocate);
1032 
1033   // Keep track of which bytes in the fixed and callee-save range are used so we
1034   // can use the holes when allocating later stack objects.  Only do this if
1035   // stack protector isn't being used and the target requests it and we're
1036   // optimizing.
1037   BitVector StackBytesFree;
1038   if (!ObjectsToAllocate.empty() &&
1039       MF.getTarget().getOptLevel() != CodeGenOpt::None &&
1040       MFI.getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(MF))
1041     computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,
1042                           FixedCSEnd, StackBytesFree);
1043 
1044   // Now walk the objects and actually assign base offsets to them.
1045   for (auto &Object : ObjectsToAllocate)
1046     if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,
1047                            StackBytesFree))
1048       AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew);
1049 
1050   // Make sure the special register scavenging spill slot is closest to the
1051   // stack pointer.
1052   if (RS && !EarlyScavengingSlots) {
1053     SmallVector<int, 2> SFIs;
1054     RS->getScavengingFrameIndices(SFIs);
1055     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
1056            IE = SFIs.end(); I != IE; ++I)
1057       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
1058   }
1059 
1060   if (!TFI.targetHandlesStackFrameRounding()) {
1061     // If we have reserved argument space for call sites in the function
1062     // immediately on entry to the current function, count it as part of the
1063     // overall stack size.
1064     if (MFI.adjustsStack() && TFI.hasReservedCallFrame(MF))
1065       Offset += MFI.getMaxCallFrameSize();
1066 
1067     // Round up the size to a multiple of the alignment.  If the function has
1068     // any calls or alloca's, align to the target's StackAlignment value to
1069     // ensure that the callee's frame or the alloca data is suitably aligned;
1070     // otherwise, for leaf functions, align to the TransientStackAlignment
1071     // value.
1072     Align StackAlign;
1073     if (MFI.adjustsStack() || MFI.hasVarSizedObjects() ||
1074         (RegInfo->needsStackRealignment(MF) && MFI.getObjectIndexEnd() != 0))
1075       StackAlign = TFI.getStackAlign();
1076     else
1077       StackAlign = TFI.getTransientStackAlign();
1078 
1079     // If the frame pointer is eliminated, all frame offsets will be relative to
1080     // SP not FP. Align to MaxAlign so this works.
1081     StackAlign = std::max(StackAlign, MaxAlign);
1082     Offset = alignTo(Offset, StackAlign, Skew);
1083   }
1084 
1085   // Update frame info to pretend that this is part of the stack...
1086   int64_t StackSize = Offset - LocalAreaOffset;
1087   MFI.setStackSize(StackSize);
1088   NumBytesStackSpace += StackSize;
1089 }
1090 
1091 /// insertPrologEpilogCode - Scan the function for modified callee saved
1092 /// registers, insert spill code for these callee saved registers, then add
1093 /// prolog and epilog code to the function.
1094 void PEI::insertPrologEpilogCode(MachineFunction &MF) {
1095   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
1096 
1097   // Add prologue to the function...
1098   for (MachineBasicBlock *SaveBlock : SaveBlocks)
1099     TFI.emitPrologue(MF, *SaveBlock);
1100 
1101   // Add epilogue to restore the callee-save registers in each exiting block.
1102   for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
1103     TFI.emitEpilogue(MF, *RestoreBlock);
1104 
1105   for (MachineBasicBlock *SaveBlock : SaveBlocks)
1106     TFI.inlineStackProbe(MF, *SaveBlock);
1107 
1108   // Emit additional code that is required to support segmented stacks, if
1109   // we've been asked for it.  This, when linked with a runtime with support
1110   // for segmented stacks (libgcc is one), will result in allocating stack
1111   // space in small chunks instead of one large contiguous block.
1112   if (MF.shouldSplitStack()) {
1113     for (MachineBasicBlock *SaveBlock : SaveBlocks)
1114       TFI.adjustForSegmentedStacks(MF, *SaveBlock);
1115     // Record that there are split-stack functions, so we will emit a
1116     // special section to tell the linker.
1117     MF.getMMI().setHasSplitStack(true);
1118   } else
1119     MF.getMMI().setHasNosplitStack(true);
1120 
1121   // Emit additional code that is required to explicitly handle the stack in
1122   // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
1123   // approach is rather similar to that of Segmented Stacks, but it uses a
1124   // different conditional check and another BIF for allocating more stack
1125   // space.
1126   if (MF.getFunction().getCallingConv() == CallingConv::HiPE)
1127     for (MachineBasicBlock *SaveBlock : SaveBlocks)
1128       TFI.adjustForHiPEPrologue(MF, *SaveBlock);
1129 }
1130 
1131 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
1132 /// register references and actual offsets.
1133 void PEI::replaceFrameIndices(MachineFunction &MF) {
1134   const auto &ST = MF.getSubtarget();
1135   const TargetFrameLowering &TFI = *ST.getFrameLowering();
1136   if (!TFI.needsFrameIndexResolution(MF))
1137     return;
1138 
1139   const TargetRegisterInfo *TRI = ST.getRegisterInfo();
1140 
1141   // Allow the target to determine this after knowing the frame size.
1142   FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) ||
1143     TRI->requiresFrameIndexReplacementScavenging(MF);
1144 
1145   // Store SPAdj at exit of a basic block.
1146   SmallVector<int, 8> SPState;
1147   SPState.resize(MF.getNumBlockIDs());
1148   df_iterator_default_set<MachineBasicBlock*> Reachable;
1149 
1150   // Iterate over the reachable blocks in DFS order.
1151   for (auto DFI = df_ext_begin(&MF, Reachable), DFE = df_ext_end(&MF, Reachable);
1152        DFI != DFE; ++DFI) {
1153     int SPAdj = 0;
1154     // Check the exit state of the DFS stack predecessor.
1155     if (DFI.getPathLength() >= 2) {
1156       MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
1157       assert(Reachable.count(StackPred) &&
1158              "DFS stack predecessor is already visited.\n");
1159       SPAdj = SPState[StackPred->getNumber()];
1160     }
1161     MachineBasicBlock *BB = *DFI;
1162     replaceFrameIndices(BB, MF, SPAdj);
1163     SPState[BB->getNumber()] = SPAdj;
1164   }
1165 
1166   // Handle the unreachable blocks.
1167   for (auto &BB : MF) {
1168     if (Reachable.count(&BB))
1169       // Already handled in DFS traversal.
1170       continue;
1171     int SPAdj = 0;
1172     replaceFrameIndices(&BB, MF, SPAdj);
1173   }
1174 }
1175 
1176 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
1177                               int &SPAdj) {
1178   assert(MF.getSubtarget().getRegisterInfo() &&
1179          "getRegisterInfo() must be implemented!");
1180   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
1181   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
1182   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
1183 
1184   if (RS && FrameIndexEliminationScavenging)
1185     RS->enterBasicBlock(*BB);
1186 
1187   bool InsideCallSequence = false;
1188 
1189   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
1190     if (TII.isFrameInstr(*I)) {
1191       InsideCallSequence = TII.isFrameSetup(*I);
1192       SPAdj += TII.getSPAdjust(*I);
1193       I = TFI->eliminateCallFramePseudoInstr(MF, *BB, I);
1194       continue;
1195     }
1196 
1197     MachineInstr &MI = *I;
1198     bool DoIncr = true;
1199     bool DidFinishLoop = true;
1200     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1201       if (!MI.getOperand(i).isFI())
1202         continue;
1203 
1204       // Frame indices in debug values are encoded in a target independent
1205       // way with simply the frame index and offset rather than any
1206       // target-specific addressing mode.
1207       if (MI.isDebugValue()) {
1208         assert(i == 0 && "Frame indices can only appear as the first "
1209                          "operand of a DBG_VALUE machine instruction");
1210         unsigned Reg;
1211         unsigned FrameIdx = MI.getOperand(0).getIndex();
1212         unsigned Size = MF.getFrameInfo().getObjectSize(FrameIdx);
1213 
1214         int64_t Offset =
1215             TFI->getFrameIndexReference(MF, FrameIdx, Reg);
1216         MI.getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
1217         MI.getOperand(0).setIsDebug();
1218 
1219         const DIExpression *DIExpr = MI.getDebugExpression();
1220 
1221         // If we have a direct DBG_VALUE, and its location expression isn't
1222         // currently complex, then adding an offset will morph it into a
1223         // complex location that is interpreted as being a memory address.
1224         // This changes a pointer-valued variable to dereference that pointer,
1225         // which is incorrect. Fix by adding DW_OP_stack_value.
1226         unsigned PrependFlags = DIExpression::ApplyOffset;
1227         if (!MI.isIndirectDebugValue() && !DIExpr->isComplex())
1228           PrependFlags |= DIExpression::StackValue;
1229 
1230         // If we have DBG_VALUE that is indirect and has a Implicit location
1231         // expression need to insert a deref before prepending a Memory
1232         // location expression. Also after doing this we change the DBG_VALUE
1233         // to be direct.
1234         if (MI.isIndirectDebugValue() && DIExpr->isImplicit()) {
1235           SmallVector<uint64_t, 2> Ops = {dwarf::DW_OP_deref_size, Size};
1236           bool WithStackValue = true;
1237           DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue);
1238           // Make the DBG_VALUE direct.
1239           MI.getOperand(1).ChangeToRegister(0, false);
1240         }
1241         DIExpr = DIExpression::prepend(DIExpr, PrependFlags, Offset);
1242         MI.getOperand(3).setMetadata(DIExpr);
1243         continue;
1244       }
1245 
1246       // TODO: This code should be commoned with the code for
1247       // PATCHPOINT. There's no good reason for the difference in
1248       // implementation other than historical accident.  The only
1249       // remaining difference is the unconditional use of the stack
1250       // pointer as the base register.
1251       if (MI.getOpcode() == TargetOpcode::STATEPOINT) {
1252         assert((!MI.isDebugValue() || i == 0) &&
1253                "Frame indicies can only appear as the first operand of a "
1254                "DBG_VALUE machine instruction");
1255         unsigned Reg;
1256         MachineOperand &Offset = MI.getOperand(i + 1);
1257         int refOffset = TFI->getFrameIndexReferencePreferSP(
1258             MF, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false);
1259         Offset.setImm(Offset.getImm() + refOffset + SPAdj);
1260         MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
1261         continue;
1262       }
1263 
1264       // Some instructions (e.g. inline asm instructions) can have
1265       // multiple frame indices and/or cause eliminateFrameIndex
1266       // to insert more than one instruction. We need the register
1267       // scavenger to go through all of these instructions so that
1268       // it can update its register information. We keep the
1269       // iterator at the point before insertion so that we can
1270       // revisit them in full.
1271       bool AtBeginning = (I == BB->begin());
1272       if (!AtBeginning) --I;
1273 
1274       // If this instruction has a FrameIndex operand, we need to
1275       // use that target machine register info object to eliminate
1276       // it.
1277       TRI.eliminateFrameIndex(MI, SPAdj, i,
1278                               FrameIndexEliminationScavenging ?  RS : nullptr);
1279 
1280       // Reset the iterator if we were at the beginning of the BB.
1281       if (AtBeginning) {
1282         I = BB->begin();
1283         DoIncr = false;
1284       }
1285 
1286       DidFinishLoop = false;
1287       break;
1288     }
1289 
1290     // If we are looking at a call sequence, we need to keep track of
1291     // the SP adjustment made by each instruction in the sequence.
1292     // This includes both the frame setup/destroy pseudos (handled above),
1293     // as well as other instructions that have side effects w.r.t the SP.
1294     // Note that this must come after eliminateFrameIndex, because
1295     // if I itself referred to a frame index, we shouldn't count its own
1296     // adjustment.
1297     if (DidFinishLoop && InsideCallSequence)
1298       SPAdj += TII.getSPAdjust(MI);
1299 
1300     if (DoIncr && I != BB->end()) ++I;
1301 
1302     // Update register states.
1303     if (RS && FrameIndexEliminationScavenging && DidFinishLoop)
1304       RS->forward(MI);
1305   }
1306 }
1307