1 //===- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass is responsible for finalizing the functions frame layout, saving
11 // callee saved registers, and for emitting prolog & epilog code for the
14 // This pass must be run after register allocation. After this pass is
15 // executed, it is illegal to construct MO_FrameIndex operands.
17 //===----------------------------------------------------------------------===//
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"
75 #define DEBUG_TYPE "prologepilog"
77 using MBBVector = SmallVector<MachineBasicBlock *, 4>;
81 class PEI : public MachineFunctionPass {
85 PEI() : MachineFunctionPass(ID) {
86 initializePEIPass(*PassRegistry::getPassRegistry());
89 void getAnalysisUsage(AnalysisUsage &AU) const override;
91 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
92 /// frame indexes with appropriate references.
93 bool runOnMachineFunction(MachineFunction &Fn) override;
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;
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;
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;
113 // Flag to control whether the scavenger should be passed even though
114 // FrameIndexVirtualScavenging is used.
115 bool FrameIndexEliminationScavenging;
118 MachineOptimizationRemarkEmitter *ORE = nullptr;
120 void calculateCallFrameInfo(MachineFunction &Fn);
121 void calculateSaveRestoreBlocks(MachineFunction &Fn);
122 void spillCalleeSavedRegs(MachineFunction &MF);
124 void calculateFrameObjectOffsets(MachineFunction &Fn);
125 void replaceFrameIndices(MachineFunction &Fn);
126 void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
128 void insertPrologEpilogCode(MachineFunction &Fn);
131 } // end anonymous namespace
135 char &llvm::PrologEpilogCodeInserterID = PEI::ID;
137 static cl::opt<unsigned>
138 WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
139 cl::desc("Warn for stack size bigger than the given"
142 INITIALIZE_PASS_BEGIN(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion", false,
144 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
145 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
146 INITIALIZE_PASS_DEPENDENCY(StackProtector)
147 INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
148 INITIALIZE_PASS_END(PEI, DEBUG_TYPE,
149 "Prologue/Epilogue Insertion & Frame Finalization", false,
152 MachineFunctionPass *llvm::createPrologEpilogInserterPass() {
156 STATISTIC(NumBytesStackSpace,
157 "Number of bytes used for stack in all functions");
159 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
160 AU.setPreservesCFG();
161 AU.addPreserved<MachineLoopInfo>();
162 AU.addPreserved<MachineDominatorTree>();
163 AU.addRequired<StackProtector>();
164 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
165 MachineFunctionPass::getAnalysisUsage(AU);
168 /// StackObjSet - A set of stack object indexes
169 using StackObjSet = SmallSetVector<int, 8>;
171 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
172 /// frame indexes with appropriate references.
173 bool PEI::runOnMachineFunction(MachineFunction &Fn) {
174 const Function &F = Fn.getFunction();
175 const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
176 const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
178 RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : nullptr;
179 FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
180 FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) ||
181 TRI->requiresFrameIndexReplacementScavenging(Fn);
182 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
184 // Calculate the MaxCallFrameSize and AdjustsStack variables for the
185 // function's frame information. Also eliminates call frame pseudo
187 calculateCallFrameInfo(Fn);
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 calculateSaveRestoreBlocks(Fn);
193 // Handle CSR spilling and restoring, for targets that need it.
194 if (Fn.getTarget().usesPhysRegsForPEI())
195 spillCalleeSavedRegs(Fn);
197 // Allow the target machine to make final modifications to the function
198 // before the frame layout is finalized.
199 TFI->processFunctionBeforeFrameFinalized(Fn, RS);
201 // Calculate actual frame offsets for all abstract stack objects...
202 calculateFrameObjectOffsets(Fn);
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 if (!F.hasFnAttribute(Attribute::Naked))
210 insertPrologEpilogCode(Fn);
212 // Replace all MO_FrameIndex operands with physical register references
213 // and actual offsets.
215 replaceFrameIndices(Fn);
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
220 if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
221 scavengeFrameVirtualRegs(Fn, *RS);
223 // Warn on stack size when we exceeds the given limit.
224 MachineFrameInfo &MFI = Fn.getFrameInfo();
225 uint64_t StackSize = MFI.getStackSize();
226 if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
227 DiagnosticInfoStackSize DiagStackSize(F, StackSize);
228 F.getContext().diagnose(DiagStackSize);
233 RestoreBlocks.clear();
234 MFI.setSavePoint(nullptr);
235 MFI.setRestorePoint(nullptr);
239 /// Calculate the MaxCallFrameSize and AdjustsStack
240 /// variables for the function's frame information and eliminate call frame
241 /// pseudo instructions.
242 void PEI::calculateCallFrameInfo(MachineFunction &Fn) {
243 const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
244 const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
245 MachineFrameInfo &MFI = Fn.getFrameInfo();
247 unsigned MaxCallFrameSize = 0;
248 bool AdjustsStack = MFI.adjustsStack();
250 // Get the function call frame set-up and tear-down instruction opcode
251 unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
252 unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
254 // Early exit for targets which have no call frame setup/destroy pseudo
256 if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
259 std::vector<MachineBasicBlock::iterator> FrameSDOps;
260 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
261 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
262 if (TII.isFrameInstr(*I)) {
263 unsigned Size = TII.getFrameSize(*I);
264 if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
266 FrameSDOps.push_back(I);
267 } else if (I->isInlineAsm()) {
268 // Some inline asm's need a stack frame, as indicated by operand 1.
269 unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
270 if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
274 assert(!MFI.isMaxCallFrameSizeComputed() ||
275 (MFI.getMaxCallFrameSize() == MaxCallFrameSize &&
276 MFI.adjustsStack() == AdjustsStack));
277 MFI.setAdjustsStack(AdjustsStack);
278 MFI.setMaxCallFrameSize(MaxCallFrameSize);
280 for (std::vector<MachineBasicBlock::iterator>::iterator
281 i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
282 MachineBasicBlock::iterator I = *i;
284 // If call frames are not being included as part of the stack frame, and
285 // the target doesn't indicate otherwise, remove the call frame pseudos
286 // here. The sub/add sp instruction pairs are still inserted, but we don't
287 // need to track the SP adjustment for frame index elimination.
288 if (TFI->canSimplifyCallFramePseudos(Fn))
289 TFI->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
293 /// Compute the sets of entry and return blocks for saving and restoring
294 /// callee-saved registers, and placing prolog and epilog code.
295 void PEI::calculateSaveRestoreBlocks(MachineFunction &Fn) {
296 const MachineFrameInfo &MFI = Fn.getFrameInfo();
298 // Even when we do not change any CSR, we still want to insert the
299 // prologue and epilogue of the function.
300 // So set the save points for those.
302 // Use the points found by shrink-wrapping, if any.
303 if (MFI.getSavePoint()) {
304 SaveBlocks.push_back(MFI.getSavePoint());
305 assert(MFI.getRestorePoint() && "Both restore and save must be set");
306 MachineBasicBlock *RestoreBlock = MFI.getRestorePoint();
307 // If RestoreBlock does not have any successor and is not a return block
308 // then the end point is unreachable and we do not need to insert any
310 if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock())
311 RestoreBlocks.push_back(RestoreBlock);
315 // Save refs to entry and return blocks.
316 SaveBlocks.push_back(&Fn.front());
317 for (MachineBasicBlock &MBB : Fn) {
318 if (MBB.isEHFuncletEntry())
319 SaveBlocks.push_back(&MBB);
320 if (MBB.isReturnBlock())
321 RestoreBlocks.push_back(&MBB);
325 static void assignCalleeSavedSpillSlots(MachineFunction &F,
326 const BitVector &SavedRegs,
327 unsigned &MinCSFrameIndex,
328 unsigned &MaxCSFrameIndex) {
329 if (SavedRegs.empty())
332 const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();
333 const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs();
335 std::vector<CalleeSavedInfo> CSI;
336 for (unsigned i = 0; CSRegs[i]; ++i) {
337 unsigned Reg = CSRegs[i];
338 if (SavedRegs.test(Reg))
339 CSI.push_back(CalleeSavedInfo(Reg));
342 const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();
343 MachineFrameInfo &MFI = F.getFrameInfo();
344 if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
345 // If target doesn't implement this, use generic code.
348 return; // Early exit if no callee saved registers are modified!
350 unsigned NumFixedSpillSlots;
351 const TargetFrameLowering::SpillSlot *FixedSpillSlots =
352 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
354 // Now that we know which registers need to be saved and restored, allocate
355 // stack slots for them.
356 for (auto &CS : CSI) {
357 unsigned Reg = CS.getReg();
358 const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
361 if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {
362 CS.setFrameIdx(FrameIdx);
366 // Check to see if this physreg must be spilled to a particular stack slot
368 const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;
369 while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
370 FixedSlot->Reg != Reg)
373 unsigned Size = RegInfo->getSpillSize(*RC);
374 if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
375 // Nope, just spill it anywhere convenient.
376 unsigned Align = RegInfo->getSpillAlignment(*RC);
377 unsigned StackAlign = TFI->getStackAlignment();
379 // We may not be able to satisfy the desired alignment specification of
380 // the TargetRegisterClass if the stack alignment is smaller. Use the
382 Align = std::min(Align, StackAlign);
383 FrameIdx = MFI.CreateStackObject(Size, Align, true);
384 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
385 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
387 // Spill it to the stack where we must.
388 FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset);
391 CS.setFrameIdx(FrameIdx);
395 MFI.setCalleeSavedInfo(CSI);
398 /// Helper function to update the liveness information for the callee-saved
400 static void updateLiveness(MachineFunction &MF) {
401 MachineFrameInfo &MFI = MF.getFrameInfo();
402 // Visited will contain all the basic blocks that are in the region
403 // where the callee saved registers are alive:
404 // - Anything that is not Save or Restore -> LiveThrough.
406 // - Restore -> LiveOut.
407 // The live-out is not attached to the block, so no need to keep
408 // Restore in this set.
409 SmallPtrSet<MachineBasicBlock *, 8> Visited;
410 SmallVector<MachineBasicBlock *, 8> WorkList;
411 MachineBasicBlock *Entry = &MF.front();
412 MachineBasicBlock *Save = MFI.getSavePoint();
418 WorkList.push_back(Entry);
419 Visited.insert(Entry);
421 Visited.insert(Save);
423 MachineBasicBlock *Restore = MFI.getRestorePoint();
425 // By construction Restore cannot be visited, otherwise it
426 // means there exists a path to Restore that does not go
428 WorkList.push_back(Restore);
430 while (!WorkList.empty()) {
431 const MachineBasicBlock *CurBB = WorkList.pop_back_val();
432 // By construction, the region that is after the save point is
433 // dominated by the Save and post-dominated by the Restore.
434 if (CurBB == Save && Save != Restore)
436 // Enqueue all the successors not already visited.
437 // Those are by construction either before Save or after Restore.
438 for (MachineBasicBlock *SuccBB : CurBB->successors())
439 if (Visited.insert(SuccBB).second)
440 WorkList.push_back(SuccBB);
443 const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
445 MachineRegisterInfo &MRI = MF.getRegInfo();
446 for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
447 for (MachineBasicBlock *MBB : Visited) {
448 MCPhysReg Reg = CSI[i].getReg();
449 // Add the callee-saved register as live-in.
450 // It's killed at the spill.
451 if (!MRI.isReserved(Reg) && !MBB->isLiveIn(Reg))
457 /// Insert restore code for the callee-saved registers used in the function.
458 static void insertCSRSaves(MachineBasicBlock &SaveBlock,
459 ArrayRef<CalleeSavedInfo> CSI) {
460 MachineFunction &Fn = *SaveBlock.getParent();
461 const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
462 const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
463 const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
465 MachineBasicBlock::iterator I = SaveBlock.begin();
466 if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) {
467 for (const CalleeSavedInfo &CS : CSI) {
468 // Insert the spill to the stack frame.
469 unsigned Reg = CS.getReg();
470 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
471 TII.storeRegToStackSlot(SaveBlock, I, Reg, true, CS.getFrameIdx(), RC,
477 /// Insert restore code for the callee-saved registers used in the function.
478 static void insertCSRRestores(MachineBasicBlock &RestoreBlock,
479 std::vector<CalleeSavedInfo> &CSI) {
480 MachineFunction &Fn = *RestoreBlock.getParent();
481 const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
482 const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
483 const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
485 // Restore all registers immediately before the return and any
486 // terminators that precede it.
487 MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator();
489 if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) {
490 for (const CalleeSavedInfo &CI : reverse(CSI)) {
491 unsigned Reg = CI.getReg();
492 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
493 TII.loadRegFromStackSlot(RestoreBlock, I, Reg, CI.getFrameIdx(), RC, TRI);
494 assert(I != RestoreBlock.begin() &&
495 "loadRegFromStackSlot didn't insert any code!");
496 // Insert in reverse order. loadRegFromStackSlot can insert
497 // multiple instructions.
502 void PEI::spillCalleeSavedRegs(MachineFunction &Fn) {
503 // We can't list this requirement in getRequiredProperties because some
504 // targets (WebAssembly) use virtual registers past this point, and the pass
505 // pipeline is set up without giving the passes a chance to look at the
507 // FIXME: Find a way to express this in getRequiredProperties.
508 assert(Fn.getProperties().hasProperty(
509 MachineFunctionProperties::Property::NoVRegs));
511 const Function &F = Fn.getFunction();
512 const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
513 MachineFrameInfo &MFI = Fn.getFrameInfo();
514 MinCSFrameIndex = std::numeric_limits<unsigned>::max();
517 // Determine which of the registers in the callee save list should be saved.
519 TFI->determineCalleeSaves(Fn, SavedRegs, RS);
521 // Assign stack slots for any callee-saved registers that must be spilled.
522 assignCalleeSavedSpillSlots(Fn, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);
524 // Add the code to save and restore the callee saved registers.
525 if (!F.hasFnAttribute(Attribute::Naked)) {
526 MFI.setCalleeSavedInfoValid(true);
528 std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
530 for (MachineBasicBlock *SaveBlock : SaveBlocks) {
531 insertCSRSaves(*SaveBlock, CSI);
532 // Update the live-in information of all the blocks up to the save
536 for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
537 insertCSRRestores(*RestoreBlock, CSI);
542 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
544 AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,
545 bool StackGrowsDown, int64_t &Offset,
546 unsigned &MaxAlign, unsigned Skew) {
547 // If the stack grows down, add the object size to find the lowest address.
549 Offset += MFI.getObjectSize(FrameIdx);
551 unsigned Align = MFI.getObjectAlignment(FrameIdx);
553 // If the alignment of this object is greater than that of the stack, then
554 // increase the stack alignment to match.
555 MaxAlign = std::max(MaxAlign, Align);
557 // Adjust to alignment boundary.
558 Offset = alignTo(Offset, Align, Skew);
560 if (StackGrowsDown) {
561 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
562 MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset
564 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
565 MFI.setObjectOffset(FrameIdx, Offset);
566 Offset += MFI.getObjectSize(FrameIdx);
570 /// Compute which bytes of fixed and callee-save stack area are unused and keep
571 /// track of them in StackBytesFree.
573 computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown,
574 unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,
575 int64_t FixedCSEnd, BitVector &StackBytesFree) {
576 // Avoid undefined int64_t -> int conversion below in extreme case.
577 if (FixedCSEnd > std::numeric_limits<int>::max())
580 StackBytesFree.resize(FixedCSEnd, true);
582 SmallVector<int, 16> AllocatedFrameSlots;
583 // Add fixed objects.
584 for (int i = MFI.getObjectIndexBegin(); i != 0; ++i)
585 AllocatedFrameSlots.push_back(i);
586 // Add callee-save objects.
587 for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i)
588 AllocatedFrameSlots.push_back(i);
590 for (int i : AllocatedFrameSlots) {
591 // These are converted from int64_t, but they should always fit in int
592 // because of the FixedCSEnd check above.
593 int ObjOffset = MFI.getObjectOffset(i);
594 int ObjSize = MFI.getObjectSize(i);
595 int ObjStart, ObjEnd;
596 if (StackGrowsDown) {
597 // ObjOffset is negative when StackGrowsDown is true.
598 ObjStart = -ObjOffset - ObjSize;
601 ObjStart = ObjOffset;
602 ObjEnd = ObjOffset + ObjSize;
604 // Ignore fixed holes that are in the previous stack frame.
606 StackBytesFree.reset(ObjStart, ObjEnd);
610 /// Assign frame object to an unused portion of the stack in the fixed stack
611 /// object range. Return true if the allocation was successful.
612 static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx,
613 bool StackGrowsDown, unsigned MaxAlign,
614 BitVector &StackBytesFree) {
615 if (MFI.isVariableSizedObjectIndex(FrameIdx))
618 if (StackBytesFree.none()) {
619 // clear it to speed up later scavengeStackSlot calls to
620 // StackBytesFree.none()
621 StackBytesFree.clear();
625 unsigned ObjAlign = MFI.getObjectAlignment(FrameIdx);
626 if (ObjAlign > MaxAlign)
629 int64_t ObjSize = MFI.getObjectSize(FrameIdx);
631 for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;
632 FreeStart = StackBytesFree.find_next(FreeStart)) {
634 // Check that free space has suitable alignment.
635 unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart;
636 if (alignTo(ObjStart, ObjAlign) != ObjStart)
639 if (FreeStart + ObjSize > StackBytesFree.size())
642 bool AllBytesFree = true;
643 for (unsigned Byte = 0; Byte < ObjSize; ++Byte)
644 if (!StackBytesFree.test(FreeStart + Byte)) {
645 AllBytesFree = false;
655 if (StackGrowsDown) {
656 int ObjStart = -(FreeStart + ObjSize);
657 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << ObjStart
659 MFI.setObjectOffset(FrameIdx, ObjStart);
661 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << FreeStart
663 MFI.setObjectOffset(FrameIdx, FreeStart);
666 StackBytesFree.reset(FreeStart, FreeStart + ObjSize);
670 /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
671 /// those required to be close to the Stack Protector) to stack offsets.
673 AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
674 SmallSet<int, 16> &ProtectedObjs,
675 MachineFrameInfo &MFI, bool StackGrowsDown,
676 int64_t &Offset, unsigned &MaxAlign, unsigned Skew) {
678 for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
679 E = UnassignedObjs.end(); I != E; ++I) {
681 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew);
682 ProtectedObjs.insert(i);
686 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
687 /// abstract stack objects.
688 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
689 const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
690 StackProtector *SP = &getAnalysis<StackProtector>();
692 bool StackGrowsDown =
693 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
695 // Loop over all of the stack objects, assigning sequential addresses...
696 MachineFrameInfo &MFI = Fn.getFrameInfo();
698 // Start at the beginning of the local area.
699 // The Offset is the distance from the stack top in the direction
700 // of stack growth -- so it's always nonnegative.
701 int LocalAreaOffset = TFI.getOffsetOfLocalArea();
703 LocalAreaOffset = -LocalAreaOffset;
704 assert(LocalAreaOffset >= 0
705 && "Local area offset should be in direction of stack growth");
706 int64_t Offset = LocalAreaOffset;
708 // Skew to be applied to alignment.
709 unsigned Skew = TFI.getStackAlignmentSkew(Fn);
711 // If there are fixed sized objects that are preallocated in the local area,
712 // non-fixed objects can't be allocated right at the start of local area.
713 // Adjust 'Offset' to point to the end of last fixed sized preallocated
715 for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) {
717 if (StackGrowsDown) {
718 // The maximum distance from the stack pointer is at lower address of
719 // the object -- which is given by offset. For down growing stack
720 // the offset is negative, so we negate the offset to get the distance.
721 FixedOff = -MFI.getObjectOffset(i);
723 // The maximum distance from the start pointer is at the upper
724 // address of the object.
725 FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i);
727 if (FixedOff > Offset) Offset = FixedOff;
730 // First assign frame offsets to stack objects that are used to spill
731 // callee saved registers.
732 if (StackGrowsDown) {
733 for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
734 // If the stack grows down, we need to add the size to find the lowest
735 // address of the object.
736 Offset += MFI.getObjectSize(i);
738 unsigned Align = MFI.getObjectAlignment(i);
739 // Adjust to alignment boundary
740 Offset = alignTo(Offset, Align, Skew);
742 DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << -Offset << "]\n");
743 MFI.setObjectOffset(i, -Offset); // Set the computed offset
745 } else if (MaxCSFrameIndex >= MinCSFrameIndex) {
746 // Be careful about underflow in comparisons agains MinCSFrameIndex.
747 for (unsigned i = MaxCSFrameIndex; i != MinCSFrameIndex - 1; --i) {
748 if (MFI.isDeadObjectIndex(i))
751 unsigned Align = MFI.getObjectAlignment(i);
752 // Adjust to alignment boundary
753 Offset = alignTo(Offset, Align, Skew);
755 DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << Offset << "]\n");
756 MFI.setObjectOffset(i, Offset);
757 Offset += MFI.getObjectSize(i);
761 // FixedCSEnd is the stack offset to the end of the fixed and callee-save
763 int64_t FixedCSEnd = Offset;
764 unsigned MaxAlign = MFI.getMaxAlignment();
766 // Make sure the special register scavenging spill slot is closest to the
767 // incoming stack pointer if a frame pointer is required and is closer
768 // to the incoming rather than the final stack pointer.
769 const TargetRegisterInfo *RegInfo = Fn.getSubtarget().getRegisterInfo();
770 bool EarlyScavengingSlots = (TFI.hasFP(Fn) &&
771 TFI.isFPCloseToIncomingSP() &&
772 RegInfo->useFPForScavengingIndex(Fn) &&
773 !RegInfo->needsStackRealignment(Fn));
774 if (RS && EarlyScavengingSlots) {
775 SmallVector<int, 2> SFIs;
776 RS->getScavengingFrameIndices(SFIs);
777 for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
778 IE = SFIs.end(); I != IE; ++I)
779 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
782 // FIXME: Once this is working, then enable flag will change to a target
783 // check for whether the frame is large enough to want to use virtual
784 // frame index registers. Functions which don't want/need this optimization
785 // will continue to use the existing code path.
786 if (MFI.getUseLocalStackAllocationBlock()) {
787 unsigned Align = MFI.getLocalFrameMaxAlign();
789 // Adjust to alignment boundary.
790 Offset = alignTo(Offset, Align, Skew);
792 DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
794 // Resolve offsets for objects in the local block.
795 for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; ++i) {
796 std::pair<int, int64_t> Entry = MFI.getLocalFrameObjectMap(i);
797 int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
798 DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" <<
800 MFI.setObjectOffset(Entry.first, FIOffset);
802 // Allocate the local block
803 Offset += MFI.getLocalFrameSize();
805 MaxAlign = std::max(Align, MaxAlign);
808 // Retrieve the Exception Handler registration node.
809 int EHRegNodeFrameIndex = std::numeric_limits<int>::max();
810 if (const WinEHFuncInfo *FuncInfo = Fn.getWinEHFuncInfo())
811 EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;
813 // Make sure that the stack protector comes before the local variables on the
815 SmallSet<int, 16> ProtectedObjs;
816 if (MFI.getStackProtectorIndex() >= 0) {
817 StackObjSet LargeArrayObjs;
818 StackObjSet SmallArrayObjs;
819 StackObjSet AddrOfObjs;
821 AdjustStackOffset(MFI, MFI.getStackProtectorIndex(), StackGrowsDown,
822 Offset, MaxAlign, Skew);
824 // Assign large stack objects first.
825 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
826 if (MFI.isObjectPreAllocated(i) &&
827 MFI.getUseLocalStackAllocationBlock())
829 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
831 if (RS && RS->isScavengingFrameIndex((int)i))
833 if (MFI.isDeadObjectIndex(i))
835 if (MFI.getStackProtectorIndex() == (int)i ||
836 EHRegNodeFrameIndex == (int)i)
839 switch (SP->getSSPLayout(MFI.getObjectAllocation(i))) {
840 case StackProtector::SSPLK_None:
842 case StackProtector::SSPLK_SmallArray:
843 SmallArrayObjs.insert(i);
845 case StackProtector::SSPLK_AddrOf:
846 AddrOfObjs.insert(i);
848 case StackProtector::SSPLK_LargeArray:
849 LargeArrayObjs.insert(i);
852 llvm_unreachable("Unexpected SSPLayoutKind.");
855 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
856 Offset, MaxAlign, Skew);
857 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
858 Offset, MaxAlign, Skew);
859 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
860 Offset, MaxAlign, Skew);
863 SmallVector<int, 8> ObjectsToAllocate;
865 // Then prepare to assign frame offsets to stack objects that are not used to
866 // spill callee saved registers.
867 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
868 if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())
870 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
872 if (RS && RS->isScavengingFrameIndex((int)i))
874 if (MFI.isDeadObjectIndex(i))
876 if (MFI.getStackProtectorIndex() == (int)i ||
877 EHRegNodeFrameIndex == (int)i)
879 if (ProtectedObjs.count(i))
882 // Add the objects that we need to allocate to our working set.
883 ObjectsToAllocate.push_back(i);
886 // Allocate the EH registration node first if one is present.
887 if (EHRegNodeFrameIndex != std::numeric_limits<int>::max())
888 AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,
891 // Give the targets a chance to order the objects the way they like it.
892 if (Fn.getTarget().getOptLevel() != CodeGenOpt::None &&
893 Fn.getTarget().Options.StackSymbolOrdering)
894 TFI.orderFrameObjects(Fn, ObjectsToAllocate);
896 // Keep track of which bytes in the fixed and callee-save range are used so we
897 // can use the holes when allocating later stack objects. Only do this if
898 // stack protector isn't being used and the target requests it and we're
900 BitVector StackBytesFree;
901 if (!ObjectsToAllocate.empty() &&
902 Fn.getTarget().getOptLevel() != CodeGenOpt::None &&
903 MFI.getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(Fn))
904 computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,
905 FixedCSEnd, StackBytesFree);
907 // Now walk the objects and actually assign base offsets to them.
908 for (auto &Object : ObjectsToAllocate)
909 if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,
911 AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew);
913 // Make sure the special register scavenging spill slot is closest to the
915 if (RS && !EarlyScavengingSlots) {
916 SmallVector<int, 2> SFIs;
917 RS->getScavengingFrameIndices(SFIs);
918 for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
919 IE = SFIs.end(); I != IE; ++I)
920 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
923 if (!TFI.targetHandlesStackFrameRounding()) {
924 // If we have reserved argument space for call sites in the function
925 // immediately on entry to the current function, count it as part of the
926 // overall stack size.
927 if (MFI.adjustsStack() && TFI.hasReservedCallFrame(Fn))
928 Offset += MFI.getMaxCallFrameSize();
930 // Round up the size to a multiple of the alignment. If the function has
931 // any calls or alloca's, align to the target's StackAlignment value to
932 // ensure that the callee's frame or the alloca data is suitably aligned;
933 // otherwise, for leaf functions, align to the TransientStackAlignment
936 if (MFI.adjustsStack() || MFI.hasVarSizedObjects() ||
937 (RegInfo->needsStackRealignment(Fn) && MFI.getObjectIndexEnd() != 0))
938 StackAlign = TFI.getStackAlignment();
940 StackAlign = TFI.getTransientStackAlignment();
942 // If the frame pointer is eliminated, all frame offsets will be relative to
943 // SP not FP. Align to MaxAlign so this works.
944 StackAlign = std::max(StackAlign, MaxAlign);
945 Offset = alignTo(Offset, StackAlign, Skew);
948 // Update frame info to pretend that this is part of the stack...
949 int64_t StackSize = Offset - LocalAreaOffset;
950 MFI.setStackSize(StackSize);
951 NumBytesStackSpace += StackSize;
954 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize",
955 Fn.getFunction().getSubprogram(),
957 << ore::NV("NumStackBytes", StackSize) << " stack bytes in function";
961 /// insertPrologEpilogCode - Scan the function for modified callee saved
962 /// registers, insert spill code for these callee saved registers, then add
963 /// prolog and epilog code to the function.
964 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
965 const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
967 // Add prologue to the function...
968 for (MachineBasicBlock *SaveBlock : SaveBlocks)
969 TFI.emitPrologue(Fn, *SaveBlock);
971 // Add epilogue to restore the callee-save registers in each exiting block.
972 for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
973 TFI.emitEpilogue(Fn, *RestoreBlock);
975 for (MachineBasicBlock *SaveBlock : SaveBlocks)
976 TFI.inlineStackProbe(Fn, *SaveBlock);
978 // Emit additional code that is required to support segmented stacks, if
979 // we've been asked for it. This, when linked with a runtime with support
980 // for segmented stacks (libgcc is one), will result in allocating stack
981 // space in small chunks instead of one large contiguous block.
982 if (Fn.shouldSplitStack()) {
983 for (MachineBasicBlock *SaveBlock : SaveBlocks)
984 TFI.adjustForSegmentedStacks(Fn, *SaveBlock);
985 // Record that there are split-stack functions, so we will emit a
986 // special section to tell the linker.
987 Fn.getMMI().setHasSplitStack(true);
989 Fn.getMMI().setHasNosplitStack(true);
991 // Emit additional code that is required to explicitly handle the stack in
992 // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
993 // approach is rather similar to that of Segmented Stacks, but it uses a
994 // different conditional check and another BIF for allocating more stack
996 if (Fn.getFunction().getCallingConv() == CallingConv::HiPE)
997 for (MachineBasicBlock *SaveBlock : SaveBlocks)
998 TFI.adjustForHiPEPrologue(Fn, *SaveBlock);
1001 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
1002 /// register references and actual offsets.
1003 void PEI::replaceFrameIndices(MachineFunction &Fn) {
1004 const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
1005 if (!TFI.needsFrameIndexResolution(Fn)) return;
1007 // Store SPAdj at exit of a basic block.
1008 SmallVector<int, 8> SPState;
1009 SPState.resize(Fn.getNumBlockIDs());
1010 df_iterator_default_set<MachineBasicBlock*> Reachable;
1012 // Iterate over the reachable blocks in DFS order.
1013 for (auto DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable);
1014 DFI != DFE; ++DFI) {
1016 // Check the exit state of the DFS stack predecessor.
1017 if (DFI.getPathLength() >= 2) {
1018 MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
1019 assert(Reachable.count(StackPred) &&
1020 "DFS stack predecessor is already visited.\n");
1021 SPAdj = SPState[StackPred->getNumber()];
1023 MachineBasicBlock *BB = *DFI;
1024 replaceFrameIndices(BB, Fn, SPAdj);
1025 SPState[BB->getNumber()] = SPAdj;
1028 // Handle the unreachable blocks.
1029 for (auto &BB : Fn) {
1030 if (Reachable.count(&BB))
1031 // Already handled in DFS traversal.
1034 replaceFrameIndices(&BB, Fn, SPAdj);
1038 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
1040 assert(Fn.getSubtarget().getRegisterInfo() &&
1041 "getRegisterInfo() must be implemented!");
1042 const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
1043 const TargetRegisterInfo &TRI = *Fn.getSubtarget().getRegisterInfo();
1044 const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
1046 if (RS && FrameIndexEliminationScavenging)
1047 RS->enterBasicBlock(*BB);
1049 bool InsideCallSequence = false;
1051 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
1052 if (TII.isFrameInstr(*I)) {
1053 InsideCallSequence = TII.isFrameSetup(*I);
1054 SPAdj += TII.getSPAdjust(*I);
1055 I = TFI->eliminateCallFramePseudoInstr(Fn, *BB, I);
1059 MachineInstr &MI = *I;
1061 bool DidFinishLoop = true;
1062 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1063 if (!MI.getOperand(i).isFI())
1066 // Frame indices in debug values are encoded in a target independent
1067 // way with simply the frame index and offset rather than any
1068 // target-specific addressing mode.
1069 if (MI.isDebugValue()) {
1070 assert(i == 0 && "Frame indices can only appear as the first "
1071 "operand of a DBG_VALUE machine instruction");
1074 TFI->getFrameIndexReference(Fn, MI.getOperand(0).getIndex(), Reg);
1075 MI.getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
1076 auto *DIExpr = DIExpression::prepend(MI.getDebugExpression(),
1077 DIExpression::NoDeref, Offset);
1078 MI.getOperand(3).setMetadata(DIExpr);
1082 // TODO: This code should be commoned with the code for
1083 // PATCHPOINT. There's no good reason for the difference in
1084 // implementation other than historical accident. The only
1085 // remaining difference is the unconditional use of the stack
1086 // pointer as the base register.
1087 if (MI.getOpcode() == TargetOpcode::STATEPOINT) {
1088 assert((!MI.isDebugValue() || i == 0) &&
1089 "Frame indicies can only appear as the first operand of a "
1090 "DBG_VALUE machine instruction");
1092 MachineOperand &Offset = MI.getOperand(i + 1);
1093 int refOffset = TFI->getFrameIndexReferencePreferSP(
1094 Fn, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false);
1095 Offset.setImm(Offset.getImm() + refOffset);
1096 MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
1100 // Some instructions (e.g. inline asm instructions) can have
1101 // multiple frame indices and/or cause eliminateFrameIndex
1102 // to insert more than one instruction. We need the register
1103 // scavenger to go through all of these instructions so that
1104 // it can update its register information. We keep the
1105 // iterator at the point before insertion so that we can
1106 // revisit them in full.
1107 bool AtBeginning = (I == BB->begin());
1108 if (!AtBeginning) --I;
1110 // If this instruction has a FrameIndex operand, we need to
1111 // use that target machine register info object to eliminate
1113 TRI.eliminateFrameIndex(MI, SPAdj, i,
1114 FrameIndexEliminationScavenging ? RS : nullptr);
1116 // Reset the iterator if we were at the beginning of the BB.
1122 DidFinishLoop = false;
1126 // If we are looking at a call sequence, we need to keep track of
1127 // the SP adjustment made by each instruction in the sequence.
1128 // This includes both the frame setup/destroy pseudos (handled above),
1129 // as well as other instructions that have side effects w.r.t the SP.
1130 // Note that this must come after eliminateFrameIndex, because
1131 // if I itself referred to a frame index, we shouldn't count its own
1133 if (DidFinishLoop && InsideCallSequence)
1134 SPAdj += TII.getSPAdjust(MI);
1136 if (DoIncr && I != BB->end()) ++I;
1138 // Update register states.
1139 if (RS && FrameIndexEliminationScavenging && DidFinishLoop)