Long live the exception handling!
[oota-llvm.git] / lib / CodeGen / PrologEpilogInserter.cpp
1 //===-- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function --===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
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.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass is responsible for finalizing the functions frame layout, saving
11 // callee saved registers, and for emitting prolog & epilog code for the
12 // function.
13 //
14 // This pass must be run after register allocation.  After this pass is
15 // executed, it is illegal to construct MO_FrameIndex operands.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #include "llvm/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"
30 #include <climits>
31 using namespace llvm;
32
33 namespace {
34   struct VISIBILITY_HIDDEN PEI : public MachineFunctionPass {
35     static char ID;
36     PEI() : MachineFunctionPass((intptr_t)&ID) {}
37
38     const char *getPassName() const {
39       return "Prolog/Epilog Insertion & Frame Finalization";
40     }
41
42     /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
43     /// frame indexes with appropriate references.
44     ///
45     bool runOnMachineFunction(MachineFunction &Fn) {
46       const MRegisterInfo *MRI = Fn.getTarget().getRegisterInfo();
47       RS = MRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
48
49       // Get MachineModuleInfo so that we can track the construction of the
50       // frame.
51       if (MachineModuleInfo *MMI = getAnalysisToUpdate<MachineModuleInfo>()) {
52         Fn.getFrameInfo()->setMachineModuleInfo(MMI);
53       }
54
55       // Allow the target machine to make some adjustments to the function
56       // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
57       MRI->processFunctionBeforeCalleeSavedScan(Fn, RS);
58
59       // Scan the function for modified callee saved registers and insert spill
60       // code for any callee saved registers that are modified.  Also calculate
61       // the MaxCallFrameSize and HasCalls variables for the function's frame
62       // information and eliminates call frame pseudo instructions.
63       calculateCalleeSavedRegisters(Fn);
64
65       // Add the code to save and restore the callee saved registers
66       saveCalleeSavedRegisters(Fn);
67
68       // Allow the target machine to make final modifications to the function
69       // before the frame layout is finalized.
70       Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn);
71
72       // Calculate actual frame offsets for all of the abstract stack objects...
73       calculateFrameObjectOffsets(Fn);
74
75       // Add prolog and epilog code to the function.  This function is required
76       // to align the stack frame as necessary for any stack variables or
77       // called functions.  Because of this, calculateCalleeSavedRegisters
78       // must be called before this function in order to set the HasCalls
79       // and MaxCallFrameSize variables.
80       insertPrologEpilogCode(Fn);
81
82       // Replace all MO_FrameIndex operands with physical register references
83       // and actual offsets.
84       //
85       replaceFrameIndices(Fn);
86
87       delete RS;
88       return true;
89     }
90   
91   private:
92     RegScavenger *RS;
93
94     // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
95     // stack frame indexes.
96     unsigned MinCSFrameIndex, MaxCSFrameIndex;
97
98     void calculateCalleeSavedRegisters(MachineFunction &Fn);
99     void saveCalleeSavedRegisters(MachineFunction &Fn);
100     void calculateFrameObjectOffsets(MachineFunction &Fn);
101     void replaceFrameIndices(MachineFunction &Fn);
102     void insertPrologEpilogCode(MachineFunction &Fn);
103   };
104   char PEI::ID = 0;
105 }
106
107
108 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
109 /// prolog and epilog code, and eliminates abstract frame references.
110 ///
111 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
112
113
114 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
115 /// registers.  Also calculate the MaxCallFrameSize and HasCalls variables for
116 /// the function's frame information and eliminates call frame pseudo
117 /// instructions.
118 ///
119 void PEI::calculateCalleeSavedRegisters(MachineFunction &Fn) {
120   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
121   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
122
123   // Get the callee saved register list...
124   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(&Fn);
125
126   // Get the function call frame set-up and tear-down instruction opcode
127   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
128   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
129
130   // These are used to keep track the callee-save area. Initialize them.
131   MinCSFrameIndex = INT_MAX;
132   MaxCSFrameIndex = 0;
133
134   // Early exit for targets which have no callee saved registers and no call
135   // frame setup/destroy pseudo instructions.
136   if ((CSRegs == 0 || CSRegs[0] == 0) &&
137       FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
138     return;
139
140   unsigned MaxCallFrameSize = 0;
141   bool HasCalls = false;
142
143   std::vector<MachineBasicBlock::iterator> FrameSDOps;
144   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
145     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
146       if (I->getOpcode() == FrameSetupOpcode ||
147           I->getOpcode() == FrameDestroyOpcode) {
148         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
149                " instructions should have a single immediate argument!");
150         unsigned Size = I->getOperand(0).getImmedValue();
151         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
152         HasCalls = true;
153         FrameSDOps.push_back(I);
154       }
155
156   MachineFrameInfo *FFI = Fn.getFrameInfo();
157   FFI->setHasCalls(HasCalls);
158   FFI->setMaxCallFrameSize(MaxCallFrameSize);
159
160   for (unsigned i = 0, e = FrameSDOps.size(); i != e; ++i) {
161     MachineBasicBlock::iterator I = FrameSDOps[i];
162     // If call frames are not being included as part of the stack frame,
163     // and there is no dynamic allocation (therefore referencing frame slots
164     // off sp), leave the pseudo ops alone. We'll eliminate them later.
165     if (RegInfo->hasReservedCallFrame(Fn) || RegInfo->hasFP(Fn))
166       RegInfo->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
167   }
168
169   // Now figure out which *callee saved* registers are modified by the current
170   // function, thus needing to be saved and restored in the prolog/epilog.
171   //
172   const TargetRegisterClass* const *CSRegClasses =
173     RegInfo->getCalleeSavedRegClasses(&Fn);
174   std::vector<CalleeSavedInfo> CSI;
175   for (unsigned i = 0; CSRegs[i]; ++i) {
176     unsigned Reg = CSRegs[i];
177     if (Fn.isPhysRegUsed(Reg)) {
178         // If the reg is modified, save it!
179       CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
180     } else {
181       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
182            *AliasSet; ++AliasSet) {  // Check alias registers too.
183         if (Fn.isPhysRegUsed(*AliasSet)) {
184           CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
185           break;
186         }
187       }
188     }
189   }
190
191   if (CSI.empty())
192     return;   // Early exit if no callee saved registers are modified!
193
194   unsigned NumFixedSpillSlots;
195   const std::pair<unsigned,int> *FixedSpillSlots =
196     TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
197
198   // Now that we know which registers need to be saved and restored, allocate
199   // stack slots for them.
200   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
201     unsigned Reg = CSI[i].getReg();
202     const TargetRegisterClass *RC = CSI[i].getRegClass();
203
204     // Check to see if this physreg must be spilled to a particular stack slot
205     // on this target.
206     const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
207     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
208            FixedSlot->first != Reg)
209       ++FixedSlot;
210
211     int FrameIdx;
212     if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) {
213       // Nope, just spill it anywhere convenient.
214       unsigned Align = RC->getAlignment();
215       unsigned StackAlign = TFI->getStackAlignment();
216       // We may not be able to sastify the desired alignment specification of
217       // the TargetRegisterClass if the stack alignment is smaller. Use the min.
218       Align = std::min(Align, StackAlign);
219       FrameIdx = FFI->CreateStackObject(RC->getSize(), Align);
220       if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
221       if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
222     } else {
223       // Spill it to the stack where we must.
224       FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second);
225     }
226     CSI[i].setFrameIdx(FrameIdx);
227   }
228
229   FFI->setCalleeSavedInfo(CSI);
230 }
231
232 /// saveCalleeSavedRegisters -  Insert spill code for any callee saved registers
233 /// that are modified in the function.
234 ///
235 void PEI::saveCalleeSavedRegisters(MachineFunction &Fn) {
236   // Get callee saved register information.
237   MachineFrameInfo *FFI = Fn.getFrameInfo();
238   const std::vector<CalleeSavedInfo> &CSI = FFI->getCalleeSavedInfo();
239   
240   // Early exit if no callee saved registers are modified!
241   if (CSI.empty())
242     return;
243
244   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
245
246   // Now that we have a stack slot for each register to be saved, insert spill
247   // code into the entry block.
248   MachineBasicBlock *MBB = Fn.begin();
249   MachineBasicBlock::iterator I = MBB->begin();
250   if (!RegInfo->spillCalleeSavedRegisters(*MBB, I, CSI)) {
251     for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
252       // Add the callee-saved register as live-in. It's killed at the spill.
253       MBB->addLiveIn(CSI[i].getReg());
254
255       // Insert the spill to the stack frame.
256       RegInfo->storeRegToStackSlot(*MBB, I, CSI[i].getReg(),
257                                    CSI[i].getFrameIdx(), CSI[i].getRegClass());
258     }
259   }
260
261   // Add code to restore the callee-save registers in each exiting block.
262   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
263   for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI)
264     // If last instruction is a return instruction, add an epilogue.
265     if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) {
266       MBB = FI;
267       I = MBB->end(); --I;
268
269       // Skip over all terminator instructions, which are part of the return
270       // sequence.
271       MachineBasicBlock::iterator I2 = I;
272       while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode()))
273         I = I2;
274
275       bool AtStart = I == MBB->begin();
276       MachineBasicBlock::iterator BeforeI = I;
277       if (!AtStart)
278         --BeforeI;
279       
280       // Restore all registers immediately before the return and any terminators
281       // that preceed it.
282       if (!RegInfo->restoreCalleeSavedRegisters(*MBB, I, CSI)) {
283         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
284           RegInfo->loadRegFromStackSlot(*MBB, I, CSI[i].getReg(),
285                                         CSI[i].getFrameIdx(),
286                                         CSI[i].getRegClass());
287           assert(I != MBB->begin() &&
288                  "loadRegFromStackSlot didn't insert any code!");
289           // Insert in reverse order.  loadRegFromStackSlot can insert multiple
290           // instructions.
291           if (AtStart)
292             I = MBB->begin();
293           else {
294             I = BeforeI;
295             ++I;
296           }
297         }
298       }
299     }
300 }
301
302
303 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
304 /// abstract stack objects.
305 ///
306 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
307   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
308
309   bool StackGrowsDown =
310     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
311
312   // Loop over all of the stack objects, assigning sequential addresses...
313   MachineFrameInfo *FFI = Fn.getFrameInfo();
314
315   unsigned MaxAlign = 0;
316
317   // Start at the beginning of the local area.
318   // The Offset is the distance from the stack top in the direction
319   // of stack growth -- so it's always positive.
320   int64_t Offset = TFI.getOffsetOfLocalArea();
321   if (StackGrowsDown)
322     Offset = -Offset;
323   assert(Offset >= 0
324          && "Local area offset should be in direction of stack growth");
325
326   // If there are fixed sized objects that are preallocated in the local area,
327   // non-fixed objects can't be allocated right at the start of local area.
328   // We currently don't support filling in holes in between fixed sized objects,
329   // so we adjust 'Offset' to point to the end of last fixed sized
330   // preallocated object.
331   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
332     int64_t FixedOff;
333     if (StackGrowsDown) {
334       // The maximum distance from the stack pointer is at lower address of
335       // the object -- which is given by offset. For down growing stack
336       // the offset is negative, so we negate the offset to get the distance.
337       FixedOff = -FFI->getObjectOffset(i);
338     } else {
339       // The maximum distance from the start pointer is at the upper
340       // address of the object.
341       FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
342     }
343     if (FixedOff > Offset) Offset = FixedOff;
344   }
345
346   // First assign frame offsets to stack objects that are used to spill
347   // callee saved registers.
348   if (StackGrowsDown) {
349     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
350       // If stack grows down, we need to add size of find the lowest
351       // address of the object.
352       Offset += FFI->getObjectSize(i);
353
354       unsigned Align = FFI->getObjectAlignment(i);
355       // If the alignment of this object is greater than that of the stack, then
356       // increase the stack alignment to match.
357       MaxAlign = std::max(MaxAlign, Align);
358       // Adjust to alignment boundary
359       Offset = (Offset+Align-1)/Align*Align;
360
361       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
362     }
363   } else {
364     for (unsigned i = MaxCSFrameIndex; i >= MinCSFrameIndex; --i) {
365       unsigned Align = FFI->getObjectAlignment(i);
366       // If the alignment of this object is greater than that of the stack, then
367       // increase the stack alignment to match.
368       MaxAlign = std::max(MaxAlign, Align);
369       // Adjust to alignment boundary
370       Offset = (Offset+Align-1)/Align*Align;
371
372       FFI->setObjectOffset(i, Offset);
373       Offset += FFI->getObjectSize(i);
374     }
375   }
376
377   // Make sure the special register scavenging spill slot is closest to the
378   // frame pointer if a frame pointer is required.
379   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
380   if (RS && RegInfo->hasFP(Fn)) {
381     int SFI = RS->getScavengingFrameIndex();
382     if (SFI >= 0) {
383       // If stack grows down, we need to add size of the lowest
384       // address of the object.
385       if (StackGrowsDown)
386         Offset += FFI->getObjectSize(SFI);
387
388       unsigned Align = FFI->getObjectAlignment(SFI);
389       // Adjust to alignment boundary
390       Offset = (Offset+Align-1)/Align*Align;
391
392       if (StackGrowsDown) {
393         FFI->setObjectOffset(SFI, -Offset);        // Set the computed offset
394       } else {
395         FFI->setObjectOffset(SFI, Offset);
396         Offset += FFI->getObjectSize(SFI);
397       }
398     }
399   }
400
401   // Then assign frame offsets to stack objects that are not used to spill
402   // callee saved registers.
403   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
404     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
405       continue;
406     if (RS && (int)i == RS->getScavengingFrameIndex())
407       continue;
408
409     // If stack grows down, we need to add size of find the lowest
410     // address of the object.
411     if (StackGrowsDown)
412       Offset += FFI->getObjectSize(i);
413
414     unsigned Align = FFI->getObjectAlignment(i);
415     // If the alignment of this object is greater than that of the stack, then
416     // increase the stack alignment to match.
417     MaxAlign = std::max(MaxAlign, Align);
418     // Adjust to alignment boundary
419     Offset = (Offset+Align-1)/Align*Align;
420
421     if (StackGrowsDown) {
422       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
423     } else {
424       FFI->setObjectOffset(i, Offset);
425       Offset += FFI->getObjectSize(i);
426     }
427   }
428
429   // Make sure the special register scavenging spill slot is closest to the
430   // stack pointer.
431   if (RS && !RegInfo->hasFP(Fn)) {
432     int SFI = RS->getScavengingFrameIndex();
433     if (SFI >= 0) {
434       // If stack grows down, we need to add size of find the lowest
435       // address of the object.
436       if (StackGrowsDown)
437         Offset += FFI->getObjectSize(SFI);
438
439       unsigned Align = FFI->getObjectAlignment(SFI);
440       // Adjust to alignment boundary
441       Offset = (Offset+Align-1)/Align*Align;
442
443       if (StackGrowsDown) {
444         FFI->setObjectOffset(SFI, -Offset);        // Set the computed offset
445       } else {
446         FFI->setObjectOffset(SFI, Offset);
447         Offset += FFI->getObjectSize(SFI);
448       }
449     }
450   }
451
452   // Round up the size to a multiple of the alignment, but only if there are
453   // calls or alloca's in the function.  This ensures that any calls to
454   // subroutines have their stack frames suitable aligned.
455   if (!RegInfo->targetHandlesStackFrameRounding() &&
456       (FFI->hasCalls() || FFI->hasVarSizedObjects())) {
457     // If we have reserved argument space for call sites in the function
458     // immediately on entry to the current function, count it as part of the
459     // overall stack size.
460     if (RegInfo->hasReservedCallFrame(Fn))
461       Offset += FFI->getMaxCallFrameSize();
462
463     unsigned AlignMask = TFI.getStackAlignment() - 1;
464     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
465   }
466
467   // Update frame info to pretend that this is part of the stack...
468   FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea());
469
470   // Remember the required stack alignment in case targets need it to perform
471   // dynamic stack alignment.
472   assert(FFI->getMaxAlignment() == MaxAlign &&
473          "Stack alignment calculation broken!");
474 }
475
476
477 /// insertPrologEpilogCode - Scan the function for modified callee saved
478 /// registers, insert spill code for these callee saved registers, then add
479 /// prolog and epilog code to the function.
480 ///
481 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
482   // Add prologue to the function...
483   Fn.getTarget().getRegisterInfo()->emitPrologue(Fn);
484
485   // Add epilogue to restore the callee-save registers in each exiting block
486   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
487   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
488     // If last instruction is a return instruction, add an epilogue
489     if (!I->empty() && TII.isReturn(I->back().getOpcode()))
490       Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I);
491   }
492 }
493
494
495 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
496 /// register references and actual offsets.
497 ///
498 void PEI::replaceFrameIndices(MachineFunction &Fn) {
499   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
500
501   const TargetMachine &TM = Fn.getTarget();
502   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
503   const MRegisterInfo &MRI = *TM.getRegisterInfo();
504   const TargetFrameInfo *TFI = TM.getFrameInfo();
505   bool StackGrowsDown =
506     TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
507   int FrameSetupOpcode   = MRI.getCallFrameSetupOpcode();
508   int FrameDestroyOpcode = MRI.getCallFrameDestroyOpcode();
509
510   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
511     int SPAdj = 0;  // SP offset due to call frame setup / destroy.
512     if (RS) RS->enterBasicBlock(BB);
513     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
514       MachineInstr *MI = I;
515
516       // Remember how much SP has been adjustment to create the call frame.
517       if (I->getOpcode() == FrameSetupOpcode ||
518           I->getOpcode() == FrameDestroyOpcode) {
519         int Size = I->getOperand(0).getImmedValue();
520         if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
521             (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
522           Size = -Size;
523         SPAdj += Size;
524         MachineBasicBlock::iterator PrevI = prior(I);
525         MRI.eliminateCallFramePseudoInstr(Fn, *BB, I);
526         // Visit the instructions created by eliminateCallFramePseudoInstr().
527         I = next(PrevI);
528         MI = NULL;
529       } else {
530         I++;
531         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
532           if (MI->getOperand(i).isFrameIndex()) {
533             // If this instruction has a FrameIndex operand, we need to use that
534             // target machine register info object to eliminate it.
535             MRI.eliminateFrameIndex(MI, SPAdj, RS);
536
537             // Revisit the instruction in full.  Some instructions (e.g. inline
538             // asm instructions) can have multiple frame indices.
539             --I;
540             MI = 0;
541             break;
542           }
543       }
544       // Update register states.
545       if (RS && MI) RS->forward(MI);
546     }
547     assert(SPAdj == 0 && "Unbalanced call frame setup / destroy pairs?");
548   }
549 }