LLVM API Documentation
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 }