1 //===-- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function --===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/CodeGen/Passes.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineFrameInfo.h"
23 #include "llvm/CodeGen/RegisterScavenging.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/MRegisterInfo.h"
26 #include "llvm/Target/TargetFrameInfo.h"
27 #include "llvm/Target/TargetInstrInfo.h"
28 #include "llvm/Support/Compiler.h"
29 #include "llvm/ADT/STLExtras.h"
34 struct VISIBILITY_HIDDEN PEI : public MachineFunctionPass {
35 const char *getPassName() const {
36 return "Prolog/Epilog Insertion & Frame Finalization";
39 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
40 /// frame indexes with appropriate references.
42 bool runOnMachineFunction(MachineFunction &Fn) {
43 const MRegisterInfo *MRI = Fn.getTarget().getRegisterInfo();
44 RS = MRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
46 // Get MachineModuleInfo so that we can track the construction of the
48 if (MachineModuleInfo *MMI = getAnalysisToUpdate<MachineModuleInfo>()) {
49 Fn.getFrameInfo()->setMachineModuleInfo(MMI);
52 // Allow the target machine to make some adjustments to the function
53 // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
54 MRI->processFunctionBeforeCalleeSavedScan(Fn, RS);
56 // Scan the function for modified callee saved registers and insert spill
57 // code for any callee saved registers that are modified. Also calculate
58 // the MaxCallFrameSize and HasCalls variables for the function's frame
59 // information and eliminates call frame pseudo instructions.
60 calculateCalleeSavedRegisters(Fn);
62 // Add the code to save and restore the callee saved registers
63 saveCalleeSavedRegisters(Fn);
65 // Allow the target machine to make final modifications to the function
66 // before the frame layout is finalized.
67 Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn);
69 // Calculate actual frame offsets for all of the abstract stack objects...
70 calculateFrameObjectOffsets(Fn);
72 // Add prolog and epilog code to the function. This function is required
73 // to align the stack frame as necessary for any stack variables or
74 // called functions. Because of this, calculateCalleeSavedRegisters
75 // must be called before this function in order to set the HasCalls
76 // and MaxCallFrameSize variables.
77 insertPrologEpilogCode(Fn);
79 // Replace all MO_FrameIndex operands with physical register references
80 // and actual offsets.
82 replaceFrameIndices(Fn);
91 // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
92 // stack frame indexes.
93 unsigned MinCSFrameIndex, MaxCSFrameIndex;
95 void calculateCalleeSavedRegisters(MachineFunction &Fn);
96 void saveCalleeSavedRegisters(MachineFunction &Fn);
97 void calculateFrameObjectOffsets(MachineFunction &Fn);
98 void replaceFrameIndices(MachineFunction &Fn);
99 void insertPrologEpilogCode(MachineFunction &Fn);
104 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
105 /// prolog and epilog code, and eliminates abstract frame references.
107 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
110 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
111 /// registers. Also calculate the MaxCallFrameSize and HasCalls variables for
112 /// the function's frame information and eliminates call frame pseudo
115 void PEI::calculateCalleeSavedRegisters(MachineFunction &Fn) {
116 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
117 const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
119 // Get the callee saved register list...
120 const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
122 // Get the function call frame set-up and tear-down instruction opcode
123 int FrameSetupOpcode = RegInfo->getCallFrameSetupOpcode();
124 int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
126 // These are used to keep track the callee-save area. Initialize them.
127 MinCSFrameIndex = INT_MAX;
130 // Early exit for targets which have no callee saved registers and no call
131 // frame setup/destroy pseudo instructions.
132 if ((CSRegs == 0 || CSRegs[0] == 0) &&
133 FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
136 unsigned MaxCallFrameSize = 0;
137 bool HasCalls = false;
139 std::vector<MachineBasicBlock::iterator> FrameSDOps;
140 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
141 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
142 if (I->getOpcode() == FrameSetupOpcode ||
143 I->getOpcode() == FrameDestroyOpcode) {
144 assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
145 " instructions should have a single immediate argument!");
146 unsigned Size = I->getOperand(0).getImmedValue();
147 if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
149 FrameSDOps.push_back(I);
152 MachineFrameInfo *FFI = Fn.getFrameInfo();
153 FFI->setHasCalls(HasCalls);
154 FFI->setMaxCallFrameSize(MaxCallFrameSize);
156 for (unsigned i = 0, e = FrameSDOps.size(); i != e; ++i) {
157 MachineBasicBlock::iterator I = FrameSDOps[i];
158 // If call frames are not being included as part of the stack frame,
159 // and there is no dynamic allocation (therefore referencing frame slots
160 // off sp), leave the pseudo ops alone. We'll eliminate them later.
161 if (RegInfo->hasReservedCallFrame(Fn) || RegInfo->hasFP(Fn))
162 RegInfo->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
165 // Now figure out which *callee saved* registers are modified by the current
166 // function, thus needing to be saved and restored in the prolog/epilog.
168 const TargetRegisterClass* const *CSRegClasses =
169 RegInfo->getCalleeSavedRegClasses();
170 std::vector<CalleeSavedInfo> CSI;
171 for (unsigned i = 0; CSRegs[i]; ++i) {
172 unsigned Reg = CSRegs[i];
173 if (Fn.isPhysRegUsed(Reg)) {
174 // If the reg is modified, save it!
175 CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
177 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
178 *AliasSet; ++AliasSet) { // Check alias registers too.
179 if (Fn.isPhysRegUsed(*AliasSet)) {
180 CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
188 return; // Early exit if no callee saved registers are modified!
190 unsigned NumFixedSpillSlots;
191 const std::pair<unsigned,int> *FixedSpillSlots =
192 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
194 // Now that we know which registers need to be saved and restored, allocate
195 // stack slots for them.
196 for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
197 unsigned Reg = CSI[i].getReg();
198 const TargetRegisterClass *RC = CSI[i].getRegClass();
200 // Check to see if this physreg must be spilled to a particular stack slot
202 const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
203 while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
204 FixedSlot->first != Reg)
208 if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) {
209 // Nope, just spill it anywhere convenient.
210 unsigned Align = RC->getAlignment();
211 unsigned StackAlign = TFI->getStackAlignment();
212 // We may not be able to sastify the desired alignment specification of
213 // the TargetRegisterClass if the stack alignment is smaller. Use the min.
214 Align = std::min(Align, StackAlign);
215 FrameIdx = FFI->CreateStackObject(RC->getSize(), Align);
216 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
217 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
219 // Spill it to the stack where we must.
220 FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second);
222 CSI[i].setFrameIdx(FrameIdx);
225 FFI->setCalleeSavedInfo(CSI);
228 /// saveCalleeSavedRegisters - Insert spill code for any callee saved registers
229 /// that are modified in the function.
231 void PEI::saveCalleeSavedRegisters(MachineFunction &Fn) {
232 // Get callee saved register information.
233 MachineFrameInfo *FFI = Fn.getFrameInfo();
234 const std::vector<CalleeSavedInfo> &CSI = FFI->getCalleeSavedInfo();
236 // Early exit if no callee saved registers are modified!
240 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
242 // Now that we have a stack slot for each register to be saved, insert spill
243 // code into the entry block.
244 MachineBasicBlock *MBB = Fn.begin();
245 MachineBasicBlock::iterator I = MBB->begin();
246 if (!RegInfo->spillCalleeSavedRegisters(*MBB, I, CSI)) {
247 for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
248 // Add the callee-saved register as live-in. It's killed at the spill.
249 MBB->addLiveIn(CSI[i].getReg());
251 // Insert the spill to the stack frame.
252 RegInfo->storeRegToStackSlot(*MBB, I, CSI[i].getReg(),
253 CSI[i].getFrameIdx(), CSI[i].getRegClass());
257 // Add code to restore the callee-save registers in each exiting block.
258 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
259 for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI)
260 // If last instruction is a return instruction, add an epilogue.
261 if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) {
265 // Skip over all terminator instructions, which are part of the return
267 MachineBasicBlock::iterator I2 = I;
268 while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode()))
271 bool AtStart = I == MBB->begin();
272 MachineBasicBlock::iterator BeforeI = I;
276 // Restore all registers immediately before the return and any terminators
278 if (!RegInfo->restoreCalleeSavedRegisters(*MBB, I, CSI)) {
279 for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
280 RegInfo->loadRegFromStackSlot(*MBB, I, CSI[i].getReg(),
281 CSI[i].getFrameIdx(),
282 CSI[i].getRegClass());
283 assert(I != MBB->begin() &&
284 "loadRegFromStackSlot didn't insert any code!");
285 // Insert in reverse order. loadRegFromStackSlot can insert multiple
299 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
300 /// abstract stack objects.
302 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
303 const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
305 bool StackGrowsDown =
306 TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
308 // Loop over all of the stack objects, assigning sequential addresses...
309 MachineFrameInfo *FFI = Fn.getFrameInfo();
311 unsigned MaxAlign = 0;
313 // Start at the beginning of the local area.
314 // The Offset is the distance from the stack top in the direction
315 // of stack growth -- so it's always positive.
316 int64_t Offset = TFI.getOffsetOfLocalArea();
320 && "Local area offset should be in direction of stack growth");
322 // If there are fixed sized objects that are preallocated in the local area,
323 // non-fixed objects can't be allocated right at the start of local area.
324 // We currently don't support filling in holes in between fixed sized objects,
325 // so we adjust 'Offset' to point to the end of last fixed sized
326 // preallocated object.
327 for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
329 if (StackGrowsDown) {
330 // The maximum distance from the stack pointer is at lower address of
331 // the object -- which is given by offset. For down growing stack
332 // the offset is negative, so we negate the offset to get the distance.
333 FixedOff = -FFI->getObjectOffset(i);
335 // The maximum distance from the start pointer is at the upper
336 // address of the object.
337 FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
339 if (FixedOff > Offset) Offset = FixedOff;
342 // First assign frame offsets to stack objects that are used to spill
343 // callee saved registers.
344 if (StackGrowsDown) {
345 for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
346 // If stack grows down, we need to add size of find the lowest
347 // address of the object.
348 Offset += FFI->getObjectSize(i);
350 unsigned Align = FFI->getObjectAlignment(i);
351 // If the alignment of this object is greater than that of the stack, then
352 // increase the stack alignment to match.
353 MaxAlign = std::max(MaxAlign, Align);
354 // Adjust to alignment boundary
355 Offset = (Offset+Align-1)/Align*Align;
357 FFI->setObjectOffset(i, -Offset); // Set the computed offset
360 for (unsigned i = MaxCSFrameIndex; i >= MinCSFrameIndex; --i) {
361 unsigned Align = FFI->getObjectAlignment(i);
362 // If the alignment of this object is greater than that of the stack, then
363 // increase the stack alignment to match.
364 MaxAlign = std::max(MaxAlign, Align);
365 // Adjust to alignment boundary
366 Offset = (Offset+Align-1)/Align*Align;
368 FFI->setObjectOffset(i, Offset);
369 Offset += FFI->getObjectSize(i);
373 // Make sure the special register scavenging spill slot is closest to the
374 // frame pointer if a frame pointer is required.
375 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
376 if (RS && RegInfo->hasFP(Fn)) {
377 int SFI = RS->getScavengingFrameIndex();
379 // If stack grows down, we need to add size of the lowest
380 // address of the object.
382 Offset += FFI->getObjectSize(SFI);
384 unsigned Align = FFI->getObjectAlignment(SFI);
385 // Adjust to alignment boundary
386 Offset = (Offset+Align-1)/Align*Align;
388 if (StackGrowsDown) {
389 FFI->setObjectOffset(SFI, -Offset); // Set the computed offset
391 FFI->setObjectOffset(SFI, Offset);
392 Offset += FFI->getObjectSize(SFI);
397 // Then assign frame offsets to stack objects that are not used to spill
398 // callee saved registers.
399 for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
400 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
402 if (RS && (int)i == RS->getScavengingFrameIndex())
405 // If stack grows down, we need to add size of find the lowest
406 // address of the object.
408 Offset += FFI->getObjectSize(i);
410 unsigned Align = FFI->getObjectAlignment(i);
411 // If the alignment of this object is greater than that of the stack, then
412 // increase the stack alignment to match.
413 MaxAlign = std::max(MaxAlign, Align);
414 // Adjust to alignment boundary
415 Offset = (Offset+Align-1)/Align*Align;
417 if (StackGrowsDown) {
418 FFI->setObjectOffset(i, -Offset); // Set the computed offset
420 FFI->setObjectOffset(i, Offset);
421 Offset += FFI->getObjectSize(i);
425 // Make sure the special register scavenging spill slot is closest to the
428 int SFI = RS->getScavengingFrameIndex();
430 // If stack grows down, we need to add size of find the lowest
431 // address of the object.
433 Offset += FFI->getObjectSize(SFI);
435 unsigned Align = FFI->getObjectAlignment(SFI);
436 // Adjust to alignment boundary
437 Offset = (Offset+Align-1)/Align*Align;
439 if (StackGrowsDown) {
440 FFI->setObjectOffset(SFI, -Offset); // Set the computed offset
442 FFI->setObjectOffset(SFI, Offset);
443 Offset += FFI->getObjectSize(SFI);
448 // Round up the size to a multiple of the alignment, but only if there are
449 // calls or alloca's in the function. This ensures that any calls to
450 // subroutines have their stack frames suitable aligned.
451 if (!RegInfo->targetHandlesStackFrameRounding() &&
452 (FFI->hasCalls() || FFI->hasVarSizedObjects())) {
453 // If we have reserved argument space for call sites in the function
454 // immediately on entry to the current function, count it as part of the
455 // overall stack size.
456 if (RegInfo->hasReservedCallFrame(Fn))
457 Offset += FFI->getMaxCallFrameSize();
459 unsigned AlignMask = TFI.getStackAlignment() - 1;
460 Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
463 // Update frame info to pretend that this is part of the stack...
464 FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea());
466 // Remember the required stack alignment in case targets need it to perform
467 // dynamic stack alignment.
468 assert(FFI->getMaxAlignment() == MaxAlign &&
469 "Stack alignment calculation broken!");
473 /// insertPrologEpilogCode - Scan the function for modified callee saved
474 /// registers, insert spill code for these callee saved registers, then add
475 /// prolog and epilog code to the function.
477 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
478 // Add prologue to the function...
479 Fn.getTarget().getRegisterInfo()->emitPrologue(Fn);
481 // Add epilogue to restore the callee-save registers in each exiting block
482 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
483 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
484 // If last instruction is a return instruction, add an epilogue
485 if (!I->empty() && TII.isReturn(I->back().getOpcode()))
486 Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I);
491 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
492 /// register references and actual offsets.
494 void PEI::replaceFrameIndices(MachineFunction &Fn) {
495 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
497 const TargetMachine &TM = Fn.getTarget();
498 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
499 const MRegisterInfo &MRI = *TM.getRegisterInfo();
500 const TargetFrameInfo *TFI = TM.getFrameInfo();
501 bool StackGrowsDown =
502 TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
503 int FrameSetupOpcode = MRI.getCallFrameSetupOpcode();
504 int FrameDestroyOpcode = MRI.getCallFrameDestroyOpcode();
506 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
507 int SPAdj = 0; // SP offset due to call frame setup / destroy.
508 if (RS) RS->enterBasicBlock(BB);
509 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
510 MachineInstr *MI = I;
512 // Remember how much SP has been adjustment to create the call frame.
513 if (I->getOpcode() == FrameSetupOpcode ||
514 I->getOpcode() == FrameDestroyOpcode) {
515 int Size = I->getOperand(0).getImmedValue();
516 if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
517 (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
520 MachineBasicBlock::iterator PrevI = prior(I);
521 MRI.eliminateCallFramePseudoInstr(Fn, *BB, I);
522 // Visit the instructions created by eliminateCallFramePseudoInstr().
527 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
528 if (MI->getOperand(i).isFrameIndex()) {
529 // If this instruction has a FrameIndex operand, we need to use that
530 // target machine register info object to eliminate it.
531 MRI.eliminateFrameIndex(MI, SPAdj, RS);
533 // Revisit the instruction in full. Some instructions (e.g. inline
534 // asm instructions) can have multiple frame indices.
540 // Update register states.
541 if (RS && MI) RS->forward(MI);
543 assert(SPAdj == 0 && "Unbalanced call frame setup / destroy pairs?");