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 "PrologEpilogInserter.h"
20 #include "llvm/ADT/IndexedMap.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallSet.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/CodeGen/MachineDominators.h"
26 #include "llvm/CodeGen/MachineFrameInfo.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineLoopInfo.h"
29 #include "llvm/CodeGen/MachineModuleInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/RegisterScavenging.h"
32 #include "llvm/CodeGen/StackProtector.h"
33 #include "llvm/IR/DiagnosticInfo.h"
34 #include "llvm/IR/InlineAsm.h"
35 #include "llvm/IR/LLVMContext.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/Target/TargetFrameLowering.h"
41 #include "llvm/Target/TargetInstrInfo.h"
42 #include "llvm/Target/TargetMachine.h"
43 #include "llvm/Target/TargetRegisterInfo.h"
44 #include "llvm/Target/TargetSubtargetInfo.h"
49 #define DEBUG_TYPE "pei"
52 char &llvm::PrologEpilogCodeInserterID = PEI::ID;
54 static cl::opt<unsigned>
55 WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
56 cl::desc("Warn for stack size bigger than the given"
59 INITIALIZE_PASS_BEGIN(PEI, "prologepilog",
60 "Prologue/Epilogue Insertion", false, false)
61 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
62 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
63 INITIALIZE_PASS_DEPENDENCY(StackProtector)
64 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
65 INITIALIZE_PASS_END(PEI, "prologepilog",
66 "Prologue/Epilogue Insertion & Frame Finalization",
69 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
70 STATISTIC(NumBytesStackSpace,
71 "Number of bytes used for stack in all functions");
73 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
75 AU.addPreserved<MachineLoopInfo>();
76 AU.addPreserved<MachineDominatorTree>();
77 AU.addRequired<StackProtector>();
78 AU.addRequired<TargetPassConfig>();
79 MachineFunctionPass::getAnalysisUsage(AU);
82 bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
83 return (MBB && !MBB->empty() && MBB->back().isReturn());
86 /// Compute the set of return blocks
87 void PEI::calculateSets(MachineFunction &Fn) {
88 // Sets used to compute spill, restore placement sets.
89 const std::vector<CalleeSavedInfo> &CSI =
90 Fn.getFrameInfo()->getCalleeSavedInfo();
92 // If no CSRs used, we are done.
96 // Save refs to entry and return blocks.
97 EntryBlock = Fn.begin();
98 for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
100 if (isReturnBlock(MBB))
101 ReturnBlocks.push_back(MBB);
106 /// StackObjSet - A set of stack object indexes
107 typedef SmallSetVector<int, 8> StackObjSet;
109 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
110 /// frame indexes with appropriate references.
112 bool PEI::runOnMachineFunction(MachineFunction &Fn) {
113 const Function* F = Fn.getFunction();
114 const TargetRegisterInfo *TRI =
115 Fn.getTarget().getSubtargetImpl()->getRegisterInfo();
116 const TargetFrameLowering *TFI =
117 Fn.getTarget().getSubtargetImpl()->getFrameLowering();
119 assert(!Fn.getRegInfo().getNumVirtRegs() && "Regalloc must assign all vregs");
121 RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : nullptr;
122 FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
124 // Calculate the MaxCallFrameSize and AdjustsStack variables for the
125 // function's frame information. Also eliminates call frame pseudo
127 calculateCallsInformation(Fn);
129 // Allow the target machine to make some adjustments to the function
130 // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
131 TFI->processFunctionBeforeCalleeSavedScan(Fn, RS);
133 // Scan the function for modified callee saved registers and insert spill code
134 // for any callee saved registers that are modified.
135 calculateCalleeSavedRegisters(Fn);
137 // Determine placement of CSR spill/restore code:
138 // place all spills in the entry block, all restores in return blocks.
141 // Add the code to save and restore the callee saved registers
142 if (!F->hasFnAttribute(Attribute::Naked))
143 insertCSRSpillsAndRestores(Fn);
145 // Allow the target machine to make final modifications to the function
146 // before the frame layout is finalized.
147 TFI->processFunctionBeforeFrameFinalized(Fn, RS);
149 // Calculate actual frame offsets for all abstract stack objects...
150 calculateFrameObjectOffsets(Fn);
152 // Add prolog and epilog code to the function. This function is required
153 // to align the stack frame as necessary for any stack variables or
154 // called functions. Because of this, calculateCalleeSavedRegisters()
155 // must be called before this function in order to set the AdjustsStack
156 // and MaxCallFrameSize variables.
157 if (!F->hasFnAttribute(Attribute::Naked))
158 insertPrologEpilogCode(Fn);
160 // Replace all MO_FrameIndex operands with physical register references
161 // and actual offsets.
163 replaceFrameIndices(Fn);
165 // If register scavenging is needed, as we've enabled doing it as a
166 // post-pass, scavenge the virtual registers that frame index elimination
168 if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
169 scavengeFrameVirtualRegs(Fn);
171 // Clear any vregs created by virtual scavenging.
172 Fn.getRegInfo().clearVirtRegs();
174 // Warn on stack size when we exceeds the given limit.
175 MachineFrameInfo *MFI = Fn.getFrameInfo();
176 uint64_t StackSize = MFI->getStackSize();
177 if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
178 DiagnosticInfoStackSize DiagStackSize(*F, StackSize);
179 F->getContext().diagnose(DiagStackSize);
183 ReturnBlocks.clear();
187 /// calculateCallsInformation - Calculate the MaxCallFrameSize and AdjustsStack
188 /// variables for the function's frame information and eliminate call frame
189 /// pseudo instructions.
190 void PEI::calculateCallsInformation(MachineFunction &Fn) {
191 const TargetInstrInfo &TII =
192 *Fn.getTarget().getSubtargetImpl()->getInstrInfo();
193 const TargetFrameLowering *TFI =
194 Fn.getTarget().getSubtargetImpl()->getFrameLowering();
195 MachineFrameInfo *MFI = Fn.getFrameInfo();
197 unsigned MaxCallFrameSize = 0;
198 bool AdjustsStack = MFI->adjustsStack();
200 // Get the function call frame set-up and tear-down instruction opcode
201 int FrameSetupOpcode = TII.getCallFrameSetupOpcode();
202 int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
204 // Early exit for targets which have no call frame setup/destroy pseudo
206 if (FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
209 std::vector<MachineBasicBlock::iterator> FrameSDOps;
210 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
211 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
212 if (I->getOpcode() == FrameSetupOpcode ||
213 I->getOpcode() == FrameDestroyOpcode) {
214 assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
215 " instructions should have a single immediate argument!");
216 unsigned Size = I->getOperand(0).getImm();
217 if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
219 FrameSDOps.push_back(I);
220 } else if (I->isInlineAsm()) {
221 // Some inline asm's need a stack frame, as indicated by operand 1.
222 unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
223 if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
227 MFI->setAdjustsStack(AdjustsStack);
228 MFI->setMaxCallFrameSize(MaxCallFrameSize);
230 for (std::vector<MachineBasicBlock::iterator>::iterator
231 i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
232 MachineBasicBlock::iterator I = *i;
234 // If call frames are not being included as part of the stack frame, and
235 // the target doesn't indicate otherwise, remove the call frame pseudos
236 // here. The sub/add sp instruction pairs are still inserted, but we don't
237 // need to track the SP adjustment for frame index elimination.
238 if (TFI->canSimplifyCallFramePseudos(Fn))
239 TFI->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
244 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
246 void PEI::calculateCalleeSavedRegisters(MachineFunction &F) {
247 const TargetRegisterInfo *RegInfo =
248 F.getTarget().getSubtargetImpl()->getRegisterInfo();
249 const TargetFrameLowering *TFI =
250 F.getTarget().getSubtargetImpl()->getFrameLowering();
251 MachineFrameInfo *MFI = F.getFrameInfo();
253 // Get the callee saved register list...
254 const MCPhysReg *CSRegs = RegInfo->getCalleeSavedRegs(&F);
256 // These are used to keep track the callee-save area. Initialize them.
257 MinCSFrameIndex = INT_MAX;
260 // Early exit for targets which have no callee saved registers.
261 if (!CSRegs || CSRegs[0] == 0)
264 // In Naked functions we aren't going to save any registers.
265 if (F.getFunction()->hasFnAttribute(Attribute::Naked))
268 std::vector<CalleeSavedInfo> CSI;
269 for (unsigned i = 0; CSRegs[i]; ++i) {
270 unsigned Reg = CSRegs[i];
271 // Functions which call __builtin_unwind_init get all their registers saved.
272 if (F.getRegInfo().isPhysRegUsed(Reg) || F.getMMI().callsUnwindInit()) {
273 // If the reg is modified, save it!
274 CSI.push_back(CalleeSavedInfo(Reg));
278 if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
279 // If target doesn't implement this, use generic code.
282 return; // Early exit if no callee saved registers are modified!
284 unsigned NumFixedSpillSlots;
285 const TargetFrameLowering::SpillSlot *FixedSpillSlots =
286 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
288 // Now that we know which registers need to be saved and restored, allocate
289 // stack slots for them.
290 for (std::vector<CalleeSavedInfo>::iterator I = CSI.begin(), E = CSI.end();
292 unsigned Reg = I->getReg();
293 const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
296 if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {
297 I->setFrameIdx(FrameIdx);
301 // Check to see if this physreg must be spilled to a particular stack slot
303 const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;
304 while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
305 FixedSlot->Reg != Reg)
308 if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
309 // Nope, just spill it anywhere convenient.
310 unsigned Align = RC->getAlignment();
311 unsigned StackAlign = TFI->getStackAlignment();
313 // We may not be able to satisfy the desired alignment specification of
314 // the TargetRegisterClass if the stack alignment is smaller. Use the
316 Align = std::min(Align, StackAlign);
317 FrameIdx = MFI->CreateStackObject(RC->getSize(), Align, true);
318 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
319 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
321 // Spill it to the stack where we must.
323 MFI->CreateFixedSpillStackObject(RC->getSize(), FixedSlot->Offset);
326 I->setFrameIdx(FrameIdx);
330 MFI->setCalleeSavedInfo(CSI);
333 /// insertCSRSpillsAndRestores - Insert spill and restore code for
334 /// callee saved registers used in the function.
336 void PEI::insertCSRSpillsAndRestores(MachineFunction &Fn) {
337 // Get callee saved register information.
338 MachineFrameInfo *MFI = Fn.getFrameInfo();
339 const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
341 MFI->setCalleeSavedInfoValid(true);
343 // Early exit if no callee saved registers are modified!
347 const TargetInstrInfo &TII =
348 *Fn.getTarget().getSubtargetImpl()->getInstrInfo();
349 const TargetFrameLowering *TFI =
350 Fn.getTarget().getSubtargetImpl()->getFrameLowering();
351 const TargetRegisterInfo *TRI =
352 Fn.getTarget().getSubtargetImpl()->getRegisterInfo();
353 MachineBasicBlock::iterator I;
355 // Spill using target interface.
356 I = EntryBlock->begin();
357 if (!TFI->spillCalleeSavedRegisters(*EntryBlock, I, CSI, TRI)) {
358 for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
359 // Add the callee-saved register as live-in.
360 // It's killed at the spill.
361 EntryBlock->addLiveIn(CSI[i].getReg());
363 // Insert the spill to the stack frame.
364 unsigned Reg = CSI[i].getReg();
365 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
366 TII.storeRegToStackSlot(*EntryBlock, I, Reg, true, CSI[i].getFrameIdx(),
371 // Restore using target interface.
372 for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) {
373 MachineBasicBlock *MBB = ReturnBlocks[ri];
377 // Skip over all terminator instructions, which are part of the return
379 MachineBasicBlock::iterator I2 = I;
380 while (I2 != MBB->begin() && (--I2)->isTerminator())
383 bool AtStart = I == MBB->begin();
384 MachineBasicBlock::iterator BeforeI = I;
388 // Restore all registers immediately before the return and any
389 // terminators that precede it.
390 if (!TFI->restoreCalleeSavedRegisters(*MBB, I, CSI, TRI)) {
391 for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
392 unsigned Reg = CSI[i].getReg();
393 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
394 TII.loadRegFromStackSlot(*MBB, I, Reg, CSI[i].getFrameIdx(), RC, TRI);
395 assert(I != MBB->begin() &&
396 "loadRegFromStackSlot didn't insert any code!");
397 // Insert in reverse order. loadRegFromStackSlot can insert
398 // multiple instructions.
410 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
412 AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx,
413 bool StackGrowsDown, int64_t &Offset,
414 unsigned &MaxAlign) {
415 // If the stack grows down, add the object size to find the lowest address.
417 Offset += MFI->getObjectSize(FrameIdx);
419 unsigned Align = MFI->getObjectAlignment(FrameIdx);
421 // If the alignment of this object is greater than that of the stack, then
422 // increase the stack alignment to match.
423 MaxAlign = std::max(MaxAlign, Align);
425 // Adjust to alignment boundary.
426 Offset = (Offset + Align - 1) / Align * Align;
428 if (StackGrowsDown) {
429 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
430 MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
432 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
433 MFI->setObjectOffset(FrameIdx, Offset);
434 Offset += MFI->getObjectSize(FrameIdx);
438 /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
439 /// those required to be close to the Stack Protector) to stack offsets.
441 AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
442 SmallSet<int, 16> &ProtectedObjs,
443 MachineFrameInfo *MFI, bool StackGrowsDown,
444 int64_t &Offset, unsigned &MaxAlign) {
446 for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
447 E = UnassignedObjs.end(); I != E; ++I) {
449 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
450 ProtectedObjs.insert(i);
454 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
455 /// abstract stack objects.
457 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
458 const TargetFrameLowering &TFI =
459 *Fn.getTarget().getSubtargetImpl()->getFrameLowering();
460 StackProtector *SP = &getAnalysis<StackProtector>();
462 bool StackGrowsDown =
463 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
465 // Loop over all of the stack objects, assigning sequential addresses...
466 MachineFrameInfo *MFI = Fn.getFrameInfo();
468 // Start at the beginning of the local area.
469 // The Offset is the distance from the stack top in the direction
470 // of stack growth -- so it's always nonnegative.
471 int LocalAreaOffset = TFI.getOffsetOfLocalArea();
473 LocalAreaOffset = -LocalAreaOffset;
474 assert(LocalAreaOffset >= 0
475 && "Local area offset should be in direction of stack growth");
476 int64_t Offset = LocalAreaOffset;
478 // If there are fixed sized objects that are preallocated in the local area,
479 // non-fixed objects can't be allocated right at the start of local area.
480 // We currently don't support filling in holes in between fixed sized
481 // objects, so we adjust 'Offset' to point to the end of last fixed sized
482 // preallocated object.
483 for (int i = MFI->getObjectIndexBegin(); i != 0; ++i) {
485 if (StackGrowsDown) {
486 // The maximum distance from the stack pointer is at lower address of
487 // the object -- which is given by offset. For down growing stack
488 // the offset is negative, so we negate the offset to get the distance.
489 FixedOff = -MFI->getObjectOffset(i);
491 // The maximum distance from the start pointer is at the upper
492 // address of the object.
493 FixedOff = MFI->getObjectOffset(i) + MFI->getObjectSize(i);
495 if (FixedOff > Offset) Offset = FixedOff;
498 // First assign frame offsets to stack objects that are used to spill
499 // callee saved registers.
500 if (StackGrowsDown) {
501 for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
502 // If the stack grows down, we need to add the size to find the lowest
503 // address of the object.
504 Offset += MFI->getObjectSize(i);
506 unsigned Align = MFI->getObjectAlignment(i);
507 // Adjust to alignment boundary
508 Offset = (Offset+Align-1)/Align*Align;
510 MFI->setObjectOffset(i, -Offset); // Set the computed offset
513 int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex;
514 for (int i = MaxCSFI; i >= MinCSFI ; --i) {
515 unsigned Align = MFI->getObjectAlignment(i);
516 // Adjust to alignment boundary
517 Offset = (Offset+Align-1)/Align*Align;
519 MFI->setObjectOffset(i, Offset);
520 Offset += MFI->getObjectSize(i);
524 unsigned MaxAlign = MFI->getMaxAlignment();
526 // Make sure the special register scavenging spill slot is closest to the
527 // incoming stack pointer if a frame pointer is required and is closer
528 // to the incoming rather than the final stack pointer.
529 const TargetRegisterInfo *RegInfo =
530 Fn.getTarget().getSubtargetImpl()->getRegisterInfo();
531 bool EarlyScavengingSlots = (TFI.hasFP(Fn) &&
532 TFI.isFPCloseToIncomingSP() &&
533 RegInfo->useFPForScavengingIndex(Fn) &&
534 !RegInfo->needsStackRealignment(Fn));
535 if (RS && EarlyScavengingSlots) {
536 SmallVector<int, 2> SFIs;
537 RS->getScavengingFrameIndices(SFIs);
538 for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
539 IE = SFIs.end(); I != IE; ++I)
540 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign);
543 // FIXME: Once this is working, then enable flag will change to a target
544 // check for whether the frame is large enough to want to use virtual
545 // frame index registers. Functions which don't want/need this optimization
546 // will continue to use the existing code path.
547 if (MFI->getUseLocalStackAllocationBlock()) {
548 unsigned Align = MFI->getLocalFrameMaxAlign();
550 // Adjust to alignment boundary.
551 Offset = (Offset + Align - 1) / Align * Align;
553 DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
555 // Resolve offsets for objects in the local block.
556 for (unsigned i = 0, e = MFI->getLocalFrameObjectCount(); i != e; ++i) {
557 std::pair<int, int64_t> Entry = MFI->getLocalFrameObjectMap(i);
558 int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
559 DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" <<
561 MFI->setObjectOffset(Entry.first, FIOffset);
563 // Allocate the local block
564 Offset += MFI->getLocalFrameSize();
566 MaxAlign = std::max(Align, MaxAlign);
569 // Make sure that the stack protector comes before the local variables on the
571 SmallSet<int, 16> ProtectedObjs;
572 if (MFI->getStackProtectorIndex() >= 0) {
573 StackObjSet LargeArrayObjs;
574 StackObjSet SmallArrayObjs;
575 StackObjSet AddrOfObjs;
577 AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown,
580 // Assign large stack objects first.
581 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
582 if (MFI->isObjectPreAllocated(i) &&
583 MFI->getUseLocalStackAllocationBlock())
585 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
587 if (RS && RS->isScavengingFrameIndex((int)i))
589 if (MFI->isDeadObjectIndex(i))
591 if (MFI->getStackProtectorIndex() == (int)i)
594 switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) {
595 case StackProtector::SSPLK_None:
597 case StackProtector::SSPLK_SmallArray:
598 SmallArrayObjs.insert(i);
600 case StackProtector::SSPLK_AddrOf:
601 AddrOfObjs.insert(i);
603 case StackProtector::SSPLK_LargeArray:
604 LargeArrayObjs.insert(i);
607 llvm_unreachable("Unexpected SSPLayoutKind.");
610 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
612 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
614 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
618 // Then assign frame offsets to stack objects that are not used to spill
619 // callee saved registers.
620 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
621 if (MFI->isObjectPreAllocated(i) &&
622 MFI->getUseLocalStackAllocationBlock())
624 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
626 if (RS && RS->isScavengingFrameIndex((int)i))
628 if (MFI->isDeadObjectIndex(i))
630 if (MFI->getStackProtectorIndex() == (int)i)
632 if (ProtectedObjs.count(i))
635 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
638 // Make sure the special register scavenging spill slot is closest to the
640 if (RS && !EarlyScavengingSlots) {
641 SmallVector<int, 2> SFIs;
642 RS->getScavengingFrameIndices(SFIs);
643 for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
644 IE = SFIs.end(); I != IE; ++I)
645 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign);
648 if (!TFI.targetHandlesStackFrameRounding()) {
649 // If we have reserved argument space for call sites in the function
650 // immediately on entry to the current function, count it as part of the
651 // overall stack size.
652 if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn))
653 Offset += MFI->getMaxCallFrameSize();
655 // Round up the size to a multiple of the alignment. If the function has
656 // any calls or alloca's, align to the target's StackAlignment value to
657 // ensure that the callee's frame or the alloca data is suitably aligned;
658 // otherwise, for leaf functions, align to the TransientStackAlignment
661 if (MFI->adjustsStack() || MFI->hasVarSizedObjects() ||
662 (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0))
663 StackAlign = TFI.getStackAlignment();
665 StackAlign = TFI.getTransientStackAlignment();
667 // If the frame pointer is eliminated, all frame offsets will be relative to
668 // SP not FP. Align to MaxAlign so this works.
669 StackAlign = std::max(StackAlign, MaxAlign);
670 unsigned AlignMask = StackAlign - 1;
671 Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
674 // Update frame info to pretend that this is part of the stack...
675 int64_t StackSize = Offset - LocalAreaOffset;
676 MFI->setStackSize(StackSize);
677 NumBytesStackSpace += StackSize;
680 /// insertPrologEpilogCode - Scan the function for modified callee saved
681 /// registers, insert spill code for these callee saved registers, then add
682 /// prolog and epilog code to the function.
684 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
685 const TargetFrameLowering &TFI =
686 *Fn.getTarget().getSubtargetImpl()->getFrameLowering();
688 // Add prologue to the function...
689 TFI.emitPrologue(Fn);
691 // Add epilogue to restore the callee-save registers in each exiting block
692 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
693 // If last instruction is a return instruction, add an epilogue
694 if (!I->empty() && I->back().isReturn())
695 TFI.emitEpilogue(Fn, *I);
698 // Emit additional code that is required to support segmented stacks, if
699 // we've been asked for it. This, when linked with a runtime with support
700 // for segmented stacks (libgcc is one), will result in allocating stack
701 // space in small chunks instead of one large contiguous block.
702 if (Fn.shouldSplitStack())
703 TFI.adjustForSegmentedStacks(Fn);
705 // Emit additional code that is required to explicitly handle the stack in
706 // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
707 // approach is rather similar to that of Segmented Stacks, but it uses a
708 // different conditional check and another BIF for allocating more stack
710 if (Fn.getFunction()->getCallingConv() == CallingConv::HiPE)
711 TFI.adjustForHiPEPrologue(Fn);
714 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
715 /// register references and actual offsets.
717 void PEI::replaceFrameIndices(MachineFunction &Fn) {
718 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
720 // Store SPAdj at exit of a basic block.
721 SmallVector<int, 8> SPState;
722 SPState.resize(Fn.getNumBlockIDs());
723 SmallPtrSet<MachineBasicBlock*, 8> Reachable;
725 // Iterate over the reachable blocks in DFS order.
726 for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> >
727 DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable);
730 // Check the exit state of the DFS stack predecessor.
731 if (DFI.getPathLength() >= 2) {
732 MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
733 assert(Reachable.count(StackPred) &&
734 "DFS stack predecessor is already visited.\n");
735 SPAdj = SPState[StackPred->getNumber()];
737 MachineBasicBlock *BB = *DFI;
738 replaceFrameIndices(BB, Fn, SPAdj);
739 SPState[BB->getNumber()] = SPAdj;
742 // Handle the unreachable blocks.
743 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
744 if (Reachable.count(BB))
745 // Already handled in DFS traversal.
748 replaceFrameIndices(BB, Fn, SPAdj);
752 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
754 const TargetMachine &TM = Fn.getTarget();
755 assert(TM.getSubtargetImpl()->getRegisterInfo() &&
756 "TM::getRegisterInfo() must be implemented!");
757 const TargetInstrInfo &TII =
758 *Fn.getTarget().getSubtargetImpl()->getInstrInfo();
759 const TargetRegisterInfo &TRI = *TM.getSubtargetImpl()->getRegisterInfo();
760 const TargetFrameLowering *TFI = TM.getSubtargetImpl()->getFrameLowering();
761 bool StackGrowsDown =
762 TFI->getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
763 int FrameSetupOpcode = TII.getCallFrameSetupOpcode();
764 int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
766 if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB);
768 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
770 if (I->getOpcode() == FrameSetupOpcode ||
771 I->getOpcode() == FrameDestroyOpcode) {
772 // Remember how much SP has been adjusted to create the call
774 int Size = I->getOperand(0).getImm();
776 if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
777 (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
782 MachineBasicBlock::iterator PrevI = BB->end();
783 if (I != BB->begin()) PrevI = std::prev(I);
784 TFI->eliminateCallFramePseudoInstr(Fn, *BB, I);
786 // Visit the instructions created by eliminateCallFramePseudoInstr().
787 if (PrevI == BB->end())
788 I = BB->begin(); // The replaced instr was the first in the block.
790 I = std::next(PrevI);
794 MachineInstr *MI = I;
796 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
797 if (!MI->getOperand(i).isFI())
800 // Frame indicies in debug values are encoded in a target independent
801 // way with simply the frame index and offset rather than any
802 // target-specific addressing mode.
803 if (MI->isDebugValue()) {
804 assert(i == 0 && "Frame indicies can only appear as the first "
805 "operand of a DBG_VALUE machine instruction");
807 MachineOperand &Offset = MI->getOperand(1);
808 Offset.setImm(Offset.getImm() +
809 TFI->getFrameIndexReference(
810 Fn, MI->getOperand(0).getIndex(), Reg));
811 MI->getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
815 // Some instructions (e.g. inline asm instructions) can have
816 // multiple frame indices and/or cause eliminateFrameIndex
817 // to insert more than one instruction. We need the register
818 // scavenger to go through all of these instructions so that
819 // it can update its register information. We keep the
820 // iterator at the point before insertion so that we can
821 // revisit them in full.
822 bool AtBeginning = (I == BB->begin());
823 if (!AtBeginning) --I;
825 // If this instruction has a FrameIndex operand, we need to
826 // use that target machine register info object to eliminate
828 TRI.eliminateFrameIndex(MI, SPAdj, i,
829 FrameIndexVirtualScavenging ? nullptr : RS);
831 // Reset the iterator if we were at the beginning of the BB.
841 if (DoIncr && I != BB->end()) ++I;
843 // Update register states.
844 if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI);
848 /// scavengeFrameVirtualRegs - Replace all frame index virtual registers
849 /// with physical registers. Use the register scavenger to find an
850 /// appropriate register to use.
852 /// FIXME: Iterating over the instruction stream is unnecessary. We can simply
853 /// iterate over the vreg use list, which at this point only contains machine
854 /// operands for which eliminateFrameIndex need a new scratch reg.
856 PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) {
857 // Run through the instructions and find any virtual registers.
858 for (MachineFunction::iterator BB = Fn.begin(),
859 E = Fn.end(); BB != E; ++BB) {
860 RS->enterBasicBlock(BB);
864 // The instruction stream may change in the loop, so check BB->end()
866 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
867 // We might end up here again with a NULL iterator if we scavenged a
868 // register for which we inserted spill code for definition by what was
869 // originally the first instruction in BB.
870 if (I == MachineBasicBlock::iterator(nullptr))
873 MachineInstr *MI = I;
874 MachineBasicBlock::iterator J = std::next(I);
875 MachineBasicBlock::iterator P =
876 I == BB->begin() ? MachineBasicBlock::iterator(nullptr)
879 // RS should process this instruction before we might scavenge at this
880 // location. This is because we might be replacing a virtual register
881 // defined by this instruction, and if so, registers killed by this
882 // instruction are available, and defined registers are not.
885 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
886 if (MI->getOperand(i).isReg()) {
887 MachineOperand &MO = MI->getOperand(i);
888 unsigned Reg = MO.getReg();
891 if (!TargetRegisterInfo::isVirtualRegister(Reg))
894 // When we first encounter a new virtual register, it
895 // must be a definition.
896 assert(MI->getOperand(i).isDef() &&
897 "frame index virtual missing def!");
898 // Scavenge a new scratch register
899 const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
900 unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj);
904 // Replace this reference to the virtual register with the
906 assert (ScratchReg && "Missing scratch register!");
907 MachineRegisterInfo &MRI = Fn.getRegInfo();
908 Fn.getRegInfo().replaceRegWith(Reg, ScratchReg);
910 // Make sure MRI now accounts this register as used.
911 MRI.setPhysRegUsed(ScratchReg);
913 // Because this instruction was processed by the RS before this
914 // register was allocated, make sure that the RS now records the
915 // register as being used.
916 RS->setRegUsed(ScratchReg);
920 // If the scavenger needed to use one of its spill slots, the
921 // spill code will have been inserted in between I and J. This is a
922 // problem because we need the spill code before I: Move I to just
924 if (I != std::prev(J)) {
925 BB->splice(J, BB, I);
927 // Before we move I, we need to prepare the RS to visit I again.
928 // Specifically, RS will assert if it sees uses of registers that
929 // it believes are undefined. Because we have already processed
930 // register kills in I, when it visits I again, it will believe that
931 // those registers are undefined. To avoid this situation, unprocess
932 // the instruction I.
933 assert(RS->getCurrentPosition() == I &&
934 "The register scavenger has an unexpected position");