LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 using namespace llvm;
00028 
00029 namespace {
00030   struct PEI : public MachineFunctionPass {
00031     const char *getPassName() const {
00032       return "Prolog/Epilog Insertion & Frame Finalization";
00033     }
00034 
00035     /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
00036     /// frame indexes with appropriate references.
00037     ///
00038     bool runOnMachineFunction(MachineFunction &Fn) {
00039       // Scan the function for modified caller saved registers and insert spill
00040       // code for any caller saved registers that are modified.  Also calculate
00041       // the MaxCallFrameSize and HasCalls variables for the function's frame
00042       // information and eliminates call frame pseudo instructions.
00043       calculateCallerSavedRegisters(Fn);
00044 
00045       // Add the code to save and restore the caller saved registers
00046       saveCallerSavedRegisters(Fn);
00047 
00048       // Allow the target machine to make final modifications to the function
00049       // before the frame layout is finalized.
00050       Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn);
00051 
00052       // Calculate actual frame offsets for all of the abstract stack objects...
00053       calculateFrameObjectOffsets(Fn);
00054 
00055       // Add prolog and epilog code to the function.  This function is required
00056       // to align the stack frame as necessary for any stack variables or
00057       // called functions.  Because of this, calculateCallerSavedRegisters
00058       // must be called before this function in order to set the HasCalls
00059       // and MaxCallFrameSize variables.
00060       insertPrologEpilogCode(Fn);
00061 
00062       // Replace all MO_FrameIndex operands with physical register references
00063       // and actual offsets.
00064       //
00065       replaceFrameIndices(Fn);
00066 
00067       RegsToSave.clear();
00068       StackSlots.clear();
00069       return true;
00070     }
00071 
00072   private:
00073     std::vector<unsigned> RegsToSave;
00074     std::vector<int> StackSlots;
00075 
00076     void calculateCallerSavedRegisters(MachineFunction &Fn);
00077     void saveCallerSavedRegisters(MachineFunction &Fn);
00078     void calculateFrameObjectOffsets(MachineFunction &Fn);
00079     void replaceFrameIndices(MachineFunction &Fn);
00080     void insertPrologEpilogCode(MachineFunction &Fn);
00081   };
00082 }
00083 
00084 
00085 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
00086 /// prolog and epilog code, and eliminates abstract frame references.
00087 ///
00088 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
00089 
00090 
00091 /// calculateCallerSavedRegisters - Scan the function for modified caller saved
00092 /// registers.  Also calculate the MaxCallFrameSize and HasCalls variables for
00093 /// the function's frame information and eliminates call frame pseudo
00094 /// instructions.
00095 ///
00096 void PEI::calculateCallerSavedRegisters(MachineFunction &Fn) {
00097   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
00098   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
00099 
00100   // Get the callee saved register list...
00101   const unsigned *CSRegs = RegInfo->getCalleeSaveRegs();
00102 
00103   // Get the function call frame set-up and tear-down instruction opcode
00104   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
00105   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
00106 
00107   // Early exit for targets which have no callee saved registers and no call
00108   // frame setup/destroy pseudo instructions.
00109   if ((CSRegs == 0 || CSRegs[0] == 0) &&
00110       FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
00111     return;
00112 
00113   // This bitset contains an entry for each physical register for the target...
00114   std::vector<bool> ModifiedRegs(RegInfo->getNumRegs());
00115   unsigned MaxCallFrameSize = 0;
00116   bool HasCalls = false;
00117 
00118   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
00119     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); )
00120       if (I->getOpcode() == FrameSetupOpcode ||
00121           I->getOpcode() == FrameDestroyOpcode) {
00122         assert(I->getNumOperands() == 1 && "Call Frame Setup/Destroy Pseudo"
00123                " instructions should have a single immediate argument!");
00124         unsigned Size = I->getOperand(0).getImmedValue();
00125         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
00126         HasCalls = true;
00127         RegInfo->eliminateCallFramePseudoInstr(Fn, *BB, I++);
00128       } else {
00129         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
00130           MachineOperand &MO = I->getOperand(i);
00131           if (MO.isRegister() && MO.isDef()) {
00132             assert(MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
00133                    "Register allocation must be performed!");
00134             ModifiedRegs[MO.getReg()] = true;         // Register is modified
00135           }
00136         }
00137         ++I;
00138       }
00139 
00140   MachineFrameInfo *FFI = Fn.getFrameInfo();
00141   FFI->setHasCalls(HasCalls);
00142   FFI->setMaxCallFrameSize(MaxCallFrameSize);
00143 
00144   // Now figure out which *callee saved* registers are modified by the current
00145   // function, thus needing to be saved and restored in the prolog/epilog.
00146   //
00147   for (unsigned i = 0; CSRegs[i]; ++i) {
00148     unsigned Reg = CSRegs[i];
00149     if (ModifiedRegs[Reg]) {
00150       RegsToSave.push_back(Reg);  // If modified register...
00151     } else {
00152       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
00153            *AliasSet; ++AliasSet) {  // Check alias registers too...
00154         if (ModifiedRegs[*AliasSet]) {
00155           RegsToSave.push_back(Reg);
00156           break;
00157         }
00158       }
00159     }
00160   }
00161 
00162   if (RegsToSave.empty())
00163     return;   // Early exit if no caller saved registers are modified!
00164 
00165   unsigned NumFixedSpillSlots;
00166   const std::pair<unsigned,int> *FixedSpillSlots =
00167     TFI->getCalleeSaveSpillSlots(NumFixedSpillSlots);
00168 
00169   // Now that we know which registers need to be saved and restored, allocate
00170   // stack slots for them.
00171   for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) {
00172     unsigned Reg = RegsToSave[i];
00173 
00174     // Check to see if this physreg must be spilled to a particular stack slot
00175     // on this target.
00176     const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
00177     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
00178            FixedSlot->first != Reg)
00179       ++FixedSlot;
00180 
00181     int FrameIdx;
00182     if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) {
00183       // Nope, just spill it anywhere convenient.
00184       FrameIdx = FFI->CreateStackObject(RegInfo->getSpillSize(Reg)/8,
00185                                         RegInfo->getSpillAlignment(Reg)/8);
00186     } else {
00187       // Spill it to the stack where we must.
00188       FrameIdx = FFI->CreateFixedObject(RegInfo->getSpillSize(Reg)/8,
00189                                         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], StackSlots[i]);
00212   }
00213 
00214   // Add code to restore the callee-save registers in each exiting block.
00215   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
00216   for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI) {
00217     // If last instruction is a return instruction, add an epilogue
00218     if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) {
00219       MBB = FI;
00220       I = MBB->end(); --I;
00221 
00222       for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) {
00223         RegInfo->loadRegFromStackSlot(*MBB, I, RegsToSave[i],StackSlots[i]);
00224         --I;  // Insert in reverse order
00225       }
00226     }
00227   }
00228 }
00229 
00230 
00231 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
00232 /// abstract stack objects...
00233 ///
00234 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
00235   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
00236   
00237   bool StackGrowsDown =
00238     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
00239  
00240   // Loop over all of the stack objects, assigning sequential addresses...
00241   MachineFrameInfo *FFI = Fn.getFrameInfo();
00242 
00243   unsigned StackAlignment = TFI.getStackAlignment();
00244 
00245   // Start at the beginning of the local area.
00246   // The Offset is the distance from the stack top in the direction
00247   // of stack growth -- so it's always positive.
00248   int Offset = TFI.getOffsetOfLocalArea();
00249   if (StackGrowsDown)
00250     Offset = -Offset;
00251   assert(Offset >= 0 
00252          && "Local area offset should be in direction of stack growth");
00253 
00254   // If there are fixed sized objects that are preallocated in the local area,
00255   // non-fixed objects can't be allocated right at the start of local area.
00256   // We currently don't support filling in holes in between fixed sized objects, 
00257   // so we adjust 'Offset' to point to the end of last fixed sized
00258   // preallocated object.
00259   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
00260     int FixedOff;
00261     if (StackGrowsDown) {
00262       // The maximum distance from the stack pointer is at lower address of
00263       // the object -- which is given by offset. For down growing stack
00264       // the offset is negative, so we negate the offset to get the distance.
00265       FixedOff = -FFI->getObjectOffset(i);
00266     } else {
00267       // The maximum distance from the start pointer is at the upper 
00268       // address of the object.
00269       FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
00270     }    
00271     if (FixedOff > Offset) Offset = FixedOff;            
00272   }
00273 
00274   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
00275     // If stack grows down, we need to add size of find the lowest
00276     // address of the object.
00277     if (StackGrowsDown)
00278       Offset += FFI->getObjectSize(i);
00279 
00280     unsigned Align = FFI->getObjectAlignment(i);
00281     assert(Align <= StackAlignment && "Cannot align stack object to higher "
00282            "alignment boundary than the stack itself!");
00283     Offset = (Offset+Align-1)/Align*Align;   // Adjust to Alignment boundary...
00284     
00285     if (StackGrowsDown) {
00286       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
00287     } else {
00288       FFI->setObjectOffset(i, Offset); 
00289       Offset += FFI->getObjectSize(i);
00290     }
00291   }
00292 
00293   // Align the final stack pointer offset, but only if there are calls in the
00294   // function.  This ensures that any calls to subroutines have their stack
00295   // frames suitable aligned.
00296   if (FFI->hasCalls())
00297     Offset = (Offset+StackAlignment-1)/StackAlignment*StackAlignment;
00298 
00299   // Set the final value of the stack pointer...
00300   FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea());
00301 }
00302 
00303 
00304 /// insertPrologEpilogCode - Scan the function for modified caller saved
00305 /// registers, insert spill code for these caller saved registers, then add
00306 /// prolog and epilog code to the function.
00307 ///
00308 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
00309   // Add prologue to the function...
00310   Fn.getTarget().getRegisterInfo()->emitPrologue(Fn);
00311 
00312   // Add epilogue to restore the callee-save registers in each exiting block
00313   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
00314   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
00315     // If last instruction is a return instruction, add an epilogue
00316     if (!I->empty() && TII.isReturn(I->back().getOpcode()))
00317       Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I);
00318   }
00319 }
00320 
00321 
00322 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
00323 /// register references and actual offsets.
00324 ///
00325 void PEI::replaceFrameIndices(MachineFunction &Fn) {
00326   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
00327 
00328   const TargetMachine &TM = Fn.getTarget();
00329   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
00330   const MRegisterInfo &MRI = *TM.getRegisterInfo();
00331 
00332   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
00333     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
00334       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00335         if (I->getOperand(i).isFrameIndex()) {
00336           // If this instruction has a FrameIndex operand, we need to use that
00337           // target machine register info object to eliminate it.
00338           MRI.eliminateFrameIndex(I);
00339           break;
00340         }
00341 }