LLVM API Documentation

PrologEpilogInserter.cpp

Go to the documentation of this file.
00001 //===-- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass is responsible for finalizing the functions frame layout, saving
00011 // callee saved registers, and for emitting prolog & epilog code for the
00012 // function.
00013 //
00014 // This pass must be run after register allocation.  After this pass is
00015 // executed, it is illegal to construct MO_FrameIndex operands.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "llvm/CodeGen/Passes.h"
00020 #include "llvm/CodeGen/MachineFunctionPass.h"
00021 #include "llvm/CodeGen/MachineInstr.h"
00022 #include "llvm/CodeGen/MachineFrameInfo.h"
00023 #include "llvm/Target/TargetMachine.h"
00024 #include "llvm/Target/MRegisterInfo.h"
00025 #include "llvm/Target/TargetFrameInfo.h"
00026 #include "llvm/Target/TargetInstrInfo.h"
00027 #include "llvm/Support/Visibility.h"
00028 using namespace llvm;
00029 
00030 namespace {
00031   struct VISIBILITY_HIDDEN PEI : public MachineFunctionPass {
00032     const char *getPassName() const {
00033       return "Prolog/Epilog Insertion & Frame Finalization";
00034     }
00035 
00036     /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
00037     /// frame indexes with appropriate references.
00038     ///
00039     bool runOnMachineFunction(MachineFunction &Fn) {
00040       // Get MachineDebugInfo so that we can track the construction of the
00041       // frame.
00042       if (MachineDebugInfo *DI = getAnalysisToUpdate<MachineDebugInfo>()) {
00043         Fn.getFrameInfo()->setMachineDebugInfo(DI);
00044       }
00045       
00046       // Scan the function for modified caller saved registers and insert spill
00047       // code for any caller saved registers that are modified.  Also calculate
00048       // the MaxCallFrameSize and HasCalls variables for the function's frame
00049       // information and eliminates call frame pseudo instructions.
00050       calculateCallerSavedRegisters(Fn);
00051 
00052       // Add the code to save and restore the caller saved registers
00053       saveCallerSavedRegisters(Fn);
00054 
00055       // Allow the target machine to make final modifications to the function
00056       // before the frame layout is finalized.
00057       Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn);
00058 
00059       // Calculate actual frame offsets for all of the abstract stack objects...
00060       calculateFrameObjectOffsets(Fn);
00061 
00062       // Add prolog and epilog code to the function.  This function is required
00063       // to align the stack frame as necessary for any stack variables or
00064       // called functions.  Because of this, calculateCallerSavedRegisters
00065       // must be called before this function in order to set the HasCalls
00066       // and MaxCallFrameSize variables.
00067       insertPrologEpilogCode(Fn);
00068 
00069       // Replace all MO_FrameIndex operands with physical register references
00070       // and actual offsets.
00071       //
00072       replaceFrameIndices(Fn);
00073 
00074       RegsToSave.clear();
00075       StackSlots.clear();
00076       return true;
00077     }
00078 
00079   private:
00080     std::vector<std::pair<unsigned, const TargetRegisterClass*> > RegsToSave;
00081     std::vector<int> StackSlots;
00082 
00083     void calculateCallerSavedRegisters(MachineFunction &Fn);
00084     void saveCallerSavedRegisters(MachineFunction &Fn);
00085     void calculateFrameObjectOffsets(MachineFunction &Fn);
00086     void replaceFrameIndices(MachineFunction &Fn);
00087     void insertPrologEpilogCode(MachineFunction &Fn);
00088   };
00089 }
00090 
00091 
00092 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
00093 /// prolog and epilog code, and eliminates abstract frame references.
00094 ///
00095 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
00096 
00097 
00098 /// calculateCallerSavedRegisters - Scan the function for modified caller saved
00099 /// registers.  Also calculate the MaxCallFrameSize and HasCalls variables for
00100 /// the function's frame information and eliminates call frame pseudo
00101 /// instructions.
00102 ///
00103 void PEI::calculateCallerSavedRegisters(MachineFunction &Fn) {
00104   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
00105   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
00106 
00107   // Get the callee saved register list...
00108   const unsigned *CSRegs = RegInfo->getCalleeSaveRegs();
00109 
00110   // Get the function call frame set-up and tear-down instruction opcode
00111   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
00112   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
00113 
00114   // Early exit for targets which have no callee saved registers and no call
00115   // frame setup/destroy pseudo instructions.
00116   if ((CSRegs == 0 || CSRegs[0] == 0) &&
00117       FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
00118     return;
00119 
00120   unsigned MaxCallFrameSize = 0;
00121   bool HasCalls = false;
00122 
00123   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
00124     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); )
00125       if (I->getOpcode() == FrameSetupOpcode ||
00126           I->getOpcode() == FrameDestroyOpcode) {
00127         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
00128                " instructions should have a single immediate argument!");
00129         unsigned Size = I->getOperand(0).getImmedValue();
00130         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
00131         HasCalls = true;
00132         RegInfo->eliminateCallFramePseudoInstr(Fn, *BB, I++);
00133       } else {
00134         ++I;
00135       }
00136 
00137   MachineFrameInfo *FFI = Fn.getFrameInfo();
00138   FFI->setHasCalls(HasCalls);
00139   FFI->setMaxCallFrameSize(MaxCallFrameSize);
00140 
00141   // Now figure out which *callee saved* registers are modified by the current
00142   // function, thus needing to be saved and restored in the prolog/epilog.
00143   //
00144   const bool *PhysRegsUsed = Fn.getUsedPhysregs();
00145   const TargetRegisterClass* const *CSRegClasses =
00146     RegInfo->getCalleeSaveRegClasses();
00147   for (unsigned i = 0; CSRegs[i]; ++i) {
00148     unsigned Reg = CSRegs[i];
00149     if (PhysRegsUsed[Reg]) {
00150         // If the reg is modified, save it!
00151       RegsToSave.push_back(std::make_pair(Reg, CSRegClasses[i]));
00152     } else {
00153       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
00154            *AliasSet; ++AliasSet) {  // Check alias registers too.
00155         if (PhysRegsUsed[*AliasSet]) {
00156           RegsToSave.push_back(std::make_pair(Reg, CSRegClasses[i]));
00157           break;
00158         }
00159       }
00160     }
00161   }
00162 
00163   if (RegsToSave.empty())
00164     return;   // Early exit if no caller saved registers are modified!
00165 
00166   unsigned NumFixedSpillSlots;
00167   const std::pair<unsigned,int> *FixedSpillSlots =
00168     TFI->getCalleeSaveSpillSlots(NumFixedSpillSlots);
00169 
00170   // Now that we know which registers need to be saved and restored, allocate
00171   // stack slots for them.
00172   for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) {
00173     unsigned Reg = RegsToSave[i].first;
00174     const TargetRegisterClass *RC = RegsToSave[i].second;
00175 
00176     // Check to see if this physreg must be spilled to a particular stack slot
00177     // on this target.
00178     const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
00179     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
00180            FixedSlot->first != Reg)
00181       ++FixedSlot;
00182 
00183     int FrameIdx;
00184     if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) {
00185       // Nope, just spill it anywhere convenient.
00186       FrameIdx = FFI->CreateStackObject(RC->getSize(), RC->getAlignment());
00187     } else {
00188       // Spill it to the stack where we must.
00189       FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second);
00190     }
00191     StackSlots.push_back(FrameIdx);
00192   }
00193 }
00194 
00195 /// saveCallerSavedRegisters -  Insert spill code for any caller saved registers
00196 /// that are modified in the function.
00197 ///
00198 void PEI::saveCallerSavedRegisters(MachineFunction &Fn) {
00199   // Early exit if no caller saved registers are modified!
00200   if (RegsToSave.empty())
00201     return;
00202 
00203   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
00204 
00205   // Now that we have a stack slot for each register to be saved, insert spill
00206   // code into the entry block.
00207   MachineBasicBlock *MBB = Fn.begin();
00208   MachineBasicBlock::iterator I = MBB->begin();
00209   for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) {
00210     // Insert the spill to the stack frame.
00211     RegInfo->storeRegToStackSlot(*MBB, I, RegsToSave[i].first, StackSlots[i],
00212                                  RegsToSave[i].second);
00213   }
00214 
00215   // Add code to restore the callee-save registers in each exiting block.
00216   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
00217   for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI)
00218     // If last instruction is a return instruction, add an epilogue.
00219     if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) {
00220       MBB = FI;
00221       I = MBB->end(); --I;
00222 
00223       // Skip over all terminator instructions, which are part of the return
00224       // sequence.
00225       MachineBasicBlock::iterator I2 = I;
00226       while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode()))
00227         I = I2;
00228 
00229       bool AtStart = I == MBB->begin();
00230       MachineBasicBlock::iterator BeforeI = I;
00231       if (!AtStart)
00232         --BeforeI;
00233       
00234       // Restore all registers immediately before the return and any terminators
00235       // that preceed it.
00236       for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) {
00237         RegInfo->loadRegFromStackSlot(*MBB, I, RegsToSave[i].first,
00238                                       StackSlots[i], RegsToSave[i].second);
00239         assert(I != MBB->begin() &&
00240                "loadRegFromStackSlot didn't insert any code!");
00241         // Insert in reverse order.  loadRegFromStackSlot can insert multiple
00242         // instructions.
00243         if (AtStart)
00244           I = MBB->begin();
00245         else {
00246           I = BeforeI;
00247           ++I;
00248         }
00249       }
00250     }
00251 }
00252 
00253 
00254 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
00255 /// abstract stack objects.
00256 ///
00257 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
00258   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
00259 
00260   bool StackGrowsDown =
00261     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
00262 
00263   // Loop over all of the stack objects, assigning sequential addresses...
00264   MachineFrameInfo *FFI = Fn.getFrameInfo();
00265 
00266   unsigned StackAlignment = TFI.getStackAlignment();
00267   unsigned MaxAlign = 0;
00268 
00269   // Start at the beginning of the local area.
00270   // The Offset is the distance from the stack top in the direction
00271   // of stack growth -- so it's always positive.
00272   int Offset = TFI.getOffsetOfLocalArea();
00273   if (StackGrowsDown)
00274     Offset = -Offset;
00275   assert(Offset >= 0
00276          && "Local area offset should be in direction of stack growth");
00277 
00278   // If there are fixed sized objects that are preallocated in the local area,
00279   // non-fixed objects can't be allocated right at the start of local area.
00280   // We currently don't support filling in holes in between fixed sized objects,
00281   // so we adjust 'Offset' to point to the end of last fixed sized
00282   // preallocated object.
00283   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
00284     int FixedOff;
00285     if (StackGrowsDown) {
00286       // The maximum distance from the stack pointer is at lower address of
00287       // the object -- which is given by offset. For down growing stack
00288       // the offset is negative, so we negate the offset to get the distance.
00289       FixedOff = -FFI->getObjectOffset(i);
00290     } else {
00291       // The maximum distance from the start pointer is at the upper
00292       // address of the object.
00293       FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
00294     }
00295     if (FixedOff > Offset) Offset = FixedOff;
00296   }
00297 
00298   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
00299     // If stack grows down, we need to add size of find the lowest
00300     // address of the object.
00301     if (StackGrowsDown)
00302       Offset += FFI->getObjectSize(i);
00303 
00304     unsigned Align = FFI->getObjectAlignment(i);
00305     // If the alignment of this object is greater than that of the stack, then
00306     // increase the stack alignment to match.
00307     MaxAlign = std::max(MaxAlign, Align);
00308     // Adjust to alignment boundary
00309     Offset = (Offset+Align-1)/Align*Align;
00310 
00311     if (StackGrowsDown) {
00312       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
00313     } else {
00314       FFI->setObjectOffset(i, Offset);
00315       Offset += FFI->getObjectSize(i);
00316     }
00317   }
00318 
00319   // Align the final stack pointer offset, but only if there are calls in the
00320   // function.  This ensures that any calls to subroutines have their stack
00321   // frames suitable aligned.
00322   if (FFI->hasCalls())
00323     Offset = (Offset+StackAlignment-1)/StackAlignment*StackAlignment;
00324 
00325   // Set the final value of the stack pointer...
00326   FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea());
00327 
00328   // Remember the required stack alignment in case targets need it to perform
00329   // dynamic stack alignment.
00330   assert(FFI->getMaxAlignment() == MaxAlign &&
00331          "Stack alignment calculation broken!");
00332 }
00333 
00334 
00335 /// insertPrologEpilogCode - Scan the function for modified caller saved
00336 /// registers, insert spill code for these caller saved registers, then add
00337 /// prolog and epilog code to the function.
00338 ///
00339 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
00340   // Add prologue to the function...
00341   Fn.getTarget().getRegisterInfo()->emitPrologue(Fn);
00342 
00343   // Add epilogue to restore the callee-save registers in each exiting block
00344   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
00345   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
00346     // If last instruction is a return instruction, add an epilogue
00347     if (!I->empty() && TII.isReturn(I->back().getOpcode()))
00348       Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I);
00349   }
00350 }
00351 
00352 
00353 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
00354 /// register references and actual offsets.
00355 ///
00356 void PEI::replaceFrameIndices(MachineFunction &Fn) {
00357   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
00358 
00359   const TargetMachine &TM = Fn.getTarget();
00360   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
00361   const MRegisterInfo &MRI = *TM.getRegisterInfo();
00362 
00363   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
00364     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
00365       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00366         if (I->getOperand(i).isFrameIndex()) {
00367           // If this instruction has a FrameIndex operand, we need to use that
00368           // target machine register info object to eliminate it.
00369           MRI.eliminateFrameIndex(I);
00370           break;
00371         }
00372 }