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 #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 }